下面材料整理自Internet&著作。

STL中的容器按存儲(chǔ)方式分為兩類，一類是按以數(shù)組形式存儲(chǔ)的容器（如：vector 、deque)；另一類是以不連續(xù)的節(jié)點(diǎn)形式存儲(chǔ)的容器（如：list、set、map）。在使用erase方法來刪除元素時(shí)，需要注意一些問題。

1.list,set,map容器

在使用 list、set 或 map遍歷刪除某些元素時(shí)可以這樣使用：

1.1 正確寫法1

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
      itList = List.erase( itList);
    }
    else
      itList++;
}

1.2 正確寫法2

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
     List.erase( itList++);
   }
   else
     itList++;
}

1.3 錯(cuò)誤寫法1

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); itList++)
{
  if( WillDelete( *itList) )
  {
     List.erase( itList);
  }
}

1.4 錯(cuò)誤寫法2

std::list< int> List;
std::list< int>::iterator itList;
for( itList = List.begin(); itList != List.end(); )
{
   if( WillDelete( *itList) )
   {
     itList = List.erase( ++itList);
   }
   else
     itList++;
}

1.5 分析

正確使用方法1：通過erase方法的返回值來獲取下一個(gè)元素的位置

正確使用方法2：在調(diào)用erase方法之前先使用 “++”來獲取下一個(gè)元素的位置

錯(cuò)誤使用方法1：在調(diào)用erase方法之后使用“++”來獲取下一個(gè)元素的位置，由于在調(diào)用erase方法以后，該元素的位置已經(jīng)

被刪除，如果在根據(jù)這個(gè)舊的位置來獲取下一個(gè)位置，則會(huì)出現(xiàn)異常。

錯(cuò)誤使用方法2：同上。

2. vector,deque容器

在使用 vector、deque遍歷刪除元素時(shí)，也可以通過erase的返回值來獲取下一個(gè)元素的位置：

2.1 正確寫法

std::vector< int> Vec;
std::vector< int>::iterator itVec;
for( itVec = Vec.begin(); itVec != Vec.end(); )
{
 if( WillDelete( *itVec) )
 {
   itVec = Vec.erase( itVec);
  }
 else
   itList++;
}

2.2 注意

注意：vector、deque 不能像上面的“正確使用方法2”的辦法來遍歷刪除。原因請(qǐng)參考Effective STL條款9。摘錄到下面：

1)  對(duì)于關(guān)聯(lián)容器(如map, set, multimap,multiset)，刪除當(dāng)前的iterator，僅僅會(huì)使當(dāng)前的iterator失效，只要在erase時(shí)，遞增當(dāng)前iterator即可。這是因?yàn)閙ap之類的容器，使用了紅黑樹來實(shí)現(xiàn)，插入、刪除一個(gè)結(jié)點(diǎn)不會(huì)對(duì)其他結(jié)點(diǎn)造成影響。

for (iter = cont.begin(); it != cont.end();)
{
(*iter)->doSomething();
if (shouldDelete(*iter))
 cont.erase(iter++);
else
 ++iter;
}

因?yàn)閕ter傳給erase方法的是一個(gè)副本，iter++會(huì)指向下一個(gè)元素。

2) 對(duì)于序列式容器(如vector,deque)，刪除當(dāng)前的iterator會(huì)使后面所有元素的iterator都失效。這是因?yàn)関etor,deque使用了連續(xù)分配的內(nèi)存，刪除一個(gè)元素導(dǎo)致后面所有的元素會(huì)向前移動(dòng)一個(gè)位置。還好erase方法可以返回下一個(gè)有效的iterator。

for (iter = cont.begin(); iter != cont.end();)
{
(*it)->doSomething();
if (shouldDelete(*iter))
 iter = cont.erase(iter); 
else
 ++iter;
}

3)對(duì)于list來說，它使用了不連續(xù)分配的內(nèi)存，并且它的erase方法也會(huì)返回下一個(gè)有效的iterator，因此上面兩種方法都可以使用。

3.迭代器失效的情況

3.1 vector

內(nèi)部數(shù)據(jù)結(jié)構(gòu)：數(shù)組。

隨機(jī)訪問每個(gè)元素，所需要的時(shí)間為常量。

在末尾增加或刪除元素所需時(shí)間與元素?cái)?shù)目無關(guān)，在中間或開頭增加或刪除元素所需時(shí)間隨元素?cái)?shù)目呈線性變化。

可動(dòng)態(tài)增加或減少元素，內(nèi)存管理自動(dòng)完成，但程序員可以使用reserve()成員函數(shù)來管理內(nèi)存。

