第10章 泛型程序設(shè)計(jì)與C++標(biāo)準(zhǔn)模板庫(kù)

第十章

泛型程序設(shè)計(jì)

與C++標(biāo)準(zhǔn)模板庫(kù)清華大學(xué)鄭莉目錄10.1泛型程序設(shè)計(jì)及STL的結(jié)構(gòu)10.2迭代器10.3容器的基本功能與分類10.4順序容器10.5關(guān)聯(lián)容器10.6函數(shù)對(duì)象10.7算法10.8綜合實(shí)例——對(duì)個(gè)人銀行賬戶管理程序的改進(jìn)10.9深度探索10.10小結(jié)210.1.1泛型程序設(shè)計(jì)的基本概念編寫不依賴于具體數(shù)據(jù)類型的程序?qū)⑺惴◤奶囟ǖ臄?shù)據(jù)結(jié)構(gòu)中抽象出來(lái)，成為通用的C++的模板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ)幾個(gè)術(shù)語(yǔ)概念（concept）：用來(lái)界定具備一定功能的數(shù)據(jù)類型，如“支持‘<’運(yùn)算符”的數(shù)據(jù)類型構(gòu)成Comparable這一概念；模型（model）：符合一個(gè)概念的數(shù)據(jù)類型稱為該概念的模型，如int型是Comparable概念的模型。為概念賦予一個(gè)名稱，并使用該名稱作為模板參數(shù)名例如，我們將用這樣的方式表示insertionSort這樣一個(gè)函數(shù)模板的原型：template<classSortable>voidinsertionSort(Sortablea[],intn);事實(shí)上，很多STL的實(shí)現(xiàn)代碼就是使用概念來(lái)命名模板參數(shù)的。310.1泛型程序設(shè)計(jì)及STL的結(jié)構(gòu)10.1.2STL簡(jiǎn)介標(biāo)準(zhǔn)模板庫(kù)（StandardTemplateLibrary，簡(jiǎn)稱STL）提供了一些非常常用的數(shù)據(jù)結(jié)構(gòu)和算法STL程序?qū)嵗ɡ?0-1）：410.1泛型程序設(shè)計(jì)及STL的結(jié)構(gòu)//包含的頭文件略去……usingnamespacestd;intmain(){ constintN=5; vector<int>s(N);

for(inti=0;i<N;i++) cin>>s[i];

transform(s.begin(),s.end(),

ostream_iterator<int>(cout,""),negate<int>()); cout<<endl; return0;}容器迭代器函數(shù)對(duì)象算法10.1.2STL簡(jiǎn)介transform算法的一種實(shí)現(xiàn)：template<classInputIterator,classOutputIterator,classUnaryFunction>OutputIteratortransform(InputIteratorfirst,InputIteratorlast,OutputIteratorresult,UnaryFunctionop){ for(;first!=last;++first,++result) *result=op(*first); returnresult;}5STL的組成部分6STL是泛型程序設(shè)計(jì)的一個(gè)范例

容器（container）迭代器（iterator）算法（algorithms）函數(shù)對(duì)象（functionobject）容器(container)算法(algorithm)容器(container)迭代器(iterator)函數(shù)對(duì)象(function

object)迭代器(iterator)10.1泛型程序設(shè)計(jì)及STL的結(jié)構(gòu)——10.1.2STL簡(jiǎn)介

10.2.1輸入流迭代器和輸出流迭代器輸入流迭代器istream_iterator<T>以輸入流（如cin）為參數(shù)構(gòu)造可用*(p++)獲得下一個(gè)輸入的元素輸出流迭代器ostream_iterator<T>構(gòu)造時(shí)需要提供輸出流（如cout）可用(*p++)=x將x輸出到輸出流二者都屬于適配器適配器是用來(lái)為已有對(duì)象提供新的接口的對(duì)象輸入流適配器和輸出流適配器為流對(duì)象提供了迭代器的接口710.2迭代器例10-2從標(biāo)準(zhǔn)輸入讀入幾個(gè)實(shí)數(shù)，分別將它們的平方輸出//10_2.cpp#include<iterator>#include<iostream>#include<algorithm>usingnamespacestd;

//求平方的函數(shù)doublesquare(doublex){ returnx*x;}

intmain(){ //從標(biāo)準(zhǔn)輸入讀入若干個(gè)實(shí)數(shù)，分別將它們的平方輸出

transform(istream_iterator<double>(cin), istream_iterator<double>(), ostream_iterator<double>(cout,"\t"),square);cout<<endl;return0;}810.2迭代器——10.2.1輸入流迭代器和輸出流迭代器10.2.2迭代器的分類910.2迭代器輸入迭代器

(InputIterator)輸出迭代器

(OutputIterator)前向迭代器(ForwardIterator)雙向迭代器(BidirectionalIterator)隨機(jī)訪問(wèn)迭代器(RandomAccessIterator)迭代器支持的操作迭代器是泛化的指針，提供了類似指針的操作（諸如++、*、->運(yùn)算符）輸入迭代器可以用來(lái)從序列中讀取數(shù)據(jù)，如輸入流迭代器輸出迭代器允許向序列中寫入數(shù)據(jù)，如輸出流迭代器前向迭代器既是輸入迭代器又是輸出迭代器，并且可以對(duì)序列進(jìn)行單向的遍歷雙向迭代器與前向迭代器相似，但是在兩個(gè)方向上都可以對(duì)數(shù)據(jù)遍歷隨機(jī)訪問(wèn)迭代器也是雙向迭代器，但能夠在序列中的任意兩個(gè)位置之間進(jìn)行跳轉(zhuǎn)，如指針、使用vector的begin()、end()函數(shù)得到的迭代器1010.2迭代器——10.2.2迭代器的分類10.2.3迭代器的區(qū)間兩個(gè)迭代器表示一個(gè)區(qū)間：[p1,p2)STL算法常以迭代器的區(qū)間作為輸入，傳遞輸入數(shù)據(jù)合法的區(qū)間p1經(jīng)過(guò)n次(n>0)自增(++)操作后滿足p1==p2區(qū)間包含p1，但不包含p21110.2迭代器例10-3綜合運(yùn)用幾種迭代器的示例//10_3.cpp#include<algorithm>#include<iterator>#include<vector>#include<iostream>usingnamespacestd;

