STL的介紹及queue,vector

1、STL簡(jiǎn)介1作為一個(gè)C+程序設(shè)計(jì)者，STL是一種不可忽視的技術(shù)。Standard Template Library (STL)：標(biāo)準(zhǔn)模板庫(kù),更準(zhǔn)確的說(shuō)是 C+ 程序設(shè)計(jì)語(yǔ)言標(biāo)準(zhǔn)模板庫(kù)。STL是所有C+編譯器和所有操作系統(tǒng)平臺(tái)都支持的一種庫(kù)，說(shuō)它是一種庫(kù)是因?yàn)椋m然STL是一種標(biāo)準(zhǔn)，也就是說(shuō)對(duì)所有的編譯器來(lái)說(shuō)，提供給C+程序設(shè)計(jì)者的接口都是一樣的。也就是說(shuō)同一段STL代碼在不同編譯器和操作系統(tǒng)平臺(tái)上運(yùn)行的結(jié)果都是相同的，但是底層實(shí)現(xiàn)可以是不同的。 令人興奮的是，STL的使用者并不需要了解它的底層實(shí)現(xiàn)。 試想一下，如果我們有一把能打開(kāi)所有鎖的鑰匙，那將是多么令人瘋狂啊。STL的目的是標(biāo)準(zhǔn)化組件，這

2、樣你就不用重新開(kāi)發(fā)它們了。你可以?xún)H僅使用這些現(xiàn)成的組件。STL現(xiàn)在是C+的一部分，因此不用額外安裝什么。它被內(nèi)建在你的編譯器之內(nèi)。2. 為什么我們需要學(xué)習(xí)STLSTL是 C+的ANSI/ISO 標(biāo)準(zhǔn)的一部分,可以用于所有C+語(yǔ)言編譯器和所有平臺(tái)(Windows/Unix/Linux.)。STL的同一版本在任意硬件配置下都是可用的；STL 提供了大量的可復(fù)用軟件組織。例如，程序員再也不用自己設(shè)計(jì)排序，搜索算法了，這些都已經(jīng)是STL的一部分了。嘎嘎，有意思吧。使用STL 的應(yīng)用程序保證了得到的實(shí)現(xiàn)在處理速度和內(nèi)存利用方面都是高效的，因?yàn)镾TL設(shè)計(jì)者們已經(jīng)為我們考慮好了。使用STL編寫(xiě)的代碼更容易修

3、改和閱讀，這是當(dāng)然的啦。因?yàn)榇a更短了，很多基礎(chǔ)工作代碼已經(jīng)被組件化了；使用簡(jiǎn)單，雖然內(nèi)部實(shí)現(xiàn)很復(fù)雜。雖然，STL的優(yōu)點(diǎn)甚多，但是STL的語(yǔ)法實(shí)在令初學(xué)者人頭疼，許多人望而卻步?？墒荢TL是每個(gè)C+程序設(shè)計(jì)者遲早都要啃的一塊骨頭。3. 初識(shí)STL下面讓我們來(lái)看幾段代碼吧：#include int main(void) double a = 1, 2, 3, 4, 5; std:coutmean(a, 5)std:endl; / will print 3 return 0;好懂吧，除了那個(gè)std有點(diǎn)讓人不舒服以外，這是一段普通的沒(méi)有使用STL的C+代碼。再看下面一段：#include #incl

4、ude int main() std:vector a; a.push_back(1); a.push_back(2); a.push_back(3); a.push_back(4); a.push_back(5); for(int i = 0; i a.size(); +i) std:coutaistd:endl; return 0;如果你真的沒(méi)有接觸過(guò)STL的話，你會(huì)問(wèn)，呀，vector 是啥呀？這是一段純種的STL代碼，看到尖括號(hào)了吧，知道那是模板了吧?？吹絘.push_back(5)、a.size()你不感覺(jué)奇怪么？可是我們并沒(méi)有定義這些函數(shù)啊。#include #include in

