容器

條款1：仔細(xì)選擇你的容器

C++提供了很多可供程序員使用的容器：
（1） 標(biāo)準(zhǔn)STL序列容器：vector均函，string，deque和list
（2） 標(biāo)準(zhǔn)STL關(guān)聯(lián)容器：set峡蟋，multiset晶通，map和multimap
（5） vector<char>可以作為string的替代品
（6） vector作為標(biāo)準(zhǔn)關(guān)聯(lián)容器的替代品
（7） 幾種標(biāo)準(zhǔn)非STL容器璃氢，包括數(shù)組、bitset狮辽、valarray一也、stack、queue和priority_queue
又新增了一些容器喉脖，包括：array椰苟，unordered容器，還有tuple容器树叽。

不同容器有不同的優(yōu)缺點(diǎn)舆蝴，用戶需要根據(jù)實(shí)際應(yīng)用的特點(diǎn)綜合決定使用哪種容器，如：vector是一種可以默認(rèn)使用的序列類型题诵，當(dāng)很頻繁地對(duì)序列中部進(jìn)行插入和刪除時(shí)應(yīng)該用list洁仗，當(dāng)大部分插入和刪除發(fā)生在序列的頭或尾時(shí)可以選擇deque這種數(shù)據(jù)結(jié)構(gòu)。

條款2：小心對(duì)“容器無(wú)關(guān)代碼”的幻想

本條款要告誡程序員：編寫與容器無(wú)關(guān)的代碼是沒(méi)有必要的性锭。
有人想編寫這樣的程序赠潦，剛開始時(shí)使用vector存儲(chǔ)，之后由于需求的變化篷店，將vector改為deque或者list祭椰，其他代碼不變臭家。實(shí)際上疲陕，這基本上是做不到的。這是因?yàn)椋?strong>不同的序列容器所對(duì)應(yīng)了不同的迭代器钉赁、指針和引用的失效規(guī)則蹄殃，此外，不同的容器支持的操作也不相同你踩，如：vector支持reserve()和capacity()诅岩，而deque和list不支持讳苦；即使是相同的操作，復(fù)雜度也不一樣（如：insert）吩谦，這會(huì)讓你的系統(tǒng)產(chǎn)生意想不到的瓶頸鸳谜。

此外，鼓勵(lì)程序員在聲明容器和迭代器的時(shí)候使用typedef進(jìn)行重命名式廷，這能夠?qū)δ愕某绦蜻M(jìn)行封轉(zhuǎn)咐扭，從而使用起來(lái)更簡(jiǎn)單，如有下面一個(gè)map容器：

map<string,vectorWidget>::iterator,CIStringCompare>;

如要用const_iterator遍歷這個(gè)map滑废，你需不止一次地寫下：

map<string, vectorWidget>::iterator, CIStringCompare>::const_iterator

如果使用typedef蝗肪，會(huì)快速方便很多。

條款3：使容器里對(duì)象的拷貝操作輕量而正確

容器容納了對(duì)象蠕趁，但不是你給它們的那個(gè)對(duì)象薛闪。當(dāng)你向容器中插入一個(gè)對(duì)象時(shí)，你插入的是該對(duì)象的拷貝而不是它本身俺陋；當(dāng)你從容器中獲取一個(gè)對(duì)象時(shí)豁延，你獲取的是容器中對(duì)象的拷貝。
拷貝是STL的基本工作方式倔韭。當(dāng)你刪除或者插入某個(gè)對(duì)象時(shí)术浪，現(xiàn)有容器中的元素會(huì)移動(dòng)（拷s貝）；當(dāng)你使用了排序算法寿酌，remove胰苏、uniquer或者他們的同類，rotate或者reverse醇疼，對(duì)象會(huì)移動(dòng)（拷貝）硕并。
一個(gè)使拷貝更高效、正確的方式是建立指針的容器而不是對(duì)象的容器秧荆，即保存對(duì)象的指針而不是對(duì)象倔毙，然而，指針的容器有它們自己STL相關(guān)的頭疼問(wèn)題乙濒，改進(jìn)的方法是采用智能指針陕赃。

條款4：用empty來(lái)代替檢查size()是否為0

對(duì)于任意容器c，寫下

if (c.size() == 0)

本質(zhì)上等價(jià)于寫下

if (c.empty())

