位图是布尔数组的压缩表示，用std::vector或std::bitset按位存储非负整数存在性；适用于值域可控场景，最大值超2^31时需手动实现动态位图。
位图Bitmap的本质是布尔数组的压缩表示
位图不是某种特殊容器，而是用 std::vector<uint8_t></uint8_t> 或 std::bitset 按位存布尔值：每个 bit 代表一个整数是否存在。比如第 137 位为 1，表示数字 137 已出现过。它只适用于**非负整数**且值域相对可控的场景（如 0~1 亿），否则内存爆炸或索引越界。
关键判断点：若数据最大值 max_val 超过 2^31（约 21 亿），std::bitset 在多数编译器下会编译失败；改用 std::vector<uint8_t></uint8_t> 手动位操作更稳妥。
手写位图：用 std::vector<uint8_t></uint8_t> 实现动态大小
标准库没提供运行时可调大小的位图，必须自己算字节偏移和位偏移。核心是两个宏/内联函数：
-
byte_index = n / 8—— 第几个字节 -
bit_offset = n % 8—— 该字节内第几位（从低位起）
设置某位为 1：bits[byte_index] |= (1U ；判断是否已存在：<code>(bits[byte_index] & (1U 。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
示例片段（去重主逻辑）：
std::vector<uint8_t> bitmap((max_val + 7) / 8, 0); // 向上取整字节数
for (int x : input_data) {
if (x < 0 || x > max_val) continue; // 跳过非法值
size_t byte_idx = x / 8;
size_t bit_idx = x % 8;
if ((bitmap[byte_idx] & (1U << bit_idx)) == 0) {
bitmap[byte_idx] |= (1U << bit_idx);
unique_result.push_back(x);
}
}
用 std::bitset 的前提和陷阱
std::bitset 只接受编译期常量大小，比如 std::bitset。如果你的数据范围是 0~9999999，它很合适；但若范围来自配置文件或运行时计算，就无法直接用。
常见错误：
- 写成
std::bitset<n></n>却让N是变量 → 编译报错non-type template parameter is not a constant expression - 忽略内存对齐和缓存局部性：超大
std::bitset（如 1 亿 bit ≈ 12.5 MB）在随机访问时可能比连续uint8_t数组慢 - 未初始化：
std::bitset默认零初始化，但手动分配的uint8_t数组必须显式std::vector<uint8_t>(size, 0)</uint8_t>，否则含脏数据
实际去重流程中必须处理的边界问题
真实数据不会“刚好”全是 0~N 的正整数。以下几点漏掉一个，结果就错：
- 负数必须过滤或偏移处理（如全部加
offset映射到非负区间） - 重复值可能极多，但位图本身不记录频次，仅能判“有/无”，需额外逻辑区分“首次出现”和“后续重复”
- 内存限制：1 亿个数的位图占 12.5 MB；10 亿个数则要 125 MB —— 若机器只有 64 MB 堆空间，得切分数据块或换布隆过滤器
- 线程安全：多个线程同时写同一 bit 会丢数据，必须加锁或按数据范围分片（如线程 A 处理 [0,1e6)，B 处理 [1e6,2e6)）
真正难的不是位运算本身，而是把原始数据清洗、映射、分块、合并这一整条链路串稳。位图只是其中一环，而且是最容易假定“没问题”的一环。
