【C++】位图详解（一文彻底搞懂位图的使用方法与底层原理）

🌈 个人主页：谁在夜里看海.

🔥 个人专栏：《C++系列》《Linux系列》

⛰️ 天高地阔，欲往观之。

目录

1.位图的概念

2.位图的使用方法

定义与创建

设置和清除

位访问和检查

转换为其他格式

3.位图的使用场景

1.快速的查找某个数据是否在一个集合中

2.排序+去重

3.求两个集合的交集和并集

4.位图的底层实现

私有成员定义与初始化

set和reset的实现

前面的博客我们介绍了哈希结构以及以哈希为底层结构的容器unordered_map和unordered_set，相较于以红黑树为底层的map和set，它们的优势是更高效的查找（平均为O(1)）不过代价是更多内存的消耗，这些内存的消耗在某些场景下会变得致命：

这是一道腾讯的面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

既然是追求高效的查询，显然哈希结构更具优势，但是在这里如果使用哈希表，会占用大量的内存。40亿个整数键需要16GB的内存，为了解决哈希冲突，实际所需容量会更多（1.5倍以上）。这是什么概念呢？

这是博主的笔记本规格，可以看到RAM（运行内存）刚好是16GB（加上虚拟内存也不过20GB左右），也就是说即使我“倾家荡产”也不足以实现上述操作。

用其他办法（比如压缩数据结构）的确可以节省内存的占用，但是并无法达到快速查询的效果。现在存在如下矛盾：

①：更快查询效率的需要

②：更少内存占用的需要

我们需要寻找一种办法，同时满足上述两种需求，以解决这个问题。于是乎，位图闪亮登场~

1.位图的概念

所谓位图，是一种使用二进制位（bit位）来表示数据状态的数据结构。其每一个二进制位（bit）可以表示一个数据的存在与否，从而通过极少的内存实现大规模数据的存储与处理。

比如，存储1个整形需要4个字节的空间，现在我用存储1个整形的空间，就可以表示32个整形元素的存储状态：

1个整形有32个bit位，每一位都可以表示一个数据的状态（数据1存在就让第一位bit值变成1），因此我们可以把每一个比特位都看成一个bool值，bool值为1表示数据存在，为0表示不存在。

现在我们回到上面那道问题：

原本需要16GB的空间存储40亿个整数，而1个整形的空间可以表示32个数据的存在状态，所以现在只需要 16GB/32 = 512KB 的存储空间，而且由于数据是映射存储的，我们想知道 整数x 存不存在，只需要看第 x 个比特位是否为1即可，所以查询的时间复杂度是O(1)。这种映射关系和哈希结构很像，所以位图实际上就是哈希的一种应用。

总结：位图是如何查询到数据的

位图只存储数据的状态（即是否存在），而不存储数据本身的值，但是我们仍可以根据位图的位索引位置间接查询到数据本身。比如要记录整数 5 是否存在，则位图第 5 位会被置为 1，看到第 5 位是 1，可以知道 5 存在，但位图中并没有存储“5”的数值。总之，我们并不是根据数据本身进行查询，而是通过位置映射关系进行查询。

2.位图的使用方法

C++标准库提供了一个名为 bitset 的数据结构，用于管理和操作bit数组，可用于实现位图。

以下是bitset使用方法的介绍：

定义与创建

bitset 是一个模版类，模版参数表示位数，在编译时确定大小，例如：

#include 
#include 
using namespace std;
int main()
{
	bitset bits;             // 定义一个大小为 8 位的位图（位数组）
	bitset bits16(0xF0F0);  // 定义一个大小为 16 位的位图，并初始化为二进制 1111 0000 1111 0000
	bitset bitsFromStr("10101010"); // 从字符串创建一个 8 位位图
	return 0;
}

设置和清除

bitset 提供了很多方法用于位操作和状态管理：

	bitset bits("10101010");
	bits.set(0);        // 将第 0 位设置为 1，结果为 10101011
	bits.reset(1);      // 将第 1 位设置为 0，结果为 10101001
	bits.flip();        // 翻转所有位，结果为 01010110
	bits.flip(2);       // 翻转第 2 位，结果为 01010010

位访问和检查

转换为其他格式

3.位图的使用场景

1.快速的查找某个数据是否在一个集合中

现在随机生成10000个范围在0~15000的整数，检验某些数据是否存在：

#include 
#include 
#include 
#include 
#include 
using namespace std;
int main() {
    const int num_elements = 10000; // 元素数量
    const int min_value = 0;         // 最小值
    const int max_value = 15000;     // 最大值
    // 获取当前时间作为种子
    unsigned seed = static_cast(std::chrono::system_clock::now().time_since_epoch().count());
    std::mt19937 gen(seed); // 使用当前时间作为种子生成随机数
    std::uniform_int_distribution dis(min_value, max_value); // 均匀分布
    // 创建一个 vector 并填充随机数
    std::vector nums(num_elements);
    for (int& number : nums) {
        number = dis(gen); // 生成随机数并赋值
    }
    // 创建位图，范围是 0 到 max_value
    bitset bitset;
    // 将生成的随机数映射到位图中
    for (const auto& it : nums) {
        bitset.set(it);
    }
    // 检查某个数是否存在
    vector num_test = { 5, 64, 862, 1356, 45, 236, 856, 12, 489, 6116, 1648, 216, 1554, 335, 795, 211 };
    cout