位图排序适合海量整数去重+排序，因其用1 bit表示一个整数是否存在，空间比vector或哈希表低32–64倍，且排序即遍历位图，时间复杂度O(N + M)；但要求数据为范围已知、非负、无重复的密集整数。
位图排序为什么适合海量整数去重+排序？
位图排序本质是用 1 bit 表示一个整数是否存在，空间比 std::vector<int></int> 或哈希表低 32–64 倍。它不适用于任意浮点数或字符串，但对「范围已知、非负、密集分布」的整数（比如 0～10⁷ 内的 ID 列表）效果极佳——排序即遍历位图，时间复杂度 O(N + M)，其中 M 是值域上限。
关键前提：你得能接受「内存占用与值域上限线性相关」，而不是与输入数据量线性相关。如果数据范围是 0～2³²−1，直接建 512MB 位图显然不可行；这时必须分段或改用其他结构。
如何用 std::vector<uint64_t></uint64_t> 实现紧凑位图？
别手写位操作循环。C++ 标准库没提供原生位图容器，但用 std::vector<uint64_t></uint64_t> 手动管理位是最常用、最可控的方式：每个 uint64_t 存 64 个标志位，索引计算快，缓存友好。
-
set(i)：bits[i / 64] |= (1ULL -
test(i)：(bits[i / 64] & (1ULL - 注意
i % 64必须用& 63替代（编译器通常会优化，但显式写更安全） - 分配大小按
(max_value + 63) / 64向上取整，别用max_value / 64 + 1——当max_value是 63 的倍数时会少一单位
遇到 std::bad_alloc 怎么办？分段位图是唯一务实解法
单一块位图超 2GB 就可能在 32 位环境或某些容器中触发 std::bad_alloc，即使物理内存足够。不要强行调大堆限制，应拆成多个固定大小的子位图（例如每段覆盖 10⁶ 个整数）：
立即学习“C++免费学习笔记（深入）”；
- 设段长
SEGMENT_SIZE = 1 （约 10⁶），则第 <code>i个数落在段i / SEGMENT_SIZE，段内偏移i % SEGMENT_SIZE - 用
std::vector<:vector>></:vector>管理段，但只在首次写入某段时才分配该段内存（惰性分配） - 排序输出时，按段号从小到大遍历，每段内再按位扫描——保证全局有序
- 这种设计下，峰值内存 ≈ 最大活跃段数 × 每段字节数，而非整个值域
读取文件后直接位图置位，别用 std::set 中转
常见错误：把几千万行数字先读进 std::set<int></int> 去重，再遍历 set 写到位图——这既浪费内存（std::set 节点含指针，至少 16 字节/数），又多一次遍历。
正确做法是边读边置位：
int x;
while (in >> x) {
if (x >= 0 && x <= MAX_VAL) { // 必须校验范围！越界访问会崩溃
bitmap.set(x);
}
}
注意：MAX_VAL 必须是你预估的最大合法值，且所有输入都需做范围检查。漏掉检查会导致 bitmap.set(x) 访问越界，轻则静默出错，重则段错误。
真正难的不是位图本身，而是值域估计和分段策略——输错一个数量级，内存就差百倍。实际部署前，务必用真实数据跑一遍内存监控，别信理论公式。
