Cyclic Pointers in C++

Question

I am implementing a suffix trie structure in C++, where I use three classes, Trie, Node and Edge. Since I'm using classes, I've separated my function/variable declarations into header (.hpp) files and their implementations in respective .cpp files. Now I'm not used to doing this (I usually used to write everything in one .cpp file), but I think it is advantageous both for readability and structure.

So I have the following files:

Launcher.cpp, containing the main() function.
Trie.hpp, containing the declarations of functions and variables.
Trie.cpp, containing the implementations of the functions declared in Trie.hpp.
Node.hpp, containing the declarations of functions and variables.
Node.cpp, containing the implementations of the functions declared in Node.hpp.
Edge.hpp, containing the declarations of functions and variables.
Edge.cpp, containing the implementations of the functions declared in Edge.hpp.

Now the way I've implemented the trie is that each Node has a vector of type Edge. Additionally, I want that Edge has a pointer Node* so that it is pointing to another node (this is what edges do). Now although this seems like a cyclic definition, I recall that it can be achieved (at least, I used to be able to do this when my programs were all in one .cpp file).

But since we now have all these separate files with lots of #includes at the top, I have to #include 'Node.hpp' in Edge.hpp, and #include 'Edge.hpp' in Node.hpp. If I do not do this, I get errors such as "Edge is not defined in this scope". But if I do all the includes, I get an infinite-loop style error message:

The command I'm running is

g++ -std=c++11 -Wall -o program Edge.cpp Node.cpp Trie.cpp Launcher.cpp

I hope that's what I'm supposed to be running. Is there any way I can achieve what I want without these errors? I'm sure this would work if I put everything into one file.

EDIT: I have done the following in Edge.hpp, and everything seems to be working fine!

#ifndef EDGE_HPP
#define EDGE_HPP

#include <string>

class Node;         //Forward definition

using namespace std;

class Edge{

    private:
        string label;
        Node* pointsTo;

    public:
        Edge();
        Edge(string, Node*);
        string getLabel();
        Node* getPointsTo();

};

#endif

This is probably easy to resolve. But you need to show your code. — selbie, Jan 08 '17 at 20:14
In `Edge.hpp`, a forward declaration should be sufficient; as in, `class Node;` You shouldn't need to `#include "Node.hpp"` — Igor Tandetnik, Jan 08 '17 at 20:15
@IgorTandetnik Is that considered good practice though? It seems like cheating. — Luke Collins, Jan 08 '17 at 20:15
It's quite common, widespread practice, if that's what you are asking. There's no other way in C++ to break circular dependencies. — Igor Tandetnik, Jan 08 '17 at 20:17
Also, make sure your headers have [include guards](https://en.wikipedia.org/wiki/Include_guard) — Igor Tandetnik, Jan 08 '17 at 20:17
@IgorTandetnik Thanks for the help - I'll check exactly what those are - I'm not used to all these files running about. — Luke Collins, Jan 08 '17 at 20:18
@LukeCollins what is bothering you is not specifically related to having multiple files. It is related to circular references between classes, a quite common pattern that is nothing unusual, and is usually solved by *forward-delcaration*. [This will surely help](http://stackoverflow.com/questions/4757565/what-are-forward-declarations-in-c) — A.S.H, Jan 08 '17 at 20:22
@IgorTandetnik Check out the update I added - did I do the #include guards right? — Luke Collins, Jan 08 '17 at 20:25

score 2 · Accepted Answer · answered Jan 08 '17 at 20:35

This is a simple case of forward declaration.

Now the way I've implemented the trie is that each Node has a vector of type Edge.

This would be translated to something like this, in Node's header file:

class Edge;

class Node {

public:
    std::vector<Edge> edges;

    Node();
    ~Node();
};

This will be sufficient to declare the Node in its header file. Don't need to include Edge's header file.

Now, the .cpp file, that defines Node's constructor and destructor, must include both header files, so that both classes are fully declared.

Additionally, I want that Edge has a pointer Node* so that it is pointing to another node (this is what edges do).

And that simply translates to, in Edge's header file:

class Node;

class Edge {

public:
    Node *from_node;
    Node *to_node;

    // ...
};

Again, don't need to include Node's header file.

Having Node's header file include Edge's header file, instead of forward-declaring the class, would probably be fine too, with only Edge's header file needing to forward-declare the Node class.

The only thing you will need to keep in mind is that any code that needs to use the Edge class, and work with its Nodes, will need to include both header files. Merely including Edge will not be sufficient, since that code won't get the declaration of each Node, that the edge points to, unless Node's header file is also included.

Also, sometimes forward declarations might make it impossible to declare inline class methods, that need to use the forward-declared class. There are various ways around that, too.

Cyclic Pointers in C++

1 Answers1