Argument Dependent Lookup ADL

What It Does What?

Situation: Multiple Namespaces

namespace pixl {
  class point { …
      point(int x, int y); …
  };
  void draw (point const&);
  void print (int);
}

namespace geom {
  class point { …
      point(double x, double y); …
  };
  void draw (point const&);

}

With ADL

Functions are looked up in the namespace(s) of the argument type(s) involved in a call expression:

pixl::point px {640, 480};
geom::point gm {1.1, 2.3};
draw(px);  // ADL ⇒ call pixl::draw
draw(gm);  // ADL ⇒ call geom::draw

Argument px has type pixl::point ⇒ ADL looks for function draw in namespace pixl ⇒ matching function found and called.

Explicit Qualification ⇒ No ADL Without ADL Without ADL

No ADL is performed if a function call is explicitly qualified with a namespace name.

Note that explicit qualification is necessary, if none of the function arguments has an associated namespace (like, e.g., fundamental types: int, double, …).

pixl::draw(px);
geom::draw(gm);

pixl::draw(gm);  //  COMPILER ERROR: expects pixl::point
geom::draw(px);  //  COMPILER ERROR: expects geom::point

// needs qualification
pixl::print(5);
// because 'int' is not in namespace 'pixl'
print(5);        //  COMPILER ERROR: 'print' not found

Standard Library Example Standard Lib Example Example

The following call to std::sort works without namespace qualification:

#include <vector>
#include <algorithm>
std::vector<int> v {1,2,3,4};
sort(begin(v), end(v));  //  compiles!

type of v is std::vector

ADL looks for begin/end in namespace std
std::begin / std::end found and called
return type of begin/end is std::vector::iterator
ADL looks for sort in namespace std
std::sort found and called

Why?

Consistent Member/Non-Member Calls Consistent Function Calls Consistency

`object.fn();`	looks up member function in object's class
`fn(object);`	looks up function in namespace of object's class

Non-member functions mentioning class X (e.g., taking an argument of type X) that are in the same namespace as X are also part of X's interface.

Non-Member Operators! Non-Member Operators! Operators!

Example: Class `point` in 2 Namespaces

want support for expressions like 5 * point{4,1}
need functions operator * (NUMBER, point)
left hand operand not a point ⇒ operator* cannot be member function of point

namespace pixl {
  class point { …
      point(int x, int y); …
  };
  // cannot be member function:
  point operator * (int factor, point const&);
}
namespace geom {
  class point { …
      point(double x, double y); …
  };
  point operator * (double factor, point const&);
}

If there was no ADL

would need explicit qualification with ::
auto p = pixl::operator*(2, px);
clumsy call syntax defeats purpose of operators (readability, infix notation, terseness)

With ADL

Operator functions are selected based on the namespace of their operand type(s):

pixl::point px {640, 480};
geom::point gm {1.1, 2.3};

// px has type pixl::point// ⇒ ADL selects pixl::operator*
auto p = 2 * px;  

// gm has type geom::point// ⇒ ADL selects geom::operator*
auto x = 2 * gm;

When and Where? Where?

General Rules

ADL is used to look up name `f`, if …

f is part of a function call expression, like e.g., f(arg)
f is the name of a function
f is called with at least one argument

ADL is not used to look up name `f`, if …

the call to f is qualified, e.g., ns::f(arg)
the name f itself is contained in an expression like, e.g., (f)(arg)
there is already a class member named f in the lookup candidate set
there is already a block-scope declaration of function f in the lookup candidate set (types declared with using are ignored)
there is already a declaration of any other (variable/object, …) f that is not a function or function template in the lookup candidate set

ADL is exclusively used for looking up …

non-member functions begin and end taking range in

for(auto const& x : range) { … }

if member-begin or member-end could not be found in range's class
non-member function get needed by structured bindings
names that depend on a template parameter (when a template is instantiated)

When Calling Functions Function Calls

namespace ns {
  class C { … };
  void f (C);
}
…
ns::C x;

