會計學1CSTL泛型編程長望班2為什么要采用泛型編程？ACM競賽中,需要用到數(shù)組、鏈表、字符串、棧、隊列、平衡二叉樹等數(shù)據(jù)結(jié)構(gòu)，以及排序、搜索等算法；若全部自行編寫比較麻煩；ANSIC++中包含了C++STL(StandardTemplateLibrary,標準模板庫,又稱C++泛型庫)，定義了常用的數(shù)據(jù)結(jié)構(gòu)和算法，使用十分方便。有了STL，不必再從頭寫大多的標準數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。但這不意味著我們不需要掌握基本數(shù)據(jù)結(jié)構(gòu)與算法;相反,只有透徹理解了,才能更好的使用泛型!第1頁/共101頁泛型程序設(shè)計由AlexanderStepanov和DavidMusser創(chuàng)立，于1998年被添加進C++標準.含義：編寫不依賴于具體數(shù)據(jù)類型的程序.目標：將程序?qū)懙帽M可能通用.將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的.C++的模板為泛型程序設(shè)計奠定了關(guān)鍵的基礎(chǔ).STL

(標準模板庫,StandardTemplateLibrary)是泛型程序設(shè)計的一個范例.代碼重用(reuse)!第2頁/共101頁函數(shù)模板簡介4

【引例】交換2個整數(shù)和交換2個浮點數(shù)的C++程序://交換2個整數(shù)voidSwap(int&a,int&b){inttmp=0;tmp=a;a=b;b=tmp;}//交換2個浮點數(shù)voidSwap(float&a,float&b){floattmp=0.0;tmp=a;a=b;b=tmp;}intmain(){inta=10,b=20;floatc=1.2,d=2.4;cout<<"a="<<a<<"b="

<<b;cout<<"c="<<c<<"d="

<<c;

Swap(a,b);cout<<"a="<<a<<"

b="

<<b;

Swap(c,d);cout<<"

c="<<c<<"d="

<<c;return0;}

兩個Swap函數(shù)實現(xiàn)的功能相同，只是參數(shù)類型不同，但為了實現(xiàn)不同類型的數(shù)據(jù)交換必須分別編寫函數(shù)。造成了重復勞動。函數(shù)重載第3頁/共101頁5

能否提供一種方法將兩個函數(shù)合并，以節(jié)省開發(fā)成本？引例typedefintDataType;voidSwap(DataType&a,DataType&b){ DataTypetmp; tmp=a; a=b; b=tmp;}intmain(){inta=10,b=20;Swap(a,b);return0;}當需要交換兩個浮點數(shù)時可以將DataType定義成float型數(shù)據(jù)即可。typedeffloatDateType;存在問題：更改一種數(shù)據(jù)類型時，需要修改程序源代碼，必須重新編譯程序。如果程序中需要交換多種數(shù)據(jù)類型數(shù)據(jù),怎么辦？第4頁/共101頁6引例#include<iostream>usingnamespacestd;template<classT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}intmain(){inta=10,b=20;floatc=1.2,d=2.4;cout<<"a="<<a<<"b="<<b<<endl;cout<<"c="<<c<<"d="<<c<<endl;

Swap(a,b);cout<<"a="<<a<<"b="<<b<<endl;

Swap(c,d);cout<<"c="<<c<<"d="<<c<<endl;return0;}模板聲明定義函數(shù)模板通用的Swap!能否將Swap函數(shù)的形式參數(shù)，作為一種無類型的參數(shù)，當使用它的時候再將它用具體的參數(shù)實現(xiàn)？模板機制第5頁/共101頁模板的概念模板是一種使用無類型參數(shù)來產(chǎn)生一系列函數(shù)或類的機制。模板是以一種完全通用的方法來設(shè)計函數(shù)或類而不必預先說明將被使用的每個對象的類型。通過模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個單獨的類或函數(shù)。

7第6頁/共101頁模板分類函數(shù)模板(functiontemplate)是獨立于類型的函數(shù)可產(chǎn)生函數(shù)的特定版本類模板(classtemplate)與類相關(guān)的模板，如vector可產(chǎn)生類對特定類型的版本，如vector<int>8第7頁/共101頁模板工作方式模板只是說明，需要實例化后才能執(zhí)行或使用.9模板函數(shù)模板類模板模板類模板函數(shù)對象實例化實例化實例化第8頁/共101頁函數(shù)模板(functiontemplate)定義格式：template<模板參數(shù)表>類型名函數(shù)名（參數(shù)表）{

函數(shù)體}template<classT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}10template:

函數(shù)模板定義關(guān)鍵字.<>中是函數(shù)的模板參數(shù)，參數(shù)可有一個或多個，逗號隔開。不能為空！

模板參數(shù)常用形式：

class標識符或者typename標識符模板參數(shù)表明函數(shù)可以接收的類型參數(shù)，可以是內(nèi)部類型，也可以是自定義類型.template<typenameT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}第9頁/共101頁