//將來(lái)自輸入迭代器p的n個(gè)T類型的數(shù)值排序，將結(jié)果通過(guò)輸出迭代器result輸出template<classT,classInputIterator,classOutputIterator>voidmySort(InputIteratorfirst,InputIteratorlast,OutputIteratorresult){ //通過(guò)輸入迭代器p將輸入數(shù)據(jù)存入向量容器s中

vector<T>s; for(;first!=last;++first) s.push_back(*first); sort(s.begin(),s.end());//對(duì)s進(jìn)行排序，sort函數(shù)的參數(shù)必須是隨機(jī)訪問(wèn)迭代器

copy(s.begin(),s.end(),result); //將s序列通過(guò)輸出迭代器輸出}1210.2迭代器——10.2.3迭代器的區(qū)間例10-3（續(xù)）intmain(){ //將s數(shù)組的內(nèi)容排序后輸出

doublea[5]={1.2,2.4,0.8,3.3,3.2}; mySort<double>(a,a+5,ostream_iterator<double>(cout,"")); cout<<endl; //從標(biāo)準(zhǔn)輸入讀入若干個(gè)整數(shù)，將排序后的結(jié)果輸出

mySort<int>(istream_iterator<int>(cin),istream_iterator<int>(),ostream_iterator<int>(cout,"")); cout<<endl; return0;}1310.2迭代器——10.2.3迭代器的區(qū)間運(yùn)行結(jié)果：0.81.22.43.23.32-458-136-5-5-4-12356810.2.4迭代器的輔助函數(shù)advance(p,n)對(duì)p執(zhí)行n次自增操作distance(first,last)計(jì)算兩個(gè)迭代器first和last的距離，即對(duì)first執(zhí)行多少次“++”操作后能夠使得first==last1410.2迭代器10.3容器的基本功能與分類容器類是容納、包含一組元素或元素集合的對(duì)象。七種基本容器：向量（vector）雙端隊(duì)列（deque）列表（list）集合（set）多重集合（multiset）映射（map）多重映射（multimap）1510.3容器的基本功能與分類（續(xù)）16容器(Container)隨機(jī)訪問(wèn)容器

(RandomAccessContainer)可逆容器(ReversibleContainer)容器(Container)順序容器(Sequence)關(guān)聯(lián)容器

(AssociativeContainer)vectordequelistmultisetmultimapsetmap容器的通用功能容器的通用功能用默認(rèn)構(gòu)造函數(shù)構(gòu)造空容器支持關(guān)系運(yùn)算符：==、!=、<、<=、>、>=begin()、end()：獲得容器首、尾迭代器clear()：將容器清空empty()：判斷容器是否為空size()：得到容器元素個(gè)數(shù)s1.swap(s2)：將s1和s2兩容器內(nèi)容交換相關(guān)數(shù)據(jù)類型（S表示容器類型）S::iterator：指向容器元素的迭代器類型S::const_iterator：常迭代器類型1710.3容器的基本功能與分類可逆容器、隨機(jī)訪問(wèn)容器可逆容器S::reverse_iterator：逆向迭代器類型S::const_reverse_iterator：逆向常迭代器類型rbegin()：指向容器尾的逆向迭代器rend()：指向容器首的逆向迭代器隨機(jī)訪問(wèn)容器s[n]：獲得容器s的第n個(gè)元素1810.3容器的基本功能與分類10.4.1順序容器的基本功能順序容器的接口賦值assign插入函數(shù)insert，push_front（只對(duì)list和deque），push_back刪除函數(shù)erase，clear，pop_front（只對(duì)list和deque）

，pop_back其他順序容器訪問(wèn)函數(shù)front，back改變大小resize1910.4順序容器例10-4順序容器的基本操作//10_4.cpp，包含的頭文件略去

//輸出指定的整型順序容器的元素template<classT>voidprintContainer(constchar*msg,constT&s){ cout<<msg<<":"; copy(s.begin(),s.end(),ostream_iterator<int>(cout,"")); cout<<endl;}

intmain(){ //從標(biāo)準(zhǔn)輸入讀入10個(gè)整數(shù)，將它們分別從s的頭部加入

deque<int>s; for(inti=0;i<10;i++){ intx; cin>>x; s.push_front(x); }2010.4順序容器——10.4.1順序容器的基本功能例10-4（續(xù)） printContainer("dequeatfirst",s); //用s容器的內(nèi)容的逆序構(gòu)造列表容器l list<int>l(s.rbegin(),s.rend()); printContainer("listatfirst",l); //將列表容器l的每相鄰兩個(gè)容器順序顛倒

list<int>::iteratoriter=l.begin(); while(iter!=l.end()){ intv=*iter; iter=l.erase(iter); l.insert(++iter,v); } printContainer("listatlast",l); //用列表容器l的內(nèi)容給s賦值，將s輸出

s.assign(l.begin(),l.end()); printContainer("dequeatlast",s); return0;}2110.4順序容器——10.4.1順序容器的基本功能例10-4（續(xù)）運(yùn)行結(jié)果如下：0986432154dequeatfirst:4512346890listatfirst:0986432154listatlast:9068341245dequeatlast:90683412452210.4順序容器——10.4.1順序容器的基本功能10.4.2三種順序容器的特性