expression	compiles?	explanation
`f(x);`		`f` is a function name and `x` has class type ⇒ ADL finds `f`
`ns::f(x);`		call explicitly qualified with `ns::` ⇒ no ADL
`(f)(x);`		`(f)` is not a simple function name, but an expression ⇒ no ADL ⇒ function not found
`using ns::f; (f)(x);`		no ADL, but `f` was explicitly made visible for regular name lookup

When Calling Function Templates Calling Function Templates Template Calls

namespace ns {
  class C { … };
  template<class T> g(T);
  template<int i> h(C);
}
…
ns::C x;

expression	compiles?	explanation
`g(x);`		ADL finds `ns::g`
`ns::g(x);`		qualification with `ns::` ⇒ no ADL
`g<ns::C>(x);`		`g<ns::C>` is not a simple function name ⇒ no ADL ⇒ function template not found
`ns::h<0>(x);`		qualification with `ns::` ⇒ no ADL
`h<0>(x);`		`h<0>` is not a simple function name ⇒ no ADL ⇒ function template not found
`using ns::h; h<0>(x);`		function template `ns::h` was explicitly made visible for regular name lookup

When Calling Lambdas ⇒ No ADL Calling Lambdas ⇒ No ADL Not For Lambdas

namespace ns {
  class C { … };
  auto lm = [](C a) { … };  // lambda
}
…
C x;

expression	compiles?	explanation
`lm(x);`		`lm` is not a function, but a compiler-generated function object ⇒ no ADL ⇒ `lm` not found
`using ns::lm; lm(x);`		no ADL but object `lm` was explicitly made visible for regular name lookup

How Does It Work? How?

ADL examines the type of each argument in a function call expression f(arg1, arg2, …) (in no particular order) and determines the set of associated namespaces and classes which will also be searched for a function (or function template) named f.

No Associated Namespace For… No Assoc. Namespace For… ADL ignores

fundamental types (int, double, …)
aliases introduced by using directives (B)

namespace na {
  class A { … };
  void f(int);
  void g(A);
}

namespace nb {
  using B = na::A;
  void h(B);

}

