位图排序不能直接用 std::vector，因其是特化容器，按位存储但迭代器异常、不支持取地址（&v[i]编译失败），导致无法进行memset清零或SIMD扫描；应改用std::vector或std::vector。
位图排序为什么不能直接用 std::vector<bool></bool>
因为 std::vector<bool></bool> 是特化容器，内部按位存储但接口伪装成布尔容器，导致迭代器行为异常、无法取地址、&v[i] 编译失败——这会让基于指针偏移的批量位操作（如按字节清零、SIMD 扫描）完全不可行。实际工程中应改用 std::vector<uint8_t></uint8_t> 或 std::vector<uint64_t></uint64_t> 手动管理位，哪怕多占一点空间，也比运行时踩坑强。
常见错误现象：std::vector<bool> bits(1000000); bits.data()</bool> 编译报错；想用 memset 清零却找不到连续内存首地址。
- 若数据范围是 [0, N)，N ≤ 10⁷，推荐用
std::vector<uint8_t></uint8_t>，每个字节管 8 个数，访问逻辑清晰：索引i对应字节i / 8、位偏移i % 8 - 若 N 达到 10⁹ 量级且内存敏感，改用
std::vector<uint64_t></uint64_t>，用(bits[i / 64] >> (i % 64)) & 1U提取位，清零用bits[i / 64] &= ~(1ULL - 别省那点内存去压成
std::bitset——它大小编译期固定，不支持动态扩容，海量数据下根本没法用
如何避免位图初始化耗时成为瓶颈
初始化一个 1GB 的位图（对应 80 亿个 bit），用 for 循环逐字节赋 0，实测在普通服务器上要 200ms+；而用 std::vector 构造时指定初值，底层会调用 memset，速度提升 5–10 倍。
使用场景：数据单次加载、长期驻留内存的离线排序任务（如日志 ID 去重排序）。
立即学习“C++免费学习笔记（深入）”；
- 正确写法：
std::vector<uint8_t> bits((max_val + 7) / 8, 0)</uint8_t>—— 构造时直接填满 0，由 STL 内部优化为memset - 错误写法：
std::vector<uint8_t> bits((max_val + 7) / 8); for (auto& b : bits) b = 0;</uint8_t>—— 显式循环无法被优化 - 若需频繁重建位图（如多轮测试），可复用同一
vector并调用std::fill(bits.begin(), bits.end(), 0)，它通常也被优化为memset
find_first_set 加速查找的现实约束
想快速跳过连续 0 段，不能只靠手写循环检查每个 byte；现代 CPU 提供 __builtin_ctz（GCC/Clang）或 _tzcnt_u64（MSVC intrinsics），但它们只对非零输入有效——传入 0 会返回 undefined 或 32/64，必须先判零。
性能影响：未加判零保护的 __builtin_ctz 在遇到全零块时可能让结果错位，后续所有位置都偏移。
- 安全扫描模式：每次读一个
uint64_t，先if (word != 0)，再用__builtin_ctzll(word)找最低置位，加上全局偏移即可得原始数值 - 不要试图用
std::countr_zero（C++20）替代——它对 0 输入定义为返回宽度值（如 64），但你要的是“跳过”，不是“返回 64” - 若目标平台不支持 builtin，退化为查表法：预建 256 字节的
first_bit_in_byte[256]，其中first_bit_in_byte[0] = 8表示无位，其余存最低位索引（0–7）
位图排序的边界与隐性成本
位图排序不是万能的：它把时间换空间，但“空间”本身也有陷阱。比如 32 位系统上，max_val = 2^32 - 1 时，位图需 512MB 内存，看似可接受；但若实际数据稀疏（仅 10⁶ 个数），你却为 42 亿个可能值分配空间，属于典型的空间误判。
容易被忽略的地方：
- 输入数据必须是非负整数且范围已知；若有负数，得整体平移，平移量也要计入内存预算
- 重复数据自动去重——这不是 bug 是特性，但业务若需要保留频次，位图就得升级为计数位图（每个槽用 2 位或更多），空间翻倍甚至更多
- 磁盘位图（mmap）看似能突破内存限制，但随机位访问触发大量缺页中断，吞吐可能比纯内存
std::sort还慢，除非你做顺序扫描+批量输出
