Question about std::less behavior

Question

What is happening there?

#include <functional>

namespace A {
    struct Class { };
}

bool operator<(const A::Class& a, const A::Class& b)
{ return false; }

int main()
{
    std::less<A::Class>()(A::Class(), A::Class());
    return 0;
}

This is compiled ok. But if I use.

#include <set>

I got errors:

g++     test.cc   -o test
In file included from /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.2/include/g++-v4/bits/stl_tree.h:64:0,
                 from /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.2/include/g++-v4/set:60,
                 from lookup.cc:1:
/usr/lib/gcc/x86_64-pc-linux-gnu/4.5.2/include/g++-v4/bits/stl_function.h: In member function 'bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = A::Class]':
test.cc:15:49:   instantiated from here
/usr/lib/gcc/x86_64-pc-linux-gnu/4.5.2/include/g++-v4/bits/stl_function.h:230:22: error: no match for 'operator<' in '__x < __y'
make: *** [test] Error 1

Answer 1

Your operator< overload needs to be in the same namespace as Class (that is, it also needs to be in the A namespace).

C++ has complex name lookup rules. One of the more interesting "features" is "argument-dependent lookup," or ADL, where names can be looked up in namespaces associated with a function's arguments. For a class that has no base classes and isn't a nested class, like your Class, the only associated namespace is the namespace within which the class is located.

So, the only namespace associated with Class is A, so only the A namespace is searched during argument-dependent lookup for an operator< overload.

Charles Bailey's answer provides a good explanation of why you only see the problem when including <set>.

Answer 2

The reason that the lookup fails is that set introduces an operator< for std::set in the std namespace that hides all other global operator<.

The lookup of < in the instantiation of std::less happens inside a scope inside the std namespace. The only way that any operator< outside of std namespace will become visible is if ADL kicks into action and this only happens for the nearest enclosing namespace.

Without including <set>, there is no operator< introduced (and this is probably implementation dependent) in the std namespace that hides the global operator< and hence the non-ADL lookup rules can still find the global operator< which take A::Class.

Correction: As @JohannesSchaub points out, this analysis would only be correct if the declaration of operator< occurred before <functional> (where std::less is defined) was first included. As it is, the only overloads of a function called through an unqualified-id that should be visible to non-ADL lookup inside a template definition are those visible at the point of definition. Definitions introduced between the point of definition and the point of instantiation should only be visible for ADL lookup. (In an expression such as x < y candidate functions named operator< are searched for and this is one particular form of unqualified-id.)

As it stands, the overloaded operator< should not be considered a candidate with or without the <set> include, although these corner cases in the lookup rules are not always handled correctly by all compilers.

Answer 3

That operator< should be in namespace A as well, otherwise it cannot be looked up.

Details: First of all, simply calling operator< on two Class objects from main(), or even implementing your own less of course works whether operator< is in the same namespace as Class or not, although it should be in the same namespace since that's what everyone, including the implementors of the libraries, expects. Both gcc and MSVC 2010 (as I just tested) include several additional operator<'s in their standard libraries, between which the compiler fails to resolve.

gcc 4.5.2's error message is misleading. Compiling the same with a pre-release 4.6, I get the more specific

In file included from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_tree.h:65:0,
                 from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/set:60,
                 from test.cc:1:
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_function.h: In member function 'bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = A::Class]':
test.cc:9:42:   instantiated from here
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_function.h:234:22: error: no match for 'operator<' in '__x < __y'
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_function.h:234:22: note: candidates are:
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_pair.h:205:67: note: template<class _T1, class _T2> bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_iterator.h:290:46: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_iterator.h:340:47: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_tree.h:847:70: 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/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_set.h:712:46: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::set<_Key, _Compare, _Alloc>&, const std::set<_Key, _Compare, _Alloc>&)
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.0-alpha20110115/include/g++-v4/bits/stl_multiset.h:695:51: note: template<class _Key, class _Compare, class _Alloc> bool std::operator<(const std::multiset<_Key, _Compare, _Alloc>&, const std::multiset<_Key, _Compare, _Alloc>&)

Incidentally, SunCC (with both rw and stlport4) compiles this cleanly and even creates a usable std::set<A::Class>.