std::vector 迭代器失效 [英] std::vector iterator invalidation

问题描述

之前有一些关于这个问题的问题；我的理解是调用 std::vector::erase 只会使位于被擦除元素之后的迭代器无效.但是，擦除元素后，该位置的迭代器是否仍然有效(当然，前提是擦除后它不指向 end())?

There have been a few questions regarding this issue before; my understanding is that calling std::vector::erase will only invalidate iterators which are at a position after the erased element. However, after erasing an element, is the iterator at that position still valid (provided, of course, that it doesn't point to end() after the erase)?

我对如何实现向量的理解似乎表明迭代器绝对可用，但我不完全确定它是否会导致未定义的行为.

My understanding of how a vector would be implemented seems to suggest that the iterator is definitely usable, but I'm not entirely sure if it could lead to undefined behavior.

作为我正在谈论的一个例子，以下代码从向量中删除所有奇数.这段代码会导致未定义的行为吗?

As an example of what I'm talking about, the following code removes all odd integers from a vector. Does this code cause undefined behavior?

typedef std::vector<int> vectype;
vectype vec;

for (int i = 0; i < 100; ++i) vec.push_back(i);

vectype::iterator it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 1) vec.erase(it);
    else ++it;
}

代码在我的机器上运行良好，但这并不能让我相信它是有效的.

The code runs fine on my machine, but that doesn't convince me that it's valid.

推荐答案

擦除一个元素后，那个位置的迭代器是否仍然有效

after erasing an element, is the iterator at that position still valid

没有；传递给 erase 的迭代器中或之后的所有迭代器都无效.

No; all of the iterators at or after the iterator(s) passed to erase are invalidated.

然而，erase 返回一个新的迭代器，该迭代器立即指向被擦除元素之后的元素(如果没有这样的元素，则指向末尾).您可以使用此迭代器来恢复迭代.

However, erase returns a new iterator that points to the element immediately after the element(s) that were erased (or to the end if there is no such element). You can use this iterator to resume iteration.

请注意，这种移除奇数元素的特殊方法非常低效:每次移除一个元素时，它之后的所有元素都必须向向量左侧移动一个位置(这是 O(n²)).您可以使用 erase-remove idiom (O(n)).您可以创建一个 is_odd 谓词:

Note that this particular method of removing odd elements is quite inefficient: each time you remove an element, all of the elements after it have to be moved one position to the left in the vector (this is O(n²)). You can accomplish this task much more efficiently using the erase-remove idiom (O(n)). You can create an is_odd predicate:

bool is_odd(int x) { return (x % 2) == 1; }

然后这可以传递给remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());

这篇关于std::vector 迭代器失效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！