C Container 以及 STL 相關的常用操作 和 注意事項

NO IMAGE

1. 對於list和各種associative containers(set, map, sultiset, multimap),erase()操作不會使指向被刪元素以外的元素的iterator或reference失效,所以可以用下面的方法來刪:

for (itr = asso_container.begin(); itr != asso_container
.end(); ) {
if (ShouldErase(*itr)) {
asso_container.erase(itr  );
} else {
itr;
}
}

   對於vector或者deque,erase()操作還會影響指向其他元素的iterator和reference,所以不能這麼刪。比較有文化的方法是用STL的remove_if()和對區間的erase()操作配合來做這個事:

container.erase(remove_if(container.begin(), container.end(), ShouldErase), container.end());

如果ShouldErase(…)函式比較複雜,可能還要藉助boost::bind()來構造unary function。如果情況再複雜一些的話(比如要把刪掉的元素輸出),那這個方法可能就不好使了。另外,使用remove_if(…)時ShouldErase肯定不能內聯展開了,所以如果效率敏感的話,也要注意。一種基於的方法是:

for (itr = seq_container.begin(); itr != seq_container.end(); ) {
if (ShouldErase(*itr)) {
DoOtherThings(*itr);
itr = seq_container.erase(itr);
} else {
itr;
}
}

這個方法的一個嚴重問題在於:當seq_container是vector,deque等連續儲存容器時,seq_container.erase(itr)的複雜度可能是線性的!

所以我認為當效率敏感時,應該自己用for來模仿remove_if,可以在儘量不損失效率的情況下獲得足夠的靈活性。

補充:對於list,上面兩種for迴圈的刪法都是可以使用的,但一般會用第二個(seq_container)那種,因為畢竟list是sequential container。另外list有自己的remove和remove_if成員函式,不使用std::remove或std::remove_if.

2. std::vector a; 我們知道a.size()和a.capacity()不一定相等,也就是a可能有一定的預留空間。如果想釋放這些預留空間怎麼辦呢?C 03裡是用“swap大法” ,vector<int>(a).swap(a);;但到了C 11有了shrink_to_fit了就直接a.shrink_to_fit();就行了。注意:swap大法和shrink_to_fit()都可能會導致reallocation——執行前後a[0]的地址可能已經變化了(g 4.5.2上的實驗結果)。另外,這裡有很重要的一點需要說明:C 標準保證呼叫vector的clear()操作是不會更改capacity的(不知道新的標準有沒有進一步保證不會發生reallocation,不過就算沒保證,難道真的會有編譯器在不改變capacity的情況下去reallocation?),這是很有用的一個保證——實際中經常希望一次reserve()到容量需求上界以後,反覆增刪元素和清空不會觸發reallocation。

Update: 在《Effective STL》第15條發現了一段話:可以通過判斷if (v.size() < v.capacity())來確定下次push_back或者single element insertion會不會觸發reallocation。但是注意在非末尾進行insertion的話,即使沒有觸發reallocation,也會使從插入位置直到末尾的所有元素的iterators/pointers/references失效。