C++程序設計第8章模板第8章模板本章學習要點函數模板類模板STL（StandardTemplateLibrary，標準模板庫）本章學習目標了解函數模板的概念，掌握函數模板的定義與使用了解類模板的概念，掌握類模板的定義與使用了解STL有關內容。第8章模板1.非類型參數與函數模板的模板參數一樣，類模板的模板參數中也可以出現非類型參數。對于【例8-8】的堆棧類模板Stack，也可以不定義一個int型常變量SSize來指定棧的容量大小，而改成為其增加一個非類型參數。§8.3.3類模板參數§8.3.3類模板參數//Stack.htemplate<classT,intSSize>classStack{public:

Stack(){top=0;}

voidpush(Te);//入棧操作

Tpop();

//出棧操作

boolStackEmpty(){returntop==0;}

boolStackFull(){returntop=SSize;}private:

Tdata[SSize];//棧元素數組，固定大小為SSize

inttop; //棧頂指針};§8.3.3類模板參數//push成員函數的類外定義template<classT,intSSize>voidStack<T,SSize>::push(Te){if(top==SSize)

{cout<<"StackisFull!Don'tpushdata!"<<endl;

return;

}

data[top++]=e;}§8.3.3類模板參數//pop成員函數的類外定義，指定為內聯函數template<classT,intSSize>inlineTStack<T,SSize>::pop(){if(top==0){cout<<"StackisEmpty!Don'tpopdata!"<<endl;return0;}top--;returndata[top];}當需要這個模板的一個實例時，必須為非類型參數SSize顯式提供一個編譯時常數值。例如：Stack<int,10>int_stack;§8.3.3類模板參數在類模板中，可以為模板參數提供默認參數，但是在函數模板中卻不行。例如，為了使上述的固定大小的Stack類模板更友好一些，可以為其非類型模板參數SSize提供默認值，如下所示：§8.3.3類模板參數template<classT,intSSize=10>classStack{public:

…private:

Tdata[SSize];//棧元素數組，固定大小為SSize

inttop;

//棧頂指針};§8.3.3類模板參數說明：（1）作為默認的模板參數，它們只能被定義一次，編譯器會知道第1次的模板聲明或定義。（2）指定默認值的模板參數必須放在模板形參表的右端，否則出錯。template<classT1,classT2,classT3=double,intN=100>//正確template<classT1,classT2=double,classT3,intN=100>//錯誤§8.3.3類模板參數說明：（3）可以為所有模板參數提供默認值，但在聲明一個實例時必須使用一對空的尖括號，這樣編譯器就知道說明了一個類模板。§8.3.3類模板參數說明：template<classT=int,intSSize=10>classStack{public:

…private:Tdata[SSize];//棧元素數組，固定大小為SSizeinttop; //棧頂指針};§8.3.3類模板參數Stack<>mystack;//sameasStack<int,10>3. 模板類型的模板參數類模板的模板形參表中的參數類型有3種：類型參數、非類型參數、類模板類型的參數，函數模板的模板參數類型也與此相同。對于前兩種類型的模板參數，我們已經比較熟悉了。下面看一個類模板類型的模板參數的例子。【例8-9】類模板類型的模板參數舉例。§8.3.3類模板參數§8.3.3類模板參數#include<iostream>usingnamespacestd;template<classT,size_tsize>classArray{

Tdata[size];

size_tcount;//數組元素個數public:

Array(){count=0;}//構造函數

voidpush_back(constT&t)

{if(count<size)data[count++]=t;}

voidpop_back()

{if(count>0)--count;}

T*begin(){returndata;}

T*end(){returndata+count;}};

typedefunsignedintsize_t;§8.3.3類模板參數//聲明Container類模板，//它有一個類模板類型的模板參數Seqtemplate<classT,size_tsize,

template<class,size_t>classSeq>classContainer{

Seq<T,size>seq;public:

voidappend(constT&t){seq.push_back(t);}

T*begin(){returnseq.begin();}

T*end(){returnseq.end();}};

§8.3.3類模板參數intmain(){constsize_tN=10;container<int,

N,

Array>container;

container.append(1);

container.append(2);

int*p=container.begin();

while(p!=container.end())

cout<<*p++<<endl;

return0;}§8.3.3類模板參數//聲明Container類模板，//它有一個類模板類型的模板參數Seqtemplate<classT,size_tsize,

