Why isn't std::find() using my operator==?
In the following snippet of code, I've overloaded the operator==
to compare my 开发者_JAVA技巧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')
}
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.
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.
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)
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 ofoperator ==
is not visible from there.ADL is a different story. Theoretically ADL can see names defined later, e.g. names visible from the point of
std::find
invocation insidemain
. 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 namespacestd
. One template argument ofstd:pair<>
is also fromstd
. Another is of fundamental typeint
, which has no associated namespace. Thereforestd
is the only associated namespace in this case. ADL looks instd
and only instd
. The above user-provided declaration ofoperator ==
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 ==
insidestd
. 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 ofoperator ==
were found instd
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 ==
.
Another "correct" solution:
struct RegPair : std::pair<std::string, int>
{
bool operator== (const std::string& rhs) const;
};
bool RegPair::operator== (const std::string& rhs) const
{
return first == rhs;
}
精彩评论