CODEWITHSUNDEEP
c++templatesmetaprogrammingcircular-dependency
Mihai Bişog
Mihai Bişog

Reputation: 1018

Yet another template circular dependency issue

I'm trying to create an object oriented template based generic graph structure however in my design I came across a possible circular dependency which I'm not sure how to avoid.

I define my vertex and edge class as follows:

template <class label_type, class edge_type>
class basic_vertex { .. }

template <class vertex_type, class weight_type = std::int32_t>
class basic_edge { .. }

In the vertex class I keep track of the inner edges and outer edges attached to the node by storing pointers to them in a std::list.

In the edge object I keep 2 references denoting the source and the destination vertices.

If I am to fill in the vertex template parameters I need to know about the type of the edge. In order to know the type of the edge I need to know about the type of the vertex.

Any idea how to solve this?

Upvotes: 0

Views: 234

Answers (3)

toch
toch

Reputation: 3945

There is a solution to resolve mutual dependencies between class templates. But before considering it, I usually ask myself: "Shouldn't I decouple it?" Indeed, it could be a bad design. But sometimes, it's part of the model. Your case, the graph, is an example.

The solution is based on decoupling at the concept level and introduce an intermediary template type that will embed and know both types (vertex and edge) a and break the loop.

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

http://ideone.com/FrBqcb

You'll find an extensive explanation of the solution in those very good lecture notes about advanced C++ technics.

Upvotes: 1

excalibur
excalibur

Reputation: 944

Whether its templates or not, its the same issue of circular dependency with classes. One of your classes has to be able to work with just a pointer/ref to the other class. Forward declare class Edge; Use Edge* in basic_vertex Use basic_vertex in Edge

Upvotes: 1

Thirler
Thirler

Reputation: 20760

you can pre-announce a class before its use to solve circular dependency, as follows:

class basic_vertex;

Upvotes: 1

Related Questions