C++ 培訓(xùn)之C++STL 一般總結(jié)(一)

一、一般介紹
      STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。
      從邏輯層次來(lái)看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；
       從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類型參數(shù)化（type parameterized）的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒(méi)有出現(xiàn)的語(yǔ)言特性--模板（template）。如果查閱任何一個(gè)版本的STL源代碼，你就會(huì)發(fā)現(xiàn)，模板作為構(gòu)成整個(gè)STL的基石是一件千真萬(wàn)確的事情。除此之外，還有許多C++的新特性為STL的實(shí)現(xiàn)提供了方便；
 
二、STL的六大組件

• 容器（Container），是一種數(shù)據(jù)結(jié)構(gòu)，如list，vector，和deques ，以模板類的方法提供。為了訪問(wèn)容器中的數(shù)據(jù)，可以使用由容器類輸出的迭代器；
• 迭代器（Iterator），提供了訪問(wèn)容器中對(duì)象的方法。例如，可以使用一對(duì)迭代器指定list或vector中的一定范圍的對(duì)象。迭代器就如同一個(gè)指針。事實(shí)上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對(duì)象；
• 算法（Algorithm），是用來(lái)操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象，函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用；
• 仿函數(shù)（Function object，仿函數(shù)(functor)又稱之為函數(shù)對(duì)象（function object），其實(shí)就是重載了()操作符的struct，沒(méi)有什么特別的地方
• 迭代適配器（Adaptor）
• 空間配制器（allocator）其中主要工作包括兩部分1.對(duì)象的創(chuàng)建與銷毀    2.內(nèi)存的獲取與釋放

以下主要討論：容器，迭代器，算法，適配器。如欲詳加了解 參見(jiàn)C++ Primer 
 
1.STL容器
1）序列式容器（Sequence containers），每個(gè)元素都有固定位置－－取決于插入時(shí)機(jī)和地點(diǎn)，和元素值無(wú)關(guān)，vector、deque、list；
    Vectors：將元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理，可以隨機(jī)存取元素（用索引直接存取），數(shù)組尾部添加或移除元素非?？焖?。但是在中部或頭部安插元素比較費(fèi)時(shí)；
    Deques：是“double-ended queue”的縮寫(xiě)，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費(fèi)時(shí)；
   Lists：雙向鏈表，不提供隨機(jī)存?。ò错樞蜃叩叫璐嫒〉脑?，O(n)），在任何位置上執(zhí)行插入或刪除動(dòng)作都非常迅速，內(nèi)部只需調(diào)整一下指針；
