Can't define templated types for my LruCache class

#include <map>
#include <list>

template < typename K, typename  V>
class LruCache
{
private:
    typedef std::pair< K, V > EntryPair;
    typedef std::list< EntryPair > CacheList;
    typedef std::map< K, CacheList::iterator > CacheMap;

public:
    LruCache(){}
    ~LruCache(){}
};

if I try simply

LruCache cache;

I get the following compilation error:

LruCache.h:17:46: error: type/value mismatch at argument 2 in template parameter list for ‘template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map’
LruCache.h:17开发者_开发知识库:46: error:   expected a type, got ‘LruCache<K, V>::CacheList:: iterator’
LruCache.h:17:46: error: template argument 4 is invalid

However, if I define the class without template types. i.e.

class LruCache
{
private:
    typedef std::pair< int, int > EntryPair;
    typedef std::list< EntryPair > CacheList;
    typedef std::map< int, CacheList::iterator > CacheMap;

public:
    LruCache(){}
    ~LruCache(){}
};

It compiles just fine.

Use typename as:

typedef std::map< K,typename CacheList::iterator > CacheMap;
                   //^^^^^^

Its because iterator is a dependent name on the template argument. Its value depends on CacheList which in turn depends on the T which is in fact a template argument. That is why typename its needed here which tells the compiler that iterator is actually a nested type, not static value.

However, in the second case, its not a dependent name.

Read this detail explanation by Johannes:

• Where and why do I have to put the "template" and "typename" keywords?

Replace this:

typedef std::map< K, CacheList::iterator > CacheMap;

with this:

typedef std::map< K, typename CacheList::iterator > CacheMap;

See this question. Basically, the compiler doesn't know (without knowing the template arguments) whether CacheList::iterator is a type or a value until instantiation time, and it's forbidden from postponing the decision until then, so it assumes that it's a value and you have to give it a "hint" otherwise.