C++ 中的递归容器？

Question

可能的重复：
C++ 递归类型定义是否可行，特别是我可以将向量在 T 的定义范围内？

最近我在查看一些代码，注意到类似于以下的数据结构：

class TreeNode {
    std::vector<TreeNode> subNodes;
};

正如您所看到的，在定义 TreeNode 之前，容器是用 TreeNode 实例化的。该代码可以在 GCC 和 MSVC 下编译，但我记得看到有人说这不能保证行为。不幸的是，我在标准中找不到任何讨论这个问题的内容。

这样的容器如何实现？标准保证这种行为吗？如果标准不能保证这一点，我对此设计有哪些替代方案？

Answer 1

这很好，因为 std::vector 类中不包含任何 T 类型的具体实例：它通常使用指针实现。模板实例化 std::vector 不需要 TreeNode 的完整定义。

std::vector 通常作为指针三元组实现（尽管标准不要求这样做）：

template <typename T>
class vector
{
  ...
  T* start;
  T* end;
  T* end_of_storage;
};

If std::vector did 中是否包含 T 的具体实例，那么您就会遇到问题。以下代码不是合法的 C++，因为它创建了一个循环“has a”定义：

template <typename T>
class container
{
  T x;
};

class TreeNode
{
  container<TreeNode> subNodes;
};