位图用比特表示整数存在状态，节省内存。通过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 等优化结构。
