typedef and typename

I'm trying to return an iterator to a map from it's wrapper class. Finally got it to compile but wanted to ask why this didn't work.

Code:

---

template <typename key, typename value>
class MgrBase
{
    typedef typename std::map< key, value> MgrMap;
    typedef typename MgrMap::iterator MapIter;
    public:
        MgrBase();
        virtual ~MgrBase();
       
        MapIter Get(key ID);   
        size_t getMemSize();
};

template <typename key,typename value>
MgrBase<key,value>::MapIter MgrBase<key,value>::Get(key ID)
{
    MgrMap::iterator map_iter(m_Objects.find(ID));
         
    return map_iter;
}

---

To get this to compile I had to add typename to the front of the function prototype and definition.

Code:

---

template<typename key,typename value>
class MgrBase
{
...
      typename MapIter Get(key ID);   
...
};

template <typename key,typename value>
typename MgrBase<key,value>::MapIter MgrBase<key,value>::Get(key ID)
{
    MgrMap::iterator map_iter(m_Objects.find(ID));
         
    return map_iter;
}

---

Why wasn't this enough?

Code:

---

typedef typename MgrMap::iterator MapIter;

---

Seems to me the typename is in the typedef so why did I have to add typename to the declaration and definition?

The short answer is that MgrMap is a dependent type so the type MgrMap::iterator is also a dependent type. The actual type depends on template parameters so is unknown to the compiler when it first parses the declaration of the templated MgrBase class.

The compiler can only deduce what the type is when the template is actually instantiated. When parsing the declaration initially (ie when it sees the declaration of the template class MgrBase, but before trying to instantiate it with actual template parameters), there is a C++ language rule that says qualified dependent names should be parsed as non-type.

You've obscured this a little in your example by using a typedef. The thing to understand, however, is that typedef does not define a new type and does not suspend those other parsing rules. It declares a pseudonym for an existing type or (within your template) a qualified dependent name of a type: the actual type still depends on template arguments - it's still a dependent type.

In your example MgrBase<key,value>::MapIter MgrBase<key,value>::Get(key ID) is obvious to you and I because we look at the whole construct.

However, the token parser in the C++ compiler does things in a more piecemeal manner: it is required to look at one token at a time. The typedef MgrBase<key,value>::MapIter is a pseudonym for MgrMap::iterator (typedef does not declare a new type). So the tokens MgrBase<key,value>::MapIter MgrBase<key,value>::Get(key ID) are actually treated by the compiler as MgrBase<key,value>::iterator MgrBase<key,value>::Get(key ID). The problem is then that MgrBase<key,value>::iterator is a qualified dependent name, so the compiler is required to treat it as a non-type name (something which may be a variable name, etc) before going further. It then gets to MgrBase<key,value>::Get(key ID) which looks like the declaration of a function, but such things are out of place if they occur immediately after a non-type name. Hence the compiler complains bitterly, as it is required to do.

The typename keyword is therefore necessary to tell the parser that MgrBase<key,value>::iterator is a type name before it gets to MgrBase<key,value>::Get(key ID). Subsequently, when the type is actually instantiated, the compiler is able to substitute in actual types for key and value, and fill in the blanks. But it is not able to do this when parsing the template declaration initially.

Interesting. Thanks for the great answer.

Quote:

---

typedef typename std::map< key, value> MgrMap;

---

The typename here is unnecessary. std::map<key, value> is not dependent.

Quote:

---

typename MapIter Get(key ID);

---

I'm pretty sure the typename here is also unnecessary. You're within the template, so there shouldn't be any confusion as to what the name refers to.

It would not compile under VS 2005 without typename.

Being "within the template" or not does not change whether something is a dependent type or not.

But it does change the lookup rules.

Anyway, I can't look it up in the standard. The rules changed in the final version (compared to the latest draft), I think, and the 0x draft has relaxed rules. And if it compiles now, all's fine.

True; it changes lookup rules. But typename (at least in C++98) affects the parser in contexts where dependent names are not treated as type names by default. Application of lookup rules comes later.

