現(xiàn)在，我們要檢查一些可以補(bǔ)充算法復(fù)雜度的重要的容器相關(guān)問(wèn)題，但首先我需要介紹一種STL容器的分類(lèi)
方法，它被討論的次數(shù)并不像它應(yīng)該的那樣多。那是連續(xù)內(nèi)存容器和基于節(jié)點(diǎn)的容器的區(qū)別。
連續(xù)內(nèi)存容器（也叫做基于數(shù)組的容器）在一個(gè)或多個(gè)（動(dòng)態(tài)分配）的內(nèi)存塊中保存它們的元素。如果一個(gè)
條款1：仔細(xì)選擇你的容器
新元素被查入或者已存元素被刪除，其他在同一個(gè)內(nèi)存塊的元素就必須向上或者向下移動(dòng)來(lái)為新元素提供空間或者填充原來(lái)被刪除的元素所占的空間。這種移動(dòng)影響了效率（參見(jiàn)條款5和14）和異常安全（就像我們將會(huì)看到的）。
標(biāo)準(zhǔn)的連續(xù)內(nèi)存容器是vector、string和deque。非標(biāo)準(zhǔn)的rope也是連續(xù)內(nèi)存容器。
基于節(jié)點(diǎn)的容器在每個(gè)內(nèi)存塊（動(dòng)態(tài)分配）中只保存一個(gè)元素。容器元素的插入或刪除只影響指向節(jié)點(diǎn)的指針，而不是節(jié)點(diǎn)自己的內(nèi)容。所以當(dāng)有東西插入或刪除時(shí)，元素值不需要移動(dòng)。表現(xiàn)為鏈表的容器——比如list和slist——是基于節(jié)點(diǎn)的，所有的標(biāo)準(zhǔn)關(guān)聯(lián)容器也是（它們的典型實(shí)現(xiàn)是平衡樹(shù)）。非標(biāo)準(zhǔn)的散列容器使用不同的基于節(jié)點(diǎn)的實(shí)現(xiàn)，就像我們將會(huì)在條款25中看到的。
利用這個(gè)不恰當(dāng)?shù)男g(shù)語(yǔ)，我們已經(jīng)準(zhǔn)備好描述一些大多數(shù)關(guān)于在容器間選擇的問(wèn)題。在這個(gè)討論中，我略過(guò)考慮非STL類(lèi)容器（比如，數(shù)組、bitset等），因?yàn)楫吘惯@是本關(guān)于STL的書(shū)。
● 你需要“可以在容器的任意位置插入一個(gè)新元素”的能力嗎？如果是，你需要序列容器，關(guān)聯(lián)容器做不到。
● 你關(guān)心元素在容器中的順序嗎？如果不，散列容器就是可行的選擇。否則，你要避免使用散列容器。
● 必須使用標(biāo)準(zhǔn)C++中的容器嗎？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一類(lèi)迭代器？如果必須是隨機(jī)訪問(wèn)迭代器，在技術(shù)上你就只能限于vector、deque和string，但你也可能會(huì)考慮rope（關(guān)于rope的更多信息在條款50）。如果需要雙向迭代器，你就用不了slist（參見(jiàn)條款50）和散列容器的一般實(shí)現(xiàn)（參見(jiàn)條款25）。
● 當(dāng)插入或者刪除數(shù)據(jù)時(shí)，是否非常在意容器內(nèi)現(xiàn)有元素的移動(dòng)？如果是，你就必須放棄連續(xù)內(nèi)存容器（參見(jiàn)條款5）。
● 容器中的數(shù)據(jù)的內(nèi)存布局需要兼容C嗎？如果是，你就只能用vector（參見(jiàn)條款16）。
● 查找速度很重要嗎？如果是，你就應(yīng)該看看散列容器（參見(jiàn)條款25），排序的vector（參見(jiàn)條款23）和標(biāo)準(zhǔn)的關(guān)聯(lián)容器——大概是這個(gè)順序。
● 你介意如果容器的底層使用了引用計(jì)數(shù)嗎？如果是，你就得避開(kāi)string，因?yàn)楹芏鄐tring的實(shí)現(xiàn)是用引用計(jì)數(shù)（參見(jiàn)條款13）。你也不能用rope，因?yàn)闄?quán)威的rope實(shí)現(xiàn)是基于引用計(jì)數(shù)的（參見(jiàn)條款50）。
于是你得重新審核你的string，你可以考慮使用vector<char>。
● 你需要插入和刪除的事務(wù)性語(yǔ)義嗎？也就是說(shuō)，你需要有可靠地回退插入和刪除的能力嗎？如果是，你就需要使用基于節(jié)點(diǎn)的容器。如果你需要多元素插入（比如，以范圍的方式——參見(jiàn)條款5）的事務(wù)性語(yǔ)義，你就應(yīng)該選擇list，因?yàn)閘ist是唯一提供多元素插入事務(wù)性語(yǔ)義的標(biāo)準(zhǔn)容器。事務(wù)性語(yǔ)義對(duì)于有興趣寫(xiě)異常安全代碼的程序員來(lái)說(shuō)非常重要。（事務(wù)性語(yǔ)義也可以在連續(xù)內(nèi)存容器上實(shí)現(xiàn)，但會(huì)有一個(gè)性能開(kāi)銷(xiāo)，而且代碼不那么直觀。要了解這方面的知識(shí)，請(qǐng)參考Sutter的《Exceptional C++》的條款17[8]。）
● 你要把迭代器、指針和引用的失效次數(shù)減到最少嗎？如果是，你就應(yīng)該使用基于節(jié)點(diǎn)的容器，因?yàn)樵?br>這些容器上進(jìn)行插入和刪除不會(huì)使迭代器、指針和引用失效（除非它們指向你刪除的元素）。一般來(lái)
說(shuō)，在連續(xù)內(nèi)存容器上插入和刪除會(huì)使所有指向容器的迭代器、指針和引用失效。
● 你需要具有有以下特性的序列容器嗎：1）可以使用隨機(jī)訪問(wèn)迭代器；2）只要沒(méi)有刪除而且插入只發(fā)
條款1：仔細(xì)選擇你的容器
生在容器結(jié)尾，指針和引用的數(shù)據(jù)就不會(huì)失效？這個(gè)一個(gè)非常特殊的情況，但如果你遇到這種情況，
deque就是你夢(mèng)想的容器。（有趣的是，當(dāng)插入只在容器結(jié)尾時(shí)，deque的迭代器也可能會(huì)失效，deque
是唯一一個(gè)“在迭代器失效時(shí)不會(huì)使它的指針和引用失效”的標(biāo)準(zhǔn)STL容器。）
這些問(wèn)題幾乎不是事情的完結(jié)。比如，它們沒(méi)有關(guān)注不同的容器類(lèi)型使用不同的內(nèi)存配置策略（條款10和14
討論了這些策略的一些方面）。但是，它們已經(jīng)足夠是你信服了，除非你對(duì)元素順序、標(biāo)準(zhǔn)的一致性、迭代
器能力、內(nèi)存布局和C的兼容性、查找速度、因?yàn)橐糜?jì)數(shù)造成的行為不規(guī)則、事務(wù)性語(yǔ)義的輕松實(shí)現(xiàn)和迭
代器失效的條件沒(méi)興趣，你得在容器操作的算法復(fù)雜度上花更多的考慮時(shí)間。當(dāng)然這樣的復(fù)雜度是重要的，
但這離整個(gè)故事很遠(yuǎn)。
當(dāng)面對(duì)容器時(shí)，STL給了你很多選項(xiàng)。如果你的視線超越了STL的范圍，那就會(huì)有更多的選項(xiàng)。在選擇一個(gè)容
器前，要保證考慮了所有你的選項(xiàng)。一個(gè)“默認(rèn)容器”？我不這么認(rèn)為。
author: 我要去桂林 summary.........
聯(lián)系客服
