STL序列式容器中刪除元素的方法和陷阱一 收藏
在 STL （標準模板庫）中經(jīng)常會(huì )碰到要刪除容器中部分元素的情況，本人在編程中就經(jīng)常編寫(xiě)這方面的代碼，在編碼和測試過(guò)程中發(fā)現在 STL 中刪除容器有很多陷阱，網(wǎng)上也有不少網(wǎng)友提到如何在 STL 中安全刪除元素這些問(wèn)題。本文將討論編程過(guò)程中最經(jīng)常使用的兩個(gè)序列式容器 vector 、 list 中安全刪除元素的方法和應該注意的問(wèn)題， 其它如 queue 、 stack 等配接器容器（ container adapter ），由于它們有專(zhuān)屬的操作行為，沒(méi)有迭代器（ iterator ），不能采用本文介紹的刪除方法，至于 deque ，它與 vector 的刪除方法一樣。 STL 容器功能強大， but no siliver bullet ，如果你使用不當，也將讓你吃盡苦頭。
1 ．手工編寫(xiě) for 循環(huán)代碼刪除 STL 序列式容器中元素的方法
例如，你能看出以下代碼有什么問(wèn)題？
例 1 ：
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化 vector 容器
for (i = 0; i < 5; i++ ) {
vectInt.push_back( i );
}
// 以下代碼是要刪除所有值為 4 的元素
vector<int>::iterator itVect = vectInt.begin();
for ( ; itVect != vectInt.end(); ++itVect ) {
if ( *itVect == 4 ) {
vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
}
例 2 ：
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化 vector 容器
for ( i = 0; i < 5; i++ ) {
vectInt.push_back( i );
if ( 3 == i ) {
// 使 3 的元素有兩個(gè)，并且相臨。這非常關(guān)鍵，否則將發(fā)現不了 bug 。
// 具體解釋見(jiàn)下。
vectInt.push_back( i );
}
}
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止 for 多重計算
// 以下代碼是要刪除所有值為 3 的元素
for ( ; itVect != itVectEnd; ++itVect ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
例 3 ：
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt( 5 );
int i;
vectInt[ 0 ] = 0;
vectInt[ 1 ] = 1;
vectInt[ 2 ] = 2;
vectInt[ 3 ] = 3;
vectInt[ 4 ] = 4; // 替換為 vectInt[ 4 ] = 3; 試試
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止 for 多重計算
// 以下代碼是要刪除所有值為 3 的元素
for ( ; itVect != itVectEnd; ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
else {
++itVect;
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
}
分析：
這里最重要的是要理解 erase 成員函數，它刪除了 itVect 迭代器指向的元素，并且返回要被刪除的 itVect 之后的迭代器， 迭代器相當于一個(gè)智能指針，指向容器中的元素，現在刪除了這個(gè)元素，將導致內存重新分配，相應指向這個(gè)元素的迭代器之后的迭代器 就失效了，但 erase 成員函數返回要被刪除的 itVect 之后的迭代器 。
例 1 將導致程序未定義的錯誤，在 windows 中即是訪(fǎng)問(wèn)非法內存，程序當掉。因為 vectInt.erase( itVect ); 調用后 itVect 之后的迭代器已無(wú)效了，所以當執行 ++itVect 后， *itVect 訪(fǎng)問(wèn)了非法內存。例 1 也是初學(xué)者最容易犯的錯誤，這個(gè)錯誤也比較容易發(fā)現。
例 2 可能會(huì )導致不能把 vectInt 中所有為 3 的元素刪除掉。因為第一次刪除成功時(shí)， itVect = vectInt.erase( itVect );itVect 為指向 3 之后的位置，之后再執行 ++itVect ， itVect 就掉過(guò)了被刪除元素 3 之后的元素 3 ，導致只刪除了一個(gè)為 3 的元素，這個(gè) bug 比較隱蔽，因為如果不是兩個(gè)均為 3 的元素相臨，就將很難捕捉到這個(gè) bug ，程序有可能在一段時(shí)間運行良好，但如碰到容器中兩值相同的元素相臨，則程序就要出問(wèn)題。
例 3 ，對于本例你可能要說(shuō)程序沒(méi)有任何問(wèn)題，解決了上面的兩個(gè) bug ，程序也運行正常。但且慢，你把 “ vectInt[ 4 ] = 4; ” 這一行改為 “ vectInt[ 4 ] = 3; ”試試，一運行，程序當掉，訪(fǎng)問(wèn)非法內存！你疑惑不解：從程序看不出 bug ，而且我還把 vectInt.end() 放在外面計算以防止 for 多重計算，提高效率。哈哈，問(wèn)題就出在最后一句話(huà)！算法大師 Donald Knuth 有一句名言：不成熟的優(yōu)化是一切惡果的根源（ Permature optimization is the root of all evil ）。由于在 for 循環(huán)中要刪除元素，則 vectInt.end() 是會(huì )變化的，所以不能在 for 循環(huán)外計算，而是每刪除一次都要重新計算，所以應放在 for 循環(huán)內。那你要問(wèn)，為什么把 “ vectInt[ 4 ] = 4; ” 這一行改為 “ vectInt[ 4 ] = 3; ”程序就會(huì )當掉，而不改程序就很正常呢？這就跟 vector 的實(shí)現機制有關(guān)了。下面以圖例詳細解釋。
vectInt 的初始狀態(tài)為：
| end
0 1 2 3 4
刪除 3 后，
| 新的 end | 原來(lái)的 end
0 1 2 4 4
注意上面“新的 end ”指向的內存并沒(méi)有被清除，為了效率， vector 會(huì )申請超過(guò)需要的內存保存數據，刪除數據時(shí)也不會(huì )把多余的內存刪除。
然后 itVect 再執行 ++itVect ，因為此時(shí) *itVect 等于 4 ，所以繼續循環(huán)， 這時(shí) itVect 等于“新的 end ”但不等于“原來(lái)的 end ”（它即為 itVectEnd ），所以繼續，因為 *itVect 訪(fǎng)問(wèn)的是只讀內存得到的值為 4 ，不等于 3 ，故不刪除，然后執行 ++itVect 此時(shí) itVect 等于 itVectEnd 退出循環(huán)。從上面過(guò)程可以看出，程序多循環(huán)了一次（刪除幾次，就要多循環(huán)幾次），但程序正常運行。
如果把 “ vectInt [ 4 ] = 4; ” 這一行改為 “ vectInt [ 4 ] = 3; ”過(guò)程如下：
| end
0 1 2 3 3
刪除 3 后，
| 新的 end | 原來(lái)的 end
0 1 2 3 3
刪除第 2 個(gè) 3 后，
| 新的 end | 原來(lái)的 end
0 1 2 3 3
這時(shí) itVect 等于“新的 end ”但不等于“原來(lái)的 end ”（它即為 itVectEnd ），所以繼續，因為 *itVect 訪(fǎng)問(wèn)的是只讀內存得到的值為 3 ，等于 3 ，所以執行刪除，但因為 *itVect 訪(fǎng)問(wèn)的是只讀內存不能刪除，所以程序當掉。
綜上，我們知道當要刪除的值在容器末尾時(shí)，會(huì )導致程序刪除非法內存，程序當掉；即使程序正常運行，也是 for 循環(huán)多執行了等于刪除個(gè)數的循環(huán)。所以把 vectInt.end() 放在 for 循環(huán)外面執行，完全是錯誤的。對于 list 容器， list.end() 在刪除過(guò)程中是不會(huì )變的，可以把它放在 for 循環(huán)外面計算，但由于 list.end() 是個(gè)常量，把 list.end() 放在 for 循環(huán)中計算編譯器應該可以?xún)?yōu)化它。從安全考慮，除非你能保證 for 循環(huán)中不會(huì )改變容器的大小，否則都應該對容器的值在 for 循環(huán)中計算，對于 vectInt.size() 這樣的計算，也應該在 for 循環(huán)中計算，不要因為微小的優(yōu)化而導致程序出錯。
正確的方法：
例 4 ：
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
for ( i = 0; i < 5; i++ ) {
vectInt.push_back( i );
if ( 3 == i ) {
// 使 3 的元素有兩個(gè)，并且相臨。
vectInt.push_back( i );
}
}
vector<int>::iterator itVect = vectInt.begin();
// 以下代碼是要刪除所有值為 3 的元素
for ( ; itVect != vectInt.end(); ) { // 刪除 ++itVect{
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
else {
++itVect;
}
}
// 把 vectInt.size() 放在 for 循環(huán)中
for ( i = 0 ; i < vectInt.size(); i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
運行結果為：
i= 0, 0
i= 1, 1
i= 2, 2
i= 3, 4
從結果顯示值為 3 的元素確實(shí)被刪除了。
本文來(lái)自CSDN博客，轉載請標明出處：http://blog.csdn.net/OExpress/archive/2006/06/15/799572.aspx
聯(lián)系客服
