位图是布尔数组的压缩表示，用std::vector或std::bitset按位存储非负整数存在性；适用于值域可控场景，最大值超2^31时需手动实现动态位图。
位图Bitmap的本质是布尔数组的压缩表示
位图不是某种特殊容器，而是用 std::vector<uint8_t></uint8_t> 或 std::bitset 按位存布尔值：每个 bit 代表一个整数是否存在。比如第 137 位为 1，表示数字 137 已出现过。它只适用于**非负整数**且值域相对可控的场景（如 0~1 亿），否则内存爆炸或索引越界。
关键判断点：若数据最大值 max_val 超过 2^31（约 21 亿），std::bitset 在多数编译器下会编译失败；改用 std::vector<uint8_t></uint8_t> 手动位操作更稳妥。
手写位图：用 std::vector<uint8_t></uint8_t> 实现动态大小
标准库没提供运行时可调大小的位图，必须自己算字节偏移和位偏移。核心是两个宏/内联函数：
-
byte_index = n / 8—— 第几个字节 -
bit_offset = n % 8—— 该字节内第几位（从低位起）
设置某位为 1：bits[byte_index] |= (1U ；判断是否已存在：<code>(bits[byte_index] & (1U 。
示例片段（去重主逻辑）：
std::vector<uint8_t> bitmap((max_val + 7) / 8, 0); // 向上取整字节数
for (int x : input_data) {
if (x max_val) continue; // 跳过非法值
size_t byte_idx = x / 8;
size_t bit_idx = x % 8;
if ((bitmap[byte_idx] & (1U
<h3>用 <code>std::bitset</code> 的前提和陷阱</h3>
<p><code>std::bitset</code> 只接受编译期常量大小，比如 <code>std::bitset</code>。如果你的数据范围是 0~9999999，它很合适；但若范围来自配置文件或运行时计算，就无法直接用。</p>
<p>常见错误：</p>
<ul>
<li>写成 <code>std::bitset<n></n></code> 却让 <code>N</code> 是变量 → 编译报错 <code>non-type template parameter is not a constant expression</code>
</li>
<li>忽略内存对齐和缓存局部性：超大 <code>std::bitset</code>（如 1 亿 bit ≈ 12.5 MB）在随机访问时可能比连续 <code>uint8_t</code> 数组慢</li>
<li>未初始化：<code>std::bitset</code> 默认零初始化，但手动分配的 <code>uint8_t</code> 数组必须显式 <code>std::vector<uint8_t>(size, 0)</uint8_t></code>，否则含脏数据</li>
</ul>
<h3>实际去重流程中必须处理的边界问题</h3>
<p>真实数据不会“刚好”全是 0~N 的正整数。以下几点漏掉一个，结果就错：</p>
<ul>
<li>负数必须过滤或偏移处理（如全部加 <code>offset</code> 映射到非负区间）</li>
<li>重复值可能极多，但位图本身不记录频次，仅能判“有/无”，需额外逻辑区分“首次出现”和“后续重复”</li>
<li>内存限制：1 亿个数的位图占 12.5 MB；10 亿个数则要 125 MB —— 若机器只有 64 MB 堆空间，得切分数据块或换布隆过滤器</li>
<li>线程安全：多个线程同时写同一 bit 会丢数据，必须加锁或按数据范围分片（如线程 A 处理 [0,1e6)，B 处理 [1e6,2e6)）</li>
</ul>
<p>真正难的不是位运算本身，而是把原始数据清洗、映射、分块、合并这一整条链路串稳。位图只是其中一环，而且是最容易假定“没问题”的一环。</p></uint8_t>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
