Bitmap适合海量整数去重，因其用1bit标识一个数是否存在，512MB内存即可覆盖0～42.9亿整数范围，比哈希表至少节省8倍空间，但仅适用于值域明确、稠密的无符号整数场景。
Bitmap 为什么适合海量整数去重
Bitmap 的核心优势不是“快”，而是“省空间”——当数据是 unsigned int 范围内（0～4294967295）的整数，且分布相对稠密时，用 1 bit 表示一个数是否存在，512 MB 内就能覆盖全部 42.9 亿个值。比 std::unordered_set<uint32_t> 至少省 8 倍内存（后者每个元素至少占 8 字节 + 哈希桶开销）。但注意：它只适用于值域明确、可枚举的整数场景，遇到负数、浮点、字符串或稀疏到百万级却跨万亿范围的数据，直接失效。
常见误用现象：std::vector<bool> 被当成 Bitmap 用——它虽节省空间，但不支持原子位操作、无随机访问优化、迭代器行为异常，且多线程下 operator[] 非线程安全。真正生产级 Bitmap 应基于 std::vector<uint64_t> 或 std::bitset（编译期大小固定）手动管理位偏移。
如何手写线程安全的 uint32_t Bitmap 类
关键在把 uint32_t 值映射到数组索引和位偏移：用 index = value / 64 定位 uint64_t 元素，offset = value % 64 定位该元素内的位。所有位操作必须用原子指令（如 __atomic_or_fetch）或加锁，否则并发 set() 会丢位。
- 用
std::vector<std::atomic<uint64_t>>存储位块，初始化为 0 -
set(uint32_t x)：检查x <= UINT32_MAX，计算idx = x >> 6，bit = x & 0x3F，执行data[idx].fetch_or(1ULL << bit, std::memory_order_relaxed) -
test(uint32_t x)：同样算出idx和bit，返回(data[idx].load(std::memory_order_relaxed) >> bit) & 1U - 避免用
std::bitset<N>动态分配——N必须是编译期常量，无法适配运行时决定的值域上限
处理超 4GB 数据时的分片与磁盘回写策略
单机内存有限，若去重数据总量达百亿级（比如日志中的用户 ID），即使 Bitmap 只需 1.25 GB（10^10 bits ≈ 1.25 GB），也建议分片：按高位哈希（如 x >> 24）将数据路由到 256 个子 Bitmap，每个约 5 MB。这样既降低单次内存压力，又便于并行构建和后续合并。
立即学习“C++免费学习笔记（深入）”；
更关键的是落盘时机：不要等全量数据读完再写，而应在内存使用达阈值（如 800 MB）时，将已处理的 Bitmap 序列化为二进制文件（write(fd, data.data(), data.size() * sizeof(uint64_t))），清空内存后继续。合并阶段用 mmap 映射多个文件，逐块 |= 操作，避免全量加载。
容易踩的坑：fseek + fwrite 随机写位图文件极慢；未对齐的 read() 会触发内核拷贝；std::ofstream 默认带缓冲但不保证原子刷盘，紧急场景要用 fsync()。
Bitmap 去重结果怎么导出成唯一整数列表
Bitmap 本身不存原始数据顺序，导出唯一值本质是“遍历所有置位的 bit”。最朴素做法是两层循环：外层遍历 vector<uint64_t>，内层用 __builtin_ctzll() 找最低位 1，再清除该位（x &= x-1），直到为 0。但这样会破坏原 Bitmap，且对稀疏数据效率低（比如每 64 位只有 1 个 1，要查 64 次）。
更实用的做法：
- 保留原始 Bitmap 不动，另开一个
std::vector<uint32_t>接收结果 - 对每个
uint64_t block，用while (block) { uint32_t pos = __builtin_ctzll(block); result.push_back(idx * 64 + pos); block &= block - 1; } - 若需排序输出，直接 push 后调用
std::sort；若只需去重后计数，累加__builtin_popcountll(block)即可，不用遍历 - 注意：Windows 下
__builtin_ctzll在 MSVC 不可用，应改用_BitScanForward64或封装跨平台宏
真正的复杂点不在算法，而在值域边界判断和内存映射对齐——比如 mmap 文件长度不是 64 的倍数时，最后一块读取要截断，否则可能触发 SIGBUS。
