How to declare two structs which have members of the others type?

Question

I am trying to make a directed graph, So I made a Graph class and it has a private edge struct and a private node struct. I would like my edges to have a node member which is the node that the edge points to, and I would like my nodes to have a list of all edges that lead away from them.

#ifndef DIRECTED_GRAPH_H 
#define DIRECTED_GRAPH_H

#include <iostream>
#include <vector>
#include <string>

class Graph {
public:
    Graph( const std::string & );
    ~Graph();

    void print();

private:
    struct GNode
    {
        std::string currency_type;
        std::vector<GEdge> edges; // line 19

        GNode( std::string name ) : currency_type( name ) {}
    };

    struct GEdge
    {
        int weight;
        GNode * node; // node that the edge is pointed towards

        GEdge( int weight, GNode* node ) : weight( weight ), node( node ) {}
    };

    GNode *source;
    std::vector<GNode> nodes; 

    void add_node( const std::string & currency );
    void add_edge( const GNode *& source, const GNode *& destination, int weight );
    std::string bellman_ford( const GNode *&source );
};

#include "directed_graph.cpp"

#endif

The problem is, the first struct being declared, in this case GNode, is not aware that GEdge exists which is causing the compiler to give me the error

directed_graph.h:19: error: ISO C++ forbids declaration of ‘vector’ with no type

How can I get around this?

Answer 1

Just use a forward declaration:

class Graph {

    // ...

private:

    struct GEdge;
//  ^^^^^^^^^^^^^
//  Forward declaration for GEdge

    struct GNode
    {
        std::string currency_type;

        std::vector<GEdge> edges; // <== This is now OK because of the
                                  //     forward declaration above

        GNode( std::string name ) : currency_type( name ) {}
    };

    struct GEdge // <== Now comes the definition of GEdge
    {
        int weight;
        GNode * node; // node that the edge is pointed towards

        GEdge( int weight, GNode* node ) 
            : weight( weight ), node( node ) {}
    };

    // ...
};

Here is a complete live example of the above code compiling.

Answer 2

You're embedding a GNode* in your GEdge. That doesn't need a struct definition, struct pointers are all represented the same, so the compiler already knows everything it needs. You're embedding full GEdges in (the vector in) your GNode. That needs a full struct definition at some point, with the vector it's deferred but if you decided to switch to std::array<> it would fail if GEdge wasn't already defined.

Swap the definition order and add a forward declaration:

#include <vector>
struct GNode;
struct GEdge { GNode *n; };
struct GNode { std::vector<GEdge> e; };

This has the advantage of working even if you're not getting help from the vector<GEdge> heap allocation's deferred construction:

struct GNode;
Struct GEdge { GNode *n; };
struct GNode { GEdge e; };

I just forward-decare structs reflexively, it helps me anyway.