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

Question

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

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

因为node_t只有定义了才知道，所以不能在自己的定义中使用。有点像第 22 条军规。但是，我可以使用此解决方法来创建所需的自引用类型：

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

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

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

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

Answer 2

你可以这样做：

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

在struct node_t之后，编译器知道名称为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

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

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

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

c++

containers

typedef

self-reference