位图排序适合海量整数去重与排序，因其用1 bit表示一个整数是否存在，空间比vector或哈希表低32–64倍，时间复杂度O(N+M)，但要求数据为范围已知、非负、无重复的密集整数。
位图排序为什么适合海量数据
位图排序在数据范围已知且密集时，能把时间复杂度压到 O(n)，空间换时间效果显著——但前提是“海量”指的是数量大（比如上亿个整数），而非值域大（比如 [0, 2^32)）。一旦值域过大，std::vector<bool></bool> 或手动位数组会直接爆内存。真实场景中，得先确认数据分布：若原始数据是 1 亿个 [0, 10^7) 内的 int，位图才真正划算；若值域接近 INT_MAX，就得切分或改用其他结构。
如何用 std::vector<bool></bool> 正确建位图
std::vector<bool></bool> 是特化容器，内部按位存储，节省空间，但不支持取地址、迭代器解引用返回的是 proxy 对象——这意味着不能直接传给需要 bool* 的函数，也不能用 &v[i] 做位运算。常见错误是误以为它和普通 vector 行为一致：
std::vector<bool> bitmap(10000000, false); bitmap[123456] = true; // ✅ 可行 auto ptr = &bitmap[0]; // ❌ 编译失败：no operator& for proxy
实操建议：
- 用
operator[]单点设置/查询，别试图取地址或做指针算术 - 若需批量操作（如 memset 风格初始化），改用
std::vector<uint8_t>+ 手动位运算，控制更稳 - 构造时显式指定容量，避免多次扩容导致的隐式拷贝（尤其在百亿位级时）
跨平台位操作必须注意字节序与对齐
当自己封装位数组（如用 uint64_t* 管理），位索引到内存偏移的转换极易出错。典型陷阱是假设 bit_index / 64 就是数组下标、bit_index % 64 就是位偏移——这在所有主流平台都成立，但若后续要序列化到位图文件或网络传输，就必须统一字节序。例如：
立即学习“C++免费学习笔记（深入）”；
// 错误：依赖本地平台字节序写入文件 fwrite(bitmap_data, sizeof(uint64_t), len, fp); // 正确：按网络序（大端）逐字节写，或明确标注格式为小端并文档化
另外，uint64_t* 指针必须 8 字节对齐，否则在 ARM 或某些 x86 模式下触发 bus error。分配时优先用 aligned_alloc(64, size) 或 std::vector<uint64_t>（其分配器通常保证对齐）。
查找加速：跳表结构比纯位扫描快得多
纯位图排序后输出，只需遍历每一位检查是否为 1；但若还需支持“找第 k 个数”或“是否存在 x”，逐位扫描最坏 O(N)。此时可在位数组之上叠加稀疏索引——比如每 65536 位存一个累计计数（popcount），构成一级跳表：
- 索引数组大小仅为原位图的 1/65536，内存开销可忽略
- 找第 k 个数：先二分索引数组定位块，再在块内线性扫描，从
O(N)降到O(65536) - 存在性查询仍为
O(1)，但范围统计（如 [a,b] 内有多少数）可做到O(log N)
这个优化不是银弹：索引本身要维护，插入动态数据时成本上升；但对只构建一次、查询多次的离线排序场景，非常值得。
位图排序真正的难点不在逻辑，而在边界——值域估算偏差 10 倍，内存就差 10 倍；位偏移算错一位，整个数据就错位；跨平台序列化不加约束，同一份位图在不同机器上解析结果可能完全相反。