【例1】簡單函數(shù)模板定義和應用.#include<iostream>usingnamespacestd;template<typenameT>TMax(Ta,Tb){returna>b?a:b;}intmain(){cout<<"Max(3,5)is"<<Max(3,5)<<endl;cout<<"Max('y','e')is"<<Max('y','e')<<endl;cout<<"Max(9.3,0.5)is"<<Max(9.3,0.5)<<endl;return0;}函數(shù)模板intMax(inta,intb){returna>b?a:b;}由實參類型實例化charMax(chara,charb){returna>b?a:b;}doubleMax(doublea,doubleb){returna>b?a:b;}編譯器生成的模板函數(shù)函數(shù)模板實例化函數(shù)模板的原理分析：函數(shù)模板中聲明了類型參數(shù)T，表示了一種抽象類型.

編譯器檢測到程序調(diào)用函數(shù)模板Max時，用其第一個實參類型替換掉模板中的T，同時建立一個完整的函數(shù)Max，并編譯該新建的函數(shù).

本例中，針對三種數(shù)據(jù)類型，生成了三種函數(shù).第10頁/共101頁

【練習1】編寫一個對具有n個元素的數(shù)組a[]求最小值的程序，要求將求最小值的函數(shù)設(shè)計成函數(shù)模板。#include<iostream>usingnamespacestd;template<classT>TMinArray(Ta[],intn){ inti; Tmina=a[0]; for(i=1;i<n;i++){ if(mina>a[i]) mina=a[i]; } returnmina;}intmain(){intarr1[]={1,3,0,2,7,6,4,5,2};doublearr2[]={1.2,-3.4,6.8,9,8};cout<<"arr1數(shù)組的最小值為："

<<MinArray(arr1,9)<<endl;cout<<"arr2數(shù)組的最小值為："

<<MinArray(arr2,4)<<endl;return0;}第11頁/共101頁

注意點1：實參類型與形參類型必須嚴格匹配.#include<iostream>usingnamespacestd;template<classT>TMax(Ta,Tb){returna>b?a:b;}intmain(){inta=3;floatb=1.5;cout<<"Max(a,b)is"<<Max(a,b)<<endl;return0;}錯誤！模板類型不能提供類型的隱式轉(zhuǎn)換第12頁/共101頁注意點2：在函數(shù)模板中允許使用多個類型參數(shù)。在template定義部分的每個模板形參前必須有關(guān)鍵字class或typename.#include<iostream>usingnamespacestd;template<classT1,classT2>voidmyfunc(T1x,T2y){cout<<x<<","<<y<<endl;}intmain(){myfunc(100,"hao");myfunc(3.14,10L);return0;}第13頁/共101頁

注意點3：在template語句與函數(shù)模板定義語句之間不允許有別的語句。Template<classT>inti;

//錯誤，不允許有別的語句TMax(Tx,Ty){return(x>y)?x:y;}8第14頁/共101頁模板優(yōu)缺點優(yōu)點:函數(shù)模板方法克服了C語言用大量不同函數(shù)名表示相似功能的弊端;克服了宏定義不能進行參數(shù)類型檢查的弊端;克服了C++函數(shù)重載用相同函數(shù)名字重寫幾個函數(shù)的繁瑣.缺點:

調(diào)試比較困難.一般先寫一個特殊版本的函數(shù)運行正確后，改成模板函數(shù)16第15頁/共101頁17

【練習2】編寫一個函數(shù)模板，它返回兩個值中的較小者，同時要求能正確處理字符串。

分析：由于C++字符串比較的方法與字符型、數(shù)值型都不同，因此函數(shù)模板不適用于字符串比較；這里設(shè)計一個函數(shù)模板template<classT>Tmin(Ta,Tb)，可以處理int、float和char等數(shù)據(jù)類型；為了能正確處理字符串，添加一個重載函數(shù)專門處理字符串比較，即char*min(char*a,char*b)。第16頁/共101頁

#include<iostream.h>#include<string.h>

template<classT>Tmin(Ta,Tb){

return(a<b?a:b);

}

char*min(char*a,char*b){

return(strcmp(a,b)<0?a:b);

}voidmain(){

doublea=3.14,b=8.28;chars1[]="Bad",s2[]="Good";cout<<"輸出結(jié)果:"<<endl;

cout<<min(a,b)<<endl;

cout<<min(s1,s2)<<endl;}

函數(shù)模板函數(shù)重載第17頁/共101頁C++STL第18頁/共101頁一、STL概述STL是一個具有工業(yè)強度的，高效的C++程序庫包含了諸多在計算機科學領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法STL主要包含了容器、算法、迭代器庫（library）是一系列程序組件的集合，它們可以在不同的程序中重復使用。第19頁/共101頁21