——向量（Vector）特點(diǎn)一個(gè)可以擴(kuò)展的動(dòng)態(tài)數(shù)組隨機(jī)訪問(wèn)、在尾部插入或刪除元素快在中間或頭部插入或刪除元素慢向量的容量容量(capacity)：實(shí)際分配空間的大小s.capacity()：返回當(dāng)前容量s.reserve(n)：若容量小于n，則對(duì)s進(jìn)行擴(kuò)展，使其容量至少為n2310.4順序容器雙端隊(duì)列（deque）特點(diǎn)在兩端插入或刪除元素快在中間插入或刪除元素慢隨機(jī)訪問(wèn)較快，但比向量容器慢2410.4順序容器——10.4.2三種順序容器的特性例10-5奇偶排序先按照從大到小順序輸出奇數(shù)，再按照從小到大順序輸出偶數(shù)。2510.4順序容器——10.4.2三種順序容器的特性//頭部分省略intmain(){istream_iterator<int>i1(cin),i2; //建立一對(duì)兒輸入流迭代器vector<int>s1(i1,i2); //通過(guò)輸入流迭代器從標(biāo)準(zhǔn)輸入流中輸入數(shù)據(jù)sort(s1.begin(),s1.end()); //將輸入的整數(shù)排序deque<int>s2;//以下循環(huán)遍歷s1for(vector<int>::iteratoriter=s1.begin();iter!=s1.end();++iter){ if(*iter%2==0) //偶數(shù)放到s2尾部

s2.push_back(*iter); else //奇數(shù)放到s2首部

s2.push_front(*iter);}//將s2的結(jié)果輸出copy(s2.begin(),s2.end(),ostream_iterator<int>(cout,""));cout<<endl;return0;}列表(list)特點(diǎn)在任意位置插入和刪除元素都很快不支持隨機(jī)訪問(wèn)接合(splice)操作s1.splice(p,s2,q1,q2)：將s2中[q1,q2)移動(dòng)到s1中p所指向元素之前2610.4順序容器——10.4.2三種順序容器的特性例10-6列表容器的splice操作//頭部分省略intmain(){ stringnames1[]={"Alice","Helen","Lucy","Susan"}; stringnames2[]={"Bob","David","Levin","Mike"}; list<string>s1(names1,names1+4);//用names1數(shù)組的內(nèi)容構(gòu)造列表s1 list<string>s2(names2,names2+4);//用names2數(shù)組的內(nèi)容構(gòu)造列表s2

//將s1的第一個(gè)元素放到s2的最后

s2.splice(s2.end(),s1,s1.begin()); list<string>::iteratoriter1=s1.begin();//iter1指向s1首

advance(iter1,2);//iter1前進(jìn)2個(gè)元素，它將指向s1第3個(gè)元素

list<string>::iteratoriter2=s2.begin();//iter2指向s2首

++iter2;//iter2前進(jìn)1個(gè)元素，它將指向s2第2個(gè)元素

2710.4順序容器——10.4.2三種順序容器的特性例10-6（續(xù)）28list<string>::iteratoriter3=iter2;//用iter2初始化iter3advance(iter3,2);//iter3前進(jìn)2個(gè)元素，它將指向s2第4個(gè)元素//將[iter2,iter3)范圍內(nèi)的結(jié)點(diǎn)接到s1中iter1指向的結(jié)點(diǎn)前s1.splice(iter1,s2,iter2,iter3);

//分別將s1和s2輸出copy(s1.begin(),s1.end(),ostream_iterator<string>(cout,""));cout<<endl;copy(s2.begin(),s2.end(),ostream_iterator<string>(cout,""));cout<<endl;return0;}10.4順序容器——10.4.2三種順序容器的特性運(yùn)行結(jié)果：HelenLucyDavidLevinSusanBobMikeAlice三種順序容器的比較STL所提供的三種順序容器各有所長(zhǎng)也各有所短，我們?cè)诰帉懗绦驎r(shí)應(yīng)當(dāng)根據(jù)我們對(duì)容器所需要執(zhí)行的操作來(lái)決定選擇哪一種容器。如果需要執(zhí)行大量的隨機(jī)訪問(wèn)操作，而且當(dāng)擴(kuò)展容器時(shí)只需要向容器尾部加入新的元素，就應(yīng)當(dāng)選擇向量容器vector；如果需要少量的隨機(jī)訪問(wèn)操作，需要在容器兩端插入或刪除元素，則應(yīng)當(dāng)選擇雙端隊(duì)列容器deque；、如果不需要對(duì)容器進(jìn)行隨機(jī)訪問(wèn)，但是需要在中間位置插入或者刪除元素，就應(yīng)當(dāng)選擇列表容器list。2910.4順序容器——10.4.2三種順序容器的特性10.4.3順序容器的插入迭代器插入迭代器用于向容器頭部、尾部或中間指定位置插入元素的迭代器包括前插迭代器（front_inserter）、后插迭代器（back_insrter）和任意位置插入迭代器（inserter）例：list<int>s;back_inserteriter(s);*(iter++)=5;//通過(guò)iter把5插入s末尾3010.4順序容器10.4.4順序容器的適配器以順序容器為基礎(chǔ)構(gòu)建一些常用數(shù)據(jù)結(jié)構(gòu)棧(stack)：最先壓入的元素最后被彈出隊(duì)列(queue)：最先壓入的元素最先被彈出優(yōu)先級(jí)隊(duì)列(priority_queue)：最“大”的元素最先被彈出3110.4順序容器例10-7利用棧反向輸出單詞//10_7.cpp，省略頭部分intmain(){ stack<char>s; stringstr; cin>>str; //從鍵盤輸入一個(gè)字符串

//將字符串的每個(gè)元素順序壓入棧中

