Why do I need to use typedef typename in g++ but not VS?

Question

It had been a while since GCC caught me with this one, but it just happened today. But I've never understood why GCC requires typedef typename within templates, while VS and I guess ICC don't. Is the typedef typename thing a "bug" or an overstrict standard, or something that is left up to the compiler writers?

For those who don't know what I mean here is a sample:

template<typename KEY, typename VALUE>
bool find(const std::map<KEY,VALUE>& container, const KEY& key)
{
    std::map<KEY,VALUE>::const_iterator iter = container.find(key);
    return iter!=container.end();
}

The above code compiles in VS (and probably in ICC), but fails in GCC because it wants it like this:

template<typename KEY, typename VALUE>
bool find(const std::map<KEY,VALUE>& container, const KEY& key)
{
    typedef typename std::map<KEY,VALUE>::const_iterator iterator; //typedef typename
    iterator = container.find(key);
    return iter!=container.end();
}

Note: This is not an actual function I'm using but just something silly that demonstrates the problem

Answer 1

Well, GCC doesn't actually require the typedef -- typename is sufficient. This works:

#include <iostream>
#include <map>

template<typename KEY, typename VALUE>
bool find(const std::map<KEY,VALUE>& container, const KEY& key)
{
    typename std::map<KEY,VALUE>::const_iterator iter = container.find(key);
    return iter!=container.end();
}

int main() {
    std::map<int, int> m;
    m[5] = 10;
    std::cout << find(m, 5) << std::endl;
    std::cout << find(m, 6) << std::endl;
    return 0;
}

This is an example of a context sensitive parsing problem. What the line in question means is not apparent from the syntax in this function only -- you need to know whether std::map<KEY,VALUE>::const_iterator is a type or not.

Now, I can't seem to think of an example of what ...::const_iterator might be except a type, that would also not be an error. So I guess the compiler can find out that it has to be a type, but it might be difficult for the poor compiler (writers).

The standard requires the use of typename here, according to litb by section 14.6/3 of the standard.

Answer 2

It looks like VS/ICC supplies the typename keyword wherever it thinks it is required. Note this is a Bad Thing (TM) -- to let the compiler decide what you want. This further complicates the issue by instilling the bad habit of skipping the typename when required and is a portability nightmare. This is definitely not the standard behavior. Try in strict standard mode or Comeau.

Answer 3

This is a bug in the Microsoft C++ compiler - in your example, std::map::iterator might not be a type (you could have specialised std::map on KEY,VALUE so that std::map::iterator was a variable for example).

GCC forces you to write correct code (even though what you meant was obvious), whereas the Microsoft compiler correctly guesses what you meant (even though the code you wrote was incorrect).

Answer 4

The typename is required by the standard. Template compilation requires a two step verification. During the first pass the compiler must verify the template syntax without actually supplying the type substitutions. In this step, std::map::iterator is assumed to be a value. If it does denote a type, the typename keyword is required.

Why is this necessary? Before substituing the actual KEY and VALUE types, the compiler cannot guarantee that the template is not specialized and that the specialization is not redefining the iterator keyword as something else.

You can check it with this code:

class X {};
template <typename T>
struct Test
{
   typedef T value;
};
template <>
struct Test<X>
{
   static int value;
};
int Test<X>::value = 0;
template <typename T>
void f( T const & )
{
   Test<T>::value; // during first pass, Test<T>::value is interpreted as a value
}
int main()
{
  f( 5 );  // compilation error
  X x; f( x ); // compiles fine f: Test<T>::value is an integer
}

The last call fails with an error indicating that during the first template compilation step of f() Test::value was interpreted as a value but instantiation of the Test<> template with the type X yields a type.