Problems using a map with a bitset as a key

Question

I am trying to create a map in C++ with bitset as a key. However the compiler generates the following error messages

In file included from /usr/include/c++/4.6/string:50:0,
                 from /usr/include/c++/4.6/bits/locale_classes.h:42,
                 from /usr/include/c++/4.6/bits/ios_base.h:43,
                 from /usr/include/c++/4.6/ios:43,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from test2.cpp:1:
/usr/include/c++/4.6/bits/stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::bitset<8u>]’:
/usr/include/c++/4.6/bits/stl_map.h:452:2:   instantiated from ‘std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::bitset<8u>, _Tp = int, _Compare = std::less<std::bitset<8u> >, _Alloc = std::allocator<std::pair<const std::bitset<8u>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::bitset<8u>]’
test2.cpp:22:30:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:236:22: error: no match for ‘operator<’ in ‘__x < __y’
/usr/include/c++/4.6/bits/stl_function.h:236:22: note: candidates are:
/usr/include/c++/4.6/bits/stl_pair.h:207:5: note: template<class _T1, class _T2> bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
/usr/include/c++/4.6/bits/stl_iterator.h:291:5: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:341:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/basic_string.h:2510:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2522:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2534:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/stl_tree.h:856:5: note: template<class _Key, class _Val, class _KeyOfValue, class _Compare, class _Alloc> bool std::operator<(const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_set.h:713:5: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::set<_Key, _Compare, _Alloc>&, const std::set<_Key, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_multiset.h:696:5: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::multiset<_Key, _Compare, _Alloc>&, const std::multiset<_Key, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_map.h:894:5: note: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::map<_Key, _Tp, _Compare, _Alloc>&, const std::map<_Key, _Tp, _Compare, _Alloc>&)
/usr/include/c++/4.6/bits/stl_multimap.h:812:5: note: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::multimap<_Key, _Tp, _Compare, _Alloc>&, const std::multimap<_Key, _Tp, _Compare, _Alloc>&)

The progam code is given below I am trying to use bitset as a key to a map in C++. However, everytime I run the code below I run into errros.

#include <iostream>
#include <algorithm>
#include <string>
#include <bitset>
#include <set>
#include <utility>

using namespace std;

int main(int argc, char *argv[])
{
    bitset<8> test;
    test = 9;
    cout<<"Set to 9"<<endl;
    map <bitset<8> , int> mymap;
    pair <biset<8> , int> p;
    p.first = test;
    p.second = 9;
    string teststring;
    teststring = test.to_string<char,char_traits<char>,allocator<char> >();
    cout<<teststring<<temymap[test]<<endl;
    return 0;
}

mfontanini · Accepted Answer · 2012-03-14T13:22:24.327

6

Just use your own comparator class:

struct Comparer {
    bool operator() (const bitset<8> &b1, const bitset<8> &b2) const {
        return b1.to_ulong() < b2.to_ulong();
    }
};
/* ... */
map <bitset<8> , int, Comparer> mymap;

Note that you can extend this solution to support arbitrary length bitsets, as long as they are small enough to be converted to an unsigned long:

template<size_t sz> struct bitset_comparer {
    bool operator() (const bitset<sz> &b1, const bitset<sz> &b2) const {
        return b1.to_ulong() < b2.to_ulong();
    }
};
map <bitset<8> , int, bitset_comparer<8> > mymap;
map <bitset<16> , int, bitset_comparer<16> > mymap16;

edited Mar 14 '12 at 13:22

answered Mar 14 '12 at 12:58

mfontanini

21,410
4
65
73

