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