c++ – Why doesn't std::find use my operator==?

Question:

I implemented my operator== overload to compare my std::pair<...> with std::string . But for some reason the compiler can't find this overload. With what it can be connected?

Code to reproduce the error:

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

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

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

int main()
{
    std::vector<RegPair> sequence;
    std::string foo("foo");
    std::find(sequence.begin(), sequence.end(), foo);
}

Error text:

  • GNU GCC:

    error: no match for 'operator==' in '__first. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* with _Iterator = std::pair, std::allocator >, int>*, _Container = std::vector, std::allocator >, int>, std:: allocator, std::allocator >, int> > > == __val'

  • clang:

    error: invalid operands to binary expression ('std::pair, int>' and 'std::basic_string const')

This question is a loose translation of Why isn't std::find() using my operator==? ".

Answer:

The answer from the link from which the translation was made is incorrect/inaccurate. ADL search does not replace/exclude regular search in any way, but only supplements it.

The correct description of the situation is as follows:

  1. The normal search is performed from the call site of the == operator in the definition of the std::find function template in the standard library. It only finds names that are visible from that location.

    It is clear that the given definition of the == operator is not visible from there.

  2. ADL lookups are performed on the associated , and only on the associated namespaces, and see those namespaces as they were at the time the std::find function was called in the calling code. The set of associated namespaces is built according to the rules described in 6.4.2/2 .

    In this case, from the call point of std::find , the above definition of the == operator is clearly visible. But this definition is made in the global namespace. And in this case, only the std space is associated for ADL, because both comparison arguments belong to the std space. Therefore, the global namespace is not considered by ADL and this definition is not found.

    The assertion that ADL allegedly stops further search for operator == definitions precisely because some operator == definitions have already been found inside std is incorrect. ADL always looks for names only within associated namespaces. Unlike a regular lookup, ADL never expands the scope of the search beyond the associated namespaces, whether or not something is found there.

The same problem can be illustrated by the following small example

namespace N
{
  struct S {};
}

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

void bar(N::S s) {}

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

With this declaration order, normal name lookup finds names visible from point 1, but ADL lookup finds names visible from point 2, but only in associated namespaces . The global namespace is not associated, so the void bar(N::S s) declaration is not found and the code does not compile.

In the original version, if we somehow "pull" the global namespace as an associated one for ADL, then this == operator will immediately begin to be through ADL. For example, let's declare in the global namespace some fictitious type cast to std::string and use it as a search key

...

struct S : std::string
{
    using std::string::string;
};

int main()
{
    std::vector<RegPair> sequence;
    S foo("foo");
    std::find(sequence.begin(), sequence.end(), foo);
}

The definition of the comparison operator does not need to be changed. The code will immediately start compiling and using this comparison operator.

Another option for a seemingly "innocent" substitution that will make the code compile is to make the second member of the pair a type from the global namespace

struct X {};
typedef std::pair<std::string, X> RegPair;

Nothing else needs to be changed – this is already enough to associate the global namespace for ADL.

Post Views: 6
Scroll to Top