Hello，今天Val来分享关于位图的模拟实现。 位图c++中有源码，c++::bitset,它的主要接口有 operator[],set(),reset()、test()等等。 本篇博客主要模拟实现位图的set(),reset(),test()函数.
位图主要是用来标记一个整型的存在与否，如果存在相应的位设置为1，不存在设置为1，它的处理对象为整型，这也是它的局限性，位图标记一个整型是否存在，节省空间/快,1个字节有8个比特位，用比特位上的数字（1和0）表示对应的数是否存在。
优点：节省空间 、快 缺点：只能运用于整型
Set（）某个数存在，则把相应位图的位置为1，Reset（）去掉某个数，则把相应位图的位置为0. Test()函数主要是判断一个数是否在位图里面。如何置1和置0？对位进行运算？
代码如下：
class BitMap { public: BitMap(size_t range) { _bitMap.resize(range / 8 + 1,0); } void Set(size_t value) { size_t index = value / 8;//或者>>3 (2*2*2=8) size_t pos = value % 8; _bitMap[index] |= (1 << pos); } void Reset(size_t value) { size_t index = value / 8;//或者>>3 (2*2*2=8) size_t pos = value % 8; _bitMap[index] &= ~(1 << pos); } bool Test(size_t value) { size_t index = value / 8; size_t pos = value % 8; if (_bitMap[index] & (1 << pos)) { return true; } else { return false; } } protected: vector<char> _bitMap; }; void TestBitMap() { //BitMap bm(1024 * 1024 * 1024 * 4); BitMap bm(-1);//-1 是整数的最大值 知道有多少个数据？方便扩容 bm.Set(1101); bm.Set(1101); bm.Set(110001); bm.Set(1133301); cout << bm.Test(1101) << endl; cout << bm.Test(110100) << endl; cout << bm.Test(110001) << endl; }位图能快速判断一个整型是否存在，而且很省空间，可是当数据变为其他类型比如string 就无能为力了，布隆过滤器可以解决位图的适用范围只能是整型的问题，之后Val会分享到博客上的。 时间不早了，好梦~