classSeq>classContainer{

Seqseq;public:

voidappend(constT&t){seq.push_back(t);}

T*begin(){returnseq.begin();}

T*end(){returnseq.end();}};

§8.3.3類模板參數intmain(){constsize_tN=10;

Container<int,

N,

Array<int,N>>container;

container.append(1);

container.append(2);

int*p=container.begin();

while(p!=container.end())

cout<<*p++<<endl;

return0;}§8.3.3類模板參數//聲明Container類模板，//它有一個類模板類型的模板參數Seqtemplate<classT,size_tsize>classContainer{

Array<T,size>seq;public:

voidappend(constT&t){seq.push_back(t);}

T*begin(){returnseq.begin();}

T*end(){returnseq.end();}};

§8.3.3類模板參數intmain(){constsize_tN=10;

Container<int,

N>container;

container.append(1);

container.append(2);

int*p=container.begin();

while(p!=container.end())

cout<<*p++<<endl;

return0;}3．編寫一個順序表類模板。4.編寫一個單鏈表類模板。作業STL是StandardTemplateLibrary（標準模板庫）的縮寫，是一個高效的C++程序庫，它被容納于C++標準程序庫（C++StandardLibrary）中，是ANSI/ISOC++標準的一部分。該庫包含了諸多在計算機科學領域里所常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性。另外，string類型用于處理字符串，也算作是STL的一部分。§8.4STL簡介向量（vector）雙向鏈表（list）雙端隊列（deque）棧（stack)隊列（queue）優先級隊列（priority_queue）集合（set和mulitset）映射（map和mulitmap）STL中的基本數據結構紅黑樹（RB_tree)（只限內部使用，不對外公開）哈希表（hashtable）（SGISTL提供的不在標準規格之列的）用類模板實現容器sort算法reverse算法copy算法merge算法find和find_if算法count和count_if算法max_element和min_element算法search和binary_search算法for_each算法STL中的基本算法用函數模板實現STL中的迭代器迭代器是STL中算法和容器的粘合劑，用來將算法和容器聯系起來，起到一種關聯的作用。迭代器類似于指針，但它是基于模板的“功能更強大、更智能、更安全的指針”，用于指示容器中的元素位置，通過迭代器能夠遍歷容器中的每個元素。STL算法利用它們對容器中的對象序列進行遍歷。【舉例】利用STL，從鍵盤輸入一系列整數，計算其中的最大數、所有元素的和以及對元素進行排序。STL中的迭代器#include<iostream>usingnamespacestd;#include<vector>#include<algorithm>#include<numeric>intmain(){ vector<int>v; intx; cout<<"請輸入一組整數，以0結束。"<<endl; cin>>x; while(x>0) {v.push_back(x); cin>>x; } STL中的迭代器vector<int>::iteratorit1=v.begin();vector<int>::iteratorit2=v.end(); cout<<"Max="<<*max_element(it1,it2)<<endl;cout<<"Sum="<<accumulate(it1,it2,0)<<endl; sort(it1,it2); cout<<"Sortedresultis:\n"; while(it1!=it2) {cout<<*it1<<''; ++it1; } cout<<endl;return0;}STL中的迭代器STL的代碼從廣義上講分為三類：container（容器）、iterator（迭代器）和algorithm（算法），幾乎所有的代碼都采用了模板（類模板和函數模板）的方式，這相比于傳統的由函數和類組成的庫來說提供了更好的代碼重用機會。在C++標準中，STL被組織為下面的13個頭文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。§8.4STL簡介從實現的角度看，STL容器是一種類模板。STL是經過精心設計的，為了減小我們使用容器的難度，大多數容器都提供了相同的成員函數，盡管一些成員函數的實現是不同的。下面我們先通過幾張表格來了解一下STL中的常用容器及其公用的成員函數。§8.4.1容器從實現的角度看，STL容器是一種類模板。STL是經過精心設計的，為了減小我們使用容器的難度，大多數容器都提供了相同的成員函數，盡管一些成員函數的實現是不同的。下面我們先通過教材上的表8-1～8-3來了解一下STL中的常用容器及其公用的成員函數。§8.4.1容器并且，除了stack、queue和priority_queue之外，其他容器中均有的通用成員函數還包括begin()、end()、rebegin()、rend()、erase()以及clear()。begin()：指向第一個元素end()：指向最后一個元素之后rbegin()：指向按反向順序的第一個元素rend()：指向按反向順序的最后一個元素之后erase()：刪除容器中的一個或多個元素clear()：刪除容器中的所有元素§8.4.1容器容器是容納、包含一組元素或元素集合的對象。不管是C++內建的基本數據類型或是用戶自定義的類類型的數據，都可以存入STL的容器中。§8.4.1容器注意：如果存儲在容器中的元素的類型是用戶自定義的類類型，那么至少要為該類提供默認的構造函數、析構函數和賦值運算符函數。一些編譯器還需要重載一些關系操作符函數（至少需要重載==和<，還可能需要重載!=和>），即使程序并不需要用到它們。另外，如果用戶自定義的類中有指針數據成員，還必須提供復制構造函數和函數operator=，因為插入操作使用的是插入元素的一個副本，而不是元素本身。§8.4.1容器STL容器按存取順序大致分為兩種：

