《编程珠玑》学习之“位向量”篇

最近在学习编程珠玑，其中有一个很经典的例子，是如何使用较小的内存存储数据，介绍了位向量，下面是其实现。

class IntSetBitVec {
    enum {BITSPERWORD = 32, SHIFT = 5, MASK = 0x1f};
    int n, hi, *x;
    void set(int i) {        x[i>>SHIFT] |= (1<<(i & MASK));}
    void clr(int i) {        x[i>>SHIFT] &= ~(1<<(i & MASK));}
    int test(int i) {return x[i>>SHIFT] & (1<<(i & MASK));}
public:
    IntSetBitVec(int maxelms, int maxval)
    {
        hi = maxval;
        x = new int[1+hi/BITSPERWORD];
        for (int i = 0; i < hi; i++)
        {
            clr(i);
        }
        n = 0;
    }

    int size() {return n;}
    void insert(int t)
    {
        if (test(t))
            return;
        set(t);
        n++;
    }

    void report(int *v)
    {
        int j = 0;
        for (int i = 0; i < hi; i++)
            if (test(i))
                v[j++] = i;
    }
};

仅仅三十几行代码，却非常经典。IntSetBitVec这个类提供了set，clr，test几个方法，参数i为32位整形，作用是设置、清除以及检测是否包含整数i。不难看出，构造函数IntSetBitVec()根据存储数据的最大值maxval来分配内存，举个例子，如果存储的最大数是100的话，那么分配的内存仅仅是1+100/32 = 4个byte，可以想象，如果用一个new int[100]来分配内存的话，需要占用主存100个字节的空间，相比而言，位向量的做法相当的节省存储空间。
使用测试代码进行测试，平台为VC2010，代码如下，

int _tmain(int argc, _TCHAR* argv[])
{
    IntSetBitVec* aSetVec = new IntSetBitVec(32, 31*31*31+1);
    for (int i = 0; i < 32; i++)
        aSetVec->insert(i*i*i);
    int array1[32];
    aSetVec->report(array1);

    for (int i = 0; i < 32; i++)
        cout << array1[i] << " ";
    cout << endl;
    system("pause");
    return 0;
}

上述代码首先分配一个位向量的对象，向位向量对象中插入32个数，分别是0到31的立方，然后将其放如一个长度为32的整形数组中，输出如下，
0 1 8 27 64 125 216 343 512 729 1000 1331 1728 2197 2744 3375 4096 4913 5832 685
9 8000 9261 10648 12167 13824 15625 17576 19683 21952 24389 27000 29791
使用这种测试用例，实际上对于位向量来说是不适合的，因为最大的数是31的立方即29791，而分配的内存空间是29791/32+1 = 931byte，相对来说是非常浪费的，那对于这种i^3的这种输入来说有没有更好的数据机构模型呢，答案是肯定的，那就是使用STL中的SET，代码如下，

class IntSetSTL {
    set<int> S;
public:
    IntSetSTL(int maxelements, int maxval) { }
    int size() {return  S.size(); }
    void report(int* v)
    {
        int j = 0;
        set<int>::iterator i;
        for (i = S.begin(); i != S.end(); ++i)
            v[j++] = *i;
    }
};

代码十分简洁，实际上熟悉SET的同学们应该知道IntSetSTL只是Set的一个简单封装，STL中的Set内部使用红黑树实现，可以达到高效的插入和查找（红黑树非常平衡）。如果要存储的数据是比较稀疏的，取值范围又很大，那么set这种容器非常合适。