ビットセットをキーとしてマップを使用する際の問題

Question

bitsetをキーにC++でmapを作成しようとしています。しかし、コンパイラはprogamコードは、私はC++でのマップのキーとしてビットセットを使用しようとしています の下に与えられている次のエラーメッセージ

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>&) 

を生成します。しかし、私は以下のコードを実行するたびに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; 
} 

Answer 1

ちょうどあなた自身のコンパレータクラスを使用します。あなたがいる限り、彼らはunsigned long型に変換されるのに十分小さいとして、任意の長さのビットセットをサポートするために、このソリューションを拡張することができ

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; 

注：

を

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

比較機能を定義することができます。 bitsetが符号なし整数値をモデル化すると仮定すると、次の関数はbitsetを昇順に並べ替えます（そしていずれもNで動作します）。あなたはこのマップを持っています

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

：あなたは、次のスニペットを実行する場合

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

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 3

これは、マップ<ビットセット<N>を許可するには、>もの直接をint型：

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

Answer 4

代替ソリューションは、まだあなたの要件を満たしている場合は、単にunordered_mapを使用することです。

これは、C++バージョンまたはperformance considerationsに応じて、std::unordered_map<bitset<N>, T>またはboost::unordered_map<bitset<N>, T>です。

これにより、比較の必要性がなくなり、要件に応じてmay prove fasterが不要になります。