序列（sequence）容器與關聯（associative）容器。序列容器主要包括vector（向量）、list（表）、deque（雙端隊列）、stack（棧）、queue（隊列）、priority_queue（優先隊列）等。其中，stack和queue由于只是將deque改頭換面，其實是一種容器適配器，但它的用途在軟件領域比deque廣泛。priority_queue也是一種容器適配器。序列容器中只能包含一種類型的數據元素，而且各元素的排列順序完全按照元素插入時的順序。§8.4.1容器關聯容器主要包括set（集合）、multiset（多重集合）、map（映射）、multimap（多重映射），可以存儲值的集合或鍵值對。鍵是關聯容器中存儲在有序序對中的特定類型的值。map和multimap存儲和操作的是鍵和與鍵相關的值，其元素是有關聯的<鍵，值>數據對。set和multiset存儲和操作的只是鍵，其元素是由單個數據構成。§8.4.1容器（1）向量（vector）向量類似于數組，它存儲具有相同數據類型的一組元素，可以從后面快速地插入與刪除元素，可以快速地隨機訪問元素，但是在序列中間插入、刪除元素較慢，因為需要移動插入或刪除處后面的所有元素。向量能夠動態改變自身大小，當要將一個元素插入到一個已滿的向量時，會為向量分配一個更大的內存空間，將向量中的元素復制到新的內存空間中，然后釋放舊的內存空間。但是重新分配更大空間需要進行大量的元素復制，從而增大了性能開銷。§8.4.1容器【例8-10】一個簡單的vector容器使用程序。#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<char*>v;

//構造空向量vv.push_back("me");//在向量v的尾部插入字符串mev.push_back("you");v.push_back("he");v.push_back("she");for(inti=0;i<4;i++)cout<<v[i]<<"";cout<<endl;return0;

}§8.4.1容器程序運行結果如下：meyouheshe（2）表（list）STL中的list是一個雙向鏈表，可以從頭到尾或從尾到頭訪問鏈表中的節點，節點可以是任意數據類型。鏈表中節點的訪問常常通過迭代器進行。它的每個元素間用指針相連，不能速記訪問元素。為了訪問表容器中指定的元素，必須從第一個位置（表頭）開始，隨著指針從一個元素到下一個元素，直到找到要找的元素。但插入元素比vector快，對每個元素分別分配空間，不存在空間不夠、重新分配的情況。§8.4.1容器【例8-11】一個簡單的List容器使用的例子。#include<iostream>#include<list>//鏈表頭文件usingnamespacestd;intmain(){inti;list<int>L1,L2;inta1[]={100,90,80,70,60};inta2[]={30,40,50,60,60,60,80};for(i=0;i<5;i++)L1.push_back(a1[i]);for(i=0;i<7;i++)L2.push_back(a2[i]);§8.4.1容器L1.reverse();//將L1鏈表倒序L1.merge(L2);//將L2合并到L1鏈表中cout<<"L1的元素個數為："<<L1.size()<<endl;L1.unique();//刪除L1中相鄰位置的相同元素，只留1個while(!L1.empty()){cout<<L1.front()<<"\t";L1.pop_front();//刪除L1的鏈首元素}cout<<endl;return0;}程序運行結果如下：L1的元素個數為：1230

