find() using overloaded operator==

Question

I try to find an element in a vector using overloaded operator==(). However, if using type1 in the following code, the output is 1 and 0 (not found). Using type2 gives both 1 and 1. The environment is Xubuntu 12.04 and g++ version 4.6.3.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<string, int> type1;
struct type2: public type1 {};
#define TYPE type1

bool operator== (const TYPE& lhs, const TYPE& rhs) {
    return lhs.first == rhs.first;
}

int main()
{
    vector<TYPE> vec;
    TYPE v1, v2;

    v1.first = "abc"; v1.second = 1; vec.push_back(v1);
    v2.first = "abc"; v2.second = 2;

    cout << (v1 == v2) << endl;
    cout << (find(vec.begin(), vec.end(), v2) != vec.end()) << endl;
}

Answer 1

std::pair has its default operator== in namespace std, which is a template for arbitrary pairs, comparing both the first and the second fields. This operator gets picked in one of the four cases, namely find with TYPE == type1. The details are a bit complicated though:

What actually happens for TYPE == type1 is (correct me if I'm wrong)

• for v1 == v2 ADL (Argument Dependent Name Lookup) is applied to find the operator== in std, meaning this operator is added to the normal overload set. However, the non-template version in the current translation unit is still preferred against the template operator== from std.
• The std::find call is instanced within std, thus lookup for operator== starts directly in std. It finds one match (without using ADL!) and therefore does not search the enclosing scope which would have contained the OP's own operator.

And for TYPE == type2

• v1 == v2 is easy -it directly finds the operator== in the enclosing namespace.
• std::find is also instanced in std, but the custom operator from the main scope is added to the overload resolution set using ADL and then found to be more specific than the one in std.

Answer 2

The answer by @AlexanderGessler is incomplete in several details. So let's play compiler for both expressions and both types, shall we?

Expression 1

cout << (v1 == v2) << endl;

First, for both type1 and type2, unqualified name lookup starts at the main() function scope outwards, and finds your own operator== function at the global scope.

Second, argument-dependent name lookup (ADL) finds the function template operator== for std::pair from namespace std. Actually, ADL finds many more std::operator== function templates (those from std::vector and std::string, since you included those headers as well).

Note: ADL also finds a match for type2, because its base class type1 will add namespace std to the set of its associated namespaces.

---

3.4.2 Argument-dependent name lookup [basic.lookup.argdep]

— 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 of which its associated classes are members.

---

Third, template argument deduction takes place for all found function templates. For type1, only the function template for std::pair will survive argument deduction (and it deduces its template arguments to be std::string and int, respectively). However, for type2, there is no set of template arguments that will fit because type2 is not an instantiation of a std::pair template.

Fourth, overload resolution comes into play. For type1, both your own function operator== and the std::operator== function template are of equal rank (Exact Match). Therefore the tie-break will select your non-template function. For type2, there is only one viable function so overload resolution does not come into play and your function will be selected.

Conclusion 1: type1 and type2 will give the same answer (your version is selected), albeit for different reasons.

Expression 2

cout << (find(vec.begin(), vec.end(), v2) != vec.end()) << endl;

Here we need to first resolve the call to find. Because of your using namespace std;, unqualified name lookup already finds (no pun intended) std::find, but even without the using directive, ADL on the std::vector iterator would have found it. It will deduce the third template argument for std::find to either type1 or type2.

Within std::find, a call to operator== is found. Again, ordinary lookup will be performed first. However, this takes place from within namespace std. It will find several operator== function templates (for std::vector, std::string and std::pair). As soon as candidates in one scope are found during unqualified name lookup, this phase of name lookup stops.

However, ADL is still being performed. Note though that the global namespace is not an associated namespace to type1 because it is only a typedef to a class in namespace std. So for type1, ADL does not find anything new. In contrast, type2 does have the global namespace as its associated namespace and so ADL will find your operator== function template in that case.

For type1, template-argument-deduction finds std::string and int as template arguments for the operator== function template for std::pair. For type2, there is again no set of template arguments that will fit because type2 is not an instantiation of a std::pair template.

That leaves overload resolution. For type1, there is only one viable function (the instance of the std::operator== template), and overloads resolution does not come into play. For type2, there is also only one viable function (viable because it only requires a standard derived-to-base conversion). Hence overload resolution also does not come into play.

Conclusion 2: for type1 (std version) and type2 (your version) you get different results.

Summary

Just because these things can get very tricky with multiple overloads in different namespaces, here's a summary table with the holy trinity (name lookup, argument deduction and overload resolution). For each phase, and for each type, I have listed the surviving candidates after that phase. The bottom row shows the called function.

Expression 1

+---------------------+-----------------+-----------------+
| phase               | type1           | type2           |
+---------------------+-----------------+-----------------+
| unqualified lookup  |    ::operator== |    ::operator== |
| ADL                 | std::operator== | std::operator== |
+---------------------+-----------------+-----------------+
| argument deduction  |    ::operator== |    ::operator== |
|                     | std::operator== |                 |
+---------------------+-----------------+-----------------+
| overload resolution |    ::operator== |    ::operator== |
+---------------------+-----------------+-----------------+

Expression 2

+---------------------+-----------------+-----------------+
| phase               | type1           | type2           |
+---------------------+-----------------+-----------------+
| unqualified lookup  | std::operator== | std::operator== |
| ADL                 |                 |    ::operator== |
+---------------------+-----------------+-----------------+
| argument deduction  | std::operator== |    ::operator== |
+---------------------+-----------------+-----------------+
| overload resolution | std::operator== |    ::operator== |
+---------------------+-----------------+-----------------+

Note that unqualified lookup finds a different name depending on the scope it starts in (function scope inside global scope versus namespace scope), and that ADL similarly finds a different name depending on which namespace is considered associated (namespace std vs the global namespace).

Answer 3

std::pair has its own operator== that takes precedence over your own.

Answer 4

I think you're better off using find_if instead of find. It takes a predicate, so you can just define your comparer as an ordinary function/functor and pass it.