Call	ADL Examins	Found
`f(0);`	NO ADL (int doesn't have namespace)	NOTHING
`na::f(0);`	explicit qualification ⇒ NO ADL	`na::f`
`nb::B b; h(b);`	`(nb::B ≡ na::A) ⇒ A, na`	NOTHING
`nb::B b; g(b);`	`(nb::B ≡ na::A) ⇒ A, na`	`na::g`

Inline Namespaces

ADL looks in:

enclosing namespace of inline namespace
inline namespaces of all previously found namespaces

namespace lib {
  class A { … };

  inline namespace v2 {
    class B { … };
    void f(A const&);
  }
  namespace v1 {
    class B { … };
    void f(A const&);
  }

  void g(B const&);  // B refers to v2::B
}

Call	ADL Examins	Found
`lib::A a; f(a);`	`lib → lib::v2`	`lib::v2::f(lib::A);`
`lib::A a; lib::v2::f(a);`	explicit qualification ⇒ NO ADL	`lib::v2::f(lib::A);`
`lib::A a; lib::v1::f(a);`	explicit qualification ⇒ NO ADL	`lib::v1::f(lib::A);`
`lib::B b; g(b);`	`lib::v2 → lib`	`lib::g(lib::v2::B);`
`lib::v1::B b1; g(b1);`	`lib::v1 → lib`	NOTHING no such function `g(lib::v1::B)`

Classes `class C` `class Args`

ADL looks in:

C itself
base classes: direct (B) + indirect (A)
any class of which C is a member (X)
innermost enclosing namespaces of all classes in the set (na, nb, nx)

Only ADL can find:

hidden friends like nx::f(nx::X::C)

namespace na {
  class A { … };
  void f(A);
}
namespace nb {
  class B : public na::A { … };
}

namespace nx {
  class X { public: …
      class C : public nb::B { … };
      friend void f(C);
  };
  void f(X);
}

Call	ADL Examins	Found
`na::A a; f(a);`	`A, na`	`na::f(na::A)`
`nb::B b; f(b);`	`B, A, nb, na`	`// B → A na::f(na::A)`
`nx::X x; f(x);`	`X, nx`	`nx::f(nx::X)`
`nx::X::C c; f(c);`	`C, X, B, A, nx, nb, na`	`// friend of X nx::f(nx::X::C)`
`nx::X::C c; nx::f(c);`	explicit qualification ⇒ NO ADL	NOTHING `nx::f(nx::X::C)` only visible to ADL!

Enumerations `enum (class) E` Enumeration Args

ADL looks in:

enclosing namespace of E
enclosing class of E

Only ADL can find:

hidden friends like ns::f(ns::C::E)

namespace ns {
  class C { public: …
    enum class E { x, y, z };
    friend void f(E);
  };
  void f(int, C::E);
}

Call	ADL Examins	Found
`f(0,C::E::x);`	`C, ns`	`ns::f(int, ns::C::E);`
`f(C::E::x);`	`C, ns`	`// friend of C ns::f(ns::C::E);`

Pointers/Addresses Pointer Args

Raw Pointer (`T`) `T`

ADL examins associated namespaces and classes of T

namespace ns {
  class T { … };
  void g(T*);
}

Call	ADL Examins	Found
`ns::T x; g(&x);`	`T, ns`	`ns::g(ns::T*)`

Pointer To Class Data Member `C::*`

ADL examins all associated namespaces and classes of the member type (A) and the containing class (C)

// forward declaration of C
namespace nc { class C; } 
namespace na {
  class A { … };
  // pointer &darr; to C member
  void f( A nc::C::* );
}

namespace nc {
  class C { public: …
    na::A x, y, z;
  };
  // pointer &darr; to C member
  void g( na::A C::* );
}

Call	ADL Examins	Found
`na::A nc::C::* p = &nc::C::x; f(p);`	`A, na, C, nc`	`na::f`
`na::A nc::C::* p = &nc::C::x; g(p);`	`A, na, C, nc`	`nc::g`

Function Pointer `Y(*)(X)`

ADL examins associated namespaces and classes of all parameter types and the return type

namespace na {  
  class A { }; 
  void f( void(*)(A) ) {}
}

void g(na::A);

Call	ADL Examins	Found
`void(*p)(na::A) = g; f(p);`	`A, na`	`na::f`

Pointer To Class Member Function `Y(C::*)(X)`

ADL examins associated namespaces and classes of all parameter types, the return type and the containing class type

namespace na {
  class A { … };
}
namespace nc {
  class C { public: …
    void set(na::A);
  };
  void f( void(nc::C::*)(na::A) );
}

Call	ADL Examins	Found
`f( &nc::C::set );`	`C, nc, A, na`	`nc::f`

Address Of Overloaded Function `&(Y(*)(X){)`}

ADL examins every function or function template in the set of overloads (here both f functions)

namespace na {
  class A { … };
  // set of overloads
  void f(A);
  void f(A, int);

  void g( void(*)(A) );
}

Call	ADL Examins	Found
`g( &na::f );`	`A, na`	`na::g`

Class Template Specializations Template Spec. Args

ADL looks in:

template type itself (X) and its associated namespaces (nx)
types of all type template arguments (A1)
template template arguments (e.g., P2=A2): classes in which they are members
template template arguments (e.g., P2=A2): enclosing namespaces (n2)

ADL skips arguments for:

non-type template parameters (int P3)
template template parameters (e.g., P2=A2: ADL skips A2 itself)

namespace nx {
  template<class P1,            template<class> class P2,            int P3> 
  class X {…};
}
namespace n1 { class A1; }
// specializations of X used as parameter:
namespace n2 {
  template<class> 
  class A2 { public: …
    friend void h( X<n1::A1,A2,5> const& );
  };
  void g( X<n1::A1,A2,5> const& );
}
namespace nx {
  void f( X<n1::A1,n2::A2,5> const& );
}
// instantiation:
nx::X< n1::A1, n2::A2, 5> spx {};

