C++实现基于位图(Bitmap)的高效排序 _ 海量数据处理技巧【源码】

先说一个关键判断：位图排序在特定约束下——数据无重复、值域已知、内存卡死——确实是唯一可行的线性时间方案。但它的前提条件极其苛刻，远没有看上去那么简单。

熟悉C++位运算的老手都知道，高效排序的关键藏在那些看似基础的位操作里，但恰恰是这些操作，稍不留神就会踩坑。接下来，我们逐一拆解这些常见的陷阱。

为什么位图排序要求数据不能重复

位图的本质就是一张布尔映射表：每个bit只能记录0或1，表示“还没出现”或者“已经有了”。如果你给进去两个一模一样的5，那第二次调用set(5)的时候，虽然程序不会报错，但bit状态也不会改变——频次信息永远丢了，原始的重复序列也注定无法复原。排序结果看起来没错，可实际上它悄悄帮你做了去重，跟原始需求根本不是一码事。

• 最常见的错误现象：bitmap_sort({5, 5, 3})输出 {3, 5}，而不是 {3, 5, 5}
• 它真正适合的场景是：日志去重统计、IP黑白名单判定、整数集合归并这类“只看有没有，不问有几个”的任务
• 如果一定要保留重复值，那就得升级方案——要么用计数位图（每个元素占多个bit），要么老老实实退回std::unordered_map

set()和test()的位运算细节必须对齐

这里有三组常量必须保持一致，缺一不可：WORD == 32、SHIFT == 5、MASK == 0x1f。它们共同定下了一个约定——每32个整数打包成一个uint32_t。但凡有一项算错了，整个位偏移都会乱套。

• 常见陷阱：有的人i % 32写成i & 0x1f，这在32位整数里没问题，但如果数组类型换成了uint64_t却还沿用SHIFT == 5，那就只能覆盖到低32位，高32位根本无人管
• 推荐的统一写法是全部用位运算：bits[i >> 5] |= (1U << (i & 0x1f))，这样避免了除法和取模的开销
• 一个容易忽略的细节：必须用1U而不是1。因为如果左移超过31位，1是默认有符号整数，可能会触发符号扩展的未定义行为

内存边界检查不能只靠size成员变量

构造时传入的参数n，代表这个位图能表示的最大整数是n - 1。但实际分配的bits数组大小是(n + 31) / 32个uint32_t。如果你脑子一热去调用set(n)，那访问bits[n / 32]的时候就已经越界了。

• 典型的崩盘点：Bitmap bm(100); bm.set(100); → 访问bits[3]，越界
• 修复方式很简单：在set()和get()里加一句if (i >= size) return;，这里的size应该是最大允许索引加1
• 更稳妥的做法是用std::vector::at()代替[]，这样在调试阶段一跑就崩，马上能发现越界

位图排序的输出循环必须遍历整个值域，不是输入长度

排序结果的输出过程，取决于值域有多大，而不是输入了多少个数。比如你只给了三个数{1, 9999999, 0}，那也得老老实实从i = 0一路扫到i = MAX_VALUE - 1，否则中间那个大数字就会被漏掉。

• 性能上的大坑：如果值域极大（比如MAX_VALUE == 2^31），而数据分布又极其稀疏，那遍历的时间开销会远远超过输入规模
• 兼容性问题：在32位系统上，MAX_VALUE > 2^31会导致int溢出，必须统一使用size_t或uint64_t
• 真实项目中的标准做法：把值域上限作为模板参数传进去，比如BitmapSort<10000000>，让编译器在编译期就能做一次校验

说到底，真正难的不是写对那几行位操作，而是事先问清楚自己：业务是否真的满足“无重复、值域可控、内存卡死”这三大前提？任意一条没想清楚就直接上位图排序，它就不是银弹，而是定时冲击波。