位图排序适合海量整数去重与排序，因其在值域远小于数据量时空间效率极高（如1亿个[0,100万)整数仅需125kb），但要求值域已知且紧凑，否则退化为稀疏哈希表；手写uint64_t位图可避免std::vector代理对象问题，通过i>>6和i&63加速寻址，并需边界检查；排序本质是顺序扫描位图输出置位下标，时间复杂度o(n)取决于值域上限而非数据量，负数需偏移处理，i/o应分块读写以控内存，性能瓶颈常在缓存访问模式，可用__builtin_popcountll等优化位扫描。
位图排序为什么适合海量整数去重与排序
位图排序不是万能的，它只在数据范围远小于数据量时才真正省空间。比如对 1 亿个 [0, 1000000) 范围内的整数排序，用 std::vector<bool></bool> 或手动管理的 uint64_t 数组只需约 125KB 内存；而直接存 1 亿个 int 就要 400MB —— 差三个数量级。关键前提是：值域必须已知且紧凑，否则位图退化成稀疏哈希表，反而更费内存。
常见误用场景：std::vector<bool></bool> 被当成普通容器调用 .data()（它不保证连续存储）、用 char 数组但未按位寻址（浪费 8 倍空间）、忽略负数或偏移导致越界访问。
如何手写紧凑位图并支持快速 set/get
别依赖 std::vector<bool></bool> 的“位压缩”语义——它的迭代器行为和内存布局不可移植，且 operator[] 返回代理对象，无法取地址。稳妥做法是自己封装一个基于 uint64_t 的位图类：
class BitMap {
std::vector<uint64_t> bits;
size_t size_;
public:
BitMap(size_t max_val) : size_(max_val + 1), bits((max_val + 64) / 64) {}
void set(size_t i) { bits[i / 64] |= (1ULL <ul>
<li>
<code>i / 64</code> 和 <code>i % 64</code> 是关键，用位运算替代除法模运算可提速（<code>i >> 6</code>、<code>i & 63</code>）</li>
<li>构造时按需分配 <code>uint64_t</code> 数量，避免 <code>std::vector<bool></bool></code> 的隐式扩容开销</li>
<li>务必检查 <code>i ，否则 <code>get()</code> 对超界索引返回垃圾值而非报错</code>
</li>
</ul>
<h3>位图排序的完整流程与 I/O 边界处理</h3>
<p>位图本身不排序，它只记录存在性；真正的“排序输出”是顺序扫描位图、遇到置位就输出下标。这个过程是 O(N)，N 是值域大小，不是输入数据量——所以值域不能过大。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>实操中容易卡住的点：</p>
<ul>
<li>输入含负数？统一加偏移量（如最小值的绝对值），并在输出时减回，<code>offset</code> 必须参与所有 <code>set()</code> 和 <code>get()</code> 计算</li>
<li>数据来自文件流？别一次性读完再建图，用 <code>std::istream::read()</code> 分块读整数，边读边 <code>set()</code>，降低峰值内存</li>
<li>输出到文件？用 <code>std::ofstream</code> 配合 <code> 会慢，改用 <code>write()</code> 写二进制格式，或至少关闭同步：<code>std::ios::sync_with_stdio(false)</code></code>
</li>
</ul>
<h3>性能瓶颈常不在位操作，而在内存访问模式</h3>
<p>当值域达到千万级，<code>uint64_t</code> 数组可能跨多个 cache line，顺序扫描时 CPU 预取效率下降。实测发现：对 1000 万位的位图，用 <code>__builtin_popcountll()</code> 逐 <code>uint64_t</code> 统计并定位置位位置，比单 bit 扫描快 3–5 倍。</p>
<p>优化建议：</p>
<ul>
<li>对每个 <code>uint64_t</code> 元素，先用 <code>if (word == 0) continue;</code> 跳过全零块</li>
<li>用 <code>__builtin_ctzll(word)</code> 找最低位 1，循环清除最低位（<code>word &= word - 1</code>），避免模 64 运算</li>
<li>若目标平台支持 AVX2，可用 <code>_mm256_movemask_epi8</code> 并行查 32 字节中的非零字节，但需额外处理字节内位</li>
</ul>
<p>位图排序的“海量”是相对的——它把时间换空间，把排序复杂度从 O(n log n) 换成 O(N)，但 N 是值域上限。一旦值域失控，缓存失效、内存带宽吃紧，优势立刻反转。真正难的不是写对位操作，而是提前判断数据分布是否匹配位图前提。</p></uint64_t>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