One of the headaches of this sort of thing is that a number of compilers get this wrong (in the sense that a pedantic interpretation of the standard must be considered right): they insist on typename in circumstances where it is not needed, or allow it to be omitted in circumstances where it is.

I'm not sure offhand if 0x has relaxed the rules or not. Given the number of compilers that get things wrong now, I'm not sure that relaxing the rules is a good idea: it could simply mean more tolerance of compilers not following the rules.

This sounds like typename is a mistake introduced into the language if you ask me. If it was meant to ease the task of writing compilers and many compilers ignore it, then... well, why did it make it into the language in the first place?

typename was not introduced to make things easier for compilers. It was introduced as a means of making the language/gramma able to express concepts it couldn't.

First there were C++ templates. One side effect of templates was introducing the notion of dependent names and types (dependent on template arguments), a notion which does not exist in C nor in any other context in C++. In some contexts, the basic rules of the language (which work in C, and in parts of C++ unrelated to templates) mean that dependent names are not treated as types but, when working with templates, some of those dependent names need to be treated as types. typename was simply the means that was introduced to force a dependent name to be treated as a dependent type - in a manner that works with the C++ grammar parsing rules.

The fact that compilers do not do things right with typename does not mean typename is a mistake. It is actually more an issue of quality of implementation of compilers. Although it is true that, when compilers are written and/or a programming language is used, lessons will be learnt about when the rules need to be tightened or relaxed.

I believe they should never have been implemented in the first place.
The fact that many compilers do get it wrong means that it is not so much about a technical challenge but rather a forced unnecessary challenge added by the standard.
Instead of having to tell the compiler if it's a dependant type or function or whatever, the compiler could simply instantiate a template to get the correct meaning of the dependant name, avoiding the whole typename/template mess.

The only problem of doing so today would mean it would probably break a huge amount of code since templates aren't instantiated until used.
Or perhaps there's something I'm missing here, due to as to why the standard chose the way it did.

Well before encountering this code I found some typedef typename stuff in the STL and in STLPort. I must confess seeing typedef and typename like that threw me at first. Later when writing this class it became clear to me what was going on.

So in the end it's been a good learning experience. One I don't think would have been given its just due by reading it in a book. For me it's one of those little nuances you have to experience by having the compiler yell at you for an hour or so before the light goes on and you finally understand it. If and when I see that error message in the future I will know exactly what the problem is.

MSVS 2005 does very good with templates but I'm not so sure how standards compliant they are. 2005 as a whole seems to follow the standard much more than 2003 and far more than 6. The only thing about templates that is very annoying is the error messages they generate when either the template code is wrong or the use of the template code is wrong. Unfortunately it does not tell you which one is the case and I'm not sure it could. Some of you are saying the new standard will correct this and if so I cannot wait. Template errors as they are now are long, messy, ugly, and not at all informative - actually they are probably a bit too informative which means they tell me everything about nothing. I'm getting better at deciphering these errors with each template I write and as my templates become more involved.

Quote:

---

Originally Posted by Elysia

I believe they should never have been implemented in the first place.
The fact that many compilers do get it wrong means that it is not so much about a technical challenge but rather a forced unnecessary challenge added by the standard.
Instead of having to tell the compiler if it's a dependant type or function or whatever, the compiler could simply instantiate a template to get the correct meaning of the dependant name, avoiding the whole typename/template mess.

The only problem of doing so today would mean it would probably break a huge amount of code since templates aren't instantiated until used.
Or perhaps there's something I'm missing here, due to as to why the standard chose the way it did.

---

Instantiate it with what? a template could easily be written such that only one particular subset of types could be a parameter. The compiler has no way of deducing what the possible or actually used template parameters may be. Only when a template is used is it possible to deduce defendant types. But before that is has to be parsed for non-dependent lookup errors, and it can't do that properly without knowing wether a given identifier is a type or a value.

