位图bitmap数据结构详解与实现

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

在地址空间中，栈是向下生长的，如果用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;
}