vector和string

所有的STL容器都很有用涤姊，但是相比于其他容器性湿，vector和string更常用苦掘。本章從多個角度覆蓋vector和string，如：為什么提倡使用 vector代替數(shù)組柱恤，怎樣改進vector和string的性能？怎樣除去過剩的內(nèi)存找爱，vector<string>是個什么東西梗顺？

條款13：盡量使用vector和string來代替動態(tài)分配的數(shù)組

使用vector和string代替動態(tài)分配的數(shù)組是個很明智的選擇，它們不僅能夠自動管理內(nèi)存（主要是自動釋放內(nèi)车摄，自動增加內(nèi)存）寺谤，還提供了很多可用的函數(shù)和類型：既有像begin、end和size這樣的成員函數(shù)练般，也有內(nèi)嵌的像iterator矗漾、 reverse_iterator或value_type的typedef。
對于string實現(xiàn)薄料，可能使用了引用計數(shù)器敞贡，這是一種那個消除了不必要的內(nèi)存分配和字符拷貝的策略，而且在很多應用中可以提高性能摄职。但這種方案在多線程環(huán)境下可能會嚴重降低性能誊役，可能的解決方法是：
（1）關閉引用計數(shù)（如果可能的話）
（2）尋找或開發(fā)一個不使用引用計數(shù)的string實現(xiàn)（或部分實現(xiàn)）替代品
（3）考慮使用vector<char>來代替string，vector實現(xiàn)不允許使用引用計數(shù)谷市，所以隱藏的多線程性能問題不會出現(xiàn)了

條款14：使用reserve避免不必要的重新分配

reserve成員函數(shù)允許你最小化必須進行的重新分配的次數(shù)蛔垢，因而可以避免真分配的開銷和迭代器/指針/引用失效。

• size()返回容器中已經(jīng)保存的元素個數(shù)
• capacity()返回容器可以保存的最大元素個數(shù)迫悠。如果要知道一個vector或string中有多少沒有被占用的內(nèi)存鹏漆，可以讓capacity() 減去size()；如果size和capacity返回同樣的值创泄，容器中就沒有剩余空間了艺玲，而下一次插入（通過insert或push_back等）會引 發(fā)重分配。
• resize(Container::size_type n)強制把容器改為容納n個元素鞠抑。調(diào)用resize之后饭聚，size將會返回n。如果n小于當前大小搁拙，容器尾部的元素會被銷毀秒梳。如果n大于當前大小，新默認 構造的元素會添加到容器尾部箕速。如果n大于當前容量酪碘，在元素加入之前會發(fā)生重新分配。
• reserve(Container::size_type n)強制容器把它的容量改為至少n盐茎，提供的n不小于當前大小婆跑。這一般強迫進行一次重新分配，因為容量需要增加庭呜。（如果n小于當前容量滑进，vector忽略 它，這個調(diào)用什么都不做募谎，string可能把它的容量減少為size()和n中大的數(shù)扶关，但string的大小沒有改變。）

條款16: 如何將vector和string的數(shù)據(jù)傳給遺留的API

我們可以將vector或者string傳遞給數(shù)組/指針類型的參數(shù)数冬，如：

• 用C風格API返回的元素初始化一個vector节槐，可以利用vector和數(shù)組潛在的內(nèi)存分布兼容性將存儲vecotr的元素的空間傳給API函數(shù)：

// C API：此函數(shù)需要一個指向數(shù)組的指針，數(shù)組最多有arraySize個double
// 而且會對數(shù)組寫入數(shù)據(jù)拐纱。它返回寫入的double數(shù)铜异，不會大于arraySize
size_t fillArray(double *pArray, size_t arraySize);
// 建立一個vector，它的大小是maxNumDoubles 
vector<double> vd(maxNumDoubles); 
// 讓fillArray把數(shù)據(jù)寫入vd秸架，然后調(diào)整vd的大小 為fillArray寫入的元素個數(shù)
vd.resize(fillArray(&vd[0], vd.size())); 

