如何在C++中声明一个自引用容器

Question

对于C中struct的typedef，我不能这样做：

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

因为node_t在定义之前是未知的，所以它不能在自己的定义中使用。有点像第二十二条军规。然而，我可以使用这个变通方法来制作所需的自引用类型：

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

类似地，我想为一个引用自身的C++容器做一些类似的事情：

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

当然，编译器抱怨在定义node_t之前从未听说过node_t，就像上面的struct typedef一样。

那么，有没有像struct那样的变通方法呢？或者更好的方法？（不，我不想使用void指针。）

Answer 1

你可以这样做：

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

在struct node_t之后，编译器知道名称为node_t的类型存在，类似于前向声明。

Answer 2

该语言不支持typedefs的前向声明。因此，您不能使用：

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

您可以使用struct node_t {...};实现容器的概念，我相信这不需要详细说明。

Answer 3

如果将结构指针命名为（即typedef struct <name> {...}），则可以自引用结构指针。我通常使用以下习语：

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

这基本上将前面的答案应用于实际代码。