STL入門基礎(chǔ)(全)-課件

C++模板與STL庫(kù)介紹(參考北京大學(xué)單棟棟課件)1ppt課件C++模板與STL庫(kù)介紹(參考北京大學(xué)單棟棟課件)1ppt課提綱1.概論2.模板機(jī)制的介紹3.STL中的基本概念4.容器概述5.迭代器6.算法簡(jiǎn)介ppt課件提綱1.概論ppt課件概論C++語(yǔ)言的核心優(yōu)勢(shì)之一就是便于軟件的重用C++中有兩個(gè)方面體現(xiàn)重用：1.面向?qū)ο蟮乃枷耄豪^承和多態(tài)，標(biāo)準(zhǔn)類庫(kù)

2.泛型程序設(shè)計(jì)(genericprogramming)的思想：模板機(jī)制，以及標(biāo)準(zhǔn)模板庫(kù)STL這次課的重點(diǎn)ppt課件概論C++語(yǔ)言的核心優(yōu)勢(shì)之一就是便于軟件的重用這次課的重點(diǎn)泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)，簡(jiǎn)單地說(shuō)就是使用模板的程序設(shè)計(jì)法。將一些常用的數(shù)據(jù)結(jié)構(gòu)（比如鏈表，數(shù)組，二叉樹(shù)）和算法（比如排序，查找）寫(xiě)成模板，以后則不論數(shù)據(jù)結(jié)構(gòu)里放的是什么對(duì)象，算法針對(duì)什么樣的對(duì)象，則都不必重新實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，重新編寫(xiě)算法。標(biāo)準(zhǔn)模板庫(kù)(StandardTemplateLibrary)就是一些常用數(shù)據(jù)結(jié)構(gòu)和算法的模板的集合。主要由AlexStepanov開(kāi)發(fā)，于1998年被添加進(jìn)C++標(biāo)準(zhǔn)有了STL，不必再?gòu)念^寫(xiě)大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。ppt課件泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)，簡(jiǎn)單地說(shuō)就是使用模板的程序設(shè)計(jì)法。模板引子1.假如設(shè)計(jì)一個(gè)求兩參數(shù)最大值的函數(shù)，在實(shí)踐中我們可能需要定義四個(gè)函數(shù)：

intmax

(

inta

,

intb

)

{

return

(

a

>

b

)

?

a

,

b

;}

longmax(longa,longb){return(a>b)?a,b;}

doublemax(doublea,doubleb){return(a>b)?a,b;}

charmax(chara,charb){return(a>b)?a,b;}2.這些函數(shù)幾乎相同，唯一的區(qū)別就是形參類型不同3.需要事先知道有哪些類型會(huì)使用這些函數(shù)，對(duì)于未知類型這些函數(shù)不起作用

ppt課件模板引子1.假如設(shè)計(jì)一個(gè)求兩參數(shù)最大值的函數(shù)，在實(shí)踐中我們可模板的概念所謂模板是一種使用無(wú)類型參數(shù)來(lái)產(chǎn)生一系列函數(shù)或類的機(jī)制。若一個(gè)程序的功能是對(duì)某種特定的數(shù)據(jù)類型進(jìn)行處理，則可以將所處理的數(shù)據(jù)類型說(shuō)明為參數(shù)，以便在其他數(shù)據(jù)類型的情況下使用，這就是模板的由來(lái)。模板是以一種完全通用的方法來(lái)設(shè)計(jì)函數(shù)或類而不必預(yù)先說(shuō)明將被使用的每個(gè)對(duì)象的類型。通過(guò)模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個(gè)單獨(dú)的類或函數(shù)。ppt課件模板的概念所謂模板是一種使用無(wú)類型參數(shù)來(lái)產(chǎn)生一系列函數(shù)或類的模板分類函數(shù)模板(functiontemplate)是獨(dú)立于類型的函數(shù)可產(chǎn)生函數(shù)的特定版本類模板(classtemplate)跟類相關(guān)的模板，如vector可產(chǎn)生類對(duì)特定類型的版本，如vector<int>7ppt課件模板分類函數(shù)模板(functiontemplate)7pp求最大值模板函數(shù)實(shí)現(xiàn)1.求兩個(gè)數(shù)最大值，使用模板

template<classT> Tmax(Ta,Tb){ return(a>b)?a,b; }2.template<模板形參表><返回值類型><函數(shù)名>（模板函數(shù)形參表）{//函數(shù)定義體}8ppt課件求最大值模板函數(shù)實(shí)現(xiàn)1.求兩個(gè)數(shù)最大值，使用模板8ppt課件模板工作方式函數(shù)模板只是說(shuō)明，不能直接執(zhí)行，需要實(shí)例化為模板函數(shù)后才能執(zhí)行在說(shuō)明了一個(gè)函數(shù)模板后，當(dāng)編譯系統(tǒng)發(fā)現(xiàn)有一個(gè)對(duì)應(yīng)的函數(shù)調(diào)用時(shí)，將根據(jù)實(shí)參中的類型來(lái)確認(rèn)是否匹配函數(shù)模板中對(duì)應(yīng)的形參，然后生成一個(gè)重載函數(shù)。該重載函數(shù)的定義體與函數(shù)模板的函數(shù)定義體相同，它稱之為模板函數(shù)9ppt課件模板工作方式函數(shù)模板只是說(shuō)明，不能直接執(zhí)行，需要實(shí)例化為模板#include<iostream>template<classT>Tmin(Ta[],intn){ inti; Tminv=a[0]; for(i=1;i<n;i++){ if(minv>a[i]) minv=a[i]; } returnminv;}編寫(xiě)一個(gè)對(duì)具有n個(gè)元素的數(shù)組a[]求最小值的程序，要求將求最小值的函數(shù)設(shè)計(jì)成函數(shù)模板。voidmain(){inaa[]={1,3,0,2,7,6,4,5,2};doubleb[]={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.4ppt課件#include<iostream>編寫(xiě)一個(gè)對(duì)具有n個(gè)元素模板優(yōu)缺點(diǎn)函數(shù)模板方法克服了C語(yǔ)言解決上述問(wèn)題時(shí)用大量不同函數(shù)名表示相似功能的壞習(xí)慣克服了宏定義不能進(jìn)行參數(shù)類型檢查的弊端克服了C++函數(shù)重載用相同函數(shù)名字重寫(xiě)幾個(gè)函數(shù)的繁瑣缺點(diǎn)，調(diào)試比較困難一般先寫(xiě)一個(gè)特殊版本的函數(shù)運(yùn)行正確后，改成模板函數(shù)11ppt課件模板優(yōu)缺點(diǎn)函數(shù)模板方法克服了C語(yǔ)言解決上述問(wèn)題時(shí)用大量不同函STL中的幾個(gè)基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。迭代器：可依次存取容器中元素的東西算法：用來(lái)操作容器中的元素的函數(shù)模板。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象。函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用。比如，數(shù)組intarray[100]就是個(gè)容器，而int*類型的指針變量就可以作為迭代器，可以為這個(gè)容器編寫(xiě)一個(gè)排序的算法ppt課件STL中的幾個(gè)基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。p容器概述可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對(duì)象等）的數(shù)據(jù)結(jié)構(gòu)。容器分為三大類：1)順序容器

vector：后部插入/刪除，直接訪問(wèn)

deque：前/后部插入/刪除，直接訪問(wèn)

list：雙向鏈表，任意位置插入/刪除

2)關(guān)聯(lián)容器

