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

第十章

泛型程序設(shè)計

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

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

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

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

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

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

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

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

copy(s.begin(),s.end(),result); //將s序列通過輸出迭代器輸出}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)輸入讀入若干個整數(shù)，將排序后的結(jié)果輸出

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

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

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

，pop_back其他順序容器訪問函數(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個整數(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的每相鄰兩個容器順序顛倒

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ù)）運行結(jié)果如下：0986432154dequeatfirst:4512346890listatfirst:0986432154listatlast:9068341245dequeatlast:90683412452210.4順序容器——10.4.1順序容器的基本功能10.4.2三種順序容器的特性

——向量（Vector）特點一個可以擴(kuò)展的動態(tài)數(shù)組隨機(jī)訪問、在尾部插入或刪除元素快在中間或頭部插入或刪除元素慢向量的容量容量(capacity)：實際分配空間的大小s.capacity()：返回當(dāng)前容量s.reserve(n)：若容量小于n，則對s進(jìn)行擴(kuò)展，使其容量至少為n2310.4順序容器雙端隊列（deque）特點在兩端插入或刪除元素快在中間插入或刪除元素慢隨機(jī)訪問較快，但比向量容器慢2410.4順序容器——10.4.2三種順序容器的特性例10-5奇偶排序先按照從大到小順序輸出奇數(shù)，再按照從小到大順序輸出偶數(shù)。2510.4順序容器——10.4.2三種順序容器的特性//頭部分省略intmain(){istream_iterator<int>i1(cin),i2; //建立一對兒輸入流迭代器vector<int>s1(i1,i2); //通過輸入流迭代器從標(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)特點在任意位置插入和刪除元素都很快不支持隨機(jī)訪問接合(splice)操作s1.splice(p,s2,q1,q2)：將s2中[q1,q2)移動到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的第一個元素放到s2的最后

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

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

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

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

2710.4順序容器——10.4.2三種順序容器的特性例10-6（續(xù)）28list<string>::iteratoriter3=iter2;//用iter2初始化iter3advance(iter3,2);//iter3前進(jìn)2個元素，它將指向s2第4個元素//將[iter2,iter3)范圍內(nèi)的結(jié)點接到s1中iter1指向的結(jié)點前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三種順序容器的特性運行結(jié)果：HelenLucyDavidLevinSusanBobMikeAlice三種順序容器的比較STL所提供的三種順序容器各有所長也各有所短，我們在編寫程序時應(yīng)當(dāng)根據(jù)我們對容器所需要執(zhí)行的操作來決定選擇哪一種容器。如果需要執(zhí)行大量的隨機(jī)訪問操作，而且當(dāng)擴(kuò)展容器時只需要向容器尾部加入新的元素，就應(yīng)當(dāng)選擇向量容器vector；如果需要少量的隨機(jī)訪問操作，需要在容器兩端插入或刪除元素，則應(yīng)當(dāng)選擇雙端隊列容器deque；、如果不需要對容器進(jìn)行隨機(jī)訪問，但是需要在中間位置插入或者刪除元素，就應(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;//通過iter把5插入s末尾3010.4順序容器10.4.4順序容器的適配器以順序容器為基礎(chǔ)構(gòu)建一些常用數(shù)據(jù)結(jié)構(gòu)棧(stack)：最先壓入的元素最后被彈出隊列(queue)：最先壓入的元素最先被彈出優(yōu)先級隊列(priority_queue)：最“大”的元素最先被彈出3110.4順序容器例10-7利用棧反向輸出單詞//10_7.cpp，省略頭部分intmain(){ stack<char>s; stringstr; cin>>str; //從鍵盤輸入一個字符串

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

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

classCell;priority_queue<Cell>cellQueue;

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

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

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

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

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

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

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

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

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

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

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

}};intCell::count=0;

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

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

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

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

} return0;}35例10-8（續(xù)）10.4順序容器——10.4.4順序容器的適配器例10-8（續(xù)）運行結(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)容器的特點每個關(guān)聯(lián)容器都有一個鍵(key)可以根據(jù)鍵高效地查找元素接口插入：insert刪除：erase查找：find定界：lower_bound、upper_bound、equal_range計數(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)簡單關(guān)聯(lián)容器(SimpleAsso-

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

ciativeContainer)multisetmultimapsetmap四種關(guān)聯(lián)容器單重關(guān)聯(lián)容器(set和map)鍵值是唯一的，一個鍵值只能對應(yīng)一個元素多重關(guān)聯(lián)容器(multiset和multimap)鍵值是不唯一的，一個鍵值可以對應(yīng)多個元素簡單關(guān)聯(lián)容器(set和multiset)容器只有一個類型參數(shù)，如set<K>、multiset<K>，表示鍵類型容器的元素就是鍵本身二元關(guān)聯(lián)容器(map和multimap)容器有兩個類型參數(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）集合用來存儲一組無重復(fù)的元素。由于集合的元素本身是有序的，可以高效地查找指定元素，也可以方便地得到指定大小范圍的元素在容器中所處的區(qū)間。例10-9輸入一串實數(shù)，將重復(fù)的去掉，取最大和最小者的中值，分別輸出小于等于此中值和大于等于此中值的實數(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(); //得到第一個元素的迭代器

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ù)）運行結(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)成的二元組。在集合中按照鍵查找一個元素時，一般只是用來確定這個元素是否存在，而在映射中按照鍵查找一個元素時，除了能確定它的存在性外，還可以得到相應(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); //將剛選過的課程從映射中刪除

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

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

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

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

charc; //存儲輸入字符

do{ cin>>c; //輸入下一個字符

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

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

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

//輸出每個字母出現(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ù)元素的集合，多重映射是允許一個鍵對應(yīng)多個附加數(shù)據(jù)的映射。多重集合與集合、多重映射與映射的用法差不多，只在幾個成員函數(shù)上有細(xì)微差異，其差異主要表現(xiàn)在去除了鍵必須唯一的限制。例10-12上課時間查詢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;

//將課程上課時間插入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")); //輸入一個課程名，直到找到該課程為止，記下每周上課次數(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ù)和上課時間

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ù)）運行結(jié)果如下：JAVACannotfindthiscourse!OS3lesson(s)perweek:1-24-15-510.6.1函數(shù)對象函數(shù)對象一個行為類似函數(shù)的對象可以沒有參數(shù)，也可以帶有若干參數(shù)其功能是獲取一個值，或者改變操作的狀態(tài)。例普通函數(shù)就是函數(shù)對象重載了“()”運算符的類的實例是函數(shù)對象5010.6函數(shù)對象函數(shù)對象概念圖5110.6函數(shù)對象——10.6.1函數(shù)對象函數(shù)對象(Function)一元函數(shù)對象(UnaryFunction)二元函數(shù)對象(BinaryFunction)產(chǎn)生器(Generator)一元謂詞(UnaryPredicate)二元謂詞(BinaryPredicate)例10-13、例10-14使用兩種方式定義表示乘法的函數(shù)對象通過定義普通函數(shù)（例10-13）通過重載類的“()”運算符（例10-14）用到以下算法：

template<classInputIterator,classType,classBinaryFunction>

Typeaccumulate(InputIteratorfirst,InputIteratorlast,Typeval,BinaryFunctionbinaryOp);對[first,last)區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行累“加”，binaryOp為用二元函數(shù)對象表示的“加”運算符，val為累“加”的初值5210.6函數(shù)對象——10.6.1函數(shù)對象#include<iostream>#include<numeric> //包含數(shù)值算法頭文件usingnamespacestd;//定義一個普通函數(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ù)對象——10.6.1函數(shù)對象例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ù)對象——10.6.1函數(shù)對象例10-14（續(xù)）STL提供的函數(shù)對象用于算術(shù)運算的函數(shù)對象：一元函數(shù)對象：negate二元函數(shù)對象：plus、minus、multiplies、divides、modulus用于關(guān)系運算、邏輯運算的函數(shù)對象一元謂詞：logical_not二元謂詞：equal_to、not_equal_to、greater、less、greater_equal、less_equal、logical_and、logical_or5510.6函數(shù)對象——10.6.1函數(shù)對象例10-15利用STL標(biāo)準(zhǔn)函數(shù)對象//10_15.cpp#include<iostream>#include<numeric>//包含數(shù)值算法頭文件#include<functional>//包含標(biāo)準(zhǔn)函數(shù)對象頭文件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ù)對象傳遞給通用算法 return0;}5610.6函數(shù)對象——10.6.1函數(shù)對象例10-16利用STL中的二元謂詞函數(shù)對象//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ù)對象——10.6.1函數(shù)對象10.6.2函數(shù)適配器綁定適配器將n元函數(shù)對象的指定參數(shù)綁定為一個常數(shù)，得到n-1元函數(shù)對象：bind1st、bind2nd組合適配器將指定謂詞的結(jié)果取反：not1、not2指針函數(shù)適配器對一般函數(shù)指針使用，使之能夠作為其它函數(shù)適配器的輸入：ptr_fun成員函數(shù)適配器對成員函數(shù)指針使用，把n元成員函數(shù)適配為n+1元函數(shù)對象，該函數(shù)對象的第一個參數(shù)為調(diào)用該成員函數(shù)時的目的對象：ptr_fun、ptr_fun_ref5810.6函數(shù)對象例10-17bind2nd產(chǎn)生binder2nd函數(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ù)對象——10.6.2函數(shù)適配器

例10-18ptr_fun、not1和not2產(chǎn)生函數(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ù)對象——10.6.2函數(shù)適配器

6110.6函數(shù)對象——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ù)適配器實例//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ù)對象——10.6.2函數(shù)適配器