但是為什么第一種方式比第二種優(yōu)呢颁股？理由很簡(jiǎn)單：對(duì)于所有的標(biāo)準(zhǔn)容器么库，empty是一個(gè)常數(shù)時(shí)間的操作，但對(duì)于一些list實(shí)現(xiàn)甘有，size花費(fèi)線性時(shí)間诉儒。
這什么造成list這么麻煩？為什么不能也提供一個(gè)常數(shù)時(shí)間的size亏掀？如果size是一個(gè)常數(shù)時(shí)間操作忱反，當(dāng)進(jìn)行增加/刪除操作時(shí)每個(gè)list成員函數(shù)必須更新list的大小泛释，也包括了splice，這會(huì)造成splice的效率降低（現(xiàn)在的splice是常量級(jí)的）温算，反之怜校，如果splice不必修改list大小，那么它就是常量級(jí)地注竿，而size則變?yōu)榫€性復(fù)雜度韭畸，因此，設(shè)計(jì)者需要權(quán)衡這兩個(gè)操作的算法：一個(gè)或者另一個(gè)可以是常數(shù)時(shí)間操作蔓搞。

條款5：盡量使用區(qū)間成員函數(shù)代替單元素操作

給定兩個(gè)vector胰丁，v1和v2，怎樣使v1的內(nèi)容和v2的后半部分一樣喂分？
可行的解決方案有：
（1）使用區(qū)間函數(shù)assign：

v1.assign(v2.begin() + v2.size() / 2, v2.end());

（2）使用單元素操作：

vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end();
++ci) 
v1.push_back(*ci);

（3）使用copy區(qū)間函數(shù)

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));

（4）使用insert區(qū)間函數(shù)

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());

最優(yōu)的方案是assign方案锦庸，理由如下：
首先，使用區(qū)間函數(shù)的好處是：
● 一般來(lái)說(shuō)使用區(qū)間成員函數(shù)可以輸入更少的代碼蒲祈。
● 區(qū)間成員函數(shù)會(huì)導(dǎo)致代碼更清晰更直接了當(dāng)甘萧。
使用copy區(qū)間函數(shù)存在的問(wèn)題是：
【1】 需要編寫更多的代碼，比如：v1.clear()梆掸，這個(gè)與insert區(qū)間函數(shù)類似
【2】 copy沒(méi)有表現(xiàn)出循環(huán)扬卷，但是在copy中的確存在一個(gè)循環(huán)，這會(huì)降低性能
使用insert單元素版本的代碼對(duì)你征收了三種不同的性能稅酸钦，分別為：
【1】 沒(méi)有必要的函數(shù)調(diào)用怪得；
【2】 無(wú)效率地把v中的現(xiàn)有元素移動(dòng)到它們最終插入后的位置的開銷；
【3】 重復(fù)使用單元素插入而不是一個(gè)區(qū)間插入必須處理內(nèi)存分配卑硫。

下面進(jìn)行總結(jié)：
說(shuō)明：參數(shù)類型iterator表示容器的迭代器類型徒恋，也就是container::iterator，參數(shù)類型InputIterator表示可以接受任何輸入迭代器欢伏。
【1】 區(qū)間構(gòu)造
所有標(biāo)準(zhǔn)容器都提供這種形式的構(gòu)造函數(shù)：

container::container(InputIterator begin,
// 區(qū)間的起點(diǎn)
InputIterator end);
// 區(qū)間的終點(diǎn)

【2】區(qū)間插入
所有標(biāo)準(zhǔn)序列容器都提供這種形式的insert：

void container::insert(iterator position,
// 區(qū)間插入的位置
InputIterator begin,
// 插入?yún)^(qū)間的起點(diǎn) 
InputIterator end);
// 插入?yún)^(qū)間的終點(diǎn)

關(guān)聯(lián)容器使用它們的比較函數(shù)來(lái)決定元素要放在哪里入挣，所以它們了省略position參數(shù)。

void container::insert(lnputIterator begin, InputIterator end);

【3】區(qū)間刪除
每個(gè)標(biāo)準(zhǔn)容器都提供了一個(gè)區(qū)間形式的erase硝拧，但是序列和關(guān)聯(lián)容器的返回類型不同径筏。序列容器提供了這個(gè)：

iterator container::erase(iterator begin, iterator end);

而關(guān)聯(lián)容器提供這個(gè)：

void
container::erase(iterator begin, iterator end);

為什么不同？解釋是如果erase的關(guān)聯(lián)容器版本返回一個(gè)迭代器（被刪除的那個(gè)元素的下一個(gè)）會(huì)招致一個(gè)無(wú)法接受的性能下降.
注意這個(gè)特點(diǎn)在新版本的STL中已經(jīng)解決了

【4】 區(qū)間賦值
所有標(biāo)準(zhǔn)列容器都提供了區(qū)間形式的assign：

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

條款7：當(dāng)使用new得指針的容器時(shí)障陶，記得在銷毀容器前delete那些指針

