c++ - 在 C++ 中将类型的容器作为字段是个坏主意吗？

Question

在 C++ 中做这样的事情是不是一个坏主意:

struct Node
{
    string name;
    vector<Node> children;
};

我问是因为它看起来像调整大小 children出于任何原因都可能导致指数复制级联。但另一方面，vector<Node*>有它自己的问题，比如vector<shared_ptr<Node>> ，虽然安全，但内存局部性差(由于间接寻址太多)，当您尝试时会开始受到伤害，例如在内存中构建一棵巨大的树。

所以，一般来说，在 C++ (03) 中拥有自己类型的容器是不是一个坏主意？是否有其他原因避免(或更喜欢)这种习惯用法，而不是使用指针容器？

Answer 1

Is having a container of a type as a field a bad idea in C++?

作为一般规则，这还不错。这真的取决于上下文。

在这种情况下，与重要的调整大小操作和级联(假设这会成为问题)相比，共享指针的间接寻址应该不重要。

如果您可以在填充 vector 之前保留适当的大小或使复制变得微不足道，那么这里就没什么可担心的了。

如果它真的很大，您可以将您的节点建立在一个外部存储的基础上，该存储处理(并可能共享)这些节点。那么您的调整大小操作将变得微不足道，因为您的 children 都是指针。

根据节点的大小，这:

struct Node
{
    string name;
    shared_pointer<vector<Node> > children;
};

可能比共享节点更好。这实际上取决于大小、深度、调整大小的频率。容器不错，但您必须知道您的程序将如何执行才能选择最佳策略(分析在这里也有帮助，即使在您认为自己知道最快的情况下也是如此)。

如果您知道自己有很多对象并且需要调整很多大小，那么快速的外部存储将是一个不错的选择； jalf 的回答概述了一个很好的策略。

如果您将有很多突变，您还可以在后备存储中使用节点 vector 的 list，以及指向子元素列表元素的指针。

支持这些更复杂的实现也比您当前的设计需要更多时间，但如果您确实需要执行大量变更，它们值得尝试。实现和维护的简单性将对您的原始设计大有裨益。

如果您的图真的不会增长到很大，另一种方法是使用自定义分配器，它要么引用节点的后备存储，要么比默认分配器收缩得更少。