One of the comments on my article last week noted that argument-dependent lookup in C++ is often called "Koenig lookup" — and, indeed, Wikipedia claims (as of May 1, 2012) that I invented it. I didn't invent it, but unfortunately, I don't know who did, so I don't know where the credit — or blame — is really due. 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 Wikipedia article identifies this problem by claiming that the following simple program would not compile were it not for ADL:

 
#include<iostream>

int main()
{
  std::cout << "Hello World, where did operator<<() come from?" << std::endl;
  return 0;
}

This claim is incorrect, although only a trifling change is needed to correct it.

To understand the problem, let's start by thinking about the meaning of the expression a<<b. In general, a<<b can mean either a.operator<< (b) or operator<< (a, b), and the compiler considers both possible meanings when it looks for candidates for an overloaded operator. This duality is necessary only when we are calling an overloaded operator, because if we call a function that is not an operator, the form of the call removes any ambiguity. Either we call a.f(b) or we call f(a, b), and never the twain shall meet.

Now let's consider how a runtime library might have been written before namespaces:

 
      class ostream {
      public:
// …
            ostream& operator<< (int);
ostream& operator<< (const char*);
// …
};
      ostream cout;

The library would define an ostream class and a global object of that class named cout. That class, in turn, would have members to handle output of each of the built-in types. Writing a statement such as

             cout << "Hello World" <<endl;
 

would be equivalent to writing

 
             cout.operator<< ("Hello World").operator<< (endl);

because the nonmember versions of operator<< would not exist, and therefore would not participate in overloading.

Next, let's add a string class:

 
      class string {
            // …
      };
 
      ostream& operator<< (const string&);

Note that operator<< for strings is not a member of class ostream. It can't be, because only programmers who want to use the string library should have to pay for it. If we change our use of operator<< to include a string:

      string hello = "Hello World";
      cout << hello << endl;

the program still works, but it is now treated as

      string hello = "Hello world";
      operator<< (cout, hello).operator<< (endl);

where the first call to operator<< finds the nonmember associated with the string class, and the second finds the member associated with endl.

Now let's introduce namespaces, and put ostream, cout, endl, and string (along with its associated operator<<) into namespace std. The obvious code

      std::cout << "Hello World" << std::endl;

still works, because it is treated as

      std::cout.operator<< ("Hello World").operator<< (std::endl);

Once std::cout has been identified, no additional special treatment is needed in order to find the right operator<<.

In contrast, the string class' users are not so lucky, because

 
      std::cout << hello << std::endl;

will not find the first operator<<. Moreover, it is far from obvious how to tell the compiler to find it. One possibility might be

 
      using std::operator<<;

and another might be

      std::operator<< (std::cout, hello) << std::endl;

but it is hard to explain — especially to a beginning programmer — why this technique is necessary for a string variable, but not for a string literal. Moreover, if we were to change the variable to a literal:

 
      std::operator<< (std::cout, "Hello World") << std::endl;

the code would stop working because we need the member operator<<, not the one in namespace std.

In other words, the standards committee was faced with the situation that introducing namespaces into the standard library would break some very common code examples. Moreover, the obvious ways of fixing those examples would work for some types (such as const char*) but fail for others (such as string) that would seem to be similar. Even worse would be that the ways of fixing the problem that worked would be clumsy and error-prone enough to make them unusable in practice. Not only that, but the committee expected that many implementations would leave the standard-library names in the global namespace as a transition aid, thereby making it harder for developers to find the problems in their code.

As I said at the beginning of the article, I did not solve this problem; someone else did. I don't remember who it was — it was probably part of a discussion on the Usenet comp.lang.c++ newsgroup. What I did do was to come up with these examples, which, in turn, helped convince the standards committee that introducing namespaces caused a problem that had to be solved somehow before the C++ standard was released. Moreover, time was running short, a solution was available, and no one else had any ideas for a better solution.

The rest, as they say, is history.