for(string::iteratoriter=str.begin();iter!=str.end();++iter) s.push(*iter); //將棧中的元素順序彈出并輸出

while(!s.empty()){ cout<<s.top(); s.pop(); } cout<<endl; return0;}3210.4順序容器——10.4.4順序容器的適配器運(yùn)行結(jié)果如下：congratulationssnoitalutargnoc優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列也像棧和隊(duì)列一樣支持元素的壓入和彈出，但元素彈出的順序與元素的大小有關(guān)，每次彈出的總是容器中最“大”的一個(gè)元素。template<classT,classSequence=vector<T>>classpriority_queue;例10-8細(xì)胞分裂模擬一種細(xì)胞在誕生（即上次分裂）后會(huì)在500到2000秒內(nèi)分裂為兩個(gè)細(xì)胞，每個(gè)細(xì)胞又按照同樣的規(guī)律繼續(xù)分裂。3310.4順序容器——10.4.4順序容器的適配器//10.8.cpp,頭部分省略constintSPLIT_TIME_MIN=500;//細(xì)胞分裂最短時(shí)間constintSPLIT_TIME_MAX=2000;//細(xì)胞分裂最長(zhǎng)時(shí)間

classCell;priority_queue<Cell>cellQueue;

classCell{ //細(xì)胞類private: staticintcount; //細(xì)胞總數(shù)

intid; //當(dāng)前細(xì)胞編號(hào)

inttime; //細(xì)胞分裂時(shí)間public: Cell(intbirth):id(count++){ //birth為細(xì)胞誕生時(shí)間

//初始化，確定細(xì)胞分裂時(shí)間

time=birth+(rand()%(SPLIT_TIME_MAX-SPLIT_TIME_MIN))+SPLIT_TIME_MIN; } intgetId()const{returnid;} //得到細(xì)胞編號(hào)

intgetSplitTime()const{returntime;} //得到細(xì)胞分裂時(shí)間

booloperator<(constCell&s)const{returntime>s.time;}//定義“<”

34例10-8（續(xù)）10.4順序容器——10.4.4順序容器的適配器//細(xì)胞分裂

voidsplit(){ Cellchild1(time),child2(time); //建立兩個(gè)子細(xì)胞

cout<<time<<"s:Cell#"<<id<<"splitsto#" <<child1.getId()<<"and#"<<child2.getId()<<endl; cellQueue.push(child1); //將第一個(gè)子細(xì)胞壓入優(yōu)先級(jí)隊(duì)列

cellQueue.push(child2); //將第二個(gè)子細(xì)胞壓入優(yōu)先級(jí)隊(duì)列

}};intCell::count=0;

intmain(){ srand(static_cast<unsigned>(time(0))); intt; //模擬時(shí)間長(zhǎng)度

cout<<"Simulationtime:"; cin>>t; cellQueue.push(Cell(0)); //將第一個(gè)細(xì)胞壓入優(yōu)先級(jí)隊(duì)列

while(cellQueue.top().getSplitTime()<=t){ cellQueue.top().split(); //模擬下一個(gè)細(xì)胞的分裂

cellQueue.pop(); //將剛剛分裂的細(xì)胞彈出

} return0;}35例10-8（續(xù)）10.4順序容器——10.4.4順序容器的適配器例10-8（續(xù)）運(yùn)行結(jié)果如下：Simulationtime:5000971s:Cell#0splitsto#1and#21719s:Cell#1splitsto#3and#41956s:Cell#2splitsto#5and#62845s:Cell#6splitsto#7and#83551s:Cell#3splitsto#9and#103640s:Cell#4splitsto#11and#123919s:Cell#5splitsto#13and#144162s:Cell#10splitsto#15and#164197s:Cell#8splitsto#17and#184317s:Cell#7splitsto#19and#204686s:Cell#13splitsto#21and#224809s:Cell#12splitsto#23and#244818s:Cell#17splitsto#25and#263610.4順序容器——10.4.4順序容器的適配器10.5.1關(guān)聯(lián)容器分類和的基本功能關(guān)聯(lián)容器的特點(diǎn)每個(gè)關(guān)聯(lián)容器都有一個(gè)鍵(key)可以根據(jù)鍵高效地查找元素接口插入：insert刪除：erase查找：find定界：lower_bound、upper_bound、equal_range計(jì)數(shù)：count3710.5關(guān)聯(lián)容器關(guān)聯(lián)容器概念圖3810.5關(guān)聯(lián)容器——10.5.1關(guān)聯(lián)容器的分類和基本功能關(guān)聯(lián)容器(AssociativeContainer)單重關(guān)聯(lián)容器(UniqueAsso-

ciativeContainer)多重關(guān)聯(lián)容器(MultipleAsso-

ciativeContainer)關(guān)聯(lián)容器(AssociativeContainer)簡(jiǎn)單關(guān)聯(lián)容器(SimpleAsso-

ciativeContainer)二元關(guān)聯(lián)容器(PairAsso-

ciativeContainer)multisetmultimapsetmap四種關(guān)聯(lián)容器單重關(guān)聯(lián)容器(set和map)鍵值是唯一的，一個(gè)鍵值只能對(duì)應(yīng)一個(gè)元素多重關(guān)聯(lián)容器(multiset和multimap)鍵值是不唯一的，一個(gè)鍵值可以對(duì)應(yīng)多個(gè)元素簡(jiǎn)單關(guān)聯(lián)容器(set和multiset)容器只有一個(gè)類型參數(shù)，如set<K>、multiset<K>，表示鍵類型容器的元素就是鍵本身二元關(guān)聯(lián)容器(map和multimap)容器有兩個(gè)類型參數(shù)，如map<K,V>、multimap<K,V>，分別表示鍵和附加數(shù)據(jù)的類型容器的元素類型是pair<K,V>，即由鍵類型和元素類型復(fù)合而成的二元組3910.5關(guān)聯(lián)容器——10.5.1關(guān)聯(lián)容器的分類和基本功能10.5.2集合（set）集合用來(lái)存儲(chǔ)一組無(wú)重復(fù)的元素。由于集合的元素本身是有序的，可以高效地查找指定元素，也可以方便地得到指定大小范圍的元素在容器中所處的區(qū)間。例10-9輸入一串實(shí)數(shù)，將重復(fù)的去掉，取最大和最小者的中值，分別輸出小于等于此中值和大于等于此中值的實(shí)數(shù)4010.5關(guān)聯(lián)容器

