STL講義-課件(PPT 86頁)

1、C+模板與STL庫(kù)介紹1學(xué)習(xí)交流PPT第1頁，共86頁。提綱1. 概論2. 模板機(jī)制的介紹3. STL中的基本概念4. 容器概述5. 迭代器6. 算法簡(jiǎn)介2學(xué)習(xí)交流PPT第2頁，共86頁。概論C+ 語言的核心優(yōu)勢(shì)之一就是便于軟件的重用C+中有兩個(gè)方面體現(xiàn)重用：1. 面向?qū)ο蟮乃枷耄豪^承和多態(tài)，標(biāo)準(zhǔn)類庫(kù)2. 泛型程序設(shè)計(jì)(generic programming) 的思想：模板機(jī)制，以及標(biāo)準(zhǔn)模板庫(kù) STL3學(xué)習(xí)交流PPT第3頁，共86頁。泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)，簡(jiǎn)單地說就是使用模板的程序設(shè)計(jì)法。將一些常用的數(shù)據(jù)結(jié)構(gòu)（比如鏈表，數(shù)組，二叉樹）和算法（比如排序，查找）寫成模板，以后則不論數(shù)據(jù)結(jié)構(gòu)里放

2、的是什么對(duì)象，算法針對(duì)什么樣的對(duì)象，則都不必重新實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，重新編寫算法。標(biāo)準(zhǔn)模板庫(kù) (Standard Template Library) 就是一些常用數(shù)據(jù)結(jié)構(gòu)和算法的模板的集合。主要由 Alex Stepanov 開發(fā)，于1998年被添加進(jìn)C+標(biāo)準(zhǔn)有了STL，不必再?gòu)念^開始編寫繁多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算法，并且一樣可獲得非常高的性能。4學(xué)習(xí)交流PPT第4頁，共86頁。模板引子1.假如設(shè)計(jì)一個(gè)求兩參數(shù)最大值的函數(shù)，在實(shí)踐中我們可能需要定義四個(gè)函數(shù)：int max ( int a , int b ) return ( a b ) ? a , b ; long max ( long a , lon

3、g 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.需要事先知道有哪些類型會(huì)使用這些函數(shù)，對(duì)于未知類型這些函數(shù)不起作用5學(xué)習(xí)交流PPT第5頁，共86頁。模板的概念所謂模板是一種使用無類型參數(shù)來產(chǎn)生一系列函數(shù)或類的機(jī)制。若一個(gè)程序的功能是對(duì)某種特定的數(shù)據(jù)類型進(jìn)行處理，則可以將所處理的數(shù)據(jù)類型說明為參數(shù)，以便在其他數(shù)據(jù)類

4、型的情況下使用，這就是模板的由來。模板是以一種完全通用的方法來設(shè)計(jì)函數(shù)或類而不必預(yù)先說明將被使用的每個(gè)對(duì)象的類型。通過模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個(gè)單獨(dú)的類或函數(shù)。 6學(xué)習(xí)交流PPT第6頁，共86頁。模板分類函數(shù)模板(function template)是獨(dú)立于類型的函數(shù)可產(chǎn)生函數(shù)的特定版本類模板(class template)跟類相關(guān)的模板，如vector可產(chǎn)生類對(duì)特定類型的版本，如vector7學(xué)習(xí)交流PPT第7頁，共86頁。求最大值模板函數(shù)實(shí)現(xiàn)1.求兩個(gè)數(shù)最大值，使用模板template T max(T a , T b)retu

5、rn ( a b ) ? a , b;2.template （模板函數(shù)形參表） /函數(shù)定義體8學(xué)習(xí)交流PPT第8頁，共86頁。模板工作方式函數(shù)模板只是說明，不能直接執(zhí)行，需要實(shí)例化為模板函數(shù)后才能執(zhí)行在說明了一個(gè)函數(shù)模板后，當(dāng)編譯系統(tǒng)發(fā)現(xiàn)有一個(gè)對(duì)應(yīng)的函數(shù)調(diào)用時(shí)，將根據(jù)實(shí)參中的類型來確認(rèn)是否匹配函數(shù)模板中對(duì)應(yīng)的形參，然后生成一個(gè)重載函數(shù)。該重載函數(shù)的定義體與函數(shù)模板的函數(shù)定義體相同，它稱之為模板函數(shù)9學(xué)習(xí)交流PPT第9頁，共86頁。#include template T min(T a,int n)int i;T minv=a0;for( i = 1;i ai) minv=ai;return m

6、inv;編寫一個(gè)對(duì)具有n個(gè)元素的數(shù)組a 求最小值的程序，要求將求最小值的函數(shù)設(shè)計(jì)成函數(shù)模板。void main() int 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ù)組的最小值為：” min(b,4)endl; 此程序的運(yùn)行結(jié)果為：a數(shù)組的最小值為：0b數(shù)組的最小值為：-3.410學(xué)習(xí)交流PPT第10頁，共86頁。函數(shù)模板與類模板使用時(shí)有何不同?函數(shù)模板使用時(shí)不提供類型參數(shù)比如: 直接調(diào)用 min(a, 9);類模板使用時(shí)要求提供類型參數(shù)比如: vector v,