5、t main() std:vector q; q.push_back(10); q.push_back(11); q.push_back(12); std:vector v; for(int i=0; i5; +i) v.push_back(i); std:vector:iterator it = v.begin() + 1; it = v.insert(it, 33); v.insert(it, q.begin(), q.end(); it = v.begin() + 3; v.insert(it, 3, -1); it = v.begin() + 4; v.erase(it); it =

6、v.begin() + 1; v.erase(it, it + 4); v.clear(); return 0;這一段你又看到了新東西了吧：iterator、insert、erase、clear。不羅嗦了，等你看完這篇文章，回頭再看就簡(jiǎn)單了。關(guān)于模板的其他細(xì)節(jié)，讀者可以參閱C+ Templates 中文版在這里，簡(jiǎn)單的介紹一下模板類(lèi)和函數(shù)模板的概念。模板是C+中實(shí)現(xiàn)代碼重用機(jī)制的一種工具，可以實(shí)現(xiàn)類(lèi)型參數(shù)化，把類(lèi)型定義為參數(shù)。函數(shù)模板和類(lèi)模板允許用戶(hù)構(gòu)造模板函數(shù)和模板類(lèi)。圖1下面我們來(lái)看一段函數(shù)模板的例子：#include#includeusing namespace std;/定義函數(shù)模板t

7、emplate /template 是關(guān)鍵字，T 表示一種待實(shí)例化的類(lèi)型 /template 也是對(duì)的T MAX(T a, T b)/函數(shù)模板，函數(shù)名為 max，此函數(shù)有2個(gè)T類(lèi)型的參數(shù)，返回類(lèi)型為T(mén)return (ab)?a:b;/在此例實(shí)例化的時(shí)候，T可以是多種類(lèi)型的，int,char,stringint main()int x=2,y=6; double x1=9.123,y1=12.6543; cout把T實(shí)例化為int:MAX(x,y)endl;/實(shí)例化函數(shù)模板，把T實(shí)例化為int cout把T實(shí)例化為double:MAX(x1,y1)endl; /把T實(shí)例化為double下面再看看

8、，類(lèi)模板：#includeusing namespace std;/定義名為ex_class的類(lèi)模板template class ex_class T value;public: ex_class(T v) value=v; void set_value(T v) value=v; T get_value(void) return value;/main()函數(shù)中測(cè)試ex_class類(lèi)模板int main() /測(cè)試int類(lèi)型數(shù)據(jù) ex_class a(5),b(10); couta.value:a.get_value()endl; coutb.value:b.get_value()endl;

9、 /測(cè)試char類(lèi)型數(shù)據(jù) ex_class ch(A); coutch.value:ch.get_value()endl; ch.set_value(a); coutch.value:ch.get_value()endl; /測(cè)試double類(lèi)型數(shù)據(jù) ex_class x(5.5); coutx.value:x.get_value()endl; x.set_value(7.5); coutx.value:x.get_value()endl;的組成STL有三大核心部分：容器（Container）、算法（Algorithms）、迭代器（Iterator），容器適配器（container adapt

10、or），函數(shù)對(duì)象(functor)，除此之外還有STL其他標(biāo)準(zhǔn)組件。通俗的講：容器：裝東西的東西，裝水的杯子，裝咸水的大海，裝人的教室STL里的容器是可容納一些數(shù)據(jù)的模板類(lèi)。算法：就是往杯子里倒水，往大海里排污，從教室里攆人STL里的算法，就是處理容器里面數(shù)據(jù)的方法、操作。迭代器：往杯子里倒水的水壺，排污的管道，攆人的那個(gè)物業(yè)管理人員STL里的迭代器：遍歷容器中數(shù)據(jù)的對(duì)象。對(duì)存儲(chǔ)于容器中的數(shù)據(jù)進(jìn)行處理時(shí)，迭代器能從一個(gè)成員移向另一個(gè)成員。他能按預(yù)先定義的順序在某些容器中的成員間移動(dòng)。對(duì)普通的一維數(shù)組、向量、雙端隊(duì)列和列表來(lái)說(shuō)，迭代器是一種指針。下面讓我們來(lái)看看專(zhuān)家是怎么說(shuō)的：容器（contai

11、ner）：容器是數(shù)據(jù)在內(nèi)存中組織的方法，例如，數(shù)組、堆棧、隊(duì)列、鏈表或二叉樹(shù)（不過(guò)這些都不是STL標(biāo)準(zhǔn)容器）。STL中的容器是一種存儲(chǔ)T（Template）類(lèi)型值的有限集合的數(shù)據(jù)結(jié)構(gòu),容器的內(nèi)部實(shí)現(xiàn)一般是類(lèi)。這些值可以是對(duì)象本身，如果數(shù)據(jù)類(lèi)型T代表的是Class的話。算法（algorithm）：算法是應(yīng)用在容器上以各種方法處理其內(nèi)容的行為或功能。例如，有對(duì)容器內(nèi)容排序、復(fù)制、檢索和合并的算法。在STL中，算法是由模板函數(shù)表現(xiàn)的。這些函數(shù)不是容器類(lèi)的成員函數(shù)。相反，它們是獨(dú)立的函數(shù)。令人吃驚的特點(diǎn)之一就是其算法如此通用。不僅可以將其用于STL容器，而且可以用于普通的C數(shù)組或任何其他應(yīng)用程序指定的

12、容器。迭代器(iterator)：一旦選定一種容器類(lèi)型和數(shù)據(jù)行為(算法)，那么剩下唯一要他做的就是用迭代器使其相互作用。可以把達(dá)代器看作一個(gè)指向容器中元素的普通指針?？梢匀邕f增一個(gè)指針那樣遞增迭代器，使其依次指向容器中每一個(gè)后繼的元素。迭代器是STL的一個(gè)關(guān)鍵部分，因?yàn)樗鼘⑺惴ê腿萜鬟B在一起。下面我將依次介紹STL的這三個(gè)主要組件。1. 容器STL中的容器有隊(duì)列容器和關(guān)聯(lián)容器，容器適配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。在本文中，我將介紹list,vector，de

