Why isn't std::find() using my operator==?

Question

In the following snippet of code, I've overloaded the operator== to compare my pair type with string. But for some reason, the compiler isn't finding my operator as a match for the find function. Why not?

Edit: Thanks for all the suggestions for alternatives, but I'd still like to understand why. The code looks like it should work; I'd like to know why it doesn't.

#include <vector>
#include <utility>
#include <string>
#include <algorithm>

typedef std::pair<std::string, int> RegPair;
typedef std::vector<RegPair> RegPairSeq;

bool operator== (const RegPair& lhs, const std::string& rhs)
{
    return lhs.first == rhs;
}

int main()
{
    RegPairSeq sequence;
    std::string foo("foo");
    // stuff that's not important
    std::find(sequence.begin(), sequence.end(), foo);
    // g++: error: no match for 'operator==' in '__first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, _Container = std::vector<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > >]() == __val'
    // clang++: error: invalid operands to binary expression ('std::pair<std::basic_string<char>, int>' and 'std::basic_string<char> const')
}

Answer 1

The problem is that std::find is a function template and it uses argument-dependent lookup (ADL) to find the right operator== to use.

Both of the arguments are in the std namespace (std::pair<std::string, int> and std::string), so ADL starts by looking in the std namespace. There it finds some operator== (which one, it doesn't matter; there are lots in the Standard Library and if you've included <string>, at least the one that compares two std::basic_string<T> objects could be found).

Because an operator== overload is found in the std namespace, ADL stops searching enclosing scopes. Your overload, which is located in the global namespace, is never found. Name lookup occurs before overload resolution; it doesn't matter during name lookup whether the arguments match.

Answer 2

The cleanest solution is to make a predicate and use find_if:

struct StringFinder
{
  StringFinder(const std::string & st) : s(st) { }
  const std::string s;
  bool operator()(const RegPair& lhs) const { return lhs.first == s; }
}

std::find_if(sequence.begin(), sequence.end(), StringFinder(foo));

If you have C++11 you can use a lambda instead.

Answer 3

The accepted answer is, unfortunately, misleading.

Overload resolution for operator == used inside std::find function template is performed by both regular lookup and argument-dependent lookup (ADL)

1. Regular lookup is performed in accordance with usual rules of unqualified name lookup. It is looked up from the definition of std::find in standard library. Obviously, the above user-provided declaration of operator == is not visible from there.

2. ADL is a different story. Theoretically ADL can see names defined later, e.g. names visible from the point of std::find invocation inside main. However, ADL does not just see everything. ADL is restricted to searching only inside so called associated namespaces. These namespaces are brought into the consideration by types of arguments used in the invocation of operator == in accordance to the rules of 6.4.2/2.

   In this example types of both arguments of == belong to namespace std. One template argument of std:pair<> is also from std. Another is of fundamental type int, which has no associated namespace. Therefore std is the only associated namespace in this case. ADL looks in std and only in std. The above user-provided declaration of operator == is not found, since it resides in global namespace.

   It is incorrect to say that ADL stops looking after finding some "other" definitions of operator == inside std. ADL does not work in "inside-out" fashion as other forms of lookup often do. ADL searches in associated namespaces and that's it. Regardless of whether any other forms of operator == were found in std or not, ADL does not attempt to continue its search in global namespace. This is the incorrect/misleading part of the accepted answer.

Here's a more compact example that illustrates the same issue

namespace N
{
  struct S {};
}

template<typename T> void foo(T a) 
{
  bar(a);
}

void bar(N::S s) {}

int main()
{
  N::S a;
  foo(a);
}

Ordinary lookup fails since there's no bar declared above foo. Seeing that bar is called with an argument of N::S type, ADL will look for bar in associated namespace N. There's no bar in N either. The code is ill-formed. Note that absense of bar in N does not make ADL to expand its search into the global namespace and find global bar.

It is quite easy to inadvertently change the set of associated namespaces used by ADL, which is why such issues often come and go after seemingly innocent and unrelated changes in the code. For example, if we change the declaration of RegPair as follows

enum E { A, B, C };
typedef std::pair<std::string, E> RegPair;

the error will suddenly disappear. After this change global namespace also becomes associated for ADL, along with std, which is why ADL finds the user-provided declaration of operator ==.