40

50

60

70

80

90

100

§8.4.1容器（3）stackSTL中的stack容器不是重新創建的，它只是對已有容器做適當的調整。默認情況下，雙端隊列（deque）是基礎容器，但是我們可以用下面的聲明選擇向量或鏈表。stack<int>stack1;

//默認為雙端隊列stack<int,vector<int>>stack2;

//向量stack<int,list<int>>stack3;

//鏈表stack是一種較簡單的操作受限的容器，只允許在一端存取元素，后進棧的元素先出棧，即LIFO（lastinfirstout）。§8.4.1容器（4）set和multisetset和multiset都屬于關聯容器，他們提供了控制數字（包括字符及串）集合的操作，集合中的數字稱為關鍵字（也稱為鍵），不需要有另一個值與關鍵字相關聯。set和multiset會根據特定的排序準則，自動將元素排序，兩者提供的操作方法基本相同，只是multiset允許元素重復而set不允許重復。§8.4.1容器#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;set<int>::iteratorpos;multiset<int>q;multiset<int>::iteratorpoq;s.insert(1);s.insert(8);s.insert(2);s.insert(1);q.insert(1);q.insert(8);q.insert(2);q.insert(1);

§8.4.1容器cout<<"theset:"<<endl;for(pos=s.begin();pos!=s.end();pos++)cout<<*pos<<"";cout<<endl;cout<<"themultiset:"<<endl;for(poq=q.begin();poq!=q.end();poq++)cout<<*poq<<"";cout<<endl;return0;}§8.4.1容器程序運行結果如下：theset：128themultiset:1128（5）map和multimap它們也屬于關聯容器，都是映射類的模板。映射是實現關鍵字與值關聯的存儲結構，可以使用一個關鍵字來訪問相應的數值。關鍵字可以是數值，如學號070203200，它對應的名字為“張三”，班級為“0707班”。map中的元素不允許重復，而multimap中的元素是可以重復的。它們的迭代器提供了兩個數據成員：一個是first，用于訪問關鍵字；另一個是second，用于訪問值。§8.4.1容器#include<iostream>#include<string>#include<map>usingnamespacestd;intmain(){stringname[]={“張大年”,“劉明海”,“李煜”};//雇員姓名doublesalary[]={1200,2000,1450}; //雇員工資map<string,double>sal;//用映射存儲姓名和工資map<string,double>::iteratorp;//定義映射的迭代器§8.4.1容器用map查詢雇員的工資。

//將姓名/工資加入映射for(inti=0;i<3;i++)sal.insert(make_pair(name[i],salary[i]));sal["tom"]=3400;//通過下標運算加入map元素sal["bob"]=2000;

//輸出映射中的全部元素for(p=sal.begin();p!=sal.end();p++)cout<<p->first<<"\t"<<p->second<<endl;§8.4.1容器stringperson;cout<<"輸入查找人員的姓名：";cin>>person;

