CODEWITHSUNDEEP
c++templatesstl
user2521308
user2521308

Reputation: 41

C++, forward declaration and recursive data types

I would like to be able to have a map where the value is a pointer into the map. Something like

std::map<KeyType, const_pointer_to_this_map's_value_type>

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

I've seen tricks for cyclic data type definitions, such as https://gist.github.com/tivtag/1208331 or http://qscribble.blogspot.fr/2008/06/circular-template-references-in-c.html but I am not sure if 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 can't just instantiate them with the Combo class.

Is there a way to define the map above?

Upvotes: 4

Views: 476

Answers (2)

willj
willj

Reputation: 2999

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

Map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>

std::map<K, M>::value_type is always std::pair<K, M>, so:

#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));
}

Upvotes: 0

Jon Purdy
Jon Purdy

Reputation: 54971

Just wrap it in a structure. You need to give a name to the 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 it with a template alias of a typedef 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 might be a bit misleading, because you’re using the key type parameter as the container’s value type. Like Mooing Duck said, you seem to be modelling a directed graph where each node has at most one outgoing edge. If you want to do something with graphs, there are graph libraries out there—if you’re doing something else, or if you just want to learn, then that’s another story.

Upvotes: 1

Related Questions