【引例】閱讀以下程序:#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v;inti;for(i=0;i<10;i++) v.push_back(i);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}Vector容器聲明一個整型Vector容器尾部元素追加用迭代器配合循環(huán)訪問向量元素第20頁/共101頁22STL中的基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)迭代器：可訪問容器中元素的特殊指針算法：用來操作容器中元素的函數(shù)模板函數(shù)對象:

是一個行為類似函數(shù)的對象，可象函數(shù)一樣調(diào)用。例如，向量Vector就是容器，

iterator是迭代器。STL用sort()來對一個vector中的數(shù)據(jù)進行排序，用find()來搜索一個list中的對象最基本的遍歷結(jié)構(gòu)對數(shù)據(jù)結(jié)構(gòu)的操作

C++STL是通用數(shù)據(jù)結(jié)構(gòu)和算法的封裝！第21頁/共101頁C++STL中，容器（container）就是通用的數(shù)據(jù)結(jié)構(gòu)。容器用來承載不同類型的數(shù)據(jù)對象;C++中的容器還存在一定的“數(shù)據(jù)加工能力”

它如同一個對數(shù)據(jù)對象進行加工的模具，可以把不同類型的數(shù)據(jù)放到這個模具中進行加工處理，形成具有一定共同特性的數(shù)據(jù)結(jié)構(gòu)。

例如,

將int型、char型或者float型放到隊列容器中，就分別生成int隊列、char型隊列或者float型隊列.它們都是隊列，具有隊列的基本特性，但是具體數(shù)據(jù)類型是不一樣的。概念之

容器就如同現(xiàn)實生活中，人們使用容器用來裝載各種物品一樣第22頁/共101頁24概念之容器適配器C++STL容器適配器用來擴充7種基本容器：

stack：棧（LIFO）

queue：隊列（FIFO）

priority_queue：優(yōu)先級隊列第23頁/共101頁25概念之迭代器用于指向容器中的元素。通過迭代器可以讀取它指向的元素。迭代器是泛化的指針，可用“++”改變其指向位置，可用“*”訪問內(nèi)容。第24頁/共101頁2626概念之算法C++STL包含70多個算法。包括：查找、排序、比較、變換、置換、容器管理等。算法是通用的，可作用于不同的類對象和預定義類型數(shù)據(jù)。第25頁/共101頁2727STL組件間的關(guān)系

容器(container)算法(algorithm)容器(container)迭代器(iterator)函數(shù)對象(function

object)迭代器(iterator)C++STL將迭代器和函數(shù)對象作為算法的參數(shù)，提供了極大靈活性。使用STL提供的或自定義的迭代器，配合STL算法，可組合出各種各樣強大的功能。第26頁/共101頁STL頭文件一覽頭文件內(nèi)容頭文件內(nèi)容<iterator>迭代器<vector>向量<utility>輔助功能<deque>雙頭隊列<memory>內(nèi)存管理<list>鏈表<algorithm>算法<set>集合與多重集合<functional>函數(shù)對象<map>映射與多重映射<numeric>數(shù)值運算<stack>棧<queue>隊列與優(yōu)先隊列第27頁/共101頁容器的基本功能與分類容器是容納、包含一組元素或元素集合的對象。七種基本容器：向量（vector）雙端隊列（deque）列表（list）集合（set）多重集合（multiset）映射（map）多重映射（multimap）C++STL的容器各有不盡相同的功能和用法。順序容器關(guān)聯(lián)容器29第28頁/共101頁二、順序容器容器名頭文件名說明vector<vector>向量，從后面快速插入和刪除，直接訪問任何元素list<list>雙向鏈表deque<deque>雙端隊列set<set>元素不重復的集合multiset<set>元素可重復的集合map<map>一個鍵只對于一個值的映射multimap<map>一個鍵可對于多個值的映射stack<stack>堆棧，后進先出（LIFO）queue<queue>隊列，先進先出（FIFO）priority_queue<queue>優(yōu)先級隊列第29頁/共101頁順序容器(sequencecontainer)簡介順序容器(也稱“序列式容器”)將一組具有相同類型的元素以嚴格的線性形式組織起來。三類順序容器：(1)vector頭文件<vector>

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

(2)deque頭文件<deque>

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

(3)list頭文件<list>

雙向鏈表，在任何位置增刪元素都能在常數(shù)時間完成。不支持隨機存取。31第30頁/共101頁關(guān)聯(lián)容器簡介關(guān)聯(lián)容器內(nèi)的元素是排序的，插入任何元素，都按相應的排序準則來確定其位置。特點是在查找時具有非常好的性能。通常以平衡二叉樹方式實現(xiàn)，插入和檢索的時間都是O(logN)四種關(guān)聯(lián)容器：

(1)set/multiset:頭文件<set>

set即集合。set中不允許相同元素，multiset中允許存在相同的元素。(2)map/multimap:頭文件<map>

