axsoft
版主
發表:681 回覆:1056 積分:969 註冊:2002-03-13
發送簡訊給我
|
STL基本介紹 資料來源及作者已不可考! 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
相等的資料,使用後會使得所有屬於這個容器 如何引用? using namespace std::list;
#include
如何宣告一個型態為 T 的 list? list listT;
list listTP;
如何將資料置入? class T {
public:
T ();
}; list listT;
list listTP; ...
T f, b; listT.push_back (b); // 將 b 複製丟到 listT 後面
listT.push_front (f) // 將 f 複製丟到 listT 前面
listTP.push_back (&b); // 將 b 的 address value 複製丟到 listT 後面
listTP.push_front (&f); // 將 f 的 address value 複製丟到 listT 前面
如何對 list 使用 for 回圈? for (list ::iterator i = listString.begin ();
i != listString.end (); i )
printf ("%s\n", *i);
如果在 for 回圈裡面要移除一份資料呢? for (list ::iterator i = listString.begin ();
i != listString.end (); i ) {
...
delete *i;
*i = NULL;
// 千萬不可寫 listString.erase (i) 或者 listString.remove (*i)
// 要不然得馬上 break,否則 i 的值馬上變成無效值
// i 就會出問題
}
// 但是這樣子還沒有結束,得清除 data 為 NULL 的 node
listString.remove ((char *)NULL);
如果清除整個 link 的資料呢? // 如果 list 裡面所指向的資料還不需要清除,下面的 for 回圈可以省去
// 基本上指標型態的 list 存的資料只是一些指向這些資料實體的指標而已
for (list ::iterator i = listString.begin ();
i != listString.end (); i )
delete *i;
listString.clear ();
如果你經常會在 list 中移除資料,該怎麼寫? void fun1 (list &listString)
{
for (list ::iterator i = listString.begin ();
i != listString.end (); i ) {
if (!*i)
continue;
...
if (...) {
delete *i;
*i = NULL;
continue;
}
...
}
// 這裡不可以使用 listString.remove ((char *)NULL);
// 因為有可能使外面呼叫的指位器消失
}
...
for (list ::iterator i = listString.begin ();
i != listString.end (); i ) {
if (!*i)
continue;
...
fun1 (listString); // 可能會在裡面動到 listString
if (!*i)
continue;
}
// 只能在確定不會影響到其他同樣指到 listString 的 iterator (指位器)
// 的情況下移除內容為 NULL 的指位器
listString.remove ((char *)NULL);
sort 有哪幾種? sort 有分 sort、stable_sort、以及 partial_sort 三種
其中 sort () 使用的演算法為 quick sort,為 unstable sort。
stable_sort () 使用的演算法為 merge sort,partial_sort ()
使用的演算法為 heap sort,皆為 stable sort。其中 partial_sort
還可以拿來做只排序前一百名的功能。
sort 使用上的限制? STL 的 sort 使用上只能針對能夠 random access 的 iterator 使用,
因此像是 list 這種容器因為只提供雙向指位器(iterator),因此並不能使用。
其他像是 vector、deque 甚至是陣列就能夠使用。不過就算不能使用的容器,只要
先把容器的內容轉到具有隨機存取指位器的容器裡面,再 sort 然後再轉回來,
由於 sort 的時間複雜度一定比轉換容器大,所以這是很划得來的。
sort 使用的範例 #include
#include
#include
#include bool StrCmp (const char *& x, const char *& y)
{
return strcmp (x, y) < 0;
} void main ()
{
char *strArray [9] = {
"sdf",
"assdf",
"d",
"ghfdgfd",
"dfgfdg",
"njxvgfd",
"fghdvs",
"sfhhgh",
"fbyhfrtgfds"
}; sort (&strArray [0], &strArray [9], StrCmp);
for (int i = 0; i < 9; i )
printf ("%s\n", strArray [i]);
}
/---------------------------------------------------------------------------
其中,sort 也可以改用 stable_sort 取代。你也可以試試看
partial_sort (&strArray [0], &strArray [5], StrCmp);
/---------------------------------------------------------------------------
如何對 list 使用 sort? 例如
s = 0;
for (list ::iterator i = strList.begin ();
i != strList.end (); i )
strArray [s ] = *i;
sort (&strArray [0], &strArray [s], StrCmp);
strList.clear ();
for (int i = 0; i < s; i )
strList.push_back (strArray [i]);
或者
vector strVector;
for (list ::iterator i = strList.begin ();
i != strList.end (); i )
strVector.push_back (*i);
sort (strVector.begin (), strVector.end (), StrCmp);
strList.clear ();
for (vector ::iterator i = strVector.begin ();
i != strVector.end (); i )
strList.push_back (*i);
strVector.clear ();
時間就是金錢---[ 發問前請先找找舊文章]
|