|
C++的 STL 是一個(gè)功能強(qiáng)大的庫(kù),，它是建立在模板機(jī)制上,，能夠滿足用戶對(duì)存儲(chǔ)管理不同類型數(shù)據(jù)的通用容器和施加在這些容器上的通用算法的巨大需求，并且具有完全的可移植性,。因此在尋求程序的解決方案時(shí),，應(yīng)該首先在 STL 中尋求恰當(dāng)?shù)娜萜骱退惴ā?/font> STL 是一個(gè)通用性極高的編程工具，這種通用性不僅表現(xiàn)在可以使用通用的容器存儲(chǔ)和管理任意類型的數(shù)據(jù),，更重要的是可以對(duì)不同的容器施加統(tǒng)一通用的算法和操作,。實(shí)現(xiàn)這種通用性的關(guān)鍵思想就是：通過(guò)引進(jìn)一個(gè)間接層對(duì)象對(duì)不同結(jié)構(gòu)的數(shù)據(jù)容器進(jìn)行統(tǒng)一的訪問(wèn)操作，從而簡(jiǎn)化了對(duì)容器的操作,，使得實(shí)現(xiàn)操作的算法和函數(shù)通用化,。這種思想是 STL 的設(shè)計(jì)原則之一，也是軟件設(shè)計(jì)中一個(gè)重要設(shè)計(jì)思想,。 在 STL 中對(duì)容器訪問(wèn)的簡(jiǎn)化和獨(dú)立就是通過(guò)循環(huán)子實(shí)現(xiàn)的,，循環(huán)子可以無(wú)須依據(jù)某種特定容器的數(shù)據(jù)結(jié)構(gòu)而完成對(duì)容器元素的訪問(wèn)，從而使得數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與施加于數(shù)據(jù)的操作相互獨(dú)立,。標(biāo)準(zhǔn)模板庫(kù) STL 是由容器類模板,，用于訪問(wèn)這些容器的循環(huán)子類模板和可以通過(guò)循環(huán)子在這些容器上實(shí)現(xiàn)的各種算法類模板以及函數(shù)類模板組成的。STL 為這種標(biāo)準(zhǔn)算法和函數(shù)（包括用戶定義的函數(shù)）借助循環(huán)子在容器上實(shí)現(xiàn)的應(yīng)用建立了統(tǒng)一的規(guī)則,。 容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),。 迭代器：可依次存取容器中元素的東西,，連接容器和算法 算法：用來(lái)操作容器中的元素的函數(shù)模板。例如,，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序,，用find()來(lái)搜索一個(gè)list中的對(duì)象。 函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān),，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用,。 比如,，數(shù)組int array[100]就是個(gè)容器,，而 int * 類型的指針變量就可以作為迭代器,，可以為這個(gè)容器編寫一個(gè)排序的算法 一、容器 (一)容器綜述 標(biāo)準(zhǔn)庫(kù)中定義了兩種標(biāo)準(zhǔn)的容器： 1,、序列容器（Sequence）：向量 vector,、表 list 和雙向隊(duì)列 deque。 vector：后部插入/刪除,，直接訪問(wèn) 2,、關(guān)聯(lián)容器 (Associative container) 映射 map、multimap 和集合 set,、multiset,。 set：快速查找，無(wú)重復(fù)元素 前兩種合稱為第一類容器。 3,、序列轉(zhuǎn)接器容器(又名容器適配器)（Sequence Adapter） 是一種可以改變函數(shù)對(duì)象或容器接口的組件,。 序列轉(zhuǎn)接器：堆棧 stack、隊(duì)列 queue 和優(yōu)先級(jí)隊(duì)列priority_queue,。 stack：LIFO 對(duì)象被插入容器中時(shí),，被插入的是對(duì)象的一個(gè)復(fù)制品。 4,、預(yù)定義數(shù)組,、字符串類 string、數(shù)值數(shù)組類 valarray 和位集合 bitset 均可以視為容器,，但不是標(biāo)準(zhǔn)容器,。標(biāo)準(zhǔn)容器的成員絕大部分都具有共同的成員名,。， （1）類型成員
（2）循環(huán)子操作
（3）訪問(wèn)元素操作
front():返回容器中第一個(gè)元素的引用,，back():返回容器中最后一個(gè)元素的引用。比如,，查 list::front 的help,得到的定義是： reference front(); const_reference front() const; list有兩個(gè)front函數(shù) reference 和 const_reference 是typedef的類型 對(duì)于 list<double> , list<double>::reference 實(shí)際上就是 double & list<double>::const_reference 實(shí)際上就是 const double & 對(duì)于 list<int> , list<int>::refrence 實(shí)際上就是 int & list<int>::const_refreence 實(shí)際上就是 const int & （4）堆棧和隊(duì)列操作
push_back(): 在容器末尾增加新元素 pop_back(): 刪除容器末尾的元素 （5）表操作
（6）其他操作
（7）構(gòu)造函數(shù)，析構(gòu)函數(shù)
（8）分配操作
（9）關(guān)聯(lián)操作
（10）標(biāo)準(zhǔn)容器的操作比較（復(fù)雜度）
表中各種容器所對(duì)應(yīng)的表項(xiàng)的含義如下： ① 空表項(xiàng)：表示容器無(wú)此項(xiàng)操作,。 ② const：表示容器此項(xiàng)操作的時(shí)間復(fù)雜度為常量,。 ③ O(n)：表示容器此項(xiàng)操作的時(shí)間復(fù)雜度與容器中元素個(gè)數(shù)n的線性相關(guān)。 ④ O(n)+：表示容器此項(xiàng)操作的時(shí)間復(fù)雜度與容器中元素個(gè)數(shù)n線性相關(guān)并且還需要增加一些附加操作時(shí)間花費(fèi),。 ⑤ O(log(n))：表示容器此項(xiàng)操作的時(shí)間復(fù)雜度與容器中元素個(gè)數(shù)n對(duì)數(shù)相關(guān),。 ⑥ O(log(n))+：表示容器此項(xiàng)操作的時(shí)間復(fù)雜度與容器中元素個(gè)數(shù)n對(duì)數(shù)相關(guān)并且還需要增加一些附加操作時(shí)間花費(fèi)。 ⑦ Ran：表示容器對(duì)應(yīng)的循環(huán)子為隨機(jī)訪問(wèn)循環(huán)子,。 ⑧ Bi：表示容器對(duì)應(yīng)的循環(huán)子為雙向訪問(wèn)循環(huán)子,。 |
|
|