//10_9.cpp,頭部分省略intmain(){ set<double>s; while(true){ doublev; cin>>v; if(v==0)break; //輸入0表示結(jié)束

pair<set<double>::iterator,bool>r=s.insert(v);//嘗試將v插入

if(!r.second) //如果v已存在，輸出提示信息

cout<<v<<"isduplicated"<<endl; } set<double>::iteratoriter1=s.begin(); //得到第一個(gè)元素的迭代器

set<double>::iteratoriter2=s.end(); //得到末尾的迭代器

doublemedium=(*iter1+*(--iter2))/2; //得到最小和最大元素的中值

//輸出小于或等于中值的元素

cout<<"<=medium:" copy(s.begin(),s.upper_bound(medium),ostream_iterator<double>(cout,"")); cout<<endl; //輸出大于或等于中值的元素

cout<<">=medium:"; copy(s.lower_bound(medium),s.end(),ostream_iterator<double>(cout,"")); cout<<endl; return0;}4110.5關(guān)聯(lián)容器——10.5.2集合（set）

例10-9（續(xù)）例10-9（續(xù)）運(yùn)行結(jié)果如下：12.553.55792.505isduplicated2.5isduplicated<=medium:12.53.55>=medium:5794210.5關(guān)聯(lián)容器——10.5.2集合（set）

10.5.3映射（map）映射與集合同屬于單重關(guān)聯(lián)容器，它們的主要區(qū)別在于，集合的元素類型是鍵本身，而映射的元素類型是由鍵和附加數(shù)據(jù)所構(gòu)成的二元組。在集合中按照鍵查找一個(gè)元素時(shí)，一般只是用來(lái)確定這個(gè)元素是否存在，而在映射中按照鍵查找一個(gè)元素時(shí)，除了能確定它的存在性外，還可以得到相應(yīng)的附加數(shù)據(jù)。例10-10有五門課程，每門都有相應(yīng)學(xué)分，從中選擇三門，輸出學(xué)分總和4310.5關(guān)聯(lián)容器

//10_10.cpp,頭部分省略intmain(){ map<string,int>courses; //將課程信息插入courses映射中

courses.insert(make_pair("CSAPP",3)); courses.insert(make_pair("C++",2)); courses.insert(make_pair("CSARCH",4)); courses.insert(make_pair("COMPILER",4)); courses.insert(make_pair("OS",5)); intn=3; //剩下的可選次數(shù)

intsum=0; //學(xué)分總和

while(n>0){ stringname; cin>>name; //輸入課程名稱

map<string,int>::iteratoriter=courses.find(name);//查找課程

if(iter==courses.end()){ //判斷是否找到

cout<<name<<"isnotavailable"<<endl; }else{ sum+=iter->second; //累加學(xué)分

courses.erase(iter); //將剛選過(guò)的課程從映射中刪除

n--; } } cout<<"Totalcredit:"<<sum<<endl; //輸出總學(xué)分

return0;}4410.5關(guān)聯(lián)容器——10.5.3映射（map）

例10-10（續(xù)）例10-10（續(xù)）運(yùn)行結(jié)果如下：C++COMPILERC++C++isnotavailableCSAPPTotalcredit:94510.5關(guān)聯(lián)容器——10.5.3映射（map）

例10-11統(tǒng)計(jì)一句話中每個(gè)字母出現(xiàn)的次數(shù)//10_11.cpp,頭部分省略intmain(){ map<char,int>s; //用來(lái)存儲(chǔ)字母出現(xiàn)次數(shù)的映射

charc; //存儲(chǔ)輸入字符

