一.現(xiàn)有哪些標(biāo)準(zhǔn)容器,？按照什么標(biāo)準(zhǔn)分類,？
● 標(biāo)準(zhǔn)STL序列容器：vector、string,、deque和list,。
序列式容器的共性：
構(gòu)造函數(shù)可以指定個數(shù)及初始值
增加了resize(len)或resize(len, fillVal)
增加了insert(position, num, data)
增加了assign(num, data)
增加了取首尾函數(shù)：front(), back() （返回引用）
增加了后增刪函數(shù)：push_back(data), pop_back()

關(guān)注的重點(diǎn)是位置。

● 標(biāo)準(zhǔn)STL關(guān)聯(lián)容器：set,、multiset,、map和multimap
關(guān)聯(lián)式容器的共性：
實(shí)質(zhì)為二叉查找樹
可自動排序（要求容器元素的類型必須支持小于運(yùn)算符）
每個元素都有一個key值
增加了insert(data)（不需指定位置）
增加了find(key)（返回第一個；若查不到,，返回end()）
增加了erase(key)（刪除所有關(guān)鍵字為key的元素）
增加了count(key)
增加了lower_bound(key), upper_bound(key)
增加了equal_range(key)

關(guān)注的重點(diǎn)是key,，實(shí)際上，前面所講的所謂序列化容器,，也可以歸為特殊的關(guān)聯(lián)容器：key為position（位置）的關(guān)聯(lián)容器,！
回憶一下，許多腳本里都提供下標(biāo)不為int的泛化數(shù)組,，我們是不是可以反過來看：通常意義上的數(shù)組只是泛化世界的一個實(shí)例呢,？

前面我們從用戶的角度，將容器分為序列性與關(guān)聯(lián)性兩種,，現(xiàn)在,，從設(shè)計者的角度，具體來說,，也就是從內(nèi)存分配的角度,，將容器分為連續(xù)內(nèi)存容器和基于節(jié)點(diǎn)的容器兩種：

● 連續(xù)內(nèi)存容器（也叫做基于數(shù)組的容器）：vector、string和deque
在一個或多個（動態(tài)分配）的內(nèi)存塊中保存它們的元素,。如果一個新元素被插入或者已存元素被刪除,，其他在同一個內(nèi)存塊的元素就必須向上或者向下移動來為新元素提供空間或者填充原來被刪除的元素所占的空間。這種移動影響了效率和異常安全,。

● 基于節(jié)點(diǎn)的容器：list和slist,，所有的標(biāo)準(zhǔn)關(guān)聯(lián)容器
在每個內(nèi)存塊（動態(tài)分配）中只保存一個元素。容器元素的插入或刪除只影響指向節(jié)點(diǎn)的指針,，而不是節(jié)點(diǎn)自己的內(nèi)容,。所以當(dāng)有東西插入或刪除時，元素值不需要移動,。

二.選擇容器的原則是什么,？有什么道理？
標(biāo)準(zhǔn)中提到的原則：
vector,、list和deque提供給程序員不同的復(fù)雜度,，因此應(yīng)該這么用：vector是一種可以默認(rèn)使用的序列類型，當(dāng)很頻繁地對序列中部進(jìn)行插入和刪除時應(yīng)該用list,，當(dāng)大部分插入和刪除發(fā)生在序列的頭或尾時可以選擇deque這種數(shù)據(jù)結(jié)構(gòu)

