第11章 模板與標(biāo)準(zhǔn)模板庫

第十一章

模板與標(biāo)準(zhǔn)模板庫函數(shù)模板11.1函數(shù)模板模板是C++支持參數(shù)化多態(tài)的工具，它可以實現(xiàn)類型參數(shù)化，即把類型定義為參數(shù)，真正實現(xiàn)了代碼的可重用性，減輕了編程及維護的工作量和難度。模板使類或函數(shù)可在編譯時定義所需處理和返回的數(shù)據(jù)類型，一個模板并非一個實實在在的類或函數(shù)，僅僅是一個類或函數(shù)的描述。模板一般分為函數(shù)模板和類模板。模板的定義函數(shù)模板并不是一個可以直接使用的函數(shù)，它是可以產(chǎn)生多個函數(shù)的模板。使用模板的目的就是要讓這些程序的實現(xiàn)與類型無關(guān)。函數(shù)模板定義函數(shù)模板的語法格式如下所示： template<typename形參名,typename形參名...>

返回值類型函數(shù)名（參數(shù)列表） {

函數(shù)體; }函數(shù)模板定義11.1函數(shù)模板11.1函數(shù)模板#include<iostream>usingnamespacestd;//定義函數(shù)模板template<typenameT>Tadd(Tt1,Tt2){ returnt1+t2;}intmain(){ cout<<add(1,2)<<endl;//傳入int類型參數(shù) cout<<add(1.2,3.4)<<endl;//傳入double類型參數(shù) system("pause"); return0;}函數(shù)模板的用法案例代碼函數(shù)模板并不是一個函數(shù)，它只相當(dāng)于一個模子，定義一次即可使用不同類型的參數(shù)來調(diào)用該函數(shù)，這樣做可以減小代碼的書寫，提高代碼的復(fù)用性。使用函數(shù)模板不會減少最終可執(zhí)行程序的大小，因為在調(diào)用函數(shù)模板時，編譯器會根據(jù)調(diào)用時的參數(shù)類型進(jìn)行相應(yīng)的實例化。函數(shù)模板實例化所謂實例化，就是用類型參數(shù)去替換模板中的模板參數(shù)，生成一個具體類型的真正函數(shù)。實例化可分為隱式實例化與顯式實例化。實例化11.1函數(shù)模板隱式實例化是根據(jù)函數(shù)調(diào)用時傳入的數(shù)據(jù)類型確定模板形參T的類型，模板形參的類型是隱式確定的。在例5-1中第一次調(diào)用add()函數(shù)模板時，傳入的是int型數(shù)據(jù)add(1,2)，此時編譯器根據(jù)傳入的實參推演出模板形參類型是int，就會將函數(shù)模板實例化出一個int類型的函數(shù)，如下所示： intadd(intt1,intt2){ returnt1+t2; }隱式實例化11.1函數(shù)模板編譯器生成具體類型函數(shù)的這一過程就稱為實例化，生成的函數(shù)稱為模板函數(shù)。生成int類型的函數(shù)后，再將實參1和2傳入進(jìn)行運算。同理當(dāng)傳入double類型的數(shù)據(jù)時，編譯器先將模板實例化為如下形式的函數(shù)： doubleadd(doublet1,doublet2){ returnt1+t2;}每一次調(diào)用時都會根據(jù)不同的類型實例化出不同類型的函數(shù)，所以最終可執(zhí)行程序的大小并不會減少，它只是提高了程序員對代碼的復(fù)用。隱式實例化11.1函數(shù)模板隱式實例化不能為同一個模板形參指定兩種不同的類型。可以用另一種實例化方式來解決這個問題——顯式實例化。顯式實例化就是顯式的指定函數(shù)模板中的數(shù)據(jù)類型。其語法格式如下所示： template函數(shù)返回值類型函數(shù)名<實例化的類型>(參數(shù)列表);注意這是聲明語句，要以分號結(jié)束，<>中是顯式實例的數(shù)據(jù)類型，即要實例化出一個什么類型的函數(shù)，例如，顯示實例化為int，則在調(diào)用時，不是int類型的數(shù)據(jù)會轉(zhuǎn)換為int類型進(jìn)行計算。例如：add()函數(shù)模板顯式實例化為int類型，代碼如下所示：templateintadd<int>(intt1,intt2);顯式實例化11.1函數(shù)模板usingnamespacestd;template<typenameT>Tadd(Tt1,Tt2){ returnt1+t2;}templateintadd<int>(intt1,intt2);//顯式實例化為int類型intmain(){ cout<<add<int>(10,'B')<<endl;//函數(shù)模板調(diào)用 cout<<add(1.2,3.4)<<endl; system("pause"); return0;}顯示實例化案例11.1函數(shù)模板函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，不同類型的參數(shù)調(diào)用就產(chǎn)生一系列重載函數(shù)。如例5-1中兩次調(diào)用add()函數(shù)模板，編譯時會根據(jù)傳入?yún)?shù)不同實例化出兩個函數(shù)，如下所示： intadd(intt1,intt2)//int類型參數(shù)實例化出的函數(shù){ returnt1+t2;} doubleadd(doublet1,doublet2)//double類型參數(shù)實例化出的函數(shù){ returnt1+t2;}函數(shù)模板重載11.1函數(shù)模板template<typenameT>//定義求兩個任意類型數(shù)據(jù)的最大值Tmax(constT&t1,constT&t2){ returnt1>t2?t1:t2;}template<typenameT>//定義求三個任意類型數(shù)據(jù)的最大值Tmax(constT&t1,constT&t2,constT&t3){ returnmax(max(t1,t2),t3);}intmain(){ cout<<max(1,2,3)<<endl;//調(diào)用三個參數(shù)的函數(shù)模板 cout<<max('a','e')<<endl;//調(diào)用兩個參數(shù)的函數(shù)模板 system("pause"); return0;}函數(shù)模板重載案例11.1函數(shù)模板類模板11.2類模板函數(shù)可以定義模板，對于類來說，也可以定義一個類模板，類模板是針對成員數(shù)據(jù)類型不同的類的抽象，它不是代表一個具體的實際的類，而是一個類型的類，一個類模板可以生成多種具體的類，定義類模板的格式如下所示： template<typename形參名,typename形參名…> class類名{}定義一個類模板并實例化11.2類模板類模板中的關(guān)鍵字含義與函數(shù)模板相同。類模板的模板形參不能為空，一旦聲明了類模板就可以用類模板的形參名聲明類中的成員變量和成員函數(shù)，即可以在類中使用數(shù)據(jù)類型的地方都可以使用模板形參名來聲明。 template<typenameT> classA{ public: Ta; Tb; Tfunc(Ta,Tb);};注意11.2類模板由于類模板包含類型參數(shù)，因此也稱為參數(shù)化類，如果說類是對象的抽象，對象是類的實例，則類模板是類的抽象，類是類模板的實例。定義了類模板后就要使用類模板創(chuàng)建對象以及實現(xiàn)類中的成員函數(shù)，這個過程其實也是類模板實例化的過程，實例化出的具體類稱為模板類。如果用類模板創(chuàng)建類的對象，如用上述定義的模板類A創(chuàng)建對象，則在類A后面跟上一個<>，并在里面表明相應(yīng)的類型，格式如下所示： A<int>a;定義一個類模板并實例化11.2類模板這樣類A中凡是用到模板形參的地方都會被int類型所代替。當(dāng)類模板有兩個模板形參時，創(chuàng)建對象時，類型之間要用逗號分隔開，如定義一個有兩個模板形參的類B，然后用B創(chuàng)建類對象，示例代碼如下所示： template<typenameT1,typenameT2> classB{ public: T1a; T2b; T1func(T1a,T2&b);}; B<int,string>b;//創(chuàng)建模板類B的一個對象定義一個類模板并實例化11.2類模板使用類模板時，必須要為模板形參顯式指定實參，不存在實參推演過程，也就是說不存在將整型值10推演為int類型傳遞給模板形參，必須要在<>中指定int類型，這一點與函數(shù)模板不同。注意11.2類模板模板的聲明或定義只能在全局、命名空間或類范圍內(nèi)進(jìn)行，不能在局部范圍、函數(shù)內(nèi)進(jìn)行，比如不能在main()函數(shù)中聲明或定義一個模板。聲明或定義一個模板還有以下幾點需要注意：如果在全局域中聲明了與模板參數(shù)同名的變量，則該變量被隱藏。模板參數(shù)名不能被當(dāng)作類模板定義中類成員的名字。同一個模板參數(shù)名在模板參數(shù)表中只能出現(xiàn)一次。在不同的類模板聲明或定義中，模板參數(shù)名可以被重復(fù)使用。模板聲明或定義的作用域11.2類模板類模板的成員函數(shù)都是在類的內(nèi)部實現(xiàn)的，類模板的成員函數(shù)可以在類模板的定義中定義(inline函數(shù))，也可以在類模板定義之外定義(此時成員函數(shù)定義前面必須加上template及模板參數(shù))，在類模板外部定義成員函數(shù)的方法如下所示： template<模板形參表>