map與set的不同在于map中存放的是成對的key/value。

并根據(jù)key對元素進行排序，可快速地根據(jù)key來檢索元素

map同multimap的不同在于是否允許多個元素有相同的key值。類似于Hash表32第31頁/共101頁容器適配器簡介(1)stack:頭文件<stack>

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

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

優(yōu)先隊列。最高優(yōu)先級元素總是第一個出列。容器適配器是一種接口類，為已有類提供新的接口三種容器適配器：33第32頁/共101頁容器的共有成員函數(shù)提供容器的通用功能；所有容器共有的成員函數(shù)：

關(guān)系運算：

=,<,<=,>,>=,==,!=

empty()

:

判斷容器中是否為空

max_size():

容器中最多能裝多少元素

size():

容器中元素個數(shù)

s1.swap(s2)：交換兩個容器的內(nèi)容構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)34第33頁/共101頁容器的共有成員函數(shù)(續(xù))所有順序容器和關(guān)聯(lián)容器共有的成員函數(shù)：begin()：返回指向容器中第一個元素的迭代器end()：返回指向容器中最后一個元素后面的位置的迭代器rbegin():

返回指向容器中最后一個元素的迭代器rend():

返回指向容器中第一個元素前面的位置的迭代器

erase():

從容器中刪除一個或幾個元素clear()：清空容器35HeadTailbeginrbeginrendend第34頁/共101頁所有容器都具有的成員函數(shù)成員函數(shù)名說明默認構(gòu)造函數(shù)對容器進行默認初始化的構(gòu)造函數(shù)，常有多個，用于提供不同的容器初始化方法拷貝構(gòu)造函數(shù)用于將容器初始化為同類型的現(xiàn)有容器的副本析構(gòu)函數(shù)執(zhí)行容器銷毀時的清理工作empty()判斷容器是否為空，若為空返回true，否則返回falsemax_size()返回容器最大容量，即容器能夠保存的最多元素個數(shù)size返回容器中當前元素的個數(shù)operator=(==)將一個容器賦給另一個同類容器operator<(<)如果第1個容器小于第2個容器，則返回true，否則返回falseoperator<=(<=)如果第1個容器小于等于第2個容器，則返回true，否則返回falseoperator>(>)如果第1個容器大于第2個容器，則返回true，否則返回falseoperator>=(>=)如果第1個容器大于等于第2個容器，則返回true，否則返回falseswap交換兩個容器中的元素第35頁/共101頁順序和關(guān)聯(lián)容器共同支持的成員函數(shù)成員函數(shù)名說明begin()指向第一個元素end()指向最后一個元素rbegin()指向按反順序的第一個元素rend()指向按反順序的末端位置erase()刪除容器中的一個或多個元素clear()刪除容器中的所有元素第36頁/共101頁【例1】創(chuàng)建兩個整型向量容器，分別從尾端增加一些值，輸出兩個容器的元素數(shù)、兩個容器的比較結(jié)果，交換兩個容器后再輸出一次。38#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v1,v2;v1.push_back(5);v1.push_back(1);v2.push_back(1);v2.push_back(2);v2.push_back(3);cout<<"v1元素數(shù):"<<v1.size()<<",v2元素數(shù):"<<v2.size()<<endl;if(v1==v2)cout<<"v1==v2"<<endl;elseif(v1<v2)cout<<"v1<v2"<<endl;elsecout<<"v1>v2"<<endl;v1.swap(v2);cout<<"v1元素數(shù):"<<v1.size()<<",v2元素數(shù):"<<v2.size()<<endl;if(v1==v2)cout<<"v1==v2"<<endl;elseif(v1<v2)cout<<"v1<v2"<<endl;elsecout<<"v1>v2"<<endl;return0;}聲明2個向量向量賦值

51

v1

123

v2求元素數(shù)向量內(nèi)容比較交換2個向量第37頁/共101頁1、vector向量容器實際上就是動態(tài)數(shù)組。但它比數(shù)組更靈活，當添加數(shù)據(jù)時，vector的大小能夠自動增加以容納新的元素。內(nèi)存自動管理?？蓜討B(tài)調(diào)整所占內(nèi)存。支持隨機訪問，隨機訪問時間為常數(shù)。所有STL算法都能對vector操作。在尾部添加速度很快，在中間插入慢。39第38頁/共101頁(1)創(chuàng)建vector對象四種方式:不指定容器的元素個數(shù)：vector<類型T>對象名；例如：vector<int>v;//創(chuàng)建整型向量v指定容器大?。簐ector<類型T>對象名(n)；例如：vector<int>v(10);//創(chuàng)建整型向量v,10個元素注意：元素下標0~9,初始化為0.指定容器大小和元素初始值：vector<類型T>對象名(n,初值)；例如：vector<int>v(10,1);

//創(chuàng)建整型向量v,10個元素,每個元素值均為1由已有向量容器創(chuàng)建:

