bitmap去重本质是值域映射+位操作+边界严控；其参数为最大可能输入值（非元素个数），合法索引范围是[0, max_val]，越界访问将导致静默错误或崩溃。
位图去重不是“把数据塞进去再遍历出来”那么简单，它本质是值域映射 + 位操作 + 边界严控。如果你的数据含负数、重复、或最大值远超实际分布，std::vector<bool></bool> 或手写 Bitmap 都会静默出错或崩溃。
为什么 set(100) 在 Bitmap(100) 下直接越界？
构造时传入的 n 是逻辑上支持的最大整数（即值域上限），但合法索引范围是 [0, n - 1]。调用 set(100) 时，计算得 i = 100 / 32 = 3，而 bits 实际只分配了 (100 + 31) / 32 = 4 个 uint32_t，下标 3 合法；但若你误以为 Bitmap(100) 能存 100 个数，又往里塞 100 这个值，就踩中了“值即索引”的前提漏洞——100 已超出 [0, 99] 范围。
-
Bitmap(size_t max_val)的参数必须是「最大可能输入值」，不是「输入个数」 - 构造内部应为
bits.resize((max_val + 31) / 32)，而非(n + 31) / 32模糊命名 -
set()中必须有if (i >= size) return;，且size应等于max_val + 1（即索引上限） - 更安全做法：用
std::vector<uint32_t>::at(i / 32)</uint32_t>替代[]，调试期自动抛std::out_of_range
std::vector 为什么不能当去重容器直接用？
它底层是位压缩特化，bitmap[i] 返回的是代理对象 std::vector<bool>::reference</bool>，不是真实 bool&。这意味着：
- 不能取地址：
&bitmap[i]编译失败 - 不能用于需要真实引用的算法，比如
std::find_if带引用谓词时行为未定义 - 迭代器解引用返回临时代理，跨表达式生命周期不可靠（尤其开 O2 优化后）
- 没有
count()、find()等集合语义接口，你得自己循环 +test()
真要快速判重，老实用 std::unordered_set；非要省空间，就手写 uint32_t* 或 std::bitset（编译期大小已知时）。
如何安全地把任意整数映射到位图索引？
“值即索引”只在数据满足「全为非负整数且 ∈ [0, MAX)」时成立。现实数据往往带偏移或符号，必须显式归一化：
- 若原始数据是用户 ID，范围已知为
[100000, 10999999]，先做x -= 100000，再喂给Bitmap(10900000) - 若含负数，拆成正负两个位图：
pos_bitmap存 ≥0 数，neg_bitmap存绝对值（-x），查-5就查neg_bitmap.test(5) - 若值域极大（如
int64_t全范围）但数据稀疏，位图失效——该换布隆过滤器或 Roaring Bitmap - 永远在
set()前加校验：if (x = max_val) continue;，别指望位图替你过滤脏数据
遍历位图提取所有“存在”的值有多慢？
位图不存值，只存状态。输出去重结果必须扫描整个值域，时间复杂度是 O(MAX_VALUE)，不是 O(input_size)。例如输入只有 {0, 1, 1000000}，你也得从 i = 0 遍历到 i = MAX_VALUE - 1 才能确保不漏掉 1000000。
- 若
MAX_VALUE是1e9，哪怕只设了 3 个位，也要执行1e9次循环+位运算 - 优化手段有限：可用
__builtin_popcount加速单字计数，但无法跳过空段；Roaring Bitmap 支持按块跳过全零区域 - 真正瓶颈常不在位操作本身，而在内存访问模式——连续扫描大位图易触发缓存失效
- 如果业务只要“是否存在”，根本不用遍历；如果真要枚举，说明你选错了结构——
std::unordered_set枚举是O(n)，与输入规模正相关
最难的从来不是写出 bits[i >> 5] |= (1U ，而是确认你的数据真的满足「非负、无重复、值域可控、内存卡死」这四个硬约束。少一个，位图就从加速器变成定时炸弹。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
