Find () using the overloaded operator ==

Question

I am trying to find an element in a vector using the overloaded operator == (). However, when using type1 in the following code, the output is 1 and 0 (not found). Using type2 gives both 1 and 1. Environment - 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

The answer from @AlexanderGessler is incomplete in a few details. So, will you allow the compiler to play for both expressions and both types?

Expression 1

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

First, for type1 and type2 , the search for an unqualified name starts from the main() function area outward and finds your own operator== function in the global area.

Secondly, an argument-dependent name (ADL) lookup finds an operator== function template for std::pair from namespace std . In fact, ADL finds much more std::operator== function templates (those of std::vector and std::string , since you also included these headers).

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

---

3.4.2 Search for argument-dependent names [basic.lookup.argdep]

- If T is a class type (including associations), its associated classes: the class itself; the class of which he is a member, if any; and these are direct and indirect base classes. Its associated namespaces are the namespace of which the associated classes are members.

---

Thirdly, the output of the template argument is performed for all found function templates. For type1 only the function template for std::pair will withstand the deduction argument (and it will output its template arguments as std::string and int , respectively). However, for type2 there is no set of template arguments that will match, because type2 not an instance of the std::pair template.

Fourth, overload resolution takes effect. For type1 your own operator== function and the std::operator== function std::operator== have equal rank (exact match). Therefore, a tie-break will select your function without a template. 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), although for different reasons.

Expression 2

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

Here we need to resolve the find call first. Due to your using namespace std; , a search for an unqualified name already finds (not a pun) std::find , but even without the using ADL directive on the std::vector iterator, it would find it. It will print the third template argument for std::find either type1 or type2 .

Inside std::find a call to operator== . Again, a regular search will be performed first. However, this comes from within the namespace std . It will find several function templates operator== (for std::vector , std::string and std::pair ). As soon as candidates in one area are found when searching for an unqualified name, this phase of the search for names ends.

However, ADL is still running. Note that the global namespace is not an associated namespace with type1 , because it is only a typedef for the class in namespace std . So, for type1 ADL does not find anything new. In contrast, type2 has a global namespace as its corresponding namespace, and therefore ADL will find your operator== function template in this case.

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

This leaves permission to overload. For type1 there is only one viable function (an instance of the std::operator== template), and overload resolution does not come into play. For type2 there is also only one viable function (viable, since it requires only a standard derived-to-base conversion). Therefore, 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 complicated with multiple overloads in different namespaces, here is a pivot table with the holy trinity (searching for a name, outputting arguments and resolving overloads). For each phase and for each type, I have listed the surviving candidates after this phase. The bottom line shows the function being called.

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 an unqualified search finds a different name depending on the scope in which it starts (the scope within the global scope and the namespace scope), and that ADL similarly finds a different name depending on which namespace is considered to be related ( namespace std vs global namespace).

Answer 2

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

What actually happens for TYPE == type1 (correct me if I am wrong)

• for v1 == v2 ADL (search for argument dependencies) is used to search for operator== in std , which means that this operator is added to the normal overload set. However, the version without the template in the current translation block is still preferable to the operator== template from std .
• The call to std::find is done in std , so the search for operator== starts directly in std . It finds one match (without using ADL!) And, therefore, does not look for an enclosing area that would contain its own OP statement.

And for TYPE == type2

• v1 == v2 easy - directly finds operator== in the enclosing namespace.
• std::find also specified in std , but a user statement from the main area is added to the overload resolution set using ADL, and then it turns out to be more specific than the one in std .

Answer 3

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

Answer 4

I think you better use find_if instead of searching. It takes a predicate, so you can just define your comparator as a regular function / functor and pass it.