vector<類型T>對象名(已有對象名)；例如：vector<int>v2(v1);//創(chuàng)建整型向量v1的副本v240拷貝構(gòu)造函數(shù)第39頁/共101頁創(chuàng)建vector向量幾種初始化vector對象的方式vector<T>v1;vector保存類型為T的對象。默認構(gòu)造函數(shù)v1為空vector<T>v2(v1);v2是v1的一個副本vector<T>v3(n,i);v3包含n個值為i的元素vector<T>v4(n);v4包含有值初始化元素的n個副本第40頁/共101頁#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(10,1);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}【例2】創(chuàng)建一個整型向量容器，輸出全部元素值。42第41頁/共101頁(2)下標方式訪問vector元素可用“[

]”運算符訪問vector的元素；【例3】用“[]”運算符為整型向量容器元素賦值，輸出全部元素值。#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v(3);

v[0]=10;v[1]=100;v[2]=-20;for(inti=0;i<3;i++) cout<<v[i]<<",";cout<<endl;return0;}43第42頁/共101頁vector(向量)下標訪問元素注意：下標操作僅能對確知已存的元素進行賦值和讀取操作vector<int>ivec;//emptyvectorfor(intix=0;ix<100;++ix){ivec[ix]=ix;//ivechasnoelement}出錯，向量中尚沒有元素，不能訪問！第43頁/共101頁(3)用迭代器訪問vector元素

如何使相同的算法能用于不同的數(shù)據(jù)結(jié)構(gòu)?

--迭代器(算法與容器的”中間人”)45

容器類迭代器定義方法：

容器類名::iterator變量名;訪問一個迭代器指向的元素：

*迭代器變量名迭代器上可執(zhí)行”++”,指向容器中的下一個元素。如果迭代器到達了容器中的最后一個元素的后面，則迭代器變成past-the-end值。使用一個past-the-end值的迭代器來訪問對象是非法的定義迭代器的關(guān)鍵字第44頁/共101頁46對照理解vector<int>::iteratorxHere=x.Begin();vector<int>::iteratorxEnd=x.End();for(;xHere!=xEnd;xHere++)func_name(*xHere);for(inti=0;i<x.Size();i++)

func_name(x.Get(i));第45頁/共101頁【例4】#include<vector>#include<iostream>usingnamespacestd;intmain(){vector<int>v;v.push_back(1); v.push_back(2);v.push_back(3);v.push_back(4);

vector<int>::const_iteratorit1;

//常量迭代器for(it1=v.begin();it1!=v.end();it1++) cout<<*it1<<",";cout<<endl;

vector<int>::reverse_iteratorit2;

//反向迭代器for(it2=v.rbegin();it2!=v.rend();it2++) cout<<*it2<<",";cout<<endl;47

vector<int>::iteratorit3;

//非常量迭代器

for(it3=v.begin();it3!=v.end();it3++) *it3=100;//重置向量 for(it3=v.begin();it3!=v.end();it3++) cout<<*it3<<","; cout<<endl; return0;}HeadTailbeginrbeginrendend第46頁/共101頁（1）const_iterator：常量迭代器。可以使用這種類型的迭代器來指向一個只讀的值。

（2）

reverse_iterator

：反向迭代器。用來反轉(zhuǎn)遍歷vector的各元素，注意用rbegin()來代替begin()，用rend()代替end()，而此時的“++”操作符會朝向后的方向遍歷。

（3）iterator：隨機迭代器，可任意方向或移動任意個位置訪問。vector的迭代器HeadTailbeginrbeginrendend有const限制的只可讀取元素值，不可修改元素值48第47頁/共101頁

不同的容器，STL提供的迭代器功能各不相同。

vector容器的迭代器：

可使用“+=”、“--”、“++”、“-=”中的任何一種操作符

可使用“<”、“<=”、“>”、“>=”、“==”、“!=”等比較運算符

可隨機訪問容器中的數(shù)據(jù)元素。vector的迭代器49第48頁/共101頁(4)元素插入push_back在尾部追加元素;insert方法可在vector任意位置插入元素.【例5】向整型向量容器追加元素，輸出全部元素值。

#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(10,1);

v.push_back(100);v.psuh_back(-200);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}

尾部追加元素，vector容器自動分配內(nèi)存；可對空的vector追加，也可對已有元素的vector追加.尾部元素追加50第49頁/共101頁vector(向量)--添加ABCDEaaABCDEABCDEABCDEaa在尾端增刪元素具有較佳的性能51第50頁/共101頁指定位置插入元素insert(iteratorit,Tt):對vector容器在指定位置插入新元素【例6】對整型向量容器插入元素，輸出全部元素值。#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(3);vector<int>::iteratorit;v[0]=10;v[1]=100;v[2]=-20;

v.insert(v.begin(),50);//在最前面插入新元素50

