STL包括兩部分內(nèi)容:容器和算法。(重要的還有融合這二者的迭代器)
容器,即存放數(shù)據(jù)的地方。比如array等。
在STL中,容器分為兩類:序列式容器和關(guān)聯(lián)式容器。
序列式容器,其中的元素不一定有序,但都可以被排序。如:vector、list、deque、stack、queue、heap、priority_queue、slist;
關(guān)聯(lián)式容器,內(nèi)部結(jié)構(gòu)基本上是一顆平衡二叉樹。所謂關(guān)聯(lián),指每個元素都有一個鍵值和一個實值,元素按照一定的規(guī)則存放。如:RB-tree、set、map、multiset、multimap、hashtable、hash_set、hash_map、hash_multiset、hash_multimap。
1、vector:向量容器,支持動態(tài)擴容,支持下標訪問和尾后插入。
2、list:鏈表容器,支持雙向鏈表,插入和刪除效率較高。
3、deque:雙端隊列,支持隊列和棧的操作,插入和刪除效率較高。
4、set:集合容器,支持有序集合,不允許重復元素。
5、multiset:多重集合容器,與set相似,允許重復元素。
6、map:映射容器,支持鍵值對存儲和查找,鍵是唯一的。
7、multimap:多重映射容器,與map相似,允許重復鍵。
8、hash_set:哈希集合容器,支持快速查找,插入和刪除操作。
9、hash_map:哈希映射容器,支持快速鍵值對存儲和查找。
10、queue:隊列容器,支持先進先出的元素順序。
11、stack:棧容器,支持后進先出的元素順序。
12、unordered_set:無序集合容器,不支持順序訪問,插入和刪除效率較高。
13、unordered_map:無序映射容器,不支持順序訪問,插入和刪除效率較高。
下面各選取一個作為說明。
vector:它是一個動態(tài)分配存儲空間的容器。區(qū)別于c++中的array,array分配的空間是靜態(tài)的,分配之后不能被改變,而vector會自動重分配(擴展)空間。
set:其內(nèi)部元素會根據(jù)元素的鍵值自動被排序。區(qū)別于map,它的鍵值就是實值,而map可以同時擁有不同的鍵值和實值。
算法,如排序,復制……以及個容器特定的算法。這點不用過多介紹,主要看下面迭代器的內(nèi)容。
迭代器是STL的精髓,我們這樣描述它:迭代器提供了一種方法,使它能夠按照順序訪問某個容器所含的各個元素,但無需暴露該容器的內(nèi)部結(jié)構(gòu)。它將容器和算法分開,好讓這二者獨立設(shè)計。