關于STL的erase()陷阱-迭代器失效問題的總結

2020-01-26 14:20:00

字體：大中小

來源：轉載

供稿：網友

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

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

1.list,set,map容器

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

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 錯誤寫法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 錯誤寫法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方法的返回值來獲取下一個元素的位置

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

錯誤使用方法1：在調用erase方法之后使用“++”來獲取下一個元素的位置，由于在調用erase方法以后，該元素的位置已經

被刪除，如果在根據這個舊的位置來獲取下一個位置，則會出現異常。

錯誤使用方法2：同上。

2. vector,deque容器

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

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”的辦法來遍歷刪除。原因請參考Effective STL條款9。摘錄到下面：

1) 對于關聯容器(如map, set, multimap,multiset)，刪除當前的iterator，僅僅會使當前的iterator失效，只要在erase時，遞增當前iterator即可。這是因為map之類的容器，使用了紅黑樹來實現，插入、刪除一個結點不會對其他結點造成影響。

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

因為iter傳給erase方法的是一個副本，iter++會指向下一個元素。

2) 對于序列式容器(如vector,deque)，刪除當前的iterator會使后面所有元素的iterator都失效。這是因為vetor,deque使用了連續分配的內存，刪除一個元素導致后面所有的元素會向前移動一個位置。還好erase方法可以返回下一個有效的iterator。

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

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

3.迭代器失效的情況

3.1 vector

內部數據結構：數組。

隨機訪問每個元素，所需要的時間為常量。

在末尾增加或刪除元素所需時間與元素數目無關，在中間或開頭增加或刪除元素所需時間隨元素數目呈線性變化。

可動態增加或減少元素，內存管理自動完成，但程序員可以使用reserve()成員函數來管理內存。

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

3.2 deque

內部數據結構：數組。

隨機訪問每個元素，所需要的時間為常量。

在開頭和末尾增加元素所需時間與元素數目無關，在中間增加或刪除元素所需時間隨元素數目呈線性變化。

可動態增加或減少元素，內存管理自動完成，不提供用于內存管理的成員函數。

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

3.3 list

內部數據結構：雙向環狀鏈表。

不能隨機訪問一個元素。

可雙向遍歷。

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

可動態增加或減少元素，內存管理自動完成。