Bitmap不能直接用于任意整数去重，因其仅适用于非负、范围已知且密集的整数；负数需偏移处理，超大值或稀疏数据会导致内存爆炸或极低利用率。
Bitmap 位图为什么不能直接用于任意整数去重
Bitmap 本质是用 1 bit 表示一个整数是否存在，但它只适合处理**非负、范围已知且密集**的整数。比如你有一亿个 [0, 99999999] 范围内的整数，std::vector 或手动管理的 uint8_t* 就很合适；但一旦数据含负数、超大值（如 2^40）、或极度稀疏（仅几个数落在极大范围内），直接建 Bitmap 会爆内存或根本不可行。
常见错误现象：std::bad_alloc、程序启动就 OOM、位图实际使用率低于 0.001% 却占了几 GB 内存。
- 判断是否适用：先统计数据 min/max 和 distinct count，若
max - min > 2^32或(max - min) / distinct_count > 1000，别硬上 Bitmap - 负数必须偏移：把
[-1000, 5000]映射成[0, 6000]，偏移量 =-min，注意 int 溢出风险 - 64 位索引需用
uint64_t算位地址，index / 8得字节偏移，index % 8得位偏移，别用int截断
手写高效 Bitmap 类要避开的三个坑
STL 的 std::vector 是代理类，不支持取地址、迭代器行为异常，做海量数据去重时性能差且易出错。自己封装更可控。
实操建议：
- 底层用
std::vector或std::unique_ptr，避免vector - set/get 操作必须内联 + 用位运算：例如
bits_[i >> 3] |= (1U ，别调用函数封装位操作（函数调用开销在百亿次操作中显著） - 构造时按字节对齐预分配，比如需要 1000000001 bit，算成
(n + 7) / 8字节，别少一分——否则i >> 3可能越界 - 多线程写入需加锁或分段 Bitmap（如按高 16 位哈希分桶），单锁会成为瓶颈
当数据超出内存怎么办：Bitmap 分片 + 外部归并思路
纯内存 Bitmap 面对几百 GB 原始数据必然失败。真正“海量”的解法不是更大内存，而是分治：把 key 映射到固定数量的桶（如 256 个文件），每个桶内用独立 Bitmap 处理，最后合并结果。
关键点：
- 分桶哈希别用
key % 256（负数取模行为不一致），改用(static_cast(key) >> offset) & 0xFF - 每个分片 Bitmap 大小按该桶实际数据范围动态分配，而非统一最大范围，省 90%+ 空间
- 最终去重结果不一定要全加载进内存：可边扫描分片、边写入
std::set或排序后归并输出到文件 - 磁盘 I/O 是瓶颈，用
posix_fadvise(POSIX_FADV_DONTNEED)或内存映射mmap提升顺序读性能
替代方案比强行优化 Bitmap 更实用的场景
如果你的数据是字符串、浮点数、或带结构的 ID（如 UUID），Bitmap 从根上就不适配。这时候硬搞位图压缩、布隆过滤器再接哈希表，不如直接换路子。
真实项目中更常见的有效组合：
- 字符串去重：用
roaring bitmap（支持 64 位、压缩好、有 C++ 绑定）+xxhash转成 uint64_t，比手写快且省内存 - 日志 ID（如 trace_id）：先抽前 8 字节转
uint64_t，用absl::flat_hash_set，插入平均 O(1)，10 亿条约 12 GB 内存，比 Bitmap 分片实现简单稳定 - 需要存在性检查但允许误判：用
boost::dynamic_bitset配合布隆过滤器两层，首层快速筛掉 99% 不存在项
最常被忽略的一点：Bitmap 的优势只在「范围小 + 密集 + 纯整数 + 写一次读多次」场景成立。其他情况，先跑个 awk '{print $1}' data.log | sort -u | wc -l 估算下基数和分布，比立刻敲代码重要得多。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
