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.

Answer 2

This is unfortunately not possible, in the way you express it.

On the other hand, it seems to me that (given your requirements) you could reverse the storage.

What if you used a list of the Values, and then had the map point to this list ?

This would break the cyclic dependency.

typedef std::list< std::pair<Key, Value> > ListType;
typedef std::multiset<typename ListType::iterator, CmpFirst> MapType;

(Not sure if I really understood what you were trying to achieve though...)

Another solution you should probably consider is to see if you can express this in terms of Boost.MultiIndex. When several iterations/lookup patterns are necessary, Boost.MultiIndex is often a better alternative than handmade solution, as it interleaves the indexes within the values so as to minimize storage. Plus consistency (ie, having all indexes referencing the same set of elements) is a given.