條款8：永不建立auto_ptr的容器**//注意滋恬，在新版本中auto_ptr已經(jīng)不再被使用

條款9：在刪除選項(xiàng)中仔細(xì)選擇

（1）假定你有一個(gè)標(biāo)準(zhǔn)STL容器，c咸这，容納int夷恍，

Container<int> c;

而你想把c中所有值為1963的對(duì)象都去魔眨，則不同的容器類型采用的方法不同：沒(méi)有一種是通用的.

• 如果采用連續(xù)內(nèi)存容器(vector媳维、queue和string)酿雪，最好的方法是erase-remove慣用法：

c.erase(remove(c.begin(), c.end(), 1963),c.end());
// 當(dāng)c是vector、string
// 或deque時(shí)侄刽，erase-remove慣用法是去除特定值的元素的最佳方法

• 對(duì)于list指黎，最有效的方法是直接使用remove函數(shù)：

c.remove(1963);

• 對(duì)于關(guān)聯(lián)容器，解決問(wèn)題的適當(dāng)方法是調(diào)用erase：

c.erase(1963);
// 當(dāng)c是標(biāo)準(zhǔn)關(guān)聯(lián)容器時(shí),erase成員函數(shù)是去除特定值的元素的最佳方法

（2）讓我們換一下問(wèn)題：不是從c中除去每個(gè)有特定值的元素州丹，而是消除下面判斷式返回真的每個(gè)對(duì)象：

bool badValue( int x);
// 返回x是否是“bad”

• 對(duì)于序列容器（vector醋安、list、deque和string）墓毒，只需要將remove換成remove_if即可：

// 當(dāng)c是vector吓揪、string
// 或deque時(shí)這是去掉badValue返回真的對(duì)象的最佳方法
c.erase(remove_if(c.begin(), c.end(), badValue),c.end());

// 當(dāng)c是list時(shí)這是去掉badValue返回真的對(duì)象的最佳方法
c.remove_if(badValue);

• 對(duì)于關(guān)聯(lián)容器，有兩種方法處理該問(wèn)題所计，一個(gè)更容易編碼柠辞，另一個(gè)更高效≈麟剩“更容
  易但效率較低”的解決方案用remove_copy_if把我們需要的值拷貝到一個(gè)新容器中叭首，然后把原容器的內(nèi)容和新的交換：
  “更高效”的解決方案是直接從原容器刪除元素。不過(guò)踪栋，因?yàn)殛P(guān)聯(lián)容器沒(méi)有提供類似remove_if的成員函數(shù)焙格，所以我們必須寫一個(gè)循環(huán)來(lái)迭代c中的元素，和原來(lái)一樣刪除元素：

AssocContainer<int> c;
...
for(AssocContainer<int>::iterator i = c.begin();i != c.end();){
    if(badValue(*i))
         c.erase(i++);
    else
         ++i;
}

• 對(duì)于vector夷都、string眷唉、list和deque，必須利用erase的返回值囤官。那個(gè)返回值正是我們需要的：一旦刪除完成厢破，它就是指向緊接在被刪元素之后的元素的有效迭代器。換句話說(shuō)治拿，我們這么寫：

for(SeqContainer<int>::iterator i = c.begin(); i != c.end();){
    if(badValue(*i)){
        i = c.erase(i);
      // 通過(guò)把erase的返回值賦給i來(lái)保持i有效
    } 
   else
       ++i;
}

條款12：對(duì)STL容器線程安全性的期待現(xiàn)實(shí)一些

在工程中多線程操作STL的場(chǎng)景應(yīng)該還是比較常見的摩泪，一個(gè)典型的例子就是用其來(lái)做生產(chǎn)者——消費(fèi)者模型的隊(duì)列或者其他共享隊(duì)列，這樣為了應(yīng)對(duì)線程安全問(wèn)題我們必須自己對(duì)容器操作進(jìn)行封裝劫谅。這是我自己實(shí)現(xiàn)的的封裝類:

template< typename Container>    
// 獲取和釋放容器的互斥量的類的模板核心见坑；
class Lock {                    
    public :                         
    // 忽略了很多細(xì)節(jié)
       Lock( const Containers container) : c(container){  
          // 在構(gòu)造函數(shù)獲取互斥量       
          getMutexFor(c); 
       }
      ~Lock(){
           // 在析構(gòu)函數(shù)里釋放它
           releaseMutexFor(c); 
       }
  private:
      const Container& c;
};

原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明： 轉(zhuǎn)載自董的博客
本文鏈接地址: http://dongxicheng.org/cpp/effective-stl-part1/