Ambiguous call to templated function due to ADL

Question

I've been bitten by this problem a couple of times and so have my colleagues. When compiling

#include <deque>
#include <boost/algorithm/string/find.hpp>
#include <boost/operators.hpp>

template< class Rng, class T >    
typename boost::range_iterator<Rng>::type find( Rng& rng, T const& t ) {
      return std::find( boost::begin(rng), boost::end(rng), t );
}

struct STest {
      bool operator==(STest const& test) const { return true; }
};

struct STest2 : boost::equality_comparable<STest2>   {
      bool operator==(STest2 const& test) const { return true; }
};

void main() {
      std::deque<STest> deq;
      find( deq, STest() ); // works
      find( deq, STest2() ); // C2668: 'find' : ambiguous call to overloaded function
}

...the VS9 compiler fails when compiling the second find. This is due to the fact that STest2 inherits from a type that is defined in boost namespace which triggers the compiler to try ADL which finds boost::algorithm::find(RangeT& Input, const FinderT& Finder).

An obvious solution is to prefix the call to find(…) with "::" but why is this necessary? There is a perfectly valid match in the global namespace, so why invoke Argument-Dependent Lookup? Can anybody explain the rationale here?

Answer 1

I'll add the obvious answer myself because I just did some research on this problem:

C++03 3.4.2

§2 For each argument type T in the function call, there is a set of zero or more associated namespaces [...] The sets of namespaces and classes are determined in the following way:

[...]

— If T is a class type (including unions), its associated classes are: the class itself; the class of which it is a member, if any; and its direct and indirect base classes. Its associated namespaces are the namespaces in which its associated classes are defined.

§ 2a If the ordinary unqualified lookup of the name finds the declaration of a class member function, the associated namespaces and classes are not considered. Otherwise the set of declarations found by the lookup of the function name is the union of the set of declarations found using ordinary unqualified lookup and the set of declarations found in the namespaces and classes associated with the argument types.

At least it's standard conformant, but I still don't understand the rationale here.

Answer 2

Consider a mystream which inherits from std::ostream. You would like that your type would support all the << operators that are defined for std::ostream normally in the std namespace. So base classes are associated classes for ADL.

I think this also follows from the substitution principle - and functions in a class' namespace are considered part of its interface (see Herb Sutter's "What's in a class?"). So an interface that works on the base class should remain working on a derived class.

You can also work around this by disabling ADL:

(find)( deq, STest2() );

Answer 3

ADL isn't a fallback mechanism to use when "normal" overload resolution fails, functions found by ADL are just as viable as functions found by normal lookup.

If ADL was a fallback solution then you might easily fall into the trap were a function was used even when there was another function that was a better match but only visible via ADL. This would seem especially strange in the case of (for example) operator overloads. You wouldn't want two objects to be compared via an operator== for types that they could be implicitly converted to when there exists a perfectly good operator== in the appropriate namespace.

Answer 4

I think you stated the problem yourself:

in the global namespace

Functions in the global namespace are considered last. It's the most outer scope by definition. Any function with the same name (not necessarily applicable) that is found in a closer scope (from the call point of view) will be picked up first.

template <typename Rng, typename T>
typename Rng::iterator find( Rng& rng, T const& t );

namespace foo
{
  bool find(std::vector<int> const& v, int);

  void method()
  {
    std::deque<std::string> deque;
    auto it = find(deque, "bar");
  }
}

Here (unless vector or deque include algorithm, which is allowed), the only method that will be picked up during name look-up will be:

bool foo::find(std::vector<int> const&, int);

If algorithm is somehow included, there will also be:

template <typename FwdIt>
FwdIt std::find(FwdIt begin, FwdIt end,
                typename std::iterator_traits<FwdIt>::value_type const& value);

And of course, overload resolution will fail stating that there is no match.

Note that name-lookup is extremely dumb: neither arity nor argument type are considered!

Therefore, there are only two kinds of free-functions that you should use in C++:

• Those which are part of the interface of a class, declared in the same namespace, picked up by ADL
• Those which are not, and that you should explicitly qualified to avoid issues of this type

If you fall out of these rules, it might work, or not, depending on what's included, and that's very awkward.