使用 vector 来最小化堆分配会导致段错误

Question

在一个函数中，我创建了一个包含大量 space 的向量，我将运行时确定数量的对象 (Edge) 推送到该向量。然而，其他对象在向量中维护指向 Edges 的指针。有时整个程序段错误是因为指针变得无效，我怀疑当向量达到容量并重新分配时会发生这种情况，从而使内存地址无效。

有什么办法解决这个问题吗？或者是否有另一种将堆分配组合在一起的解决方案？

注意：这样做的主要动机是最小化堆分配，因为这是减慢我的算法的原因。最初我有 vector<Edge *> 并且添加的每个元素都是单独分配的。批量分配显着提高了速度，但此处描述的 vector 方法会使指针无效。

您的代码示例，根据要求：这是我声明为堆栈变量的向量：

vector<Edge> edgeListTemp(1000);

然后我使用右值重载将其添加到其中：

edgeListTemp.push_back(Edge{edge->movie, first, second});

Node 对象保留指向这些的指针：

first->edges.push_back(&edgeListTemp.back());
second->edges.push_back(&edgeListTemp.back());

其中edges声明如下：

std::vector<Edge *> edges; /**< Adjacency list */

Answer 1

A std::deque 添加后不会移动元素，因此只要您不删除引用的元素，迭代器和引用就是稳定的。

与 std::vector 一样，std::deque 提供随机访问迭代器。随机访问双端队列比 std::vector 慢一点，但仍然是 O(1)。如果您需要稳定的参考，轻微的减速可能是可以接受的。

或者，您可以保留对向量的引用和向量中的索引，而不是指向元素的指针。

Answer 2

有几种可能的解决方案：

如果您已经预先知道元素的最大数量，请从头开始对向量执行 reserve；在达到该大小之前不会重新分配元素；
如果您不知道最大数量 elements/don 出于性能原因不想预分配最大大小但是您只有 add/remove 个元素从向量的结尾（或开头）开始，使用 std::deque 代替。 std::deque 保证指向元素的指针不会失效，只要您只 push/pop 来自 front/back;
std::list 保证永远不会使对元素的引用无效，但它引入了几个严重的性能损失（没有 O(1) 寻址，每个节点一个分配）；
如果你想完全忽略这个问题，添加一个间接层，并将指针存储到向量中，指向堆上分配的元素；更好的是，制作一个 std::shared_ptr 的向量，并始终使用它来保持对元素的引用；这显然有一个缺点，即需要为每个元素分配一次，这可能会或可能不会被接受，具体取决于您的用例。

Using vector to minimize heap allocations causes seg faults