set：快速查找，無(wú)重復(fù)元素

multiset：快速查找，可有重復(fù)元素

map：一對(duì)一映射，無(wú)重復(fù)元素，基于關(guān)鍵字查找

multimap：一對(duì)一映射，可有重復(fù)元素，基于關(guān)鍵字查找前2者合稱為第一類容器3)容器適配器

stack：LIFO

queue：FIFO

priority_queue：優(yōu)先級(jí)高的元素先出ppt課件容器概述可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對(duì)象等）容器概述對(duì)象被插入容器中時(shí)，被插入的是對(duì)象的一個(gè)復(fù)制品。許多算法，比如排序，查找，要求對(duì)容器中的元素進(jìn)行比較，所以，放入容器的對(duì)象所屬的類，還應(yīng)該實(shí)現(xiàn)==和<

運(yùn)算符。ppt課件容器概述對(duì)象被插入容器中時(shí)，被插入的是對(duì)象的一個(gè)復(fù)制品。pp順序容器簡(jiǎn)介1)vector頭文件<vector>

實(shí)際上就是個(gè)動(dòng)態(tài)數(shù)組。隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成。在尾端增刪元素具有較佳的性能。

2)deque頭文件<deque>

也是個(gè)動(dòng)態(tài)數(shù)組，隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。

3)list頭文件<list>

雙向鏈表，在任何位置增刪元素都能在常數(shù)時(shí)間完成。不支持隨機(jī)存取。上述三種容器稱為順序容器，是因?yàn)樵氐牟迦胛恢猛氐闹禑o(wú)關(guān)，只跟插入的時(shí)機(jī)有關(guān)。ppt課件順序容器簡(jiǎn)介1)vector頭文件<vector>p關(guān)聯(lián)容器簡(jiǎn)介關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來(lái)確定其位置。關(guān)聯(lián)式容器的特點(diǎn)是在查找時(shí)具有非常好的性能。1)set/multiset:頭文件<set>set即集合。set中不允許相同元素，multiset中允許存在相同的元素。2)map/multimap:頭文件<map>map與set的不同在于map中存放的是成對(duì)的key/value。并根據(jù)key對(duì)元素進(jìn)行排序，可快速地根據(jù)key來(lái)檢索元素

map同multimap的不同在于是否允許多個(gè)元素有相同的key值。上述4種容器通常以平衡二叉樹(shù)方式實(shí)現(xiàn)，插入、查找和刪除的時(shí)間都是O(logN)

ppt課件關(guān)聯(lián)容器簡(jiǎn)介關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相容器適配器簡(jiǎn)介1)stack:頭文件<stack>

棧。是項(xiàng)的有限序列，并滿足序列中被刪除、檢索和修改的項(xiàng)只能是最近插入序列的項(xiàng)。即按照后進(jìn)先出的原則2)queue:頭文件<queue>

隊(duì)列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照先進(jìn)先出的原則。3）priority_queue:頭文件<queue>

優(yōu)先級(jí)隊(duì)列。最高優(yōu)先級(jí)元素總是第一個(gè)出列ppt課件容器適配器簡(jiǎn)介1)stack:頭文件<stack>p容器的共有成員函數(shù)1)所有標(biāo)準(zhǔn)庫(kù)容器共有的成員函數(shù)： 相當(dāng)于按詞典順序比較兩個(gè)容器大小的運(yùn)算符：

=,<,<=,>,>=,==,!= empty:判斷容器中是否有元素

max_size:容器中最多能裝多少元素

size:容器中元素個(gè)數(shù)

swap:交換兩個(gè)容器的內(nèi)容ppt課件容器的共有成員函數(shù)1)所有標(biāo)準(zhǔn)庫(kù)容器共有的成員函數(shù)：ppt比較兩個(gè)容器的例子19比較兩個(gè)容器的例子：#include<vector>#include<iostream>intmain(){ std::vector<int>v1; std::vector<int>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);return0;}若兩容器長(zhǎng)度相同、所有元素相等，則兩個(gè)容器就相等，否則為不等。若兩容器長(zhǎng)度不同，但較短容器中所有元素都等于較長(zhǎng)容器中對(duì)應(yīng)的元素，則較短容器小于另一個(gè)容器若兩個(gè)容器均不是對(duì)方的子序列，則取決于所比較的第一個(gè)不等的元素輸出：0ppt課件比較兩個(gè)容器的例子19比較兩個(gè)容器的例子：若兩容器長(zhǎng)度相同、容器的成員函數(shù)2)只在第一類容器中的函數(shù)：

begin返回指向容器中第一個(gè)元素的迭代器

end返回指向容器中最后一個(gè)元素后面的位置的迭代器

rbegin返回指向容器中最后一個(gè)元素的迭代器

rend返回指向容器中第一個(gè)元素前面的位置的迭代器

erase從容器中刪除一個(gè)或幾個(gè)元素

clear從容器中刪除所有元素HeadTailbeginrbeginrendendppt課件容器的成員函數(shù)2)只在第一類容器中的函數(shù)：HeadTai迭代器用于指向第一類容器中的元素。有const和非const兩種。通過(guò)迭代器可以讀取它指向的元素，通過(guò)非const迭代器還能修改其指向的元素。迭代器用法和指針類似。定義一個(gè)容器類的迭代器的方法可以是：

容器類名::iterator變量名;或：

容器類名::const_iterator變量名;訪問(wèn)一個(gè)迭代器指向的元素：

*迭代器變量名ppt課件迭代器用于指向第一類容器中的元素。有const和非con迭代器迭代器上可以執(zhí)行++

操作,以指向容器中的下一個(gè)元素。如果迭代器到達(dá)了容器中的最后一個(gè)元素的后面，則迭代器變成past-the-end值。使用一個(gè)past-the-end值的迭代器來(lái)訪問(wèn)對(duì)象是非法的，就好像使用NULL或未初始化的指針一樣。ppt課件迭代器迭代器上可以執(zhí)行++操作,以指向容器中的下一個(gè)元例如：#include<vector>#include<iostream>usingnamespacestd;intmain(){ vector<int>v;//一個(gè)存放int元素的向量，一開(kāi)始里面沒(méi)有元素

