在向量中插入元素会损坏指向向量的指针吗？

Question

在模拟逻辑门的程序中,我从使用数组切换

node N[1000];

到矢量

vector<node> N;

我的程序在使用向量之前确实工作正常,但现在它打印出错误的结果,所以我尝试调试,我发现错误发生在这里:

node* Simulator::FindNode(string h)
{
    int i;
    for(i = 0; i < NNodes; i++)
    {
        if (N[i].getname() == h)
        {
            return &N[i];
        }
    }

    node n ;
    N.push_back(n);
    N[NNodes].setname(h);
    NNodes++;
    return &N[NNodes-1]; //why?because of NNodes++  
}

// ...

node* inp1;
node* inp2;
node* out;
string NodeName;

inp_file >> NodeName;
inp1 = FindNode(NodeName);
s1 = inp1;

inp_file >> NodeName;
inp2 = FindNode(NodeName); //inp1 is destroyed here 

inp_file >> NodeName;
out = FindNode(NodeName); //inp2 and inp1 are destroyed here 

当FindNode第一次调用时,第一个指针inp1指向正确的位置&N[0].

当FindNode第二次调用时,第一个指针inp1指向垃圾,第二个指针inp2指向正确的位置&N[1].

当FindNode第3次呼叫时,第1和第2指针(inp1,inp2)都指向垃圾!并且第3个指针指向正确的位置.

为什么会这样？
当我向它们插入项目时,矢量如何工作？我应该使用哪种指针指向矢量项目？

Answer 1

是的,它可以重新分配整个缓冲区,使所有指向旧位置的指针无效.

你可以通过预分配来限制这个,但这只是一个性能提升.更好的方法是使用索引而不是原始指针.

Answer 2

一些东西.

首先,据我所知NNodes,只是跟踪大小.但是你有std::vector::size()这个.然后使用它来获取最后插入的元素,但您可以使用std::vector::back()它:return &N.back();.

当你的参数可能通过const-reference传递时,你的参数也是按值传递的:const string& h.这样可以避免不必要的副本,一般情况下,你应该通过const-reference而不是by-value传递东西.

这很糟糕:

node n;
N.push_back(n);
N[NNodes].setname(h);

node应该有一个构造函数,它const string&在初始化期间接受并设置名称.这样你就永远不会有一个没有名字的节点,如:

node n(h);
N.push_back(n);

或者更简洁:

N.push_back(node(h));

好多了.

第二,是的,vector可以使指向元素的指针无效; 即,每当需要增加矢量的容量时.如果可以的话,reserve()预先考虑容量以避免重新分配.在你的情况下,你不能,所以你可以走两条不同的路线.

第一条路线是间接层.而不是直接指向事物,将其索引放入数组中.请注意,虽然它们的地址可能会更改,但它们在矢量中的位置却不会.你会Simulator::FindNode回来的size_t,然后回来N.size() - 1.添加一个成员一样node& GetNode(size_t index),它只是做return N[index];(如果你愿意将错误检查).现在,只要您需要成员,请将索引传递给该成员,GetNode然后您将获得对该节点的引用.

另一条路线是更换容器.deque例如,您可以使用a .这没有连续的存储,但它很像vector.push_back并且pop_back仍然是O(1),它仍然具有良好的缓存一致性.(顺便说一句,deque交易连续存储的能力push_front和pop_front在O(1)时间内)

重要的是,deque会不会从两端推或弹出操作过程中无效的指针.它通过一种矢量列表混合工作,您可以获得链接在一起的元素的存储块.将您的底层存储更改为deque(并且不要将任何东西放在中间),您可以指向正常的东西.

但是,据我所知,你有一张非常低效的地图.您将名称映射到节点.您应该只使用std::map,它具有您尝试重新创建的确切界面.您甚至可以指向地图中的任何元素,这些元素永远不会使事物无效.

_{*该规则,以const引用传递,除非该类型是基本类型(内置样int,double等等),如果该类型的大小小于sizeof(void*),或者如果你打算无论如何需要它的一个副本.}

也就是说,不要这样做:

void foo(const std::string& s)
{
    std::string ss(s); // make a copy, use copy
}

但这样做:

void foo(std::string s) // make a copy, use copy
{
}