do{ cin>>c; //輸入下一個(gè)字符

if(isalpha(c)){ //判斷是否是字母

c=tolower(c); //將字母轉(zhuǎn)換為小寫

s[c]++; //將該字母的出現(xiàn)頻率加1 } }while(c!='.'); //碰到“.”則結(jié)束輸入

//輸出每個(gè)字母出現(xiàn)次數(shù)

for(map<char,int>::iteratoriter=s.begin();iter!=s.end();++iter) cout<<iter->first<<""<<iter->second<<""; cout<<endl; return0;}4610.5關(guān)聯(lián)容器——10.5.3映射（map）

10.5.4多重集合（multiset）與多重映射（multimap）多重集合是允許有重復(fù)元素的集合，多重映射是允許一個(gè)鍵對(duì)應(yīng)多個(gè)附加數(shù)據(jù)的映射。多重集合與集合、多重映射與映射的用法差不多，只在幾個(gè)成員函數(shù)上有細(xì)微差異，其差異主要表現(xiàn)在去除了鍵必須唯一的限制。例10-12上課時(shí)間查詢4710.5關(guān)聯(lián)容器

//10_12.cpp#include<iostream>#include<map>#include<utility>#include<string>usingnamespacestd;intmain(){ multimap<string,string>courses; typedefmultimap<string,string>::iteratorCourseIter;

//將課程上課時(shí)間插入courses映射中

courses.insert(make_pair("C++","2-6")); courses.insert(make_pair("COMPILER","3-1")); courses.insert(make_pair("COMPILER","5-2")); courses.insert(make_pair("OS","1-2")); courses.insert(make_pair("OS","4-1")); courses.insert(make_pair("OS","5-5")); //輸入一個(gè)課程名，直到找到該課程為止，記下每周上課次數(shù)

stringname; intcount;

4810.5關(guān)聯(lián)容器——10.5.4多重集合與多重映射例10-12（續(xù)） do{ cin>>name; count=courses.count(name); if(count==0) cout<<"Cannotfindthiscourse!"<<endl; }while(count==0); //輸出每周上課次數(shù)和上課時(shí)間

cout<<count<<"lesson(s)perweek:"; pair<CourseIter,CourseIter>range=courses.equal_range(name); for(CourseIteriter=range.first;iter!=range.second;++iter) cout<<iter->second<<""; cout<<endl;

return0;}4910.5關(guān)聯(lián)容器——10.5.4多重集合與多重映射例10-12（續(xù)）運(yùn)行結(jié)果如下：JAVACannotfindthiscourse!OS3lesson(s)perweek:1-24-15-510.6.1函數(shù)對(duì)象函數(shù)對(duì)象一個(gè)行為類似函數(shù)的對(duì)象可以沒(méi)有參數(shù)，也可以帶有若干參數(shù)其功能是獲取一個(gè)值，或者改變操作的狀態(tài)。例普通函數(shù)就是函數(shù)對(duì)象重載了“()”運(yùn)算符的類的實(shí)例是函數(shù)對(duì)象5010.6函數(shù)對(duì)象函數(shù)對(duì)象概念圖5110.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象函數(shù)對(duì)象(Function)一元函數(shù)對(duì)象(UnaryFunction)二元函數(shù)對(duì)象(BinaryFunction)產(chǎn)生器(Generator)一元謂詞(UnaryPredicate)二元謂詞(BinaryPredicate)例10-13、例10-14使用兩種方式定義表示乘法的函數(shù)對(duì)象通過(guò)定義普通函數(shù)（例10-13）通過(guò)重載類的“()”運(yùn)算符（例10-14）用到以下算法：

template<classInputIterator,classType,classBinaryFunction>

Typeaccumulate(InputIteratorfirst,InputIteratorlast,Typeval,BinaryFunctionbinaryOp);對(duì)[first,last)區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行累“加”，binaryOp為用二元函數(shù)對(duì)象表示的“加”運(yùn)算符，val為累“加”的初值5210.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象#include<iostream>#include<numeric> //包含數(shù)值算法頭文件usingnamespacestd;//定義一個(gè)普通函數(shù)intmult(intx,inty){returnx*y;};

intmain(){ inta[]={1,2,3,4,5}; constintN=sizeof(a)/sizeof(int); cout<<"Theresultbymultiplingallelementsinais" <<accumulate(a,a+N,1,mult) <<endl; return0;}5310.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象例10-13（續(xù)）//10_14.cpp#include<iostream>#include<numeric> //包含數(shù)值算法頭文件usingnamespacestd;

classMultClass {//定義MultClass類public:

intoperator()(intx,inty)const{returnx*y;} //重載操作符operator()};

intmain(){ inta[]={1,2,3,4,5}; constintN=sizeof(a)/sizeof(int); cout<<"Theresultbymultiplingallelementsinais" <<accumulate(a,a+N,1,MultClass()) //將類multclass傳遞給通用算法

<<endl; return0;}5410.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象例10-14（續(xù)）STL提供的函數(shù)對(duì)象用于算術(shù)運(yùn)算的函數(shù)對(duì)象：一元函數(shù)對(duì)象：negate二元函數(shù)對(duì)象：plus、minus、multiplies、divides、modulus用于關(guān)系運(yùn)算、邏輯運(yùn)算的函數(shù)對(duì)象一元謂詞：logical_not二元謂詞：equal_to、not_equal_to、greater、less、greater_equal、less_equal、logical_and、logical_or5510.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象例10-15利用STL標(biāo)準(zhǔn)函數(shù)對(duì)象//10_15.cpp#include<iostream>#include<numeric>//包含數(shù)值算法頭文件#include<functional>//包含標(biāo)準(zhǔn)函數(shù)對(duì)象頭文件usingnamespacestd; intmain(){ inta[]={1,2,3,4,5}; constintN=sizeof(a)/sizeof(int); cout<<"TheresultbymultiplingallelementsinAis“<<accumulate(a,a+N,1,multiplies<int>())

<<endl;//將標(biāo)準(zhǔn)函數(shù)對(duì)象傳遞給通用算法 return0;}5610.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象例10-16利用STL中的二元謂詞函數(shù)對(duì)象//10_16.cpp,省略頭部分…intmain(){ intintArr[]={30,90,10,40,70,50,20,80}; constintN=sizeof(intArr)/sizeof(int); vector<int>a(intArr,intArr+N);

cout<<"beforesorting:"<<endl; copy(a.begin(),a.end(),ostream_iterator<int>(cout,"\t")); cout<<endl;

sort(a.begin(),a.end(),greater<int>());

cout<<"aftersorting:"<<endl; copy(a.begin(),a.end(),ostream_iterator<int>(cout,"\t")); cout<<endl; return0;}5710.6函數(shù)對(duì)象——10.6.1函數(shù)對(duì)象10.6.2函數(shù)適配器綁定適配器將n元函數(shù)對(duì)象的指定參數(shù)綁定為一個(gè)常數(shù)，得到n-1元函數(shù)對(duì)象：bind1st、bind2nd組合適配器將指定謂詞的結(jié)果取反：not1、not2指針函數(shù)適配器對(duì)一般函數(shù)指針使用，使之能夠作為其它函數(shù)適配器的輸入：ptr_fun成員函數(shù)適配器對(duì)成員函數(shù)指針使用，把n元成員函數(shù)適配為n+1元函數(shù)對(duì)象，該函數(shù)對(duì)象的第一個(gè)參數(shù)為調(diào)用該成員函數(shù)時(shí)的目的對(duì)象：ptr_fun、ptr_fun_ref5810.6函數(shù)對(duì)象例10-17bind2nd產(chǎn)生binder2nd函數(shù)適配器實(shí)例//10_17.cpp#include<functional>#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;