v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::const_iteratori;//常量迭代器

for(i=v.begin();i!=v.end();i++) cout<<*i<<","; cout<<endl;ppt課件例如：ppt課件 vector<int>::reverse_iteratorr;//反向迭代器

for(r=v.rbegin();r!=v.rend();r++) cout<<*r<<","; cout<<endl; vector<int>::iteratorj;//非常量迭代器

for(j=v.begin();j!=v.end();j++) *j=100; for(i=v.begin();i!=v.end();i++) cout<<*i<<",";}輸出結(jié)果：1,2,3,4,4,3,2,1,100,100,100,100,ppt課件 vector<int>::reverse_iterator迭代器不同容器上支持的迭代器功能強(qiáng)弱有所不同。容器的迭代器的功能強(qiáng)弱，決定了該容器是否支持STL中的某種算法。例1：只有第一類容器能用迭代器遍歷。例2：排序算法需要通過(guò)隨機(jī)迭代器來(lái)訪問(wèn)容器中的元素，那么有的容器就不支持排序算法。ppt課件迭代器不同容器上支持的迭代器功能強(qiáng)弱有所不同。ppt課件STL中的迭代器STL中的迭代器按功能由弱到強(qiáng)分為5種：

1.輸入：Inputiterators提供對(duì)數(shù)據(jù)的只讀訪問(wèn)。

1.輸出：Outputiterators提供對(duì)數(shù)據(jù)的只寫(xiě)訪問(wèn)

2.正向：Forwarditerators提供讀寫(xiě)操作，并能一次一個(gè)地向前推進(jìn)迭代器。

3.雙向：Bidirectionaliterators提供讀寫(xiě)操作，并能一次一個(gè)地向前和向后移動(dòng)。

