Iteration through boost :: dynamic_bitset

Question

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

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

My first thought was to make a simple "dump" cycle through each index and ask if it was installed:

 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() , which, as I thought, were intended for this purpose:

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

I have done some tests and it seems that the second method is more efficient, but it concerns me that there may be another “more correct” way to perform this iteration. I could not find in the documentation any examples or notes indicating the correct way to iterate over the given bits.

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

Answer 1

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

Note that dynamic_bitset has no iterators , so it will behave a bit non-C ++ 'ish, no matter what.

Answer 2

Depending on your definition, more correct. The correct method should probably produce the correct results on all valid inputs and be fast enough.

find_first and find_next so that they can be optimized to scan entire blocks of bits in a single comparison. If a block is, say, an unsigned length of 64 bits, one block comparison analyzes 64 bits at once, where a simple loop like the one you sent will do 64 iterations for this.