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

Question

对于C语言中一个结构体的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之前从未听说过它，就像上面的struct typedef一样。

那么是否有类似于struct的解决方法呢？或者有更好的方法吗？（不，我不想使用void指针。）

- Mark Adler

---

这个有帮助吗：STL map onto itself? - Rahul Tripathi

你可以查看http://www.boost.org/doc/libs/1_57_0/boost/variant/recursive_variant.hpp或http://www.boost.org/doc/libs/1_57_0/boost/variant/recursive_wrapper.hpp的实现。 - ForEveR

你的第一个情况在C++中并不是问题：struct node_t { node_t* left; node_t* right; }; 完全没有问题。此外，std::pair 不是一个容器。 - juanchopanza

啊，抱歉。我是根据Wikipedia STL页面来的，它说pair是一个“简单容器”。而且，我知道第一种情况在C++中不是问题，这就是为什么我用“在C中”澄清了一下。 - Mark Adler

Answer 1

你可以像这样做：

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

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

- Rabbid76

Answer 2

这种语言不支持typedef的前向声明。因此，你不能使用以下代码：

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

您可以使用struct node_t {...};来实现容器的概念，我相信这不需要进一步解释。

- R Sahu

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

基本上，这将把之前的答案应用到实际代码中。

- Matthieu