4.隨機(jī)訪問(wèn)：Randomaccessiterators提供讀寫(xiě)操作，并能在數(shù)據(jù)中隨機(jī)移動(dòng)。編號(hào)大的迭代器擁有編號(hào)小的迭代器的所有功能，能當(dāng)作編號(hào)小的迭代器使用。ppt課件STL中的迭代器STL中的迭代器按功能由弱到強(qiáng)分為5種：不同迭代器所能進(jìn)行的操作(功能）所有迭代器：++p,p++輸入迭代器：*p,p=p1,p==p1,p!=p1輸出迭代器：*p,p=p1正向迭代器：上面全部雙向迭代器：上面全部，--p,p--,隨機(jī)訪問(wèn)迭代器：上面全部，以及：

p+=i,p-=i, p+i：返回指向p后面的第i個(gè)元素的迭代器

p-i：返回指向p前面的第i個(gè)元素的迭代器p[i]: p后面的第i個(gè)元素的引用

p<p1,p<=p1,p>p1,p>=p1ppt課件不同迭代器所能進(jìn)行的操作(功能）所有迭代器：++p,p容器所支持的迭代器類別

容器 迭代器類別

vector 隨機(jī)

deque 隨機(jī)

list 雙向

set/multiset 雙向

map/multimap 雙向

stack 不支持迭代器

queue 不支持迭代器

priority_queue 不支持迭代器ppt課件容器所支持的迭代器類別 容器 迭代器類別ppt課件例如，vector的迭代器是隨機(jī)迭代器，所以遍歷vector可以有以下幾種做法：vector<int>v(100);inti;for(i=0;i<v.size();i++) cout<<v[i];vector<int>::const_iteratorii;for(ii=v.begin();ii!=v.end();ii++) cout<<*ii;//間隔一個(gè)輸出：ii=v.begin();while(ii<v.end()){ cout<<*ii; ii=ii+2;}ppt課件例如，vector的迭代器是隨機(jī)迭代器，所以遍歷vecto而list的迭代器是雙向迭代器，所以以下代碼可以：

list<int>v;

list<int>::const_iteratorii; for(ii=v.begin();ii?。絭.end();ii++) cout<<*ii; 以下代碼則不行：

for(ii=v.begin();ii<v.end();ii++) cout<<*ii; //雙向迭代器不支持< for(inti=0;i<v.size();i++) cout<<v[i];//雙向迭代器不支持[]ppt課件而list的迭代器是雙向迭代器，所以以下代碼可以：ppt算法簡(jiǎn)介STL中提供能在各種容器中通用的算法，比如插入，刪除，查找，排序等。大約有70種標(biāo)準(zhǔn)算法。 算法就是一個(gè)個(gè)函數(shù)模板。 算法通過(guò)迭代器來(lái)操縱容器中的元素。許多算法需要兩個(gè)參數(shù)，一個(gè)是起始元素的迭代器，一個(gè)是終止元素的后面一個(gè)元素的迭代器。比如，排序和查找 有的算法返回一個(gè)迭代器。比如find()算法，在容器中查找一個(gè)元素，并返回一個(gè)指向該元素的迭代器。 算法可以處理容器，也可以處理C語(yǔ)言的數(shù)組ppt課件算法簡(jiǎn)介STL中提供能在各種容器中通用的算法，比如插入，刪除

算法分類變化序列算法copy,remove,fill,replace,random_shuffle,swap,…..會(huì)改變?nèi)萜鞣亲兓蛄兴惴ǎ篴djacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n以上函數(shù)模板都在<algorithm>中定義此外還有其他算法，比如<numeric>中的算法ppt課件 算法分類變化序列算法ppt課件算法示例：find()template<classInIt,classT>InItfind(InItfirst,InItlast,constT&val);

first和last這兩個(gè)參數(shù)都是容器的迭代器，它們給出了容器中的查找區(qū)間起點(diǎn)和終點(diǎn)。這個(gè)區(qū)間是個(gè)左閉右開(kāi)的區(qū)間，即區(qū)間的起點(diǎn)是位于查找范圍之中的，而終點(diǎn)不是val參數(shù)是要查找的元素的值函數(shù)返回值是一個(gè)迭代器。如果找到，則該迭代器指向被找到的元素。如果找不到，則該迭代器指向查找區(qū)間終點(diǎn)。ppt課件算法示例：find()template<classInIt#include<vector>#include<algorithm>#include<iostream>usingnamespacestd;intmain(){ intarray[10]={10,20,30,40}; vector<int>v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iteratorp; p=find(v.begin(),v.end(),3); if(p!=v.end()) cout<<*p<<endl;ppt課件#include<vector>ppt課件 p=find(v.begin(),v.end(),9); if(p==v.end()) cout<<"notfound"<<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;}輸出：3notfound320ppt課件 p=find(v.begin(),v.end(),9)順序容器除前述共同操作外，順序容器還有以下共同操作：

front():返回容器中第一個(gè)元素的引用

back():返回容器中最后一個(gè)元素的引用

push_back():在容器末尾增加新元素

pop_back():刪除容器末尾的元素

ppt課件順序容器除前述共同操作外，順序容器還有以下共同操作：ppt課vector支持隨機(jī)訪問(wèn)迭代器，所有STL算法都能對(duì)vector操作。隨機(jī)訪問(wèn)時(shí)間為常數(shù)。在尾部添加速度很快，在中間插入慢。實(shí)際上就是動(dòng)態(tài)數(shù)組。ppt課件vector支持隨機(jī)訪問(wèn)迭代器，所有STL算法都能對(duì)vect例1：intmain(){ inti; inta[5]={1,2,3,4,5};vector<int>v(5); cout<<v.end()-v.begin()<<endl; for(i=0;i<v.size();i++)v[i]=i; v.at(4)=100; for(i=0;i<v.size();i++) cout<<v[i]<<","; cout<<endl;

vector<int>v2(a,a+5);//構(gòu)造函數(shù)

v2.insert(v2.begin()+2,13);//在begin()+2位置插入13 for(i=0;i<v2.size();i++) cout<<v2[i]<<",";return0;}ppt課件例1：ppt課件輸出：50,1,2,3,100,1,2,13,3,4,5,ppt課件輸出：ppt課件例2：intmain(){ constintSIZE=5; inta[SIZE]={1,2,3,4,5}; vector<int>v(a,a+5);//構(gòu)造函數(shù)

try{

v.at(100)=7; } catch(out_of_rangee){ cout<<e.what()<<endl; } cout<<v.front()<<“,”<<v.back()<<endl; v.erase(v.begin());

ostream_iterator<int>output(cout,“*"); copy(v.begin(),v.end(),output); v.erase(v.begin(),v.end());//等效于v.clear();ppt課件例2：ppt課件 if(v.empty()) cout<<"empty"<<endl; v.insert(v.begin(),a,a+SIZE); copy(v.begin(),v.end(),output);}//輸出：invalidvector<T>subscript1,52*3*4*5*empty1*2*3*4*5*ppt課件ppt課件算法解釋ostream_iterator<int>output(cout,“*");定義了一個(gè)ostream_iterator對(duì)象，可以通過(guò)cout輸出以*分隔的一個(gè)個(gè)整數(shù)copy(v.begin(),v.end(),output);導(dǎo)致v的內(nèi)容在cout上輸出copy函數(shù)模板(算法）：template<classInIt,classOutIt>OutItcopy(InItfirst,InItlast,OutItx);本函數(shù)對(duì)每個(gè)在區(qū)間[0,last-first)中的N執(zhí)行一次*(x+N)=*(first+N)，返回x+N對(duì)于copy(v.begin(),v.end(),output);first和last的類型是vector<int>::const_iteratoroutput的類型是ostream_iterator<int>ppt課件算法解釋ostream_iterator<int>outplist容器在任何位置插入刪除都是常數(shù)時(shí)間，不支持隨機(jī)存取。除了具有所有順序容器都有的成員函數(shù)以外，還支持8個(gè)成員函數(shù)：push_front:在前面插入pop_front:刪除前面的元素sort:排序(list不支持STL的算法sort)remove:刪除和指定值相等的所有元素unique:刪除所有和前一個(gè)元素相同的元素merge:合并兩個(gè)鏈表，并清空被合并的那個(gè)reverse:顛倒鏈表splice:在指定位置前面插入另一鏈表中的一個(gè)或多個(gè)元素,并在另一鏈表中刪除被插入的元素ppt課件list容器在任何位置插入刪除都是常數(shù)時(shí)間，不支持隨機(jī)存取deque容器所有適用于vector的操作都適用于dequedeque還有push_front（將元素插入到前面）和pop_front(刪除最前面的元素）操作ppt課件deque容器所有適用于vector的操作都適用于dequ45關(guān)聯(lián)容器set,multiset,map,multimap

內(nèi)部元素有序排列，新元素插入的位置取決于它的值，查找速度快map關(guān)聯(lián)數(shù)組：元素通過(guò)鍵來(lái)存儲(chǔ)和讀取set大小可變的集合，支持通過(guò)鍵實(shí)現(xiàn)的快速讀取multimap支持同一個(gè)鍵多次出現(xiàn)的map類型multiset支持同一個(gè)鍵多次出現(xiàn)的set類型與順序容器的本質(zhì)區(qū)別關(guān)聯(lián)容器是通過(guò)鍵(key)存儲(chǔ)和讀取元素的而順序容器則通過(guò)元素在容器中的位置順序存儲(chǔ)和訪問(wèn)元素。ppt課件45關(guān)聯(lián)容器set,multiset,map,mult46關(guān)聯(lián)容器除了各容器都有的函數(shù)外，還支持以下成員函數(shù)：設(shè)m表容器，k表鍵值

m.find(k)：如果容器中存在鍵為k的元素，則返回指向該元素的迭代器。如果不存在，則返回end()值。m.lower_bound(k)：返回一個(gè)迭代器，指向鍵不小于k的第一個(gè)元素m.upper_bound(k)：返回一個(gè)迭代器，指向鍵大于k的第一個(gè)元素m.count(k)：返回m中k的出現(xiàn)次數(shù)插入元素用insertppt課件46關(guān)聯(lián)容器除了各容器都有的函數(shù)外，還支持以下成員函數(shù)：設(shè)m47settemplate<classKey,classPred=less<Key>,classA=allocator<Key>>classset{…}插入set中已有的元素時(shí)，插入不成功。ppt課件47settemplate<classKey,class48pair模板pair模板類用來(lái)綁定兩個(gè)對(duì)象為一個(gè)新的對(duì)象，該類型在<utility>頭文件中定義。pair模板類支持如下操作：pair<T1,T2>p1：創(chuàng)建一個(gè)空的pair對(duì)象，它的兩個(gè)元素分別是T1和T2類型，采用值初始化pair<T1,T2>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.first<p2.first或者!(p2.first<p1.first)&&p1.second<p2.second，則返回truep1==p2：如果兩個(gè)pair對(duì)象的first和second成員依次相等，則這兩個(gè)對(duì)象相等。p.first：返回p中名為first的（公有）數(shù)據(jù)成員p.second：返回p中名為second的（公有）數(shù)據(jù)成員ppt課件48pair模板pair模板類用來(lái)綁定兩個(gè)對(duì)象為一個(gè)新的對(duì)象#include<set>#include<iostream>usingnamespacestd;intmain(){ typedefset<double,less<double>>double_set; constintSIZE=5; doublea[SIZE]={2.1,4.2,9.5,2.1,3.7}; double_setdoubleSet(a,a+SIZE);

ostream_iterator<double>output(cout,""); cout<<"1)"; copy(doubleSet.begin(),doubleSet.end(),output); cout<<endl;pair<double_set::const_iterator,bool>p;p=doubleSet.insert(9.5);if(p.second) cout<<"2)"<<*(p.first)<<"inserted"<<endl;elsecout<<"2)"<<*(p.first)<<"notinserted"<<endl;return0;}insert函數(shù)返回值是一個(gè)pair對(duì)象,其first是被插入元素的迭代器，second代表是否成功插入了ppt課件#include<set>insert函數(shù)返回值是一個(gè)pa輸出：1)2.13.74.29.52)9.5notinsertedppt課件ppt課件51multimaptemplate<classKey,classT,classPred=less<Key>,classA=allocator<T>>classmultimap{ …. typedefpair<constKey,T>value_type; ……. };//Key代表關(guān)鍵字multimap中的元素由<關(guān)鍵字,值>組成，每個(gè)元素是一個(gè)pair對(duì)象。multimap中允許多個(gè)元素的關(guān)鍵字相同。元素按照關(guān)鍵字升序排列，缺省情況下用less<Key>定義關(guān)鍵字的“小于”關(guān)系ppt課件51multimaptemplate<classKey,52maptemplate<classKey,classT,classPred=less<Key>,classA=allocator<T>>classmap{ …. typedefpair<constKey,T>value_type; ……. };map中的元素關(guān)鍵字各不相同。元素按照關(guān)鍵字升序排列，缺省情況下用less定義“小于”ppt課件52maptemplate<classKey,class53map可以用pairs[key]訪形式問(wèn)map中的元素。pairs為map容器名，key為關(guān)鍵字的值。該表達(dá)式返回的是對(duì)關(guān)鍵值為key的元素的值的引用。如果沒(méi)有關(guān)鍵字為key的元素，則會(huì)往pairs里插入一個(gè)關(guān)鍵字為key的元素，并返回其值的引用如：map<int,double>pairs;則pairs[50]=5;會(huì)修改pairs中關(guān)鍵字為50的元素，使其值變成5ppt課件53map可以用pairs[key]訪形式問(wèn)map中的元素#include<iostream>#include<map>usingnamespacestd;ostream&operator<<(ostream&o,constpair<int,double>&p){ o<<"("<<p.first<<","<<p.second<<")"; returno;}intmain(){ typedefmap<int,double,less<int>>mmid; mmidpairs; cout<<"1)"<<pairs.count(15)<<endl; pairs.insert(mmid::value_type(15,2.7));

pairs.insert(make_pair(15,99.3));//make_pair生成pair對(duì)象

cout<<"2)"<<pairs.count(15)<<endl; pairs.insert(mmid::value_type(20,9.3));ppt課件#include<iostream>ppt課件 mmid::iteratori; cout<<"3)"; for(i=pairs.begin();i!=pairs.end();i++) cout<<*i<<","; cout<<endl; cout<<"4)"; intn=pairs[40];//如果沒(méi)有關(guān)鍵字為40的元素，則插入一個(gè)

for(i=pairs.begin();i!=pairs.end();i++) cout<<*i<<","; cout<<endl; cout<<"5)"; pairs[15]=6.28;//把關(guān)鍵字為15的元素值改成6.28 for(i=pairs.begin();i!=pairs.end();i++) cout<<*i<<",";return0;}ppt課件 mmid::iteratori;ppt課件輸出：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),ppt課件ppt課件57思考題如何用程序用來(lái)統(tǒng)計(jì)一篇英文文章中單詞出現(xiàn)的頻率（為簡(jiǎn)單起見(jiàn)，假定依次從鍵盤輸入該文章）

#include<iostream>

#include<map>

usingnamespacestd;

intmain()

{

map<string,int>wordCount;

stringword;

while(cin>>word)

++wordCount[word];

for(map<string,int>::iteratorit=wordCount.begin();it!=wordCount.end();++it)

cout<<"Word:"<<(*it).first<<"\tCount:"<<(*it).second<<endl;

return0;

}ppt課件57思考題如何用程序用來(lái)統(tǒng)計(jì)一篇英文文章中單詞出現(xiàn)的頻率（為58容器適配器:stack可用vector,list,deque來(lái)實(shí)現(xiàn)缺省情況下，用deque實(shí)現(xiàn)用vector和deque實(shí)現(xiàn)，比用list實(shí)現(xiàn)性能好template<classT,classCont=deque<T>>classstack{ …..};stack是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，只能插入、刪除、訪問(wèn)棧頂?shù)脑豴pt課件58容器適配器:stack可用vector,list,59

容器適配器:stackstack上可以進(jìn)行以下操作：

push: 插入元素

pop: 彈出元素

top: 返回棧頂元素的引用ppt課件59 容器適配器:stackstack上可以進(jìn)行以下操作：60容器適配器:queue和stack基本類似，可以用list和deque實(shí)現(xiàn)，缺省情況下用deque實(shí)現(xiàn)template<classT,classCont=deque<T>>classqueue{

……};同樣也有push,pop,top函數(shù)但是push發(fā)生在隊(duì)尾，pop,top發(fā)生在隊(duì)頭，先進(jìn)先出ppt課件60容器適配器:queue和stack基本類似，可以用61容器適配器:priority_queue和queue類似，可以用vector和deque實(shí)現(xiàn)，缺省情況下用vector實(shí)現(xiàn)。priority_queue通常用堆排序技術(shù)實(shí)現(xiàn)，保證最大的元素總是在最前面。即執(zhí)行pop操作時(shí)，刪除的是最大的元素，執(zhí)行top操作時(shí)，返回的是最大元素的引用。默認(rèn)的元素比較器是less<T>ppt課件61容器適配器:priority_queue和queue#include<queue>#include<iostream>usingnamespacestd;intmain(){ priority_queue<double>priorities; priorities.push(3.2); priorities.push(9.8); priorities.push(5.4); while(!priorities.empty()){ cout<<priorities.top()<<"";priorities.pop(); }return0;}//輸出結(jié)果：9.85.43.2ppt課件#include<queue>ppt課件63排序和查找算法Sort template<classRanIt> voidsort(RanItfirst,RanItlast);findtemplate<classInIt,classT>InItfind(InItfirst,InItlast,constT&val);

binary_search折半查找，要求容器已經(jīng)有序template<classFwdIt,classT>boolbinary_search(FwdItfirst,FwdItlast,constT&val);ppt課件63排序和查找算法Sortppt課件intmain(){ constintSIZE=10; inta1[]={2,8,1,50,3,100,8,9,10,2}; vector<int>v(a1,a1+SIZE); vector<int>::iteratorlocation; location=find(v.begin(),v.end(),10); if(location!=v.end()){ cout<<endl<<"1)"<<location-v.begin(); }

sort(v.begin(),v.end());if(binary_search(v.begin(),v.end(),9))cout<<endl<<“2)"<<"9found";else cout<<endl<<"

2)"<<"

9notfound";return0;}ppt課件intmain(){ppt課件輸出：1)82)9foundppt課件輸出：ppt課件66sortsort實(shí)際上是快速排序，時(shí)間復(fù)雜度O(n*log(n));平均性能最優(yōu)。但是最壞的情況下，性能可能非常差。如果要保證“最壞情況下”的性能，那么可以使用stable_sortstable_sortstable_sort實(shí)際上是歸并排序（將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列），特點(diǎn)是能保持相等元素之間的先后次序stable_sort用法和sort相同排序算法要求隨機(jī)存取迭代器的支持，所以list不能使用排序算法，要使用list::sortppt課件66sortsort實(shí)際上是快速排序，時(shí)間復(fù)雜度O(n小結(jié)C++模板函數(shù)模板STL庫(kù)各種容器迭代器算法67ppt課件小結(jié)C++模板67ppt課件C++模板與STL庫(kù)介紹(參考北京大學(xué)單棟棟課件)68ppt課件C++模板與STL庫(kù)介紹(參考北京大學(xué)單棟棟課件)1ppt課提綱1.概論2.模板機(jī)制的介紹3.STL中的基本概念4.容器概述5.迭代器6.算法簡(jiǎn)介ppt課件提綱1.概論ppt課件概論C++語(yǔ)言的核心優(yōu)勢(shì)之一就是便于軟件的重用C++中有兩個(gè)方面體現(xiàn)重用：1.面向?qū)ο蟮乃枷耄豪^承和多態(tài)，標(biāo)準(zhǔn)類庫(kù)

2.泛型程序設(shè)計(jì)(genericprogramming)的思想：模板機(jī)制，以及標(biāo)準(zhǔn)模板庫(kù)STL這次課的重點(diǎn)ppt課件概論C++語(yǔ)言的核心優(yōu)勢(shì)之一就是便于軟件的重用這次課的重點(diǎn)泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)，簡(jiǎn)單地說(shuō)就是使用模板的程序設(shè)計(jì)法。將一些常用的數(shù)據(jù)結(jié)構(gòu)（比如鏈表，數(shù)組，二叉樹(shù)）和算法（比如排序，查找）寫(xiě)成模板，以后則不論數(shù)據(jù)結(jié)構(gòu)里放的是什么對(duì)象，算法針對(duì)什么樣的對(duì)象，則都不必重新實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，重新編寫(xiě)算法。標(biāo)準(zhǔn)模板庫(kù)(StandardTemplateLibrary)就是一些常用數(shù)據(jù)結(jié)構(gòu)和算法的模板的集合。主要由AlexStepanov開(kāi)發(fā)，于1998年被添加進(jìn)C++標(biāo)準(zhǔn)有了STL，不必再?gòu)念^寫(xiě)大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。ppt課件泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)，簡(jiǎn)單地說(shuō)就是使用模板的程序設(shè)計(jì)法。模板引子1.假如設(shè)計(jì)一個(gè)求兩參數(shù)最大值的函數(shù)，在實(shí)踐中我們可能需要定義四個(gè)函數(shù)：