函數(shù)返回類型類名<模板形參名>::函數(shù)名（參數(shù)列表）｛｝在類模板外部定義成員函數(shù)11.2類模板

template是類模板的聲明，在實現(xiàn)成員函數(shù)時，也要加上類作用域，而且在類名后要用<>指明類的模板形參。例如有下列類模板的定義：

template<typenameT1,typenameT2> classB{ public: T1a; T2b; T1func(T1a,T2&b);};在類模板外部定義成員函數(shù)11.2類模板上述代碼中，如果在類模板外定義類B的成員函數(shù)func()，其實現(xiàn)如下所示：

template<typenameT1,typenameT2> T1B<T1,T2>::func(T1a,T2&b){}在類模板外部定義成員函數(shù)11.2類模板template<typenameT>classCompare{private:

Tt1,t2;public:

Compare(Ta,Tb):t1(a),t2(b){}

Tmax(){returnt1>t2?t1:t2;}

Tmin(){returnt1<t2?t1:t2;}};intmain(){

Compare<int>c1(1,2);//定義int類型的類對象 cout<<"intmax:"<<c1.max()<<endl;

Compare<double>c2(1.2,3.4);//定義double類型的對象 cout<<"doublemin:"<<c2.min()<<endl; return0;}類模板案例實戰(zhàn)STL與容器11.3.1STL簡介STLStandardTemplateLibrary，即標(biāo)準(zhǔn)模板庫，包含了諸多在計算機科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和算法。為C++程序員們提供了一個可擴展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性，極大地提高了軟件編程的效率。

STL的一個重要特點是數(shù)據(jù)結(jié)構(gòu)和算法的分離。例如，由于STL的sort()函數(shù)是完全通用的，可以用它來操作幾乎任何數(shù)據(jù)集合，包括鏈表，容器和數(shù)組。

從邏輯層次來看，在STL中體現(xiàn)了泛型化程序設(shè)計的思想。提倡使用現(xiàn)有模板開發(fā)應(yīng)用程序，將算法和數(shù)據(jù)結(jié)構(gòu)分離，大部分算法獨立于與之對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，是一種軟件的復(fù)用技術(shù)。從實現(xiàn)層次看，整個STL是以一種類型參數(shù)化的方式實現(xiàn)的，是一個基于模板的標(biāo)準(zhǔn)類庫。概念：

特點：11.3.1STL簡介8.1STL簡介STL容器（container）算法（algorithm）迭代器（iterator）通用的數(shù)據(jù)結(jié)構(gòu)，承載不同類型的數(shù)據(jù)對象。獨立與數(shù)據(jù)對象的常用數(shù)據(jù)處理方法，以函數(shù)模板實現(xiàn)的。指向容器中數(shù)據(jù)對象的指針，通過迭代器訪問數(shù)據(jù)元素，是容器和算法連接的紐帶。

序列式容器11.3.2序列式容器序列容器也叫順序容器，用于存儲線性表類型的數(shù)據(jù)結(jié)構(gòu)，有連續(xù)存儲和鏈?zhǔn)酱鎯煞N存儲方式。11.3.2序列式容器向量,連續(xù)存儲，動態(tài)數(shù)組同義詞，動態(tài)擴展與收縮，可以隨機存取元素（用[]運算符存?。膊刻砑踊蛞瞥胤浅？焖佟５窃谥胁炕蝾^部安插元素比較費時。頭文件<vector>

