STL
是個(gè)部件庫(kù)
(component library)
，其中的部件包括有容器
(container
，儲(chǔ)存任意類型對(duì)象的對(duì)象
)
和算法。只要用戶對(duì)自己定義的部件做點(diǎn)小小的要求，
STL
中的算法就可以工作在用戶自定義的容器上，或者
STL
中的容器可以使用用戶自定義的算法。
我們可以把軟件部件想象成一個(gè)三位空間。第一維表示數(shù)據(jù)類型(int, double, char, …)，第二維表示容器(array, linked-list, …)
，
第三維表示算法
(sort, merge, search, …)
。
STL
包含
5
個(gè)主要的部分，
·算法
(Algorithm)
：能運(yùn)行在不同容器
(container)
上的計(jì)算過(guò)程
·容器
(Container)
：能夠保留并管理對(duì)象的對(duì)象
·迭代器
(Iterator)
：算法存取容器
(algorithm-access to containers)
的抽象，以便算法可以應(yīng)用在不同的容器上
·函數(shù)對(duì)象
(Function Object)
：定義了函數(shù)調(diào)用操作符
(operator())
的類
·適應(yīng)器
(Adaptor)
：封裝一個(gè)部件以提供另外的接口
(
例如用
list
實(shí)現(xiàn)
stack)
正是因?yàn)橛辛薎terator,算法才和容器分開(kāi)了.
容器
(Container)
是能夠保存其他類型的對(duì)象的類。容器形成了
STL
的關(guān)鍵部件。當(dāng)書寫任何類型軟件的時(shí)候，把特定類型的元素集聚起來(lái)都是很至關(guān)重要的任務(wù)。
?????? STL
中有順序容器
(Sequence Container)
和關(guān)聯(lián)容器
(Associative Container)
。
STL
中支持的容器總結(jié)如下：
|
順序容器
(Sequence Container)
|
向量
(Vector)
|
|
?
|
雙向隊(duì)列
(Deque)
|
|
?
|
線性表
(List)
|
|
關(guān)聯(lián)容器
(Associative Container)
|
集合
(Set)
|
|
?
|
多集合
(MultiSet)
|
|
?
|
映射
(Map)
|
|
?
|
多映射
(MultiSet)
|
迭代器
(Iterator)
是指針
(pointer)
的泛化，它允許程序員以相同的方式處理不同的數(shù)據(jù)結(jié)構(gòu)
(
容器
)
。
STL
中有
5
中類型的迭代器，它們分別滿足一定的要求。不同的迭代器要求定義的操作不一樣。
輸入和輸出迭代器
向前迭代器
雙向迭代器
任意存取迭代器
算法
STL
庫(kù)中的算法都以迭代器類型為參數(shù)，這就和數(shù)據(jù)結(jié)果的具體實(shí)現(xiàn)分離開(kāi)了。基于此，這些算法被稱作基本算法
(generic algorithm)
。
如“尋找(Find)”、“鄰居尋找(Adjacent find)”、“計(jì)數(shù)(Count)”、“不匹配(Mismatch)”、“相等(Equal)”、“搜索(Search)
”拷貝(Copy)”、“交換(Swap)”、“變換(Transform)”、“替換(Replace)”、“填充(Fill)”、“產(chǎn)生(Generate)”、“遷移(Remove)”、“唯一(Unique)”、“翻轉(zhuǎn)(Reverse)”、“旋轉(zhuǎn)(Rotate)”、“任意洗牌(Random shuffle)”、“分區(qū)(Partitions)”
適應(yīng)器
(Adaptor)
是提供接口映射的模板類
(Adaptors are template classes that provide interface mappings)
。適應(yīng)器基于其他類來(lái)實(shí)現(xiàn)新的功能，成員函數(shù)可以被添加、隱藏，也可合并以得到新的功能。
棧
(Stack)
??????
棧可以用向量
(vector)
、線性表
(list)
或雙向隊(duì)列
(deque)
來(lái)實(shí)現(xiàn)：
stack<vector<int>>?????? s1;
stack<list<int>?????? >???? s2;
stack<deque<int>>s3;
隊(duì)列
(Queue)
??????
隊(duì)列可以用線性表
(list)
或雙向隊(duì)列
(deque)
來(lái)實(shí)現(xiàn)
(
注意
vector container
不能用來(lái)實(shí)現(xiàn)
queue
，
因?yàn)?/span>
vector
沒(méi)有成員函數(shù)
pop_front!
)
：
queue<list<int>>??? q1;
queue<deque<int>>?????? q2;
優(yōu)先級(jí)隊(duì)列
(Priority Queue)
??????
優(yōu)先級(jí)隊(duì)列可以用向量
(vector)
或雙向隊(duì)列
(deque)
來(lái)實(shí)現(xiàn)
(
注意
list container
不能用來(lái)實(shí)現(xiàn)
queue
，
因?yàn)?/span>
list
的迭代器不是任意存取
iterator
，而
pop
中用到堆排序時(shí)是要求
random access iterator
的
!
)
：
priority_queue<vector<int>, less<int>>??????? pq1;??????? //
使用遞增
less<int>
函數(shù)對(duì)象排序
priority_queue<deque<int>, greater<int>>??? pq2; ????? //
使用遞減
greater<int>
函數(shù)對(duì)象排序
迭代適應(yīng)器
逆向迭代器
(Reverse Iterator)
??????
顧名思義，逆向迭代器的遞增是朝反方向前進(jìn)的。對(duì)于順序容器
(vector, list
和
deque)
，其成員函數(shù)
rbegin()
和
rend()
都返回了相應(yīng)的逆向迭代器：
list<int> l;
for (int i = 1; i < 5; i++)
?????? l.push_back(i);
copy(l.rbegin(), l.rend(), ostream_iterator<int> (cout, “ “));
輸出結(jié)果是：
4 3 2 1
?
插入迭代器
(Insert Iterator)
??????
插入迭代器簡(jiǎn)化了向容器中插入元素的工作。插入迭代器指定了向容器中插入元素的位置。
STL
中有三種插入迭代器：
·向后插入
(back_insert_iterator)
，在容器尾部插入
·向前插入
(front_insert_iterator)
，在容器頭部插入
·插入
(insert_iterator)
，在容器中任一位置
STL
中提供了三個(gè)函數(shù)分別構(gòu)造相應(yīng)的插入迭代器：
·
back_inserter
·
front_inserter
·
inserter
?
原始存儲(chǔ)迭代器
(Raw Storage Iterator)
??????
該迭代器允許算法將其結(jié)果保存進(jìn)沒(méi)有初始化的內(nèi)存中。
函數(shù)適應(yīng)器
否認(rèn)者
(Negator)
??????
有兩個(gè)否認(rèn)者
not1
和
not2
分別是一元和二元函數(shù)，它們分別使用一元和二元的謂詞
(Predicate)
，返回的是謂詞的結(jié)果的取反。
?
包扎者
(Binder)
?????? STL
中有兩個(gè)包扎者函數(shù)
bind1st
和
bind2nd
，可以將一些值限定在指定區(qū)間中。
?
函數(shù)指針的適應(yīng)器
(Adaptors for pointers to function)
?????? STL
中的算法和容器一般都需要函數(shù)對(duì)象
(function object)
作為參數(shù)。如果想用到常用的
C++
函數(shù)時(shí)，可以用
ptr_fun
把普通函數(shù)轉(zhuǎn)換成函數(shù)對(duì)象。比如
ptr_fun(strcmp)
就把常用的串比較函數(shù)
strcmp
包裝成一個(gè)函數(shù)對(duì)象，就可用在
STL
算法和容器中了。