intmax

(

inta

,

intb

)

{

return

(

a

>

b

)

?

a

,

b

;}

longmax(longa,longb){return(a>b)?a,b;}

doublemax(doublea,doubleb){return(a>b)?a,b;}

charmax(chara,charb){return(a>b)?a,b;}2.這些函數(shù)幾乎相同，唯一的區(qū)別就是形參類型不同3.需要事先知道有哪些類型會(huì)使用這些函數(shù)，對(duì)于未知類型這些函數(shù)不起作用

ppt課件模板引子1.假如設(shè)計(jì)一個(gè)求兩參數(shù)最大值的函數(shù)，在實(shí)踐中我們可模板的概念所謂模板是一種使用無(wú)類型參數(shù)來(lái)產(chǎn)生一系列函數(shù)或類的機(jī)制。若一個(gè)程序的功能是對(duì)某種特定的數(shù)據(jù)類型進(jìn)行處理，則可以將所處理的數(shù)據(jù)類型說(shuō)明為參數(shù)，以便在其他數(shù)據(jù)類型的情況下使用，這就是模板的由來(lái)。模板是以一種完全通用的方法來(lái)設(shè)計(jì)函數(shù)或類而不必預(yù)先說(shuō)明將被使用的每個(gè)對(duì)象的類型。通過(guò)模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個(gè)單獨(dú)的類或函數(shù)。ppt課件模板的概念所謂模板是一種使用無(wú)類型參數(shù)來(lái)產(chǎn)生一系列函數(shù)或類的模板分類函數(shù)模板(functiontemplate)是獨(dú)立于類型的函數(shù)可產(chǎn)生函數(shù)的特定版本類模板(classtemplate)跟類相關(guān)的模板，如vector可產(chǎn)生類對(duì)特定類型的版本，如vector<int>74ppt課件模板分類函數(shù)模板(functiontemplate)7pp求最大值模板函數(shù)實(shí)現(xiàn)1.求兩個(gè)數(shù)最大值，使用模板

