在向量中插入元素会损坏指向该向量的指针吗? [英] Does insertion of elements in a vector damages a pointer to the vector?

问题描述

在一个模拟逻辑门的程序中，我从使用数组切换了

In a program to simulate logic gates I switched from using arrays

node N[1000];

到向量

vector<node> N;

在使用向量之前，我的程序确实运行良好，但是现在它打印了错误的结果，所以我尝试调试，发现该错误发生在这里:

And my program did work perfectly before using vectors but now it prints wrong results, so I tried debugging and I found out that the bug happens here:

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].

When calling FindNode for the 1st time, the 1st pointer inp1 points to the right place which is &N[0].

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

When calling FindNode for the second time the 1st pointer inp1 points to rubbish and the second pointer inp2 points to the right place &N[1].

当第三次调用FindNode时，第一指针和第二指针(inp1，inp2)都指向垃圾！第三个指针指向正确的位置.

When calling FindNode for the 3rd time the both the 1st and 2nd pointers (inp1, inp2) point to rubbish! And 3rd pointer out points to the right place.

为什么会这样?
将向量插入向量时，向量如何工作?应该使用哪种指针指向向量项目?

推荐答案

一些事情.

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

First, as far as I can tell NNodes is just tracking the size. But you have std::vector::size() for that. You then use it to get the last inserted element, but you can just use std::vector::back() for that: return &N.back();.

当您的参数可能应该通过const-reference:const string& h传递时，也通过值传递.这样可以避免不必要的复制，通常，您应该通过const-reference而不是按值传递内容.

Also your parameter is being passed by value, when it should probably be passed by const-reference: const string& h. This avoids unnecessary copies, and in general* you should pass things by const-reference instead of by-value.

这很糟糕:

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

node可能应该具有一个采用const string&并在初始化期间设置名称的构造函数.这样一来，您将永远无法拥有一个没有名称的节点，如:

node should probably have a constructor that takes a const string& and sets the name during initialization. That way you can never have a node without a name, as in:

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

或更简洁:

N.push_back(node(h));

好多了.

第二，是的，vector可以使指向元素的指针无效；即，每当需要增加向量的容量时.如果可以，请提前reserve()容量以避免重新分配.对于您而言，您不能，因此可以选择两条不同的路线.

Second, yes, vector can invalidate pointers to elements; namely, whenever the capacity of the vector needs to be increased. If you can, reserve() the capacity up front to avoid re-allocations. In your case you cannot, so you can go two different routes.

第一条路线是

The first route is a level of indirection. Instead of pointing directly at things, get their index into the array. Note that while their address may change, their location within the vector will not. You would have Simulator::FindNode return a size_t, and return N.size() - 1. Add a member like node& GetNode(size_t index), which just does return N[index]; (will error checking if you wish). Now whenever you need a member, hand the index to that member to GetNode and you'll get a reference to that node back.

另一种方法是更改​​容器.例如，您可以使用deque.它没有连续的存储，但是很像vector. push_back和pop_back仍为O(1)，并且仍具有良好的缓存一致性. (顺便说一下，deque也在O(1)时间内将连续存储换为push_front和pop_front的能力)

The other route is to change your container. You can use a deque, for example. This does not have contiguous storage, but it's much like vector. push_back and pop_back are still O(1), and it still has good cache-coherence. (And by the way, deque trades contiguous storage for the ability to push_front and pop_front in O(1) time as well)

重要的是，deque不会在从任一端进行的推入或弹出操作期间使指针无效.它通过某种矢量列表混合工作，您可以在其中获得链接在一起的元素的存储块.将您的基础存储更改为deque(不要在中间放置任何东西)，您可以指出一切.

The important thing is that deque will not invalidate pointers during a push or pop operation from either end. It works by a sort of vector-list hybrid, where you get chunks of storage for elements linked together. Change your underlying storage to deque (and don't take or put anything in the middle), and you can point to things just fine.

但是，据我所知，您有一张极其低效的地图.您正在将名称映射到节点.您可能应该只使用std::map，它具有您要重新创建的确切接口.您甚至可以指向地图中的任何元素，而这些元素永远不会使事物无效.

However, from what I can tell you have a terribly inefficient map. You're mapping names to nodes. You should probably just use std::map, which has the exact interface you're trying to recreate. You can even point to any element in a map, which never invalidates things.

_{*规则是，除非类型是原始类型(如int，double等内置类型)，类型大小小于sizeof(void*)或需要使用，否则按const引用传递仍然是它的副本.}

_{*The rule is, pass by const-reference unless the type is primitive (built-in like int, double, etc.), if the types size is less than sizeof(void*), or if you are going to need a copy of it anyway.}

也就是说，不要这样做:

That is, don't do this:

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
{
}

这篇关于在向量中插入元素会损坏指向该向量的指针吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！