Call	ADL Examins	Found
`f(spx);`	`X, nx, A1, n1, n2`	`nx::f`
`g(spx);`	`X, nx, A1, n1, n2`	`n2::g`
`h(spx);`	`X, nx, A1, n1, n2`	`NOTHING`

ADL-Related Idioms Idioms Idioms

2-Step: ADL + Fallback ADL+Fallback

template<class T>
void generic_function (…) {
    T x;
    T y;
    …
    using std::swap;
    swap(x, y);
    …
}

This makes `swap` a customization point:

if custom swap(T&,T&) declared in T's namespace
⇒ visible to ADL ⇒ custom swap will be used
if no special overload for T exists
⇒ std::swap will be used as fallback (made visible with using directive)

If you want to suppress ADL and make sure that std::swap is always used, namespace-qualify the function call: std::swap(x,y).

Use the fallback idiom only in generic (template) code and only if a common fallback implementation, like e.g. std::swap exists.

C++20 If you want to enforce constraints on the arguments through concepts you should use a customization point object to make sure that the constraints can't be bypassed by custom functions.

Arthur O'Dwyer's blog post about this idiom

Hidden Friends

namespace math {
  class ratio { …
  public:
    explicit
    ratio(int64_t numerator,           int64_t denominator=1);
    …
    friend ratio operator + (ratio a, ratio b)     { … }
  };
}

Only ADL can find `math::operator+(ratio,ratio)`

declaring it friend of ratio makes it a member of namespace math
it was not directly declared in namespace scope
it was not directly defined (=implemented) in namespace scope

// ADL finds math::operator+(ratio,ratio)
math::ratio x {2,3}, y {1,6};
math::ratio z = x + y;  
// qualified call ⇒ No ADL ⇒ operator+ not found!
math::ratio x {2,3}, y {1,6};
math::ratio w = math::operator+(x,y);  //  COMPILER ERROR

Hidden friends are not callable through implicit conversions!

class B { };

class A { public:
  A() {}
  A(B) {}    // implicit
  A(int) {}  // implicit

  friend void foo(A)   { } 
  friend void foo(B)   { } 
  friend void foo(int) { } 
};

void bar(A) { }

A a1{ };      // 
A a2{ B{} };  // 
A a3{ 47 };   // 
bar( A{} );  // 
// implicit conversions:
bar( B{} );  //  bar( A{B{}} )
bar( 123 );  //  bar( A{123} )
// hidden friend 'foo':
foo( A{} );  // 
// can't find foo(B) & foo(int),
// no implicit conversions to 'A'
foo( B{} );  //  
foo( 123 );  //

Example: No Constructor Conversions! Example 1

namespace math {
  class tiny_ratio {
    // no operator+! (on purpose)
    …
  };
  class ratio { 
    …
  public:
    explicit
    ratio(int64_t numerator,           int64_t denominator=1);
    // implicit conversion from tiny_ratio:
    ratio(tiny_ratio r);
    …
    friend ratio operator + (ratio a, ratio b)     { … }
  };
}
// No implicit conversions possible:
math::tiny_ratio r{1,2}, s{1,4};
auto t = r + s;   //  COMPILER ERROR ⇒ good!

The hidden friend version of operator+(ratio,ratio) can only be found by ADL, so only if a ratio argument is involved in the call.

Since we can implicitly construct a ratio from a tiny_ratio any non-hidden function taking ratio as input (by value or non-const reference) could also be called with tiny_ratio objects.

So, if operator+(ratio,ratio) had been declared in namespace scope instead of as hidden friend, we could use it to add tiny_ratio objects despite the fact that we explicitly did not want that!

Example: No Operator Conversions! Example 2

Hidden friends also protect against conversion operators that implicitly convert other types to ratio!