vector的迭代器在內(nèi)存重新分配時(shí)將失效（它所指向的元素在該操作的前后不再相同）。當(dāng)把超過capacity()-size()個(gè)元素插入vector中時(shí)，內(nèi)存會(huì)重新分配，所有的迭代器都將失效；否則，指向當(dāng)前元素以后的任何元素的迭代器都將失效。當(dāng)刪除元素時(shí)，指向被刪除元素以后的任何元素的迭代器都將失效。

3.2 deque

內(nèi)部數(shù)據(jù)結(jié)構(gòu)：數(shù)組。

隨機(jī)訪問每個(gè)元素，所需要的時(shí)間為常量。

在開頭和末尾增加元素所需時(shí)間與元素?cái)?shù)目無關(guān)，在中間增加或刪除元素所需時(shí)間隨元素?cái)?shù)目呈線性變化。

可動(dòng)態(tài)增加或減少元素，內(nèi)存管理自動(dòng)完成，不提供用于內(nèi)存管理的成員函數(shù)。

增加任何元素都將使deque的迭代器失效。在deque的中間刪除元素將使迭代器失效。在deque的頭或尾刪除元素時(shí)，只有指向該元素的迭代器失效。

3.3 list

內(nèi)部數(shù)據(jù)結(jié)構(gòu)：雙向環(huán)狀鏈表。

不能隨機(jī)訪問一個(gè)元素。

可雙向遍歷。

在開頭、末尾和中間任何地方增加或刪除元素所需時(shí)間都為常量。

可動(dòng)態(tài)增加或減少元素，內(nèi)存管理自動(dòng)完成。

增加任何元素都不會(huì)使迭代器失效。刪除元素時(shí)，除了指向當(dāng)前被刪除元素的迭代器外，其它迭代器都不會(huì)失效。

3.4 slist

內(nèi)部數(shù)據(jù)結(jié)構(gòu)：?jiǎn)蜗蜴湵怼?/p>

不可雙向遍歷，只能從前到后地遍歷。

其它的特性同list相似。

3.5 stack

適配器，它可以將任意類型的序列容器轉(zhuǎn)換為一個(gè)堆棧，一般使用deque作為支持的序列容器。

元素只能后進(jìn)先出（LIFO）。

不能遍歷整個(gè)stack。

3.6 queue

適配器，它可以將任意類型的序列容器轉(zhuǎn)換為一個(gè)隊(duì)列，一般使用deque作為支持的序列容器。

元素只能先進(jìn)先出（FIFO）。

不能遍歷整個(gè)queue。

3.7 priority_queue

適配器，它可以將任意類型的序列容器轉(zhuǎn)換為一個(gè)優(yōu)先級(jí)隊(duì)列，一般使用vector作為底層存儲(chǔ)方式。

只能訪問第一個(gè)元素，不能遍歷整個(gè)priority_queue。

第一個(gè)元素始終是優(yōu)先級(jí)最高的一個(gè)元素。

3.8 set

鍵和值相等。

鍵唯一。

元素默認(rèn)按升序排列。

如果迭代器所指向的元素被刪除，則該迭代器失效。其它任何增加、刪除元素的操作都不會(huì)使迭代器失效。

3.9 multiset

鍵可以不唯一。

其它特點(diǎn)與set相同。

3.10 hash_set

與set相比較，它里面的元素不一定是經(jīng)過排序的，而是按照所用的hash函數(shù)分派的，它能提供更快的搜索速度（當(dāng)然跟hash函數(shù)有關(guān)）。

其它特點(diǎn)與set相同。

3.11 hash_multiset

鍵可以不唯一。

其它特點(diǎn)與hash_set相同。

3.12 map

鍵唯一。

元素默認(rèn)按鍵的升序排列。

如果迭代器所指向的元素被刪除，則該迭代器失效。其它任何增加、刪除元素的操作都不會(huì)使迭代器失效。

3.13 multimap

鍵可以不唯一。

其它特點(diǎn)與map相同。

3.14 hash_map

與map相比較，它里面的元素不一定是按鍵值排序的，而是按照所用的hash函數(shù)分派的，它能提供更快的搜索速度（當(dāng)然也跟hash函數(shù)有關(guān)）。

其它特點(diǎn)與map相同。

3.15 hash_multimap

鍵可以不唯一。

其它特點(diǎn)與hash_map相同。

以上就是小編為大家?guī)淼年P(guān)于STL的erase()陷阱-迭代器失效問題的總結(jié)全部?jī)?nèi)容了，希望大家多多支持腳本之家~

最新評(píng)論