一、STL六大部件為：
（1）容器（Containers）
（2）分配器（Allocators）
（3）算法（Algorithm）
（4）迭代器（Iterators）
（5）適配器（Adapters）
（6）仿函數(shù)（Functors）
其相互之間的關(guān)系如下圖：
通過一個例子了解這六大部件的基本用法：
在上例中，分配器可以不寫，編譯器會自動添加分配器。
二、復(fù)雜度的概念
在上述所介紹的復(fù)雜度中，只有n足夠大時，不同復(fù)雜度之間的區(qū)別才能夠被察覺。
三、前閉后開區(qū)間
從上圖可以看出：end指的是最后一個元素的下一個元素。
四、C++11中的for循環(huán)的新的形式
上述代碼中紅色部分說明：{}也會形成一個數(shù)據(jù)聚合體。
五、C++11中的auto
六、容器的分類
容器大致可以分為序列式容器與關(guān)聯(lián)式容器兩大類。
（1）array
array的數(shù)據(jù)結(jié)構(gòu)是一個兩端封閉的數(shù)據(jù)空間，所以對于array必須指定其尺寸。這也就是說array是一個靜態(tài)空間，一旦配置了就不能再改變了。
測試代碼：
timestart = clock(); // 開始計時
qsort(c.data(),ASIZE,sizeof(long),compareLongs); // 快速排序，利用仿函數(shù)來指定排序規(guī)則
long* pItem = (long*)bsearch(&target,(c.data()),ASIZE,sizeof(long),compareLongs); // 二分法查找，利用二分法查找的前提是所查找的對象必須經(jīng)過排序處理。
利用clock()-timestart就能夠得到所耗費的時間。
（2）vector
vector的數(shù)據(jù)結(jié)構(gòu)是允許在一側(cè)進(jìn)行數(shù)據(jù)操作的后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。
array是一個靜態(tài)空間，所以如果要擴充array的空間就必須執(zhí)行以下操作：
<1>配置一個新的更大的空間；
<2>將舊的空間中的數(shù)據(jù)依次遷移至新的空間中；
<3>將舊的數(shù)據(jù)空間釋放。
vector則會動態(tài)的擴充vector空間。vector以兩個迭代器start和finish分別指向配置的連續(xù)空間中的已經(jīng)使用的范圍，并以迭代器end_of_storage指向整塊連續(xù)空間（包括備用空間）的尾端。一般vector中配置的空間可能比實際需要的空間更大一些，以備將來可能的擴充。動態(tài)增加大小，并不是在原空間之后接續(xù)新的空間（因為無法保證原空間之后尚有可供配置的空間），而是以原大小的兩倍另外配置一塊較大的空間，然后將原空間中的數(shù)據(jù)拷貝至新的空間，然后再在新的空間上構(gòu)造新的元素，并釋放原有空間。所以對于vector中的操作，一旦其配置空間發(fā)生重新設(shè)置，指向原有vector的所有迭代器就會全部失效。
vector的常用函數(shù)：begin、end、size、capacity、empty、front、back、push_back、erase、resize、insert等。
vector的迭代器：vector的迭代器應(yīng)能夠提供*、->、++、--、+、-、+=、-=操作。普通的指針就能夠提供上述操作，同時還能夠滿足vector對于隨機存取的需求，所以普通的指針都可以作為vector的迭代器。vector提供的Random Access iterators。
vector::iterator vciterator1; 其類型就是int*
vector::iterator vciterator2;? 其類型就是X*
注意以下auto的使用：
auto所指代的實際是一種迭代器類型。
利用find算法得到vetor容器中與target相同的字符串，返回其在容器中的位置。
（3）list
list的數(shù)據(jù)結(jié)構(gòu)相對于vector所采用的數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜，其優(yōu)勢在于每次插入或刪除一個元素，就會配置或釋放一個元素空間，因此list對于空間的運用絕對的精準(zhǔn)，一點也不浪費。
list數(shù)據(jù)結(jié)構(gòu)可以看做是一個雙向鏈表，其鏈表節(jié)點分別指向起一個節(jié)點和后一個節(jié)點。因為list節(jié)點不能保證在存儲空間上是連續(xù)存在的，所以不能夠像vector一樣用普通指針作為迭代器。list迭代器必須有能力進(jìn)行正確的operator==、operator!= 、operator*(取的是節(jié)點的數(shù)據(jù)值,reference)、operator->（取用的是節(jié)點的成員，pointer）、operator++（節(jié)點前移）、operator--（節(jié)點后退）。list是一個雙向鏈表，所以其迭代器必須具備前移、后移能力。list提供的是一個Bidirectional iterators。
list的一個重要的性質(zhì)：插入insert和接合操作splice都不會造成原有的list迭代器失效；list的元素刪除操作（erase）只有使指向被刪除元素的迭代器失效，其余不受影響。
常用函數(shù)：
void push_back(const T& x) // 插入要素作為尾節(jié)點
void push_front(const T& x) // 插入要素作為頭結(jié)點
iterator erase(iterator position) // 刪除迭代器所指向的節(jié)點
void pop_back() // 移除尾節(jié)點
void pop_front() // 移除頭結(jié)點
void clear() // 清空
void remove(const T& value) // 將數(shù)值為value的所有元素移除
void unique() // 移除數(shù)值相同的連續(xù)元素。注意：只有“連續(xù)且相同的元素”，才會被移除只剩一個
void splice(iterator position,list& x) // 將x接合于position所指位置之前
void splice(iterator position, list&, iterator i) // 將i所指向的元素結(jié)合于position所指向的元素之前，position和i可以指向同一個list
void merge(list& x) //將x合并到*this身上。兩個list的內(nèi)容都必須首先經(jīng)過增序排列。
void reverse() // 將this中的內(nèi)容逆向重置
void sort() // list 不使用STL算法sort(),使用自身定義的sort函數(shù)。因為STL中的sort算法只接受Random Access iterators。
看一下以下例子：
int iv[5] = {5,6,7,8};
listilist2{iv,iv+5};
// 一個ilist中存放0 2 99 3 4
ite = find(ilist.begin(),ilist.end(),99);
ilist.splice(ite,ilist2); ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 0 2 5 6 7 8 99 3 4
ilist.reverse(); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 4 3 99 8 7 6 5 2 0
ilist.sort(); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 0 2 3 4 5 6 7 8 9 99
（4）forward-list
（5）slist
slist是一種單向鏈表。slist與list的區(qū)別在于：slist的迭代器屬于單向的Forward iterator。list的迭代器屬于雙向的Bidirectional iterator。因此slist的功能會受到一定的限制，但是單向鏈表所占用的空間更小，一些操作的效率更高。
slist與list相似，其插入（insert）、移除（erase）、接合（splice）等操作不會造成原有迭代器的失效。在STL中，插入操作都會將新的元素插入到指定位置之前。作為一個單向鏈表，slist沒有辦法可以回頭定位之前的要素，必須從頭開始。所以除非slist起點處附近的區(qū)域之外，在其他位置進(jìn)行插入或移除操作都會比較復(fù)雜。
slist不提供push_back操作，提供push_front操作，因此slist的元素次序會和元素插入進(jìn)來的次序相反。
（6）deque
deque是一個雙向開口的連續(xù)線性空間，可以在頭尾兩端分別進(jìn)行元素的插入與刪除操作。
deque和vector的最大差異，一在于deque允許在頭部進(jìn)行元素的插入或刪除操作；二是deque是沒有容量capacity的觀念的。deque是動態(tài)地以分段連續(xù)空間組合而成的，隨時可以添加一段新的空間并將其鏈接起來。所有deque沒有必要提供空間保留(reserver)功能。
deque的中控器：
deque在邏輯上看來是一個連續(xù)空間，由此可以聯(lián)想到array與vector。其中，array無法成長；vector只能夠在尾部增長，而且其在尾部增長也是一個表面的假象，其過程實際是：<1>另外尋覓更大的存儲空間；<2>將原數(shù)據(jù)復(fù)制到新的存儲空間；<3>釋放原有空間。如果vector在分配空間時都會留有一定的余量，那么vector的成長的代價就太大了！
deque是由一段一段的定量連續(xù)空間組成，一旦有必要在deque的前端或尾端進(jìn)行增加新的空間，便會配置一段定量連續(xù)空間，并將此空間串接在整個deque的頭端或尾端。
deque的最大任務(wù)在于在這些分段的定量連續(xù)空間上，維護其整體連續(xù)的假象，并且能夠提供一個隨機存取的接口，避免vector的三部曲。為了能夠?qū)崿F(xiàn)以上，deque需要一個復(fù)雜的迭代器架構(gòu)。deque使用一塊map（不是STL中的map容器）作為主控。此處的map是一小塊連續(xù)空間，其中每一個中元素(node，節(jié)點)都是一個指針，指向另外一段較大的連續(xù)線性空間（緩沖區(qū)）。緩沖區(qū)才是deque的存儲主體。
deque的迭代器應(yīng)當(dāng)具有的結(jié)構(gòu)：（1）必須能夠指出緩沖區(qū)在哪兒;（2）必須能夠判斷迭代器是否已經(jīng)處于其所在緩沖區(qū)的邊緣。如果位于邊緣，那么一旦前進(jìn)或者后退就會跳至下一個或者上一個緩沖區(qū)中。為此deque必須能夠?qū)崿F(xiàn)對map中控的控制。迭代器結(jié)構(gòu)：cur、first、last、node
deque的常用操作：
void push_back(const T& x) ? ?// 插入要素作為尾節(jié)點
void push_front(const T& x) ? // 插入要素作為頭結(jié)點
iterator erase(iterator position) // 刪除迭代器所指向的節(jié)點
void pop_back() ? ? ? // 移除尾節(jié)點
void pop_front() ? ? ?// 移除頭結(jié)點
void clear() ? ? ? ? ? ? // 清空
(7)stack
stack是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，只有一個出口。stack允許新增元素、移除元素、取得最頂端元素。但是除了最頂端之外，沒有任何辦法可以存取stack中的其他元素。也就是說stack不允許存在遍歷行為。這意味著stack是沒有迭代器的。
stack是以某種現(xiàn)有容器作為底部結(jié)構(gòu)，將其接口改變，使其符合“先進(jìn)后出”的特性，以此形成一個stack。deque是一個雙開口的數(shù)據(jù)結(jié)構(gòu)，如果以deque作為底部結(jié)構(gòu)并將其頭端開口封閉，就形成了一個stack。STL在缺省情況下就是采用deque作為其底部容器。由于stack是以其底部容器完成所有功能，因此被稱之為adapter（配接器）。STL stack往往不被歸類為容器，而被歸類為container adapter。
（8）queue
queue是一個先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，有兩個出口。queue允許新增元素、移除元素、從最低端加入元素、取出最頂端元素，但是除了最底端可以加入元素、最頂端可以取出元素外，沒有任何其他方法可以存取queue中的其他元素。queue不存在遍歷行為。
queue是以某種現(xiàn)有容器作為底部結(jié)構(gòu)，將其接口改變，使其符合“先進(jìn)先出”的特性，以此形成一個queue。deque是一個雙開口的數(shù)據(jù)結(jié)構(gòu)，如果以deque作為底部結(jié)構(gòu)并將其頭端入口和底端出口封閉，就形成了一個queue。STL在缺省情況下就是采用deque作為其底部容器。queue同樣是一種適配器。queue沒有迭代器。
以上介紹的都是序列式容器，關(guān)聯(lián)式容器與序列式容器的本質(zhì)區(qū)別是：序列式容器通過元素在容器中的位置順序存儲和訪問元素；關(guān)聯(lián)式容器通過鍵（key）來存儲與訪問容器中的元素。
常見的關(guān)聯(lián)式容器包括：map、set、multimap以及multiset。
map：關(guān)聯(lián)數(shù)組，元素通過鍵值對來存儲和讀取。
set：大小可變的集合，支持通過鍵實現(xiàn)的快速讀取。
multimap：支持同一個鍵多次出現(xiàn)的map類型。
multiset：支持同一個鍵多次出現(xiàn)的set類型。
關(guān)聯(lián)容器共享大部分序列容器的操作，不提供：front、push_front、pop_front 、back、push_back、pop_back。
（9）Map/Multimap
map容器的定義：
map<k,v>a
map<k,v>m(m2) ?創(chuàng)建m2的副本，m與m2必須具有相同的鍵類型和值類型?
map<k,v>m(b,e) ?創(chuàng)建map類型的對象m，存儲迭代器b和e標(biāo)記的范圍內(nèi)的所有元素的副本。
map定義的類型：
map<k,v>::key_type? ? ? ? 在map容器中，用作索引的鍵的類型
map<k,v>::mapped_type ? 在map容器中，鍵所關(guān)聯(lián)的值得類型
map<k,v>::value_type? ? ? 一個pair類型，其first元素具有Map::key_type類型，second元素則為map<k,v>::mapped_type類型
使用下標(biāo)訪問map對象：
map<string,string>A;
A[“aa”] = 1；
將會如下執(zhí)行：
(1)在A中查找鍵為aa的元素，未找到;
(2)將新的鍵值對插入A中;
(3)讀取新插入的元素，將該值賦值為1。
由此可見：如果該鍵已經(jīng)存在與容器中，則map的下標(biāo)運算與vector的下標(biāo)運算是相同的，返回該鍵所關(guān)聯(lián)的值。當(dāng)所查找的鍵不存在時，map容器會為該鍵創(chuàng)建一個新的元素。
利用下標(biāo)進(jìn)行map元素的讀取是非常不可取的，如果該鍵不存在與map容器中，那么下標(biāo)操作將會插入一個新的要素。如何判斷某一個鍵值是否存在與map容器中？
方法一：使用count方法
使用count獲取map中K值的出現(xiàn)次數(shù)。在map中，K值出現(xiàn)的次數(shù)只能是0或1，所以可以利用該方法判斷map中某個值是否存在。
int num = 0;
if(Wordcount.count(“AAA”))
{
? ? // 插入
? ?num = Wordcount[“AAA”];
}
方法二：使用find方法
int occurs = 0;
map<string,int>::iterator it = Wordcount.find(“AAA”);
If(it != Wordcount.end())
{
? ? num = it->second;
}
map要素的插入：
（1）wordcount.insert(map<string,int>::value_type(“A”,1));
（2）wordcount.insert(make_pair(“A”,1));
（3）typedef? map<string,int>::value_type? valType;
wordcount.insert(valType(“A”,1));
map元素的刪除：
m.erase(k)：刪除m中鍵為k的元素，返回size_type類型的值，表示刪除的元素的個數(shù)。
m.erase(p)：刪除m中迭代器p所指向的元素，p不能為m.end()，返回值為void。
m.erase(b，e) ：一定范圍內(nèi)的元素的刪除，b需在e的前方，返回值為void。
multimap的特性與用法與map完全相同，唯一的差別在于multimap允許存在重復(fù)的鍵值。
(10)set/multiset
set不支持下標(biāo)[]操作符，而且沒有定義mapped_type類型。在set容器中，value_type不是pair類型，而是key_type相同的類型，其指的都是set中存儲的元素類型。set中存儲的元素僅僅是鍵，而沒有所關(guān)聯(lián)的值。在set中插入元素：
(1)set<string> strset1;?
?strset1.insert(“A”);
(2)set<int> niset2;
niset2.insert(nivec.begin(),nivec.end());
在set中查找元素：
niset.find(1); // 返回值1存在，0不存在
(11)unordered_multiset/unordered_multimap
上述兩種容器都是用到hash table。hash table將一個key映射到一個數(shù)組的下標(biāo)，數(shù)組的每一個元素都是一個鏈表，鏈表中存放的是value值。數(shù)組中存放的value的個數(shù)除以數(shù)組的長度就是load factor，表示hash table已經(jīng)加載的程度。load_factor()返回當(dāng)前的加載因子。max_load_factor為最大加載因子，如果加載因子超過這個值將會引起rehash。
unordered_multiset與set相似，都不支持下標(biāo)操作。
(11)分配器
默認(rèn)的分配器:
直接使用分配器：
不建議直接使用分配器。