namespace math {
  class ratio { 
    …
  public: 
    friend ratio operator + (ratio a, ratio b)     { … }
    …
  };
  class my_num {
    …
  public: 
    …
    // conversion operator that can
    // create a 'ratio' from a 'my_num'
    operator ratio() const     { return ratio{…}; }
    // forgot operator + for my_num!
  };
}
math::my_num u = 23;
math::my_num v = 47;
auto w = u + v ;  //  COMPILER ERROR: operator+ not found

The hidden friend version of operator+(ratio,ratio) can only be found by ADL, so only if a ratio argument is involved in the call.

Since my_num::operator ratio() can convert any my_num into a ratio, any non-hidden function taking ratio as input (by value or non-const reference) can also be called with my_num objects.

So, if operator+(ratio,ratio) had been declared in namespace scope instead of as hidden friend, the last line would have compiled and yielded a math::ratio w!

Disabling ADL with Niebloids Disabling ADL: Niebloids Niebloids

Goal: prevent ADL from picking up custom overloads of a generic library function

Idea: Use Function Object

namespace lib {
  namespace detail {
    struct foo_fn {
      template<class T>
      void operator() (T const& x) const { … }
    };
  }
  // global function object lib::foo
  inline constexpr const detail::foo_fn foo {};
  // note: inline variable requires C++17
}

⇒ Consistent Behavior!

namespace na {
  class A { … };
}
namespace nb {
  class B { … };
  // custom foo
  void foo(B const& b) {…}
}
na::A a;
nb::B b;
// with explicit qualification:
lib::foo(a);  // lib::foo → lib::detail::foo
lib::foo(b);  // lib::foo → lib::detail::foo
// same with using statement:
using lib::foo;
foo(a);      // lib::foo → lib::detail::foo
foo(b);      // lib::foo → lib::detail::foo

qualified and unqualified calls have the same effect
users cannot override library function's behavior

C++20's standard library makes use of such function objects, that are also known as Niebloids (named after Eric Niebler).

Customization Point Objects Customization Objects CPOs
C++20

Goal: consistent concept checking on (potential) customization points of a generic library!

The traditional 2-Step ADL & Fallback Idiom:

using std::swap; // fallback

swap(x,y); // ADL may find custom swap

cannot guarantee that a custom implementation of swap constrains its parameters the same way as the fallback implementation std::swap.

Idea: Function Object as Single Entry Point Idea: Single-Entry Function Object

All objects passed to any 'foo' implementation should satisfy concept 'Fooable':

namespace lib {
  template<class T>   concept Fooable = requires (T x) { 
    {x.size()} -> std::integral; };

  namespace detail {
    inline namespace defaults {
      template<Fooable T>  // constrained!
      void foo(T const& x) { … }
    }
    struct foo_fn {
      template<Fooable T>  // constrained!
      void operator() (T const& x) const {
        // calls custom foo found by ADL
        // or fallback defaults::foo
        foo(x);
      }
    };
  }
  namespace defaults = detail::defaults;
  // global function object lib::foo
  inline constexpr const detail::foo_fn foo {};
}

Make sure that your default implementation (here lib::defaults::foo) is not unconstrained or underconstrained! Otherwise it might act as catch-all and custom functions (found by ADL) won't be selected! Functions with forwarding reference parameters and/or variadic parameter packs are especially prone to being catch-alls.

⇒ Consistent Behavior

namespace na {
  class A { public: size_t size() const; };
}
namespace nb {
  class B { public: int size() const; };
  void foo(B const& b);
}
na::A a;
nb::B b;
using lib::foo;
foo(a);      // lib::foo → fallback lib::defaults::foo
foo(b);      // lib::foo → custom   nb::foo
// explicit qualification has no effect:
lib::foo(a);  // lib::foo → fallback lib::defaults::foo
lib::foo(b);  // lib::foo → custom   nb::foo
// force default implementation:
lib::defaults::foo(a);
lib::defaults::foo(b);

