Я пытаюсь создать объектно-ориентированную основанную на шаблонах общую структуру графа, однако в моем дизайне я наткнулся на возможную циклическую зависимость, которую я не знаю, как ее избежать.
Я определяю свою вершину и класс ребер следующим образом:
template <class label_type, class edge_type>
class basic_vertex { .. }
template <class vertex_type, class weight_type = std::int32_t>
class basic_edge { .. }
В классе вершин я отслеживаю внутренние ребра и внешние ребра, прикрепленные к узлу, сохраняя указатели на них в std :: list.
В объекте ребра я храню 2 ссылки, обозначающие исходную и целевую вершины.
Если я хочу заполнить параметры шаблона вершины, мне нужно знать тип ребра. Чтобы узнать тип ребра, мне нужно знать тип вершины.
Есть идеи, как это решить?
Существует решение для разрешения взаимозависимостей между шаблонами классов. Но прежде чем рассмотреть это, я обычно спрашиваю себя: «Разве я не должен отделить это?» Действительно, это может быть плохой дизайн. Но иногда это часть модели. Ваш случай, график, является примером.
Решение основано на разделении на уровне концепции и введении промежуточного типа шаблона, который будет встраивать и знать оба типа (вершина и ребро) a и прерывать цикл.
template <typename T_graph, typename T_label>
struct vertex_tmpl {
typedef typename T_graph::edge_t edge_t;
edge_t* edge;
// .... maybe some more edges ....
};
template <typename T_graph, typename T_weight>
struct edge_tmpl {
typedef typename T_graph::vertex_t vertex_t;
vertex_t* vertex;
};
template < template <typename, typename> class T_vertex,
template <typename, typename> class T_edge,
typename T_weight = int,
typename T_label = int >
struct graph_tmpl {
typedef graph_tmpl< T_vertex, T_edge> self_t;
typedef T_vertex<self_t, T_label> vertex_t;
typedef T_edge<self_t, T_weight> edge_t;
};
int main() {
typedef graph_tmpl< vertex_tmpl, edge_tmpl> graph_t;
typedef typename graph_t::edge_t basic_edge;
typedef typename graph_t::vertex_t basic_vertex;
basic_edge edge;
basic_vertex vertex;
vertex.edge = &edge;
edge.vertex = &vertex;
}
Вы найдете подробное объяснение решения в эти очень хорошие лекционные заметки о продвинутой технике C ++.
Вы можете предварительно объявить класс перед его использованием для решения циклической зависимости следующим образом:
class basic_vertex;
Будь то шаблоны или нет, это одна и та же проблема круговой зависимости с классами. Один из ваших классов должен иметь возможность работать только с указателем / ссылкой на другой класс.
Форвард объявляет класс Edge;
Используйте Edge * в basic_vertex
Используйте basic_vertex в Edge