STL入門基礎(chǔ)全實用教案

1、提綱(tgng) 1. 概論 2. 模板機制的介紹(jisho) 3. STL中的基本概念 4. 容器概述 5. 迭代器 6. 算法簡介第1頁/共67頁第一頁，共68頁。概論(giln) C+ 語言的核心優(yōu)勢之一就是便于軟件的重用 C+中有兩個方面體現(xiàn)(txin)重用： 1. 面向?qū)ο蟮乃枷耄豪^承和多態(tài)，標準類庫2. 泛型程序設(shè)計(generic programming) 的思想：模板機制，以及標準模板庫 STL這次(zh c)課的重點第2頁/共67頁第二頁，共68頁。泛型程序設(shè)計(chn x sh j) 泛型程序設(shè)計，簡單地說就是使用模板的程序設(shè)計法。 將一些常用的數(shù)據(jù)結(jié)構(gòu)（比如鏈表，數(shù)組，

2、二叉樹）和算法（比如排序，查找）寫成模板，以后則不論數(shù)據(jù)結(jié)構(gòu)里放的是什么對象，算法針對什么樣的對象，則都不必重新(chngxn)實現(xiàn)數(shù)據(jù)結(jié)構(gòu)，重新(chngxn)編寫算法。 標準模板庫 (Standard Template Library) 就是一些常用數(shù)據(jù)結(jié)構(gòu)和算法的模板的集合。主要由 Alex Stepanov 開發(fā)，于1998年被添加進C+標準 有了STL，不必再從頭寫大多的標準數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。第3頁/共67頁第三頁，共68頁。模板(mbn)引子1.假如設(shè)計一個求兩參數(shù)最大值的函數(shù)，在實踐中我們可能(knng)需要定義四個函數(shù)：int max ( int a ,

3、int b ) return ( a b ) ? a , b ; long max ( long a , long b ) return ( a b ) ? a , b ;double max ( double a , double b ) return ( a b)? a , b ; char max ( char a , char b ) return ( a b ) ? a , b ;2.這些函數(shù)幾乎相同，唯一的區(qū)別就是形參類型不同3.需要事先知道有哪些類型會使用這些函數(shù)，對于未知類型這些函數(shù)不起作用第4頁/共67頁第四頁，共68頁。模板(mbn)的概念1.所謂模板是一種使用無類型參數(shù)來

4、產(chǎn)生一系列函數(shù)或類的機制。2.若一個程序的功能是對某種特定(tdng)的數(shù)據(jù)類型進行處理，則可以將所處理的數(shù)據(jù)類型說明為參數(shù)，以便在其他數(shù)據(jù)類型的情況下使用，這就是模板的由來。3.模板是以一種完全通用的方法來設(shè)計函數(shù)或類而不必預(yù)先說明將被使用的每個對象的類型。4.通過模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個單獨的類或函數(shù)。 第5頁/共67頁第五頁，共68頁。模板(mbn)分類 函數(shù)模板(function template) 是獨立于類型(lixng)的函數(shù) 可產(chǎn)生函數(shù)的特定版本 類模板(class template) 跟類相關(guān)的模板，如vect

5、or 可產(chǎn)生類對特定類型(lixng)的版本，如vector6第6頁/共67頁第六頁，共68頁。求最大值模板函數(shù)(hnsh)實現(xiàn)1.求兩個數(shù)最大值，使用模板template T max(T a , T b)return ( a b ) ? a , b;2.template （模板函數(shù)(hnsh)形參表） /函數(shù)(hnsh)定義體7第7頁/共67頁第七頁，共68頁。模板(mbn)工作方式 函數(shù)模板只是說明，不能直接執(zhí)行，需要實例化為模板函數(shù)后才能執(zhí)行 在說明了一個函數(shù)模板后，當編譯系統(tǒng)發(fā)現(xiàn)有一個對應(yīng)的函數(shù)調(diào)用時，將根據(jù)實參中的類型來確認(qurn)是否匹配函數(shù)模板中對應(yīng)的形參，然后生成一個重載函

