iouvxz iouvxz - 3 months ago 15
C++ Question

c++ Compiler can't use my overloaded < operator for bitset key comparison

I know I can always use the set(comp) constructor to initialize the comparasion function for my set .

But I usually prefer overloading the operator < .

So when I want to use bitsets as set keys ,I use this code below .

#include <bitset>
#include <set>
using namespace std;

bool operator<(const std::bitset<128>& x, const std::bitset<128>& y)
{
return false;//show the brief idea of overloading operator< ,never mind .
};

int main()
{
set<bitset<128> > s{ bitset<128>() };
return 0;
}


The compiler gives me these compile errors below .

Error 1 error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 2 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 3 error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 4 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 5 error C2784: 'bool std::operator <(const std::move_iterator<_RanIt> &,const std::move_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::move_iterator<_RanIt> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 6 error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 7 error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 8 error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const std::bitset<128>' c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test
Error 9 error C2676: binary '<' : 'const std::bitset<128>' does not define this operator or a conversion to a type acceptable to the predefined operator c:\program files (x86)\microsoft visual studio 12.0\vc\include\xstddef 193 1 test


But this piece of code compiles .

#include <bitset>
#include <set>
using namespace std;

struct wrapper
{
std::bitset<128> a;
};

bool operator<(const std::bitset<128>& x, const std::bitset<128>& y)
{
return false;
};

bool operator<(const wrapper& x, const wrapper& y)
{
return x.a<y.a;
};

int main()
{
set<wrapper> s{ wrapper() };
return 0;
}


I wonder why .

Answer

This has everything to do with the complexities of name lookup in C++.

By default, std::set uses std::less<Key> as its comparator, whose implementation looks approximately like:

template <class K>
struct less {
    bool operator()(K const& lhs, K const& rhs) const {
        return lhs < rhs;  // (*)
    }
};

The marked line is where < is actually called. To find which < to call, we look in the scope of the template definition (which will not find your operator<) and we look in the associated namespaces of the arguments (which is std::, and your operator< is not in that namespace. It would actually be illegal to add it to that namespace too). Since neither of those lookups will find anything, the code is ill-formed.

Your second example fixes the argument-dependent part of the lookup: now there is an operator< in the associated namespace of the argument (which is ::), and it will be found.

Note that you can still have a std::set of std::bitset<N>. You just have to provide a custom comparator to the class template.

Comments