的介紹及queuevector

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

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

3、TL設(shè)計者們已經(jīng)為我們考慮好了。使用STL編寫的代碼更容易修改和閱讀，這是當(dāng)然的啦。因?yàn)榇a更短了，很多基礎(chǔ)工作代碼已經(jīng)被組件化了；使用簡單，雖然內(nèi)部實(shí)現(xiàn)很復(fù)雜。雖然，STL的優(yōu)點(diǎn)甚多，但是STL的語法實(shí)在令初學(xué)者人頭疼，許多人望而卻步。可是STL是每個C+程序設(shè)計者遲早都要啃的一塊骨頭。3.      初識STL下面讓我們來看幾段代碼吧：#include <iostream>int main(void)    double a = 1, 2, 3, 4, 5;    st

4、d:cout<<mean(a, 5)<<std:endl;    / will print 3    return 0;好懂吧，除了那個std有點(diǎn)讓人不舒服以外，這是一段普通的沒有使用STL的C+代碼。再看下面一段：#include <vector>#include <iostream>int main()    std:vector<double> a;    a.push_back(1);  

5、  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:cout<<ai<<std:endl;        return

6、 0;如果你真的沒有接觸過STL的話，你會問，呀，vector 是啥呀？這是一段純種的STL代碼，看到尖括號了吧，知道那是模板了吧?？吹絘.push_back(5)、a.size()你不感覺奇怪么？可是我們并沒有定義這些函數(shù)啊。#include <vector>#include <iostream>int main()    std:vector< int > q;    q.push_back(10);    q.push_back(11);  &

7、#160; q.push_back(12);    std:vector< int > v;    for(int i=0; i<5; +i)        v.push_back(i);        std:vector<int>:iterator it = v.begin() + 1;    it = v.insert(it, 33);

8、60;   v.insert(it, q.begin(), q.end();    it = v.begin() + 3;    v.insert(it, 3, -1);    it = v.begin() + 4;    v.erase(it);    it = v.begin() + 1;    v.erase(it, it + 4);    v.clear();

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

10、板template<class T>   /template 是關(guān)鍵字，T 表示一種待實(shí)例化的類型                    /template<typename T> 也是對的T MAX(T a, T b)/函數(shù)模板，函數(shù)名為 max，此函數(shù)有2個T類型的參數(shù)，返回類型為Treturn (a>b)?a:b;/在此例實(shí)例化的時候，T可以是多種類型

11、的，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下面再看看，類模板：#include<iostream&g

12、t;using namespace std;/定義名為ex_class的類模板template < typename T> 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()  

13、;  /測試int類型數(shù)據(jù)    ex_class <int> a(5),b(10);    cout<<"a.value:"<<a.get_value()<<endl;    cout<<"b.value:"<<b.get_value()<<endl;    /測試char類型數(shù)據(jù)    ex_class <

14、;char> ch('A');    cout<<"ch.value:"<<ch.get_value()<<endl;    ch.set_value('a');    cout<<"ch.value:"<<ch.get_value()<<endl;    /測試double類型數(shù)據(jù)    ex_c

15、lass <double> x(5.5);    cout<<"x.value:"<<x.get_value()<<endl;    x.set_value(7.5);    cout<<"x.value:"<<x.get_value()<<endl;< STL>的組成STL有三大核心部分：容器（Container）、算法（Algorithms）、迭代器（Iterator

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

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

18、且可以用于普通的C數(shù)組或任何其他應(yīng)用程序指定的容器。迭代器(iterator)：一旦選定一種容器類型和數(shù)據(jù)行為(算法)，那么剩下唯一要他做的就是用迭代器使其相互作用?？梢园堰_(dá)代器看作一個指向容器中元素的普通指針?？梢匀邕f增一個指針那樣遞增迭代器，使其依次指向容器中每一個后繼的元素。迭代器是STL的一個關(guān)鍵部分，因?yàn)樗鼘⑺惴ê腿萜鬟B在一起。下面我將依次介紹STL的這三個主要組件。1.       容器STL中的容器有隊列容器和關(guān)聯(lián)容器，容器適配器（congtainer adapters：stack,queue，priority queu

19、e），位集（bit_set），串包(string_package)等等。在本文中，我將介紹list,vector，deque等隊列容器，和set和multisets,map和multimaps等關(guān)聯(lián)容器，一共7種基本容器類。隊列容器（順序容器）：隊列容器按照線性排列來存儲T類型值的集合，隊列的每個成員都有自己的特有的位置。順序容器有向量類型、雙端隊列類型、列表類型三種。u     基本容器向量向量（vector容器類）：include <vector>，vector是一種動態(tài)數(shù)組，是基本數(shù)組的類模板。其內(nèi)部定義了很多基本操作。既然這是一個類，