There is no work around. There are times when the rules are unnecessarily strict, however. And there are some inconsistencies for when typename and .template are or aren't optional. But even if you fixed that, there wouldn't be any way to completely remove these constucts without creating ambiguities or decreasing functionality.

A typedef, for example, must be a specialized type, or the compiler will complain. This in turn tells me that the compiler must know all the parameters for the template, and can in turn instantiate the template to deduce the correct type of the dependant name. Is it not so?

No, it is not.

Template code must be parsed (i.e. read in and interpreted) before it can be instantiated (i.e. when it is used for particular types). During the interval between when the template code is parsed and when it is instantiated, the compiler needs help from things like typename to correctly handle dependent types.

The basic principle - inherited from C, incidentally - is that code which comes after a definition cannot be used as part of that definition. Changing that principle would have meant breaking backward compatibility between C++ and C (at least C89). Templates encounter problems with that because the definition of a template (i.e. the template code) has to be parsed by the compiler before any code that instantiates the template. However, one benefit of the approach is that code which innocently #includes a template definition (eg from a header file) is not forced to instantiate that template. That would be a consequence of the sort of changes you think should happen.

When you're programming now, you take it for granted that #include <iostream> does not force your code to make use of std::cout. However, the behaviour you are describing would mean that #include <some_template_code> forces your code to instantiate that template whether you have any need to or not. More generally, any code that uses a header would be forced to use EVERYTHING that is declared or defined in that header.

While, yes, it would theoretically be possible to change C++ to remove the need for the typename keyword. However, doing that properly would require significant changes of how other parts of C++ works. Programming language design in the real world is like that: change one aspect, and a trade-off is that it becomes necessary to change another aspect. The typename keyword was introduced to allow template metaprogramming to work, without propagating a series of changes on other parts of the language (eg changing the way code is parsed) or ... worse ... forcing changes to other parts of the language that break essential features.

That is not exactly true. VC++ really wouldn't care about typename at all weren't it for the standard saying that it has to.
There is nothing that prevents a compiler from parsing the template and storing it as an ambiguous parse tree until instantiation. A compiler following this strategy (and VC++ does that, more or less, based on its behaviour) has no need of type disambiguation.

On the other hand, such a compiler also loses the ability for early syntax checking of templates. Consider this code:

Code:

---

int p;

template <typename T> void foo()
{
  some_template<T>::xyz * p;
  p->bar();
}

---

An early-checking compiler decides that xyz is not a type (no typename keyword) and thus treats the first statement as

Code:

---

lookup::operator *(some_template<T>::xyz, ::p);

---

Then the second line is treated as

Code:

---

::p->bar();

---

Since the global p has type int, this is faulty and the early-checking compiler immediately complains. It does not require the template to be instantiated to complain! This is important in developing templates. (That's half the point of concepts.)

The late-checking compiler must wait until somebody actually instantiates the code to see whether the p here is a local variable or binds to the global. Only then can it issue compile errors.

Worse! Look at this modified example:

Code:

---

struct stru { void bar() { do_something(); } stru* operator ->() { return this; } };
struct ct { void bar() { do_something_else(); } };
stru operator *(int, const stru&) { return stru(); }

stru something;

template <typename T> struct templ { typedef ct xyz; };
template <> struct templ<float> { static int xyz; };
int templ<float>::xyz;

template <typename T> void foo()
{
  templ<T>::xyz * something;
  something->bar();
}

int main()
{
  foo<int>();
  foo<float>();
}

---

Here, both interpretations of xyz are valid. The foo<int>() will have a local something of type ct* and thus call do_something_else() (yes, it's undefined because it's through an uninitialized pointer, but given that ct::bar() doesn't access the this pointer, this is what will happen in typical systems). The foo<float>() will only have a global something of type stru, and thanks to the operator ->, it will call stru::bar() and thus do_something().

Yes, contrived, but it shows that the ambiguity is real and potentially dangerous.

Wow. Had no idea my little question would spawn such an interesting slew of posts. Excellent thread. Thanks all for some very good information and logical debate.