13、que等隊(duì)列容器，和set和multisets,map和multimaps等關(guān)聯(lián)容器，一共7種基本容器類(lèi)。隊(duì)列容器（順序容器）：隊(duì)列容器按照線性排列來(lái)存儲(chǔ)T類(lèi)型值的集合，隊(duì)列的每個(gè)成員都有自己的特有的位置。順序容器有向量類(lèi)型、雙端隊(duì)列類(lèi)型、列表類(lèi)型三種。u 基本容器向量向量（vector容器類(lèi)）：include ，vector是一種動(dòng)態(tài)數(shù)組，是基本數(shù)組的類(lèi)模板。其內(nèi)部定義了很多基本操作。既然這是一個(gè)類(lèi)，那么它就會(huì)有自己的構(gòu)造函數(shù)。vector 類(lèi)中定義了4中種構(gòu)造函數(shù)： 默認(rèn)構(gòu)造函數(shù)，構(gòu)造一個(gè)初始長(zhǎng)度為0的空向量，如：vector v1; 帶有單個(gè)整形參數(shù)的構(gòu)造函數(shù)，此參數(shù)描述了向量的初始大小

14、。這個(gè)構(gòu)造函數(shù)還有一個(gè)可選的參數(shù)，這是一個(gè)類(lèi)型為T(mén)的實(shí)例，描述了各個(gè)向量種各成員的初始值；如：vector v2(n,0); 如果預(yù)先定義了：n,他的成員值都被初始化為0； 復(fù)制構(gòu)造函數(shù)，構(gòu)造一個(gè)新的向量，作為已存在的向量的完全復(fù)制，如：vector v3(v2); 帶兩個(gè)常量參數(shù)的構(gòu)造函數(shù)，產(chǎn)生初始值為一個(gè)區(qū)間的向量。區(qū)間由一個(gè)半開(kāi)區(qū)間first,last) 來(lái)指定。如：vector v4(first,last）下面一個(gè)例子用的是第四種構(gòu)造方法，其它的方法讀者可以自己試試。/程序：初始化演示#include #include #include using namespace std;int

15、ar10 = 12, 45, 234, 64, 12, 35, 63, 23, 12, 55 ;char* str = Hello World;int main() vector vec1(ar, ar+10); /first=ar,last=ar+10,不包括ar+10 vector vec2(str,str+strlen(str); /first=str,last= str+strlen(str), coutvec1:endl; /打印vec1和vec2，const_iterator是迭代器，后面會(huì)講到 /當(dāng)然，也可以用for (int i=0; ivec1.size(); i+)cout

16、 veci;輸出 /size()是vector的一個(gè)成員函數(shù) for(vector:const_iterator p=vec1.begin();p!=vec1.end(); +p) cout*p; coutnvec2:endl; for(vector:const_iterator p1=vec2.begin();p1!=vec2.end(); +p1) cout*p1; coutn; return 0; 為了幫助理解向量的概念，這里寫(xiě)了一個(gè)小例子，其中用到了vector的成員函數(shù)：begin()，end()，push_back()，assign()，front()，back()，erase()

17、，empty()，at()，size()。#include #include using namespace std;typedef vector INTVECTOR;/自定義類(lèi)型INTVECTOR/測(cè)試vector容器的功能int main() /vec1對(duì)象初始為空 INTVECTOR vec1; /vec2對(duì)象最初有10個(gè)值為6的元素 INTVECTOR vec2(10,6); /vec3對(duì)象最初有3個(gè)值為6的元素，拷貝構(gòu)造 INTVECTOR vec3(vec2.begin(),vec2.begin()+3); /聲明一個(gè)名為i的雙向迭代器 INTVECTOR:iterator i;

18、/從前向后顯示vec1中的數(shù)據(jù) coutvec1.begin()-vec1.end():endl; for (i =vec1.begin(); i !=vec1.end(); +i) cout *i ; cout endl; /從前向后顯示vec2中的數(shù)據(jù) coutvec2.begin()-vec2.end():endl; for (i =vec2.begin(); i !=vec2.end(); +i) cout *i ; cout endl; /從前向后顯示vec3中的數(shù)據(jù) coutvec3.begin()-vec3.end():endl; for (i =vec3.begin(); i

19、!=vec3.end(); +i) cout *i ; cout endl; /測(cè)試添加和插入成員函數(shù)，vector不支持從前插入 vec1.push_back(2);/從后面添加一個(gè)成員 vec1.push_back(4); vec1.insert(vec1.begin()+1,5);/在vec1第一個(gè)的位置上插入成員5 /從vec1第一的位置開(kāi)始插入vec3的所有成員 vec1.insert(vec1.begin()+1,vec3.begin(),vec3.end(); coutafter push() and insert() now the vec1 is: endl; for (i

20、=vec1.begin(); i !=vec1.end(); +i) cout *i ; cout endl; /測(cè)試賦值成員函數(shù) vec2.assign(8,1); / 重新給vec2賦值，8個(gè)成員的初始值都為1 coutvec2.assign(8,1): endl; for (i =vec2.begin(); i !=vec2.end(); +i) cout *i ; cout endl; /測(cè)試引用類(lèi)函數(shù) coutvec1.front()=vec1.front()endl;/vec1第零個(gè)成員 coutvec1.back()=vec1.back()endl;/vec1的最后一個(gè)成員 co

21、utvec1.at(4)=vec1.at(4)endl;/vec1的第五個(gè)成員 coutvec14=vec14endl; /測(cè)試移出和刪除 vec1.pop_back();/將最后一個(gè)成員移出vec1 vec1.erase(vec1.begin()+1,vec1.end()-2);/刪除成員 coutvec1.pop_back() and vec1.erase(): endl; for (i =vec1.begin(); i !=vec1.end(); +i) cout *i ; cout endl; /顯示序列的狀態(tài)信息 coutvec1.size(): vec1.size()endl;/打

22、印成員個(gè)數(shù) coutvec1.empty(): vec1.empty()endl;/清空push_back()是將數(shù)據(jù)放入vector（向量）或deque（雙端隊(duì)列）的標(biāo)準(zhǔn)函數(shù)。Insert()是一個(gè)與之類(lèi)似的函數(shù)，然而它在所有容器中都可以使用，但是用法更加復(fù)雜。end()實(shí)際上是取末尾加一，以便讓循環(huán)正確運(yùn)行-它返回的指針指向最靠近數(shù)組界限的數(shù)據(jù)。在Java里面也有向量的概念。Java中的向量是對(duì)象的集合。其中，各元素可以不必同類(lèi)型，元素可以增加和刪除，不能直接加入原始數(shù)據(jù)類(lèi)型。u 雙端隊(duì)列（qeque容器類(lèi)）：deque（讀音：deck，意即：double queue，#include）容

23、器類(lèi)與vector類(lèi)似，支持隨機(jī)訪問(wèn)和快速插入刪除，它在容器中某一位置上的操作所花費(fèi)的是線性時(shí)間。與vector不同的是，deque還支持從開(kāi)始端插入數(shù)據(jù)：push_front()。此外deque也不支持與vector的capacity()、reserve()類(lèi)似的操作。#include #include using namespace std;typedef deque INTDEQUE;/有些人很討厭這種定義法，呵呵/從前向后顯示deque隊(duì)列的全部元素void put_deque(INTDEQUE deque, char *name) INTDEQUE:iterator pdeque;/

24、仍然使用迭代器輸出 cout The contents of name : ; for(pdeque = deque.begin(); pdeque != deque.end(); pdeque+) cout *pdeque ;/注意有 *號(hào)哦，沒(méi)有*號(hào)的話會(huì)報(bào)錯(cuò) coutendl;/測(cè)試deqtor容器的功能int main() /deq1對(duì)象初始為空 INTDEQUE deq1; /deq2對(duì)象最初有10個(gè)值為6的元素 INTDEQUE deq2(10,6); /聲明一個(gè)名為i的雙向迭代器變量 INTDEQUE:iterator i; /從前向后顯示deq1中的數(shù)據(jù) put_deque(d

25、eq1,deq1); /從前向后顯示deq2中的數(shù)據(jù) put_deque(deq2,deq2); /從deq1序列后面添加兩個(gè)元素 deq1.push_back(2); deq1.push_back(4); coutdeq1.push_back(2) and deq1.push_back(4):endl; put_deque(deq1,deq1); /從deq1序列前面添加兩個(gè)元素 deq1.push_front(5); deq1.push_front(7); coutdeq1.push_front(5) and deq1.push_front(7):endl; put_deque(deq1,

26、deq1); /在deq1序列中間插入數(shù)據(jù) deq1.insert(deq1.begin()+1,3,9); coutdeq1.insert(deq1.begin()+1,3,9):endl; put_deque(deq1,deq1); /測(cè)試引用類(lèi)函數(shù) coutdeq1.at(4)=deq1.at(4)endl; coutdeq14=deq14endl; deq1.at(1)=10; deq12=12; coutdeq1.at(1)=10 and deq12=12 :endl; put_deque(deq1,deq1); /從deq1序列的前后各移去一個(gè)元素 deq1.pop_front()

27、; deq1.pop_back(); coutdeq1.pop_front() and deq1.pop_back():endl; put_deque(deq1,deq1); /清除deq1中的第2個(gè)元素 deq1.erase(deq1.begin()+1); coutdeq1.erase(deq1.begin()+1):endl; put_deque(deq1,deq1); /對(duì)deq2賦值并顯示 deq2.assign(8,1); coutdeq2.assign(8,1):endl; put_deque(deq2,deq2);上面我們演示了deque如何進(jìn)行插入刪除等操作，像erase()

28、,assign()是大多數(shù)容器都有的操作。關(guān)于deque的其他操作請(qǐng)參閱其他書(shū)籍。u 表（List容器類(lèi)）List（#include）又叫鏈表，是一種雙線性列表，只能順序訪問(wèn)（從前向后或者從后向前），圖2是list的數(shù)據(jù)組織形式。與前面兩種容器類(lèi)有一個(gè)明顯的區(qū)別就是：它不支持隨機(jī)訪問(wèn)。要訪問(wèn)表中某個(gè)下標(biāo)處的項(xiàng)需要從表頭或表尾處（接近該下標(biāo)的一端）開(kāi)始循環(huán)。而且缺少下標(biāo)預(yù)算符：operator。圖2同時(shí)，list仍然包涵了erase(),begin(),end(),insert(),push_back(),push_front()這些基本函數(shù)，下面我們來(lái)演示一下list的其他函數(shù)功能。merge

29、()：合并兩個(gè)排序列表；splice()：拼接兩個(gè)列表；sort()：列表的排序。#include #include #include using namespace std;void PrintIt(list n) for(list:iterator iter=n.begin(); iter!=n.end(); +iter) cout*iter ;/用迭代器進(jìn)行輸出循環(huán)int main() list listn1,listn2; /給listn1,listn2初始化 listn1.push_back(123); listn1.push_back(0); listn1.push_back(34

30、); listn1.push_back(1123); /now listn1:123,0,34,1123 listn2.push_back(100); listn2.push_back(12); /now listn2:12,100 listn1.sort(); listn2.sort(); /給listn1和listn2排序 /now listn1:0,34,123,1123 listn2:12,100 PrintIt(listn1); coutendl; PrintIt(listn2); listn1.merge(listn2); /合并兩個(gè)排序列表后,listn1:0，12，34，100

31、，123，1123 coutendl; PrintIt(listn1);queue FunctionsIllustrates how to use the queue:push, queue:pop, queue:empty, queue:back, queue:front, and queue:size Standard Template Library (STL) functions in Visual C+.queue:push( );queue:pop( );queue:empty( );queue:back( );queue:front( );queue:size( );NoteTh

32、e class/parameter names in the prototype do not match the version in the header file. Some have been modified to improve readability.DescriptionThe sample shows the queue implementation using list and deque containers. Example/ queue.cpp/ compile with: /EHsc/ Functions:/ queue:push(), queue:pop(), queue:empty(), q