一.現(xiàn)有哪些標準容器？按照什么標準分類？
● 標準STL序列容器：vector、string、deque和list。
序列式容器的共性：
構造函數(shù)可以指定個數(shù)及初始值
增加了resize(len)或resize(len, fillVal)
增加了insert(position, num, data)
增加了assign(num, data)
增加了取首尾函數(shù)：front(), back() （返回引用）
增加了后增刪函數(shù)：push_back(data), pop_back()
關注的重點是位置。
● 標準STL關聯(lián)容器：set、multiset、map和multimap
關聯(lián)式容器的共性：
實質為二叉查找樹
可自動排序（要求容器元素的類型必須支持小于運算符）
每個元素都有一個key值
增加了insert(data)（不需指定位置）
增加了find(key)（返回第一個；若查不到，返回end()）
增加了erase(key)（刪除所有關鍵字為key的元素）
增加了count(key)
增加了lower_bound(key), upper_bound(key)
增加了equal_range(key)
關注的重點是key，實際上，前面所講的所謂序列化容器，也可以歸為特殊的關聯(lián)容器：key為position（位置）的關聯(lián)容器！
回憶一下，許多腳本里都提供下標不為int的泛化數(shù)組，我們是不是可以反過來看：通常意義上的數(shù)組只是泛化世界的一個實例呢？
前面我們從用戶的角度，將容器分為序列性與關聯(lián)性兩種，現(xiàn)在，從設計者的角度，具體來說，也就是從內存分配的角度，將容器分為連續(xù)內存容器和基于節(jié)點的容器兩種：
● 連續(xù)內存容器（也叫做基于數(shù)組的容器）：vector、string和deque
在一個或多個（動態(tài)分配）的內存塊中保存它們的元素。如果一個新元素被插入或者已存元素被刪除，其他在同一個內存塊的元素就必須向上或者向下移動來為新元素提供空間或者填充原來被刪除的元素所占的空間。這種移動影響了效率和異常安全。
● 基于節(jié)點的容器：list和slist，所有的標準關聯(lián)容器
在每個內存塊（動態(tài)分配）中只保存一個元素。容器元素的插入或刪除只影響指向節(jié)點的指針，而不是節(jié)點自己的內容。所以當有東西插入或刪除時，元素值不需要移動。
二.選擇容器的原則是什么？有什么道理？
標準中提到的原則：
vector、list和deque提供給程序員不同的復雜度，因此應該這么用：vector是一種可以默認使用的序列類型，當很頻繁地對序列中部進行插入和刪除時應該用list，當大部分插入和刪除發(fā)生在序列的頭或尾時可以選擇deque這種數(shù)據(jù)結構
實際采用的原則：
● 你需要“可以在容器的任意位置插入一個新元素”的能力嗎？如果是，你需要序列容器，關聯(lián)容器做不到。
● 你關心元素在容器中的順序嗎？如果不，散列容器就是可行的選擇。否則，你要避免使用散列容器。
● 必須使用標準C++中的容器嗎？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一類迭代器？如果必須是隨機訪問迭代器，在技術上你就只能限于vector、deque和string。
● 當插入或者刪除數(shù)據(jù)時，是否非常在意容器內現(xiàn)有元素的移動？如果是，你就必須放棄連續(xù)內存容器。
● 容器中的數(shù)據(jù)的內存布局需要兼容C嗎？如果是，你就只能用vector。
● 查找速度很重要嗎？如果是，你就應該看看散列容器，排序的vector和標準的關聯(lián)容器——大概是這個順序。
● 你介意如果容器的底層使用了引用計數(shù)嗎？如果是，你就得避開string，因為很多string的實現(xiàn)是用引用計數(shù)。于是你得重新審核你的string，你可以考慮使用vector<char>。
● 你需要插入和刪除的事務性語義嗎？也就是說，你需要有可靠地回退插入和刪除的能力嗎？如果是，你就需要使用基于節(jié)點的容器。如果你需要多元素插入（比如，以范圍的方式）的事務性語義，你就應該選擇list，因為list是唯一提供多元素插入事務性語義的標準容器。事務性語義對于有興趣寫異常安全代碼的程序員來說非常重要。
● 你要把迭代器、指針和引用的失效次數(shù)減到最少嗎？如果是，你就應該使用基于節(jié)點的容器，因為在這些容器上進行插入和刪除不會使迭代器、指針和引用失效（除非它們指向你刪除的元素）。一般來說，在連續(xù)內存容器上插入和刪除會使所有指向容器的迭代器、指針和引用失效。
● 你需要具有有以下特性的序列容器嗎：1）可以使用隨機訪問迭代器；2）只要沒有刪除而且插入只發(fā)生在容器結尾，指針和引用的數(shù)據(jù)就不會失效？這個一個非常特殊的情況，但如果你遇到這種情況，deque就是你夢想的容器。（有趣的是，當插入只在容器結尾時，deque的迭代器也可能會失效，deque是唯一一個“在迭代器失效時不會使它的指針和引用失效”的標準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()); // ??！良好定義的行為！
}
四.容量與重新分配
STL通常會比要求的多分配一些內存，元素erase后也不立即釋放內存，這樣的好處是不必頻繁得“申請->釋放->申請”，不僅影響效率，而且增加內存碎片。
當預先分配得內存不夠時，會有一個重新分配得過程，例如：
對于vector和string，是以realloc等價的思想來增長。這個類似于realloc的操作有四個部分：
1. 分配新的內存塊，它有容器目前容量的幾倍。在大部分實現(xiàn)中，vector和string的容量每次以2為因數(shù)增
長。也就是說，當容器必須擴展時，它們的容量每次翻倍。
2. 把所有元素從容器的舊內存拷貝到它的新內存。
3. 銷毀舊內存中的對象。
4. 回收舊內存。
重新分配導致兩個后果：
1.分配，回收，拷貝和析構，那些步驟都很昂貴
2.所有指向vector或string中的迭代器、指針和引用都會失效，因為新內存并不是舊內存在物理上得延續(xù)，它可能是在內存中任何一個位置。
所以，如何盡量減少重新分配的機會，非常重要，STL提供reserve，可以做到這一點。例如：
vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
期間，可以保證不會有重新分配。
相關函數(shù)：
● size()告訴你容器中有多少元素。它沒有告訴你容器為它容納的元素分配了多少內存。
● capacity()告訴你容器在它已經(jīng)分配的內存中可以容納多少元素。
● resize(Container::size_type n)強制把容器改為容納n個元素。
● reserve(Container::size_type n)強制容器把它的容量改為至少n，提供的n不小于當前大小。
五.如何修改容器占用內存？
只能用swap，例如：
vector<Contestant>(contestants).swap(contestants);
表達式vector<Contestant>(contestants)建立一個臨時vector，它是contestants的一份拷貝：vector的拷貝構造函數(shù)做了這個工作。但是，vector的拷貝構造函數(shù)只分配拷貝的元素需要的內存，所以這個臨時vector沒有多余的
容量。然后我們讓臨時vector和contestants交換數(shù)據(jù)，這時我們完成了，contestants只有臨時變量的修整過的容
量，而這個臨時變量則持有了曾經(jīng)在contestants中的發(fā)脹的容量。在這里（這個語句結尾），臨時vector被銷
毀，因此釋放了以前contestants使用的內存。
