不能直接用std::vector<bool>做海量去重，因其是特化容器，operator[]返回代理对象，不支持取地址、指针运算、原子操作及SIMD加速，迭代器行为异常，实测性能比手写uint64_t位操作慢3–5倍。
Bitmap 为什么不能直接用 std::vector<bool></bool> 做海量去重
它不是真正意义上的位容器——std::vector<bool></bool> 是特化实现，内部虽按位存储，但operator[] 返回的是代理对象（std::vector<bool>::reference</bool>），无法取地址、不支持指针算术，且迭代器行为异常；在高频随机写入（如亿级整数标记）时，编译器难优化，实测比裸 uint64_t* 慢 3–5 倍。更关键的是：它不提供原子位操作接口，多线程并发标记会出错。
手写 Bitmap 必须自己管理内存对齐和跨字节寻址
核心是把整数 n 映射到具体字节 + 具体位：byte_index = n / 8，bit_offset = n % 8。但真实场景中，必须用 size_t 对齐（如 64 位平台用 uint64_t 为单位），否则 cache line 利用率低。正确做法是：
- 容量按
ceil(n / 64)计算uint64_t元素个数，而非字节数 - 设置位：用
data[idx] |= (1ULL ，注意 <code>1ULL强制 64 位无符号，避免1 溢出为负 - 检查位：用
(data[idx] & (1ULL ，别漏括号，C++ 运算符优先级里 <code>&低于!= - 清零整块：调用
memset(data, 0, bytes)，别用循环赋 0，后者编译器未必能向量化
查找阶段要规避分支预测失败导致的性能断崖
当你要查「某个数是否出现过」，看似一个 get(n) 就完事，但实际部署中，如果查询序列高度随机（比如日志 ID 查重），CPU 分支预测器会大量失效。解决方案不是换算法，而是调整访问模式：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 批量查询时，把待查数组按
n % 64分桶，同一桶内n的idx相近，提升 cache 局部性 - 单次查询务必内联，函数体控制在 10 行内，GCC/Clang 下加
[[gnu::always_inline]] - 不要在
get()里做范围检查（如n >= capacity），上线前用assert或构建时静态断言，运行时检查成本太高
源码里最容易被忽略的三个边界
实战中 80% 的崩溃来自这三个点，不是逻辑错，是位运算惯性思维导致：
立即学习“C++免费学习笔记（深入）”；
-
n = 0：0 / 64 = 0，0 % 64 = 0，没问题；但若你误写成n >> 6和n & 63，那0没问题，可一旦n是有符号负数（比如读错二进制数据），>>是算术右移，结果错乱 -
n刚好等于容量上限：比如申请了1ULL 个 bit，最大合法 <code>n是(1ULL ；若传入 <code>1ULL ，<code>idx = n >> 6会越界，但不会触发std::vector的 bounds check（你用的是裸指针） - 多线程写入未加锁或未用原子操作：即使只设位，x86 上
or byte ptr [rax], 1是原子的，但or qword ptr [rax], 1不是——64 位写入在某些 CPU 上可能分两步，必须用__atomic_or_fetch(&data[idx], mask, __ATOMIC_RELAXED)
位图本身没魔法，赢在确定性：O(1) 时间、精确去重、内存占用可预测。但所有优势，都建立在你亲手踩过这三道坎之后。
