Круговая шаблонная справочная структура

У меня есть проблема с круговой ссылкой на шаблон. Я хочу сделать дерево, используя класс узла и края класса следующим образом;

template <typename EdgeT>
class node
{
public:
std::vector<EdgeT> edge_out;
std::vector<EdgeT> edge_in;
};template <typename NodeT>
class edge
{
public:
NodeT* src;
NodeT* dst;
int weight;
};template <typename NodeT, typename EdgeT>
class graph
{
public:
std::vector<NodeT> nodes;
};

Я обнаружил, что не могу объявить класс графа ex:

graph< node, edge > g; // <--- this cannot be solved

graph< node< edge <node.....>, edge< node< edge>>  >  //it makes infinity declaration..

Как я могу переопределить структуру классов?

0

Решение

Вот один из подходов:

#include <vector>

template<template<typename NodeT,typename T>class EdgeT, typename T=double>
struct Node {
typedef Node<EdgeT,T> self_type;
typedef EdgeT<self_type, T> edge_type;
std::vector<edge_type> edge_out;
std::vector<edge_type> edge_in;
T data;
};

template<typename NodeT,typename T>
struct Edge {
typedef NodeT node_type;
node_type* src;
node_type* dst;
int weight;
};

template<typename NodeT, typename EdgeT=typename NodeT::edge_type>
struct graph {
typedef NodeT node_type;
typedef EdgeT edge_type;
std::vector<NodeT> nodes;
};

int main() {
typedef graph< Node<Edge> > graph_type;
graph_type my_graph;
my_graph.nodes.push_back( graph_type::node_type() );
my_graph.nodes.push_back( graph_type::node_type() );
my_graph.nodes.front().edge_out.push_back( {&my_graph.nodes[0], &my_graph.nodes[1], 1} );
my_graph.nodes.back().edge_in.push_back( {&my_graph.nodes[0], &my_graph.nodes[1], 1} );
}

для другого подхода, вы можете посмотреть, как boost::variant обрабатывает рекурсивные варианты.

Другой способ приблизиться к этому был бы более формальным. Метапрограммирование шаблонов C ++ — это функциональный язык — существуют различные методы функционального программирования для описания рекурсивных структур без предварительного объявления, которые можно использовать.

Могу поспорить, что комбинатор с фиксированной запятой какого-то рода может сработать, но я не могу понять, как это сделать. 🙂

2

Другие решения

Вам нужно выяснить причину, по которой вам нужно использовать шаблоны. Например, если вы хотите, чтобы данные были динамическими в ребре, вы можете использовать:

//foward declaration
template <typename T>
class node
{
std::vector<Edge<T> > edge_out;
std::vector<Edge<T> > edge_in;
}template <typename T>
class edge
{
Node<T>* src;
Node<T>* dst;
T    weight
}template <typename T>
class graph
{
std::vector<Node<T> > nodes;
}

Точно так же, если вы хотите иметь данные, которые отличаются в вашем узле. Но в целом лучше заранее выяснить причину шаблонов. Я посмотрел на чрезмерно шаблонизированный производственный код, и он совершенно не поддерживается.

0