一、STL六大部件為：

（1）容器（Containers）

（2）分配器（Allocators）

（3）算法（Algorithm）

（4）迭代器（Iterators）

（5）適配器（Adapters）

（6）仿函數(shù)（Functors）

其相互之間的關(guān)系如下圖：

通過(guò)一個(gè)例子了解這六大部件的基本用法：

在上例中涂臣，分配器可以不寫(xiě)盾计，編譯器會(huì)自動(dòng)添加分配器售担。

二、復(fù)雜度的概念

在上述所介紹的復(fù)雜度中署辉，只有n足夠大時(shí)族铆，不同復(fù)雜度之間的區(qū)別才能夠被察覺(jué)。

三哭尝、前閉后開(kāi)區(qū)間

從上圖可以看出：end指的是最后一個(gè)元素的下一個(gè)元素哥攘。

四、C++11中的for循環(huán)的新的形式

上述代碼中紅色部分說(shuō)明：{}也會(huì)形成一個(gè)數(shù)據(jù)聚合體材鹦。

五逝淹、C++11中的auto

六、容器的分類(lèi)

容器大致可以分為序列式容器與關(guān)聯(lián)式容器兩大類(lèi)桶唐。

（1）array

array的數(shù)據(jù)結(jié)構(gòu)是一個(gè)兩端封閉的數(shù)據(jù)空間栅葡，所以對(duì)于array必須指定其尺寸。這也就是說(shuō)array是一個(gè)靜態(tài)空間莽红，一旦配置了就不能再改變了妥畏。

測(cè)試代碼：

timestart = clock(); // 開(kāi)始計(jì)時(shí)

qsort(c.data(),ASIZE,sizeof(long),compareLongs); // 快速排序邦邦，利用仿函數(shù)來(lái)指定排序規(guī)則

long* pItem = (long*)bsearch(&target,(c.data()),ASIZE,sizeof(long),compareLongs); // 二分法查找安吁，利用二分法查找的前提是所查找的對(duì)象必須經(jīng)過(guò)排序處理。

利用clock()-timestart就能夠得到所耗費(fèi)的時(shí)間燃辖。

（2）vector

vector的數(shù)據(jù)結(jié)構(gòu)是允許在一側(cè)進(jìn)行數(shù)據(jù)操作的后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)鬼店。

array是一個(gè)靜態(tài)空間，所以如果要擴(kuò)充array的空間就必須執(zhí)行以下操作：

<1>配置一個(gè)新的更大的空間黔龟；

<2>將舊的空間中的數(shù)據(jù)依次遷移至新的空間中妇智；

<3>將舊的數(shù)據(jù)空間釋放。

vector則會(huì)動(dòng)態(tài)的擴(kuò)充vector空間氏身。vector以?xún)蓚€(gè)迭代器start和finish分別指向配置的連續(xù)空間中的已經(jīng)使用的范圍巍棱，并以迭代器end_of_storage指向整塊連續(xù)空間（包括備用空間）的尾端。一般vector中配置的空間可能比實(shí)際需要的空間更大一些蛋欣，以備將來(lái)可能的擴(kuò)充航徙。動(dòng)態(tài)增加大小，并不是在原空間之后接續(xù)新的空間（因?yàn)闊o(wú)法保證原空間之后尚有可供配置的空間）陷虎，而是以原大小的兩倍另外配置一塊較大的空間到踏，然后將原空間中的數(shù)據(jù)拷貝至新的空間，然后再在新的空間上構(gòu)造新的元素尚猿，并釋放原有空間窝稿。所以對(duì)于vector中的操作，一旦其配置空間發(fā)生重新設(shè)置凿掂，指向原有vector的所有迭代器就會(huì)全部失效伴榔。

vector的常用函數(shù)：begin、end、size踪少、capacity骗灶、empty、front秉馏、back耙旦、push_back、erase萝究、resize免都、insert等。

vector的迭代器：vector的迭代器應(yīng)能夠提供*帆竹、->绕娘、++、--栽连、+险领、-、+=秒紧、-=操作绢陌。普通的指針就能夠提供上述操作，同時(shí)還能夠滿(mǎn)足vector對(duì)于隨機(jī)存取的需求熔恢，所以普通的指針都可以作為vector的迭代器脐湾。vector提供的Random Access iterators。

vector::iterator vciterator1; 其類(lèi)型就是int*

vector::iterator vciterator2;? 其類(lèi)型就是X*

注意以下auto的使用：

auto所指代的實(shí)際是一種迭代器類(lèi)型叙淌。

