使用包含结构的 Vector 的指针问题

Question

我目前真的很困惑如何解决以下问题：

struct node {
    int a;
    node* b;
}

我将有两个没有父节点的根节点，然后有更多节点指向其父节点

vector<node> IholdAllTheNodes;

node noparent1; <--- these get returned from a method
node noparent2;

IholdAllTheNodes.pushback(noparent1);
IholdAllTheNodes.pushback(noparent2);

node withparent1; <---- i am happily points to noparent1
node withparent2; <-----i am happily points to noparent2

到目前为止没有任何问题，

IholdAllTheNodes.pushback(withparent1) <<<< oops this causes all the pointers to move.

现在都工作得很好，withparent 节点不再指向其父节点，因为我已经移动它们了。

我的问题只是如何在不移动原始节点的指针的情况下向节点向量添加更多节点。 （我无法获得向量的固定大小）

如果有人有时间解释，为什么即使推回添加到向量列表的末尾，先前信息的位置也会发生变化？

Answer 1

致电 reserve

IholdAllTheNodes.reserve(MAX_SIZE);

您可以提前 以避免重新分配。它要求您预先知道 MAX_SIZE。

或者，

• 建议：将其设为 指针容器
• 使其成为std::vector； > （类似但效率较低）
• 使其成为 std::vector （类似但乏味且容易出错）
• 建议：避免如果可以的话使用指针。按 size_t（整数）索引将节点寻址到 IholdAllTheNodes 中

Answer 2

您的问题是您按向量中的值存储节点。它们被复制，可能被复制很多次。每次一个节点都会被放置在不同的内存地址中。结果，您将收到指向它的不同指针，并且旧指针将指向无效位置。

正如其他答案所建议的，使用任何类型的指针将节点存储在向量中。我会推荐 boost::ptr_vector 或 std::vector; >

编辑：

只是不同意保留建议：

这很危险。您需要在所有可能的地方放置大的粗体警告，以便将来修改此代码的人不能忽略它。因为当您向矢量添加超过 MAX_SIZE 个元素时，您的太空飞船将在太阳上结束燃烧。在这种情况下，我建议使用 boost::array 因为它的大小是固定的（因此使您的假设更加明显）并且至少在调试版本中捕获缓冲区溢出

Answer 3

调用具有特定大小的 IholdAllTheNodes.reserve() ，它将保证进一步的插入不会使指针无效，直到达到这样的保留量。