STL的介紹及queue,vector

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

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

3、改和閱讀，這是當然的啦。因為代碼更短了，很多基礎(chǔ)工作代碼已經(jīng)被組件化了；使用簡單，雖然內(nèi)部實現(xiàn)很復(fù)雜。雖然，STL的優(yōu)點甚多，但是STL的語法實在令初學(xué)者人頭疼，許多人望而卻步?？墒荢TL是每個C+程序設(shè)計者遲早都要啃的一塊骨頭。3. 初識STL下面讓我們來看幾段代碼吧：#include int main(void) double a = 1, 2, 3, 4, 5; std:coutmean(a, 5)std:endl; / will print 3 return 0;好懂吧，除了那個std有點讓人不舒服以外，這是一段普通的沒有使用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;如果你真的沒有接觸過STL的話，你會問，呀，vector 是啥呀？這是一段純種的STL代碼，看到尖括號了吧，知道那是模板了吧?？吹絘.push_back(5)、a.size()你不感覺奇怪么？可是我們并沒有定義這些函數(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。不羅嗦了，等你看完這篇文章，回頭再看就簡單了。關(guān)于模板的其他細節(jié)，讀者可以參閱C+ Templates 中文版在這里，簡單的介紹一下模板類和函數(shù)模板的概念。模板是C+中實現(xiàn)代碼重用機制的一種工具，可以實現(xiàn)類型參數(shù)化，把類型定義為參數(shù)。函數(shù)模板和類模板允許用戶構(gòu)造模板函數(shù)和模板類。圖1下面我們來看一段函數(shù)模板的例子：#include#includeusing namespace std;/定義函數(shù)模板t

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

8、，類模板：#includeusing namespace std;/定義名為ex_class的類模板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ù)中測試ex_class類模板int main() /測試int類型數(shù)據(jù) ex_class a(5),b(10); couta.value:a.get_value()endl; coutb.value:b.get_value()endl;

9、 /測試char類型數(shù)據(jù) ex_class ch(A); coutch.value:ch.get_value()endl; ch.set_value(a); coutch.value:ch.get_value()endl; /測試double類型數(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ù)對象(functor)，除此之外還有STL其他標準組件。通俗的講：容器：裝東西的東西，裝水的杯子，裝咸水的大海，裝人的教室STL里的容器是可容納一些數(shù)據(jù)的模板類。算法：就是往杯子里倒水，往大海里排污，從教室里攆人STL里的算法，就是處理容器里面數(shù)據(jù)的方法、操作。迭代器：往杯子里倒水的水壺，排污的管道，攆人的那個物業(yè)管理人員STL里的迭代器：遍歷容器中數(shù)據(jù)的對象。對存儲于容器中的數(shù)據(jù)進行處理時，迭代器能從一個成員移向另一個成員。他能按預(yù)先定義的順序在某些容器中的成員間移動。對普通的一維數(shù)組、向量、雙端隊列和列表來說，迭代器是一種指針。下面讓我們來看看專家是怎么說的：容器（contai

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

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

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