v.insert(v.begin()+2,8);//在第2個元素之前插入新元素8

v.insert(v.end(),9);//在末尾插入新元素8for(it=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}

注意：insert方法要求插入的位置，是迭代器位置，而不是下標！52通過迭代器隨機訪問元素第51頁/共101頁(5)元素刪除pop_back刪除向量最后一個元素；erase刪除指定位置或一段區(qū)間的元素;clear方法刪除所有元素.【例7】向量容器刪除元素方法示例。#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v(10);vector<int>::iteratorit;for(inti=0;i<10;i++)v[i]=i;

v.erase(v.begin()+3);//刪除第3個元素，從0開始計數(shù)

for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;

v.erase(v.begin()+1,v.begin()+3);//刪除第1~3個元素for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl<<"向量V中元素數(shù)："<<v.size()<<endl;

v.clear();//清空向量cout<<endl<<"向量V中元素數(shù)："<<v.size()<<endl;return0;}區(qū)間刪除53第52頁/共101頁(6)向量大小的有關(guān)操作向量大小有關(guān)操作列表v.size();返回向量的大小v.max_size();返回向量可容納的最大個數(shù)v.empty();返回向量是否為空v.resize(n);調(diào)整向量的大小，使其可以容納n個元素，如果n<v.size(),則刪除多出來的元素;v.resize(n,t);調(diào)整向量的大小，使其可以容納n個元素，所有新添加的元素初始化為tv.capacity();獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個數(shù)54第53頁/共101頁向量的大小size()和resize()vector<int>vec(10,42);//10int,eachhasvalue42cout<<vec.size()<<endl;vec.resize(15);//adds5elementsofvalue0tothebackofthevectorcout<<vec.size()<<endl;vec.resize(25,-1);//adds10elementsofvalue-1tothebackofthevectorcout<<vec.size()<<endl;新增元素初始化為-155第54頁/共101頁size(),max_size()和capacity()vector<int>v1;cout<<v1.size()<<""<<v1.max_size()<<""<<v1.capacity()<<endl;vector<int>v2(100,-1);cout<<v2.size()<<""<<v2.max_size()<<""<<v2.capacity()<<endl;

size()返回向量中元素的個數(shù)

max_size()返回向量中最多可容納的元素個數(shù)

capacity()獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個數(shù),當元素個數(shù)等于capacity返回的元素個數(shù)時，vector自動分配一段空間用于存儲輸入的新元素012…23……vec.size()vec.capacity()向量的大小systemmemorymax_sizemax_size是系統(tǒng)最大可分配的容量,并非實際分配56第55頁/共101頁(7)在向量上使用算法C++STL很多算法都可以在向量上使用;使用算法需要包含頭文件<algorithm>.【例8】在整型向量容器上使用排序算法。#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){vector<int>v;vector<int>::iteratorit;for(inti=0;i<10;i++)v.push_back(10-i);for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;

sort(v.begin(),v.end());//對向量排序

for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;return0;}57第56頁/共101頁(8)vector作為函數(shù)參數(shù)#include<iostream>#include<vector>usingnamespacestd;voidprint(vector<int>v){for(vector<int>::iteratorit=v.begin();it!=v.end();it++)cout<<*it<<endl;}intmain(){vector<int>vec;vec.push_back(1);vec.push_back(2);vec.push_back(3);

print(vec);return0;}【例9】向量作為函數(shù)參數(shù)示例。58第57頁/共101頁#include<iostream>#include<vector>usingnamespacestd;constintKVectSize=5;intmain(){vector<int>vec;inti;for(i=0;i!=KVectSize;i++){vec.push_back(i);cout<<vec.size()<<","<<vec.capacity()<<endl;}vector<int>*p=newvector<int>(vec);cout<<p->size()<<","<<p->capacity()<<endl;for(i=0;i!=p->size();i++){(*p)[i]=0;}p->clear();cout<<p->size()<<","<<p->capacity()<<endl;deletep;return0;}

【練習】

閱讀程序59第58頁/共101頁【練習】

學生成績標準分的計算方法為：成績/最高成績*100；編寫程序，使用向量作為存儲結(jié)構(gòu)，輸入學生原始成績（以輸入-1為結(jié)束），將學生成績轉(zhuǎn)換為標準分輸出，每行一個。SampleInput769258958772-1

輸入結(jié)束SampleOutput8096.842161.052610091.578975.789560第59頁/共101頁分析：首先須比較所有學生的成績，取得最高分，將學生原始成績除以最高分，然后乘上100。由于程序沒有給出學生人數(shù)，所以采用向量作為數(shù)據(jù)存儲結(jié)構(gòu)，因為向量的元素個數(shù)可以自動的動態(tài)增長。

#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<double>score;//創(chuàng)建向量vector<double>::iteratorit;

doublemax,temp;cin>>max;

