位图：
概念：
由于位图是通过一个比特位来判断是不是在范围里面的，所以其对应的时间复杂度都是O(1)的。
位图的实现：
如上图所示：
上图对应的就是3个字节，即24个比特位
要想实现位图，就得知道我们要记录的这个数应该存储到哪个位置，假设这个数是x
那么对应：
x / 32 所得的值就是该数字应该存在第几个字节上
x % 32 所得的值就是对应在此字节的第几位上，这样一来位图就简单了
我们主要实现 set,reset,test这三个借口，代码如下：
#pragma once
#include<vector>
using namespace std;
namespace bit
{
template<size_t N>
class bitset
{
public:
bitset()
{
_a.resize(N / 32 + 1);
}
// x映射的那个标记成1
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_a[i] |= (1 << j);
}
// x映射的那个标记成0
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_a[i] &= (~(1 << j));
}
// 判断 x 是否在位图里面
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _a[i] & (1 << j);
}
private:
vector<int> _a;
};
}注意这里模板的应用，是为了开出大小适中的位图出来。
测试代码：
位图的应用：
1. 给定100亿个整数，设计算法找到只出现一次的整数？
要找到只出现一次的整数，就要让出现一次和出现多次的数有所区别，
而位图只能存储0或1，所以没法区别，这是就需要用到两个位图：
只要出现多次，就将其记成10，这样就得以区分
对应的代码实现：
template<size_t N>
class TwoBitSet1
{
public:
void set(size_t x)
{
// 00 -> 01
if (!_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x);
}
//01 -> 10
else if (!_bs1.test(x) && _bs2.test(x))
{
_bs1.set(x);
_bs2.reset(x);
}
}
bool is_once(size_t x)
{
return !_bs1.test(x) && _bs2.test(x);
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};测试代码：
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
解法：
将两个文件分别映射到两个位图，再将两个位图的值与一下即可：
对应的代码实现如下：
int main()
{
int a1[] = { 1, 2, 3, 3, 4, 4, 4, 4, 4, 2, 3, 6, 3, 1, 5, 5, 8, 9 };
int a2[] = { 8, 4, 8, 4, 1, 1, 1, 1 };
bit::bitset<10> bs1;
bit::bitset<10> bs2;
for (auto e : a1)
{
bs1.set(e);
}
for (auto e : a2)
{
bs2.set(e);
}
for (int i = 0; i < 10; i++)
{
if (bs1.test(i) && bs2.test(i))
{
cout << i << " ";
}
}
cout << endl;
return 0;
}代码测试：
3.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
其实做法与第一题很像，直接上代码：
template<size_t N>
class TwoBitSet2
{
public:
void set(size_t x)
{
// 00 -> 01
if (!_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x);
}
//01 -> 10
else if (!_bs1.test(x) && _bs2.test(x))
{
_bs1.set(x);
_bs2.reset(x);
}
//10 -> 11
else if (_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x);
}
}
bool is_once(size_t x)
{
return !_bs1.test(x) && _bs2.test(x);
}
bool is_twice(size_t x)
{
return _bs1.test(x) && !_bs2.test(x);
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};测试代码：
库里面的位图接口：
布隆过滤器：
概念：
只能确定其一定不存在或者可能存在，注意可能二字
所以说布隆过滤器不能准确判断一个东西是否存在。
应用：
1.不需要精确的场景，快速判断昵称是否存在
2.精确的场景，布隆过滤器
