BitMagic Home C++ Boost
SourceForge.net Logo
BitMagic Home
BitMagic News
BitMagic Technical Articles
BitMagic Documentation
BitMagic Team
BitMagic Download

Bitvector as a Container

Introduction

STL library has a powerful concept of standard containers and iterators. Iterators provide unified access of elements in a standard container. Iterators for a particular container are defined in the container class definition. There are three types of iterators, iterator, reverse_iterator, and random access. Random access iterators are simply iterators that can go both forward and backward through a collection with any step value. In most cases iterator mimics behavior of a standard C pointer and works as a bridge between containers and algorithms, which facilitates generic programming and code reuse.

The following code example prints content of vector:

    void PrintVector(const vector& vect)
    {
          vector::const_iterator i = vect.begin();
          for ( i = vect.begin(); i < vect.end(); i++)
          {
                cout << *i << endl;
          }
    }

STL bitset overview

STL includes a compact convinient implementation of bitset which can manipulate bits in 0 - N-1 range, implements logical AND, OR, XOR operations, bit shifts and so on. Since bitset consists of independent, atomic elements, provides access operators to elements it can be considered as "almost container". But current STL design for some reasons does not provide iterators. But in many real-life situations iterators for bitsets can be in fact very useful.

Bitset traversal

One of the tasks programmers routinely encounter is container traversal. Like in the example above we often need to walk through the elements of a container and do something with it. For the bitset this task often means that we need to bring all ON bits. To be more specific we often need not the bits itself but indexes of ON bits in the bitset.

Doing this in STL can be very simple, and ... rather inefficient.

    bitset<20000>  bs;

    bs[10] = true;
    bs[100] = true;
    bs[10000] = true;

    for (int i = 0; i < bs.bitset_size; ++i)
    {
        if (bs[i])
        {
            cout << i << endl;
        }
    }

What is wrong with this code ?

From the implementation standpoint bitset needs to go and "extract" every bit from the bitset, convert it to Boolean value and make a comparison. Of course C++ says that STL always takes care of implementation, but we should not expect miracles here. In cases when we have a lot of 0 bits this code is a performance disaster.

A real alternative here is to add a specialized function to bitset that would directly retrieve index of next ON bit.

BM bvector template class provides get_first and get_next functions. It makes bitvector traversal much faster since this implementation takes care of possible 0 blocks and designed to deal with it.

    bm::bvector<>   bv;  

    bv.set_bit(10);
    bv.set_bit(100);
    bv.set_bit(1000000);

    unsigned value = bv.get_first();
    do
    {
        cout << value << endl;
        value = bv.get_next(value);
        if (!value)
        {
            break;
        }
    } while(1);

The provided approach is almost optimal but actually we can do even better. bvector class will includes a special iterator-like internal class specifically designed for retrieving coordinates of ON bits. Traditional iterator as it is defined for all STL containers works in terms of the same type container operates. Bitvectors operate with bits (which has no direct representation in C/C++ language) or values of type bool. Our traversal iterator works with unsigned integer values and it was decided not to use any "iterator" like name and traversal iterator was called enumerator.

Enumerator

bvector<> template defines an internal class called enumerator designed as forward constant iterator sequentially traversing bitvector in order to retrieve indexes of ON bits.

The fragment below does the job using BM enumerators.

    bm::bvector<>   bv;    

    bv[10] = true;
    bv[100] = true;
    bv[10000] = true;

    bm::bvector<>::enumerator en = bv.first();
    bm::bvector<>::enumerator en_end = bv.end();

    while (en < en_end)
    {
        cout << *en << endl;
        ++en;  // Fastest way to increment enumerator
    }

In tests enumerator demonstrates even better performance than traversal functions. You know that bvector<> keeps data as a tree of blocks each one can be a plain bit block or GAP block. Every time we call for the next bit it has to find the target block, target word, calculate the bit mask and check the bit. In case of enumerator we have a stateful object and we do not need to repeat all the positioning steps every time. In fact current implementation simply deciphers the local portion of the bitset and keeps indexes on all ON bits as a short array inside the enumerator.

Pre-increment vs post-increment.

When using enumerator you should remember, that pre-increment operator (++en) is significantly faster than post-increment (en++). Why this happens ? The best answer comes if we take a look at the code.

Implementation of the post-increment operator:

   enumerator operator++(int)
   {
       enumerator tmp = *this;       //  Temporary object (copyctor is called here)
       go_up();
       return tmp;                           //  Good chances of another copyctor call 
    }

Pre-increment is much simpler and always faster:

    enumerator& operator++()
    {
        go_up();
        return *this;
     }

The rule of thumb is to avoid post-increment if pre-increment works just as fine. My first example should be re-implemented.

    void PrintVector(const vector& vect)
    {
          vector::const_iterator i = vect.begin();
          for (i = vect.begin(); i < vect.end(); ++i)      // Avoid  i++ 
          {
                cout << *i << endl;
          }
    }

Since STL is designed around algorithms we employ for_each to do the same job. But if we try to use it we can easily bump into a problem. Enumerator is not a truly random access iterator. Some algorithms can try to calculate difference between iterators. Sometimes it is not obvious if algorithm needs "-" or not. Often it is done as a part of loop unrolling for optimization. For enumerator difference is very expensive and optimization like this we can end up with performance degradation. So be extra careful when you use enumerator with the standard algorithms.


(c) Anatoliy Kuznetsov. 2003.
[ anatoliy_kuznetsov at yahoo.com ]