c++ - 不使用指针的递归数据结构

Question

在我攻读 CS 学士学位期间，我多次遇到递归数据结构的使用。在 C++ 中，我总是最终使用指针使我的数据结构递归，就像我在 C 中所做的那样。

一个简化的例子如下:

struct Tree{
    int data;
    struct Tree *left, *right;
};

但是，使用指针往往是一项有风险的工作，需要花费大量时间调试和测试代码。对于这些结果，我想知道是否有任何其他有效的方法可以在 C++ 中定义递归数据结构。

在其他编程语言中，比如 Rust，我见过这样的事情:

struct Node {
    children: Vec<Node>,
    node_type: NodeType,
}

在 C++ 中是否有更安全、更舒适的方式来定义此类递归结构。一种可能性是使用 std::Vector，但我不知道该方法的性能。

Answer 1

使用指针而不是值的原因是因为您永远无法定义您的 struct，因为它的大小将无限递归。

struct Tree{
    int data;
    struct Tree left, right;
};

忽略填充等，您可以将 Tree 的大小近似为

sizeof(Tree) == sizeof(int) + sizeof(Tree) + sizeof(Tree)
//                     ^data         ^left          ^right

但是你可以看到，因为 Tree 有两个 Tree 成员，而这些成员本身有两个 Tree 成员，而那些成员有两个树成员....你可以看到这是怎么回事。