現(xiàn)在，我們要檢查一些可以補充算法復(fù)雜度的重要的容器相關(guān)問題，但首先我需要介紹一種STL容器的分類
方法，它被討論的次數(shù)并不像它應(yīng)該的那樣多。那是連續(xù)內(nèi)存容器和基于節(jié)點的容器的區(qū)別。
連續(xù)內(nèi)存容器（也叫做基于數(shù)組的容器）在一個或多個（動態(tài)分配）的內(nèi)存塊中保存它們的元素。如果一個
條款1：仔細(xì)選擇你的容器
新元素被查入或者已存元素被刪除，其他在同一個內(nèi)存塊的元素就必須向上或者向下移動來為新元素提供空間或者填充原來被刪除的元素所占的空間。這種移動影響了效率（參見條款5和14）和異常安全（就像我們將會看到的）。

標(biāo)準(zhǔn)的連續(xù)內(nèi)存容器是vector、string和deque。非標(biāo)準(zhǔn)的rope也是連續(xù)內(nèi)存容器。

基于節(jié)點的容器在每個內(nèi)存塊（動態(tài)分配）中只保存一個元素。容器元素的插入或刪除只影響指向節(jié)點的指針，而不是節(jié)點自己的內(nèi)容。所以當(dāng)有東西插入或刪除時，元素值不需要移動。表現(xiàn)為鏈表的容器——比如list和slist——是基于節(jié)點的，所有的標(biāo)準(zhǔn)關(guān)聯(lián)容器也是（它們的典型實現(xiàn)是平衡樹）。非標(biāo)準(zhǔn)的散列容器使用不同的基于節(jié)點的實現(xiàn)，就像我們將會在條款25中看到的。

利用這個不恰當(dāng)?shù)男g(shù)語，我們已經(jīng)準(zhǔn)備好描述一些大多數(shù)關(guān)于在容器間選擇的問題。在這個討論中，我略過考慮非STL類容器（比如，數(shù)組、bitset等），因為畢竟這是本關(guān)于STL的書。
● 你需要“可以在容器的任意位置插入一個新元素”的能力嗎？如果是，你需要序列容器，關(guān)聯(lián)容器做不到。
● 你關(guān)心元素在容器中的順序嗎？如果不，散列容器就是可行的選擇。否則，你要避免使用散列容器。

● 必須使用標(biāo)準(zhǔn)C++中的容器嗎？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一類迭代器？如果必須是隨機訪問迭代器，在技術(shù)上你就只能限于vector、deque和string，但你也可能會考慮rope（關(guān)于rope的更多信息在條款50）。如果需要雙向迭代器，你就用不了slist（參見條款50）和散列容器的一般實現(xiàn)（參見條款25）。
● 當(dāng)插入或者刪除數(shù)據(jù)時，是否非常在意容器內(nèi)現(xiàn)有元素的移動？如果是，你就必須放棄連續(xù)內(nèi)存容器（參見條款5）。
● 容器中的數(shù)據(jù)的內(nèi)存布局需要兼容C嗎？如果是，你就只能用vector（參見條款16）。
● 查找速度很重要嗎？如果是，你就應(yīng)該看看散列容器（參見條款25），排序的vector（參見條款23）和標(biāo)準(zhǔn)的關(guān)聯(lián)容器——大概是這個順序。
● 你介意如果容器的底層使用了引用計數(shù)嗎？如果是，你就得避開string，因為很多string的實現(xiàn)是用引用計數(shù)（參見條款13）。你也不能用rope，因為權(quán)威的rope實現(xiàn)是基于引用計數(shù)的（參見條款50）。
于是你得重新審核你的string，你可以考慮使用vector<char>。
● 你需要插入和刪除的事務(wù)性語義嗎？也就是說，你需要有可靠地回退插入和刪除的能力嗎？如果是，你就需要使用基于節(jié)點的容器。如果你需要多元素插入（比如，以范圍的方式——參見條款5）的事務(wù)性語義，你就應(yīng)該選擇list，因為list是唯一提供多元素插入事務(wù)性語義的標(biāo)準(zhǔn)容器。事務(wù)性語義對于有興趣寫異常安全代碼的程序員來說非常重要。（事務(wù)性語義也可以在連續(xù)內(nèi)存容器上實現(xiàn)，但會有一個性能開銷，而且代碼不那么直觀。要了解這方面的知識，請參考Sutter的《Exceptional C++》的條款17[8]。）
● 你要把迭代器、指針和引用的失效次數(shù)減到最少嗎？如果是，你就應(yīng)該使用基于節(jié)點的容器，因為在
這些容器上進(jìn)行插入和刪除不會使迭代器、指針和引用失效（除非它們指向你刪除的元素）。一般來
說，在連續(xù)內(nèi)存容器上插入和刪除會使所有指向容器的迭代器、指針和引用失效。
● 你需要具有有以下特性的序列容器嗎：1）可以使用隨機訪問迭代器；2）只要沒有刪除而且插入只發(fā)
條款1：仔細(xì)選擇你的容器
生在容器結(jié)尾，指針和引用的數(shù)據(jù)就不會失效？這個一個非常特殊的情況，但如果你遇到這種情況，
deque就是你夢想的容器。（有趣的是，當(dāng)插入只在容器結(jié)尾時，deque的迭代器也可能會失效，deque
是唯一一個“在迭代器失效時不會使它的指針和引用失效”的標(biāo)準(zhǔn)STL容器。）
這些問題幾乎不是事情的完結(jié)。比如，它們沒有關(guān)注不同的容器類型使用不同的內(nèi)存配置策略（條款10和14
討論了這些策略的一些方面）。但是，它們已經(jīng)足夠是你信服了，除非你對元素順序、標(biāo)準(zhǔn)的一致性、迭代
器能力、內(nèi)存布局和C的兼容性、查找速度、因為引用計數(shù)造成的行為不規(guī)則、事務(wù)性語義的輕松實現(xiàn)和迭
代器失效的條件沒興趣，你得在容器操作的算法復(fù)雜度上花更多的考慮時間。當(dāng)然這樣的復(fù)雜度是重要的，
但這離整個故事很遠(yuǎn)。
當(dāng)面對容器時，STL給了你很多選項。如果你的視線超越了STL的范圍，那就會有更多的選項。在選擇一個容
器前，要保證考慮了所有你的選項。一個“默認(rèn)容器”？我不這么認(rèn)為。

author: 我要去桂林 summary.........