C++, форвардные декларации и рекурсивные типы данных

Question

Я хотел бы иметь возможность иметь карту, где значение является указателем на карту. Что-то вроде

std::map<KeyType, const_pointer_to_this_map's_value_type> 

Я знаю, что я мог бы использовать константную пустоту * вместо const_pointer_to_this_map's_value_type.

Я видел трюки для определения типов циклических данных, например https://gist.github.com/tivtag/1208331 или http://qscribble.blogspot.fr/2008/06/circular-template-references-in-c.html, но я не уверен, что и как они могут применяться к моему делу.

Там они используют свои собственные классы (Вершина и Край, A и B), но здесь std :: map и std :: map :: value_type уже определены в заголовках STL, и я не могу просто их создавать с помощью класс Combo.

Возможно ли определение того, как вверху карту?

Answer 1

Просто оберните его в конструкцию. Вам нужно указать имя типа, чтобы иметь возможность ссылаться на него.

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

В C++ 11 вы можете сделать это с помощью шаблона псевдонима в ЬурейеЕ с упреждающее объявление:

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; 

Конечно, используя std::map здесь может быть немного вводит в заблуждение, потому что вы 'используя параметр типа ключа в качестве типа значения контейнера. Как сказал Mooing Duck, вы, кажется, моделируете ориентированный граф, где каждый узел имеет не более одного исходящего края. Если вы хотите что-то делать с графиками, там есть библиотеки графов - если вы делаете что-то еще или хотите просто учиться, то это еще одна история.

Answer 2

От http://www.sgi.com/tech/stl/Map.html

Карта является пара ассоциативный контейнер, а это означает, что его тип значения является pair<const Key, Data>

std::map<K, M>::value_type всегда std::pair<K, M>, так:

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