C++ mutual template dependency?

Question

I'd like to have two structures which point to eachother. Specifically, I'd like to have the following:

template<typename Key, typename Value> 
class MyStructure {
public:
  typedef map<Key, list<pair<Value, typename ListType::iterator>>> MapType;
  typedef list<typename MapType::element_type::iterator> ListType;
private:
  MapType map_;
  ListType list_;
}

Obviously this will not work since ListType is not declared previously as a type. How could I do this? As you can see I am using the iterator types as pointers to these two structures' elements.

I was thinking of using the curiously recurring template pattern, but could not get anywhere with that. Someone on ##c++ also suggested using template aliases, but that failed as well (at least, I don't know how to use this idea).

Am I doing something wrong, conceptually? Or perhaps "not in line with C++ concepts"? I could certainly do this with void*s, but I'm trying to make things The Right Way :)

Thanks!

Answer 1

Although I suspected this might be a duplicate (and in many ways it is), "Cheers and hth. - Alf" is right in pointing out that the potential duplicate question was specifically about the use of typedef for this kind of thing.

However, in the present question, the OP would like to know how generally to deal with mutual inclusion in the scenario described in the question.

Here is a suggestion:

#include <list>
#include <map>

template <typename Key, typename Value>
class MyElement;

template <typename Key, typename Value>
class MyStructure
{
public:
  typedef std::map<Key,MyElement<Key,Value> > MapType;
  typedef std::list<MyElement<Key,Value> >    ListType;
};

template <typename Key, typename Value>
class MyElement {
public:
  typename MyStructure<Key,Value>::MapType::iterator  map_iterator;
  typename MyStructure<Key,Value>::ListType::iterator list_iterator;
};

As you can see, I introduced a new data type MyElement, which contains the list iterator as well as the map iterator. Because that is a class rather than a typedef, it can be forward-declared.