How to use a set of boost::dynamic_bitsets?

Question

I'm trying to use a set of dynamic_bitset objects, but I'm getting an assertion failure at runtime:

a.out: boost/dynamic_bitset/dynamic_bitset.hpp:1291: 
 bool boost::operator<(const boost::dynamic_bitset<Block, Allocator>&, 
                       const boost::dynamic_bitset<Block, Allocator>&) 
 [with Block = long unsigned int, 
       Allocator = std::allocator<long unsigned int>]: 
 Assertion `a.size() == b.size()' failed.

Here is the code:

#include <iostream>
#include <set>
#include <boost/dynamic_bitset.hpp>

int main() {
  typedef boost::dynamic_bitset<> bitset;
  std::set<bitset> myset;
  bitset x(2, 0);
  bitset y(3, 1);
  myset.insert(x);
  myset.insert(y);
  return 0;
}

I'm wondering why the same size for the inserted dynamic_bitset objects is required. For the operator< to work, couldn't it assume that the most significant bits in the shorter bitset are implicitly filled with zeros?

Is there any way to do get that set of dynamic_bitsets to work?

I've also tried an unordered_set because it doesn't need the operator< but it can't compile because dynamic_bitset doesn't have a hash_value and I'm not sure how to write that without using its to_ulong member function, which would work only for short bitsets.

Answer 1

The reason for the assertion is the way the operator< is implemented:

for (size_type ii = a.num_blocks(); ii > 0; --ii)

Only the block count of the first operand is used to iterate through the bitsets. If the size of the first bitset is larger, it would access the second bitset out of bounds.

You can define and use your own comperator with std::set and handle the comparison of different sized bitsets as you see fit:

struct my_less {
    bool operator()(const boost::dynamic_bitset<>& lhs, 
                    const boost::dynamic_bitset<>& rhs) const
    {
        //TODO: implement custom comparison for lhs < rhs
        return false;
    }
};

typedef boost::dynamic_bitset<> bitset;
std::set<bitset,my_less> myset;

myset.insert( bitset(2, 0) );
myset.insert( bitset(3, 1) );