Saturday 14 February 2009

Koenig lookup...wha?

This is the first piece of C++ code many programmers wrote:


std::operator<<(std::cout, "hello world!").operator<<(std::endl);



Don't believe me? Let's reorganize it a little bit:


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


More familiar now, isn't it?

The dark feature that makes it possible for the latter to be equivalent to the former is a feature of C++ language called "Koenig lookup" a.k.a. "Argument Dependent name lookup".

Let's unveil why without it you could not write that piece of code the easy way....

This is the signature for operator<<:


// Extracted from libstdc++-v3, with minor modifications
namespace std {
template<typename _CharT, typename _Traits&
basic_ostream<_CharT, _Traits> &
operator<<(basic_ostream<_CharT, _Traits>& __out, const char* __s);
};


Better without the templates clutter...


namespace std {
ostream& operator<<(ostream&, const char*);
};


You can see it's defined in namespace std. like the other stuff from the STL.

When something is defined inside a namespace, we have to either use "using" directive or prefix it with that namespace and "::", like with cout and endl in this piece of code...


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


But then why don't we need to use any prefix for operator<< ??? Because of Koenig lookup, which states that unqualified calls (i.e. not namespace-prefixed) to functions are also looked up in the namespaces associated to the types of the invocation arguments.

This makes it possible for operators to be called using the classic infix syntax and to avoid annoying namespace prefixes all over the place, without the need of a "using namespace".

Koenig lookup relies on the interface principle, which states that nonmember functions which mention a class and are supplied along with that very class (e.g. are declared in the same header file), are also part -logically speaking- of its interface.

But it can also lead to the opposite, forcing us to prefix a function call even when we already placed a "using" directive or directly being inside in the same namespace the function is declared in, due to the ambiguity it introduces (this is often referred to as Myers' example):


namespace A {
class AClass { };
ostream& operator<<(ostream&, const AClass&);
}

namespace B {
ostream& operator<<(ostream&, const A::AClass&);
void doStuff(A::AClass& a) {
cout << a; // ambiguous, operator<< from A or from B?
}
}


One last curious thing...do you know the type of std::end? it actually is a function template that receives an ostream as argument; it just appends an endline character to its input ostream and then flushes it:


// From libstdc++ v3.
template <typename _CharT, typename _Traits>
inline basic_ostream <_CharT, _Traits>&
endl(basic_ostream <_CharT, _Traits>& __os)
{
return flush(__os.put(__os.widen('\n')));
}


It is possible to append a function template to a series of invocations to << because of class basic_ostream's member operator<<, defined as follows:


// From libstdc++ v3.
__ostream_type&
operator<<(__ostream_type& (*__pf)(__ostream_type&))
{
return __pf(*this);
}


To test it, just use std:endl as the function it actually is:


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


NOTE: for those historicians out there, just recall Koenig lookup was not there since the beginning; it replaced "friend name injection" which stated that when a class template is instantiated, the names of friend classes and functions are “injected” into the enclosing namespace. g++ still supports this feature with the -ffriend-injection flag.

NOTE: cited pieces of the standard template library have been taken from GNU Standard C++ Library v3.

2 comments:

  1. Should the first line of code be like this:

    std::cout.op<<(char*).op<<(std:endl);

    or like this:

    std::op<<(std::cout, char*).op<<(std::endl);

    The first one would seem to be "obvious" and not rely on Koenig lookup. It would only use the magic of C++ operator overloading and require that ostream defined an operator<< inside the class rather than outside. The latter snippet is less obvious and does rely on Koenig lookup to work.

    ReplyDelete
  2. You're quite right. Thanks for the correction. I just addressed it.

    ReplyDelete