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 iter = 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.

Inhibitory

The reason it is needed in g++, is because g++ is more compliant with the standard. VS was a bit lax on this part of the templatisation parsing (which has lead to other problems in more complex templates). – Nightmare

Yes but why does the standard friggin do this? I've dealt with identical code! – Aneurysm

Answer 1

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.

Touchhole

I think you mixed up your comments on the two calls to f, f( X() ); succeeds while f( 5 ); is a compile error. Anyway, MSVC handles this alright -- it seems to delay the decision of whether Test<T>::value is a value or a type until the template has been instantiated. It doesn't do this for members of a class template, however. – Rawalpindi

@Sumudu: you are right, I also corrected the f( X() ) call into the more explicit code above. If MSVC delays the check until the type is instantiated then MSVC is not complying with the standard. – Inkblot

Answer 2

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.

Cinemascope

Here, too, I think you mean KEY,VALUE in the line that starts with "typename". With that change, it compiles for me. :) – Sonics

I saw your comment on the question and fixed it just now :) – Cinemascope

for a good faq, consider womble.decadentplace.org.uk/c++/… – Icing

..::iterator can reference an static member. – Ranket

dribeas, have you actually read his answer? he literally says "standard requires the use of typename". – Icing

i tested the code, and yeah he needs const_iterator . i've overlooked that too. but it's really too easy to overlook imho :) – Icing

oh wait. the .map() was also wrong in the original question. and ::iterator too. i'm not sure whether it's right to correct it in the answer then as i did. anyway i will leave it as is and let magnus/robert decide on that. cheers! – Icing

xhantt: Yes, it could be a static member, but that would (as I say in my answer) be an error. Given no other context, in the line "std::map<KEY,VALUE>::const_iterator iter = container.find(key);", "...::const_iterator" must be a type, if we want it to compile. Is that not right? – Cinemascope

indeed. the typename is used to help the compiler do analysis. but the compiler is actually not required to check any syntax within a template if it's not instantiated. whether and when the compiler signals an error (even if you write "; +;") or not is a question of its quality of implementation. – Icing

the only requirement is that the compiler signals an error (if there is something wrong) (actually, only some kind of diagnostic, could be a warning too. the standard does not know a distinction between "warning" and "error") at instantiation time (like, if you actually call the function template). – Icing

btw, i'm sorry if "dribeas, have you actually read his answer?" sounded a little offensive. i was just quite confused as to where he is saying it's not required. :) no offence, of course. – Icing

Indeed both are good answers, but Dribeas had really good(concise) example of a real conflict of meanings for iterator. – Inhibitory

Robert: You are of course free to decide which answer helped you the most :) – Cinemascope

@litb: I had read the answer twice, and nonetheless I had not actually read it. I somehow read that typename was not required, instead of what the Magnus had actually said: typedef is not actually required.'Attention deficit reader' is a nice way of putting it :) – Inkblot

I have already removed the downvote, and my dearest excuses Magnus. – Inkblot

Simple example of fragment where compiler cannot parse without typename: (X::t)(y), is that a cast or function call? Note the precedence is different too! Whoever added typedef to C should be shot:) – Pedaiah

Answer 3

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.

Curkell

It would be a Bad Thing if the compiler did so willy-nilly. In fact, it's doing this only on broken code. There's actually no prohibition in the standard against compiling broken code. Should still be a warning (diagnostic) though. – Agribusiness

Answer 4

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).

Dungdungan

Actually, it looks like MSVC will check to see whether std::map::iterator is a type or not before deciding. I don't have a copy of the standard but this seems like non-conforming behaviour, but it only means that it will (try to) correct and compile some incorrect programs, not introduce errors into correct ones. – Rawalpindi

Yes, it's a bug because the compiler doesn't issue a diagnostic for illegal code. – Dungdungan

There's no such thing as illegal code. A diagnostic is only required if the program is ill-formed. – Pedaiah

Answer 5

It should be noted that the value/type kinding issue is not the fundamental problem. The primary issue is parsing. Consider

template<class T>
void f() { (T::x)(1); }

There is no way to tell if this is a cast or a function call unless the typename keyword is mandatory. In that case, the above code contains a function call. In general the choice cannot be delayed without forgoing parsing altogether, just consider fragment

(a)(b)(c)

In case you didn't remember, cast has a higher precedence than function call in C, one reason Bjarne wanted function style casts. It is therefore not possible to tell if the above means

(a)(b)  (c)   // a is a typename

or

(a) (b)(c)    // a is not a typename , b is

or

(a)(b) (c)    // neither a nor b is a typename

where I inserted space to indicate grouping.

Note also "templatename" keyword is required for the same reason as "typename", you can't parse things without knowing their kind in C/C++.

Pedaiah

MSVC uses an incredibly simple solution to this problem: it doesn't parse code inside a template function until the template is instantiated with a specific T. IMO that's a far more pleasant solution for developers than requiring lots of extra "this->", "typename" and "template" keywords, and lots of extra typedefs to redefine names that are already defined in a base class. (Yeah, yeah, I know, MSVC is not standard--but it's easier to use.) – Gagarin

However that behaviour exposes one to the possibility the semantics of two distinct instantiations are more different than the existing poor C++ rules already allow. – Pedaiah

True, but after spending dozens of hours converting my template code to be correct standard C++ by adding lots of syntactic noise, while puzzling over GCC's useless error messages (some of my favorites: "declaration of ‘operator =’ as non-function", "too few template-parameter-lists", "expected primary-expression before ‘>’ token")... I have come to loathe the official rules of C++. – Gagarin

@Qwertie, agreed. While MSVC may not be strictly conforming by allowing typenames to be ommitted in many instances, in my 16 years of using it I've never encountered a case where this behavior caused unexpected behavior in the resulting binaries. I'm just now porting some code over to GCC and am loving all of the errors it gives that don't provide any clue that a missing typename is the actual problem. Another word that begins with 't' comes to mind. – Ochoa