ZY's WordPress

以前用STL时，曾用过vector::erase()来删除vector中的特定元素，今天在网上搜了一下发现原来有很多人在讨论vector::erase()方法的使用，最初的问题来源于：当使用循环语句，从vector中删除所有满足一定条件的元素时，如果已完成删除一个元素，则对iterator再次使用就会引起错误。

其实这个错误，是因为不理解vector、iterator、erase()的语义而望文生义地编程造成的：erase()的参数iterator，在erase()返回后（即已完成删除操作），就已经废掉了，再对iterator使用当然会引起错误。这个简单的问题网上讨论的都一致，我把几个规范性的写法记录下，已备后用。

vector::erase()参考

接口规格参考（Reference），是解决所有这种使用语义问题的源泉，下面列举几个vector::erase()参考地址：

• cplusplus.com上的vector::erase()参考
• cppreference.com上的vector::erase()参考
• MSDN上的vector::erase()参考
• Microsoft KB上的vector::erase()使用例子

从上面的参考中还可以知道：

1. vector::erase()的算法效率：是被删除元素的个数，加上被删除的最后一个元素后剩余的元素个数，这个总数的线性函数。

   Linear on the number of elements erased (destructors) plus the number of elements after the last element deleted (moving).

2. vector::erase()没有list或dqueue中删除元素的效率高。

3. vecotr::iterator是随机访问迭代器（Random Access Iterator），因此这样的写法是可以的：vec.begin() + 5，表示begin()后的第5个元素，也是序列中的第6个元素。

常用的vector::erase()写法

下面列举几种常用的vector::erase()写法，假设if_remove()是判断元素是否需要被删除的谓词逻辑。

• 我喜欢的写法

  for ( it = vec.begin(); it != vec.end(); )
  {
  	if ( if_remove(it) )
  	{
  		it = vec.erase(it);
  		continue;
  	}
  	// 对不删除的元素的操作
  	...
  	it++;
  }
  

• 常用写法

  for ( it = vec.begin(); it != vec.end(); )
  {
  	if ( if_remove(it) )
  	{
  		it = vec.erase(it);
  	}
  	else
  	{
  		// 对不删除的元素的操作
  		...
  		it++;
  	}
  }
  

• find()通用算法写法

  vector<type>::iterator it = find(vec.begin(), vec.end(), type_val);
  
  if ( it != vec.end() )
  {
  	vec.erase(it);
  }
  

  这种方法适用于type上有定义/重载的operator==()，而且功能上只删除一个type对象为type_val值的元素：这相对于一开始说的有问题的erase()写法，没有什么功能上的改进，因为这种写法的意思是：成功删除第一个找到的元素后就break，不再继续查找下一个满足条件的元素。

  如果要从vector中删除所有匹配type_val值的元素，可以使用下面写法：

  vector<type>::iterator it = find(vec.begin(), vec.end(), type_val);
  
  while ( it != vec.end() )
  {
  	it = vec.erase(it);
  	it = find(it, vec.end(), type_val);
  }