7、其中int就是類型參數(shù)11學(xué)習(xí)交流PPT第11頁，共86頁。模板優(yōu)缺點(diǎn)函數(shù)模板方法克服了C語言解決上述問題時(shí)用大量不同函數(shù)名表示相似功能的壞習(xí)慣克服了宏定義不能進(jìn)行參數(shù)類型檢查的弊端克服了C+函數(shù)重載用相同函數(shù)名字重寫幾個(gè)函數(shù)的繁瑣缺點(diǎn)，調(diào)試比較困難一般先寫一個(gè)特殊版本的函數(shù)運(yùn)行正確后，改成模板函數(shù)12學(xué)習(xí)交流PPT第12頁，共86頁。STL中的幾個(gè)基本概念容器：可容納各種數(shù)據(jù)類型的多元素?cái)?shù)據(jù)結(jié)構(gòu)。迭代器：可依次存取容器中元素的東西(指針？下標(biāo)?)算法：用來操作容器中的元素的函數(shù)模板。例如，STL用sort()來對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來搜索一個(gè)list中的對(duì)象。函數(shù)

8、本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用。比如，數(shù)組int array100就是個(gè)容器，而 int * 類型的指針變量就可以作為迭代器，可以為這個(gè)容器編寫一個(gè)排序的算法13學(xué)習(xí)交流PPT第13頁，共86頁。容器概述可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對(duì)象等）的數(shù)據(jù)結(jié)構(gòu)。容器分為三大類：1) 順序容器 vector：后部插入/刪除，直接訪問deque：前/后部插入/刪除，直接訪問list：雙向鏈表，任意位置插入/刪除2)關(guān)聯(lián)容器set：快速查找，無重復(fù)元素multiset ：快速查找，可有重復(fù)元素map：一對(duì)一映射，無重復(fù)元素，基于

9、關(guān)鍵字查找multimap ：一對(duì)一映射，可有重復(fù)元素，基于關(guān)鍵字查找前2者合稱為第一類容器 3)容器適配器stack：LIFOqueue：FIFOpriority_queue：優(yōu)先級(jí)高的元素先出 14學(xué)習(xí)交流PPT第14頁，共86頁。容器概述對(duì)象被插入容器中時(shí)，被插入的是對(duì)象的一個(gè)復(fù)制品。許多算法，比如排序，查找，要求對(duì)容器中的元素進(jìn)行比較，所以，放入容器的對(duì)象所屬的類，還應(yīng)該實(shí)現(xiàn) = 和 運(yùn)算符。15學(xué)習(xí)交流PPT第15頁，共86頁。順序容器簡(jiǎn)介1) vector 頭文件 實(shí)際上就是個(gè)動(dòng)態(tài)數(shù)組。隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成。在尾端增刪元素具有較佳的性能。 2) deque 頭文件 也