• 讓C風格API把數(shù)據(jù)放入一個vector揍庄，然后拷到你實際想要的STL容器中的主意總是有效的：

size_t fillArray(double *pArray, size_t arraySize); // 同上
vector<double> vd(maxNumDoubles); // 一樣同上
vd.resize(fillArray(&vd[0], vd.size()));
deque<double> d(vd.begin(), vd.end()); // 拷貝數(shù)據(jù)到deque
list<double> l(vd.begin(), vd.end()); // 拷貝數(shù)據(jù)到list
set<double> s(vd.begin(), vd.end()); // 拷貝數(shù)據(jù)到set

• 如何將vector和string以外的STL容器中的數(shù)據(jù)傳給C風格API？只要將容器的每個數(shù)據(jù)拷到vector东抹，然后將它們傳給API：

void doSomething(const int* pints, size_t numInts); // C API (同上)
set<int> intSet; // 保存要傳遞給API數(shù)據(jù)的set
...
vector<int> v(intSet.begin(), intSet.end()); // 拷貝set數(shù)據(jù)到vector
if (!v.empty()) doSomething(&v[0], v.size()); // 傳遞數(shù)據(jù)到API

條款17：使用“交換技巧”來修整過剩容量

實際項目中可能遇到這樣的情況：剛開始時蚂子，將大量數(shù)據(jù)插入到一個vector中，后來隨著實際的需要缭黔，將大量元素從這個vector中刪除食茎，這樣的 話，vector中會占用大量未使用的內(nèi)存（通過函數(shù)capacity()可看到結果）馏谨，如何將這些未使用的內(nèi)存釋放别渔，可采用以下幾種方法：

vector<Contestant>(contestants).swap(contestants);

表達式vector<Contestant>(contestants)建立一個臨時vector，它是 contestants的一份拷貝：vector的拷貝構造函數(shù)做了這個工作惧互。但是哎媚，vector的拷貝構造函數(shù)只分配拷貝的元素需要的內(nèi)存，所以這個臨 時vector沒有多余的容量壹哺。然后我們讓臨時vector和contestants交換數(shù)據(jù)抄伍，這時contestants只有臨時變量的修整過的容量， 而這個臨時變量則持有了曾經(jīng)在contestants中的發(fā)脹的容量管宵。在這里（這個語句結尾）截珍，臨時vector被銷毀，因此釋放了以前 contestants使用的內(nèi)存
同樣的技巧可以應用于string：

string s;
... // 使s變大箩朴，然后刪除所有它的字符
string(s).swap(s); // 在s上進行“收縮到合適”

條款18：避免使用vector<bool>

作為一個STL容器岗喉，vector<bool>有兩個問題。
它不是一個STL容器炸庞。它并未實際保存一個bool, 而是用位域的概念進行了封裝钱床。

標準庫提供了兩個替代品，它們能滿足幾乎所有需要埠居。
第一個是deque<bool>查牌。deque提供了幾乎所有vector所提供的（唯一值得 注意的是reserve和capacity）事期，而deque<bool>是一個STL容器，它保存真正的bool值纸颜。
當然兽泣，deque內(nèi)部內(nèi)存不是連續(xù)的。所以不能傳遞deque<bool>中的數(shù)據(jù)給一個希望得到bool數(shù)組的C API胁孙。
第二個vector<bool>的替代品是bitset唠倦。bitset不是一個STL容器，但它是C++標準庫的一部分涮较。與STL容器不同稠鼻，它的大小（元素數(shù)量）在編譯期固定狂票，因此它不支持插入和刪除元素候齿。此外，因為它不是一個STL容器苫亦，它也不支持iterator毛肋。
標準非STL容器是指可以認為它們是容器，但是他們并不滿足STL容器的所有要求屋剑。前文提到的容器適配器stack润匙、queue及priority_queue都是標準非STL容器的一部分。此外唉匾，valarray也是標準非STL容器孕讳。
bitset：一種高效位集合操作容器。

