Is there a deque-like bitset in C++?

Question

I am trying to store a very large search mask with a filter of bits.

Both std::vector<bool> and std::bitset<n> store their bool representations as bits, which is different from a normal bool which is usually the size of a char or int32_t.

The problem is both of those data structures store their elements in memory in one giant block. The operating systems are getting mad at me for requesting blocks that are too big. One thing std::deque<bool> does is store its elements in something like a linked list I think.

Now I know you cannot use a pointer to a single bit without shifting, and using a linked list type structure defeats the purpose of memory conservation. But you could store like a 2gig block of char[], use shifts to set individual bits, and then a linked pointer to another 2gb block, you dig?

So tell me if this type of structure exists somewhere or is even possible.

Answer 1

I don't know of any direct solution to your problem but it could easily be resolved by a custom container.

One solution woudl simply involve std::deque of std::bitset. Where the size of the bitset is a power of 2 such as 256. With this you can take the index and just mask off the deque index and bitset index individually:

std::deque< std::bitset<256> > ;
unsigned long long = 1500;

bool val = bigBitset[ index>>8 ][ index & 0xFF ];

This could also be encapsulated within a class for convenience:

class DequeBitset : public std::deque< std::bitset<256> >
{
public:
    struct Index
    {
        unsigned long index;

        unsigned long dequeIndex() const { return index>>8; }       
        unsigned long bitsetIndex() const { return index&0xFF; }
        Index( unsigned long index ) : index(index) {}
    };
public:

    bool operator[]( const Index& index )
    { return std::deque< std::bitset<256> >::operator [](index.dequeIndex())[ index.bitsetIndex() ]; }
};

int _tmain(int argc, _TCHAR* argv[])
{
    DequeBitset test;
    test.resize(10);
    bool val = test[259];
    return 0;
}