intmain(){ intintArr[]={30,90,10,40,70,50,20,80}; constintN=sizeof(intArr)/sizeof(int); vector<int>a(intArr,intArr+N); vector<int>::iteratorp=find_if(a.begin(),a.end(),bind2nd(greater<int>(),40)); if(p==a.end()) cout<<"noelementgreaterthan40"<<endl; else cout<<"firstelementgreaterthan40is:"<<*p<<endl; return0;}5910.6函數(shù)對(duì)象——10.6.2函數(shù)適配器

例10-18ptr_fun、not1和not2產(chǎn)生函數(shù)適配器實(shí)例//10_18.cpp,頭部分省略boolg(intx,inty){ returnx>y;}

intmain(){ intintArr[]={30,90,10,40,70,50,20,80}; constintN=sizeof(intArr)/sizeof(int); vector<int>a(intArr,intArr+N);

vector<int>::iteratorp; p=find_if(a.begin(),a.end(),bind2nd(ptr_fun(g),40)); if(p==a.end()) cout<<"noelementgreaterthan40"<<endl; else cout<<"firstelementgreaterthan40is:"<<*p<<endl;6010.6函數(shù)對(duì)象——10.6.2函數(shù)適配器

6110.6函數(shù)對(duì)象——10.6.2函數(shù)適配器

p=find_if(a.begin(),a.end(),not1(bind2nd(greater<int>(),15))); if(p==a.end()) cout<<"noelementisnotgreaterthan15"<<endl; else cout<<"firstelementthatisnotgreaterthan15is:"<<*p<<endl;

p=find_if(a.begin(),a.end(),bind2nd(not2(greater<int>()),15)); if(p==a.end()) cout<<"noelementisnotgreaterthan15"<<endl; else cout<<"firstelementthatisnotgreaterthan15is:"<<*p<<endl; return0;}例10-17（續(xù)）例10-19成員函數(shù)適配器實(shí)例//10_19.cpp#include<functional>#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;

structCar{ intid; Car(intid){this->id=id;} voiddisplay()const{cout<<"car"<<id<<endl;}};

intmain(){ vector<Car*>pcars; vector<Car>cars;6210.6函數(shù)對(duì)象——10.6.2函數(shù)適配器

6310.6函數(shù)對(duì)象——10.6.2函數(shù)適配器

for(inti=0;i<5;i++) pcars.push_back(newCar(i)); for(inti=5;i<10;i++) cars.push_back(Car(i)); cout<<"elementsinpcars:"<<endl; for_each(pcars.begin(),pcars.end(),std::mem_fun(&Car::display)); cout<<endl;

cout<<"elementsincars:"<<endl; for_each(cars.begin(),cars.end(),std::mem_fun_ref(&Car::display)); cout<<endl;

for(size_ti=0;i<pcars.size();++i) deletepcars[i];

return0;}例10-19（續(xù)）10.7.1STL算法基礎(chǔ)STL算法本身是一種函數(shù)模版通過(guò)迭代器獲得輸入數(shù)據(jù)通過(guò)函數(shù)對(duì)象對(duì)數(shù)據(jù)進(jìn)行處理通過(guò)迭代器將結(jié)果輸出STL算法是通用的，獨(dú)立于具體的數(shù)據(jù)類型、容器類型STL算法分類不可變序列算法可變序列算法排序和搜索算法數(shù)值算法6410.7算法10.7.2不可變序列算法不可變序列算法不直接修改所操作的容器內(nèi)容的算法用于查找指定元素、比較兩個(gè)序列是否相等、對(duì)元素進(jìn)行計(jì)數(shù)等例：template<classInputIterator,classUnaryPredicate>InputIteratorfind_if(InputIteratorfirst,InputIteratorlast,UnaryPredicatepred);用于查找[first,last)區(qū)間內(nèi)pred(x)為真的首個(gè)元素6510.7算法例10-20不可變序列算法應(yīng)用實(shí)例//10_20.cpp，頭部分省略….

intmain(){ intiarray[]={0,1,2,3,4,5,6,6,6,7,8}; vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int)); intiarray1[]={6,6}; vector<int>ivector1(iarray1,iarray1+sizeof(iarray1)/sizeof(int)); intiarray2[]={5,6}; vector<int>ivector2(iarray2,iarray2+sizeof(iarray2)/sizeof(int)); intiarray3[]={0,1,2,3,4,5,7,7,7,9,7}; vector<int>ivector3(iarray3,iarray3+sizeof(iarray3)/sizeof(int));

//找出ivector之中相鄰元素值相等的第一個(gè)元素

cout<<*adjacent_find(ivector.begin(),ivector.end())<<endl;

//找出ivector之中小于7的元素個(gè)數(shù)

cout<<count_if(ivector.begin(),ivector.end(),bind2nd(less<int>(),7))<<endl;6610.7算法——10.7.2不可變序列算法

//找出ivector之中大于2的第一個(gè)元素所在位置的元素

cout<<*find_if(ivector.begin(),ivector.end(),bind2nd(greater<int>(),2))<<endl;

//子序列ivector2在ivector中出現(xiàn)的起點(diǎn)位置元素

cout<<*search(ivector.begin(),ivector.end(), ivector2.begin(),ivector2.end())<<endl;

//查找連續(xù)出現(xiàn)3個(gè)6的起點(diǎn)位置元素

