C++ 培訓之C++STL 一般總結(一)

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

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

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

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

 
2.STL迭代器 
Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內部表示?；蛘哌@樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。
迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無間隙的粘合起來，重載了*，＋＋，＝＝，?。?，＝運算符。用以操作復雜的數(shù)據(jù)結構，容器提供迭代器，算法使用迭代器；
常見的一些迭代器類型：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                                       
 
要注意，上面這圖表并不是表明它們之間的繼承關系：而只是描述了迭代器的種類和接口。處于圖表下層的迭代器都是相對于處于圖表上層迭代器的擴張集。例如：forward迭代器不但擁有input和output迭代器的所有功能，還擁有更多的功能。
各個迭代器的功能如下：

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

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

迭代器操作	說明
所有迭代器
p++	后置自增迭代器
++p	前置自增迭代器
輸入迭代器
*p	復引用迭代器，作為右值
p=p1	將一個迭代器賦給另一個迭代器
p==p1	比較迭代器的相等性
p!=p1	比較迭代器的不等性
輸出迭代器
*p	復引用迭代器，作為左值
p=p1	將一個迭代器賦給另一個迭代器
正向迭代器	提供輸入輸出迭代器的所有功能
雙向迭代器
--p	前置自減迭代器
p--	后置自減迭代器
隨機迭代器
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的前面或同一位置時返回true，否則返回false
p>p1	如果迭代器p的位置在p1后，返回true，否則返回false
p>=p1	p的位置在p1的后面或同一位置時返回true，否則返回false

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

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

 本文版權歸傳智播客C++培訓學院所有，歡迎轉載，轉載請注明作者出處。謝謝！
作者：傳智播客C/C++培訓學院
首發(fā)：http://m.fskzgqt.cn/c/