第一章.容器

• 條款1.慎重選擇容器類型

標(biāo)準(zhǔn)STL序列容器：vector、string蔓搞、deque和list
標(biāo)準(zhǔn)STL關(guān)聯(lián)容器：set骤星、map吃沪、multiset和multimap
非標(biāo)準(zhǔn)的關(guān)聯(lián)容器：hash_set跃巡、hash_multiset危号、hash_map和hash_multimap
標(biāo)準(zhǔn)的非STL容器：數(shù)組牧愁、bitset素邪、valarray、stack猪半、queue和priority_queue

另一種分類：
連續(xù)內(nèi)存容器(元素存放在一塊或多塊內(nèi)存中兔朦，每塊內(nèi)存中存有多個元素)：vector、string和deque
基于節(jié)點的容器(每塊內(nèi)存存放一個元素)：list和所有標(biāo)準(zhǔn)的關(guān)聯(lián)容器

• 條款2.不要試圖編寫?yīng)毩⒂谌萜黝愋偷拇a

序列容器與關(guān)聯(lián)容器數(shù)據(jù)結(jié)構(gòu)不同 磨确，所提供的操作也不同沽甥。
序列容器支持push_front或push_back，但關(guān)聯(lián)容器不支持乏奥。
關(guān)聯(lián)容器提供對數(shù)時間復(fù)雜度的lower_bound摆舟、upper_bound和equal_range成員函數(shù)，但序列容器卻沒有。
寫既要和序列容器又要和關(guān)聯(lián)容器一起工作的代碼并沒有什么意義恨诱。很多成員函數(shù)(包括運算符重載)只存在于其中一類容器中媳瞪。

• 條款3.確保容器中的對象拷貝正確且高效

當(dāng)你向容器中添加一個對象（比如通過insert或push_back等），進(jìn)入容器的是你指定的對象的拷貝照宝，
如果你從vector蛇受、string或deque中插入或刪除了什么或使用了任何排序算法，現(xiàn)有的容器元素會移動（拷貝）厕鹃。
因此把一個派生類對象插入基類對象的容器會導(dǎo)致派生部分被刪除兢仰，而且容器中如果放的對象拷貝過程很昂貴，元素的移動會成為性能瓶頸剂碴，
所以使拷貝更高效把将、正確而且對分割問題免疫的簡單的方式是建立指針的容器而不是對象的容器。但是指針容器也有自己的問題汗茄，詳見條款7和條款33秸弛。

• 條款4.調(diào)用empty()而不是檢查size()是否為0

empty的典型實現(xiàn)是一個返回size()==0結(jié)果的內(nèi)聯(lián)函數(shù)。
對于所有的標(biāo)準(zhǔn)容器洪碳，empty是一個常數(shù)時間的操作递览，但對于一些list實現(xiàn)，size花費線性時間瞳腌。
list中有一個變量用于記錄元素個數(shù)绞铃。特殊的是，list::splice()用于拼接兩個list嫂侍，為了達(dá)到splice的高效率儿捧，在splice時可能不更新size，而在調(diào)用size時遍歷list計算size挑宠，
這就會導(dǎo)致size()花費線性時間而不是常數(shù)時間菲盾。
但書中沒有說empty()為什么一定是常數(shù)時間。
所以我看了下我所用的QT中l(wèi)ist::empty()的實現(xiàn)方式各淀，發(fā)現(xiàn)list是由循化鏈表實現(xiàn)的懒鉴，empty()的實現(xiàn)是判斷頭節(jié)點的下個節(jié)點是否還是頭結(jié)點，因此為常數(shù)時間碎浇。
所以我的理解是：由于STL的實現(xiàn)方式不同临谱，empty()的效率比0 == size()更加穩(wěn)定(如循環(huán)鏈表實現(xiàn)的List)。

• 條款5.區(qū)間成員函數(shù)優(yōu)先于與之對應(yīng)的單元素成員函數(shù)

本文以insert的單元素版本和區(qū)間版本說明奴璃，區(qū)間成員函數(shù)優(yōu)點有三：

1. 省去了沒有必要的函數(shù)調(diào)用悉默，調(diào)用1次與調(diào)用n次，即使將單元素版本聲明為內(nèi)聯(lián)苟穆，也有可能不會成為內(nèi)聯(lián)抄课。
2. 每次insert單元素唱星，要將插入位置后的所有元素進(jìn)行移動，進(jìn)行拷貝跟磨，區(qū)間insert則先算好一共要插入的總數(shù)魏颓，然后將插入位置后的元素只整體挪動一次
3. 看原因3前需要先看Part2.條款14中，了解序列容器插入元素時內(nèi)存的重新分配機(jī)制吱晒。多次插入單元素可能導(dǎo)致內(nèi)存多次重新分配甸饱，而區(qū)間插入則一次性分配足夠的空間，然后進(jìn)行插入仑濒。

常用區(qū)間成員函數(shù)整理：
區(qū)間構(gòu)造：

container::container(InputIterator begin, InputIterator end); 

begin和end為舊容器中叹话，被拷貝區(qū)間的起始

區(qū)間插入：

序列容器：void container::insert(iterator position,InputIterator begin, InputIterator end); 
關(guān)聯(lián)容器：void container::insert(lnputIterator begin, InputIterator end);//關(guān)聯(lián)容器使用自己的比較函數(shù)決定插入元素放在哪

begin和end為舊容器中，要插到新容器中的區(qū)間起始
position為新容器中墩瞳，要插入位置的迭代器驼壶，新元素插入到該迭代器之前

區(qū)間刪除：

C++11以上: iterator container::erase(iterator begin, iterator end);
C++11以下: 關(guān)聯(lián)容器erase()返回值void