score.push_back(max);while(true){cin>>temp;if(temp==-1)break;

score.push_back(temp);if(temp>max) max=temp;}

for(it=score.begin();it!=score.end();it++){

*it/=max;cout<<*it<<endl;}

return0;}61第60頁/共101頁對比代碼：

#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<double>score;//創(chuàng)建向量

doublemax,temp;inti;cin>>max;

score.push_back(max);for(i=1;true;i++){cin>>temp;if(temp==-1)break;

score.push_back(temp);if(temp>max) max=temp;}

max/=100;for(i=0;i<score.size();i++){

score[i]/=max;cout<<score[i]<<endl;}return0;}

未充分使用向量容器上的迭代器來訪問元素，仍自己管理下標，存在不安全隱患！62第61頁/共101頁【練習】

ImageTransformation圖像是以像素矩陣存儲在計算機中。在rgb三色系統(tǒng)中，一個像素的顏色以“rgb”格式表示；r,g,b：0~255;然而，有時候我們需要灰度圖像而不是彩色圖像。把RGB圖像轉(zhuǎn)換為灰度圖像的一種簡單方法為：把一個像素的r,g,b值都設(shè)置為一個相同的值（即(r+g+b)/3，這里假定(r+g+b)總能被3整除）。編寫程序測試這種方法的有效性。63第62頁/共101頁輸入：包含多個測試樣例,每個測試樣例以2個整數(shù)N和M(1≤N,M≤100)打頭，表示圖像的高度和寬度，接下來是3個N*M矩陣，分別代表每個像素的r,g,b值。當一行上的N和M都為0時，表示輸入結(jié)束，這行數(shù)據(jù)不需處理。輸出：對每個測試樣例，先輸出“Case#:”，“#”是測試樣例序號，從1開始。然后輸出一個N*M矩陣，它描述了灰度圖像中每個像素的灰度值。應當有N行，每行有M個整數(shù)，其間用逗號隔開。

SampleInput22146925710368112301234201234301234400輸入結(jié)束SampleOutputCase1:2,57,10Case2:0,1,23,4,364第63頁/共101頁【分析】本題英文原題比較長，理解題意比較難。每個測試樣例的數(shù)據(jù)由兩部分組成：第一行是矩陣大?。∟,M）;第二部分是三個N*M矩陣，共3*N行數(shù)據(jù)含義：2214692571036811(1,2,3)(4,5,6)(6,7,8)(9,10,11)提示：問題中涉及r、g、b三類數(shù)據(jù)的存儲和計算，而每個測試樣例包含的像素數(shù)是N*M個，每個樣例的N、M可能都不一樣；若自行管理數(shù)組，涉及動態(tài)存儲管理，較為復雜；可考慮建立三個向量r、g、b，分別存儲像素點的r,g,b值；利用向量的方法可方便的處理元素。第64頁/共101頁2、list列表容器66list是一個雙向鏈表可以雙向（從頭到尾，從尾到頭）訪問鏈表中的結(jié)點；結(jié)點可以是任意數(shù)據(jù)類型；鏈表中結(jié)點的訪問常通過迭代器進行;不可隨機訪問。

第65頁/共101頁67list數(shù)據(jù)結(jié)構(gòu)分析a1a2an頭結(jié)點list每個結(jié)點有三個域；存儲可以不連續(xù)；迭代器只能通過“++”或”--”移動到目標元素上;每個元素還有兩個指針的額外空間開銷.第66頁/共101頁(1)創(chuàng)建list對象四種方式:創(chuàng)建空鏈表：list<類型T>對象名；例如：list<int>table;//創(chuàng)建整型鏈表table創(chuàng)建具有n個元素的鏈表：list<類型T>對象名(n)；例如：list<int>table(10);//創(chuàng)建整型鏈表table

,10個元素創(chuàng)建具有n個元素的鏈表，指定元素初始值：list<類型T>對象名(n,初值)；例如：list<int>table(10,9);

//創(chuàng)建整型鏈表table

,10個元素,每個元素值均為9由已有l(wèi)ist容器創(chuàng)建:

list<類型T>對象名(已有對象名)；例如：list<int>t2(t1);//創(chuàng)建整型鏈表t1的副本t268第67頁/共101頁創(chuàng)建list鏈表幾種初始化list對象的方式list<T>t1;list保存類型為T的對象。默認構(gòu)造函數(shù)t1為空list<T>t2(t1);t2是t1的一個副本list<T>t3(n,i);t3包含n個值為i的元素list<T>t4(n);t4包含有值初始化元素的n個結(jié)點69第68頁/共101頁#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>t1(5);//創(chuàng)建鏈表

list<int>t3(3,9);

list<int>::iteratorit;t1.push_back(2);t1.push_front(3);

list<int>t2(t1);//創(chuàng)建鏈表

