What Are the Pitfalls of Adl

What are the pitfalls of ADL?

There is a huge problem with argument-dependent lookup. Consider, for example, the following utility:

#include <iostream>

namespace utility
{
    template <typename T>
    void print(T x)
    {
        std::cout << x << std::endl;
    }

    template <typename T>
    void print_n(T x, unsigned n)
    {
        for (unsigned i = 0; i < n; ++i)
            print(x);
    }
}

It's simple enough, right? We can call print_n() and pass it any object and it will call print to print the object n times.

Actually, it turns out that if we only look at this code, we have absolutely no idea what function will be called by print_n. It might be the print function template given here, but it might not be. Why? Argument-dependent lookup.

As an example, let's say you have written a class to represent a unicorn. For some reason, you've also defined a function named print (what a coincidence!) that just causes the program to crash by writing to a dereferenced null pointer (who knows why you did this; that's not important):

namespace my_stuff
{
    struct unicorn { /* unicorn stuff goes here */ };

    std::ostream& operator<<(std::ostream& os, unicorn x) { return os; }

    // Don't ever call this!  It just crashes!  I don't know why I wrote it!
    void print(unicorn) { *(int*)0 = 42; }
}

Next, you write a little program that creates a unicorn and prints it four times:

int main()
{
    my_stuff::unicorn x;
    utility::print_n(x, 4);
}

You compile this program, run it, and... it crashes. "What?! No way," you say: "I just called print_n, which calls the print function to print the unicorn four times!" Yes, that's true, but it hasn't called the print function you expected it to call. It's called my_stuff::print.

Why is my_stuff::print selected? During name lookup, the compiler sees that the argument to the call to print is of type unicorn, which is a class type that is declared in the namespace my_stuff.

Because of argument-dependent lookup, the compiler includes this namespace in its search for candidate functions named print. It finds my_stuff::print, which is then selected as the best viable candidate during overload resolution: no conversion is required to call either of the candidate print functions and nontemplate functions are preferred to function templates, so the nontemplate function my_stuff::print is the best match.

(If you don't believe this, you can compile the code in this question as-is and see ADL in action.)

Yes, argument-dependent lookup is an important feature of C++. It is essentially required to achieve the desired behavior of some language features like overloaded operators (consider the streams library). That said, it's also very, very flawed and can lead to really ugly problems. There have been several proposals to fix argument-dependent lookup, but none of them have been accepted by the C++ standards committee.

ADL without templates

I can't show you something leading to a pitfall, but I can demonstrate ADL working without templates:

namespace foo {
   struct T {} lol;
   void f(T) {}
}

int main() {
   f(foo::lol);
}

Note that lol's type has to be a class-type; I originally tried with a built-in, as you saw, and it didn't work.

ADL not working outside (even of structure)

ADL doesn't find members. It finds free functions.

You have a member foo.begin(), not a free function begin(foo).

friend constexpr auto begin(Array10&)
{
    return std::begin(m_array); // #1
}
friend constexpr auto begin(Array10 const&)
{
    return std::begin(m_array); // #1
}

those are non-member begin functions that will be found via ADL.

ADL versus scope-resolution -- which to prefer?

That is not ADL. In both of your examples, foo is found via normal lookup. An example using ADL would be as follows:

namespace ns {
    class A { };
    void f(A) { };
}

int main() {
    f(A());
}

Here, f is not found via normal lookup, but it is found via argument-dependent lookup (because it is in namespace ns alongside A). In any case...

Avoid ADL wherever possible.

ADL is beneficial in certain, specific scenarios, for example for operator overloading and for the swappable concept. However, it should be used sparingly, as it leads to bizarre, unexpected behavior in many other cases.

Are there any pitfalls in using move() instead of std::move()?

ADL will only find things in std if the argument types are also in std.

If there is another symbol called move in another namespace that is being used, then the compiler won't know which you meant. There may not be one now, but future changes may bring one in.

Additionally, always having the std:: makes it a lot easier for people reading your code later. It makes it clear that it's not a move that you've defined yourself or included from another library. Especially useful if they've not heard of the (relatively new) std::move before.

Argument-dependent lookup and function templates

Argument-dependent lookup works for unqualified function call expressions. This is true for "normal" functions just as well as for function template specializations.

However, when you provide explicit template parameter for a template function, then the expression does not syntactically look like an function call:

foo<3>(x)  //   "foo less than three?"

That's why those cases don't trigger ADL. However, once a name is known to be a template, ADL does apply!

template <int> void foo();

foo<double, 5, T>(x);   // uses ADL

Why does boost recommend using core functions over member functions?

It's not boost per se, but modern C++ API design.

• By not requiring member functions, you can adapt your own classes and even third party library types to work with the boost Api of your choice. (This way you can e.g. make types from a third party library serializable to a Boost Serialization archive).

• Also, by making the functions free functions, there is an improved decoupling of dependencies. E.g.: fusion/tuple.hpp doesn't need to depend on anything IO related, because the streaming operations are free functions, and hence can be declared (and defined) in a separate header: fusion/tuple_io.hpp.

• It also helps encapsulation because by default the free functions aren't friends of the host class (and as such are unable to access private members).

• free functions can "Do The Right Thing" based on ADL:

  using std::swap;
  swap(a, b); // will lookup `swap` in the namespaces that declare the parameter types
  

  (several other namespaces are also used for lookup)

• Finally, free functions can generically service a group of types, that need not be OO-related (inheritance related). In this way, free functions encourage avoiding duplication of code.

Edit Addressing the question of why you should prefer the non-member syntax, if both exist:

• it works for types that don't have the member function
• it doesn't require .template disambiguation in template code (as pointed out by @Simple)

• Again: it's not boost specific.

  • c++03 has had std::swap() as a free function
  • c++11 introduces std::begin() and std::end() as free functions
  • std::hash<>, std::less<>, std::greater<>, std::equal_to<> similarly provide customization points that are not intrusive (but aren't functions of course)

C++ - How to enable ADL with advance() on iterators in custom templated data container?

Although both the posted answers are correct (and I have upvoted both) I thought I would cover this in a little more depth, for anyone who finds this in future.

'Friend' meanings

For starters, 'friend' has a different meaning on functions within a class. If it is simply a function declaration, then it declares the given function a friend of the class and allows access to it's private/protected members. If however it is a function implementation, it means the function is (a) a friend of the class, (b) not a member of the class and (c) not accessible from within any enclosing namespace. ie. it becomes a global function which is only accessible via argument-dependent lookup (ADL).

Take the following test code for example:

#include <iostream>
#include <iterator>

namespace nsp
{

template <class element_type, class element_allocator_type = std::allocator<element_type> >
class test_container
{
private:
    element_type numbers[50];
    friend class iterator;

public:
    class iterator : public std::iterator<std::bidirectional_iterator_tag, element_type>
    {
    private: 
        element_type *i;

        template <class distance_type>
        friend void advance(iterator &it, distance_type n);

        friend typename std::iterator_traits<iterator>::difference_type distance(const iterator &first, const iterator &last)
        {
            return last.i - first.i;
        }


    public: 

        iterator(element_type &_i)
        {
            i = &(_i);
        }

        element_type & operator *()
        {
            return *i;
        }

        element_type & operator = (const iterator source)
        {
            i = source.i;
            return *this;
        }

        bool operator != (const iterator rh)
        {
            return i != rh.i;
        }

        iterator & operator ++()
        {
            ++i;
            return *this;
        }

        iterator & operator --()
        {
            --i;
            return *this;
        }
    };


    iterator begin()
    {
        return iterator(numbers[0]);
    }


    iterator end()
    {
        return iterator(numbers[50]);
    }


    template <class distance_type>
    friend void advance(iterator &it, distance_type n)
    {
        it.i += 2 * n;
    }

};


}


int main(int argc, char **argv)
{
    nsp::test_container<int> stuff;

    int counter = 0;

    for (nsp::test_container<int>::iterator it = stuff.begin(); it != stuff.end(); ++it)
    {
        *it = counter++;
    }

    nsp::test_container<int>::iterator it = stuff.begin(), it2 = stuff.begin();

    using namespace std;

    cout << *it << endl;

    ++it;

    cout << *it << endl;

    advance(it, 2);

    cout << *it << endl;

    std::advance(it, 2);

    cout << *it << endl;

    int distance_between = distance(it2, it);

    cout << distance_between << endl;

    cin.get();

    return 0;
}

If, from within main(), advance() is called, ADL will function and the custom advance for the class iterator will be called. However, if nsp::advance(), nsp::test_container<int>::advance() or stuff.advance() are tried, these will result in compile errors ("no matching function call").

Template issues

While it is true that non-template function overloads will be called in preference of template function overloads, this is irrelevant for ADL usage. Regardless of whether the function is template or non-template, the correct overload for the specific type will be called. In addition, advance() specifically requires a template parameter of the distance type (int, long int, long long int etc), it is not possible to skip this because we don't know what type the compiler is going to infer from, say "1000000", and we don't know what kind of types the programmer might throw at advance(). Luckily we don't need to worry about partial specialization, as std::advance() is in a different namespace to our custom advance, and can simply implement our own advance() with our hardcoded iterator type, as the example above shows.

This still works if our iterator itself is a template and takes parameters - we simply include the parameters in the advance template and hardcode the template'd iterator type that way. eg.:

template <class element_type, class distance_type>
friend void advance(iterator<element_type>, distance_type distance);

More template issues (a side note)

While this doesn't relate specifically to the implementation of advance() it relates to the implementation of class friend functions in general. You will notice in the example above I implemented the non-template function distance() directly inside the iterator class, while the advance() template'd function is declared as a friend outside the iterator class but within the test_container class. This is to illustrate a point.

You cannot have a non-template friend function implemented outside the class it is friends with, if the class is a template (or part of a template) as your compiler will throw an error. However the template'd function advance() can be declared outside the class with only the definition included in the friend class. The advance() function can also be implemented directed within the friend class, I just chose not to in order to illustrate this point.

Template friend function parameter shadowing

This is not relevant to the above example but can be a pitfall for programmers stepping into template friend functions. If you have a template class, and a friend function which operates upon that class, obviously you are going to need to specify the template parameters in the function definition as well as the class. For example:

template <class element_type, class element_allocator_type = std::allocator<element_type> >
class test_container
{
private:
    element_type numbers[50];

public:
    template <class element_type, class element_allocator_type>
    friend void do_stuff(test_container<element_type, element_allocator_type> &container)
    {
        numbers[1] = 5; // or whatever
    }

};

However the above will not work because the compiler considers your using the same names for 'element_type' and 'element_allocator_type' to be a redefinition of the template parameters first used in the definition of test_container, and will throw an error. Therefore you must use different names for these. ie. this works:

template <class element_type, class element_allocator_type = std::allocator<element_type> >
class test_container
{
private:
    element_type numbers[50];

public:
    template <class c_element_type, class c_element_allocator_type>
    friend void do_stuff(test_container<c_element_type, c_element_allocator_type> &container)
    {
        numbers[1] = 5; // or whatever
    }

};

That's all-
I hope anybody stumbling across this gets some use out of it - most of this information is spread out across stackoverflow in some way, shape or form, but bringing it together is important for the novice.

[UPDATE:] Even with all of the above, it still may not be enough to correctly resolve the ADL to the correct function, despite it being 'correct'. This is because clang, microsoft visual studio 2010-2013, possibly others, have difficulties resolving ADL in complex templates and may crash or throw errors regardless. In this case, you would be wise to simply resort to standard container functions which are friended by the iterator classes.

make_pair namespace pollution

That's a less-known feature of C++, as @jrok pointed out blazingly fast, Koenig Lookup, or in modern C++ ¹⁾, ADL (Argument-Dependent Lookup). What it does is basically searches in the namespaces of the arguments for the function that you want to call (make_pair in this example). The argument triggering the ADL is obviously std::pair.

¹⁾_{the naming has been changed, though a lot of people know the first term}

---

Perhaps it's worth mentioning that ADL is quite important for one particular type of function: operators. If not for ADL, it would be impossible for even the trivial C++ "hello, world!" to work, because this:

std::cout << "Hello, world!";

Would have to be written as this:

std::operator<< (std::cout, "Hello, world!");

Thanks to ADL, << is properly resolved to be in std namespace.

---

References:

• Wikipedia Article
• Great video by Stephan T. Lavavej, Core C++ Part 1
• A broader look on ADL and its uses by Herb Sutter
• It can be found in The C++ Standard (I was using n3485 version) in § 3.4.2

---

Related Topics