6、數(shù)。該重載函數(shù)的定義體與函數(shù)模板的函數(shù)定義體相同，它稱之為模板函數(shù)8第8頁/共67頁第八頁，共68頁。#include template T min(T a,int n)int i;T minv=a0;f o r ( i = 1 ; i ai) minv=ai;return minv;編寫一個對具有n個元素的數(shù)組a 求最小值的程序，要求將求最小值的函數(shù)設(shè)計(shj)成函數(shù)模板。void main() ina a=1,3,0,2,7,6,4,5,2; double b=1.2,-3.4,6.8,9,8; cout”a數(shù)組的最小值為：” min(a,9) endl; cout”b數(shù)組的最小值為：”

7、 min(b,4)endl; 此程序的運行(ynxng)結(jié)果為：a數(shù)組的最小值為：0b數(shù)組的最小值為：-3.4第9頁/共67頁第九頁，共68頁。模板(mbn)優(yōu)缺點 函數(shù)模板方法克服了C語言解決上述問題時用大量不同函數(shù)名表示相似功能的壞習(xí)慣 克服了宏定義不能進行參數(shù)類型檢查( jinch)的弊端 克服了C+函數(shù)重載用相同函數(shù)名字重寫幾個函數(shù)的繁瑣 缺點，調(diào)試比較困難 一般先寫一個特殊版本的函數(shù) 運行正確后，改成模板函數(shù)10第10頁/共67頁第十頁，共68頁。STL中的幾個(j )基本概念 容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。 迭代器：可依次存取容器中元素的東西 算法(sun f)：用來操作容器

8、中的元素的函數(shù)模板。例如，STL用sort()來對一個vector中的數(shù)據(jù)進行排序，用find()來搜索一個list中的對象。 函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無關(guān)，因此他們可以在從簡單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用。 比如，數(shù)組int array100就是個容器，而 int * 類型的指針變量就可以作為迭代器，可以為這個容器編寫一個排序的算法(sun f)第11頁/共67頁第十一頁，共68頁。容器(rngq)概述 可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對象等）的數(shù)據(jù)結(jié)構(gòu)。 容器分為三大類： 1) 順序容器 vector：后部插入/刪除(shnch)，直接訪問deque：前/

9、后部插入/刪除(shnch)，直接訪問list：雙向鏈表，任意位置插入/刪除(shnch) 2)關(guān)聯(lián)容器set：快速查找，無重復(fù)元素multiset ：快速查找，可有重復(fù)元素map：一對一映射，無重復(fù)元素，基于關(guān)鍵字查找multimap ：一對一映射，可有重復(fù)元素，基于關(guān)鍵字查找 前2者合稱為第一類容器 3)容器適配器stack：LIFOqueue：FIFOpriority_queue：優(yōu)先級高的元素先出 第12頁/共67頁第十二頁，共68頁。容器(rngq)概述 對象被插入容器中時，被插入的是對象的一個復(fù)制品。 許多算法，比如排序，查找，要求對容器中的元素進行比較，所以(suy)，放入容器的

10、對象所屬的類，還應(yīng)該實現(xiàn) = 和 運算符。第13頁/共67頁第十三頁，共68頁。順序(shnx)容器簡介1) vector 頭文件 實際上就是個動態(tài)數(shù)組。隨機存取任何元素都能在常數(shù)時間完成。在尾端增刪元素具有較佳的性能。 2) deque 頭文件 也是個動態(tài)數(shù)組，隨機存取任何元素都能在常數(shù)時間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。 3) list 頭文件 雙向鏈表，在任何位置增刪元素都能在常數(shù)時間完成。不支持隨機存取。 上述(shngsh)三種容器稱為順序容器，是因為元素的插入位置同元素的值無關(guān)，只跟插入的時機有關(guān)。第14頁/共67頁第十四頁，共68頁。關(guān)聯(lián)容器(rng

11、q)簡介 關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準則來確定其位置。關(guān)聯(lián)式容器的特點是在查找時具有非常好的性能。 1) set/multiset: 頭文件 set 即集合。set中不允許相同元素，multiset中允許存在相同的元素。 2) map/multimap: 頭文件 map與set的不同在于map中存放的是成對的key/value。 并根據(jù)key對元素進行排序，可快速地根據(jù)key來檢索元素 map同multimap的不同在于是否允許多個元素有相同的key值。 上述4種容器通常以平衡二叉樹方式實現(xiàn)，插入、查找和刪除(shnch)的時間都是 O(logN)第15頁/共67

