C++ 迭代时修改数据结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5638323/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Modifying a data structure while iterating over it
提问by user620189
What happens when you add elements to a data structure such as a vector while iterating over it. Can I not do this?
在迭代过程中将元素添加到数据结构（例如向量）时会发生什么。我不能这样做吗？
I tried this and it breaks:
我试过了，它坏了：
int main() {
vector<int> x = { 1, 2, 3 };
int j = 0;
for (auto it = x.begin(); it != x.end(); ++it) {
x.push_back(j);
j++;
cout << j << " .. ";
}
}
采纳答案by Lightness Races in Orbit
Iterators are invalidated by some operations that modify a std::vector.
某些修改 a 的操作会使迭代器失效std::vector。
Other containers have various rules about when iterators are and are not invalidated. This is a post(by yours truly) with details.
其他容器有关于迭代器何时失效和何时失效的各种规则。这是一篇包含详细信息的帖子（由您本人撰写）。
By the way, the entrypoint function main()MUSTreturn int:
顺便说一句，入口点函数main()必须返回int：
int main() { ... }
回答by Nawaz
What happens when you add elements to a data structure such as a vector while iterating over it. Can I not to this?
在迭代过程中将元素添加到数据结构（例如向量）时会发生什么。我可以不这样做吗？
The iterator would become invalid IF the vector resizes itself. So you're safe as long as the vector doesn't resize itself.
如果向量自行调整大小，则迭代器将无效。因此，只要矢量不调整自身大小，您就是安全的。
I would suggest you to avoid this.
我建议你避免这种情况。
The short explanation why resizing invalidates iterator:
调整大小使迭代器无效的简短解释：
Initially the vector has some capacity (which you can know by calling vector::capacity().), and you add elements to it, and when it becomes full, it allocates larger size of memory, copying the elements from the old memory to the newly allocated memory, and then deletes the old memory, and the problem is that iterator still points to the old memory, which has been deallocated. That is how resizing invalidates iterator.
最初向量有一定的容量（你可以通过调用vector::capacity().然后删除旧内存，问题是迭代器仍然指向已经释放的旧内存。这就是调整大小使迭代器无效的方式。
Here is simple demonstration. Just see when the capacitychanges:
这里是简单的演示。看看什么时候capacity改变：
std::vector<int> v;
for(int i = 0 ; i < 100 ; i++ )
{
std::cout <<"size = "<<v.size()<<", capacity = "<<v.capacity()<<std::endl;
v.push_back(i);
}
Partial Output:
部分输出：
size = 0, capacity = 0
size = 1, capacity = 1
size = 2, capacity = 2
size = 3, capacity = 4
size = 4, capacity = 4
size = 5, capacity = 8
size = 6, capacity = 8
size = 7, capacity = 8
size = 8, capacity = 8
size = 9, capacity = 16
size = 10, capacity = 16
See the complete output here : http://ideone.com/rQfWe
在此处查看完整输出：http: //ideone.com/rQfWe
Note:capacity()tells the maximum number of elements the vector can contain without allocating new memory, and size()tells the number of elements the vector currently containing.
注意：capacity()告诉向量在不分配新内存的情况下可以包含的最大元素数，并size()告诉向量当前包含的元素数。
回答by Luke Halliwell
It's a bad idea in general, because if the vector is resized, the iterator will become invalid (it's wrapping a pointer into the vector's memory).
通常这是一个坏主意，因为如果调整向量的大小，迭代器将变得无效（它将指针包装到向量的内存中）。
It's also not clear what your code is really trying to do. If the iterator somehow didn't become invalid (suppose it was implemented as an index), I'd expect you to have an infinite loop there - the end would never be reached because you're always adding elements.
也不清楚你的代码真正想要做什么。如果迭代器以某种方式没有变得无效（假设它是作为索引实现的），我希望你在那里有一个无限循环 - 永远不会到达终点，因为你总是在添加元素。
Assuming you want to loop over the originalelements, and add one for each, one solution would be to add the new elements to a second vector, and then concatenate that at the end:
假设您要循环遍历原始元素，并为每个元素添加一个，一种解决方案是将新元素添加到第二个向量中，然后在最后将其连接起来：
vector<int> temp;
// ...
// Inside loop, do this:
temp.push_back(j);
// ...
// After loop, do this to insert all new elements onto end of x
x.insert(x.end(), temp.begin(), temp.end());
回答by Drahakar
It's not a good idea to do it.
这样做不是一个好主意。
You could think about the case where your vector would need to be resized after a push_back. It would then need to be moved to a bigger memory spot and your iterators would now be invalid.
您可以考虑在 push_back 后需要调整矢量大小的情况。然后需要将其移动到更大的内存位置，并且您的迭代器现在将无效。
回答by Xoanon
While you used vector as an example, there are other stl containers which are able to have elements pushed-back without invalidating iterators. Pushing back an element into a std::list doesn't require any re-allocation of existing elements as they aren't stored contiguously (lists instead comprise of nodes linked together by pointers to the next node), therefore iterators remain valid as the node they internally point to still resides at the same address.
虽然您使用 vector 作为示例，但还有其他 stl 容器能够在不使迭代器无效的情况下将元素推回。将元素推回 std::list 不需要对现有元素进行任何重新分配，因为它们不是连续存储的（列表而是由通过指向下一个节点的指针链接在一起的节点组成），因此迭代器仍然有效它们内部指向的节点仍然位于相同的地址。
回答by dmjalund
if you need to do it this way, you can reservethe maximum number of records you could add. this will stop the vector from needing to resize, and this should prevent crashes
如果您需要这样做，您可以reserve添加最大数量的记录。这将阻止向量需要调整大小，这应该可以防止崩溃