關聯(lián)容器

條款19：了解相等和等價的區(qū)別

set中的find函數(shù)采用的是等價準則巍膘，而find算法采用的是相等準則厂财。

find算法在某個區(qū)間中查找一個元素時，需要比較兩個對象峡懈，看一個對象的值是否等于零一個對象璃饱，它對相同的定義是相等，是以operator==為基礎的肪康。
set的insert需要確定插入的元素的值是否已經(jīng)在set中了荚恶，它對相同的定義是等價，是以operator<為基礎的磷支。
兩個對象相等并不意味著它們的所有數(shù)據(jù)成員都有相等的值谒撼。
等價關系是以“在已排序的區(qū)間中對象值的相對順序”為基礎的。對于兩個對象x和y雾狈，如果按照關聯(lián)容器的排列順序廓潜，每個都不在另一個的前面，那么稱這兩個對象按照關聯(lián)容器的排列順序有等價的值。用表達式表示就是：!(x < y) && !(y < x) 為true辩蛋，x和y對于operator<有等價的值呻畸。
一般情況下，一個關聯(lián)容器的比較函數(shù)不是operator<堪澎，甚至也不是less擂错，是用戶定義的判別式，只要把<改為判別式的調(diào)用即可樱蛤。
如果有一個不區(qū)分大小寫的set<string>，我們向其中插入Persephone剑鞍，如果再插入persephone昨凡，后面一個將不會被插入，因為兩個是等價的蚁署。稍后我們使用成員函數(shù)find去查找persephone便脊，查找會成功，但是如果用find算法去查找光戈，那么查找將會失敗哪痰。

條款20：為指針的關聯(lián)容器指定比較類型

當關聯(lián)容器中保存的是對象指針時，需要自己定義比較器（不是一個函數(shù)久妆，而是一個仿函數(shù)模板）晌杰，不然關聯(lián)容器會按照指針大小進行排序，而不是指針指向的內(nèi)容筷弦。

條款21: 永遠讓比較函數(shù)對“相等的值”返回false

在關聯(lián)容器中肋演，用戶自定義比較類型時，當兩個元素相等時烂琴，應該返回false爹殊。
舉例：建立一個set，比較類型用less_equal奸绷，然后插入一個10：

set<int, less_equal<int> > s; // s以“<=”排序
s.insert(10); // 插入10
然后再插入一次10：
s.insert(10);

關聯(lián)容器對“相同”的定義是等價梗夸，因此set測試10B是否等價于10A。當執(zhí)行這個測試時号醉，它自然是使用set的比較函數(shù)反症。在這一例子 里，是operator<=扣癣，因為我們指定set的比較函數(shù)為less_equal惰帽，而less_equal意思就是operator<=。 于是父虑，set將計算這個表達式是否為真：

!(10A <= 10B) && !(10B <= 10A) // 測試10A和10B是否等價

顯然该酗，該表達式返回false，于是兩個10都會插入這個set，結果是set以擁有了兩個為10的值的拷貝而告終呜魄，也就是說它不再是一個set了悔叽。通過使用less_equal作為我們的比較類型，我們破壞了容器爵嗅！

條款22：避免原地修改set和multiset的鍵

原地修改map和multimap的鍵值是不允許的娇澎，同時，應避免原地修改set和multiset的鍵（盡管這是允許的）睹晒，因為這可能影響容器有序性的元素部分趟庄，破壞掉容器。

條款23：考慮用有序vector代替關聯(lián)容器

在你的應用中伪很，如果查找的頻繁程度比插入和刪除的高很多戚啥，那么推薦你用有序vector代替關聯(lián)容器，這主要是從內(nèi)存引用失效頻率考慮的锉试。
用vector模擬關聯(lián)數(shù)組的代碼如下：

typedef pair<string, int> Data; // 在這個例子里 "map"容納的類型
class DataCompare { // 用于比較的類
 public:
     bool operator()(const Data& lhs, // 用于排序的比較函數(shù)
     const Data& rhs) const {
         return keyLess(lhs.first, rhs.first); // keyLess在下面
     }
 