cout<<*search_n(ivector.begin(),ivector.end(),3,6,equal_to<int>())<<endl;

//判斷兩個(gè)區(qū)間ivector和ivector3相等否(0為假，1為真) cout<<equal(ivector.begin(),ivector.end(),ivector3.begin())<<endl;

//查找區(qū)間ivector3在ivector中不匹配點(diǎn)的位置

pair<vector<int>::iterator,vector<int>::iterator>result=

mismatch(ivector.begin(),ivector.end(),ivector3.begin()); cout<<result.first-ivector.begin()<<endl; return0;}6710.7算法——10.7.2不可變序列算法

例10-20（續(xù)）10.7.3可變序列算法可變序列算法可以修改它們所操作的容器對(duì)象包括對(duì)序列進(jìn)行復(fù)制、刪除、替換、倒序、旋轉(zhuǎn)、交換、變換、分割、去重、填充、洗牌的算法及生成一個(gè)序列的算法例：template<classForwardIterator,classT>InputIteratorfind_if(ForwardIteratorfirst,ForwardIteratorlast,constT&x);把[first,last)區(qū)間內(nèi)的元素全部改寫為x6810.7算法例10-21以可變序列算法對(duì)數(shù)據(jù)序列進(jìn)行復(fù)制，生成，刪除，替換，倒序，旋轉(zhuǎn)等可變性操作6910.7算法——10.7.3可變序列算法//10_21.cpp,頭部分省略classevenByTwo{private: intx;public: evenByTwo():x(0){} intoperator()(){returnx+=2;}};intmain(){ intiarray1[]={0,1,2,3,4,4,5,5,6,6,6,6,6,7,8}; intiarray2[]={0,1,2,3,4,5,6,6,6,7,8}; vector<int>ivector1(iarray1,iarray1+sizeof(iarray1)/sizeof(int)); vector<int>ivector2(iarray2,iarray2+sizeof(iarray2)/sizeof(int)); vector<int>ivector3(2); ostream_iterator<int>output(cout,"");//定義流迭代器用于輸出數(shù)據(jù)

//迭代遍歷ivector3區(qū)間，每個(gè)元素填上-1

fill(ivector3.begin(),ivector3.end(),-1); copy(ivector3.begin(),ivector3.end(),output);//使用copy進(jìn)行輸出

cout<<endl; //迭代遍歷ivector3區(qū)間，對(duì)每一個(gè)元素進(jìn)行evenByTwo操作

generate(ivector3.begin(),ivector3.end(),evenByTwo()); copy(ivector3.begin(),ivector3.end(),output); cout<<endl;7010.7算法——10.7.3可變序列算法例10-21（續(xù)）//將刪除元素6后的ivector2序列置于另一個(gè)容器ivector4之中

vector<int>ivector4;

remove_copy(ivector2.begin(),ivector2.end(),back_inserter(ivector4),6); copy(ivector4.begin(),ivector4.end(),output); cout<<endl; //刪除小于6的元素

ivector2.erase(remove_if(ivector2.begin(),ivector2.end(),bind2nd(less<int>(),6)),ivector2.end()); copy(ivector2.begin(),ivector2.end(),output); cout<<endl; //將所有的元素值6，改為元素值3

replace(ivector2.begin(),ivector2.end(),6,3); copy(ivector2.begin(),ivector2.end(),output); cout<<endl; //逆向重排每一個(gè)元素

reverse(ivector2.begin(),ivector2.end()); copy(ivector2.begin(),ivector2.end(),output); cout<<endl; //旋轉(zhuǎn)（互換元素）[first,middle),和[middle,end)，結(jié)果直接輸出

rotate_copy(ivector2.begin(),ivector2.begin()+3,ivector2.end(),output); cout<<endl; return0;}7110.7算法——10.7.3可變序列算法例10-21（續(xù)）例10-21（續(xù)）運(yùn)行結(jié)果：-1-12401234578666783337887333338737210.7算法——10.7.3可變序列算法10.7.4排序和搜索算法排序和搜索算法對(duì)序列進(jìn)行排序?qū)捎行蛐蛄羞M(jìn)行合并對(duì)有序序列進(jìn)行搜索有序序列的集合操作堆算法例：template<classRandomAccessIterator,classUnaryPredicate>voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast,UnaryPredicatecomp);以函數(shù)對(duì)象comp為“<”，對(duì)[first,last)區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行排序7310.7算法例10-22排序與搜索算法示例//10_22.cpp,頭部分省略…intmain(){ intiarray[]={26,17,15,22,23,33,32,40}; vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int));

//查找并輸出第一個(gè)最大值元素及其位置

vector<int>::iteratorp=max_element(ivector.begin(),ivector.end()); intn=p-ivector.begin(); cout<<"maxelement:"<<*p<<"foundat"<<n<<endl;

vector<int>ivector1(5);//局部排序并復(fù)制到別處

partial_sort_copy(ivector.begin(),ivector.end(),ivector1.begin(),ivector1.end()); copy(ivector1.begin(),ivector1.end(),ostream_iterator<int>(cout,"")); cout<<endl;

sort(ivector.begin(),ivector.end());//排序，缺省為遞增。 copy(ivector.begin(),ivector.end(),ostream_iterator<int>(cout,"")); cout<<endl;7410.7算法——10.7.4排序和搜索算法//返回小于等于24和大于等于24的元素的位置

cout<<*lower_bound(ivector.begin(),ivector.end(),24)<<endl; cout<<*upper_bound(ivector.begin(),ivector.end(),24)<<endl;

//對(duì)于有序區(qū)間，可以用二分查找方法尋找某個(gè)元素

cout<<binary_search(ivector.begin(),ivector.end(),33)<<endl;

//合并兩個(gè)序列ivector和ivector1，并將結(jié)果放到ivector2中

vector<int>ivecto