C++中如何实现一个位图（Bitmap）？C++数据结构与内存优化【算法】

位图（Bitmap）在 C++ 中本质是用一个 bit 位表示一个布尔状态（如是否存在、是否被标记），核心目标是**空间极致压缩 + O(1) 随机访问**。标准库没有直接叫 “Bitmap” 的容器，但 std::vector<bool></bool> 是特化实现（底层按位存储），而更灵活、可控、高性能的方案是手写基于 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<uint64_t></uint64_t> 存储数据，避免裸指针和内存泄漏
• 提供 set(i)、reset(i)、test(i)、size()、capacity()
• 添加 count()（统计置位数）可用 __builtin_popcountll()（GCC/Clang）加速
• 重载 [] 可返回代理对象（proxy），支持 bitmap[i] = true 语法

与 std::vector 的关键区别

虽然 std::vector<bool></bool> 是位图语义，但它是特化容器，有明显限制：

标签： 字节 c++ proxy 区别 标准库