實(shí)際采用的原則：
● 你需要“可以在容器的任意位置插入一個新元素”的能力嗎,？如果是，你需要序列容器,，關(guān)聯(lián)容器做不到,。
● 你關(guān)心元素在容器中的順序嗎,？如果不,，散列容器就是可行的選擇,。否則,，你要避免使用散列容器。
● 必須使用標(biāo)準(zhǔn)C++中的容器嗎,？如果是,，就可以除去散列容器,、slist和rope。
● 你需要哪一類迭代器,？如果必須是隨機(jī)訪問迭代器,，在技術(shù)上你就只能限于vector、deque和string,。
● 當(dāng)插入或者刪除數(shù)據(jù)時,，是否非常在意容器內(nèi)現(xiàn)有元素的移動,？如果是，你就必須放棄連續(xù)內(nèi)存容器,。
● 容器中的數(shù)據(jù)的內(nèi)存布局需要兼容C嗎,？如果是，你就只能用vector,。
● 查找速度很重要嗎,？如果是，你就應(yīng)該看看散列容器,，排序的vector和標(biāo)準(zhǔn)的關(guān)聯(lián)容器——大概是這個順序,。
● 你介意如果容器的底層使用了引用計數(shù)嗎？如果是,，你就得避開string,，因?yàn)楹芏鄐tring的實(shí)現(xiàn)是用引用計數(shù)。于是你得重新審核你的string,，你可以考慮使用vector<char>,。
● 你需要插入和刪除的事務(wù)性語義嗎？也就是說,，你需要有可靠地回退插入和刪除的能力嗎,？如果是，你就需要使用基于節(jié)點(diǎn)的容器,。如果你需要多元素插入（比如,， 以范圍的方式）的事務(wù)性語義，你就應(yīng)該選擇list,，因?yàn)閘ist是唯一提供多元素插入事務(wù)性語義的標(biāo)準(zhǔn)容器,。事務(wù)性語義對于有興趣寫異常安全代碼的程序 員來說非常重要。
● 你要把迭代器,、指針和引用的失效次數(shù)減到最少嗎,？如果是，你就應(yīng)該使用基于節(jié)點(diǎn)的容器,，因?yàn)樵谶@些容器上進(jìn)行插入和刪除不會使迭代器,、指針和引用失效（除非它們指向你刪除的元素）。一般來說,，在連續(xù)內(nèi)存容器上插入和刪除會使所有指向容器的迭代器,、指針和引用失效。
● 你需要具有有以下特性的序列容器嗎：1）可以使用隨機(jī)訪問迭代器,；2）只要沒有刪除而且插入只發(fā)生在容器結(jié)尾,，指針和引用的數(shù)據(jù)就不會失效？這個一個非常 特殊的情況,，但如果你遇到這種情況,，deque就是你夢想的容器,。（有趣的是，當(dāng)插入只在容器結(jié)尾時,，deque的迭代器也可能會失效,，deque是唯一 一個“在迭代器失效時不會使它的指針和引用失效”的標(biāo)準(zhǔn)STL容器。）

三.使用new得指針的容器時,，需要做些什么,？
在銷毀容器前delete那些指針。例如：
struct DeleteObject {
  template<typename T> // 模板化加在這里
  void operator()(const T* ptr) const
  {
    delete ptr;
  }
}

void doSomething()
{
  deque<SpecialString*> dssp;
  ...
  for_each(dssp.begin(), dssp.end(),
  DeleteObject()); // ?。×己枚x的行為,！
}

四.容量與重新分配
STL通常會比要求的多分配一些內(nèi)存,，元素erase后也不立即釋放內(nèi)存，這樣的好處是不必頻繁得“申請->釋放->申請”,，不僅影響效率,，而且增加內(nèi)存碎片。
當(dāng)預(yù)先分配得內(nèi)存不夠時,，會有一個重新分配得過程,，例如：
對于vector和string，是以realloc等價的思想來增長,。這個類似于realloc的操作有四個部分：
1. 分配新的內(nèi)存塊,，它有容器目前容量的幾倍。在大部分實(shí)現(xiàn)中,，vector和string的容量每次以2為因數(shù)增
長,。也就是說，當(dāng)容器必須擴(kuò)展時,，它們的容量每次翻倍,。
2. 把所有元素從容器的舊內(nèi)存拷貝到它的新內(nèi)存。
3. 銷毀舊內(nèi)存中的對象,。
4. 回收舊內(nèi)存,。
重新分配導(dǎo)致兩個后果：
1.分配，回收,，拷貝和析構(gòu),，那些步驟都很昂貴
2.所有指向vector或string中的迭代器、指針和引用都會失效,，因?yàn)樾聝?nèi)存并不是舊內(nèi)存在物理上得延續(xù),，它可能是在內(nèi)存中任何一個位置。
所以,，如何盡量減少重新分配的機(jī)會,，非常重要,，STL提供reserve，可以做到這一點(diǎn),。例如：
vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
期間,，可以保證不會有重新分配。

相關(guān)函數(shù)：
● size()告訴你容器中有多少元素,。它沒有告訴你容器為它容納的元素分配了多少內(nèi)存,。
● capacity()告訴你容器在它已經(jīng)分配的內(nèi)存中可以容納多少元素。
● resize(Container::size_type n)強(qiáng)制把容器改為容納n個元素,。
● reserve(Container::size_type n)強(qiáng)制容器把它的容量改為至少n,，提供的n不小于當(dāng)前大小。

五.如何修改容器占用內(nèi)存,？
只能用swap,，例如：
vector<Contestant>(contestants).swap(contestants);
表 達(dá)式vector<Contestant>(contestants)建立一個臨時vector，它是contestants的一份拷 貝：vector的拷貝構(gòu)造函數(shù)做了這個工作,。但是,，vector的拷貝構(gòu)造函數(shù)只分配拷貝的元素需要的內(nèi)存，所以這個臨時vector沒有多余的
容量,。然后我們讓臨時vector和contestants交換數(shù)據(jù),，這時我們完成了，contestants只有臨時變量的修整過的容
量,，而這個臨時變量則持有了曾經(jīng)在contestants中的發(fā)脹的容量,。在這里（這個語句結(jié)尾），臨時vector被銷
毀,，因此釋放了以前contestants使用的內(nèi)存,。