位图本质是用单个bit表示布尔状态，追求空间压缩与O(1)访问；推荐用uint64_t数组实现，索引转位置为i/64和i%64，支持动态扩容、popcount优化及代理引用，优于std::vector。
位图（Bitmap）在 C++ 中本质是用一个 bit 位表示一个布尔状态（如是否存在、是否被标记），核心目标是**空间极致压缩 + O(1) 随机访问**。标准库没有直接叫 “Bitmap” 的容器，但 std::vector 是特化实现（底层按位存储），而更灵活、可控、高性能的方案是手写基于 uint32_t 或 uint64_t 的位数组。
用 uint64_t 数组实现紧凑位图（推荐）
以 64 位整数为单位管理位，兼顾内存对齐、缓存友好和操作效率：
-
索引转位置：第
i位 → 数组下标i / 64，位偏移i % 64 -
置位：
data[i / 64] |= (1ULL -
清位：
data[i / 64] &= ~(1ULL -
查位：
(data[i / 64] >> (i % 64)) & 1ULL -
初始化大小：需预估最大位数
n，分配(n + 63) / 64个uint64_t
支持动态扩容的位图类（实用封装）
手动管理内存时，可封装成类，支持自动扩容和常用接口：
- 内部用
std::vector存储数据，避免裸指针和内存泄漏 - 提供
set(i)、reset(i)、test(i)、size()、capacity() - 添加
count()（统计置位数）可用__builtin_popcountll()（GCC/Clang）加速 - 重载
[]可返回代理对象（proxy），支持bitmap[i] = true语法
与 std::vector 的关键区别
虽然 std::vector 是位图语义，但它是特化容器，有明显限制：
立即学习“C++免费学习笔记（深入）”；
- 不满足标准容器要求（如
data()不可用，迭代器不是原生指针） - 无法取地址（
&v[i]无效），不能用于需要真实布尔引用的场景 - 多线程下
v[i] = true非原子（可能与其他位操作竞争） - 性能不如手写位图可控（例如未对齐访问、无 popcount 优化）
内存与缓存优化技巧
位图高频用于海量数据标记（如布隆过滤器、去重、集合运算），优化要点：
-
对齐分配：用
aligned_alloc或std::aligned_storage对齐到 64 字节，提升 SIMD 和缓存行加载效率 -
批量操作：用
_mm256_loadu_si256等 intrinsic 一次处理 256 位，加速 set/reset 范围 - 稀疏优化：若置位极少，可改用 Roaring Bitmap（C++ 有 CRoaring 绑定）
-
零初始化：用
memset(data, 0, bytes)或std::vector构造函数，比循环赋值快得多
基本上就这些。位图本身逻辑简单，难点在于边界处理（如越界检查）、跨平台位序一致性（小端机器上