序列式容器主要有三種：vector、deque、listvector雙向鏈表，鏈?zhǔn)酱鎯?，不提供隨機存取，插入刪除迅速。頭文件<list>雙端隊列,可以隨機存取元素，數(shù)組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費時。頭文件<deque>

Deque:

List11.3.2序列式容器函數(shù)含義front();back()返回容器頭部元素的引用;返回容器尾部元素的引用push_back()將元素val插入到尾部，無返回值pop_back()刪除尾部的元素，無返回值begin(),end()然后容器前端和尾部的迭代器（指針）insert()向容器中插入元素erase()刪除容器中間元素vecktor存儲結(jié)構(gòu)示意圖intmain(){ vector<char>v; //創(chuàng)建空的vector容器v v.insert(v.begin(),'a'); //在頭部位置插入元素a v.insert(v.begin(),'b'); //在頭部位置插入元素b v.insert(v.begin(),'c'); //在頭部位置插入元素c v.insert(v.begin()+1,5,'t'); //在v.begin()+1位置插入5個元素t for(inti=0;i<8;i++) //輸出容器v中的元素 cout<<v[i]<<"";

v.erase(v.begin()+1,v.begin()+6); //刪除5個元素 for(inti=0;i<3;i++) //輸出容器v中的元素 cout<<v[i]<<""; return0;

}程序運行結(jié)果為：ctttttbacba11.3.2序列式容器元素位置取決于特定的排序準(zhǔn)則，和插入順序無關(guān)，set、multiset、map、multimap等。Set/Multiset

