C++ 容器及选用总结
原文地址
目錄
====================================================
第一章?容器
第二章?Vector和string
第三章?關(guān)聯(lián)容器
第四章?迭代器
第五章?算法
第六章?函數(shù)
第七章?在程序中使用STL
====================================================
第1章?容器
第1條：慎重選擇容器類型。
?
標(biāo)準(zhǔn)STL序列容器：vector、string、deque和list。
標(biāo)準(zhǔn)STL關(guān)聯(lián)容器：set、multiset、map和multimap。
非標(biāo)準(zhǔn)序列容器slist和rope。slist是一個單向鏈表，rope本質(zhì)上是一“重型”string。
非標(biāo)準(zhǔn)的關(guān)聯(lián)容器hash_set、hase_multiset、hash_map和hash_multimap。
vector<char>?作為string的替代。(見第13條)
vector作為標(biāo)準(zhǔn)關(guān)聯(lián)容器的替代。(見第23條)
幾種標(biāo)準(zhǔn)的非STL容器，包括數(shù)組、bitset、valarray、stack、queue和priority_queue。
?
你是否關(guān)心容器中的元素是如何排序的？如果不關(guān)心，選擇哈希容器.
容器中數(shù)據(jù)的布局是否需要和C兼容？如果需要兼容，就只能選擇vector。(第16條)
元素的查找速度是否是關(guān)鍵的考慮因素？如果是，就要考慮哈希容器、排序的vector和標(biāo)準(zhǔn)關(guān)聯(lián)容器－或許這就是優(yōu)先順序。
對插入和刪除操作，你需要事務(wù)語義嗎？如果是，只能選擇list。因為在標(biāo)準(zhǔn)容器中，只有l(wèi)ist對多個元素的插入操作提供了事務(wù)語義。
deque是唯一的、迭代器可能會變?yōu)闊o效（插入操作僅在容器末尾發(fā)生時，deque的迭代器可能會變?yōu)闊o效）而指向數(shù)據(jù)的指針和引用依然有效的標(biāo)準(zhǔn)STL容器。
?
第2條：不要試圖編寫?yīng)毩⒂谌萜黝愋偷拇a。
?
如果你想編寫對大多數(shù)的容器都適用的代碼，你只能使用它們的功能的交集。不同的容器是不同的，它們有非常明顯的優(yōu)缺點。它們并不是被設(shè)計用來交換使用的。?
?
第3條：確保容器中的對象拷貝正確而高效。
copy?in,copy?out，是STL的工作方式，它總的設(shè)計思想是為了避免不必要的拷貝。
?
第4條：調(diào)用empty而不是檢查size()是否為0。
理由很簡單：empty對所有的標(biāo)準(zhǔn)容器都是常數(shù)時間操作，而對一些list的實現(xiàn)，size耗費線性時間。
?
第5條：區(qū)間成員函數(shù)優(yōu)先于與之對應(yīng)的單元素成員函數(shù)。
區(qū)間成員函數(shù)寫起來更容易，更能清楚地表達你的意圖，而且它們表現(xiàn)出了更高的效率。
第6條：當(dāng)心C＋＋編譯器最煩人的分析機制。
把形參加括號是合法的，把整個形參（包括數(shù)據(jù)類型和形參名）用括號括起來是非法的。
?
第7條：如果容器中包含通過new操作創(chuàng)建的指針，切記在容器對象析構(gòu)前將指針delete。
STL很智能，但沒有智能到知道是否該刪除自己所包含的指針?biāo)赶虻膶ο蟮某潭?。為了避免資源泄漏，你必須在容器被析構(gòu)前手工刪除其中的每個指針，或使用引用計數(shù)形式的智能指針（比如Boost的sharedprt）代替指針。
?
第8條：切勿創(chuàng)建包含auto_ptr的容器對象。
拷貝一個auto_ptr意味著改變它的值。例如對一個包含auto_ptr的vector調(diào)用sort排序，結(jié)果是vector的幾個元素被置為NULL而相應(yīng)的元素被刪除了。
第9條：慎重選擇刪除元素的方法。
要刪除容器中指定值的所有對象：
如果容器是vector、string或deque，則使用erase-remove習(xí)慣用法。
SeqContainer<int>?c;
c.erase(remove(c.begin(),c.end(),1963),c.end());
如果容器是list，則使用list::remove。
如果容器是一個標(biāo)準(zhǔn)關(guān)聯(lián)容器，則使用它的erase成員函數(shù)。
要刪除容器中滿足特定條件的所有對象：
如果容器是vector、string或deque，則使用erase-remove_if習(xí)慣用法。
如果容器是list，則使用list::remove_if。
如果容器是一個標(biāo)準(zhǔn)關(guān)聯(lián)容器，則使用remove_copy_if和swap，或者寫一個循環(huán)遍歷容器的元素，記住當(dāng)把迭代器傳給erase時，要對它進行后綴遞增。
AssocCOntainer<int>?c;
...
AssocContainer<int>?goodValues;
remove_copy_if(c.begin(),?c.end(),?
?????????????????inserter(goodValues,?goodValues.end()),?badValue);
c.swap(goodValues);
或
for(AssocContainer<int>::iterator?i?=?c.begin();i?!=c.end();/*?do?nothing?*/){
if(badValue(*i))?c.erase(i++);
?????????else?++i;
}
要在循環(huán)內(nèi)部做某些（除了刪除對象之外的）操作：
如果容器是一個標(biāo)準(zhǔn)序列容器，則寫一個循環(huán)來遍歷容器中的元素，記住每次掉用erase時，要用它的返回值更新迭代器。
如果容器是一個標(biāo)準(zhǔn)關(guān)聯(lián)容器，則寫一個循環(huán)來遍歷容器中的元素，記住每次把迭代器傳給erase時，要對迭代器做后綴遞增。
?
第12條：切勿對STL容器的線程安全性有不切實際的依賴。
對一個STL實現(xiàn)你最多只能期望：多個線程讀是安全的；多個線程對不同的容器寫入操作是安全的。
你不能期望STL庫會把你從手工同步控制中解脫出來，且你不能依賴于任何線程支持。
?
第2章?vector和string
第13條：vector和string優(yōu)先于動態(tài)分配的數(shù)組。
如果用new，意味著你要確保后面進行了delete。
如果你所使用的string是以引用計數(shù)來實現(xiàn)的，而你又運行在多線程環(huán)境中，并認為string的引用計數(shù)實現(xiàn)會影響效率，那么你至少有三種可行的選擇，而且，沒有一種選擇是舍棄STL。首先，檢查你的庫實現(xiàn)，看看是否可以禁用引用計數(shù)，通常是通過改變某個預(yù)處理變量的值。其次，尋找或開發(fā)一個不使用引用計數(shù)的string實現(xiàn)。第三，考慮使用vector<char>而不是string。vector的實現(xiàn)不允許使用引用計數(shù)，所以不會發(fā)生隱藏的多線程性能問題。
第14條：使用reserve來避免不必要的重新分配。
通常有兩種方式來使用reserve以避免不必要的重新分配。第一種方式是，若能確切知道或大致預(yù)計容器中最終會有多少個元素，則此時可使用reserve。第二種方式是，先預(yù)留足夠大的空間，然后，當(dāng)把所有的數(shù)據(jù)都加入后，再去除多余的容量。
第15條：注意string實現(xiàn)的多樣性。
如果你想有效的使用STL，那么你需要知道string實現(xiàn)的多樣性，尤其是當(dāng)你編寫的代碼必須要在不同的STL平臺上運行而你又面臨著嚴格的性能要求的時候。
第16條：了解如何把vector和string數(shù)據(jù)傳給舊的API。
如果你有個vector?v，而你需要得到一個只想v中的數(shù)據(jù)的指針，從而可把數(shù)據(jù)作為數(shù)組來對才，那么只需要使用＆v［0］就可以了，也可以用＆＊v.begin（），但是不好理解。對于string?s，隨應(yīng)的形式是s.c_str()。
如果想用來自C?API的數(shù)據(jù)來初始化一個vector，那么你可以利用vector和數(shù)組的內(nèi)存布局兼容性，先把數(shù)據(jù)寫入到vector中，然后把數(shù)據(jù)拷貝到期望最終寫入的STL容器中。
?
第17條：使用“swap技巧”除去多余的容量。
vector<Contestant>(contestants).swap(contestants);
表達式vector<Contestant>(contestants)創(chuàng)建一個臨時的矢量，它是contestants的拷貝：這是由?vector的拷貝構(gòu)造函數(shù)來完成的。然而，vector的拷貝構(gòu)造函數(shù)只為所拷貝的元素分配所需要的的內(nèi)存，所以這個臨時矢量沒有多余的容量。然后我們把臨時矢量中的數(shù)據(jù)和contestants中的數(shù)據(jù)作swap操作，在這之后，contestants具有了被去除之后的容量，即原先臨時變量的容量，而臨時變量的容量則變成了原先contestants臃腫的容量。到這時，臨時矢量被析構(gòu)，從而釋放了先前為contestants所占據(jù)的內(nèi)存。
同樣的技巧對string也實用：
string?s；
...
string(s).swap(s);
?
第3章?關(guān)聯(lián)容器
第19條：理解相等（equality）和等價（equivalence）的區(qū)別。
標(biāo)準(zhǔn)關(guān)聯(lián)容器總是保持排列順序的，所以每個容器必須有一個比較函數(shù)（默認為less）。等價的定義正是通過該比較函數(shù)而確定的。相等一定等價，等價不一定相等。
第20條：為包含指針的關(guān)聯(lián)容器指定比較類型。
每當(dāng)你創(chuàng)建包含指針的關(guān)聯(lián)容器時，容器將會按照指針的值（就是內(nèi)存地址）進行排序，絕大多數(shù)情況下，這不是你所希望的。
?
第21條：總是讓比較函數(shù)在等值情況下返回false。
現(xiàn)在我給你演示一個很酷的現(xiàn)象。創(chuàng)建一個set，用less_equal作為它的比較類型，然后把10插入到該集合中：
set<int,?less_equal<int>?>?s;?//s?用"<="?來排序
s.insert(10);
s.insert(10);
對于第二個insert，集合會檢查下面的表達式是否為真：
!(10a?<=?10b)?&&?!(10b?<=?10a);?//檢查10a和10b是否等價，結(jié)果為false
結(jié)果集合中有兩個10！
從技術(shù)上講，用于對關(guān)聯(lián)容器排序的比較函數(shù)必須為他們所比較的對象定義個“嚴格的弱序化”（strict?weak?ordering）。
?
第22條：切勿直接修改set或multiset中的鍵。
如果你不關(guān)心可移植性，而你想改變set或multiset中元素的值，并且你的STL實現(xiàn)（有的STL實現(xiàn)中，比如set<T>::?iterator?的operator*總是返回const?T&，就不能修改了）允許你這么做，則請繼續(xù)做下去。只是注意不要改變元素中的鍵部分，即元素中能夠影響容器有序性的部分。
如果你重視可移植性，就要確保set和multiset中的元素不能被修改。至少不能未經(jīng)過強制類型轉(zhuǎn)換（轉(zhuǎn)換到一個引用類型const_cast<T&>）就修改。
如果你想以一種總是可行而且安全的方式來許該set、multiset、map和multimap中的元素，則可以分5個簡單步驟來進行：
1.?找到你想修改的容器的元素。如果你不能肯定最好的做法，第45條介紹了如何執(zhí)行一次恰當(dāng)?shù)乃阉鱽碚业教囟ǖ脑亍?/span>
2.?為將要被修改的元素做一份拷貝，。在map和multimap的情況下，請記住，不要把該拷貝的第一個部分聲明為const。畢竟，你想要改變它。
3.?修改該拷貝，使它具有你期望的值。
4.?把該元素從容器中刪除，通常是通過erase來進行的（見第9條）。
5.?把拷貝插到容器中去。如果按照容器的排列順序，新元素的位置可能與被刪除元素的位置相同或緊鄰，則使用“提示”（hint）形式的insert，以便把插入的效率從對數(shù)時間提高到常數(shù)時間。把你從第1步得來的迭代器作為提示信息。
?
第23條：考慮用排序的vector替代關(guān)聯(lián)容器。
標(biāo)準(zhǔn)關(guān)聯(lián)容器通常被實現(xiàn)為平衡的二叉查找樹。也就是說，它所適合的那些應(yīng)用程序首先做一些插入操作，然后做查找，然后可能又插入一些元素，或許接著刪掉一些，隨后又做查找，等等。這一系列時間的主要特征是插入、刪除和超找混在一起?？偟膩碚f，沒辦法預(yù)測出針對這顆樹的下一個操作是什么。
很多應(yīng)用程序使用其數(shù)據(jù)結(jié)構(gòu)的方式并不這么混亂。他們使用其數(shù)據(jù)結(jié)構(gòu)的過程可以明顯地分為三個階段，總結(jié)如下：
1.?設(shè)置階段。創(chuàng)建一個新的數(shù)據(jù)結(jié)構(gòu)，并插入大量元素。在這個階段，幾乎所有的操作都是插入和刪除操作。很少或幾乎沒有查找操作。
2.?查找操作。查詢該數(shù)據(jù)結(jié)構(gòu)以找到特定的信息。在這個階段，幾乎所有的操作都是查找操作，很少或幾乎沒有插入和刪除操作。
3.?重組階段。改變該數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，或許是刪除所有的當(dāng)前數(shù)據(jù)，再插入新的數(shù)據(jù)。在行為上，這個階段與第1階段類似。當(dāng)這個階段結(jié)束以后，應(yīng)用程序又回到第2階段。
第24條：當(dāng)效率至關(guān)重要時，請在map::operator[]與map::insert之間謹慎作出選擇。?
?????? 如果要更新一個已有的映射表元素，選擇operator[]；如果要添加一個新的元素，選擇insert。
?
第25條：熟悉非標(biāo)準(zhǔn)的哈希容器。
標(biāo)準(zhǔn)C++庫沒有任何哈希容器，每個人認為這是一個遺憾，但是C++標(biāo)準(zhǔn)委員會認為，把它們加入到標(biāo)準(zhǔn)中所需的工作會拖延標(biāo)準(zhǔn)完成的時間。已經(jīng)有決定要在標(biāo)準(zhǔn)的下一個版本中包含哈希容器。
第4章?迭代器
第26條：iterator優(yōu)先于const_iterator、reverse_iterator以及const_reverse_iterator。
減少混用不同類型的迭代器的機會，盡量用iterator代替const_iterator。從const正確性的角度來看，僅僅為了避免一些可能存在的?STL實現(xiàn)缺陷而放棄使用const_iteraor顯得有欠公允。但考慮到在容器類的某些成員函數(shù)中指定使用iterator的現(xiàn)狀，得出?iterator較之const_iterator更為實用的結(jié)論也就不足為奇了。更何況，從實踐的角度來看，并不總是值得卷入?const_iterator的麻煩中。
第27條：使用distance和advance將容器的const_iterator轉(zhuǎn)換成iterator。
下面的代碼試圖把一個const_iterator強制轉(zhuǎn)換為iterator：
typedef?deque<int>?IntDeque;?//類型定義，簡化代碼
typedef?IntDeque::iterator?Iter;
typedeef?IntDeque:;const_iterator?ConstIter;
ConstIter?ci;?//ci?是一個const_iterator
...
Iter?i(ci);?//編譯錯誤！從const_iterator?到?iterator沒有隱式轉(zhuǎn)換途徑
Iter?i(const_cast<Iter>(ci));?//仍然是編譯錯誤！不能將const_iterator強制轉(zhuǎn)換為iterator
包含顯式類型轉(zhuǎn)換的代碼不能通過編譯的原因在于，對于這些容器類型，iterator和const_iterator是完全不同的類，他們之間的關(guān)系甚至比string和complex<double>之間的關(guān)系還要遠。
下面是這種方案的本質(zhì)。
typedef?deque<int>?IntDeque;?//類型定義，簡化代碼
typedef?IntDeque::iterator?Iter;
typedeef?IntDeque:;const_iterator?ConstIter;
IntDeque?d;
ConstIter?ci;?//ci?是一個const_iterator
...?//使ci指向d
Iter?i(d.begin());//使i指向d的起始位置
advance(i,distance<ConstIter>(i,ci));//移動i，使它指向ci所指的位置
這中方法看上去非常簡單和直接，也很令人吃驚。為了得到一個與const_iterator指向同一位置的iterator，首先創(chuàng)建一個新的?iterator，將它指向容器的起始位置，然后取得const_iterator距離容器起始位置的偏移量，并將iterator向前移動相同的偏移量即可。這項技術(shù)的效率取決于你所使用的迭代起，對于隨機迭代器，它是常數(shù)時間的操作；對于雙向迭代器，以及某些哈希容器，它是線性時間的操作。
第28條：正確理解由reverse_iterator的base()成員函數(shù)所產(chǎn)生的iterator的用法。
如果要在一個reverse_iterator?ri指定的位置上插入元素，則只需在ri.base()位置處插入元素即可。對于插入操作而言，ri和ri.base()是等價的，ri.base()是真正與ri對應(yīng)的iterator。
如果要在一個reverse_iterator?ri指定的位置上刪除一個元素，則需要在ri.base()前一個位置上執(zhí)行刪除操作。對于刪除操作而言，ri和ri.base()是不等價的。
我們還是有必要來看一看執(zhí)行這樣一個刪除操作的實際代碼，其中暗藏著驚奇之處：
vector<int>?v;
...?//同上，插入1到5
vector<int>::reverse_iterator?ri?=?find(v.rbegin(),v.rend(),3);//使ri指向3
v.erase(--ri.base());?//試圖刪除ri.base()前面的元素，對于vector，往往編譯通不過
對于vector和string，這段代碼也許能工作，但對于vector和string的許多實現(xiàn)，它無法通過編譯。這是因為在這樣的實現(xiàn)中，?iterator(和vconst_iterator)是以內(nèi)置指針的方式實現(xiàn)的，所以ri.base()的結(jié)果是一個指針。C和C＋＋都規(guī)定了從函數(shù)返回的指針不應(yīng)該被修改，所以所以編譯不能通過。
既然不能對base()的結(jié)果做遞減操作，那么只要先遞增reverse_iterator，然后再調(diào)用base()函數(shù)即可！
...
v.erase((++ri).base());?//刪除ri所指的元素，這下編譯沒問題了！
第29條：對于逐個字符的輸入請考慮使用istreambuf_iterator。
假如你想把一個文本文件的內(nèi)容拷貝到一個string對象中，以下的代碼看上去是一種合理的解決方案：
ifstream?inputFile("interestingData.txt");
inputFIle.unsetf(ios::skipws);//istream_iterator使用operator>>函數(shù)來完成實際的讀操作，而默認情況下operator>>函數(shù)會跳過空白字符
string?fileData((istream_iterator<char>?(inputFIle)),istream_iterator<char>());
然而，你可能會發(fā)現(xiàn)整個拷貝過程遠不及你希望的那般快。istream_iterator內(nèi)部使用的operator>>實際上執(zhí)行了格式化的輸入，但如果你只是想從輸入流中讀出下一個字符的話，它就顯得有點多余了。
有一種更為有效的途徑，那就是使用STL中最為神秘的法寶之一：istreambuf_iterator。?istreambuf_iterator<char>對象使用方法與istream_iterator<char>大致相同，但是istreambuf_iterator<char>直接從流的緩沖區(qū)讀取下一個字符。（更為特殊的是，?istreambuf_iterator<char>對象從一個輸入流istream?s中讀取下一個字符的操作是通過s.rdbuf()->sgetc()來完成的。）
ifstream?inputFile("interestingData.txt");
string?fileData((istreambuf_iterator<char>(inputFile)),istreambuf_iterator<char>());
這次我們用不著清楚輸入流的skipws標(biāo)志，因為istreambuf_iterator不會跳過任何字符。
同樣的，對于非格式化的逐個字符輸出過程，你也應(yīng)該考慮使用ostreambuf_iterator。
第5章?算法
第30條：確保目標(biāo)區(qū)間足夠大。
當(dāng)程序員希望向容器中添加新的對象，這里有一個例子：
int?transmogrify(int?x);?//該函數(shù)根據(jù)x生成一個新的值
vector<int>?values;
vector<int>?results;
transform(values.begin(),values.end(),back_inserter(results),transmogrify);
back_inserter返回的迭代起將使得push_back被調(diào)用，所以back_inserter可適用于所有提供了push_back方法的容器。同理，front_inserter僅適用于那些提供了push_front成員函數(shù)的容器（如deque和list）。
當(dāng)是使用reserver提高一個序列插入操作的效率的時候，切記reserve只是增加了容器的容量，而容器的大小并未改變。當(dāng)一個算法需要向?vector或者string中加入新的元素，即使已經(jīng)調(diào)用了reserve，你也必須使用插入型的迭代器。如下代碼給出了一種錯誤的方式：
vector<int>?values;
vector<int>?results;
...
results.reserve(results.size()?+?values.size());
transform(values.begin(),?values.end(),?results.end(),?transmogrify);//變換的結(jié)果會寫入到尚未初始化的內(nèi)存，結(jié)果將是不確定的
在以上代碼中transform欣然接受了在results尾部未初始化的內(nèi)存中進行復(fù)制操作的任務(wù)。由于賦值操作重視在兩個對象之間而不是在一個對象與一個未初始化的內(nèi)存塊之間進行，所以一般情況下，這段代碼在運行時會失敗。
假設(shè)希望transform覆蓋results容器中已有的元素，那么就需要確保results中已有的元素至少和values中的元素一樣多。否則，就必須使用resize來保證這一點。
vector<int>?values;
vector<int>?results;
...
if(results.size()?<?values.size()){
results.resize(values.size());
}
transform(values.begin(),values.end(),results.begin(),transmogrify);
或者，也可以先清空results，然后按通常的方式使用一個插入型迭代起：
...
results.clear();
results.reserve(values.size());
transform(values.begin(),values.end(),back_inserter(results),transmogrify);
第31條：了解各種與排序有關(guān)的選擇。
sort(stable_sort)、partial_sort和nth_element算法都要求隨即訪問迭代器，所以這些算法只能被應(yīng)用于?vector、string、deque和數(shù)組。partion（stable_partion）只要求雙向迭代器就能完成工作。
對于標(biāo)準(zhǔn)關(guān)聯(lián)容器中的元素進行排序并沒有實際意義，因為它們總是使用比較函數(shù)來維護內(nèi)部元素的有效性。
list是唯一需要排序卻無法使用這些排序算法的容器，為此，list特別提供了sort成員函數(shù)（有趣的是，list::sort執(zhí)行的是穩(wěn)定排序）。如果希望希望一個list進行完全排序，可以用sort成員函數(shù)；但是，如果需要對list使用partial_sort或者nth_element算法的話，你就只能通過間接途徑來完成了。一種間接做法是，將list中的元素拷貝到一個提供隨即訪問迭代器的容器中，然后對該容器執(zhí)行你所期望的算法；另一種簡介做法是，先創(chuàng)建一個list::iterator的容器，再對該容器執(zhí)行相應(yīng)的算法，然后通過其中的迭代器訪問list的元素；第三中方法是利用一個包含迭代器的有序容器的信息，通過反復(fù)地調(diào)用splice成員函數(shù)，將?list中的元素調(diào)整到期望的目標(biāo)位置。可以看到，你會有很多中選擇。
第32條：如果確實需要刪除元素，則需要在remove這一類算法之后調(diào)用erase。
1?2?3?99?5?99?7?8?9?99
調(diào)用remove(v.begin(),v.end(),99)；后變成
1?2?3?5?7?8?9?8?9?99
remove無法從迭代器推知對應(yīng)的容器類型，所以就無法調(diào)用容器的成員函數(shù)erase，因此就無法真正刪除元素。其他兩個算法remove_if和?unique也類似。不過list::remove和list::unique會真正刪除元素（比用erase-remove和erase-unique?更為高效），這是STL中一個不一致的地方。
第33條：對包含指針的容器使用remove這一類算法時要特別小心。
無論你如何處理那些存放動態(tài)分配的指針的容器，你總是可以這樣來進行：或者調(diào)用remove類算法之前先手工刪除指針并將它們置為空，或者通過引用計數(shù)的智能指針(?如boost::shared_ptr)，或者你自己發(fā)明的其他某項技術(shù)。
下面的代碼利用第一種方式：
void?delAndNullifyUncertified(Widget*&?pWidget)
{
if(!pWidget->isCertified())
{
delete?pWidget;
pWidget?=?0;
}
}
for_each(v.begin(),v.end(),delAndNullifyUndertified);
v.erase(vemove(v.begin(),v.end(),static_cast<Widget*>(0)),v.end());
下面的的代碼使用第二中方式：
template<typename?T>?//RSCP?=?"Reference?Counting?Smart?Pointer"
class?RCSP{...};
tpedef?RCSP<Widget>?RCSPW;
vector<RCSPW>?v;
...
v.push_back(RCSPW(new?Widget));
...
v.erase(remove_if(v.begin(),v.end(),not1(mem_fun(&Widget::isCertified))),v.end());
第34條：了解哪些算法要求使用排序的區(qū)間作為參數(shù)。
下面的代碼要求排序的區(qū)間：
binary_search?lower_bound
upper_bound?equal_range
set_union?set_intersection
set_difference?set_symmetric_difference
merge?inplace_merge
includes
下面的算法并不一定需要排序的區(qū)間：
unique?unique_copy
第35條：通過mismatch或lexicographical_compare實現(xiàn)簡單的忽略大小寫的字符串比較。
用mistatch實現(xiàn)：
//此函數(shù)判斷兩個字母是否相同，而忽略它們的大小寫
int?ciCharCompare(char?c1,?char?c2)
{
int?lc1?=?tolower(static_cast<unsigned_char>(c1));
int?lc2?=?tolower(static_cast<unsigned_char>(c2));
if(lc1?<?lc2)?return?-1;
if(lc1?>?lc2)?return?1;
return?0;
}
/*?此函數(shù)保證傳遞給ciStringCompareImpl的s1比s2短，如果s1和s2相同，返回0；如果s1比s2短，返回-1；如果s1比s2長，返回1。*/
int?ciStringCompare(const?string&?s1,?const?string&?s2)
{
if(s1.size()?<=?s2.size())?return?ciStringCompareImpl(s1,?s2);
else?return?–?ciStringCompareImpl(s2,?s1);?
}
//如果s1和s2相同，返回0；如果s1比s2短，返回-1；如果s1和s2都是在非結(jié)尾處發(fā)生不匹配，有開始不匹配的那個字符決定。
int?ciStringCompareImpl(const?string?&s1,?const?string?&c2)
{
typedef?pair<string::const_iterator,string::const_iterator>?PSCI;
PSCI?p?=?mismatch(s1.begin(),s1.end(),s2.begin(),not2(ptr_fun(ciCharCompare)));
if(p.first?==?s1.end()){
if(p.second?==?s2.end())?return?0;
else?return?-1;
}
return?ciCharCompair(*p.first,?*p.second);
}
用lexicographical_compare實現(xiàn)：
bool?ciCharLess(char?c1,?char?c2)
{
return?tolower(static_cast<unsigned?char>(c1))?<?tolower(static_cast<unsigned?char>(c2));
}
bool?ciStringCompare(const?string?&s1,const?string?&s2)
{
return?lexicographical_compare(s1.begin(),?s1.end(),?s2.begin(),?s2.end(),?ciCharLess);
}
第36條：理解copy_if算法的正確實現(xiàn)。
STL中沒有copy_if的算法，下面是一個實現(xiàn)，但是不夠完美：
template<typename?INputIterator,typename?OUtputIterator,tpename?Predicate>
OutputIterator?copy_if(INputIterator?begin,INputIterator?end,OutputIterator?destBegin,Predicate?p)
{
return?remove_copy_if(begin,end,destBegin,?not1(0));
}
copy_if(widgets.begin(),?widgets.end(),?ostream_iterator<Widget>(cerr,?"\n"),isDefective);//編譯錯誤
因為not1不能被直接應(yīng)用到一個函數(shù)指針上（見41條），函數(shù)指針必須先用ptr_fun進行轉(zhuǎn)換。為了調(diào)用copy_if的這個實現(xiàn)，你傳入的不僅是一個函數(shù)對象，而且還應(yīng)該是一個可配接（adaptable）的函數(shù)對象。雖然這很容易做到，但是要想成為STL算法，它不能給客戶這樣的負擔(dān)。
下面是copy_if的正確實現(xiàn)：
template<typename?INputIterator,typename?OUtputIterator,typename?Predicate>
OutputIterator?copy_if(INputIterator?begin,INputIterator?end,OutputIterator?destBegin,Predicate?p)
{
while(begin?!=?end){
if(p(*begin))?*destBegin++?=?*begin;
++begin;
}
return?destBegin;
}
第37條：使用accumulate或者for_each進行區(qū)間統(tǒng)計。
確保accumulate的返回類西和初始值類型相同。for_each返回的是一個函數(shù)對象。accumulate不允許副作用而for_each允許。（這是一個深層次的問題，也是一個涉及STL核心的問題，待解）
第6章?函數(shù)子、函數(shù)子類、函數(shù)及其他
第38條：遵循按值傳遞的原則來設(shè)計函數(shù)子類。
在STL中，函數(shù)對象在函數(shù)之間來回傳遞的時候也是像函數(shù)指針那樣按值傳遞的。因此，你的函數(shù)對象必須盡可能的小，否則拷貝的開銷會很大；其次，函數(shù)對象必須是單態(tài)的，也就是說，它們不得使用虛函數(shù)。這是因為，如果參數(shù)的類型是基類類型，而實參是派生類對象，那么在傳遞過程中會產(chǎn)生剝離問題（slicing?problem）：在對象拷貝過程中，派生部分可能會被去掉，而僅保留了基類部分（見第3條）。
試圖禁止多態(tài)的函數(shù)子同樣也是不實際的。所以必須找到一種兩全其美的辦法，既允許函數(shù)對象可以很大并且／或保留多態(tài)性，又可以與STL所采用的按值傳遞函數(shù)子的習(xí)慣保持一致。這個辦法就是：將所需要的數(shù)據(jù)和虛函數(shù)從函數(shù)子中分離出來，放到一個新的類中，然后在函數(shù)子中設(shè)一個指針，指向這個新類。
第39條：確保判別式是“純函數(shù)”。
一個判別式（predicate）是一個返回值為bool類型的函數(shù)。一個純函數(shù)（pure?function）是指返回值僅僅依賴于其參數(shù)的函數(shù)。
因為接受函數(shù)子的STL算法可能會先創(chuàng)建函數(shù)子對象的拷貝，然后使用這個拷貝，因此這一特性的直接反映就是判別式函數(shù)必須是純函數(shù)。
template<typename?FwdIterator,typename?Predicata>
FwdIterator?remove_if(FwdIterator?begin,?FwdIterator?end,?Predicate?p)
{
begin?=?find_if(begin,?end,?p);//可能是p的拷貝
if(begin?==?end?return?begin;
else{
FwdIterator?next?=?begin;
return?remove_copy_if(++next,?end,?begin,?p);//可能是p的另一個拷貝
}
}
第40條：若一個類是函數(shù)子，則應(yīng)使它可配接。
4個標(biāo)準(zhǔn)的函數(shù)配接器(not1、not2、bind1st和bind2nd）都要求一些特殊的類型定義。提供了這些必要的類型定義（argument_type、first_argument_type、second_argument_type以及result_type）的函數(shù)對象被稱為可配接的（adaptable）函數(shù)對象，反之，如果函數(shù)對象缺少這些類型定義，則稱為不可配接的。可配接的函數(shù)對象能夠與其他STL組件更為默契地協(xié)同工作。不過不同種類的函數(shù)子類所需要提供的類型定義也不盡相同，除非你要編寫自定義的配接器，否則你并不需要知道有關(guān)這些類型定義的細節(jié)。這是因為，提供這些類型定義最簡便的辦法是讓函數(shù)子從特定的基類繼承，或者更準(zhǔn)確的說，如果函數(shù)子類的operator()只有一個形參，那么它應(yīng)該從?std::unary_function模板的一個實例繼承；如果函數(shù)子類的operator()有兩個形參，那么它應(yīng)該從std::?binary_function繼承。
對于unary_function，你必須指定函數(shù)子類operator()所帶的參數(shù)的類型，以及返回類型；對于binary_function，你必須指定三個類型：operator()的第一個和第二個參數(shù)的類型，以及operator()的返回類型。以下是兩個例子：
template<typename?T>
class?MeetsThreshold:?public?std::unary_function<Widget,?bool>?{
private:
const?T?threshold;
public:
MeetsThreshold(const?T&?threshold);
bool?operator()(const?Widget&)?const;
...
};
struct?WidgetNameCompare:
public?std::binary_function<Widget,?Widget,?bool>?{
bool?operator()?(const?Widget&?lhs,?const?Widget&?rhs)?const;
};
你可能已經(jīng)注意到MeetsThreshold是一個類，而WidgetNameCompare是一個結(jié)構(gòu)。這是因為MeetsThreshold包含了狀態(tài)信息（數(shù)據(jù)成員threshold），而類是封裝狀態(tài)信息的一種邏輯方式；與此相反，WidgetNameCompare并不包含狀態(tài)信息，因而不需要任何私有成員。如果一個函數(shù)子的所有成員都是公有的，那么通常會將其聲明為結(jié)構(gòu)而不是類。究竟是選擇結(jié)構(gòu)還是類來定義函數(shù)子純屬個人編碼風(fēng)格，但是如果你正在改進自己的編碼風(fēng)格，并希望自己的風(fēng)格更加專業(yè)一點的話，你就應(yīng)該注意到，STL中所有無狀態(tài)的函數(shù)子類（如less<T>、?plus<T>等）一般都定義成結(jié)構(gòu)。
我們在看一下WidgetNameCompare：
struct?WidgetNameCompare:
public?std::binary_function<Widget,?Widget,?bool>?{
bool?operator()?(const?Widget&?lhs,?const?Widget&?rhs)?const;
};
雖然operator()的參數(shù)類型都是const?Widget&，但我們傳遞給binary_function的類型卻是Widget。一般情況下，傳遞給unary_function或?binary_function的非指針類型需要去掉const和引用（&）部分（不要問其中的原因，如果你有興趣，可以訪問?boost.org，卡可能看他們在調(diào)用特性(traits)和函數(shù)對象配接器方面的工作）。
如果operator()帶有指針參數(shù)，規(guī)則又有不同了。下面是WidgetNameCOmpare函數(shù)子的另一個版本，所不同的是，這次以Widget*指針作為參數(shù)：
struct?PtrWidgetNameCompare:
public?std::binary_function<const?Widget*,?const?Widget*,?bool>?{
bool?operator()?(const?Widget*?lhs,?const?Widget*?rhs)?const;
};
第41條：理解ptr_fun、mem_fun和mem_fun_ref的來由。
如果有一個函數(shù)f和一個對象x，現(xiàn)在希望在x上調(diào)用f，而我們在x的成員函數(shù)之外，那么為了執(zhí)行這個調(diào)用，C＋＋提供了三種不同的語法：
f(x);?//語法#1：f是一個非成員函數(shù)
x.f();?//語法#2：f是一個成員函數(shù)，并且x是一個對象或一個對象引用
p->f();?//語法#3：f是成員函數(shù)，并且p是一個指向?qū)ο髕的指針
現(xiàn)在假設(shè)有個可用于測試Widget對象的函數(shù)：
void?test(Widget&?w);
另有一個存放Widget對象的容器：
vector<Widget>?vw;
為了測試vw中的每一個Widget對象，自然可以用如下的方式來調(diào)用for_each：
for_each(vw.begin(),?vw.end(),?test);?//調(diào)用#1?(可以通過編譯)
但是，加入test是Widget的成員函數(shù)，即Widget支持自測：
class?Widget{
public:
...
void?test();
....
};
那么在理想情況下，應(yīng)該也可以用for_each在vw中的每個對象上調(diào)用Widget::test成員函數(shù)：
for_each(vw.begin(),?vw.end(),?&Widget::test);//調(diào)用#2（不能通過編譯）
實際上，如果真的很理想的話，那么對于一個存放Widget*?指針的容器，應(yīng)該也可以通過for_each來調(diào)用Widget::test：
list<Widget*>?lpw;
for_each(lpw.begin(),?lpw.end(),?&Widget::test);//調(diào)用#3（也不能通過編譯）
這是因為STL中一種和普遍的慣例：函數(shù)或函數(shù)對象在被調(diào)用的時候，總是使用非成員函數(shù)的語法形式（即#1）。
現(xiàn)在mem_fun和mem_fun_ref之所以必須存在已經(jīng)很清楚了－－它們被用來調(diào)整（一般是#2和#3）成員函數(shù)，使之能夠通過語法#1被調(diào)用。?mem_fun、mem_fun_ref的做法其實很簡單，只要看一看其中任意一個函數(shù)的聲明就清楚了。它們是真正的函數(shù)模板，針對它們所配接的成員函數(shù)的圓形的不同，有幾種變化形式。我們來看其中一個聲明，以便了解它是如何工作的：
template<typename?R,?typename?C>?//該mem_fun聲明針對不帶參數(shù)的非const成員函數(shù)，C是類，R是所指向的成員函數(shù)的返回類型
mem_fun_t<R,C>
mem_fun(R(C::*pmf)?());
mem_fun帶一個指向某個成員函數(shù)的指針參數(shù)pmf，并且返回一個mem_fun_t類型的對象。mem_fun_t是一個函數(shù)子類，它擁有該成員函數(shù)的指針，并提供了operator()函數(shù)，在operator()中調(diào)用了通過參數(shù)傳遞進來的對象上的該成員函數(shù)。例如，請看下面一段代碼：
list<Widget*>?lpw;
...
for_each(lpw.begin(),lpw.end(),mem_fun(&Widget::test));//現(xiàn)在可以通過編譯了
for_each接受到一個類型為mem_fun_t的對象，該對象中保存了一個指向Widget::test的指針。對于lpw中的每一個?Widget*指針，for_each將會使用語法#1來調(diào)用mem_fun_t對象，然后，該對象立即用語法#3調(diào)用Widget*指針的?Widget::test()。
（ptr_fun是多余的嗎？）mem_fun是針對成員函數(shù)的配接器，mem_fun_ref是針對對象容器的配接器。
第42條：確保less<T>與operator<具有相同的含義。
operator<不僅僅是less的默認實現(xiàn)方式，它也是程序員期望less所做的事情。讓less不調(diào)用operator<而去坐別的事情，這會無端地違背程序員的意愿，這與“少”帶給人驚奇的原則（the?principle?of?least?astonishment）完全背道而馳。這是很不好的，你應(yīng)該盡量避免這樣做。
如果你希望以一種特殊的方式來排序?qū)ο?#xff0c;那么最好創(chuàng)建一個特殊的函數(shù)子類，它的名字不能是less。
第7章?在程序中使用STL
第43條：算法調(diào)用優(yōu)于手寫的循環(huán)。
有三個理由：
效率：算法通常比程序員自己寫的循環(huán)效率更高。STL實現(xiàn)者可以針對具體的容器對算法進行優(yōu)化；幾乎所有的STL算法都使用了復(fù)雜的計算機科學(xué)算法，有些科學(xué)算法非常復(fù)雜，并非一般的C＋＋程序員所能夠到達。
正確性：自己寫的循環(huán)比使用算法容易出錯。比如迭代器可能會在插入元素后失效。
可維護性：使用算法的代碼通常比手寫循環(huán)的代碼更加簡介明了。算法的名稱表明了它的功能，而for、while和do卻不能，每一位專業(yè)的C＋＋程序員都應(yīng)該知道每一個算法所做的事情，看到一個算法就可以知道這段代碼的功能，而對于循環(huán)只能繼續(xù)往下看具體的代碼才能懂代碼的意圖。
第44條：容器的成員函數(shù)優(yōu)先于同名的算法。
第一：成員函數(shù)往往速度快；第二，成員函數(shù)通常與容器（特別是關(guān)聯(lián)容器）結(jié)合得更緊密（相等和等價的差別，比如對于關(guān)聯(lián)容器，count只能使用相等測試）。
第45條：正確區(qū)分count、find、binary_search、lower_bound、upper_bound和equal_range。
| 想知道什么 | | | ||
| ?? | ?? | ? | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
第46條：考慮使用函數(shù)對象而不是函數(shù)指針作為STL算法的參數(shù)。
函數(shù)指針抑制了內(nèi)聯(lián)機制，而函數(shù)對象可以被編譯器優(yōu)化為內(nèi)聯(lián)。
另一個理由是，這樣做有助于避免一些微妙的、語言本身的缺陷。在偶然的情況下，有些看似合理的代碼會被編譯器以一些合法但又含糊不清的理由而拒絕。例如，當(dāng)一個函數(shù)模板的實例化名稱并不完全等同于一個函數(shù)的名稱時，就可能會出現(xiàn)這樣的問題。下面是一個例子：
template<typename?FPType>
FPType?average(FPType?val1,?FPType?val2)//返回兩個浮點的平均值
{
return?(val1?+?val2)?/?2;
}
template<typename?InputIter1,typename?InputIter2>
void?writeAverages(InputIter1?begin1,?INputIter1?end1,?InputIter2?begin2,ostream&?s)?//將兩個序列的值按順序?qū)?yīng)取平均，然后寫到一個流中
{
transform(begin1,?end1,?begin2,
ostream_iterator<typename?iterator_trais<InputIterl>::value_type(s,"\n")>,
average<typename?iterator_traits<InputIterl>::value_type> //錯誤？
);
}
許多編譯器接受這段代碼，但是Ｃ＋＋標(biāo)準(zhǔn)卻不認同這樣的代碼。原因在于，理論上存在另一個名為average的函數(shù)模板，它也只帶一個類型參數(shù)。如果這樣的話，表達式average<typename?iterator_traits<InputIterl>::value_type>就會有二義性，因為編譯器無法分辨到底應(yīng)該實例化哪一個模板。換成函數(shù)對象就可以了。
第47條：避免產(chǎn)生“直寫型”（write-only）的代碼。
代碼被閱讀的次數(shù)遠遠大于它被編寫的次數(shù)。
第48條：總是包含（#include）正確的頭文件。
幾乎所有的標(biāo)準(zhǔn)STL容器都被聲明在與之同名的頭文件中。
除了４個STL算法外，其他所有的算法都被聲明在<algorithm>中，這4個算法是accumulate、?inner_product、adjacent_difference和partial_sum，它們都被聲明在頭文件<numeric>?中。
特殊類型的迭代器，包括istream_iterator和istreambuf_iterator（見第29條），被聲明在<iterator>中。
標(biāo)準(zhǔn)的函數(shù)子（比如less<T>）和函數(shù)子配接器（比如not1、bind2nd）被聲明在頭文件<functional>中。
第49條：學(xué)會分析與STL相關(guān)的編譯器診斷信息。
用文本替換（例如用string替換掉basic_string<char,struct?std::char_traits<char>,class?std::allocator<char>?>）。
第50條：熟悉STL相關(guān)的Web站點。
SGI?STL
站點：http://www.sig.com/tech/stl/STLport
站點：http://stlport.orgBOost
站點：http://boost.org轉(zhuǎn)載于:https://www.cnblogs.com/yan456jie/p/5369388.html
總結(jié)
以上是生活随笔為你收集整理的C++ 容器及选用总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Ajax请求中的async:false/
- 下一篇： C++中的引用（257BinaryTre