Problems using a card with biteta 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 program code is given below. I am trying to use a bitset as a key to a card in C ++. However, every time I run the code below, I run errors.

 #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; } 

Answer 1

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 bits if they are small enough to convert to 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; 

Answer 2

An alternative solution would be to simply use unordered_map if it still meets your requirements.

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

This avoids the need for comparison, and can be faster , depending on requirements.

Answer 3

You can define your comparison function. If you assume that your bitset models have an unsigned integer value, the following function will sort bitset in ascending 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 follow 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 card:

 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) 

Answer 4

This will display the <bitset <N>, int> material 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 } }; }