How to declare a self-referential container in C++?

Question

For a typedef of a struct in C, I can't do this:

typedef struct {
    unsigned id;
    node_t *left;
    node_t *right;
} node_t;

because node_t is not known until it is defined, so it can't be used in its own definition. A bit of a Catch-22. However, I can use this workaround to make the desired self-referential type:

typedef struct node_s node_t;
struct node_s {
    unsigned id;
    node_t *left;
    node_t *right;
};

Similarly, I would like to do something like this for a C++ container referring to itself:

typedef pair<unsigned, pair<node_t *, node_t * > > node_t;

but of course, the compiler complains that it's never heard of node_t before it's defined node_t, as it would for the struct typedef above.

So is there a workaround like for the struct? Or some better way to do this? (And no, I don't want to use void pointers.)

Answer 1

You can self-reference a struct pointer if you name it (i.e. typedef struct <name> {...}). I usually use the following idiom:

typedef struct _node_t { // "Temporary" name "_node_t"
    unsigned id;
    struct _node_t *left; // Have to use "struct _node_t"
    struct _node_t *right;
} node_t; // "Final" name

That basically applies the previous answers to actual code.

Answer 2

You can do it like this:

struct node_t : std::pair<unsigned, std::pair<node_t *, node_t * > >
{};

After struct node_t the compiler knows that the type with name node_t exists, similar to a forward declaration.