8

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; }
Improve this question

5 Answers 5

Reset to default
7

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;
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

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.
Yes, i have pointed that out in the templated solution. Thanks for the clarification anyway.
@MatthieuM.: to_ulong (as the name suggests) converts to unsigned long, so we have 32 guaranteed bits here.
@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.
@PlasmaHH: oups right, I slipped there. However it does not change the fundamental issue.
|
4

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.

Improve this answer

Comments

2

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)
Improve this answer

Comments

0

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 } }; }
Improve this answer

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.