template<classT> Tmax(Ta,Tb){ return(a>b)?a,b; }2.template<模板形參表><返回值類型><函數(shù)名>（模板函數(shù)形參表）{//函數(shù)定義體}75ppt課件求最大值模板函數(shù)實(shí)現(xiàn)1.求兩個(gè)數(shù)最大值，使用模板8ppt課件模板工作方式函數(shù)模板只是說(shuō)明，不能直接執(zhí)行，需要實(shí)例化為模板函數(shù)后才能執(zhí)行在說(shuō)明了一個(gè)函數(shù)模板后，當(dāng)編譯系統(tǒng)發(fā)現(xiàn)有一個(gè)對(duì)應(yīng)的函數(shù)調(diào)用時(shí)，將根據(jù)實(shí)參中的類型來(lái)確認(rèn)是否匹配函數(shù)模板中對(duì)應(yīng)的形參，然后生成一個(gè)重載函數(shù)。該重載函數(shù)的定義體與函數(shù)模板的函數(shù)定義體相同，它稱之為模板函數(shù)76ppt課件模板工作方式函數(shù)模板只是說(shuō)明，不能直接執(zhí)行，需要實(shí)例化為模板#include<iostream>template<classT>Tmin(Ta[],intn){ inti; Tminv=a[0]; for(i=1;i<n;i++){ if(minv>a[i]) minv=a[i]; } returnminv;}編寫(xiě)一個(gè)對(duì)具有n個(gè)元素的數(shù)組a[]求最小值的程序，要求將求最小值的函數(shù)設(shè)計(jì)成函數(shù)模板。voidmain(){inaa[]={1,3,0,2,7,6,4,5,2};doubleb[]={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.4ppt課件#include<iostream>編寫(xiě)一個(gè)對(duì)具有n個(gè)元素模板優(yōu)缺點(diǎn)函數(shù)模板方法克服了C語(yǔ)言解決上述問(wèn)題時(shí)用大量不同函數(shù)名表示相似功能的壞習(xí)慣克服了宏定義不能進(jìn)行參數(shù)類型檢查的弊端克服了C++函數(shù)重載用相同函數(shù)名字重寫(xiě)幾個(gè)函數(shù)的繁瑣缺點(diǎn)，調(diào)試比較困難一般先寫(xiě)一個(gè)特殊版本的函數(shù)運(yùn)行正確后，改成模板函數(shù)78ppt課件模板優(yōu)缺點(diǎn)函數(shù)模板方法克服了C語(yǔ)言解決上述問(wèn)題時(shí)用大量不同函STL中的幾個(gè)基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。迭代器：可依次存取容器中元素的東西算法：用來(lái)操作容器中的元素的函數(shù)模板。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象。函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用。比如，數(shù)組intarray[100]就是個(gè)容器，而int*類型的指針變量就可以作為迭代器，可以為這個(gè)容器編寫(xiě)一個(gè)排序的算法ppt課件STL中的幾個(gè)基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。p容器概述可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對(duì)象等）的數(shù)據(jù)結(jié)構(gòu)。容器分為三大類：1)順序容器

vector：后部插入/刪除，直接訪問(wèn)

deque：前/后部插入/刪除，直接訪問(wèn)

list：雙向鏈表，任意位置插入/刪除

2)關(guān)聯(lián)容器

