C++:指针向量在push_back()之后失去引用

Question

在我的代码中,a有一个Node对象的全局向量和一个Node指针的局部向量:

#include<cstdio>
#include<cstdlib>
#include<vector>

using namespace std;

class Node {
    int n;

public:
    Node(int i) : n(i);
    int getN() { return n; }
};

vector<Node> v;

int main() {
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

我将一个节点对象插入到全局向量中,并将该对象的指针插入到本地向量中.我上面代码的输出是:

first node id : 1

但是,如果我将主要功能更改为:

int main()
{
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    v.push_back(Node(2));
    p.push_back(&v[1]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

代码打印垃圾值:

first node id : 32390176

我无法弄清楚这个问题.vector插入后数据结构是否会更改每个对象的引用？我怎样才能解决这个问题 ？

Answer 1

"插入后向量是否会更改引用？"

可能,是的.一个std::vector 时添加/可重新分配其(堆)存储push_back()的附加元件,无效所有的指针:

迭代器[读取:指针]失效

(用于操作)push_back,emplace_back...如果向量改变了容量,则所有这些[即所有迭代器都无效].如果没有,只有end().

"我怎样才能解决这个问题？"

如果向量的容量由于插入而没有改变,则上述失效规则不适用 - 因为向量不会不必要地重新分配存储.因此,如果您在示例中预先将矢量的容量设置为2(例如,with v.reserve(2)),则指针将保持有效.如果你事先不知道大小,但你可以延迟第二个向量的构造(使用指针),你不必保留,你只需要插入最后一个元素后的大小.

然而,上述方法是非常不受推荐的.如果你要使向量保持不变 - 至少在你将构造和使用第二个向量的函数范围内 - 你将有一个强大的非重新分配保证.或者,如果您可以提前确定大小,则可以使用a std::array,并且将指针用于该容器的存储更为合适:

迭代器失效

通常,数组的迭代器在数组的整个生命周期中永远不会失效.

您也可以考虑将索引存储到向量中(尽管也存在向量可能缩小,索引无效,或者您可能在中间插入元素等).

无论如何,我怀疑你可能实际上并不想做任何这样的事情,即它似乎是一个不太好的解决方案,可以用一个完全不同的方法处理问题.

_{PS - 如果向量具有自定义分配器,那么我写的所有内容都可能无关紧要.}

Answer 2

是的，push_back()如果必须重新分配，向量上的 a 会使对该向量中元素的所有引用（和指针）无效。有多种方法可以解决这个问题。如果您知道向量将具有特定数量的节点，则可以使用reserve()。在您的示例中，您可以保留两个元素：

int main()
{
    v.reserve(2);
    .
    .
    .
}

这将确保向量已预先分配足够的存储空间，以便不需要重新分配。

如果您事先不知道尺寸，那么您就必须改变您的方法。您可以使用 astd::deque而不是 a std::vector，因为std::deque使用 时不会使引用无效push_back()。您可以存储索引而不是指针。或者，您可能需要在创建指针之前将所有节点推入向量中。

int main()
{
    v.push_back(Node(1));
    v.push_back(Node(2));

    vector<Node*> p;
    p.push_back(&v[0]);
    p.push_back(&v[1]);

    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

Answer 3

您正在做的是向量的未定义行为，p因为向量v可以更改其对象的存储位置。

Astd::vector的内存是连续的，因此在多次之后，它可能push_backs必须分配新的块内存并将其内容复制到新块。这将使所有碰巧指向旧内存位置的指针无效。