17

I'd expect in the example bellow compiler will fail to compile the code, since it doesn't know what is "find()", which defined in std namespace in algorithm header.

However this code compiles on RHEL 5.3 with gcc 4.1.2.

What do I miss?

#include <string>    
#include <algorithm>

int main()
{
    std::string s;
    find(s.begin(), s.end(), 'a');  // should not compile
}
dimba
  • 26,717
  • 34
  • 141
  • 196

1 Answers1

27

This works due to Argument Dependent Lookup. The function-template is searched in the namespace of the arguments types. In this case, the arguments are std::string::iterator, so the function is searched in the namespace std.

Jan Hudec
  • 73,652
  • 13
  • 125
  • 172
Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
  • +1 — ADL begins to make more sense in some contexts: Extending boost::hash_value, for example, can be done using ADL. – Thanatos May 19 '11 at 08:28
  • 2
    Aka Koenig lookup. dimba: if you want to prove this to yourself, you can see that `::find` won't get a match in the global namespace, and given `char a[1]`, `find(&a[0], &a[0], 'a')` won't find the `std::find() template`.... – Tony Delroy May 19 '11 at 08:29
  • 6
    Just to elaborate on *why* ADL exists, the "primary" justification for ADL is so that operators work naturally. given two `std::string` objects `s1` and `s2`, you want to be able to concatenate them with `s1 + s2`. Without ADL, you'd have to write `std::operator+(s1, s2)`. But it has turned out to be a very useful mechanism for other cases as well – jalf May 19 '11 at 08:41
  • Another good example for how ADL can be used to customize the Standard Library is shown [here](http://stackoverflow.com/questions/11562/how-to-overload-stdswap/2684544#2684544). – Björn Pollex May 19 '11 at 08:44
  • @jalf: Is that example really sound? As far as I can see (which isn't very far tonight - got to stop playing stupid games until 4am), a global `::operator+(const std::string&, const std::string&)` could be matched anyway. So, it's more about finding the right `find()` despite other unrelated `find()`s in intervening namespaces associated with the calling code.... – Tony Delroy May 19 '11 at 09:28
  • @Space_C0wb0y: I met this behavior a couple of years ago. I was not compiling using `-ansi` and "thus" able to access STL types without prefixing with `std`. Would you mind having a look at my [issue](http://stackoverflow.com/questions/5990898/how-to-overload-the-ostream-operator-to-make-it-work-with-log4cxx-in-c)? – mister why May 19 '11 at 09:51
  • @mister: Sorry, but I cannot help you there. – Björn Pollex May 19 '11 at 10:03
  • @Tony: but then they'd have to put standard library components outside of the `std` namespace, which would make the namespace pretty pointless. – jalf May 19 '11 at 10:47
  • @jalf: not really - the names of the function parameter types - including their use of `std::` - partake in the formation of the overall linker symbol anyway, so such a global function's still safe from clashes.... – Tony Delroy May 19 '11 at 13:05
  • @Tony: True, but my point was simply that the standard library is otherwise consistent about placing everything in a `std` namespace. Suddenly deciding that "hey, let's put all the operator overloads in the global namespace" would seem very inconsistent, and, with modern IDE's offering intellisense and autocompletion, would clutter up the global namespace needlessly. – jalf May 19 '11 at 13:25
  • Keep in mind also that the standard prohibits users from adding or modifying anything in namespace `std` (with an exception made specifically for template specializations for user-defined types). Putting standard library components outside that namespace would needlessly complicate that issue. Yes, they could have worked around the operator problem without adding ADL, but it would have been a messy, inconsistent and misleading hack, and it would have prevented users from doing what seems intuitive (putting the operators next to the class they operate on) – jalf May 19 '11 at 13:31