20、那么它就會有自己的構(gòu)造函數(shù)。vector 類中定義了4中種構(gòu)造函數(shù)：· 默認(rèn)構(gòu)造函數(shù)，構(gòu)造一個初始長度為0的空向量，如：vector<int> v1;· 帶有單個整形參數(shù)的構(gòu)造函數(shù)，此參數(shù)描述了向量的初始大小。這個構(gòu)造函數(shù)還有一個可選的參數(shù)，這是一個類型為T的實(shí)例，描述了各個向量種各成員的初始值；如：vector<int> v2(n,0); 如果預(yù)先定義了：n,他的成員值都被初始化為0；· 復(fù)制構(gòu)造函數(shù)，構(gòu)造一個新的向量，作為已存在的向量的完全復(fù)制，如：vector<int> v3(v2);· 帶兩個常量參數(shù)的構(gòu)造函數(shù)

21、，產(chǎn)生初始值為一個區(qū)間的向量。區(qū)間由一個半開區(qū)間first,last) 來指定。如：vector<int> v4(first,last）下面一個例子用的是第四種構(gòu)造方法，其它的方法讀者可以自己試試。/程序：初始化演示#include <cstring>#include <vector>#include <iostream>using namespace std;int ar10 = 12, 45, 234, 64, 12, 35, 63, 23, 12, 55 ;char* str = "Hello World"int mai

22、n()    vector <int> vec1(ar, ar+10);   /first=ar,last=ar+10,不包括ar+10    vector < char > vec2(str,str+strlen(str); /first=str,last= str+strlen(str),    cout<<"vec1:"<<endl;      /打印vec1和v

23、ec2，const_iterator是迭代器，后面會講到    /當(dāng)然，也可以用for (int i=0; i<vec1.size(); i+)cout << veci;輸出    /size()是vector的一個成員函數(shù)    for(vector<int>:const_iterator p=vec1.begin();p!=vec1.end(); +p)        cout<<*p;&#

24、160;       cout<<'n'<<"vec2:"<<endl;    for(vector< char >:const_iterator p1=vec2.begin();p1!=vec2.end(); +p1)        cout<<*p1;    cout<<'n'&#

25、160;   return 0;     為了幫助理解向量的概念，這里寫了一個小例子，其中用到了vector的成員函數(shù)：begin()，end()，push_back()，assign()，front()，back()，erase()，empty()，at()，size()。#include <iostream>#include <vector>using namespace std;typedef vector<int> INTVECTOR;/自定義類型INTVECTOR/測試vector容器的功

26、能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的雙向

27、迭代器    INTVECTOR:iterator i;    /從前向后顯示vec1中的數(shù)據(jù)    cout<<"vec1.begin()-vec1.end():"<<endl;    for (i =vec1.begin(); i !=vec1.end(); +i)        cout << *i << " "&

28、#160;   cout << endl;    /從前向后顯示vec2中的數(shù)據(jù)    cout<<"vec2.begin()-vec2.end():"<<endl;    for (i =vec2.begin(); i !=vec2.end(); +i)        cout << *i << " " &

29、#160;  cout << endl;    /從前向后顯示vec3中的數(shù)據(jù)    cout<<"vec3.begin()-vec3.end():"<<endl;    for (i =vec3.begin(); i !=vec3.end(); +i)        cout << *i << " "  &

30、#160; 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(

31、)+1,vec3.begin(),vec3.end();    cout<<"after push() and insert() now the vec1 is:" <<endl;    for (i =vec1.begin(); i !=vec1.end(); +i)        cout << *i << " "    cout <<

32、; endl;    /測試賦值成員函數(shù)    vec2.assign(8,1);   / 重新給vec2賦值，8個成員的初始值都為1    cout<<"vec2.assign(8,1):" <<endl;    for (i =vec2.begin(); i !=vec2.end(); +i)        cout << *i

33、 << " "    cout << endl;    /測試引用類函數(shù)    cout<<"vec1.front()="<<vec1.front()<<endl;/vec1第零個成員    cout<<"vec1.back()="<<vec1.back()<<endl;/vec1的最后一個成員  &#

34、160; cout<<"vec1.at(4)="<<vec1.at(4)<<endl;/vec1的第五個成員    cout<<"vec14="<<vec14<<endl;   /測試移出和刪除    vec1.pop_back();/將最后一個成員移出vec1    vec1.erase(vec1.begin()+1,vec1.end()-2);/刪除成員 

35、60;  cout<<"vec1.pop_back() and vec1.erase():" <<endl;    for (i =vec1.begin(); i !=vec1.end(); +i)        cout << *i << " "    cout << endl;    /顯示序列的狀態(tài)信息 

36、0;  cout<<"vec1.size(): "<<vec1.size()<<endl;/打印成員個數(shù)    cout<<"vec1.empty(): "<<vec1.empty()<<endl;/清空push_back()是將數(shù)據(jù)放入vector（向量）或deque（雙端隊列）的標(biāo)準(zhǔn)函數(shù)。Insert()是一個與之類似的函數(shù)，然而它在所有容器中都可以使用，但是用法更加復(fù)雜。end()實(shí)際上是取末尾加一，以便讓循環(huán)正確運(yùn)行-它返回的指針指向最

37、靠近數(shù)組界限的數(shù)據(jù)。在Java里面也有向量的概念。Java中的向量是對象的集合。其中，各元素可以不必同類型，元素可以增加和刪除，不能直接加入原始數(shù)據(jù)類型。u     雙端隊列（qeque容器類）：deque（讀音：deck，意即：double queue，#include<qeque>）容器類與vector類似，支持隨機(jī)訪問和快速插入刪除，它在容器中某一位置上的操作所花費(fèi)的是線性時間。與vector不同的是，deque還支持從開始端插入數(shù)據(jù)：push_front()。此外deque也不支持與vector的capacity()、reserve(

38、)類似的操作。#include <iostream>#include <deque>using namespace std;typedef deque<int> INTDEQUE;/有些人很討厭這種定義法，呵呵/從前向后顯示deque隊列的全部元素void put_deque(INTDEQUE deque, char *name)    INTDEQUE:iterator pdeque;/仍然使用迭代器輸出    cout << "The contents of "

