C++ ADL for Dummies

C++ has a lot of features that seem harmful until you consider why they exist, and ADL is one of them. ADL stands for argument-dependent lookup, which means that the lookup of a name depends on the arguments used when calling it. To illustrate this, let’s look at a simple example:

#include <iostream>
#include <iterator>
#include <vector>

int main(void) {
  std::vector<int> vec{1, 2};
  auto start = vec.begin();
  auto end = vec.end();

  // distance() is not defined, how does this compile!?
  std::cout << distance(start, end);
  // similarly, endl() is not defined here and we didn't use std::!
  endl(std::cout);
}

This code compiles and runs and prints 2 just like you’d expect! How is this possible? We didn’t use std::distance or std::endl, and yet the compiler knew which functions we meant to call. This is what ADL does.

Given a call to an unqualified function a in the form a(...), the compiler can deduce which function named a to call based on the arguments given to it. Here, distance(start, end) is a call to some function distance with types std::vector<int>::iterator. Since these are in the std namespace, the compiler can deduce that std::distance is the function you intended to call, as it’s allowed to look in the std namespace to find the distance function. The same goes for endl. This can have a negative impact on your code. Consider the following: if you had a function called distance in a template function, you might expect it to work with any type passed into it, including std::vector<int>::iterator. However, std::distance may be chosen first. As a result, you would have to fully qualify your call to distance, e.g., with the namespace it’s in, or ::distance if it’s a global function. Since this can mess with your code, why is this allowed? You might immediately think this makes no sense.

Let’s look at a different example. Given the following code:

int operator+(const MyType&, int);

This declaration tells us immediately that there’s an operator overload for + which works on MyType and int. When the compiler encounters some code that says my_thing + 5, where my_thing is an instance of MyType, how does it know what to do with that? This is where ADL comes in.

When you write my_thing + 5, the compiler really interprets that as a call to a function operator+(my_thing, 5). However, you didn’t give it a namespace to find that operator+ in, so how does it know what to call? This is an example of why ADL exists. Based on the types of the arguments and their namespaces, the compiler is able to find our overloaded operator+ and successfully call it.

While this is one reason ADL exists, it is not the only one. ADL also allows for specialization of functions for user-defined types. For example, in many cases, the STL actually calls swap(a, b) instead of std::swap(a, b). Since it uses an unqualified name for swap, this will use ADL to lookup the swap function to use. As a result, you can overload swap for your own types. Many libraries do this, too! For example, fmt uses ADL to find a function called format_to for your type to allow it to format your types. nlohmann::json uses ADL to find your user-defined to_json and from_json functions. This means you don’t have to explicitly tell these libraries which functions to call. Neat, huh?

Example

Let’s look at a complete example of using ADL in your own code. This code may look like it won’t compile, but it actually does!

namespace nature {
template <class Animal>
Animal Breed(Animal&& mother, Animal&& father) {
  // Notice that Reproduce for any particular type is not defined here!
  // (I will forego forwarding here for brevity.)
  return Reproduce(mother, father);
}
}

namespace pets {
struct Cat {};

Cat Reproduce(const Cat& mother, const Cat& father) {
  std::cout << "making a new cat!\n";
  return Cat{};
}
}

int main(void) {
  pets::Cat mother;
  pets::Cat father;
  // This compiles!
  auto child = nature::Breed(mother, father);
}

Here, despite pets::Reproduce(const Cat&, const Cat&) not being declared nor defined within the scope of Breed(), it is still valid to call this function on two cats. This is because of ADL. When the compiler sees that Animal is pets::Cat, it can look in pets to resolve the name Reproduce, since its arguments are from the pets namespace.

Hopefully, you’ve learned something about ADL here. If you are a C++ veteran, I should imagine you were bored to death, and I’d be surprised if you got to this point. However, if you’re a newer C++ user, I hope you found this helpful!