Dependent Lookup" (aka ADL, or "Koenig Lookup")?
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:
(Note: This is meant to be an entry to Stack Overflow's C++ FAQ.)
Koenig Lookup is also commonly known as Argument Dependent Lookup in C++ and most of the Standard C++ compilers support it.
The C++11 standard § 3.4.2/1 states:
When the postfix-expression in a function call (5.2.2) is an unqualified-id, other namespaces not considered during the usual unqualified lookup (3.4.1) may be searched, and in those namespaces, namespace-scope friend function declarations (11.3) not otherwise visible may be found. These modifications to the search depend on the types of the arguments (and for template template arguments, the namespace of the template argument).
In simpler terms Nicolai Josuttis states1:
You don't have to qualify the namespace for functions if one or more argument types are defined in the namespace of the function.
A simple code example:
namespace MyNamespace
{
class MyClass {};
void doSomething(MyClass);
}
MyNamespace::MyClass obj; // global object
int main()
{
doSomething(obj); // Works Fine - MyNamespace::doSomething() is called.
}
In the above example there is neither a using-declaration nor a using-directive but still the compiler correctly identifies the unqualified name doSomething() as the function declared in namespace MyNamespace by applying the Koenig algorithm.
How does it work?
The algorithm tells the compiler to not just look at local scope, but also the namespaces that contain the argument's type. Thus, in the above code, the compiler finds that the object obj , which is the argument of the function doSomething() , belongs to the namespace MyNamespace . So, it looks at that namespace to locate the declaration of doSomething() .
What is the advantage of Koenig Lookup ?
As the simple code example above demonstrates above the Koenig Algorithm provides convenience and ease of usage to the programmer. Without Koenig Algorithm there would be an overhead on the programmer, to repeatedly specify the fully qualified names, or instead, use numerous using-declarations.
Why the criticism of Koenig Algorithm ?
Over dependence on Koenig Algorithm can lead to semantic problems,and catch the programmer off guard sometimes.
Consider the example of std::swap , which is a standard library algorithm to swap two values. With the Koenig algorithm one would have to be cautious while using this algorithm because:
std::swap(obj1,obj2);
may not show the same behavior as:
using std::swap;
swap(obj1, obj2);
With ADL, which version of swap function gets called would depend on the namespace of the arguments passed to it.
If there exists an namespace A and if A::obj1 , A::obj2 & A::swap() exist then the second example will result in a call to A::swap() which might not be what the user wanted.
Further, if for some reason both:
A::swap(A::MyClass&, A::MyClass&) and std::swap(A::MyClass&, A::MyClass&) are defined, then the first example will call std::swap(A::MyClass&, A::MyClass&) but the second will not compile because swap(obj1, obj2) would be ambiguous.
Trivia:
Why is it called Koenig Lookup ?
Because it was devised by former AT&T and Bell Labs researcher and programmer, Andrew Koenig .
Good Reads:
Herb Sutter's Name Lookup on GotW
Standard C++03/11 [basic.lookup.argdep]: 3.4.2 Argument-dependent name lookup.
1 The definition of Koenig Algorithm is as defined in Josuttis's book, The C++ Standard Library: A Tutorial and Reference .
In Koenig Lookup, if a function is called without specifying it's namespace, then the name of a function is also search 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, in the absense of Koenig Lookup, we have to write:
std::operator<<(std::operator<<(std::cout, "Hello World!"), "n");
which is really too much typying and the code looks really ugly!
In other words, in the absence of Koenig Lookup, even a Hello World program looks complicated.
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, ie 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() .