條款9:在刪除選項中仔細選擇
假定你有一個標準STL容器,c,容納int,
Container<int> c;
而你想把c中所有值為1963的對象都去掉。令人吃驚的是,完成這項任務的方法因不同的容器類型而不同:沒有一種方法是通用的。
如果你有一個連續內存容器(vector、deque或string——參見條款1),最好的方法是erase-remove慣用法(參見條款32):
c.erase(remove(c.begin(), c.end(), 1963), // 當c是vector、string c.end()); // 或deque時, // erase-remove慣用法 // 是去除特定值的元素 // 的最佳方法
這方法也適合于list,但是,正如條款44解釋的,list的成員函數remove更高效:
c.remove(1963); // 當c是list時, // remove成員函數是去除 // 特定值的元素的最佳方法
當c是標準關聯容器(即,set、multiset、map或multimap)時,使用任何叫做remove的東西都是完全錯誤的。這樣的容器沒有叫做remove的成員函數,而且使用remove算法可能覆蓋容器值(參見條款32),潛在地破壞容器。(關于這樣的破壞的細節,參考條款22,那個條款也解釋了為什么試圖在map和multimap上使用remove肯定不能編譯,而試圖在set和multiset上使用可能不能編譯。)
不,對于關聯容器,解決問題的適當方法是調用erase:
c.erase(1963); // 當c是標準關聯容器時 // erase成員函數是去除 // 特定值的元素的最佳方法
這不僅是正確的,而且很高效,只花費對數時間。(序列容器的基于刪除的技術需要線性時間。)并且,關聯容器的erase成員函數有基于等價而不是相等的優勢,條款19解釋了這一區別的重要性。
讓我們現在稍微修改一下這個問題。不是從c中除去每個有特定值的物體,讓我們消除下面判斷式(參見條款39)返回真的每個對象:
bool badValue(int x); // 返回x是否是“bad”
對于序列容器(vector、string、deque和list),我們要做的只是把每個remove替換為remove_if,然后就完成了:
c.erase(remove_if(c.begin(), c.end(), badValue), // 當c是vector、string c.end()); // 或deque時這是去掉 // badValue返回真 // 的對象的最佳方法 c.remove_if(badValue); // 當c是list時這是去掉 // badValue返回真 // 的對象的最佳方法
對于標準關聯容器,它不是很直截了當。有兩種方法處理該問題,一個更容易編碼,另一個更高效。“更容易但效率較低”的解決方案用remove_copy_if把我們需要的值拷貝到一個新容器中,然后把原容器的內容和新的交換:
AssocContainer<int> c; // c現在是一種 ... // 標準關聯容器 AssocContainer<int> goodValues; // 用于容納不刪除 // 的值的臨時容器 remove_copy_if(c.begin(), c.end(), // 從c拷貝不刪除 inserter(goodValues, // 的值到 goodValues.end()), // goodValues badValue); c.swap(goodValues); // 交換c和goodValues // 的內容
對這種方法的缺點是它拷貝了所有不刪除的元素,而這樣的拷貝開銷可能大于我們感興趣支付的。
我們可以通過直接從原容器刪除元素來避開那筆帳單。不過,因為關聯容器沒有提供類似remove_if的成員函數,所以我們必須寫一個循環來迭代c中的元素,和原來一樣刪除元素。
看起來,這個任務很簡單,而且實際上,代碼也很簡單。不幸的是,那些正確工作的代碼很少是躍出腦海的代碼。例如,這是很多程序員首先想到的:
AssocContainer<int> c; ... for (AssocContainer<int>::iterator i = c.begin(); // 清晰,直截了當 i!= c.end(); // 而漏洞百出的用于 ++i) { // 刪除c中badValue返回真 if (badValue(*i)) c.erase(i); // 的每個元素的代碼 } // 不要這么做!
唉,這有未定義的行為。當容器的一個元素被刪時,指向那個元素的所有迭代器都失效了。當c.erase(i)返回時,i已經失效。那對于這個循環是個壞消息,因為在erase返回后,i通過for循環的++i部分自增。
為了避免這個問題,我們必須保證在調用erase之前就得到了c中下一元素的迭代器。最容易的方法是當我們調用時在i上使用后置遞增:
AssocContainer<int> c; ... for (AssocContainer<int>::iterator i = c.begin(); // for循環的第三部分 i != c.end(); // 是空的;i現在在下面 /*nothing*/ ){ // 自增 if (badValue(*i)) c.erase(i++); // 對于壞的值,把當前的 else ++i; // i傳給erase,然后 } // 作為副作用增加i; // 對于好的值, // 只增加i
這種調用erase的解決方法可以工作,因為表達式i++的值是i的舊值,但作為副作用,i增加了。因此,我們把i的舊值(沒增加的)傳給erase,但在erase開始執行前i已經自增了。那正好是我們想要的。正如我所說的,代碼很簡單,只不過不是大多數程序員在第一次嘗試時想到的。
現在讓我們進一步修改該問題。不僅刪除badValue返回真的每個元素,而且每當一個元素被刪掉時,我們也想把一條消息寫到日志文件中。
對于關聯容器,這說多容易就有多容易,因為只需要對我們剛才開發的循環做一個微不足道的修改就行了:
ofstream logFile; // 要寫入的日志文件 AssocContainer<int> c; ... for (AssocContainer<int>::iterator i = c.begin(); // 循環條件和前面一樣 i !=c.end();){ if (badValue(*i)){ logFile << "Erasing " << *i <<'\n'; // 寫日志文件 c.erase(i++); // 刪除元素 } else ++i; }
現在是vector、string和deque給我們帶來麻煩。我們不能再使用erase-remove慣用法,因為沒有辦法讓erase或remove寫日志文件。而且,我們不能使用剛剛為關聯容器開發的循環,因為它為vector、string和deque產生未定義的行為!要記得對于那樣的容器,調用erase不僅使所有指向被刪元素的迭代器失效,也使被刪元素之后的所有迭代器失效。在我們的情況里,那包括所有i之后的迭代器。我們寫i++,++i或你能想起的其它任何東西都沒有用,因為沒有能導致迭代器有效的。
我們必須對vector、string和deque采用不同的戰略。特別是,我們必須利用erase的返回值。那個返回值正是我們需要的:一旦刪除完成,它就是指向緊接在被刪元素之后的元素的有效迭代器。換句話說,我們這么寫:
for (SeqContainer<int>::iterator i = c.begin(); i != c.end();){ if (badValue(*i)){ logFile << "Erasing " << *i << '\n'; i = c.erase(i); // 通過把erase的返回值 } // 賦給i來保持i有效 else ++i; }
這可以很好地工作,但只用于標準序列容器。由于論證一個可能的問題(條款5做了),標準關聯容器的erase的返回類型是void[1]。對于那些容器,你必須使用“后置遞增你要傳給erase的迭代器”技術。(順便說說,在為序列容器編碼和為關聯容器編碼之間的這種差別是為什么寫容器無關代碼一般缺乏考慮的一個例子——參見條款2。)
為了避免你奇怪list的適當方法是什么,事實表明對于迭代和刪除,你可以像vector/string/deque一樣或像關聯容器一樣對待list;兩種方法都可以為list工作。
如果我們觀察在本條款中提到的所有東西,我們得出下列結論:
- 去除一個容器中有特定值的所有對象:
如果容器是vector、string或deque,使用erase-remove慣用法。
如果容器是list,使用list::remove。
如果容器是標準關聯容器,使用它的erase成員函數。
- 去除一個容器中滿足一個特定判定式的所有對象:
如果容器是vector、string或deque,使用erase-remove_if慣用法。
如果容器是list,使用list::remove_if。
如果容器是標準關聯容器,使用remove_copy_if和swap,或寫一個循環來遍歷容器元素,當你把迭代器傳給erase時記得后置遞增它。
- 在循環內做某些事情(除了刪除對象之外):
如果容器是標準序列容器,寫一個循環來遍歷容器元素,每當調用erase時記得都用它的返回值更新你的迭代器。
如果容器是標準關聯容器,寫一個循環來遍歷容器元素,當你把迭代器傳給erase時記得后置遞增它。
如你所見,與僅僅調用erase相比,有效地刪除容器元素有更多的東西。解決問題的最好方法取決于你是怎樣鑒別出哪個對象是要被去掉的,儲存它們的容器的類型,和當你刪除它們的時候你還想要做什么(如果有的話)。只要你小心而且注意了本條款的建議,你將毫不費力。如果你不小心,你將冒著產生不必要低效的代碼或未定義行為的危險。
posted on 2008-08-02 16:57 肥仔 閱讀(266) 評論(0) 編輯 收藏 引用 所屬分類: Boost & STL