39、<< name << " : "    for(pdeque = deque.begin(); pdeque != deque.end(); pdeque+)        cout << *pdeque << " "/注意有 "*"號哦，沒有"*"號的話會報錯    cout<<endl;/測試deqtor容器的功能int m

40、ain()    /deq1對象初始為空    INTDEQUE deq1;      /deq2對象最初有10個值為6的元素    INTDEQUE deq2(10,6);    /聲明一個名為i的雙向迭代器變量    INTDEQUE:iterator i;    /從前向后顯示deq1中的數(shù)據(jù)    put_deque(deq1,&

41、quot;deq1");    /從前向后顯示deq2中的數(shù)據(jù)    put_deque(deq2,"deq2");    /從deq1序列后面添加兩個元素    deq1.push_back(2);    deq1.push_back(4);    cout<<"deq1.push_back(2) and deq1.push_back(4):"<&

42、lt;endl;    put_deque(deq1,"deq1");    /從deq1序列前面添加兩個元素    deq1.push_front(5);    deq1.push_front(7);    cout<<"deq1.push_front(5) and deq1.push_front(7):"<<endl;    put_deque(de

43、q1,"deq1");    /在deq1序列中間插入數(shù)據(jù)    deq1.insert(deq1.begin()+1,3,9);    cout<<"deq1.insert(deq1.begin()+1,3,9):"<<endl;    put_deque(deq1,"deq1");    /測試引用類函數(shù)    cout<&

44、lt;"deq1.at(4)="<<deq1.at(4)<<endl;    cout<<"deq14="<<deq14<<endl;    deq1.at(1)=10;    deq12=12;    cout<<"deq1.at(1)=10 and deq12=12 :"<<endl;    put_

45、deque(deq1,"deq1");    /從deq1序列的前后各移去一個元素    deq1.pop_front();    deq1.pop_back();    cout<<"deq1.pop_front() and deq1.pop_back():"<<endl;    put_deque(deq1,"deq1");   

46、 /清除deq1中的第2個元素    deq1.erase(deq1.begin()+1);    cout<<"deq1.erase(deq1.begin()+1):"<<endl;    put_deque(deq1,"deq1");    /對deq2賦值并顯示    deq2.assign(8,1);    cout<<"d

47、eq2.assign(8,1):"<<endl;    put_deque(deq2,"deq2");上面我們演示了deque如何進(jìn)行插入刪除等操作，像erase(),assign()是大多數(shù)容器都有的操作。關(guān)于deque的其他操作請參閱其他書籍。u     表（List容器類）List（#include<list>）又叫鏈表，是一種雙線性列表，只能順序訪問（從前向后或者從后向前），圖2是list的數(shù)據(jù)組織形式。與前面兩種容器類有一個明顯的區(qū)別就是：它不支持隨機(jī)訪問。要訪

48、問表中某個下標(biāo)處的項需要從表頭或表尾處（接近該下標(biāo)的一端）開始循環(huán)。而且缺少下標(biāo)預(yù)算符：operator。圖2同時，list仍然包涵了erase(),begin(),end(),insert(),push_back(),push_front()這些基本函數(shù)，下面我們來演示一下list的其他函數(shù)功能。merge()：合并兩個排序列表；splice()：拼接兩個列表；sort()：列表的排序。#include <iostream>#include <string>#include <list>using namespace std;void PrintIt(li

49、st<int> n)    for(list<int>:iterator iter=n.begin(); iter!=n.end(); +iter)      cout<<*iter<<" "/用迭代器進(jìn)行輸出循環(huán)   int main()    list<int> listn1,listn2;    /給listn1,listn2初始化 

50、;   listn1.push_back(123);    listn1.push_back(0);    listn1.push_back(34);    listn1.push_back(1123);    /now listn1:123,0,34,1123    listn2.push_back(100);    listn2.push_back(12);   

51、 /now listn2:12,100    listn1.sort();    listn2.sort();    /給listn1和listn2排序    /now listn1:0,34,123,1123         listn2:12,100    PrintIt(listn1);    cout<<endl;&#

52、160;   PrintIt(listn2);    listn1.merge(listn2);    /合并兩個排序列表后,listn1:0，12，34，100，123，1123    cout<<endl;    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( )