//據姓名查工資，找到就輸出for(p=sal.begin();p!=sal.end();p++)if(p->first==person)cout<<p->second<<endl;return0;}§8.4.1容器（6）stringSTL中的string是一種特殊類型的容器，原因是它除了可作為字符類型的容器外，更多的是作為一種數據類型——字符串，可以像int、double之類的基本數據類型那樣定義string類型的數據，并進行各種運算。string容器在STL中被實現為一個類——string類，該類提供了用于字符串賦值（assign）、比較（compare）的函數，同時還重載了賦值和比較運算符。表8-6列出了string類重載的運算符。§8.4.1容器（6）string注意：與char*字符串不同的是，string類型的字符串不一定以“\0”終止，其長度可用成員函數length讀取，可用下標運算符[]訪問其中的單個字符，起始下標為0，終止下標是字符串長度減1。§8.4.1容器（6）stringstring類提供的常用成員函數如下：出于介紹成員函數的需要，我們事先定義兩個string類型變量s1、s2。strings1="ABCDEFG";strings2="0123456123";§8.4.1容器（6）stringsubstr(n1,n)：取子串函數，從當前字符串的n1下標開始，取出n個字符。如“s=s1.substr(2,3)”的結果為：s="CDE"swap(s)：將當前字符串與s交換。如“s1.swap(s2)”的結果為：s1="0123456123"，s2="ABCDEFG"size()/length()：計算當前字符串中目前存放的字符個數。如“s1.length()”的結果為：7§8.4.1容器（6）stringcapacity()：計算字符串的容量（即在不增加內存的情況下，可容納的字符個數）。如“s1.capacity()”的結果為：31max_size()：計算string類型數據的最大容量。如“s1.max_size()”的結果為：4294967293find(s)：在當前字符串中查找子串s，如找到，就返回s在當前字符串中的起始位置；如沒找到，返回常數string::npos。如“s1.find("EF")”的結果為：4§8.4.1容器（6）stringrfind(s)：同find，但從后向前進行查找。如“s1.rfind("BCD")”的結果為：1find_first_of(s)：在當前串中查找子串s第一次出現的位置。如“s2.find_first_of("123")”的結果為：1find_last_of(s)：在當前串中查找子串s最后一次出現的位置。如“s2.find_last_of("123")”的結果為：9§8.4.1容器（6）stringreplace(n1,n,s)：替換當前字符串中的字符，n1是替換的起始下標，n是要替換的字符個數，s是用來替換的字符串。replace(n1,n,s,n2,m)：替換當前字符串中的字符，n1是替換的起始下標，n是要替換的字符個數，s是用來替換的字符串，n2是s中用來替換的起始下標，m是s中用于替換的字符個數。如“s1.replace(2,3,s2,2,3)”的結果為：s1="AB234FG"§8.4.1容器（6）stringinsert(n,s)：在當前串的下標位置n之前，插入s串。insert(n1,s,n2,m)：在當前串的n1下標之后插入s串，n2是s串中要插入的起始下標，m是s串中要插入的字符個數。§8.4.1容器迭代器是STL中算法和容器的粘合劑，用來將算法和容器聯系起來，起到一種關聯的作用。迭代器類似于指針，但它是基于模板的“功能更強大、更智能、更安全的指針”，用于指示容器中的元素位置，通過迭代器能夠遍歷容器中的每個元素。STL算法利用它們對容器中的對象序列進行遍歷。§8.4.2迭代器（iterator）

迭代器提供的主要操作如下：operator*：

返回當前位置上的元素值operator++：將迭代器前進到下一個元素位置operator--：

將迭代器后退到前一個元素位置operator=：

為迭代器賦值begin()：

指向容器起點（即第一個元素）位置end()：指向容器的結束點（最后一個元素之后）位置rbegin()：

指向按反向順序的第一個元素位置rend()：

指向按反向順序的最后一個元素后的位置§8.4.2迭代器（iterator）

#include<iostream>#include<list>usingnamespacestd;intmain(){inti;//L1、L2為空鏈表，L3為有10個元素的鏈表list<int>L1,L2,L3(10);list<int>::iteratoriter;//定義迭代器iter

inta1[]={100,90,80,70,60};inta2[]={30,40,50,60,60,60,80};鏈表中迭代器的應用例子。§8.4.2迭代器（iterator）

//插入L1鏈表元素，在表尾插入for(i=0;i<5;i++)L1.push_back(a1[i]);

//插入L2鏈表元素，在表頭插入for(i=0;i<7;i++)L2.push_front(a2[i]);

//通過迭代器順序輸出L1的所有元素for(iter=L1.begin();iter!=L1.end();iter++)cout<<*iter<<"\t";cout<<endl;§8.4.2迭代器（iterator）

intsum=0;

//通過迭代器反向輸出L2的所有元素for(iter=--L2.end();iter!=L2.begin();iter--){cout<<*iter<<"\t";sum+=*iter;//計算L2所有鏈表節點的總和}cout<<"\nL2:sum="<<sum<<endl;§8.4.2迭代器（iterator）

intdata=0;

//通過迭代器修改L3鏈表的內容for(iter=L3.begin();iter!=L3.end();iter++) *iter=data+=10;for(iter=L3.begin();iter!=L3.end();iter++)cout<<*iter<<"\t";cout<<endl;return0;}§8.4