【C++】位图

04-13 1635阅读

> 作者：დ旧言~

> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：手撕哈希表的闭散列和开散列

> 毒鸡汤：坚持不懈，才能在困难面前看到光明的希望。

> 专栏选自：C嘎嘎进阶

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

前面我们已经学习了开散列实现unordered_map与unordered_set的封装，在这个封装当中能拓展出一个知识点--->位图，位图其实是开散列实现unordered_map与unordered_set的封装的一个应用场景，那它这个实际应用到底是个啥呢？今天我们就来看看

⭐主体

学习位图咱们按照下面的图解：

🌙 位图的介绍

💫 位图的概念

概念分析：

位图就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，该数据都是不重复的简单数据。通常是用来判断某个数据存不存在的

举个栗子：

案例：

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

分析：

如果不看数据量，我们第一想到的肯定就是依次从头遍历，但是这个数据量是非常大的，有40亿，遍历40亿次消耗的时间和内存是非常多的。但是引入位图后，就可以专门解决这种大量数据查找是否存在的问题。查找这个数是否存在所消耗的时间复杂度为O(1)，且节省了32倍的容量（下面有解释）。

💫 位图的原理

问题抛出：

查找一个数是否存在，其实答案就是存在或者不存在，这种只需要回答是与否的问题，我们都可以用二进制中的位来表示，1表示该数存在，反之0表示该数不存在。而位图中的每个数据单元都是一个bit位，这样子平时我们都要话32位4字节来存储数据，而现在我们只需要花1个字节就能“存储数据”，在空间上减少了约32倍的容量。例如40G的数据我们只要花1.3G来存储。但是我们平时操作的数据类型最小就是一个字节，我们不能直接对位进行操作，所以我们可以借助位运算来对数据进行操作。

图解：

我们这里给出一个数组

int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31}；则我们只需要花1个字节来存这些数据

分析：

我们目前很多的机器都是小端存储，也就是低地址存低位，一个整形数据中，第一个字节用来存储0-7的数字，第二个字节用来存储8-15的数字，第三个字节用来存储16-23的数字，第四个字节用来存储24-31的数字。我们来看看数字10是如何存储的。先通过模上32，取余还是10，然后再将4字节中第10个比特位置为1，则表示该数字出现过。由于我们的机器是小端存储，所以我们的每个比特位都是要从右边开始计算的

总结：

所以说我们只需要将对应的比特位置为1即可。但是如果我们要存储的数据很大呢？其实也很简单，我们可以定义一个数组，当做一个位图，如果该数字在0-31之间，我们就存储在0号下标的元素中进行操作，如果在32-63之间，则就在1号下标之间进行操作。计算下标我们可以通过模32来获得下标。

💫 位图的应用

快速查找某个数据是否在一个集合中
排序 + 去重
求两个集合的交集、并集等
操作系统中磁盘块标记
🌙 位图的使用

💫 位图的定义

方式一: 构造一个8位的位图,所有位默认初始化为0.
```
bitset bs; //00000000
```
方式二: 构造一个8位的位图,使用string类型对象初始化.
```
bitset bs( string("1111" ))  // 00001111
```
方式三: 构造一个8位的位图,使用字符串"1111"初始化.
```
bit bs("1111");  //00001111
```
💫 位图的成员函数

相关函数：

举个栗子：
```
int main()
{
	bitset bs("1110");
	 
	bs.set(0);                  //设置指定位
	cout 
```