2）關(guān)聯(lián)式容器（Associated containers），元素位置取決于特定的排序準(zhǔn)則，和插入順序無(wú)關(guān)，set、multiset、map、multimap；
    Sets/Multisets：內(nèi)部的元素依據(jù)其值自動(dòng)排序，Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multisets內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)（實(shí)際上基于紅黑樹(shù)(RB-tree）實(shí)現(xiàn)），便于查找；
    Maps/Multimaps：Map的元素是成對(duì)的鍵值/實(shí)值，內(nèi)部的元素依據(jù)其值自動(dòng)排序，Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multimaps內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)（實(shí)際上基于紅黑樹(shù)(RB-tree）實(shí)現(xiàn)），便于查找；
另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。
  容器的比較：

	Vector	Deque	List	Set	MultiSet	Map	MultiMap
內(nèi)部結(jié)構(gòu)	dynamic array	array of arrays	double linked list	binary tree	binary tree	binary tree	binary tree
隨機(jī)存取	Yes	Yes	No	No	No	Yes(key)	No
搜索速度	慢	慢	很慢	快	快	快	快
快速插入移除	尾部	首尾	任何位置	--	--	--	--

 
2.STL迭代器 
Iterator（迭代器）模式又稱Cursor（游標(biāo)）模式，用于提供一種方法順序訪問(wèn)一個(gè)聚合對(duì)象中各個(gè)元素, 而又不需暴露該對(duì)象的內(nèi)部表示?；蛘哌@樣說(shuō)可能更容易理解：Iterator模式是運(yùn)用于聚合對(duì)象的一種模式，通過(guò)運(yùn)用該模式，使得我們可以在不知道對(duì)象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問(wèn)聚合對(duì)象中的各個(gè)元素。
迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無(wú)間隙的粘合起來(lái)，重載了*，＋＋，＝＝，?。?，＝運(yùn)算符。用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，容器提供迭代器，算法使用迭代器；
常見(jiàn)的一些迭代器類型：iterator、const_iterator、reverse_iterator和const_reverse_iterator
迭代器一般聲明使用示例
vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

            input         output
              \            /  
                forward
                     |
                bidirectional
                     |
               random access                                       
 
要注意，上面這圖表并不是表明它們之間的繼承關(guān)系：而只是描述了迭代器的種類和接口。處于圖表下層的迭代器都是相對(duì)于處于圖表上層迭代器的擴(kuò)張集。例如：forward迭代器不但擁有input和output迭代器的所有功能，還擁有更多的功能。
各個(gè)迭代器的功能如下：

迭代器類別	說(shuō)明
輸入	從容器中讀取元素。輸入迭代器只能一次讀入一個(gè)元素向前移動(dòng)， 輸入迭代器只支持一遍算法，同一個(gè)輸入迭代器不能兩遍遍歷一個(gè)序列
輸出	向容器中寫(xiě)入元素。輸出迭代器只能一次一個(gè)元素向前移動(dòng)。 輸出迭代器只支持一遍算法，統(tǒng)一輸出迭代器不能兩次遍歷一個(gè)序列
正向	組合輸入迭代器和輸出迭代器的功能，并保留在容器中的位置
雙向	組合正向迭代器和逆向迭代器的功能，支持多遍算法
隨機(jī)訪問(wèn)	組合雙向迭代器的功能與直接訪問(wèn)容器中任何元素的功能， 即可向前向后跳過(guò)任意個(gè)元素

迭代器的操作：
每種迭代器均可進(jìn)行包括表中前一種迭代器可進(jìn)行的操作。

迭代器操作	說(shuō)明
所有迭代器
p++	后置自增迭代器
++p	前置自增迭代器
輸入迭代器
*p	復(fù)引用迭代器，作為右值
p=p1	將一個(gè)迭代器賦給另一個(gè)迭代器
p==p1	比較迭代器的相等性
p!=p1	比較迭代器的不等性
輸出迭代器
*p	復(fù)引用迭代器，作為左值
p=p1	將一個(gè)迭代器賦給另一個(gè)迭代器
正向迭代器	提供輸入輸出迭代器的所有功能
雙向迭代器
--p	前置自減迭代器
p--	后置自減迭代器
隨機(jī)迭代器
p+=i	將迭代器遞增i位
p-=i	將迭代器遞減i位
p+i	在p位加i位后的迭代器
p-i	在p位減i位后的迭代器
p[i]	返回p位元素偏離i位的元素引用
p<p1	如果迭代器p的位置在p1前，返回true，否則返回false
p<=p1	p的位置在p1的前面或同一位置時(shí)返回true，否則返回false
p>p1	如果迭代器p的位置在p1后，返回true，否則返回false
p>=p1	p的位置在p1的后面或同一位置時(shí)返回true，否則返回false

只有順序容器和關(guān)聯(lián)容器支持迭代器遍歷，各容器支持的迭代器的類別如下：

容器	支持的迭代器類別	說(shuō)明
vector	隨機(jī)訪問(wèn)	一種隨機(jī)訪問(wèn)的數(shù)組類型，提供了對(duì)數(shù)組元素進(jìn)行快速隨機(jī)訪問(wèn)以及在序列尾部進(jìn)行快速的插入和刪除操作的功能?？梢栽傩枰臅r(shí)候修改其自身的大小
deque	隨機(jī)訪問(wèn)	一種隨機(jī)訪問(wèn)的數(shù)組類型，提供了序列兩端快速進(jìn)行插入和刪除操作的功能?？梢栽傩枰臅r(shí)候修改其自身的大小
list	雙向	一種不支持隨機(jī)訪問(wèn)的數(shù)組類型，插入和刪除所花費(fèi)的時(shí)間是固定的，與位置無(wú)關(guān)。
set	雙向	一種隨機(jī)存取的容器，其關(guān)鍵字和數(shù)據(jù)元素是同一個(gè)值。所有元素都必須具有惟一值。
multiset	雙向	一種隨機(jī)存取的容器，其關(guān)鍵字和數(shù)據(jù)元素是同一個(gè)值。可以包含重復(fù)的元素。
map	雙向	一種包含成對(duì)數(shù)值的容器，一個(gè)值是實(shí)際數(shù)據(jù)值，另一個(gè)是用來(lái)尋找數(shù)據(jù)的關(guān)鍵字。一個(gè)特定的關(guān)鍵字只能與一個(gè)元素關(guān)聯(lián)。
multimap	雙向	一種包含成對(duì)數(shù)值的容器，一個(gè)值是實(shí)際數(shù)據(jù)值，另一個(gè)是用來(lái)尋找數(shù)據(jù)的關(guān)鍵字。一個(gè)關(guān)鍵字可以與多個(gè)數(shù)據(jù)元素關(guān)聯(lián)。
stack	不支持	適配器容器類型，用vector，deque或list對(duì)象創(chuàng)建了一個(gè)先進(jìn)后出容器
queue	不支持	適配器容器類型，用deque或list對(duì)象創(chuàng)建了一個(gè)先進(jìn)先出容器
priority_queue	不支持	適配器容器類型，用vector或deque對(duì)象創(chuàng)建了一個(gè)排序隊(duì)列

 本文版權(quán)歸傳智播客C++培訓(xùn)學(xué)院所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明作者出處。謝謝！
作者：傳智播客C/C++培訓(xùn)學(xué)院
首發(fā)：http://www.xamj520.com/c/