:集合。內(nèi)部的元素依據(jù)其值自動排序，Set存儲無重復(fù)的數(shù)據(jù)元素，Multisets允許存儲重復(fù)的元素，內(nèi)部由二叉樹實現(xiàn)，便于查找。Map/Multimap

:映射。Map的元素是成對的鍵值/實值，內(nèi)部的元素依據(jù)其值自動排序，Map內(nèi)的元素不允許重復(fù)，Multimaps內(nèi)元素允許重復(fù)，內(nèi)部由二叉樹實現(xiàn)，便于查找；容器類自動申請和釋放內(nèi)存，無需new和delete操作。11.3.3關(guān)聯(lián)性容器11.3.4適配器容器容器適配器是一個封裝了序列容器的類模板，它在一般序列容器的基礎(chǔ)上提供了一些不同的功能。之所以稱作適配器類，是因為它可以通過適配容器現(xiàn)有的接口來提供不同的功能。本章將介紹3種容器適配器，分別是stack、queue、priority_queue：stack<T>：是一個封裝了deque<T>容器的適配器類模板，默認(rèn)實現(xiàn)的是一個后入先出（Last-In-First-Out，LIFO）的壓入棧。stack<T>模板定義在頭文件stack中。queue<T>：是一個封裝了deque<T>容器的適配器類模板，默認(rèn)實現(xiàn)的是一個先入先出（First-In-First-Out，LIFO）的隊列?？梢詾樗付ㄒ粋€符合確定條件的基礎(chǔ)容器。queue<T>模板定義在頭文件queue中。priority_queue<T>：是一個封裝了vector<T>容器的適配器類模板，默認(rèn)實現(xiàn)的是一個會對元素排序，從而保證最大元素總在隊列最前面的隊列。priority_queue<T>模板定義在頭文件queue中。11.3.4適配性容器

stack存儲的元素具有后進(jìn)先出的特點，存儲結(jié)構(gòu)如下圖。

函數(shù)含義top()返回棧頂元素的引用，即最后一個進(jìn)入stack容器適配器的元素push(val)將元素val插入到棧頂，無返回值pop()刪除棧頂?shù)脑?，無返回值swap(s1,s2)交換兩個stack容器中的元素，是非成員函數(shù)重載(C++11)11.3.4適配性容器queue容器適配器是一個先進(jìn)先出(FIFO)的存儲結(jié)構(gòu)，具有隊列的特點。容器中的元素只能從一端使用push()函數(shù)進(jìn)行插入，從另一端使用pop()函數(shù)進(jìn)行刪除,queue容器適配器不允許一次插入或刪除多個元素，且不支持迭代器方法如begin()、rbegin()等。11.3.5經(jīng)典案例11.3.5經(jīng)典案例11.3.5經(jīng)典案例11.3.5經(jīng)典案例

泛型算法傳統(tǒng)的程序設(shè)計中，算法與數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)緊密耦合，缺乏通用性。STL倡導(dǎo)泛型編程，實現(xiàn)容器（數(shù)結(jié)結(jié)構(gòu)）與算法分離，即同一算法適用不同的容器和數(shù)據(jù)類型，成為通用算法，即泛型算法。可以最大限度地節(jié)省源代碼資源。因此比傳統(tǒng)的函數(shù)庫或類庫具有通用性。11.4.1算法概述STL中提供的所有算法都包含在三個頭文件中：<algorithm>、<numeric>、<functional>?！?/p>

algorithm是最大的一個頭文件，它由一大堆函數(shù)模板組成，其中涉及到的功能有比較、交換、查找、遍歷、復(fù)制、修改、刪除、合并、排序等。●

頭文件numeric很小，只包括幾個在序列中進(jìn)行簡單數(shù)學(xué)運算的函數(shù)模板，以及加法和乘法在序列中的一些操作?！?/p>

