位图（std::vector<bool>）不能直接当去重集合用，因其底层按位存储、迭代器解引用返回代理对象、不支持取地址、缺乏find/count等集合接口，且映射需确保数据范围可穷举、非负、无冲突。
位图（std::vector<bool></bool>）为什么不能直接当去重集合用？
它能省空间，但不是万能的“去重容器”。std::vector<bool></bool> 是特化实现，底层按位存储，不支持取地址、迭代器解引用返回的是代理对象——这意味着你没法把它当普通容器塞进 std::set 或传给需要真实 bool& 的算法。
常见错误现象：auto& b = bitmap[i]; b = true; 看似正常，但 b 是临时代理；后续再读可能失效，尤其在跨函数或优化开启时。更隐蔽的问题是：它不提供 find、count 这类集合语义接口。
- 真要用位图做去重，核心逻辑必须自己写：把数据映射到索引，再查/设对应位
- 映射前务必确认数据范围可穷举（比如只处理
[0, 10^7)的整数） - 别试图用
std::vector<bool></bool>替代std::unordered_set<int></int>去存任意整数——越界或负数会直接崩
怎么安全地把整数映射到位图索引？
映射不是简单 i % size，而是要保证无冲突、可逆、且覆盖全集。最常用的是“值即索引”：若已知所有输入都在 [0, N) 内，就直接用值当索引。
使用场景举例：日志中提取用户 ID（假设已知 ID 全是 0~9999999 的正整数），想统计出现过哪些 ID。
立即学习“C++免费学习笔记（深入）”；
- 先确定最大值：
constexpr size_t MAX_ID = 10'000'000; - 声明位图：
std::vector<bool> seen(MAX_ID);</bool> - 处理每个 ID
x前，必须检查x >= 0 && x ，否则越界访问未定义行为 - 负数或超大数要提前过滤，或改用布隆过滤器（Bloom Filter）这类概率结构
std::bitset 和手动 uint64_t[] 哪个更适合海量数据？
std::bitset 编译期定长、零拷贝、支持 &/| 等位运算，但大小必须是常量表达式，无法应对运行时才知规模的场景。而手写 uint64_t* 数组灵活，但得自己算偏移、掩码、边界。
性能影响明显：现代 CPU 对 uint64_t 的位操作（如 bts 指令）比 std::vector<bool></bool> 的封装调用快得多，尤其批量置位时。
- 若数据规模固定且不大（std::bitset 最省心
- 若需动态分配几 GB 位图（比如 10⁹ 位），用
std::unique_ptr<uint64_t></uint64_t>+ 手动位操作更可控 - 注意对齐：
aligned_alloc或posix_memalign分配 64 字节对齐内存，避免某些 SIMD 指令报错
去重后怎么高效遍历所有“已出现”的值？
位图本身不存值，只存“是否出现”，所以遍历本质是扫描 + 解码。别用 for (int i = 0; i —— 这是 O(N)，而实际活跃数据可能只有千分之一。
更优做法是逐字（word）扫描，用内置函数跳过全零字：
for (size_t word_i = 0; word_i < words.size(); ++word_i) {
uint64_t w = words[word_i];
while (w) {
int tz = __builtin_ctzll(w); // GCC/Clang 获取最低位 1 的位置
int val = word_i * 64 + tz;
// val 就是实际出现过的值
w &= w - 1; // 清除最低位 1
}
}
-
__builtin_ctzll在 x86 上编译为tzcnt指令，极快；但输入为 0 时行为未定义，务必先判非零 - Windows 下用
_BitScanForward64，需包含<intrin.h> - 如果后续还要排序或随机访问，别硬扫——直接把结果存进
std::vector<int></int>，空间开销通常远小于原位图
真正难的不是建位图，而是确保映射不漏、不重、不越界；还有就是别忘了：位图只解决“存在性”，没存原始数据、没顺序、也没计数——这些需求一多，就得换方案了。
