Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

A Personal Note About Argument-Dependent Lookup

May 03, 2012

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.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

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.

Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video