CODEWITHSUNDEEP
c++boost
JaredC
JaredC

Reputation: 5300

Iterating through a boost::dynamic_bitset

I have a boost dynamic_bitset that I am trying to extract the set bits from:

boost::dynamic_bitset<unsigned long> myBitset(1000);

My first thought was to do a simple 'dump' loop through each index and ask if it was set:

for(size_t index = 0 ; index < 1000 ; ++index)
{
   if(myBitset.test(index))
   {
      /* do something */
   }
}

But then I saw two interesting methods, find_first() and find_next() that I thought for sure were meant for this purpose:

size_t index = myBitset.find_first();
while(index != boost::dynamic_bitset::npos)
{
        /* do something */
        index = myBitset.find_next(index);
}

I ran some tests and it seems like the second method is more efficient, but this concerns me that there might be another 'more correct' way to perform this iteration. I wasn't able to find any examples or notes in the documentation indicating the correct way to iterate over the set bits.

So, is using find_first() and find_next() the best way to iterate over a dynamic_bitset, or is there another way?

Upvotes: 12

Views: 6317

Answers (2)

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136208

Depends on your definition of more correct. A correct method probably must yield correct results on all valid inputs and be fast enough.

find_first and find_next are there so that they can be optimized to scan entire blocks of bits in one comparison. If a block is, say, an unsigned long of 64 bits, one block comparison analyses 64 bits at once, where a straightforward loop like you posted would do 64 iterations for that.

Upvotes: 1

Fred Foo
Fred Foo

Reputation: 363467

find_first and find_next are the fastest way. The reason is that these can skip over an entire block (of dynamic_bitset::bits_per_block bits, probably 32 or 64) if none of them are set.

Note that dynamic_bitset does not have iterators, so it will behave a bit un-C++'ish no matter what.

Upvotes: 12

Related Questions