利用find算法得到vetor容器中與target相同的字符串秤掌，返回其在容器中的位置。

（3）list

list的數(shù)據(jù)結(jié)構(gòu)相對(duì)于vector所采用的數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜鹰霍，其優(yōu)勢(shì)在于每次插入或刪除一個(gè)元素闻鉴，就會(huì)配置或釋放一個(gè)元素空間，因此list對(duì)于空間的運(yùn)用絕對(duì)的精準(zhǔn)茂洒，一點(diǎn)也不浪費(fèi)孟岛。

list數(shù)據(jù)結(jié)構(gòu)可以看做是一個(gè)雙向鏈表，其鏈表節(jié)點(diǎn)分別指向起一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)获黔。因?yàn)閘ist節(jié)點(diǎn)不能保證在存儲(chǔ)空間上是連續(xù)存在的蚀苛，所以不能夠像vector一樣用普通指針作為迭代器。list迭代器必須有能力進(jìn)行正確的operator==玷氏、operator!= 堵未、operator*(取的是節(jié)點(diǎn)的數(shù)據(jù)值,reference)、operator->（取用的是節(jié)點(diǎn)的成員盏触，pointer）渗蟹、operator++（節(jié)點(diǎn)前移）块饺、operator--（節(jié)點(diǎn)后退）。list是一個(gè)雙向鏈表雌芽，所以其迭代器必須具備前移授艰、后移能力。list提供的是一個(gè)Bidirectional iterators世落。

list的一個(gè)重要的性質(zhì)：插入insert和接合操作splice都不會(huì)造成原有的list迭代器失效淮腾；list的元素刪除操作（erase）只有使指向被刪除元素的迭代器失效，其余不受影響屉佳。

常用函數(shù)：

void push_back(const T& x) // 插入要素作為尾節(jié)點(diǎn)

void push_front(const T& x) // 插入要素作為頭結(jié)點(diǎn)

iterator erase(iterator position) // 刪除迭代器所指向的節(jié)點(diǎn)

void pop_back() // 移除尾節(jié)點(diǎn)

void pop_front() // 移除頭結(jié)點(diǎn)

void clear() // 清空

void remove(const T& value) // 將數(shù)值為value的所有元素移除

void unique() // 移除數(shù)值相同的連續(xù)元素谷朝。注意：只有“連續(xù)且相同的元素”，才會(huì)被移除只剩一個(gè)

void splice(iterator position,list& x) // 將x接合于position所指位置之前

void splice(iterator position, list&, iterator i) // 將i所指向的元素結(jié)合于position所指向的元素之前武花，position和i可以指向同一個(gè)list

void merge(list& x) //將x合并到*this身上圆凰。兩個(gè)list的內(nèi)容都必須首先經(jīng)過(guò)增序排列。

void reverse() // 將this中的內(nèi)容逆向重置

void sort() // list 不使用STL算法sort(),使用自身定義的sort函數(shù)体箕。因?yàn)镾TL中的sort算法只接受Random Access iterators专钉。

看一下以下例子：

int iv[5] = {5,6,7,8};

listilist2{iv,iv+5};

// 一個(gè)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的功能會(huì)受到一定的限制，但是單向鏈表所占用的空間更小争群，一些操作的效率更高回怜。

slist與list相似大年，其插入（insert）换薄、移除（erase）、接合（splice）等操作不會(huì)造成原有迭代器的失效翔试。在STL中轻要，插入操作都會(huì)將新的元素插入到指定位置之前。作為一個(gè)單向鏈表垦缅，slist沒(méi)有辦法可以回頭定位之前的要素冲泥，必須從頭開(kāi)始。所以除非slist起點(diǎn)處附近的區(qū)域之外壁涎，在其他位置進(jìn)行插入或移除操作都會(huì)比較復(fù)雜凡恍。

slist不提供push_back操作，提供push_front操作怔球，因此slist的元素次序會(huì)和元素插入進(jìn)來(lái)的次序相反嚼酝。

（6）deque

deque是一個(gè)雙向開(kāi)口的連續(xù)線性空間，可以在頭尾兩端分別進(jìn)行元素的插入與刪除操作竟坛。

deque和vector的最大差異闽巩，一在于deque允許在頭部進(jìn)行元素的插入或刪除操作钧舌；二是deque是沒(méi)有容量capacity的觀念的。deque是動(dòng)態(tài)地以分段連續(xù)空間組合而成的涎跨，隨時(shí)可以添加一段新的空間并將其鏈接起來(lái)洼冻。所有deque沒(méi)有必要提供空間保留(reserver)功能。

deque的中控器：

