Koenig Lookup - a C++ primer

Introduction

With the release of Everett looming, it's probably timely for some articles to be written on some of the 'new' features that are finally making it into Microsoft's C++ compiler. By new, I of course mean the things that every compiler since CFront has had, barring Visual C++. Nevertheless, they say it's better late than never, and so at last we are to have full Koenig lookup. So what is it ?

The standard

Let's start with what the standard says, always a good place to start.

When an unqualified name is used as the postfix-expression in a function call, other namespaces not considered during the usual unqualified lookup may be searched, and namespace-scope friend function declarations not otherwise visible may be found. These modifications to the search depend on the types of the arguments...

So what does this mean ? It means that if I call a function, and pass in a parameter that lives in a namespace, that namespace becomes a valid place for the compiler to look for that function. Why do we have such a rule ? Let's consider how it's likely to be used.

What is an interface ?

The most common assumption is that an interface is the list of methods which are exposed by an object, those found in its header file. However, this is not all there is to it. If I have a class called Bar(), and I want to insert it into an ostream, I would write a method that looks like this:

template<class charT, class Traits>
std::basic_ostream<charT, Traits> &
operator << (std::basic_ostream<charT, Traits> & os, const Bar & b)
{
    // Stream some meaningful data from the object into the stream 'os' here.

    return os;
}

Is this a method on the public interface of the Bar class ? No. Is it part of the interface that Bar offers ? Most certainly. Without Bar, it is of no use to anyone, it wouldn't even compile without it. I'd like you to keep this example in mind as I show you an example of Koenig lookup, taken direct from the C++ standard.

namespace NS
{
    class T { };
    void f(T){};
}

NS::T parm;

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

In this example, a namespace is created, which contains a class and a function. Replace NS with std, and f with the inserter above and you'll see how it could exist in real life. Now we create an instance of NS::T, and then in our main function, we call the f method. What Koening lookup says is this:

When a function is called, in order to determine if that function is visible in the current scope, the namespaces in which the functions parameters reside must be taken into account.

So even though f is in theory hidden ( add a function called f in the namespace that takes an int, and if you try to call it from main, it will fail to compile), Koenig lookup says the function is visible because you have an instance of an object which exists in that namespace, and which is a parameter to the function.

So how did the old compiler versions work ?

If we need Koenig lookup to write stream operators, etc., then how did it work in the past ? I'm not sure of the implimentation details, but the net result was that Koenig lookup only worked for operators, while straight functions, like the one in our example, did not work. Which in theory covered about 90% of the ways most people would use Koenig lookup, but also allowed you to write code which VC6/7 would compile, but a conforming C++ compiler would not. For example:

namespace NS
{
    class T { };
    void f(T){};
}

NS::T parm;

void f(T){};

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

This should not compile, because the call to f() is ambiguous. Under VC.NET and VC6 it compiles fine, because Koenig lookup fails.

More broken code

Here is an example of code that equally fails to compile in all compilers, just to keep the playing ground level:

namespace NS1
{
   class T1 {/*...*/};
}
namespace NS2
{
   class T2 {/*...*/};
   void f(NS1::T1, T2) {/*...*/};
}

namespace NS1
{
   void f(T1, NS2::T2) {/*...*/};
}

NS1::T1 t1;
NS2::T2 t2;

int main()
{
    f(t1,t2);
}

Thanks to whoever brought this up in the questions ( can't see them right now ). An earlier VC version simply cannot see ANY function named f. Add one to the global namespace, and it would call that. Everett, and every other compiler I know of, will complain that there are two functions visible with the same prototype. Passing int1 makes the function in NS1 visible to the global namespace, and passing in T2 makes the function in NS2 visible. Koenig lookup is being applied twice here.

To reiterate

I have had quite a few complaints with regard to this article, so I apologise if I am hammering the one simple point over and over, I don't get paid by the word, I just want everyone to 'get it'. Here is the standard example fleshed out to include a real class, and a real operator.

#include <iostream>


using std::cout;
using std::cin;

namespace NS
{
    struct Date
    {
        int m_nYear,  m_nMonth, m_nDay;
        
        Date::Date() : m_nYear(1969), m_nMonth(2), m_nDay(17) // My birthday

        {
        }
    };

    template<class charT, class Traits>
        std::basic_ostream<charT, Traits> &
        operator << (std::basic_ostream<charT, Traits> & os, const Date & d)
    {
        os << d.m_nDay << "-" << d.m_nMonth << "-" << d.m_nYear;
        return os;
    }
}

int main()
{
    NS::Date d;
    cout << d << " is my birthday, so buy me lots of loot";

    int i;
    cin >> i;
}

This code defines a struct for holding a date, for simplicity the members are public. The iostream inserter is badly written, also for simplicity. Read my article if you want to know how to write good ones. The thing with this example is that if I ask 'how does the compiler know how to call the inserter', the answer seems obvious, it has to. It's part of the interface. Yes, but it's also a function that is not part of the class, and is hidden in a namespace. By now I hope you know that the reason the operator is visible is Koenig lookup. This example would probably compile on VC6 and 7 ( I cannot test it ), because as I said before, operators have always worked. However, the change is that now all code, including the example we pulled from the standard, will use Koenig lookup to decide which namespaces to search to find a function to call.

Conclusion

To be honest, I'd regard examples like the one in the standard with caution. I can't think of a real world use for Koenig lookup outside of the sort of thing that compiled on previous versions of the Microsoft C++ compiler. However, I don't think that is the point. It's a bit hard to learn what cool things you can do with a language feature if that feature is not supported in your compiler. The fact that it was possible to write code on previous versions of VC which ( correctly ) won't compile in the next release is just one more reason that this change is long overdue. I look forward to finding new and exciting uses for Koenig lookup, and I hope you do as well.

Version 1.1

In response to the small percentage of people who felt that this was as clear as mud, I have added a couple of extra examples and some more explanation. I'd appreciate feedback as to if this clarifies things for you all.