set：快速查找，無(wú)重復(fù)元素

multiset：快速查找，可有重復(fù)元素

map：一對(duì)一映射，無(wú)重復(fù)元素，基于關(guān)鍵字查找

multimap：一對(duì)一映射，可有重復(fù)元素，基于關(guān)鍵字查找前2者合稱為第一類容器3)容器適配器

stack：LIFO

queue：FIFO

priority_queue：優(yōu)先級(jí)高的元素先出ppt課件容器概述可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對(duì)象等）容器概述對(duì)象被插入容器中時(shí)，被插入的是對(duì)象的一個(gè)復(fù)制品。許多算法，比如排序，查找，要求對(duì)容器中的元素進(jìn)行比較，所以，放入容器的對(duì)象所屬的類，還應(yīng)該實(shí)現(xiàn)==和<

運(yùn)算符。ppt課件容器概述對(duì)象被插入容器中時(shí)，被插入的是對(duì)象的一個(gè)復(fù)制品。pp順序容器簡(jiǎn)介1)vector頭文件<vector>

實(shí)際上就是個(gè)動(dòng)態(tài)數(shù)組。隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成。在尾端增刪元素具有較佳的性能。

2)deque頭文件<deque>

也是個(gè)動(dòng)態(tài)數(shù)組，隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。

3)list頭文件<list>

雙向鏈表，在任何位置增刪元素都能在常數(shù)時(shí)間完成。不支持隨機(jī)存取。上述三種容器稱為順序容器，是因?yàn)樵氐牟迦胛恢猛氐闹禑o(wú)關(guān)，只跟插入的時(shí)機(jī)有關(guān)。ppt課件順序容器簡(jiǎn)介1)vector頭文件<vector>p關(guān)聯(lián)容器簡(jiǎn)介關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來(lái)確定其位置。關(guān)聯(lián)式容器的特點(diǎn)是在查找時(shí)具有非常好的性能。1)set/multiset:頭文件<set>set即集合。set中不允許相同元素，multiset中允許存在相同的元素。2)map/multimap:頭文件<map>map與set的不同在于map中存放的是成對(duì)的key/value。并根據(jù)key對(duì)元素進(jìn)行排序，可快速地根據(jù)key來(lái)檢索元素

map同multimap的不同在于是否允許多個(gè)元素有相同的key值。上述4種容器通常以平衡二叉樹(shù)方式實(shí)現(xiàn)，插入、查找和刪除的時(shí)間都是O(logN)

ppt課件關(guān)聯(lián)容器簡(jiǎn)介關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相容器適配器簡(jiǎn)介1)stack:頭文件<stack>

棧。是項(xiàng)的有限序列，并滿足序列中被刪除、檢索和修改的項(xiàng)只能是最近插入序列的項(xiàng)。即按照后進(jìn)先出的原則2)queue:頭文件<queue>

隊(duì)列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照先進(jìn)先出的原則。3）priority_queue:頭文件<queue>

優(yōu)先級(jí)隊(duì)列。最高優(yōu)先級(jí)元素總是第一個(gè)出列ppt課件容器適配器簡(jiǎn)介1)stack:頭文件<stack>p容器的共有成員函數(shù)1)所有標(biāo)準(zhǔn)庫(kù)容器共有的成員函數(shù)： 相當(dāng)于按詞典順序比較兩個(gè)容器大小的運(yùn)算符：

=,<,<=,>,>=,==,!= empty:判斷容器中是否有元素

max_size:容器中最多能裝多少元素

size:容器中元素個(gè)數(shù)

swap:交換兩個(gè)容器的內(nèi)容ppt課件容器的共有成員函數(shù)1)所有標(biāo)準(zhǔn)庫(kù)容器共有的成員函數(shù)：ppt比較兩個(gè)容器的例子86比較兩個(gè)容器的例子：#include<vector>#include<iostream>intmain(){ std::vector<int>v1; std::vector<int>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);return0;}若兩容器長(zhǎng)度相同、所有元素相等，則兩個(gè)容器就相等，否則為不等。若兩容器長(zhǎng)度不同，但較短容器中所有元素都等于較長(zhǎng)容器中對(duì)應(yīng)的元素，則較短容器小于另一個(gè)容器若兩個(gè)容器均不是對(duì)方的子序列，則取決于所比較的第一個(gè)不等的元素輸出：0ppt課件比較兩個(gè)容器的例子19比較兩個(gè)容器的例子：若兩容器長(zhǎng)度相同、容器的成員函數(shù)2)只在第一類容器中的函數(shù)：

begin返回指向容器中第一個(gè)元素的迭代器

end返回指向容器中最后一個(gè)元素后面的位置的迭代器

rbegin返回指向容器中最后一個(gè)元素的迭代器