將容器中[begin, end)前閉后開區(qū)間內(nèi)的元素刪除

區(qū)間賦值：

void container::assign(InputIterator begin, InputIterator end);

begin和end為舊容器中，被拷貝區(qū)間的起始

• 條款6.當(dāng)心C++編譯器最煩人的分析機(jī)制

按照條款5中所說喉酌，嘗試使用list的區(qū)間構(gòu)造热凹，以一個文件中的全部內(nèi)容構(gòu)造一個list對象data

ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

上面這段代碼乍一看好像沒有問題，從文件的begin開始泪电，一直迭代到NULL般妙，即文件末尾，以此區(qū)間內(nèi)的元素構(gòu)造對象data相速。
但是編譯器會將第二句代碼解析為一個函數(shù)聲明碟渺。問題出在構(gòu)造時使用了一個匿名迭代器。
目前最好的解決方式突诬，是在數(shù)據(jù)聲明中避免使用匿名迭代器對象苫拍。

ifstream dataFile("ints.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd;
list<int> data(dataBegin, dataEnd);

• 條款7.如果在容器中包含了通過new操作創(chuàng)建的指針，切記在容器對象析構(gòu)前將指針delete掉

可以通過遍歷容器釋放指針旺隙，這樣做能行绒极，但不是異常安全的。
如果在向容器中放入和釋放指針時有異常拋出蔬捷，同樣會有資源泄露垄提。
所以最安全的做法是用引用計數(shù)智能指針（如Boost::shared_ptr）容器代替指針容器。
ps.不要創(chuàng)建auto_ptr的容器抠刺，并指望其中的指針被自動刪除塔淤，詳見下一條款

• 條款8.切勿創(chuàng)建包含auto_ptr的容器對象

auto_ptr最大的古怪在于它的拷貝構(gòu)造和賦值操作符摘昌，會將被拷貝的指針置為NULL速妖。
STL算法中的sort()采用的快速排序算法，會用臨時對象拷貝vector中的值作為基準(zhǔn)值聪黎。
這將導(dǎo)致vector<auto_ptr>調(diào)用sort()時罕容，其中的值被臨時對象拷貝备恤，vector中的值被置為NULL，臨時對象在作用域結(jié)束時釋放了該auto_ptr锦秒。
ps.C++標(biāo)準(zhǔn)委員會做了很多使vector<auto_ptr>不被編譯通過露泊，并最終在C++11中移除了auto_ptr.

• 條款9.慎重選擇刪除元素的方法

9.1.1. 對于連續(xù)內(nèi)存的容器(vector、deuqe和string)旅择，刪除元素的最好辦法是使用erase-remove

vec.erase( std::remove(vec.begin(), vec.end(), value), vec.end());

erase-remove講解：先要說一下erase和remove惭笑，

std::remove (Itertor first, Itertor last, const T& val);
    是<algorithm>中的算法，通過傳入的迭代器確定容器遍歷區(qū)間生真，將區(qū)間中不等于val的元素依次拷貝到區(qū)間中的前端沉噩。
    完成遍歷之后即確定了一段由first起始，沒有val值的新區(qū)間柱蟀，
    最后返回該新區(qū)間后一個位置的迭代器

iterator erase (iterator first, iterator last);
    將前開后閉區(qū)間[first, last)中的元素刪除川蒙，返回last

erase-remove:
    先通過remove將容器遍歷，將不等于value值的元素放在容器前端新區(qū)間
    再將新區(qū)間后一個位置的迭代器和容器的end()傳入erase长已，將新區(qū)間以外的部分刪除

9.1.2. 對于list畜眨，erase-remove同樣適用，但list::remove()更有效(詳見條款44)

list.remove(value);
從list中移除所有值等于value的元素

9.1.3. 對于關(guān)聯(lián)容器(set术瓮、multiset康聂、map、multimap)胞四，刪除元素正確且高效的方法是調(diào)用erase（高效的原因詳見條款19）早抠，不要對關(guān)聯(lián)容器使用std::remove（詳見條款22）

set.erase(value);
從set中刪除所有值為value的元素（multiset中也是刪除所有）

ps.書中提到，序列容器erase會返回下一個位置的迭代器撬讽，而關(guān)聯(lián)容器erase返回void蕊连，所以序列容器可以通過iter = vec.erase(iter)獲得erase后有效的迭代器，而關(guān)聯(lián)容器則要通過set.erase(iter++)后置++的方式獲得游昼。
不過我在QtCreator和VisualStudio2005兩個編譯器都試了下甘苍，關(guān)聯(lián)容器erase的返回值已經(jīng)是下一個元素的迭代器了，兩種容器可以都通過iter = vec.erase(iter)有效迭代烘豌，但對于序列容器不要使用vec.erase(iter++),因為序列容器調(diào)用erase后载庭，會使被刪除元素之后所有的迭代器失效（雖然QtCreator對此有優(yōu)化，但在visual studio中的確如此廊佩，還是不要這么使用的好）囚聚。

9.2. 要刪除容器中滿足特定判別式的所有對象，序列容器使用erase-remove_if标锄，list使用list::remove_if顽铸，關(guān)聯(lián)容器使用遍歷+erase(沒有erase_if)

bool badvalue(int); //特定判別式

vec.erase( std::remove_if( vec.begin(),  vec.end(),  badvalue));
    序列容器，遍歷vec料皇，刪除使badvalue返回true的對象

list.remove_if(badvalue);
    list::remove_if是刪除使badvalue返回true的對象的最好辦法

for(auto iter = set.begin(); iter != set.end(); /*for第三個參數(shù)什么也不做*/)
{
    if(badvalue(*i))  set.erase(iter++);
    else  ++iter;
}

如有錯誤谓松，歡迎指正