all calls are constrained with Fooable because they all invoke lib::detail::foo_fn::operator()
always does the same thing; no need for ADL+Fallback (ADL 2-step)
might be surprising that forcing default implementation is not possible with explicit qualification (because lib::foo is an object)

⇒ Cannot Bypass Constraints!

namespace lib {
  template<class T>   concept Fooable = requires (T x) { 
    {x.size()} -> std::integral; };
  …
}

Calls to lib::foo will never pick up unconstrained custom foo overloads:

namespace nc {
  class C {   };  // no member 'size()'
  void foo(C const&);
}
nc::C c;
lib::foo(c);  COMPILER ERROR: C doesn't satisfy 'lib::Fooable'
using lib::foo;
foo(c);       COMPILER ERROR: C doesn't satisfy 'lib::Fooable'

class D { public: 
  // non-integral return type:
  double size() const { … } 
  friend void foo(D const&) { … }
};
D d;
lib::foo(d);  COMPILER ERROR: D doesn't satisfy 'lib::Fooable'
using lib::foo;
foo(d);       COMPILER ERROR: D doesn't satisfy 'lib::Fooable'

Related …

Last updated: 2021-02-28

What It Does What?

Situation: Multiple Namespaces

With ADL

Explicit Qualification ⇒ No ADL Without ADL Without ADL

Standard Library Example Standard Lib Example Example

Why?

Consistent Member/Non-Member Calls Consistent Function Calls Consistency

Non-Member Operators! Non-Member Operators! Operators!

Example: Class point in 2 Namespaces

If there was no ADL

With ADL

When and Where? Where?

General Rules

ADL is used to look up name f, if …

ADL is not used to look up name f, if …

ADL is exclusively used for looking up …

When Calling Functions Function Calls

When Calling Function Templates Calling Function Templates Template Calls

When Calling Lambdas ⇒ No ADL Calling Lambdas ⇒ No ADL Not For Lambdas

How Does It Work? How?

No Associated Namespace For… No Assoc. Namespace For… ADL ignores

Inline Namespaces

ADL looks in:

Classes class C class Args

ADL looks in:

Only ADL can find:

Enumerations enum (class) E Enumeration Args

ADL looks in:

Only ADL can find:

Pointers/Addresses Pointer Args

Raw Pointer (T*) T*

Pointer To Class Data Member C::*

Function Pointer Y(*)(X)

Pointer To Class Member Function Y(C::*)(X)

Address Of Overloaded Function &(Y(*)(X){)}

Class Template Specializations Template Spec. Args

ADL looks in:

ADL skips arguments for:

ADL-Related Idioms Idioms Idioms

2-Step: ADL + Fallback ADL+Fallback

This makes swap a customization point:

Hidden Friends

Only ADL can find math::operator+(ratio,ratio)

Hidden friends are not callable through implicit conversions!

Example: No Constructor Conversions! Example 1

Example: No Operator Conversions! Example 2

Disabling ADL with Niebloids Disabling ADL: Niebloids Niebloids

Goal: prevent ADL from picking up custom overloads of a generic library function

Idea: Use Function Object

⇒ Consistent Behavior!

Customization Point Objects Customization Objects CPOs C++20

Goal: consistent concept checking on (potential) customization points of a generic library!

Idea: Function Object as Single Entry Point Idea: Single-Entry Function Object

⇒ Consistent Behavior

⇒ Cannot Bypass Constraints!

Related …

Comments

Example: Class `point` in 2 Namespaces

ADL is used to look up name `f`, if …

ADL is not used to look up name `f`, if …

Classes `class C` `class Args`

Enumerations `enum (class) E` Enumeration Args

Raw Pointer (`T`) `T`

Pointer To Class Data Member `C::*`

Function Pointer `Y(*)(X)`

Pointer To Class Member Function `Y(C::*)(X)`

Address Of Overloaded Function `&(Y(*)(X){)`}

This makes `swap` a customization point:

Only ADL can find `math::operator+(ratio,ratio)`

Customization Point Objects Customization Objects CPOs
C++20