12、頁第十五頁，共68頁。容器(rngq)適配器簡介1) stack :頭文件 棧。是項的有限序列，并滿足序列中被刪除、檢索和修改(xigi)的項只能是最近插入序列的項。即按照后進先出的原則2) queue :頭文件 隊列。插入只可以在尾部進行，刪除、檢索和修改(xigi)只允許從頭部進行。按照先進先出的原則。3）priority_queue :頭文件 優(yōu)先級隊列。最高優(yōu)先級元素總是第一個出列第16頁/共67頁第十六頁，共68頁。容器的共有(n yu)成員函數(shù)1) 所有標準庫容器共有的成員函數(shù)：相當于按詞典順序(shnx)比較兩個容器大小的運算符： =, , , =, = , !=empty :

13、判斷容器中是否有元素max_size: 容器中最多能裝多少元素size: 容器中元素個數(shù)swap: 交換兩個容器的內(nèi)容第17頁/共67頁第十七頁，共68頁。比較兩個容器(rngq)的例子18比較(bjio)兩個容器的例子：#include #include int main()std:vector v1;std:vector v2;v1.push_back (5); v1.push_back (1);v2.push_back (1); v2.push_back (2);v2.push_back (3);std:cout (v1 v2); return 0;若兩容器長度相同、所有元素相等，則兩個

14、容器就相等，否則為不等。若兩容器長度不同，但較短容器中所有元素都等于較長容器中對應(yīng)的元素，則較短容器小于另一個容器若兩個容器均不是對方的子序列(xli)，則取決于所比較的第一個不等的元素輸出：0第18頁/共67頁第十八頁，共68頁。容器的成員(chngyun)函數(shù) 2) 只在第一類容器中的函數(shù)：begin 返回指向容器中第一個元素(yun s)的迭代器end 返回指向容器中最后一個元素(yun s)后面的位置的迭代器rbegin 返回指向容器中最后一個元素(yun s)的迭代器rend 返回指向容器中第一個元素(yun s)前面的位置的迭代器erase 從容器中刪除一個或幾個元素(yun s)

15、clear 從容器中刪除所有元素(yun s)HeadTailbeginrbeginrendend第19頁/共67頁第十九頁，共68頁。迭代(di di)器 用于指向第一類容器中的元素。有const 和非 const兩種。 通過迭代器可以讀取它指向的元素，通過非const迭代器還能修改其指向的元素。迭代器用法和指針類似。 定義(dngy)一個容器類的迭代器的方法可以是：容器類名:iterator 變量名; 或：容器類名:const_iterator 變量名; 訪問一個迭代器指向的元素：* 迭代器變量名第20頁/共67頁第二十頁，共68頁。迭代(di di)器 迭代器上可以執(zhí)行 + 操作, 以指

16、向容器中的下一個元素。如果迭代器到達了容器中的最后一個元素的后面，則迭代器變成past-the-end值。 使用一個past-the-end值的迭代器來訪問對象是非法的，就好像(ho xin)使用NULL或未初始化的指針一樣。第21頁/共67頁第二十一頁，共68頁。例如：#include #include using namespace std;int main() vector v; /一個存放int元素的向量，一開始里面沒有(mi yu)元素v.push_back(1);v.push_back(2); v.push_back(3); v.push_back(4);vector:const_

17、iterator i; /常量迭代器for( i = v.begin();i != v.end();i + ) cout * i ,;cout endl;第22頁/共67頁第二十二頁，共68頁。vector:reverse_iterator r; /反向迭代器for( r = v.rbegin();r != v.rend();r+ ) cout * r ,;cout endl;vector:iterator j; /非常量迭代器for( j = v.begin();j != v.end();j + ) * j = 100;for( i = v.begin();i != v.end();i+ )

