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

Asked 13/11, 2011 at 12:58 Answered 13/11, 2011 at 13:33

Solved c++argument-dependent-lookup name-lookup c++-faq

226

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?

Leela answered 13/11, 2011 at 12:58 Comment(3)

gotw.ca/gotw/030.htm – Claudine 13/11, 2011 at 13:17

It is a good thing because Otherwise: std::cout << "Hello world"; would not compile – Altorelievo 13/11, 2011 at 13:30

en.cppreference.com/w/cpp/language/adl – Sitka 19/3, 2018 at 9:39

288

Argument Dependent Lookup (ADL), sometimes called Koenig Lookup, describes how unqualified names are looked up by the compiler in C++.

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 states¹:

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 ADL.

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 ADL?

As the simple code example above demonstrates, ADL provides convenience and ease of usage to the programmer. Without ADL 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 ADL?

Over-reliance on ADL 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 ADL 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 a namespace A, and if A::obj1, A::obj2, and 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 sometimes called a “Koenig lookup”?

Because it was devised by former AT&T and Bell Labs researcher and programmer, Andrew Koenig, although Koenig himself disputes this in a 2012 blog post:

The reason that my name is associated with argument-dependent lookup is that although I did not invent the idea, I did recognize that the introduction of namespaces causes a severe problem that ADL, or something similar, was needed to solve.

The example in the criticism of the Koenig Algorithm can be considered a "feature" of Koenig lookup as much as a "con". Using std::swap() in such a way is a common idiom: Provide a 'using std::swap()' in case a more specialized version A::swap() is not provided. If a specialized version of A::swap() is available, we would normall want that one to be called. This provides more genericity for the swap() call, since we can trust the call to compile and work, but we can also trust the more specialized version to be used if there is one. – Laundryman 9/12, 2014 at 19:16

@anthrond There is more into this. With std::swap you actually have to do that since the only alternative would be to add std::swap template function explicit specialization for your A class. Yet if your A class is a template itself it would be partial specialization rather than explicit specialization. And partial specialization of template function is not allowed. Adding overload of std::swap would be an alternative but is explicitly forbidden (you may not add things to std namespace). So ADL is the only way for std::swap. – Familist 10/4, 2015 at 11:23

I would have expected to see a mention of overloaded operators under "advantage of koenig lookup". the example with std::swap() seems a bit backwards. I would expect the problem do be when std::swap() is selected rather than the overload specific to the type, A::swap(). The example with std::swap(A::MyClass&, A::MyClass&) seems misleading. since std would never have a specific overload for a user type, I don't think it's a great example. – Patois 24/10, 2016 at 16:26

ERROR: prog.cpp:(.text.startup+0x7): undefined reference to MyNamespace::doSomething(MyNamespace::MyClass)'`. – Shamikashamma 6/9, 2017 at 11:36

@Shamikashamma ...And? We can all see that the function was never defined. Your error message proves that it worked, actually, because it's looking for MyNamespace::doSomething, not just ::doSomething. – Zhao 12/6, 2018 at 23:47

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.

Warga answered 13/11, 2011 at 13:7 Comment(9)

The example is actually incorrect. It would be correct if (for example) std::string was used instead of string literal. See Koenig's explanation: drdobbs.com/cpp/a-personal-note-about-argument-dependent/… – Familist 10/4, 2015 at 11:54

@AdamBadura: Please note that std::cout is one argument to the function, which is enough to enable ADL. Did you notice that? – Warga 10/4, 2015 at 15:58

@Nawaz Funny thing. I was about to prove my point since Koenig's article apparently didn't convince you. But while doing that I realized that operator<< for const char* is not a member but a global function. So Koenig is wrong there. Then I thought that it is unlikely that no one noticed it so far and if there are comments surly someone already pointed that out. And I wasn't mistaken. Indeed someone did pointed that out. It was you! ;) Sorry for my mistake, now I stand corrected! – Familist 11/4, 2015 at 18:25

@Nawaz: Why you have written std::operator<< 2 times? Is it allowed to write std::operator<<(std::operator<<(std::cout, "Hello World!"), std::endl); explicitly? Why you have used std:: before operator keyword? Thanks – Coacervate 26/5, 2015 at 16:12

@meet: Your question needs a long answer which cannot be provided in this space. So I can only advise you to read on topics such as : 1) signature of ostream<< (as in what it takes as arguments and what it returns). 2) Fully qualified names (like std::vector or std::operator<<). 3) A more detailed study of Argument Dependent Lookup. – Warga 27/5, 2015 at 3:26

The code is buggy: std::operator<<(std::operator<<(std::cout, s), std::endl); should be std::operator<<(std::cout, s).operator<<(std::endl);, see ideone.com/FFKA7b – Cashmere 6/7, 2015 at 20:4

@WorldSEnder: Yes, you're right. The function which can take std::endl as argument, is actually a member function. Anyway, if I use "\n" instead of std::endl, then my answer is correct. Thanks for the comment. – Warga 16/7, 2015 at 7:4

@Nawaz: I still not understand why std::operator<<(std::operator<<(std::cout, s), std::endl); fails in compilation but If endl is replaced by '\n' then it works? Will you please explain more about it ? – Coacervate 6/6, 2016 at 5:24

@Destructor: Because a function call of the form of f(a,b) invokes a free function. So in case of std::operator<<(std::cout, std::endl);, there is no such free function which takes std::endl as second argument. It is the member function which takes std::endl as argument, and for which you have to write std::cout.operator<<(std::endl);. and since there is a free function which takes char const* as second argument, "\n" works; '\n' would work as well. – Warga 6/6, 2016 at 5:42

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().

Nonchalant answered 13/11, 2011 at 13:32 Comment(0)

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).

Mutton answered 13/11, 2011 at 13:33 Comment(6)

I have always wondered what benefit there is to considering template arguments in the first place. – Firenew 13/11, 2011 at 16:21

Is it fair to say ADL is recommended only for operators and its better to write the namespaces explicitly for other functions? – Flagpole 16/4, 2013 at 14:40

Does it also consider the namespaces of base classes of arguments? (that would be mad if it does, of course). – Stinkhorn 28/6, 2013 at 9:23

how to fix? use std::begin? – Eolande 30/12, 2014 at 20:19

Interesting read on the topic: https://mcmap.net/q/120207/-why-is-adl-not-working-with-boost-range – Louisville 25/5, 2018 at 11:59

This is easy enough for boost to fix -- get rid of boost::begin and replace it with using std::begin in namespace boost. Everything in boost that has been added to std really needs to be removed from namespace boost, leaving behind just a using std::whatever – Musty 2/3, 2023 at 20:58

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++