rend返回指向容器中第一個(gè)元素前面的位置的迭代器

erase從容器中刪除一個(gè)或幾個(gè)元素

clear從容器中刪除所有元素HeadTailbeginrbeginrendendppt課件容器的成員函數(shù)2)只在第一類容器中的函數(shù)：HeadTai迭代器用于指向第一類容器中的元素。有const和非const兩種。通過(guò)迭代器可以讀取它指向的元素，通過(guò)非const迭代器還能修改其指向的元素。迭代器用法和指針類似。定義一個(gè)容器類的迭代器的方法可以是：

容器類名::iterator變量名;或：

容器類名::const_iterator變量名;訪問(wèn)一個(gè)迭代器指向的元素：

*迭代器變量名ppt課件迭代器用于指向第一類容器中的元素。有const和非con迭代器迭代器上可以執(zhí)行++

操作,以指向容器中的下一個(gè)元素。如果迭代器到達(dá)了容器中的最后一個(gè)元素的后面，則迭代器變成past-the-end值。使用一個(gè)past-the-end值的迭代器來(lái)訪問(wèn)對(duì)象是非法的，就好像使用NULL或未初始化的指針一樣。ppt課件迭代器迭代器上可以執(zhí)行++操作,以指向容器中的下一個(gè)元例如：#include<vector>#include<iostream>usingnamespacestd;intmain(){ vector<int>v;//一個(gè)存放int元素的向量，一開(kāi)始里面沒(méi)有元素

v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::const_iteratori;//常量迭代器

for(i=v.begin();i!=v.end();i++) cout<<*i<<","; cout<<endl;ppt課件例如：ppt課件 vector<int>::reverse_iteratorr;//反向迭代器

for(r=v.rbegin();r!=v.rend();r++) cout<<*r<<","; cout<<endl; vector<int>::iteratorj;//非常量迭代器

for(j=v.begin();j!=v.end();j++) *j=100; for(i=v.begin();i!=v.end();i++) cout<<*i<<",";}輸出結(jié)果：1,2,3,4,4,3,2,1,100,100,100,100,ppt課件 vector<int>::reverse_iterator迭代器不同容器上支持的迭代器功能強(qiáng)弱有所不同。容器的迭代器的功能強(qiáng)弱，決定了該容器是否支持STL中的某種算法。例1：只有第一類容器能用迭代器遍歷。例2：排序算法需要通過(guò)隨機(jī)迭代器來(lái)訪問(wèn)容器中的元素，那么有的容器就不支持排序算法。ppt課件迭代器不同容器上支持的迭代器功能強(qiáng)弱有所不同。ppt課件STL中的迭代器STL中的迭代器按功能由弱到強(qiáng)分為5種：

1.輸入：Inputiterators提供對(duì)數(shù)據(jù)的只讀訪問(wèn)。

1.輸出：Outputiterators提供對(duì)數(shù)據(jù)的只寫(xiě)訪問(wèn)

2.正向：Forwarditerators提供讀寫(xiě)操作，并能一次一個(gè)地向前推進(jìn)迭代器。

3.雙向：Bidirectionaliterators提供讀寫(xiě)操作，并能一次一個(gè)地向前和向后移動(dòng)。

4.隨機(jī)訪問(wèn)：Randomaccessiterators提供讀寫(xiě)操作，并能在數(shù)據(jù)中隨機(jī)移動(dòng)。編號(hào)大的迭代器擁有編號(hào)小的迭代器的所有功能，能當(dāng)作編號(hào)小的迭代器使用。ppt課件STL中的迭代器STL中的迭代器按功能由弱到強(qiáng)分為5種：不同迭代器所能進(jìn)行的操作(功能）所有迭代器：++p,p++輸入迭代器：*p,p=p1,p==p1,p!=p1輸出迭代器：*p,p=p1正向迭代器：上面全部雙向迭代器：上面全部，--p,p--,隨機(jī)訪問(wèn)迭代器：上面全部，以及：

p+=i,p-=i, p+i：返回指向p后面的第i個(gè)元素的迭代器

p-i：返回指向p前面的第i個(gè)元素的迭代器p[i]: p后面的第i個(gè)元素的引用

p<p1,p<=p1,p>p1,p>=p1ppt課件不同迭代器所能進(jìn)行的操作(功能）所有迭代器：++p,p容器所支持的迭代器類別

容器 迭代器類別

vector 隨機(jī)

deque 隨機(jī)

list 雙向

set/multiset 雙向

map/multimap 雙向

stack 不支持迭代器

queue 不支持迭代器

priority_queue 不支持迭代器ppt課件容器所支持的迭代器類別 容器 迭代器類別ppt課件例如，vector的迭代器是隨機(jī)迭代器，所以遍歷vector可以有以下幾種做法：vector<int>v(100);inti;for(i=0;i<v.size();i++) cout<<v[i];vector<int>::const_iteratorii;for(ii=v.begin();ii!=v.end();ii++) cout<<*ii;//間隔一個(gè)輸出：ii=v.begin();while(ii<v.end()){ cout<<*ii; ii=ii+2;}ppt課件例如，vector的迭代器是隨機(jī)迭代器，所以遍歷vecto而list的迭代器是雙向迭代器，所以以下代碼可以：

list<int>v;

list<int>::const_iteratorii; for(ii=v.begin();ii?。絭.end();ii++) cout<<*ii; 以下代碼則不行：

for(ii=v.begin();ii<v.end();ii++) cout<<*ii; //雙向迭代器不支持< for(inti=0;i<v.size();i++) cout<<v[i];//雙向迭代器不支持[]ppt課件而list的迭代器是雙向迭代器，所以以下代碼可以：ppt算法簡(jiǎn)介STL中提供能在各種容器中通用的算法，比如插入，刪除，查找，排序等。大約有70種標(biāo)準(zhǔn)算法。 算法就是一個(gè)個(gè)函數(shù)模板。 算法通過(guò)迭代器來(lái)操縱容器中的元素。許多算法需要兩個(gè)參數(shù)，一個(gè)是起始元素的迭代器，一個(gè)是終止元素的后面一個(gè)元素的迭代器。比如，排序和查找 有的算法返回一個(gè)迭代器。比如find()算法，在容器中查找一個(gè)元素，并返回一個(gè)指向該元素的迭代器。 算法可以處理容器，也可以處理C語(yǔ)言的數(shù)組ppt課件算法簡(jiǎn)介STL中提供能在各種容器中通用的算法，比如插入，刪除

算法分類變化序列算法copy,remove,fill,replace,random_shuffle,swap,…..會(huì)改變?nèi)萜鞣亲兓蛄兴惴ǎ篴djacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n以上函數(shù)模板都在<algorith