STL容器的迭代器失效

容器的大小指的是容器中的元素数目；容器的容量指的是重新分配更多内存之前容器能够保存的元素数目。在改变大小或容量时，元素可能会移动到新的存储位置。这意味着指向元素的迭代器(以及指针或引用)可能会失效(即指向旧元素的位置)。
指向关联容器元素的迭代器只有当所指元素从容器中删除时(erase)才会失效。与之相反，指向顺序容器元素的迭代器当重新分配空间(resize()/reverse()或push_back())或指向元素在容器中移动(如在前一个位置进行erase()或者insert())也会失效。

下面我们来看一下顺序容器中erase造成迭代器失效的情况。
当我们使用erase从容器中删除一个元素时，会使迭代器失效(invalidate)，其执行效果并不是我们直觉感觉的那样。

string coll{"aaaabbbccaadcvc"};
for(auto pos=coll.begin();pos<coll.end();++pos){
  if(*pos=='a')
    coll.erase(pos);
}
// result: aabbbccadcvc

上面的代码看似是要删除str中所有的字符a，但是实际结果并不是，会“漏掉”部分a字符。
先来看一下SGI STL中erase的实现stl/string：

iterator erase(iterator __position) {
  // The move includes the terminating null.
  _Traits::move(__position, __position + 1, _M_finish - __position);
  destroy(_M_finish);
  --_M_finish;
  return __position;
}

会将该迭代器之后的所有元素向前移动一位，虽然我们传入的迭代器__position本身并未变化，但是它在执行过erase之后所指向的是执行之前的下一元素的位置(注意，具体行为还要依赖于STL版本的实现，这里列出的只是SGI STL的一个实现，C++11之前的实现可能不带返回值)。

Unfortunately, before C++11, it was a design decision not to return the following position, because if not needed, it costs unnecessary time.

因为执行过erase之后已经相当于__position指向了下一个迭代器(SGI的这份实现)，所以我们再在循环中对其自增就会导致跳过了一个元素的检查。(实际上对已失效的迭代器操作是未定义行为。)

Calling erase() for the element to which you are referring with pos invalidates pos as an iterator of coll. Thus, if you use pos after removing its element without any reinitialization, all bets are off. In fact, calling ++pos results in undefined behavior.

所以正确的写法为(C++11之前)：

string coll{"aaaabbbccaadcvc"};
for(auto pos=coll.begin();pos<coll.end();){
  if(*pos=='a')
	coll.erase(pos); // 执行之后相当于pos已经递增
  else{
    ++pos;
  }
}

可以在下面的链接中看几种常用容器的erase原型：

Since C++11, a solution is easy because erase() always returns the value of the following element.

即在C++11中，可以这么写：

string coll{"aaaabbbccaadcvc"};
for(auto pos=coll.begin();pos<coll.end();){
  if(*pos=='a')
	pos=coll.erase(pos); // 返回erase之后的当前迭代器
  else{
    ++pos;
  }
}

[TC++PL4]An iterator to an element of an associative container (e.g., a map) is only invalidated if the element to which it points is removed from the container (erase()d; §31.3.7). To contrast, an iterator to an element of a sequence container (e.g., a vector) is inv alidated if the elements are relocated (e.g.,by a resize(), reserve(), or push_back()) or if the element to which it points is moved within the container (e.g., by an erase() or insert() of an element with a lower index).
It is tempting to assume that reserve() improves performance, but the standard growth strategies for vector (§31.4.1.1) are so effective that performance is rarely a good reason to use reserve().Instead, see reserve() as a way of increasing the predictability of performance and for avoiding invalidation of iterators.

Vector：

Inserting or removing elements invalidates references, pointers, and iterators that refer to the follow-ing elements. An insertion that causes reallocation invalidates all references, iterators, and pointers.

Deque：

An insertion or deletion of elements might cause a reallocation. Thus, any insertion or deletion
invalidates all pointers, references, and iterators that refer to other elements of the deque. The
exception is when elements are inserted at the front or the back. In this case, references and
pointers to elements stay valid, but iterators don’t.