deque在邏輯上看來(lái)是一個(gè)連續(xù)空間隅很，由此可以聯(lián)想到array與vector撞牢。其中，array無(wú)法成長(zhǎng)叔营；vector只能夠在尾部增長(zhǎng)普泡，而且其在尾部增長(zhǎng)也是一個(gè)表面的假象，其過(guò)程實(shí)際是：<1>另外尋覓更大的存儲(chǔ)空間审编；<2>將原數(shù)據(jù)復(fù)制到新的存儲(chǔ)空間撼班；<3>釋放原有空間。如果vector在分配空間時(shí)都會(huì)留有一定的余量垒酬，那么vector的成長(zhǎng)的代價(jià)就太大了砰嘁！

deque是由一段一段的定量連續(xù)空間組成，一旦有必要在deque的前端或尾端進(jìn)行增加新的空間勘究，便會(huì)配置一段定量連續(xù)空間矮湘，并將此空間串接在整個(gè)deque的頭端或尾端。

deque的最大任務(wù)在于在這些分段的定量連續(xù)空間上口糕，維護(hù)其整體連續(xù)的假象缅阳，并且能夠提供一個(gè)隨機(jī)存取的接口，避免vector的三部曲景描。為了能夠?qū)崿F(xiàn)以上十办，deque需要一個(gè)復(fù)雜的迭代器架構(gòu)。deque使用一塊map（不是STL中的map容器）作為主控超棺。此處的map是一小塊連續(xù)空間向族，其中每一個(gè)中元素(node，節(jié)點(diǎn))都是一個(gè)指針棠绘，指向另外一段較大的連續(xù)線性空間（緩沖區(qū)）件相。緩沖區(qū)才是deque的存儲(chǔ)主體。

deque的迭代器應(yīng)當(dāng)具有的結(jié)構(gòu)：（1）必須能夠指出緩沖區(qū)在哪兒;（2）必須能夠判斷迭代器是否已經(jīng)處于其所在緩沖區(qū)的邊緣氧苍。如果位于邊緣夜矗，那么一旦前進(jìn)或者后退就會(huì)跳至下一個(gè)或者上一個(gè)緩沖區(qū)中。為此deque必須能夠?qū)崿F(xiàn)對(duì)map中控的控制让虐。迭代器結(jié)構(gòu)：cur紊撕、first、last澄干、node

deque的常用操作：

void push_back(const T& x) ? ?// 插入要素作為尾節(jié)點(diǎn)

void push_front(const T& x) ? // 插入要素作為頭結(jié)點(diǎn)

iterator erase(iterator position) // 刪除迭代器所指向的節(jié)點(diǎn)

void pop_back() ? ? ? // 移除尾節(jié)點(diǎn)

void pop_front() ? ? ?// 移除頭結(jié)點(diǎn)

void clear() ? ? ? ? ? ? // 清空

(7)stack

stack是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)逛揩，只有一個(gè)出口柠傍。stack允許新增元素、移除元素辩稽、取得最頂端元素惧笛。但是除了最頂端之外，沒(méi)有任何辦法可以存取stack中的其他元素逞泄。也就是說(shuō)stack不允許存在遍歷行為患整。這意味著stack是沒(méi)有迭代器的膏萧。

stack是以某種現(xiàn)有容器作為底部結(jié)構(gòu)乎完，將其接口改變旋奢，使其符合“先進(jìn)后出”的特性迈着，以此形成一個(gè)stack。deque是一個(gè)雙開(kāi)口的數(shù)據(jù)結(jié)構(gòu)昆码，如果以deque作為底部結(jié)構(gòu)并將其頭端開(kāi)口封閉湿镀，就形成了一個(gè)stack椎侠。STL在缺省情況下就是采用deque作為其底部容器憔四。由于stack是以其底部容器完成所有功能膀息，因此被稱(chēng)之為adapter（配接器）。STL stack往往不被歸類(lèi)為容器了赵，而被歸類(lèi)為container adapter潜支。

（8）queue

queue是一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，有兩個(gè)出口柿汛。queue允許新增元素冗酿、移除元素、從最低端加入元素络断、取出最頂端元素裁替，但是除了最底端可以加入元素、最頂端可以取出元素外妓羊，沒(méi)有任何其他方法可以存取queue中的其他元素胯究。queue不存在遍歷行為。