18、 cout * i ,;輸出(shch)結(jié)果：1,2,3,4,4,3,2,1,100,100,100,100,第23頁/共67頁第二十三頁，共68頁。迭代(di di)器 不同容器上支持的迭代器功能強弱(qin ru)有所不同。 容器的迭代器的功能強弱(qin ru)，決定了該容器是否支持STL中的某種算法。 例1：只有第一類容器能用迭代器遍歷。 例2：排序算法需要通過隨機迭代器來訪問容器中的元素，那么有的容器就不支持排序算法。第24頁/共67頁第二十四頁，共68頁。STL 中的迭代(di di)器 STL 中的迭代器按功能由弱到強分為5種： 1. 輸入：Input iterators 提供(

19、tgng)對數(shù)據(jù)的只讀訪問。 1. 輸出：Output iterators 提供(tgng)對數(shù)據(jù)的只寫訪問 2. 正向：Forward iterators 提供(tgng)讀寫操作，并能一次一個地向前推進迭代器。 3. 雙向：Bidirectional iterators提供(tgng)讀寫操作，并能一次一個地向前和向后移動。 4. 隨機訪問：Random access iterators提供(tgng)讀寫操作，并能在數(shù)據(jù)中隨機移動。 編號大的迭代器擁有編號小的迭代器的所有功能，能當作編號小的迭代器使用。第25頁/共67頁第二十五頁，共68頁。不同迭代(di di)器所能進行的操作(功能）

20、 所有迭代器： +p, p + 輸入迭代器： * p, p = p1, p = p1 , p!= p1 輸出迭代器： * p, p = p1 正向迭代器： 上面(shng min)全部 雙向迭代器： 上面(shng min)全部，-p, p -, 隨機訪問迭代器： 上面(shng min)全部，以及：p+= i, p -= i, p + i： 返回指向 p 后面的第i個元素的迭代器p - i： 返回指向 p 前面的第i個元素的迭代器 pi: p 后面的第i個元素的引用p p1, p p1, p= p1第26頁/共67頁第二十六頁，共68頁。容器所支持(zhch)的迭代器類別容器迭代器類別(li

21、bi)vector隨機deque隨機list 雙向set/multiset雙向map/multimap雙向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器第27頁/共67頁第二十七頁，共68頁。例如，vector的迭代器是隨機迭代器，所以遍歷 vector 可以有以下幾種(j zhn)做法：vector v(100);int i; for(i = 0;i v.size() ; i +)cout vi;vector:const_iterator ii;for( ii = v.begin(); ii != v.end ();ii + )cout * ii;/間隔

22、一個輸出：ii = v.begin();while( ii v.end() cout * ii; ii = ii + 2; 第28頁/共67頁第二十八頁，共68頁。而 list 的迭代(di di)器是雙向迭代(di di)器，所以以下代碼可以：list v;list:const_iterator ii;for( ii = v.begin(); ii ！ v.end ();ii + )cout * ii;以下代碼則不行：for( ii = v.begin(); ii v.end ();ii + )cout * ii;/雙向迭代(di di)器不支持 for(int i = 0;i v.size

23、() ; i +)cout vi; /雙向迭代(di di)器不支持 第29頁/共67頁第二十九頁，共68頁。算法(sun f)簡介 STL中提供能在各種容器中通用的算法，比如插入，刪除，查找，排序等。大約有70種標準算法。算法就是( jish)一個個函數(shù)模板。算法通過迭代器來操縱容器中的元素。許多算法需要兩個參數(shù)，一個是起始元素的迭代器，一個是終止元素的后面一個元素的迭代器。比如，排序和查找有的算法返回一個迭代器。比如 find() 算法，在容器中查找一個元素，并返回一個指向該元素的迭代器。算法可以處理容器，也可以處理C語言的數(shù)組第30頁/共67頁第三十頁，共68頁。算法(sun f)分類

24、變化序列算法 copy ,remove,fill,replace,random_shuffle,swap, . 會改變?nèi)萜?非變化序列算法： adjacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_n 以上函數(shù)模板都在 中定義 此外(cwi)還有其他算法，比如中的算法第31頁/共67頁第三十一頁，共68頁。算法(sun f)示例：find()templateInIt find(InIt first, InIt last, const T& val); first 和 last 這兩個參

25、數(shù)都是容器的迭代器，它們(t men)給出了容器中的查找區(qū)間起點和終點。這個區(qū)間是個左閉右開的區(qū)間，即區(qū)間的起點是位于查找范圍之中的，而終點不是val參數(shù)是要查找的元素的值函數(shù)返回值是一個迭代器。如果找到，則該迭代器指向被找到的元素。如果找不到，則該迭代器指向查找區(qū)間終點。第32頁/共67頁第三十二頁，共68頁。#include #include #include using namespace std;int main() int array10 = 10,20,30,40;vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.pus

26、h_back(4);vector:iterator p;p = find(v.begin(),v.end(),3);if( p != v.end()cout * p endl;第33頁/共67頁第三十三頁，共68頁。p = find(v.begin(),v.end(),9);if( p = v.end()cout not found endl;p = find(v.begin()+1,v.end()-2,1);if( p != v.end()cout * p endl;int * pp = find( array,array+4,20);cout * pp endl;輸出(shch)：3not

27、 found320第34頁/共67頁第三十四頁，共68頁。順序(shnx)容器 除前述共同操作外，順序容器還有以下共同操作：front() :返回(fnhu)容器中第一個元素的引用back() : 返回(fnhu)容器中最后一個元素的引用push_back(): 在容器末尾增加新元素pop_back(): 刪除容器末尾的元素第35頁/共67頁第三十五頁，共68頁。vector 支持隨機訪問迭代器，所有STL算法都能對vector操作。 隨機訪問時間為常數(shù)。在尾部添加速度(sd)很快，在中間插入慢。實際上就是動態(tài)數(shù)組。第36頁/共67頁第三十六頁，共68頁。例1：int main() int i

28、;int a5 = 1,2,3,4,5 ; vector v(5);cout v.end() - v.begin() endl;for( i = 0;i v.size();i + ) vi = i;v.at(4) = 100;for( i = 0;i v.size();i + )cout vi , ;cout endl;vector v2(a,a+5); /構(gòu)造函數(shù)v2.insert( v2.begin() + 2, 13 ); /在begin()+2位置(wi zhi)插入 13for( i = 0;i v2.size();i + )cout v2i , ; return 0;第37頁/共6

29、7頁第三十七頁，共68頁。輸出(shch)：50,1,2,3,100,1,2,13,3,4,5,第38頁/共67頁第三十八頁，共68頁。例2：int main() const int SIZE = 5;int aSIZE = 1,2,3,4,5 ; vector v (a,a+5); /構(gòu)造函數(shù)try v.at(100) = 7;catch( out_of_range e) cout e.what() endl;cout v.front() “,” v.back() endl;v.erase(v.begin();ostream_iterator output(cout ,“*);copy (v

30、.begin(),v.end(),output);v.erase( v.begin(),v.end(); /等效于 v.clear();第39頁/共67頁第三十九頁，共68頁。if( v.empty ()cout empty endl;v.insert (v.begin(),a,a+SIZE);copy (v.begin(),v.end(),output); / 輸出(shch)：invalid vector subscript1,52*3*4*5*empty1*2*3*4*5*第40頁/共67頁第四十頁，共68頁。算法(sun f)解釋 ostream_iterator output(cou

31、t ,“*); 定義了一個 ostream_iterator 對象，可以通過cout輸出以 * 分隔的一個個整數(shù) copy (v.begin(),v.end(),output); 導(dǎo)致v的內(nèi)容在 cout上輸出 copy 函數(shù)模板(算法）： template OutIt copy(InIt first, InIt last, OutIt x); 本函數(shù)對每個在區(qū)間0, last - first)中的N執(zhí)行(zhxng)一次 *(x+N) = * ( first + N) ，返回 x + N 對于copy (v.begin(),v.end(),output); first 和 last 的類型是

32、 vector:const_iterator output 的類型是 ostream_iterator 第41頁/共67頁第四十一頁，共68頁。list 容器(rngq) 在任何位置插入刪除都是常數(shù)時間，不支持隨機存取。除了具有所有順序容器都有的成員函數(shù)以外，還支持8個成員函數(shù)： push_front: 在前面插入 pop_front: 刪除前面的元素 sort: 排序( list 不支持STL 的算法sort) remove: 刪除和指定值相等的所有元素 unique: 刪除所有和前一個元素相同的元素 merge: 合并兩個鏈表，并清空被合并的那個(n ge) reverse: 顛倒鏈表 s

33、plice: 在指定位置前面插入另一鏈表中的一個或多個元素,并在另一鏈表中刪除被插入的元素第42頁/共67頁第四十二頁，共68頁。deque 容器(rngq) 所有適用于vector的操作都適用于deque deque還有push_front（將元素插入(ch r)到前面）和pop_front(刪除最前面的元素）操作第43頁/共67頁第四十三頁，共68頁。44關(guān)聯(lián)(gunlin)容器 set, multiset, map, multimap內(nèi)部元素有序排列，新元素插入的位置取決于它的值，查找速度快 map關(guān)聯(lián)數(shù)組：元素通過鍵來存儲和讀取 set大小可變的集合，支持通過鍵實現(xiàn)(shxin)的快速

34、讀取 multimap支持同一個鍵多次出現(xiàn)的map類型 multiset支持同一個鍵多次出現(xiàn)的set類型 與順序容器的本質(zhì)區(qū)別 關(guān)聯(lián)容器是通過鍵(key)存儲和讀取元素的 而順序容器則通過元素在容器中的位置順序存儲和訪問元素。 第44頁/共67頁第四十四頁，共68頁。45關(guān)聯(lián)(gunlin)容器 除了各容器都有的函數(shù)外，還支持以下成員函數(shù)：設(shè)m表容器，k表鍵值m.find(k) ：如果容器中存在(cnzi)鍵為k的元素，則返回指向該元素的迭代器。如果不存在(cnzi)，則返回end()值。 m.lower_bound(k)：返回一個迭代器，指向鍵不小于k的第一個元素 m.upper_bound

35、(k)：返回一個迭代器，指向鍵大于k的第一個元素 m.count(k) ：返回m中k的出現(xiàn)次數(shù) 插入元素用 insert 第45頁/共67頁第四十五頁，共68頁。46settemplateclass Key, class Pred = less, class A = allocator class set 插入set中已有的元素(yun s)時，插入不成功。第46頁/共67頁第四十六頁，共68頁。47pair模板(mbn) pair模板類用來綁定兩個對象為一個新的對象，該類型在頭文件中定義。 pair模板類支持如下操作： pair p1：創(chuàng)建一個空的pair對象，它的兩個元素分別是T1和T2類

36、型，采用(ciyng)值初始化 pair p1(v1, v2)：創(chuàng)建一個pair對象，它的兩個元素分別是T1和T2類型，其中first成員初始化為v1，second成員初始化為v2 make_pair(v1, v2)：以v1和v2值創(chuàng)建一個新的pair對象，其元素類型分別是v1和v2的類型 p1 p2字典次序：如果p1.firstp2.first或者!(p2.first p1.first)& p1.secondp2.second，則返回true p1 = p2：如果兩個pair對象的first和second成員依次相等，則這兩個對象相等。 p.first：返回p中名為first的（公有

37、）數(shù)據(jù)成員 p.second：返回p中名為second的（公有）數(shù)據(jù)成員第47頁/共67頁第四十七頁，共68頁。#include #include using namespace std;int main() typedef setdouble,less double_set;const int SIZE = 5;double aSIZE = 2.1,4.2,9.5,2.1,3.7 ;double_set doubleSet(a,a+SIZE);ostream_iterator output(cout, );cout 1) ;copy(doubleSet.begin(),doubleSet.e

38、nd(),output);cout endl; pair p; p = doubleSet.insert(9.5); if( p.second ) cout 2) * (p.first) inserted endl; else cout 2) * (p.first) not inserted endl; return 0; insert函數(shù)返回值是一個(y )pair對象, 其first是被插入元素的迭代器，second代表是否成功插入了第48頁/共67頁第四十八頁，共68頁。輸出(shch)：1) 2.1 3.7 4.2 9.52) 9.5 not inserted第49頁/共67頁第四十九

39、頁，共68頁。50multimaptemplateclass Key, class T, class Pred = less, class A = allocator class multimap .typedef pair value_type; . ; /Key 代表關(guān)鍵字multimap中的元素由 組成，每個元素是一個pair對象(duxing)。multimap 中允許多個元素的關(guān)鍵字相同。元素按照關(guān)鍵字升序排列，缺省情況下用 less 定義關(guān)鍵字的“小于”關(guān)系第50頁/共67頁第五十頁，共68頁。51maptemplateclass Key, class T, class Pred

40、= less, class A = allocator class map .typedef pair value_type; . ;map 中的元素關(guān)鍵字各不相同。元素按照關(guān)鍵字升序排列(pili)，缺省情況下用 less 定義“小于”第51頁/共67頁第五十一頁，共68頁。52map可以(ky)用pairskey 訪形式問map中的元素。pairs 為map容器名，key為關(guān)鍵字的值。該表達式返回的是對關(guān)鍵值為key的元素的值的引用。如果沒有關(guān)鍵字為key的元素，則會往pairs里插入一個關(guān)鍵字為key的元素，并返回其值的引用如：map pairs;則 pairs50 = 5; 會修改pa

41、irs中關(guān)鍵字為50的元素，使其值變成5第52頁/共67頁第五十二頁，共68頁。#include #include using namespace std;ostream & operator ( ostream & o,const pair & p)o ( p.first , p.second );return o;int main() typedef mapint,double,less mmid;mmid pairs;cout 1) pairs.count(15) endl;pairs.insert(mmid:value_type(15,2.7);pairs.in

42、sert(make_pair(15,99.3);/make_pair生成(shn chn)pair對象cout 2) pairs.count(15) endl;pairs.insert(mmid:value_type(20,9.3);第53頁/共67頁第五十三頁，共68頁。 mmid:iterator i; cout 3) ; for( i = pairs.begin(); i != pairs.end();i + ) cout * i ,;cout endl;cout 4) ;int n = pairs40;/如果沒有關(guān)鍵字為40的元素，則插入一個(y )for( i = pairs.beg

43、in(); i != pairs.end();i + )cout * i ,;cout endl;cout 5) ;pairs15 = 6.28; /把關(guān)鍵字為15的元素值改成6.28for( i = pairs.begin(); i != pairs.end();i + )cout * i ,; return 0;第54頁/共67頁第五十四頁，共68頁。輸出(shch)：1) 02) 13) (15,2.7),(20,9.3),4) (15,2.7),(20,9.3),(40,0),5) (15,6.28),(20,9.3),(40,0),第55頁/共67頁第五十五頁，共68頁。56思考題

