STL 的組成
STL 由三部分所組成,由資料容器(也就是所謂的資料結構的部分)
、資料指位器以及演算法。其中大家可能比較不瞭解的是資料指位器的部分。
簡單來說,一種資料容器就是一種存放資料的空間;而每種容器擺放資料的
方式都不一樣。例如 list 是以 double-linked list 的方式存放資料,而
vector 則是以向量陣列的方式存放資料。
然而我們要透過什麼東西來存取一個資料結構裡面的資料呢?以 array 來講
,我們透過Index來存取資料,以 linked list 而言我們透過 node 來存取資料
。而資料指位器扮演的就是這些角色,透過指位器我們可以處理指位器所指向的
資料。而且也可以透過對指位器的運算達到有目的地遊走於資料結構裡面的各筆
資料間。
而 STL 所提供的演算法則是架構在一個有統一存取介面的資料容器與指位器上
。而我們的程式其實就是演算法與資料結構的配合,演算法就是處理資料的一套
有系統的流程。(所謂的有系統,通惇O指具有泛用性,可以適用在各種需要它的
地方,該流程幾乎不需要改變就能達到目的。)
引用 STL 的方式
基本上 STL 既然是 template,所以它所有的 source code 全部可以在你
Include 它的檔案裡面找到。
Include STL 的標準如下:
1. 檔案名不含 .h
2. 不同的資料容器存放在不同名稱的檔案
3. 你可以在 function 裡面找到一些悼峈� function 如 max ()
4. 你可以在 algorithm 裡面找到所有 STL 提供的演算法
5. STL 的 namespace 為 std,如果沒有使用 using namespace std;
你要在使用的 template 前面加上 std:: 才行
資料結構的歸類
目前 STL 所提供的資料容器,常用的有
list、vector、deque、stack、set、map、multiset與multimap。幾乎你想要用到的資料結構都可以用這幾類代替。
基本上 vector 悼峔茈N替 array ,而且是一種不限制長度的 array。跟 vector
一樣的還有 deque ,所不同的是 vector 只能從最後面增加與刪除資料,deque
則到處都可以。
而 set、map、multiset與multimap
基本上都是使用了紅黑樹資料結構所做成的,基本上這些東西存取資料的速度都是以
lgN 的速度計算的。
這些資料容器大都具有的 member functions
1. iterator begin () 傳回指向第一筆資料的指向器
2. iterator end () 傳回當結尾用的指向器
3. reverse_iterator rbegin () 傳回指向反方向第一筆資料的反向指向器
4. reverse_iterator rend () 傳回反方向存取當結尾用的反向指向器
5. bool empty () 用來檢查資料容器是否是空的
6. int size () 傳回資料容器內存放資料個數(關於這點惘頂~會)
7. void clear ()
清除所有存放資料(這個也是經惘頂~會的地方),使用完後會使所有屬於這個容器的指位器失效
8. iterator find (value_type &x) 尋找與 x 相等的資料並傳回指向它的指向器
9. void remove (value_type &x) 移除與 x
相等的資料,使用後會使得所有屬於這個容器