queue是以某種現(xiàn)有容器作為底部結(jié)構(gòu)躁绸，將其接口改變，使其符合“先進(jìn)先出”的特性臣嚣，以此形成一個(gè)queue净刮。deque是一個(gè)雙開(kāi)口的數(shù)據(jù)結(jié)構(gòu)，如果以deque作為底部結(jié)構(gòu)并將其頭端入口和底端出口封閉硅则，就形成了一個(gè)queue淹父。STL在缺省情況下就是采用deque作為其底部容器。queue同樣是一種適配器怎虫。queue沒(méi)有迭代器暑认。

以上介紹的都是序列式容器困介，關(guān)聯(lián)式容器與序列式容器的本質(zhì)區(qū)別是：序列式容器通過(guò)元素在容器中的位置順序存儲(chǔ)和訪問(wèn)元素；關(guān)聯(lián)式容器通過(guò)鍵（key）來(lái)存儲(chǔ)與訪問(wèn)容器中的元素蘸际。

常見(jiàn)的關(guān)聯(lián)式容器包括：map座哩、set、multimap以及multiset粮彤。

map：關(guān)聯(lián)數(shù)組根穷，元素通過(guò)鍵值對(duì)來(lái)存儲(chǔ)和讀取。

set：大小可變的集合导坟，支持通過(guò)鍵實(shí)現(xiàn)的快速讀取屿良。

multimap：支持同一個(gè)鍵多次出現(xiàn)的map類(lèi)型。

multiset：支持同一個(gè)鍵多次出現(xiàn)的set類(lèi)型惫周。

關(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必須具有相同的鍵類(lèi)型和值類(lèi)型?

map<k,v>m(b,e) ?創(chuàng)建map類(lèi)型的對(duì)象m逊躁，存儲(chǔ)迭代器b和e標(biāo)記的范圍內(nèi)的所有元素的副本似踱。

map定義的類(lèi)型：

map<k,v>::key_type? ? ? ? 在map容器中，用作索引的鍵的類(lèi)型

map<k,v>::mapped_type ? 在map容器中稽煤，鍵所關(guān)聯(lián)的值得類(lèi)型

map<k,v>::value_type? ? ? 一個(gè)pair類(lèi)型核芽，其first元素具有Map::key_type類(lèi)型，second元素則為map<k,v>::mapped_type類(lèi)型

使用下標(biāo)訪問(wèn)map對(duì)象：

map<string,string>A;

A[“aa”] = 1酵熙；

將會(huì)如下執(zhí)行：

(1)在A中查找鍵為aa的元素轧简，未找到;

(2)將新的鍵值對(duì)插入A中;

(3)讀取新插入的元素，將該值賦值為1匾二。

由此可見(jiàn)：如果該鍵已經(jīng)存在與容器中哮独，則map的下標(biāo)運(yùn)算與vector的下標(biāo)運(yùn)算是相同的，返回該鍵所關(guān)聯(lián)的值察藐。當(dāng)所查找的鍵不存在時(shí)皮璧，map容器會(huì)為該鍵創(chuàng)建一個(gè)新的元素。

利用下標(biāo)進(jìn)行map元素的讀取是非常不可取的分飞，如果該鍵不存在與map容器中悴务，那么下標(biāo)操作將會(huì)插入一個(gè)新的要素。如何判斷某一個(gè)鍵值是否存在與map容器中譬猫？

方法一：使用count方法

使用count獲取map中K值的出現(xiàn)次數(shù)讯檐。在map中羡疗，K值出現(xiàn)的次數(shù)只能是0或1，所以可以利用該方法判斷map中某個(gè)值是否存在别洪。

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類(lèi)型的值，表示刪除的元素的個(gè)數(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)[]操作符蒸其，而且沒(méi)有定義mapped_type類(lèi)型。在set容器中库快，value_type不是pair類(lèi)型摸袁，而是key_type相同的類(lèi)型，其指的都是set中存儲(chǔ)的元素類(lèi)型义屏。set中存儲(chǔ)的元素僅僅是鍵靠汁，而沒(méi)有所關(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將一個(gè)key映射到一個(gè)數(shù)組的下標(biāo)，數(shù)組的每一個(gè)元素都是一個(gè)鏈表兄墅，鏈表中存放的是value值踢星。數(shù)組中存放的value的個(gè)數(shù)除以數(shù)組的長(zhǎng)度就是load factor，表示hash table已經(jīng)加載的程度隙咸。load_factor()返回當(dāng)前的加載因子沐悦。max_load_factor為最大加載因子，如果加載因子超過(guò)這個(gè)值將會(huì)引起rehash扎瓶。

unordered_multiset與set相似所踊，都不支持下標(biāo)操作。

(11)分配器

默認(rèn)的分配器:

直接使用分配器：

不建議直接使用分配器概荷。