6310.6函數(shù)對象——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ù)模版通過迭代器獲得輸入數(shù)據(jù)通過函數(shù)對象對數(shù)據(jù)進(jìn)行處理通過迭代器將結(jié)果輸出STL算法是通用的，獨立于具體的數(shù)據(jù)類型、容器類型STL算法分類不可變序列算法可變序列算法排序和搜索算法數(shù)值算法6410.7算法10.7.2不可變序列算法不可變序列算法不直接修改所操作的容器內(nèi)容的算法用于查找指定元素、比較兩個序列是否相等、對元素進(jìn)行計數(shù)等例：template<classInputIterator,classUnaryPredicate>InputIteratorfind_if(InputIteratorfirst,InputIteratorlast,UnaryPredicatepred);用于查找[first,last)區(qū)間內(nèi)pred(x)為真的首個元素6510.7算法例10-20不可變序列算法應(yīng)用實例//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之中相鄰元素值相等的第一個元素

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

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

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

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

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

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

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

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

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

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

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

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可變序列算法可變序列算法可以修改它們所操作的容器對象包括對序列進(jìn)行復(fù)制、刪除、替換、倒序、旋轉(zhuǎn)、交換、變換、分割、去重、填充、洗牌的算法及生成一個序列的算法例：template<classForwardIterator,classT>InputIteratorfind_if(ForwardIteratorfirst,ForwardIteratorlast,constT&x);把[first,last)區(qū)間內(nèi)的元素全部改寫為x6810.7算法例10-21以可變序列算法對數(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ū)間，每個元素填上-1

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

cout<<endl; //迭代遍歷ivector3區(qū)間，對每一個元素進(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序列置于另一個容器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; //逆向重排每一個元素

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ù)）運行結(jié)果：-1-12401234578666783337887333338737210.7算法——10.7.3可變序列算法10.7.4排序和搜索算法排序和搜索算法對序列進(jìn)行排序?qū)捎行蛐蛄羞M(jìn)行合并對有序序列進(jìn)行搜索有序序列的集合操作堆算法例：template<classRandomAccessIterator,classUnaryPredicate>voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast,UnaryPredicatecomp);以函數(shù)對象comp為“<”，對[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));

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

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;

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

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

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

vector<int>ivecto