当数据量很大而每个数据的状态又很少的情况时候,可以用位图来设计存储数据的容器。

在地址空间中,栈是向下生长的,如果用int32_t来作为一个存储单元,则每32位可以看作一组,底层的数据结构可以连续的数组,则原本用32个字节才可以表示一个状态现在可以用一个字节表示一个状态。在数据插入位图的时候,用位或运算,在查找的时候,用位与运算。

代码如下:

#include <iostream>
#include <vector>

using namespace std;

class Bitmap {
public:
    Bitmap(int size, int _key = 32)
    {
        key = _key;
        buffer.resize(size / key + 1);
    }
    void insert(int value)
    {
        //组序号
        int seg_index = value / key;
        //具体序号
        int index = value % key;
        buffer[seg_index] |= (1 << index);
    }
    void get(int value)
    {
        int seg_index = value / key;
        int index = value % key;
        if (buffer[seg_index] & (1 << index)) {
            cout << value << " is in bitmap" << endl;
        } else {
            cout << value << "is not int bitmap" << endl;
        }
    }

private:
    vector<uint32_t> buffer;
    int key;//key个位为一组
};

int main()
{
    Bitmap b(60);
    b.insert(30);
    b.insert(60);
    b.get(30);
    b.get(60);
    b.insert(70);
    b.get(70);
    return 0;
}