   // 用于查找的比較函數(shù)
    bool operator()(const Data& Ihs, const Data::first_type& k) const{ 
         return keyLess(lhs.first, k);
    }

   bool operator()(const Data::first_type& k,  const Data& rhs) const{
         return keyLess(k, rhs.first);
   }
 
 private:
     bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const{
         return k1 < k2;
     }
};
 
vector<Data> vd; // 代替map<string, int>
... // 建立階段：很多插入猫十，幾乎沒有查找

// 結束建立階段。（當模擬multimap時呆盖，你可能更喜歡用stable_sort 來代替）
sort(vd.begin(), vd.end(), DataCompare());  
string s; // 用于查找的值的對象
... // 開始查找階段
if (binary_search(vd.begin(), vd.end(), s, DataCompare()))... // 通過binary_search查找
vector<Data>::iterator i = lower_bound(vd.begin(), vd.end(), s, 
DataCompare()); // 再次通過lower_bound查找拖云，

對于這么使用它們的數(shù)據(jù)結構的應用來說，一個vector可能比一個關聯(lián)容器能提供更高的
性能（時間和空間上都是）应又。但不是任意的vector都會宙项，只有有序vector。因為只有有序
容器才能正確地使用查找算法——binary_search丁频、lower_bound杉允、equal_range等。但為什么一個（有序的）vector的二分法查找比一個二叉樹的二分法查找提供了
更好的性能席里？其中的一個是大小問題叔磷，另外一個是引用局部性問題。

考慮第一個大小問題奖磁。假設我們需要一個容器來容納Widget對象改基，而且，因為查找速度對
我們很重要咖为，我們考慮一個Widget的關聯(lián)容器和一個有序vector<Widget>秕狰。如果我們選擇
一個關聯(lián)容器，我們幾乎確定了要使用平衡二叉樹躁染。這樣的樹是由樹節(jié)點組成鸣哀，每個都不
僅容納了一個Widget，而且保存了一個該節(jié)點到左孩子的指針吞彤，一個到它右孩子的指針我衬，
和（典型的）一個到它父節(jié)點的指針叹放。這意味著在關聯(lián)容器中用于存儲一個 Widget的空間
開銷至少會是三個指針。

與之相對的是挠羔，當在vector中存儲Widget并沒有開銷：我們簡單地存儲一個Widget井仰。當然
，vector本身有開銷破加，在vector結尾也可能有空的（保留）空間（參見條款14）俱恶，但是每
個vector開銷是可以忽略的（通常是三個機器字，比如范舀，三個指針或兩個指針和一個int）
合是，而且如果必要的話，末尾空的空間可以通過“交換技巧”去掉（看見條款17）尿背。即使這
個附加的空間沒有去掉端仰，也并不影響下面的分析，因為當查找時不會引用那段內(nèi)存田藐。

假設我們的數(shù)據(jù)結構足夠大，它們可以分成多個內(nèi)存頁面吱七，但是vector比關聯(lián)容器需要的
頁面要少汽久。那是因為vector不需要每個Widget的開銷，而關聯(lián)容器給每個Widget上附加了
三個指針踊餐。要知道為什么這很重要景醇，假設在你使用的系統(tǒng)上一個Widget的大小是12個字節(jié)
，指針是4個字節(jié)吝岭，一個內(nèi)存頁面是4096（4K）字節(jié)三痰。忽略每個容器的開銷，當用vector保
存時窜管，你可以在一頁面上放置341個Widget散劫，但使用關聯(lián)容器時你最多只能放170個。因此
關聯(lián)容器和vector比起來幕帆，你將會使用大約兩倍的內(nèi)存获搏。如果你使用的環(huán)境可以用虛擬內(nèi)
存，就很可以容易地看出那會造成大量的頁面錯誤失乾，因此一個系統(tǒng)會因為大數(shù)據(jù)量而明顯
慢下來常熙。

