位图用比特表示整数存在状态，节省内存。通过vector<char>或bitset实现，支持set、clear、get操作，适用于去重排序小整数，如输出2 3 5 7 8；std::bitset适合固定大小场景，手动实现更灵活，广泛用于系统级设计。
在c++中，位图（Bitmap）是一种高效的数据结构，用于表示一组布尔状态，通常用来标记某个整数是否出现过。它的核心思想是用一个比特（bit）来表示一个元素的存在与否，从而极大节省内存空间。
位图的基本原理
假设我们要处理的整数范围是 0 到 N-1，那么可以用 N 个比特来表示这些整数的状态：0 表示未出现，1 表示已出现。由于一个字节有8位，我们可以使用 unsigned char 或 std::vector<bool> 来存储这些比特。
更高效的做法是使用 std::vector<char> 或 std::bitset，通过位操作直接访问特定位置的比特。
手动实现简单的位图类
下面是一个基于 vector<char> 的简单位图实现：
#include <iostream> #include <vector> class Bitmap { private: std::vector<char> bits; int size; public: // 构造函数，指定最大数值范围 Bitmap(int n) : size(n) { bits.resize((n + 7) / 8, 0); // 每个 char 8 bit，向上取整 } // 设置某一位为 1 void set(int i) { if (i < 0 || i >= size) return; int byteIndex = i / 8; int bitIndex = i % 8; bits[byteIndex] |= (1 << bitIndex); } // 清除某一位为 0 void clear(int i) { if (i < 0 || i >= size) return; int byteIndex = i / 8; int bitIndex = i % 8; bits[byteIndex] &= ~(1 << bitIndex); } // 检查某一位是否为 1 bool get(int i) { if (i < 0 || i >= size) return false; int byteIndex = i / 8; int bitIndex = i % 8; return (bits[byteIndex] & (1 << bitIndex)) != 0; } };
使用示例：去重与排序小整数
位图常用于对非负整数进行快速去重和排序。比如我们有一组数据，想输出不重复且有序的结果：
立即学习“C++免费学习笔记（深入）”；
int main() { Bitmap bm(100); // 支持 0~99 int nums[] = {5, 2, 7, 5, 3, 2, 8, 7}; int n = sizeof(nums) / sizeof(nums[0]); // 插入所有数字（自动去重） for (int i = 0; i < n; ++i) { bm.set(nums[i]); } // 按顺序输出存在的数字 std::cout << "Unique sorted numbers: "; for (int i = 0; i < 100; ++i) { if (bm.get(i)) { std::cout << i << " "; } } std::cout << std::endl; return 0; }
输出结果：
Unique sorted numbers: 2 3 5 7 8
标准库替代方案：std::bitset
如果大小在编译期已知，可以直接使用 std::bitset，它更安全且接口简洁：
#include <bitset> #include <iostream> int main() { std::bitset<100> bs; // 固定大小为100 bs.set(5); bs.set(2); bs.set(7); bs.set(5); // 重复设置无影响 for (int i = 0; i < 100; ++i) { if (bs.test(i)) { std::cout << i << " "; } } std::cout << std::endl; return 0; }
基本上就这些。自己实现的 Bitmap 更灵活，可动态扩展；而 std::bitset 更适合固定场景，写起来更简单。实际应用中，位图广泛用于布隆过滤器、内存页管理、文件系统索引等底层系统设计中。注意它只适用于整数且范围不太大的情况，超出后要考虑 Roaring Bitmap 等优化结构。