What is "Argument-Dependent Lookup" (aka ADL, or "Koenig Lookup")?

Question

What are some good explanations on what argument dependent lookup is? Many people also call it Koenig Lookup as well.

Preferably I'd like to know:

• Why is it a good thing?
• Why is it a bad thing?
• How does it work?

Answer 1

In Koenig Lookup, if a function is called without specifying its namespace, then the name of a function is also searched in namespace(s) in which the type of the argument(s) is defined. That is why it is also known as Argument-Dependent name Lookup, in short simply ADL.

It is because of Koenig Lookup, we can write this:

std::cout << "Hello World!" << "\n";

Otherwise, we would have to write:

std::operator<<(std::operator<<(std::cout, "Hello World!"), "\n");

which really is too much typing and the code looks really ugly!

In other words, in the absence of Koenig Lookup, even a Hello World program looks complicated.

Answer 2

Maybe it is best to start with the why, and only then go to the how.

When namespaces were introduced, the idea was to have everything defined in namespaces, so that separate libraries don't interfere with each other. However that introduced a problem with operators. Look for example at the following code:

namespace N
{
  class X {};
  void f(X);
  X& operator++(X&);
}

int main()
{
  // define an object of type X
  N::X x;

  // apply f to it
  N::f(x);

  // apply operator++ to it
  ???
}

Of course you could have written N::operator++(x), but that would have defeated the whole point of operator overloading. Therefore a solution had to be found which allowed the compiler to find operator++(X&) despite the fact that it was not in scope. On the other hand, it still should not find another operator++ defined in another, unrelated namespace which might make the call ambiguous (in this simple example, you wouldn't get ambiguity, but in more complex examples, you might). The solution was Argument Dependent Lookup (ADL), called that way since the lookup depends on the argument (more exactly, on the argument's type). Since the scheme was invented by Andrew R. Koenig, it is also often called Koenig lookup.

The trick is that for function calls, in addition to normal name lookup (which finds names in scope at the point of use), there is done a second lookup in the scopes of the types of any arguments given to the function. So in the above example, if you write x++ in main, it looks for operator++ not only in global scope, but additionally in the scope where the type of x, N::X, was defined, i.e. in namespace N. And there it finds a matching operator++, and therefore x++ just works. Another operator++ defined in another namespace, say N2, will not be found, however. Since ADL is not restricted to namespaces, you also can use f(x) instead of N::f(x) in main().

Answer 3

Not everything about it is good, in my opinion. People, including compiler vendors, have been insulting it because of its sometimes unfortunate behavior.

ADL is responsible for a major overhaul of the for-range loop in C++11. To understand why ADL can sometimes have unintended effects, consider that not only the namespaces where the arguments are defined are considered, but also the arguments of template arguments of the arguments, of parameter types of function types / pointee types of pointer types of those arguments, and so on and forth.

An example using boost

std::vector<boost::shared_ptr<int>> v;
auto x = begin(v);

This resulted in an ambiguity if the user uses the boost.range library, because both std::begin is found (by ADL using std::vector) and boost::begin is found (by ADL using boost::shared_ptr).