Bitmap不能直接用std::vector因底层按位存储导致指针操作受限、无原始内存视图，无法支持SIMD/原子操作；海量去重需连续对齐裸内存，推荐std::vector或mmap管理。
Bitmap 为什么不能直接用 std::vector<bool></bool> 做海量去重
因为 std::vector<bool></bool> 是特化容器，底层按位存储但接口伪装成“布尔数组”，导致无法直接取地址、不支持指针算术、迭代器行为异常；更关键的是它不提供原始内存视图，没法用 SIMD 或原子操作加速批量置位。海量数据（比如 10 亿整数）去重时，你真正需要的是可随机访问、可 mmap、可按字节/字对齐操作的裸内存块。
实操建议：
- 改用
std::vector<uint8_t></uint8_t>或std::unique_ptr<uint64_t></uint64_t>管理位图内存，确保内存连续且对齐 - 位索引计算必须用
index / 8取字节偏移、index % 8取位偏移，避免除法——改用index >> 3和index & 7 - 若数据范围已知（如 0~2^32−1），直接按最大值申请位图；若稀疏且范围大（如只含 100 万个 64 位 ID），优先考虑 Roaring Bitmap 等压缩结构，而非全量
uint8_t[512MB]
如何用 constexpr + 模板推导实现编译期位宽适配
硬编码 64 位或 8 位位图会限制场景：小数据用 64 位浪费空间，大数据用 8 位频繁 cache miss。正确做法是让编译器根据数据范围自动选择基础单元（uint8_t/uint32_t/uint64_t）和掩码策略。
示例核心逻辑：
立即学习“C++免费学习笔记（深入）”；
template <uint64_t MAX_VAL>
struct Bitmap {
static constexpr size_t kSize = (MAX_VAL + 1 + 7) / 8;
std::unique_ptr<uint8_t[]> data_ = std::make_unique<uint8_t[]>(kSize);
<pre class='brush:php;toolbar:false;'>__forceinline__ void set(uint64_t x) {
const size_t byte_idx = x >> 3;
const uint8_t bit_mask = 1U << (x & 7);
data_[byte_idx] |= bit_mask;
}};
注意点：
-
MAX_VAL必须是编译期常量，否则模板无法实例化；运行时范围要用其他结构（如分段 Bitmap） - 不要在
set()里加边界检查——海量数据下分支预测失败代价远高于越界崩溃，上线前用测试数据校验范围 - 若需线程安全，别用
std::atomic<uint8_t></uint8_t>包裹每个字节（太重），改用 CAS 循环或按 cache line 分片加锁
查重性能卡在内存带宽？试试 _mm256_testc_si256 批量探测
单次 get(x) 查一个 bit 没问题，但做“判断某批 10 万个数是否全部已存在”时，逐个查会触发上万次 cache line 加载。这时应把查询向量化：一次读入 32 字节（256 bit），用 AVX2 指令并行检测。
实操建议：
- 先对输入数组排序并去重（减少重复访存），再按 32 字节对齐分组
- 用
_mm256_loadu_si256((__m256i*)&bitmap_bytes[i])加载，配合_mm256_movemask_epi8提取 32 个字节的最高位成掩码整数 - 注意：AVX2 在某些老 CPU（如 Intel Haswell 以前）不支持，生产环境需运行时
__builtin_cpu_supports("avx2")检测 - 若数据局部性差（随机地址），向量化收益极小，此时不如用布隆过滤器预筛
磁盘级 Bitmap：用 mmap 避免 std::bad_alloc 的真实写法
10 亿个 int（32 位）对应位图约 125MB，看着不大，但若处理 IPv4 全空间（2^32 bit ≈ 512MB）或用户 ID（int64_t 范围则不可行），malloc 会失败。这时候必须绕过堆，直连文件映射。
关键代码片段：
int fd = open("bitmap.dat", O_RDWR | O_CREAT, 0644);
ftruncate(fd, bitmap_size_bytes);
uint8_t* ptr = static_cast<uint8_t*>(mmap(nullptr, bitmap_size_bytes,
PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0));
// 后续所有 set/get 直接操作 ptr[index>>3] |= (1 << (index&7))容易踩的坑：
-
mmap后必须调用msync(ptr, size, MS_SYNC)才能保证落盘，否则进程崩溃就丢数据 - 多进程共享时，
MAP_SHARED是必须的，MAP_PRIVATE写时复制会导致各自副本 - Linux 下
/proc/sys/vm/max_map_count限制总映射区数量，大数据服务需提前调高（如设为 65536）
实际用起来最麻烦的不是算法本身，而是数据范围是否稳定、内存是否真的够、以及 mmap 后忘记 msync 导致静默丢数据——这些地方一出错，结果既不报错也不正确。
