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

问题描述

之前有关于此问题的几个问题;我的理解是，调用 std :: vector :: erase 将只会使位于之后的已擦除元素的迭代器无效。但是，在擦除一个元素之后，该位置的迭代器仍然有效（当然，在擦除之后它不指向 end（））

我对于如何实现向量的理解似乎暗示迭代器是绝对可用的，但我不完全确定是否可能导致未定义的行为。 p>

作为我所说的一个例子，下面的代码从向量中删除所有的奇整数。此代码是否会导致未定义的行为？

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

代码在我的机器上运行良好，但这不能说服我它是有效的。

解决方案

p>

否;在传递给 erase 的迭代器中或之后的所有迭代器都将无效。

但是， erase 返回一个新的迭代器，它指向被擦除的元素之后的元素（如果没有这样的元素，则返回结束）。您可以使用此迭代器恢复迭代。

---

请注意，删除奇数元素的特定方法效率很低：你删除一个元素，所有元素必须在向量中向左移动一个位置（这是O（n ² ））。您可以使用 erase-remove成语（O（n ））。您可以创建 is_odd 谓词：

  bool is_odd {return（x％2）== 1; } 
  

然后可以传递给 remove_if ：

  vec.erase（std :: remove_if（vec.begin（），vec.end（），is_odd），vec 。结束（））; 
  

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

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

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.

---

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

Then this can be passed to remove_if:

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

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