erase 迭代器失效,stl 迭代器失效

  erase 迭代器失效,stl 迭代器失效

  以下资料是从网络作品中整理出来的。

  STL中的容器按照存储方式可以分为两种,一种是以数组形式存储的容器(比如vector和Deque);另一种是存储在不连续节点中的容器(如list、set、map)。使用erase方法删除元素时,有一些问题需要注意。

  当使用list、set或map遍历来删除一些元素时,可以这样使用:

  正确使用方法1

  STD:List int List;

  STD:list int:iterator it list;

  for(it list=list . begin();itList!=list . end();)

  {

  if(WillDelete(*itList))

  {

  it list=list . erase(it list);

  }

  其他

  itList

  }

  或者

  正确使用方法2

  STD:List int List;

  STD:list int:iterator it list;

  for(it list=list . begin();itList!=list . end();)

  {

  if(WillDelete(*itList))

  {

  list . erase(it list);

  }

  其他

  itList

  }

  这里有两种错误的使用方法:

  错误方法1

  STD:List int List;

  STD:list int:iterator it list;

  for(it list=list . begin();itList!=list . end();itList)

  {

  if(WillDelete(*itList))

  {

  list . erase(it list);

  }

  }

  或者

  错误方法2

  STD:List int List;

  STD:list int:iterator it list;

  for(it list=list . begin();itList!=list . end();)

  {

  if(WillDelete(*itList))

  {

  it list=list . erase(it list);

  }

  其他

  itList

  }

  正确方法1:通过erase方法的返回值获取下一个元素的位置。

  正确方法2:在调用erase方法之前,使用" "获取下一个元素的位置。

  错误方法1:调用erase方法后,使用“”获取下一个元素的位置。由于这个元素的位置在调用erase方法后已经被删除,如果根据这个旧位置获取下一个位置,就会出现异常。

  错误方法二:同上。

  这里的“”运算符正好与我们通常的理解相反。erase( itList)是先获取下一个元素的位置,然后删除;Erase( itList)是删除后下一个元素的位置。

  当使用vector和deque遍历被删除的元素时,也可以通过erase的返回值获得下一个元素的位置:

  正确使用方法

  STD:vector int Vec;

  STD:vector int:iteratoritVec;

  for(it vec=vec . begin();itVec!=vec . end();)

  {

  if(WillDelete(*itVec))

  {

  it vec=vec . erase(it vec);

  }

  其他

  itList

  }

  注意:vector和deque不能像上面“正确使用方法2”的方法那样遍历和删除。原因请参考有效STL第9条。摘录如下:

  1.对于关联容器(如map、set、multimap、multiset),删除当前迭代器只会使当前迭代器失效,只要当前迭代器在擦除时递增即可。这是因为map等容器是用红黑树实现的,插入或删除一个节点不会影响到其他节点。

  for(ITER=cont . begin();它!=cont . end();)

  {

  (* ITER)-do something();

  if(shouldDelete(*iter))

  cont . erase(ITER);

  其他

  iter

  }

  因为iter传递了copy to erase方法,所以iter会指向下一个元素。

  2.对于顺序容器(比如vector,deque),删除当前迭代器会使后面所有元素的迭代器失效。这是因为vetor,deque使用连续分配的内存,删除一个元素会导致后面所有的元素向前移动一个位置。幸运的是,erase方法可以返回下一个有效的迭代器。

  for(ITER=cont . begin();iter!=cont . end();)

  {

  (* it)-do something();

  if(shouldDelete(*iter))

  ITER=cont . erase(ITER);

  其他

  iter

  }

  3.对于list,它使用的是不连续分配的内存,它的erase方法也会返回下一个有效的迭代器,所以以上两种方法都可以使用。

  -

  迭代器失败:

  (1)矢量

  内部数据结构:数组。

  对每个元素的随机访问需要恒定的时间。

  在末尾添加或删除元素所需的时间与元素个数无关,而在中间或开头添加或删除元素所需的时间随元素个数线性变化。

  元素可以动态增减,内存管理自动完成,但是程序员可以使用reserve()成员函数来管理内存。

  vector的迭代器在内存重新分配时会失效(它所指向的元素在这次操作前后不再相同)。当超过capacity()-size()的元素被插入到vector中时,内存将被重新分配,所有迭代器都将失败;否则,指向当前元素之后任何元素的迭代器都将无效。当删除一个元素时,指向被删除元素后任何元素的迭代器都将失效。

  (2)得缺

  内部数据结构:数组。

  对每个元素的随机访问需要恒定的时间。

  开头和结尾添加元素所需时间与元素个数无关,中间添加或删除元素所需时间随元素个数线性变化。

  可以动态添加或减少元素,自动完成内存管理,不提供内存管理的成员函数。

  添加任何元素都会使deque的迭代器失效。删除deque中间的元素会使迭代器失效。当一个元素在deque的头部或尾部被删除时,只有指向该元素的迭代器是无效的。

  (3)列表

  内部数据结构:双向循环链表。

  您不能随机访问元素。

  它可以双向穿越。

  在开始、结束和中间的任何地方添加或删除元素所需的时间是恒定的。

  可以动态地添加或减少元素,并且自动完成内存管理。

  添加任何元素都不会使迭代器失效。删除元素时,除了指向当前删除元素的迭代器外,所有迭代器都不会失败。

  (4)列表

  内部数据结构:单向链表。

  不能双向穿越;只能从前向后遍历。

  的其他功能与列表类似。

  (5)堆栈

  适配器,可以将任何类型的序列容器转换成堆栈。通常,deque被用作支持的序列容器。

  要素只能是后进先出(LIFO)。

  您不能遍历整个堆栈。

  (6)排队

  适配器,它可以将任何类型的序列容器转换成队列。通常,deque被用作支持的序列容器。

  元素只能先进先出(FIFO)。

  您不能遍历整个队列。

  (7)优先级_队列

  Adapter可以将任何类型的序列容器转换为优先级队列,一般使用vector作为底层存储模式。

  只能访问第一个元素,但不能遍历整个priority_queue。

  第一个元素总是具有最高优先级的元素。

  (8)设置

  键等于值。

  唯一键。

  默认情况下,元素按升序排序。

  如果迭代器指向的元素被删除,迭代器将失效。任何其他添加或删除元素的操作都不会使迭代器失效。

  (9)多重集合

  键可能不是唯一的。

  其他功能与set相同。

  (10)哈希集

  与set相比,它里面的元素不一定是排序的,而是根据使用的哈希函数进行赋值,可以提供更快的搜索速度(当然与哈希函数有关)。

  其他功能与set相同。

  (11)哈希多重集

  键可能不是唯一的。

  其他特性与hash_set相同。

  (十二)地图

  唯一键。

  默认键的升序。

  如果迭代器指向的元素被删除,迭代器将失效。任何其他添加或删除元素的操作都不会使迭代器失效。

  (13)多地图

  键可能不是唯一的。

  其他功能与地图相同。

  (14)哈希映射

  和map相比,它里面的元素不一定按照键值排序,而是按照使用的哈希函数进行赋值,可以提供更快的搜索速度(当然也和哈希函数有关)。

  其他功能与地图相同。

  (15)哈希_多重映射

  键可能不是唯一的。

  其他特性与hash_map相同。

erase 迭代器失效,stl 迭代器失效