10、是個(gè)動(dòng)態(tài)數(shù)組，隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。 3) list 頭文件 雙向鏈表，在任何位置增刪元素都能在常數(shù)時(shí)間完成。不支持隨機(jī)存取。 上述三種容器稱為順序容器，是因?yàn)樵氐牟迦胛恢猛氐闹禑o關(guān)。16學(xué)習(xí)交流PPT第16頁，共86頁。關(guān)聯(lián)容器簡(jiǎn)介關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來確定其位置。關(guān)聯(lián)式容器的特點(diǎn)是在查找時(shí)具有非常好的性能。1) set/multiset: 頭文件 set 即集合。set中不允許相同元素，multiset中允許存在相同的元素。2) map/multimap: 頭文件 map與s

11、et的不同在于map中存放的是成對(duì)的key/value。 并根據(jù)key對(duì)元素進(jìn)行排序，可快速地根據(jù)key來檢索元素 map同multimap的不同在于是否允許多個(gè)元素有相同的key值。 上述4種容器通常以平衡二叉樹方式實(shí)現(xiàn)，插入和檢索的時(shí)間都是 O(logN)17學(xué)習(xí)交流PPT第17頁，共86頁。容器適配器簡(jiǎn)介1) stack :頭文件 棧。是項(xiàng)的有限序列，并滿足序列中被刪除、檢索和修改的項(xiàng)只能是最近插入序列的項(xiàng)。即按照后進(jìn)先出的原則2) queue :頭文件 隊(duì)列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照先進(jìn)先出的原則。3）priority_queue :頭文件 優(yōu)先級(jí)隊(duì)

12、列。最高優(yōu)先級(jí)元素總是第一個(gè)出列18學(xué)習(xí)交流PPT第18頁，共86頁。容器的共有成員函數(shù)1) 所有標(biāo)準(zhǔn)庫(kù)容器共有的成員函數(shù)：相當(dāng)于按詞典順序比較兩個(gè)容器大小的運(yùn)算符： =, , , =, = , !=empty : 判斷容器中是否有元素max_size: 容器中最多能裝多少元素size: 容器中元素個(gè)數(shù)swap: 交換兩個(gè)容器的內(nèi)容19學(xué)習(xí)交流PPT第19頁，共86頁。比較兩個(gè)容器的例子比較兩個(gè)容器的例子：#include #include int main()std:vector v1;std:vector v2;v1.push_back (5); v1.push_back (1);v2.p

