位图排序的核心优势是省空间，但前提是数据范围已知且集中；若范围过大、稀疏或含负数，需动态分段、平移或改用多级桶+局部位图。
位图排序（Bitmap Sort）在 C++ 中处理海量整数数据时，核心优势不是“快”，而是“省空间”——但这个“省”是有严格前提的：数据范围必须已知且相对集中（比如 0～10⁷ 内的 10⁶ 个整数）。一旦范围过大（如 int32 全集）、稀疏（如只有千分之一的数被使用）或含负数/大偏移，直接套用 std::vector<bool></bool> 或 std::bitset 就会吃满内存甚至崩溃。
为什么不能直接用 std::bitset<int_max></int_max>？
编译器会直接报错或静默截断：INT_MAX 是 2147483647，std::bitset 需要约 268 MB 连续栈/编译期内存，绝大多数编译器不支持；即使改用堆分配，new bool[INT_MAX] 也需 2 GB 内存（未压缩），远超位图本意。实际中必须按数据实际范围动态分段或映射。
- 先扫描一遍输入，得到
min_val和max_val，确认跨度range = max_val - min_val + 1 - 若
range > 1e8（约 12.5 MB 原始位图），放弃单层位图，改用多级桶 + 局部位图（见下节） - 负数必须平移：所有值减
min_val，使最小值变为 0，否则索引越界 -
std::vector<bool></bool>是特化代理类，迭代器行为异常，别对它取地址或传&v[0]
如何用 std::vector<uint8_t></uint8_t> 手动实现可寻址位图？
比 std::vector<bool></bool> 更可控、兼容性更好，支持指针运算和 mmap 直接加载。每个 uint8_t 存 8 个 bit，索引换算为：byte_idx = val / 8，bit_offset = val % 8。
void set_bit(std::vector<uint8_t>& bitmap, size_t val) {
size_t byte_idx = val / 8;
uint8_t bit_mask = 1 = bitmap.size()) bitmap.resize(byte_idx + 1, 0);
bitmap[byte_idx] |= bit_mask;
}
<p>bool get_bit(const std::vector<uint8_t>& bitmap, size_t val) {
size_t byte_idx = val / 8;
if (byte_idx >= bitmap.size()) return false;
return bitmap[byte_idx] & (1 </uint8_t></p></uint8_t>
- 不要用
std::vector<bool>::operator[]</bool>返回的 proxy 对象做&取地址——它不是真实引用 - resize 前检查是否需要扩展，避免每次 set 都无脑 push_back（影响缓存局部性）
- 批量写入时，优先按字节填充再按位置位，比逐 bit 调用
set_bit快 3–5 倍
面对 10⁹ 级数据范围，怎么避免 O(N) 内存爆炸？
用两级结构：外层是稀疏哈希表（std::unordered_map<size_t std::vector>></size_t>），key 是高位桶号（如 val / 65536），value 是对应 64K 范围的紧凑位图。这样内存只分配“有数据的桶”。
- 桶大小选 65536（2¹⁶）：便于位运算（
val >> 16取桶号，val & 0xFFFF取桶内偏移） - 插入时先算
bucket = val >> 16，再查 map 是否存在该 key；不存在则 emplace 一个 8KB 的vector<uint8_t>(8192)</uint8_t> - 遍历时按 bucket key 排序，再对每个桶内位图从 0 到 65535 扫描 bit —— 保证输出有序
- 如果数据极度稀疏（比如每桶平均不到 10 个数），改用
std::set或 Roaring Bitmap 库更合适
真正难的不是写对位图逻辑，而是预判数据分布——没做 range 分析就开位图，和没看说明书就拧高压阀一样。线上环境里，一个没处理 min_val 为负的 case，会让整个位图索引全偏移，结果输出全是错的数，还很难 debug。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