頭文件functional中則定義了一些類模板，用于聲明一些函數(shù)對象。11.4.2常用算法1.for_each()算法函數(shù)原型定義如下所示：template<typenameInputIterator,typenameFunction>for_each(InputIteratorbegin,InputIteratorend,Functionfunc);for_each()算法對[begin,end)區(qū)間中的每個元素都調(diào)用func函數(shù)（對象）進(jìn)行操作，它不會對區(qū)間中的元素做任何修改，也不會改變原來序列的元素次序。11.4.2常用算法2.find()算法find()函數(shù)原型如下所示：template<typenameInputIterator,typenameT>InputIteratorfind(InputeIterator

first,

InputIteratorlast,constT&value);find()算法用于在[begin,last)區(qū)間查找value元素是否存在，如果存在，就返回指向這個元素的迭代器，如果不存在，就返回end。11.4.2常用算法3.copy()算法函數(shù)原型如下所示：template<typenameInputIterator,typenameOutputIterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputIteratorDestBeg);copy()函數(shù)實現(xiàn)將[first,last)區(qū)間的元素復(fù)制到另一個地方，這個地方的起始位置為DestBeg。11.4.2常用算法4.sort()算法sort()屬于可變序列算法，它支持對容器中的所有元素進(jìn)行排序。函數(shù)的原型有如下兩種形式：template<typenameRanIt>

//第一種形式，默認(rèn)為升序voidsort(RanItfirst,RanItlast);template<typenameRanIt,typenamePred>

//第二種形式,指定排序規(guī)則voidsort(RanItfirst,RanItlast,Predop);注意：sort()算法只支持隨機迭代器，只能適用于vector與deque容器；

list容器不支持隨機迭代器，只能使用sort()成員函數(shù)，用于自身的元素排序。11.4.2常用算法5.accumulate()算法accumulate()算法屬于數(shù)值算法，它的原型如下所示：template<typenameInputIterator,typenameT>

//第一種形式Taccumulate(InputIteratorfirst,InputIteratorlast,Tt);template<typenameInputIterator,typenameT,typenamePred>

//第二種形式Taccumulate(InputIteratorfirst,InputIteratorlast,Tt,Predop);accumulate()函數(shù)的功能是將[first,last)區(qū)間內(nèi)的數(shù)值累加，累加的初始值為t，它的返回值是元素累加結(jié)果。第二種形式可以按照指定的規(guī)則將元素相加。11.4.3程序舉例classMulti{ //類模板private:

Tvalue;public: Multi(constT&v):value(v){} //構(gòu)造函數(shù) voidoperator()(T&elem)const{elem*=value;}//重載()運算符};voidprint(intelem){ //打印元素 cout<<elem<<"";}11.4.3程序舉例intmain(){

intarr[]={21,4,55,22,46,79,9,5,78,34,100};

vector<int>v;

v.assign(arr,arr+sizeof(arr)/sizeof(int)); //用數(shù)組給v容器賦值

//調(diào)用for_each()函數(shù)將容器中每個元素都乘以2

for_each(v.begin(),v.end(),Multi<int>(2));//調(diào)用copy()構(gòu)造函數(shù)將容器中元素輸出

copy(v.begin(),v.end(),ostream_iterator<int>(cout,""));

cout<<endl;

//調(diào)用find()算法查找容器中是否存在值為200的元素

vector<int>::iteratorit=find(v.begin(),v.end(),200);11.4.3程序舉例if(*it==200)

cout<<"容器中有值為200的元素"<<endl;else

cout<<"容器中不存在值為200的元素"<<endl;

sort(v.begin(),v.end());//調(diào)用sort()算法將容器中元素從小到大排列

cout<<"排序之后："<<endl;

copy(v.begin(),v.end(),ostream_iterator<int>(cout,""));

cout<<endl;

intsum=accumulate(v.begin(),v.end(),0);//累加容器中元素

cout<<"sum="<<sum<<endl;

return0;}

案例實戰(zhàn)與實訓(xùn)11.5案例實戰(zhàn)與實訓(xùn)數(shù)組函數(shù)模板。分別編寫一個數(shù)組元素輸入函數(shù)模板、數(shù)組元素求和函數(shù)模板和數(shù)組元素輸出的函數(shù)模板，函數(shù)參數(shù)為數(shù)組名，長度。編寫主程序，檢驗各種類型的輸入、求和和輸出。案例