44、如何用程序用來統(tǒng)計一篇英文文章中單詞(dnc)出現(xiàn)的頻率（為簡單起見，假定依次從鍵盤輸入該文章） #include #include using namespace std;int main() map wordCount; string word; while (cin word) +wordCountword; for (map:iterator it = wordCount.begin(); it != wordCount.end(); +it) coutWord: (*it).first tCount: (*it).secondendl; return 0;第56頁/共67頁第五十六頁

45、，共68頁。57容器(rngq)適配器:stack 可用 vector, list, deque來實現(xiàn) 缺省情況下，用deque實現(xiàn) 用 vector和deque實現(xiàn)，比用list實現(xiàn)性能好 templateclass T, class Cont = deque class stack . ; stack 是后進先出的數(shù)據(jù)結(jié)構(gòu)，只能插入、刪除、訪問(fngwn)棧頂?shù)脑氐?7頁/共67頁第五十七頁，共68頁。58容器(rngq)適配器:stack stack 上可以進行以下操作：push: 插入元素(yun s)pop:彈出元素(yun s)top:返回棧頂元素(yun s)的引用第58頁/

46、共67頁第五十八頁，共68頁。59容器(rngq)適配器: queue和stack 基本類似，可以用 list和deque實現(xiàn)，缺省情況(qngkung)下用deque實現(xiàn)templateclass T, class Cont = deque class queue ;同樣也有push,pop,top函數(shù)但是push發(fā)生在隊尾，pop,top發(fā)生在隊頭，先進先出第59頁/共67頁第五十九頁，共68頁。60容器(rngq)適配器: priority_queue 和 queue類似，可以用vector和deque實現(xiàn)，缺省情況下用vector實現(xiàn)。 priority_queue 通常用堆排序技術(shù)實現(xiàn)，保證最大的元素(yun s)總是在最前面。即執(zhí)行pop操作時，刪除的是最大的元素(yun s)，執(zhí)行top操作時，返回的是最大元素(yun s)的引用。默認的元素(yun