14、。這個構(gòu)造函數(shù)還有一個可選的參數(shù)，這是一個類型為T的實例，描述了各個向量種各成員的初始值；如：vector v2(n,0); 如果預(yù)先定義了：n,他的成員值都被初始化為0； 復(fù)制構(gòu)造函數(shù)，構(gòu)造一個新的向量，作為已存在的向量的完全復(fù)制，如：vector v3(v2); 帶兩個常量參數(shù)的構(gòu)造函數(shù)，產(chǎn)生初始值為一個區(qū)間的向量。區(qū)間由一個半開區(qū)間first,last) 來指定。如：vector v4(first,last）下面一個例子用的是第四種構(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是迭代器，后面會講到 /當然，也可以用for (int i=0; ivec1.size(); i+)cout

16、 veci;輸出 /size()是vector的一個成員函數(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; 為了幫助理解向量的概念，這里寫了一個小例子，其中用到了vector的成員函數(shù)：begin()，end()，push_back()，assign()，front()，back()，erase()

17、，empty()，at()，size()。#include #include using namespace std;typedef vector INTVECTOR;/自定義類型INTVECTOR/測試vector容器的功能int main() /vec1對象初始為空 INTVECTOR vec1; /vec2對象最初有10個值為6的元素 INTVECTOR vec2(10,6); /vec3對象最初有3個值為6的元素，拷貝構(gòu)造 INTVECTOR vec3(vec2.begin(),vec2.begin()+3); /聲明一個名為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; /測試添加和插入成員函數(shù)，vector不支持從前插入 vec1.push_back(2);/從后面添加一個成員 vec1.push_back(4); vec1.insert(vec1.begin()+1,5);/在vec1第一個的位置上插入成員5 /從vec1第一的位置開始插入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; /測試賦值成員函數(shù) vec2.assign(8,1); / 重新給vec2賦值，8個成員的初始值都為1 coutvec2.assign(8,1): endl; for (i =vec2.begin(); i !=vec2.end(); +i) cout *i ; cout endl; /測試引用類函數(shù) coutvec1.front()=vec1.front()endl;/vec1第零個成員 coutvec1.back()=vec1.back()endl;/vec1的最后一個成員 co

21、utvec1.at(4)=vec1.at(4)endl;/vec1的第五個成員 coutvec14=vec14endl; /測試移出和刪除 vec1.pop_back();/將最后一個成員移出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、印成員個數(shù) coutvec1.empty(): vec1.empty()endl;/清空push_back()是將數(shù)據(jù)放入vector（向量）或deque（雙端隊列）的標準函數(shù)。Insert()是一個與之類似的函數(shù)，然而它在所有容器中都可以使用，但是用法更加復(fù)雜。end()實際上是取末尾加一，以便讓循環(huán)正確運行-它返回的指針指向最靠近數(shù)組界限的數(shù)據(jù)。在Java里面也有向量的概念。Java中的向量是對象的集合。其中，各元素可以不必同類型，元素可以增加和刪除，不能直接加入原始數(shù)據(jù)類型。u 雙端隊列（qeque容器類）：deque（讀音：deck，意即：double queue，#include）容

23、器類與vector類似，支持隨機訪問和快速插入刪除，它在容器中某一位置上的操作所花費的是線性時間。與vector不同的是，deque還支持從開始端插入數(shù)據(jù)：push_front()。此外deque也不支持與vector的capacity()、reserve()類似的操作。#include #include using namespace std;typedef deque INTDEQUE;/有些人很討厭這種定義法，呵呵/從前向后顯示deque隊列的全部元素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 ;/注意有 *號哦，沒有*號的話會報錯 coutendl;/測試deqtor容器的功能int main() /deq1對象初始為空 INTDEQUE deq1; /deq2對象最初有10個值為6的元素 INTDEQUE deq2(10,6); /聲明一個名為i的雙向迭代器變量 INTDEQUE:iterator i; /從前向后顯示deq1中的數(shù)據(jù) put_deque(d

25、eq1,deq1); /從前向后顯示deq2中的數(shù)據(jù) put_deque(deq2,deq2); /從deq1序列后面添加兩個元素 deq1.push_back(2); deq1.push_back(4); coutdeq1.push_back(2) and deq1.push_back(4):endl; put_deque(deq1,deq1); /從deq1序列前面添加兩個元素 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); /測試引用類函數(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序列的前后各移去一個元素 deq1.pop_front()

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

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

29、()：合并兩個排序列表；splice()：拼接兩個列表；sort()：列表的排序。#include #include #include using namespace std;void PrintIt(list n) for(list:iterator iter=n.begin(); iter!=n.end(); +iter) cout*iter ;/用迭代器進行輸出循環(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); /合并兩個排序列表后,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