How do I create a map with iterator values?

Question

I am trying to define a class with a map of K -> pair of V and iterator of a list of K. This is to implement LRU cache. I got this working with decltype:

template <typename K, typename V> class LRUCache {
  std::list<K> q;
  typedef decltype(q.begin()) Iterator;

  typedef std::pair<V, Iterator> Node;

  int max_size;
  std::map<const K, Node> m;
}

However, I am not satisfied with using decltype and it all seems brittle when I try to use it. What would be the canonical way of doing this?

@Holt this doesn't work error: need ‘typename’ before ‘std::__cxx11::list::iterator’ because ‘std::__cxx11::list’ is a dependent scope typedef std::list::iterator Iterator; — ThamP, Jan 10 '17 at 09:47
`typedef typename std::list::iterator Iterator;`, this is written in the error message actually. — Holt, Jan 10 '17 at 09:50
When I use `typename std::list::iterator Iterator;` then it fails on declaration of `typedef std::pair Node;`, if I change them all to `typename`, I get different errors. Why do I need to use `typename` instead of `typedef`? — ThamP, Jan 10 '17 at 09:51
@Qwertiy If all rules corresponding to such iterators are satisfied (i.e. itearator validity), why not? — Zereges, Jan 10 '17 at 09:53
@ThamP You need `typedef typename std::list iterator Iterator;` (both keywords). — Holt, Jan 10 '17 at 09:53
Having a `const` key in `std::map` is pointless as it's already immutable. — molbdnilo, Jan 10 '17 at 09:53
Tip: you could use `using` instead of `typedef`. See here: http://stackoverflow.com/questions/10747810/what-is-the-difference-between-typedef-and-using-in-c11 — AMA, Jan 10 '17 at 09:55

score 1 · Accepted Answer · answered Jan 10 '17 at 09:58

I quite do not like old fashioned way of using typedef, since it seems to use reverse syntax for declaring stuff. You are also using int i = 5 and not int 5 i. (Not only) for this, new usage of using was introduced.

using Iterator = decltype(a.begin());

If you do not like decltype, you can use std::list<K>::iterator, but because K is template parameter, std::list<K> is dependent name and needs to be prefixed with typename.

using Iterator = typename std::list<K>::iterator;

Or with old fashioned typedef

typedef typename std::list<K>::iterator Iterator;

score 0 · Answer 2 · answered Jan 10 '17 at 09:54

The type of the iterator is

std::list<K>::iterator

If you want to use it, you have to use a typename in front of it, or alias it first with a

using iterator = typename std::list<K>::iterator;

However, using decltype there seems to be a perfectly valid use of it, if you can be sure everyone calling this code has c++11 or later.

score 0 · Answer 3 · answered Jan 27 '17 at 07:59

To add to the answers of others - the std::list<K>::iterator is a dependent type and C++ requires us to use typename in front of it.

The reason for this is that the compiler doesn't know whether ::iterator is a type, so it needs a hint with typename.

Another way of dealing with the original issue is to use using template, similar to the way some of <type_traits> are defined in C++14. We can define:

template <typename T> using ListIterator = typename std::list<T>::iterator;

Now, we can simply use ListIterator<K> in the LRUCache code:

template <typename K, typename V> class LRUCache {
  using Node = std::pair<V, ListIterator<K>>;
  std::list<K> q;      
  std::map<const K, Node> m;
  int max_size;
}

How do I create a map with iterator values?

3 Answers3