C ++, forward declarations and recursive data types

Question

I would like to be able to have a map where the value is a pointer to a map. Sort of

std::map<KeyType, const_pointer_to_this_map's_value_type> 

I know that I could use const void * instead of const_pointer_to_this_map's_value_type.

I have seen tricks for determining types of cyclic data, for example https://gist.github.com/tivtag/1208331 or http://qscribble.blogspot.fr/2008/06/circular-template-references-in-c.html , but I'm not sure what and how they can be applied to my case.

There they use their own classes (Vertex and Edge; A and B), but here std :: map and std :: map :: value_type are already defined in the STL headers, and I cannot just create them using the Combo class.

Is there a way to identify the map above?

Answer 1

Just wrap it in a structure. You need to specify a name of this type in order to be able to refer to it.

 template<class T> class Graph { std::map<T, const Graph<T>*> data; public: // ... }; 

In C ++ 11, you can also do this with a typedef template alias with a forward declaration:

 namespace { template<class T> struct GraphWrap { class type; typedef std::map<T, const typename GraphWrap<T>::type*> type; }; } template<class T> using Graph = typename GraphWrap<T>::type; 

Of course, using std::map here can be a little misleading, because you are using the key type parameter as the type of the container value. As Mooing Duck said, you seem to be modeling a directed graph where each node has at most one outgoing edge. If you want to do something with charts, there are graph libraries, if you do something else or just want to find out, then this is a different story.

Answer 2

From http://www.sgi.com/tech/stl/Map.html

A map is an associative container of pairs, which means that its value type is pair<const Key, Data>

std::map<K, M>::value_type always std::pair<K, M> , therefore:

 #include <map> typedef int KeyType; struct MappedType { const std::pair<const KeyType, MappedType>* p; }; void g() { std::map<KeyType, MappedType> m; m[0].p = 0; m[1].p = &(*m.find(0)); }