目录
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 <bitset>
#include <iostream>
using namespace std;
int main()
{
bitset<8> bits; // 定义一个大小为 8 位的位图(位数组)
bitset<16> bits16(0xF0F0); // 定义一个大小为 16 位的位图,并初始化为二进制 1111 0000 1111 0000
bitset<8> bitsFromStr("10101010"); // 从字符串创建一个 8 位位图
return 0;
}
设置和清除
bitset 提供了很多方法用于位操作和状态管理:
set() | 将所有位设置为 1 |
set(size_t pos, bool value = true) | 将指定位置 pos 的位设置为 value |
reset() | 将所有位重置为 0 |
reset(size_t pos) | 将指定位置 pos 的位重置为 0 |
flip() | 将所有位翻转(0 变 1,1 变 0) |
flip(size_t pos) | 将指定位置 pos 的位翻转 |
bitset<8> bits("10101010");
bits.set(0); // 将第 0 位设置为 1,结果为 10101011
bits.reset(1); // 将第 1 位设置为 0,结果为 10101001
bits.flip(); // 翻转所有位,结果为 01010110
bits.flip(2); // 翻转第 2 位,结果为 01010010
位访问和检查
operator[] | 使用 [] 访问位 |
test(size_t pos) | 测试指定位置的位是否为 1,返回 true 表示为 1,返回 false 表示为 0 |
all() | 检查所有位是否都为 1,是返回 true ,否则返回 false |
any() | 检查是否存在至少一位为 1,是则返回 true |
none() | 检查是否所有位都是 0,是则返回 true |
count() | 返回所有 1 的数量 |
转换为其他格式
to_string() | 将位图转换为字符串 |
to_ulong() | 将位图转换为 unsigned long 类型 |
to_ullong() | 将位图转换为 unsigned long long 类型 |
3.位图的使用场景
1.快速的查找某个数据是否在一个集合中
现在随机生成10000个范围在0~15000的整数,检验某些数据是否存在:
#include <bitset>
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
int main() {
const int num_elements = 10000; // 元素数量
const int min_value = 0; // 最小值
const int max_value = 15000; // 最大值
// 获取当前时间作为种子
unsigned seed = static_cast<unsigned>(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<int> nums(num_elements);
for (int& number : nums) {
number = dis(gen); // 生成随机数并赋值
}
// 创建位图,范围是 0 到 max_value
bitset<max_value + 1> bitset;
// 将生成的随机数映射到位图中
for (const auto& it : nums) {
bitset.set(it);
}
// 检查某个数是否存在
vector<int> num_test = { 5, 64, 862, 1356, 45, 236, 856, 12, 489, 6116, 1648, 216, 1554, 335, 795, 211 };
cout << "存在性检查结果:\n";
for (const auto& it : num_test) {
if (bitset.test(it)) { // 检查 num 的位是否为 1
cout << it << " 存在.\n";
}
else {
cout << it << " 不存在.\n";
}
}
return 0;
}
分别运行三次的结果:
2.排序+去重
位图和哈希表底层都是哈希结构,为什么哈希表不能实现排序而位图可以呢?
因为哈希表的存储位置是通过哈希函数求得的的哈希值决定的,不同的元素可能有相同的哈希值,因此元素的存储是非线性的。
而位图的存储位置就是数据本身决定的,每个比特位对于一个元素,因此元素的存储是线性的。
下面来看示例:
#include <iostream>
using namespace std;
#include <bitset>
#include <vector>
const size_t MAX_SIZE = 1000; // 数据范围是 0 到 1,000,000
int main() {
bitset<MAX_SIZE> bitset;
// 模拟数据插入(包括重复数据)
vector<int> data = { 566,254,4,26,326,2,495,56,98,26,254,566,235,66 };
cout << "排序+去重前的数据:\n";
for (auto it : data) {
cout << it << " ";
}
cout << "\n";
for (int num : data) {
bitset.set(num); // 将数据映射到位图中
}
// 遍历位图,输出所有置位为 1 的位置(即有序的、去重的数据)
cout << "排序+去重后的数据:\n";
for (size_t i = 0; i < MAX_SIZE; ++i) {
if (bitset.test(i)) {
cout << i << " ";
}
}
cout << "\n";
return 0;
}
3.求两个集合的交集和并集
位图是如何完成交集并集运算的呢?由于位图的每一个bit位存储对应元素的bool值(0或1),而相同元素在不同位图中的存储位置是一样的,我们对两个位图进行按位与运算,就可以得到交集;进行按位或运算,就可以得到并集。
#include <iostream>
#include <bitset>
const size_t MAX_SIZE = 1000000;
using namespace std;
int main() {
bitset<MAX_SIZE> setA;
bitset<MAX_SIZE> setB;
// 插入一些数据到集合 A
setA.set(123456);
setA.set(654321);
setA.set(500);
// 插入一些数据到集合 B
setB.set(654321);
setB.set(500);
setB.set(999999);
// 求交集(A & B)
bitset<MAX_SIZE> intersection = setA & setB;
cout << "交集:\n";
for (size_t i = 0; i < MAX_SIZE; ++i) {
if (intersection.test(i)) {
cout << i << " ";
}
}
cout << "\n";
// 求并集(A | B)
bitset<MAX_SIZE> unionSet = setA | setB;
cout << "并集:\n";
for (size_t i = 0; i < MAX_SIZE; ++i) {
if (unionSet.test(i)) {
cout << i << " ";
}
}
cout << "\n";
return 0;
}
4.位图的底层实现
位图的底层其实是一个vector容器,容器内部存放整形元素,一个整形元素可以存放32个对应元素的状态(bool值),并且通过位运算实现映射关系的对应。
底层存储结构:
私有成员定义与初始化
在bitset类中,我们需要一个_bitCount成员表示比特位的总个数用于对bitset的初始化,以及一个_bit(vector<int>类型的容器 )用于存储元素。
class bitset
{
private:
vector<int> _bit;
size_t _bitCount;
};
位图的大小是固定的,根据_bitCount的大小进行空间开辟,而_bitCount的大小是由待存储元素的最大值决定的。但是_bitCount的单位是bit,而vector中存储单位是整形,所以我们需要进行换算,将_bitCount>>5(也就是除以2^5)并+1(由于除法会向下取整,例如 bitCount
是 33,33 >> 5
计算结果是 1,但我们实际上需要 2 个整型来存储 33 个比特位)
bitset(size_t bitCount)
: _bit((bitCount >> 5) + 1), _bitCount(bitCount)
{}
set和reset的实现
假设用which表示要存储的元素,我们需要求得映射位置。我们可以把每个元素当成一个数组,数组中包含32个比特位,此时将which/32就可以得出存储在第几个数组中,并用which%32得到在该数组下的具体比特位,假设which = 152:
存储位置为v[4]的第24个比特位:
如此一来就找到了对应的映射关系。下面是代码部分:
// 将which比特位置1
void set(size_t which)
{
if (which > _bitCount)
return;
size_t index = (which >> 5);
size_t pos = which % 32;
_bit[index] |= (1 << pos); // 将对应bit位改为1
}
// 将which比特位置0
void reset(size_t which)
{
if (which > _bitCount)
return;
size_t index = (which >> 5);
size_t pos = which % 32;
_bit[index] &= ~(1 << pos); // 将对应bit位改为0
}
// 检测位图中which是否为1
bool test(size_t which)
{
if (which > _bitCount)
return false;
size_t index = (which >> 5);
size_t pos = which % 32;
return _bit[index] & (1 << pos);
}
// 获取位图中比特位的总个数
size_t size()const { return _bitCount; }
以上就是对位图的详细介绍说明,欢迎指正~
码文不易,还请多多关注支持,这是我持续创作的最大动力!