Thread: 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.

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

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

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.

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.

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?

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.

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.