for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;for(it=t2.begin();it!=t2.end();it++) cout<<*it<<",";cout<<endl;for(it=t3.begin();it!=t3.end();it++) cout<<*it<<",";cout<<endl;return0;}【例10】創(chuàng)建整型鏈表，輸出全部元素值。70第69頁/共101頁(2)元素插入push_back在尾部插入元素;push_front在頭部插入元素;insert向迭代器位置處插入新元素。71三個方法：注意：插入元素時，鏈表自動擴展;不可自行修改迭代器。insert(iteratorit,Tt):對list容器在指定位置插入新元素第70頁/共101頁【例11】用insert向整型鏈表中插入元素，輸出全部元素值。#include<iostream>#include<list>usingnamespacestd;intmain(){

list<int>t1(5);//創(chuàng)建鏈表

list<int>::iteratorit;

t1.push_back(2);t1.push_front(3);it=t1.begin();

it++;it++;

t1.insert(it,100);for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;return0;}注意：鏈表的迭代器只能順序逐位移動，不可+n72第71頁/共101頁(3)元素刪除remove刪除鏈表中值相同的元素；pop_front刪除鏈表首元素；pop_back刪除鏈表尾元素；erase刪除迭代器位置上的元素;clear方法刪除所有元素.73五個方法：第72頁/共101頁remove刪除鏈表中相同值元素remove(Telem):刪除鏈表中所有與elem值相等的元素【例12】list的remove方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){

list<int>t1;//創(chuàng)建鏈表

t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(list<int>::iteratorit=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;

t1.remove(13);//刪除表中所有值為13的元素

for(list<int>::iteratorit=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;return0;}74第73頁/共101頁刪除鏈表首、尾元素pop_front()、pop_back()刪除鏈表中首、尾元素【例13】list的pop_front()、pop_back()方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){

list<int>t1;//創(chuàng)建鏈表

t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(list<int>::iteratorit=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;

t1.pop_front();t1.pop_back();//刪除表中首、尾元素

for(list<int>::iteratorit=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;return0;}75第74頁/共101頁erase刪除指定元素erase(iteratorit)刪除鏈表中迭代器it所指位置處的元素【例14】list的erase方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>t1;//創(chuàng)建鏈表

list<int>::iteratorit;

t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;it=t1.begin();it++;

t1.erase(it);//刪除it所指位置的元素

for(it=t1.begin();it!=t1.end();it++)cout<<*it<<",";cout<<endl;return0;}

注意迭代器當前位置

思考：若list鏈表為空，執(zhí)行刪除操作會產(chǎn)生何結(jié)果？76第75頁/共101頁(4)遍歷鏈表iterator前向迭代器—前向迭代reverse_iterator反向迭代器—反向迭代【例15】list的反向迭代器reverse_iterator示例。#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>t1;//創(chuàng)建鏈表

list<int>::iteratorit1;

list<int>::reverse_iteratorit2;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it1=t1.begin();it1!=t1.end();it1++)cout<<*it1<<",";cout<<endl;for(it2=t1.rbegin();it2!=t1.rend();it2++)cout<<*it2<<",";cout<<endl;return0;}反向遍歷77前向遍歷第76頁/共101頁(5)元素排序list的sort方法—對鏈表元素排序【例16】list的sort方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){

list<int>t1;//創(chuàng)建鏈表

list<int>::iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;

t1.sort();for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;return0;}78第77頁/共101頁(6)剔除連續(xù)重復元素list的unique方法—剔除鏈表中連續(xù)的重復元素【例17】list的unique方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>t1;//創(chuàng)建鏈表

list<int>::iteratorit;t1.push_back(20);t1.push_front(13);

t1.push_back(100);t1.push_back(100);

t1.push_back(100);t1.push_back(100);

t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;

t1.sort();for(it=t1.begin();it!=t1.end();it++) cout<<*it<<",";cout<<endl;return0;}79第78頁/共101頁(7)重組列表list的splice方法—拼接方法,用來重組列表voidsplice(iteratorit,list&x);//將列表x中的元素插入到當前列表中it之前，刪除x中的元素，使之為空；注意x與當前列表不能是同一個voidsplice(iteratorit,list&x,iteratorfirst);//將first所指向的元素從列表x中移出，并插入到當前列表中it之前；x與當前列表可以是同一個；如果it==first或it=++first，則此函數(shù)什么也不做voidsplice(iteratorit,list&x,iteratorfirst,,iteratorlast);//將范圍[fast,last]中的元素從列表x中移出，并插入到當前列表中it之前；x與當前列表可以是同一個，當這時范圍[first,last]不能包含it所指的元素80splice方法使序列便于重組，無需移動大量元素第79頁/共101頁【例18】list的unique方法示例。#include<iostream>#include<list>usingnamespacestd;intmain(){list<int>t1;//創(chuàng)建鏈表1

list<int>t2;//創(chuàng)建鏈表2list<int>::iteratorit1,it2,it3;

t1.push_back(2