13、ush_back (1); v2.push_back (2);v2.push_back (3);std:cout (v1 , pre and post / increment, and equality testing operators / come hereprivate: ChainNode *current;24學(xué)習(xí)交流PPT第24頁，共86頁。ConstructorChainIterator(ChainNode * startNode = 0) current = startNode;25學(xué)習(xí)交流PPT第25頁，共86頁。Dereferencing OperatorsT& opera

14、tor*() const return current-data;T& operator-() const return ¤t-data;26學(xué)習(xí)交流PPT第26頁，共86頁。IncrementChainIterator& operator+() / preincrement current = current-link; return *this;ChainIterator& operator+(int) / postincrement ChainIterator old = *this; current = current-link; return old;27學(xué)習(xí)交流PPT第

15、27頁，共86頁。Equality Testingbool operator!=(const ChainIterator right) const return current != right.current;bool operator=(const ChainIterator right) const return current = right.current;28學(xué)習(xí)交流PPT第28頁，共86頁。Using An IteratorChain:iterator xHere = x.Begin();Chain:iterator xEnd = x.End();for (; xHere !=

16、xEnd; xHere+) examine( *xHere); vsfor (int i = 0; i x.Size(); i+) examine(x.Get(i);29學(xué)習(xí)交流PPT第29頁，共86頁。迭代器用于指向第一類容器中的元素。有const 和非 const兩種。通過迭代器可以讀取它指向的元素，通過非const迭代器還能修改其指向的元素。迭代器用法和指針類似。定義一個(gè)容器類的迭代器的方法可以是：容器類名:iterator 變量名;或：容器類名:const_iterator 變量名;訪問一個(gè)迭代器指向的元素：* 迭代器變量名30學(xué)習(xí)交流PPT第30頁，共86頁。迭代器迭代器上可以執(zhí)行

17、+ 操作, 以指向容器中的下一個(gè)元素。如果迭代器到達(dá)了容器中的最后一個(gè)元素的后面，則迭代器變成past-the-end值。使用一個(gè)past-the-end值的迭代器來訪問對(duì)象是非法的，就好像使用NULL或未初始化的指針一樣。31學(xué)習(xí)交流PPT第31頁，共86頁。例如：#include #include using namespace std;int main() vector v; /一個(gè)存放int元素的向量，一開始里面沒有元素v.push_back(1);v.push_back(2); v.push_back(3); v.push_back(4);vector:const_iterator

18、i; /常量迭代器for( i = v.begin();i != v.end();i + ) cout * i ,;cout endl;32學(xué)習(xí)交流PPT第32頁，共86頁。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+ ) cout * i

19、,;輸出結(jié)果：1,2,3,4,4,3,2,1,100,100,100,100,33學(xué)習(xí)交流PPT第33頁，共86頁。迭代器不同容器上支持的迭代器功能強(qiáng)弱有所不同。 容器的迭代器的功能強(qiáng)弱，決定了該容器是否支持STL中的某種算法。例1：只有第一類容器能用迭代器遍歷。例2：排序算法需要通過隨機(jī)迭代器來訪問容器中的元素，那么有的容器就不支持排序算法。34學(xué)習(xí)交流PPT第34頁，共86頁。STL 中的迭代器STL 中的迭代器按功能由弱到強(qiáng)分為5種： 1. 輸入：Input iterators 提供對(duì)數(shù)據(jù)的只讀訪問。 1. 輸出：Output iterators 提供對(duì)數(shù)據(jù)的只寫訪問 2. 正向：For

20、ward iterators 提供讀寫操作，并能一次一個(gè)地向前推進(jìn)迭代器。 3. 雙向：Bidirectional iterators提供讀寫操作，并能一次一個(gè)地向前和向后移動(dòng)。 4. 隨機(jī)訪問：Random access iterators提供讀寫操作，并能在數(shù)據(jù)中隨機(jī)移動(dòng)。編號(hào)大的迭代器擁有編號(hào)小的迭代器的所有功能，能當(dāng)作編號(hào)小的迭代器使用。35學(xué)習(xí)交流PPT第35頁，共86頁。不同迭代器所能進(jìn)行的操作(功能）所有迭代器： +p, p +輸入迭代器： * p, p 1= p, p = p1 , p!= p1輸出迭代器： * p, p = p1正向迭代器： 上面全部雙向迭代器： 上面全部，-

21、p, p -,隨機(jī)訪問迭代器： 上面全部，以及：p+= i, p -= i, p + i： 返回指向 p 后面的第i個(gè)元素的迭代器p - i： 返回指向 p 前面的第i個(gè)元素的迭代器p p1, p p1, p= p136學(xué)習(xí)交流PPT第36頁，共86頁。容器所支持的迭代器類別容器迭代器類別vector隨機(jī)deque隨機(jī)list 雙向set/multiset雙向map/multimap雙向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器37學(xué)習(xí)交流PPT第37頁，共86頁。例如，vector的迭代器是隨機(jī)迭代器，所以遍歷 vector 可以有以下幾種做法：ve

22、ctor v(100);vector:value_type i; /等效于寫 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;/間隔一個(gè)輸出：ii = v.begin();while( ii v.end() cout * ii; ii = ii + 2; 38學(xué)習(xí)交流PPT第38頁，共86頁。而 list 的迭代器是雙向迭代器，所以以下代碼可以：list v;list:const_iterator ii;fo

23、r( ii = v.begin(); ii ！ v.end ();ii + )cout * ii;以下代碼則不行：for( ii = v.begin(); ii v.end ();ii + )cout * ii;/雙向迭代器不支持 for(int i = 0;i v.size() ; i +)cout vi; /雙向迭代器不支持 39學(xué)習(xí)交流PPT第39頁，共86頁。算法簡(jiǎn)介STL中提供能在各種容器中通用的算法，比如插入，刪除，查找，排序等。大約有70種標(biāo)準(zhǔn)算法。算法就是一個(gè)個(gè)函數(shù)模板。算法通過迭代器來操縱容器中的元素。許多算法需要兩個(gè)參數(shù)，一個(gè)是起始元素的迭代器，一個(gè)是終止元素的后面一個(gè)元素

24、的迭代器。比如，排序和查找有的算法返回一個(gè)迭代器。比如 find() 算法，在容器中查找一個(gè)元素，并返回一個(gè)指向該元素的迭代器。算法可以處理容器，也可以處理C語言的數(shù)組40學(xué)習(xí)交流PPT第40頁，共86頁。算法分類變化序列算法copy ,remove,fill,replace,random_shuffle,swap, .會(huì)改變?nèi)萜鞣亲兓蛄兴惴ǎ篴djacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_n以上函數(shù)模板都在 中定義此外還有其他算法，比如中的算法41學(xué)習(xí)交流PPT第41頁，共86頁。

25、算法示例：find()templateInIt find(InIt first, InIt last, const T& val); first 和 last 這兩個(gè)參數(shù)都是容器的迭代器，它們給出了容器中的查找區(qū)間起點(diǎn)和終點(diǎn)。這個(gè)區(qū)間是個(gè)左閉右開的區(qū)間，即區(qū)間的起點(diǎn)是位于查找范圍之中的，而終點(diǎn)不是val參數(shù)是要查找的元素的值函數(shù)返回值是一個(gè)迭代器。如果找到，則該迭代器指向被找到的元素。如果找不到，則該迭代器指向查找區(qū)間終點(diǎn)。42學(xué)習(xí)交流PPT第42頁，共86頁。#include #include #include using namespace std;main() int array10 =

26、 10,20,30,40;vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:iterator p;p = find(v.begin(),v.end(),3);if( p != v.end()cout * p endl;43學(xué)習(xí)交流PPT第43頁，共86頁。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 *

27、 p endl;int * pp = find( array,array+4,20);cout * pp endl;輸出：3not found32044學(xué)習(xí)交流PPT第44頁，共86頁。各種容器介紹45學(xué)習(xí)交流PPT第45頁，共86頁。順序容器除前述共同操作外，順序容器還有以下共同操作：front() :返回容器中第一個(gè)元素的引用back() : 返回容器中最后一個(gè)元素的引用push_back(): 在容器末尾增加新元素pop_back(): 刪除容器末尾的元素比如，查 list:front 的help,得到的定義是：reference front(); const_reference fro

28、nt() const;list有兩個(gè)front函數(shù)46學(xué)習(xí)交流PPT第46頁，共86頁。順序容器reference和 const_reference 是typedef的類型對(duì)于 list , list:reference 實(shí)際上就是 double &list:const_reference 實(shí)際上就是 const double &對(duì)于 list , list:refrence 實(shí)際上就是 int &list:const_refreence 實(shí)際上就是 const int &47學(xué)習(xí)交流PPT第47頁，共86頁。vector支持隨機(jī)訪問迭代器，所有STL算法都能對(duì)vector操作。隨機(jī)訪問時(shí)間為

29、常數(shù)。在尾部添加速度很快，在中間插入慢。實(shí)際上就是動(dòng)態(tài)數(shù)組。48學(xué)習(xí)交流PPT第48頁，共86頁。例1：int main() int i;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位置插入

30、 13for( i = 0;i v2.size();i + )cout v2i , ; return 0;49學(xué)習(xí)交流PPT第49頁，共86頁。輸出：50,1,2,3,100,1,2,13,3,4,5,50學(xué)習(xí)交流PPT第50頁，共86頁。例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

31、(v.begin();ostream_iterator output(cout ,“*);copy (v.begin(),v.end(),output);v.erase( v.begin(),v.end(); /等效于 v.clear();51學(xué)習(xí)交流PPT第51頁，共86頁。if( v.empty ()cout empty endl;v.insert (v.begin(),a,a+SIZE);copy (v.begin(),v.end(),output); / 輸出：invalid vector subscript1,52*3*4*5*empty1*2*3*4*5*52學(xué)習(xí)交流PPT第52頁

32、，共86頁。算法解釋ostream_iterator output(cout ,“*);定義了一個(gè) ostream_iterator 對(duì)象，可以通過cout輸出以 * 分隔的一個(gè)個(gè)整數(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ù)對(duì)每個(gè)在區(qū)間0, last - first)中的N執(zhí)行一次 *(x+N) = * ( first + N) ，返回 x + N對(duì)于copy (v.begin(),v.end(),ou

33、tput);first 和 last 的類型是 vector:const_iteratoroutput 的類型是 ostream_iterator 53學(xué)習(xí)交流PPT第53頁，共86頁。關(guān)于 ostream_iterator, istream_iterator的例子int main() istream_iterator inputInt(cin);int n1,n2;n1 = * inputInt; /讀入 n1inputInt +; n2 = * inputInt; /讀入 n2cout n1 , n2 endl;ostream_iterator outputInt(cout);* outp

34、utInt = n1 + n2; cout endl;int a5 = 1,2,3,4,5;copy(a,a+5,outputInt); /輸出整個(gè)數(shù)組 return 0;54學(xué)習(xí)交流PPT第54頁，共86頁。程序運(yùn)行后輸入 78 90敲回車，則輸出結(jié)果為：78,901681234555學(xué)習(xí)交流PPT第55頁，共86頁。list 容器在任何位置插入刪除都是常數(shù)時(shí)間，不支持隨機(jī)存取。除了具有所有順序容器都有的成員函數(shù)以外，還支持8個(gè)成員函數(shù)：push_front: 在前面插入pop_front: 刪除前面的元素sort: 排序( list 不支持STL 的算法sort)remove: 刪除和指定

35、值相等的所有元素unique: 刪除所有和前一個(gè)元素相同的元素merge: 合并兩個(gè)鏈表，并清空被合并的那個(gè)reverse: 顛倒鏈表splice: 在指定位置前面插入另一鏈表中的一個(gè)或多個(gè)元素,并在另一鏈表中刪除被插入的元素56學(xué)習(xí)交流PPT第56頁，共86頁。deque 容器所有適用于vector的操作都適用于dequedeque還有push_front（將元素插入到前面）和pop_front(刪除最前面的元素）操作57學(xué)習(xí)交流PPT第57頁，共86頁。關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部元素有序排列，新元素插入的位置取決于它的值，查找速度快map關(guān)聯(lián)數(shù)組：

36、元素通過鍵來存儲(chǔ)和讀取set大小可變的集合，支持通過鍵實(shí)現(xiàn)的快速讀取multimap支持同一個(gè)鍵多次出現(xiàn)的map類型multiset支持同一個(gè)鍵多次出現(xiàn)的set類型與順序容器的本質(zhì)區(qū)別關(guān)聯(lián)容器是通過鍵(key)存儲(chǔ)和讀取元素的而順序容器則通過元素在容器中的位置順序存儲(chǔ)和訪問元素。 58學(xué)習(xí)交流PPT第58頁，共86頁。關(guān)聯(lián)容器除了各容器都有的函數(shù)外，還支持以下成員函數(shù)：設(shè)m表容器，k表鍵值m.find(k) ：如果容器中存在鍵為k的元素，則返回指向該元素的迭代器。如果不存在，則返回end()值。 m.lower_bound(k)：返回一個(gè)迭代器，指向鍵不小于k的第一個(gè)元素 m.upper_bo

37、und(k)：返回一個(gè)迭代器，指向鍵大于k的第一個(gè)元素 m.count(k) ：返回m中k的出現(xiàn)次數(shù) 插入元素用 insert 59學(xué)習(xí)交流PPT第59頁，共86頁。settemplateclass Key, class Pred = less, class A = allocator class set 插入set中已有的元素時(shí)，插入不成功。60學(xué)習(xí)交流PPT第60頁，共86頁。multiset定義：templateclass Key, class Pred = less, class A = allocator class multiset ;第二個(gè)參數(shù) Pred 是個(gè)函數(shù)對(duì)象Pred決定

38、了multiset 中的元素，“一個(gè)比另一個(gè)小”是怎么定義的，即 Pred(x,y) 如果返回值為true,則 x比y小Pred的缺省值是 lessless 模板的定義：template struct less : public binary_function bool operator()(const T& x, const T& y) return x y ; const; ; /less模板是靠 來比較大小的61學(xué)習(xí)交流PPT第61頁，共86頁。函數(shù)對(duì)象是個(gè)對(duì)象，但是用起來看上去象函數(shù)調(diào)用，實(shí)際上也執(zhí)行了函數(shù)調(diào)用 class CMyAverage public:double operat

39、or()( int a1, int a2, int a3 ) /重載 () 運(yùn)算符return (double)(a1 + a2+a3) / 3; / 重載 () 運(yùn)算符時(shí)，參數(shù)可以是任意多個(gè) CMyAverage Average; /函數(shù)對(duì)象 cout Average(3,2,3); / Average.operator(3,2,3) 用起來看上去象函數(shù)調(diào)用輸出 2.6666762學(xué)習(xí)交流PPT第62頁，共86頁。multiset的用法class A.;multiset a; 就等效于multisetA, less a;由于less模板是用 進(jìn)行比較的，所以這都要求 A 的對(duì)象能用 比較，即

40、適當(dāng)重載了 63學(xué)習(xí)交流PPT第63頁，共86頁。/出錯(cuò)的例子：#include using namespace std;class A ;int main() multiset a;a.insert( A(); /error return/編譯出錯(cuò)是因?yàn)?，插入元素時(shí)，multiset會(huì)將被插入元素和已有元素進(jìn)行比較，以決定新元素的存放位置。本例中缺省地就是用less函數(shù)對(duì)象進(jìn)行比較，然而less函數(shù)對(duì)象進(jìn)行比較時(shí)，前提是A對(duì)象能用 進(jìn)行比較。但本例中沒有適當(dāng)重載 64學(xué)習(xí)交流PPT第64頁，共86頁。pair模板pair模板類用來綁定兩個(gè)對(duì)象為一個(gè)新的對(duì)象，該類型在頭文件中定義。pair模板

41、類支持如下操作：pair p1：創(chuàng)建一個(gè)空的pair對(duì)象，它的兩個(gè)元素分別是T1和T2類型，采用值初始化pair p1(v1, v2)：創(chuàng)建一個(gè)pair對(duì)象，它的兩個(gè)元素分別是T1和T2類型，其中first成員初始化為v1，second成員初始化為v2make_pair(v1, v2)：以v1和v2值創(chuàng)建一個(gè)新的pair對(duì)象，其元素類型分別是v1和v2的類型p1 p2字典次序：如果p1.firstp2.first或者!(p2.first p1.first)& p1.secondp2.second，則返回truep1 = p2：如果兩個(gè)pair對(duì)象的first和second成員依次相等，則這兩個(gè)

42、對(duì)象相等。p.first：返回p中名為first的（公有）數(shù)據(jù)成員p.second：返回p中名為second的（公有）數(shù)據(jù)成員65學(xué)習(xí)交流PPT第65頁，共86頁。#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(dou

43、bleSet.begin(),doubleSet.end(),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ù)返回值是一個(gè)pair對(duì)象, 其first是被插入元素的迭代器，second代表是否成功插入了66學(xué)習(xí)交流PPT第66頁，共86頁。輸出：1) 2.1 3.7 4.2 9.52) 9.5 not insert

44、ed67學(xué)習(xí)交流PPT第67頁，共86頁。multimaptemplateclass Key, class T, class Pred = less, class A = allocator class multimap .typedef pair value_type; . ; /Key 代表關(guān)鍵字multimap中的元素由 組成，每個(gè)元素是一個(gè)pair對(duì)象。multimap 中允許多個(gè)元素的關(guān)鍵字相同。元素按照關(guān)鍵字升序排列，缺省情況下用 less 定義關(guān)鍵字的“小于”關(guān)系68學(xué)習(xí)交流PPT第68頁，共86頁。maptemplateclass Key, class T, class Pre

45、d = less, class A = allocator class map .typedef pair value_type; . ;map 中的元素關(guān)鍵字各不相同。元素按照關(guān)鍵字升序排列，缺省情況下用 less 定義“小于”69學(xué)習(xí)交流PPT第69頁，共86頁。map可以用pairskey 訪形式問map中的元素。pairs 為map容器名，key為關(guān)鍵字的值。該表達(dá)式返回的是對(duì)關(guān)鍵值為key的元素的值的引用。如果沒有關(guān)鍵字為key的元素，則會(huì)往pairs里插入一個(gè)關(guān)鍵字為key的元素，并返回其值的引用如：map pairs;則 pairs50 = 5; 會(huì)修改pairs中關(guān)鍵字為50的

46、元素，使其值變成570學(xué)習(xí)交流PPT第70頁，共86頁。#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.insert(make_pair(15,99.3);

47、/make_pair生成pair對(duì)象cout 2) pairs.count(15) endl;pairs.insert(mmid:value_type(20,9.3);71學(xué)習(xí)交流PPT第71頁，共86頁。 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的元素，則插入一個(gè)for( i = pairs.begin(); i != pairs.end();i + )cout * i ,

48、;cout endl;cout 5) ;pairs15 = 6.28; /把關(guān)鍵字為15的元素值改成6.28for( i = pairs.begin(); i != pairs.end();i + )cout * i ,; return 0;72學(xué)習(xí)交流PPT第72頁，共86頁。輸出：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),73學(xué)習(xí)交流PPT第73頁，共86頁。思考題如何用程序用來統(tǒng)計(jì)一篇英文文章中單詞出現(xiàn)的頻率（為簡(jiǎn)單起見，假定依次從鍵盤輸入該文章） #incl

49、ude #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;74學(xué)習(xí)交流PPT第74頁，共86頁。容器適配器:stack可用 vector, list, deque來實(shí)現(xiàn)缺省情況下，用deque實(shí)現(xiàn)用 vec

50、tor和deque實(shí)現(xiàn)，比用list實(shí)現(xiàn)性能好templateclass T, class Cont = deque class stack .;stack 是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，只能插入、刪除、訪問棧頂?shù)脑?5學(xué)習(xí)交流PPT第75頁，共86頁。容器適配器:stackstack 上可以進(jìn)行以下操作：push: 插入元素pop:彈出元素top:返回棧頂元素的引用76學(xué)習(xí)交流PPT第76頁，共86頁。容器適配器: queue和stack 基本類似，可以用 list和deque實(shí)現(xiàn)，缺省情況下用deque實(shí)現(xiàn)templateclass T, class Cont = deque class queue ;同樣也有push,pop,top函數(shù)但是push發(fā)生在隊(duì)尾，pop,top發(fā)生在隊(duì)頭，先進(jìn)