實際上我在這里還是對關聯(lián)容器很樂觀的，因為我們假設在二叉樹中的節(jié)點都群集在一個
相關的小內(nèi)存頁面集中碱茁。大部分STL實現(xiàn)使用自定義內(nèi)存管理器（實現(xiàn)在容器的配置器上—
—參見條款10和11）來達到這樣的群集裸卫，但是如果你的STL實現(xiàn)沒有改進樹節(jié)點中的引用局
部性，這些節(jié)點會分散在所有你的內(nèi)存空間纽竣。那會導致更多的頁面錯誤墓贿。即使使用了自定
義群集內(nèi)存管理器，關聯(lián)容器也會導致很多頁面錯誤，因為募壕，不像連續(xù)內(nèi)存容器调炬，比如ve
ctor，基于節(jié)點的容器更難保證在容器的遍歷順序中一個挨著一個的元素在物理內(nèi)存上也
是一個挨著一個舱馅。但當進行二分查找時那種內(nèi)存組織方式（譯注：遍歷順序中一個挨著一
個的元素在物理內(nèi)存上也是一個挨著一個）正好是頁面錯誤最少的缰泡。

概要：在有序vector中存儲數(shù)據(jù)很有可能比在標準關聯(lián)容器中保存相同的數(shù)據(jù)消耗更少的
內(nèi)存；當頁面錯誤值得重視的時候代嗤，在有序vector中通過二分法查找可能比在一個標準關
聯(lián)容器中查找更快棘钞。

當然，有序vector的大缺點是它必須保持有序干毅！當一個新元素插入時宜猜，大于這個新元素的
所有東西都必須向上移一位。它和聽起來一樣昂貴硝逢，如果vector必須重新分配它的內(nèi)在內(nèi)
存（參見條款14）姨拥，則會更昂貴，因為vector中所有的元素都必須拷貝渠鸽。同樣的叫乌，如果一
個元素從vector中被刪除，所有大于它的元素都要向下移動徽缚。vector的插入和刪除都很昂
貴憨奸，但是關聯(lián)容器的插入和刪除則很輕量。這就是為什么只有當你知道你的數(shù)據(jù)結構使用
的時候查找?guī)缀醪缓筒迦牒蛣h除混合時凿试，使用有序 vector代替關聯(lián)容器才有意義

條款24：當關乎效率時應該在map::operator[]和map-insert之間仔細選擇

STL map的operator[]被設計為簡化“添加或更新”功能排宰，但事實上，當“增加”被執(zhí)行時那婉，insert比operator[]更高效板甘。當進行更新時，情形正好相反吧恃，也就是虾啦，當一個等價的鍵已經(jīng)在map里時，operator[]更高效痕寓。
理由如下：當進行“增加”操作時傲醉，operator[]會有三個函數(shù)調(diào)用：構造臨時對象，撤銷臨時對象和對對象復制呻率，而insert不會有硬毕；而對于更新操作，insert需要構造和析構對象礼仗，而operator[] 采用的對象引用吐咳，不會有這樣的效率損耗逻悠。一個較為高效的“添加或更新”功能實現(xiàn)如下：

 // map的類型
// KeyArgType和ValueArgtype是類型參數(shù)
template<typename MapType, typename KeyArgType,  typename ValueArgtype>
typename MapType::iterator
efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgtype& v)
{
  // 找到k在或應該在哪里；
  typename MapType::iterator Ib =  m.lower_bound(k); 
  // 如果Ib指向一個pair而且它的鍵等價于k...
  if(Ib != m.end() && !(m.key_comp()(k, Ib->first))) { 
       Ib->second = v; // 更新這個pair的值
       return Ib; // 并返回指向pair的迭代器
 } else{
      typedef typename MapType::value_type MVT;
      // 把pair(k, v)添加到m并返回指向新map元素的迭代器
       return m.insert(Ib, MVT(k, v)); 
 }
}

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