Note: `to_ulong` only works if an `unsigned int` may hold the result, and `unsigned int` is only ever guaranteed by the Standard to be at least 16 bits, which is not much. – Matthieu M. Mar 14 '12 at 13:04
Yes, i have pointed that out in the templated solution. Thanks for the clarification anyway. – mfontanini Mar 14 '12 at 13:06
@MatthieuM.: to_ulong (as the name suggests) converts to unsigned long, so we have 32 guaranteed bits here. – PlasmaHH Mar 14 '12 at 13:19
@fontanini: Just use the same type as std::bitset does for the size parameter (size_t). You might also prefer to name the struct e.g. bitset_less to emphasize that it is for bitsets specifically. Or you could specialize std::less for bitsets. – rjnilsson Mar 14 '12 at 13:19
@PlasmaHH: oups right, I slipped there. However it does not change the fundamental issue. – Matthieu M. Mar 14 '12 at 13:22
@Cwan, i missed the size_t parameter. Thanks, i've fixed it. – mfontanini Mar 14 '12 at 13:23
@mfontanini What about if an unsigned long is not enough? Maybe if the unsigned long is enough you do not need to use the bitset... – Alessandro Jacopson Jun 12 '12 at 08:32
@uvts_cvs OP's code uses 8 bit bitsets, so converting to an unsigned long is surely enough here. On another situation, you could use another approach. – mfontanini Jun 12 '12 at 11:18

score 3 · Answer 2 · edited May 23 '17 at 12:02

3

An alternative solution would be to simply use an unordered_map, if this still meets your requirements.

This could be std::unordered_map<bitset<N>, T> or boost::unordered_map<bitset<N>, T>, depending on C++ version or performance considerations.

This avoids the need for comparison and may prove faster, depending on requirements.

edited May 23 '17 at 12:02

Community

1
1

answered Aug 05 '14 at 03:59

Timotheos

405
3
8

score 2 · Answer 3 · answered Jun 12 '12 at 08:29

You can define your comparison function. If you assume your bitset models an unsigned integral value then the following function will order the bitsets in increasing order (and works for any N).

template <size_t N>
class LessThan { 
public:
   bool operator() (const std::bitset<N> &lhs, const std::bitset<N> &rhs) const 
   { 
      size_t i = N;
      while ( i > 0 ) {
         if ( lhs[i-1] == rhs[i-1] ) {
            i--;
         } else if ( lhs[i-1] < rhs[i-1] ) {
            return true;
         } else {
            return false;
         }
      }
      return false;
   } 
};

If you run the following snippet:

  const size_t mysz = 10;
  std::map< std::bitset<mysz>, size_t, Less<mysz> > mymap;
  for ( size_t i = 0; i < 10; i++ ) {
     mymap.insert( std::make_pair(std::bitset<mysz>(i),i) );
  }

You will have this map:

mymap[0]    is the pair ((0,0,0,0,0,0,0,0,0,0), 0)  
mymap[1]    is the pair ((1,0,0,0,0,0,0,0,0,0), 1)  
mymap[2]    is the pair ((0,1,0,0,0,0,0,0,0,0), 2)  
mymap[3]    is the pair ((1,1,0,0,0,0,0,0,0,0), 3)  
mymap[4]    is the pair ((0,0,1,0,0,0,0,0,0,0), 4)  
mymap[5]    is the pair ((1,0,1,0,0,0,0,0,0,0), 5)  
mymap[6]    is the pair ((0,1,1,0,0,0,0,0,0,0), 6)  
mymap[7]    is the pair ((1,1,1,0,0,0,0,0,0,0), 7)  
mymap[8]    is the pair ((0,0,0,1,0,0,0,0,0,0), 8)  
mymap[9]    is the pair ((1,0,0,1,0,0,0,0,0,0), 9)

score 0 · Answer 4 · answered Jan 24 '14 at 04:08

This will allow map<bitset<N>,int> stuff directly:

namespace std{
    template<size_t N>
    struct less<bitset<N> > : binary_function <bitset<N>,bitset<N>,bool>{
        bool operator()(const bitset<N> &L, const bitset<N> &R) const{
            for(unsigned int i=0;i<L.size();i++)
                if(L.test(i)){
                    if(!R.test(i))return false;
                }else{
                    if(R.test(i))return true;
            }
            return false; //same
        }
    };
}

score 0 · Answer 5 · edited Oct 31 '20 at 10:03

For storing in the map you can convert bitset to string for large bitset if it's not convertible to u_long and for updating you can change back to bitset and do your changes and store back as a string.

map<string , int> mymap;
bitset<N> mybs("10100"); // converting string to bitset
map[mybs.to_string()] = 34; // bitset to string for map

This is valid as long as you don't care about the comparison.

Problems using a map with a bitset as a key

5 Answers5

Linked