第12章C++標(biāo)準(zhǔn)模板庫

1、第十二章 C+標(biāo)準(zhǔn)模板庫內(nèi)蒙古科技大學(xué)12.1 C+標(biāo)準(zhǔn)模板庫簡(jiǎn)介標(biāo)準(zhǔn)模板庫簡(jiǎn)介 nC+標(biāo)準(zhǔn)模板庫（Standard Template Library）是C+標(biāo)準(zhǔn)程序庫的核心內(nèi)容。它是使用了泛型技術(shù)的模板庫，可以很方便地使用高效的算法來處理數(shù)據(jù)。STL對(duì)于程序原來說是可以實(shí)現(xiàn)多種數(shù)據(jù)結(jié)構(gòu)功能的類的集合，以及在這些類中可以實(shí)現(xiàn)的多種算法的總和。模板技術(shù)使得STL可以處理任意的數(shù)據(jù)類型。STL的基本觀念是實(shí)現(xiàn)數(shù)據(jù)與操作的分離。STL的目的是標(biāo)準(zhǔn)化組件，這樣就不用重新開發(fā)，可以使用現(xiàn)成的組件。nSTL被內(nèi)建在你的編譯系統(tǒng)之內(nèi)。STL的版本很多，常見的有HP STL、PJ STL、 SGI STL等。

2、n在C+標(biāo)準(zhǔn)中，STL被組織為下面的13個(gè)頭文件：、和。12.2 C+標(biāo)準(zhǔn)模板庫概述標(biāo)準(zhǔn)模板庫概述nSTL由六部分組成，它們分別是容器（Container），迭代器（Iterators），算法（Algorithms），空間配置器（Allocator），配接器（Adaptors）和仿函數(shù)（Functors）。其中容器，迭代器和算法是STL的核心內(nèi)容。n容器（Container）是管理某類對(duì)象的集合。STL里面有多種容器類型，每種類型的容器都有自身的優(yōu)缺點(diǎn)，程序員可以根據(jù)具體需要來選擇適合自己程序的容器類型。n迭代器（Iterators）是類似于C+中的指針，可以對(duì)一組對(duì)象集合執(zhí)行遍歷操作。通過使

3、用一組公共接口，迭代器可以很方便的找到這組對(duì)象集合的下一個(gè)元素。查找下一個(gè)對(duì)象元素的具體內(nèi)容取決于對(duì)象集合的具體類型。每種容器都提供了自己的迭代器，通過使用相應(yīng)的迭代器，可以很方便地對(duì)容器中的元素進(jìn)行正確的遍歷。n算法（Algorithms）用來處理對(duì)象集合中的所有元素。其中包含了對(duì)群集元素的查找、排序、修改以及使用等。通過使用迭代器，我們寫一次算法，就可以把它應(yīng)用到所有容器上面（所有容器的迭代器的接口是一致的）。通過使用自定義的輔助函數(shù)可以實(shí)現(xiàn)更靈活的算法實(shí)現(xiàn)。nSTL的思想是實(shí)現(xiàn)數(shù)據(jù)和操作的分離。數(shù)據(jù)統(tǒng)一保存在容器中來管理，而操作則是由可定制的算法來規(guī)定。迭代器將容器和算法聯(lián)系起來，起著一

4、種粘合劑的作用。幾乎所有的算法都是通過迭代器操作容器中的元素來工作的。nSTL中的每一部分都可以處理任意一種數(shù)據(jù)類型，這歸功于模板（Template）技術(shù)的運(yùn)用。STL是泛型編程中的一個(gè)出色的范例。nSTL中還可以使用配接器（adaptors）和仿函數(shù)（functors）等更加泛型化的組件。它們可以進(jìn)一步調(diào)整算法來適應(yīng)特定的需求。12.2 C+標(biāo)準(zhǔn)模板庫概述標(biāo)準(zhǔn)模板庫概述n容器時(shí)管理某類對(duì)象的集合，STL根據(jù)不同的需要提供了不同的容器。從總體上，容器可以分為序列式容器和關(guān)聯(lián)式容器。n序列式容器： STL內(nèi)部定義好了三種序列式容器，它們分別是Vectors，Deques和Lists： Vecto

5、rs: Vector容器使用起來相當(dāng)于一個(gè)動(dòng)態(tài)增長的數(shù)組。它可以隨機(jī)進(jìn)行存取，也就是向數(shù)組一樣通過索引來訪問任意一個(gè)元素。在它的尾部增加和刪除元素都很快速，但是在它的頭部和中部插入元素就比較耗時(shí)，因?yàn)椴迦胄略睾螅略睾竺娴拿總€(gè)元素都要向后移動(dòng)一位。12.3 容器容器【例12-1】vector容器使用舉例。/*12-1.cpp*/#include #include /包含vector的頭文件using namespace std; int main() vector ivec; / 實(shí)例化一個(gè)裝載int類型的vector容器 int i;/ 向容器中加入數(shù)字1到5 for ( i=1; i=

6、5; i+) ivec.push_back(i); / 打印出vector中的所有元素，以空格隔開 for (i=0; iivec.size(); i+) cout iveci ; cout endl;return 0;nDeques: Deque容器使用起來類似Vector，它的長度也是動(dòng)態(tài)增長的。它與Vector的區(qū)別在與它可以向兩端增長，在它頭部和尾部安插元素都很快速，只是在中部插入元素比較費(fèi)時(shí)。【例12-2】deque容器使用舉例。/*12-2.cpp*/#include #include /包含deque容器的頭文件using namespace std;int main() deq

7、ue ddeq; / 實(shí)例化一個(gè)裝載double類型的容器ddeq int i;for (i=1; i=5; +i) /向deque插入1到5的1.5倍的實(shí)數(shù)值 ddeq.push_front(i*1.5); / 從容器的前面進(jìn)行插入操作 for (i=0; iddeq.size(); +i) /打印出容器中的所有元素，并且以空格隔開 cout ddeqi ; cout endl; return 0;nLists: List容器是通過雙向鏈表實(shí)現(xiàn)的。其中的每個(gè)元素都作為鏈表的一個(gè)結(jié)點(diǎn)，List不支持隨機(jī)存取，但是對(duì)List中的元素進(jìn)行插入和刪除操作非?？旖??！纠?2-3】 list容器使用舉例

8、。#include #include /加入包含list容器的頭文件using namespace std;int main() list ilist;/實(shí)例化一個(gè)裝載int類型的list容器 int i; for ( i=1; i=5; i+) /在list的尾部加入1到5 ilist.push_back(i); while (! ilist.empty() /輸出list中所有元素的值 cout ilist.front() ; /輸出頭元素的值 ilist.pop_front(); /刪除頭元素 cout endl; return 0;n關(guān)聯(lián)式容器關(guān)聯(lián)式容器 關(guān)聯(lián)式容器根據(jù)自身的排序準(zhǔn)則，

9、自動(dòng)對(duì)其中的元素進(jìn)行排序。關(guān)聯(lián)式容器的內(nèi)部實(shí)現(xiàn)通常都采用二叉樹的形式。排序準(zhǔn)則通過定義排序函數(shù)來實(shí)現(xiàn)。STL在默認(rèn)情況下使用運(yùn)算符operator來訪問它們。 (2) Operator +: 類似于指針操作，將迭代器指向下一個(gè)元素。 (3) Operator =和Operator !=: 判斷兩個(gè)迭代器是否指向同一個(gè)位置。 (4) Operator =: 為迭代器進(jìn)行賦值操作。12.4 迭代器迭代器n迭代器分類 所有的容器提供了一些相同的公共接口，使得我們可以獲取迭代器的并對(duì)容器中的元素進(jìn)行訪問和遍歷等操作。其中尤為常用的成員函數(shù)是begin()和end()。 (1) begin(): 函數(shù)返

10、回一個(gè)迭代器，指向容器的起始位置。 (2) end(): 函數(shù)返回一個(gè)迭代器，指向容器的最后一個(gè)元素的后一位。begin()和end()形成了一個(gè)半閉開區(qū)間，迭代器從begin()訪問到end()-1就可以完成對(duì)容器中所有元素的遍歷?！纠?2-4】使用迭代器遍歷list容器中的元素。/*12-4.cpp*/#include #include using namespace std;int main() list ilist; /實(shí)例化一個(gè)裝載int類型的list容器 int i; for (i=1;i=5;i+) /在list的尾部加入1到5 ilist.push_back(i); list:

11、iterator pos; for (pos = ilist.begin(); pos != ilist.end(); +pos) cout *pos ; /使用迭代器輸出容器 中所有元素的值 cout endl;return 0;12.4 迭代器迭代器n迭代器分類 迭代器在基本操作的基礎(chǔ)上，會(huì)根據(jù)它指向容器的具體類型擁有其它能力。例如，如果容器支持隨機(jī)訪問（vectors，deques），那么迭代器也可以進(jìn)行隨機(jī)操作。容器的迭代器都屬于如下兩類：(1) 雙向迭代器（Bidirectional iterator）：雙向迭代器可以通過遞增遞減運(yùn)算來實(shí)現(xiàn)前進(jìn)后退操作。lists，maps，mult

12、imaps，sets和multisets提供雙向迭代器。(2) 隨機(jī)存取迭代器（Random access iterator）：隨機(jī)存取迭代器在雙向迭代器的基礎(chǔ)上還具有隨機(jī)訪問容器元素的能力。你可以通過索引來查找訪問容器中的任意一個(gè)元素。vectors和deques提供隨機(jī)存取迭代器。12.5 算法算法 為了對(duì)容器內(nèi)的元素進(jìn)行處理，STL中以全局函數(shù)的形式提供了一些標(biāo)準(zhǔn)算法，方向覆蓋了排序、修改、查找、拷貝、數(shù)值運(yùn)算等常用算法。算法函數(shù)都定義在頭文件里面。 通過與迭代器結(jié)合使用，STL中的算法只需定義一次，就可以在所有具備使用條件的容器上使用，非常的方便。算法甚至可以用在用戶自定義的容器上面，

13、這使得代碼復(fù)用率大大提高，同時(shí)提高了STL的彈性和能力。12.5 算法算法n區(qū)間的概念 算法都是用來處理一個(gè)或多個(gè)區(qū)間中的元素。這個(gè)區(qū)間可以包含容器中的所有元素。為了確定被算法處理的區(qū)間范圍，我們需要把區(qū)間的首尾作為參數(shù)傳給算法函數(shù)。所有的算法使用的都是半閉開區(qū)間，包含起始元素不包含最后一個(gè)元素。【例12-5】使用STL中的全局算法函數(shù)對(duì)容器中指定區(qū)間元素進(jìn)行處理/*12-5.cpp*/#include #include /引入包含vector容器的頭文件#include /引入包含算法函數(shù)的頭文件using namespace std;int main() vector ivec; /實(shí)例化

14、一個(gè)裝載int類型的vector容器 vector:iterator pos; /實(shí)例化一個(gè)上述容器類型的迭代器 ivec.push_back(2); /亂序向ivec尾部插入1到5 ivec.push_back(5); ivec.push_back(4); ivec.push_back(3); ivec.push_back(1); /查找容器中的最小元素和最大元素并進(jìn)行輸出 pos = min_element (ivec.begin(), ivec.end(); cout min: *pos endl; pos = max_element (ivec.begin(), ivec.end();

15、 cout max: *pos endl; /使用STL中的sort函數(shù)對(duì)于整個(gè)容器中的元素進(jìn)行排序 sort (ivec.begin(), ivec.end(); /使用STL中的find函數(shù)查找容器中第一個(gè)值為3元素 pos = find (ivec.begin(), ivec.end(), 3); / 區(qū)間（從起始到結(jié)尾） / 要查找的值 /使用STL中的reverse函數(shù)將找到的第一個(gè)是3的元素到最后的元素進(jìn)行逆序 reverse (pos, ivec.end(); /打印出容器中所有元素的值 for (pos=ivec.begin(); pos!=ivec.end(); +pos)

16、cout *pos ; cout endl; return 0;12.5 算法算法n多區(qū)間處理 有的算法可以同時(shí)處理多個(gè)區(qū)間，對(duì)于第一個(gè)區(qū)間，算法通常需要它的起點(diǎn)和終點(diǎn)作為參數(shù)，而對(duì)于其它區(qū)間來說，通常算法只知道它們的起點(diǎn)即可。在執(zhí)行算法是，需要保證第二個(gè)（或者其它）區(qū)間擁有元素的個(gè)數(shù)至少和第一個(gè)區(qū)間相同，否則會(huì)發(fā)生錯(cuò)誤?！纠?2-6】使用STL中的全局算法函數(shù)對(duì)容器中指定區(qū)間元素進(jìn)行處理/*12-6.cpp*/#include#include #include #include using namespace std;int main() list ilist; vector ivec; i

17、nt i; for (i=1; i=5; +i)/把數(shù)值1到5插入的容器ilist的尾部 / 下面注釋掉的代碼如果被調(diào)用會(huì)因?yàn)楦膶懳粗獌?nèi)存引發(fā)運(yùn)行時(shí)錯(cuò)誤/ copy (ilist.begin(), ilist.end(), / 源區(qū)間/ ivec.begin(); / 目標(biāo)區(qū)間ivec.resize(ilist.size(); /使ivec的大小等于ilist/拷貝ilist中的元素到ivec中copy (ilist.begin(), ilist.end(), / 源區(qū)間 ivec.begin(); / 目標(biāo)區(qū)間for (i=0;iivec.size();i+)coutiveci ; /遍歷容

18、器ivec并輸出所有元素coutendl;return 0;12.6 配接器配接器 配接器可以看成一種特殊的迭代器，它可以輔助迭代器實(shí)現(xiàn)更強(qiáng)大的功能。常見的配接器有安插型迭代器、流迭代器和逆向迭代器等類型。(1) 安插型迭代器（Insert Iterators）可以使算法對(duì)容器插入元素，通過它可以解決算法對(duì)應(yīng)目標(biāo)區(qū)間空間不足的問題。它可以使目標(biāo)區(qū)間大小按照需要來增長。(2) 流迭代器（Stream Iterators）是用來讀寫流（stream）的迭代器。它可以把輸出的內(nèi)容重新定位到文件中或者屏幕上。(3) 逆向迭代器（Reverse Iterators）以逆向的方式來進(jìn)行一般迭代器的操作。適

19、用于逆序訪問容器中的元素?！纠?2-7】安插型迭代器使用舉例/*12-7.cpp*/#include #include #include #include #include using namespace std;int main() list ilist;/ 將數(shù)字1-5插入到list容器中for (int i=1; i=5; i+) ilist.push_back(i); / 在vector容器尾部插入ilist中的元素vector ivec; copy (ilist.begin(), ilist.end(), / 源區(qū)間back_inserter(ivec); / 目標(biāo)位置vector:

20、iterator iterv;/使用迭代器遍歷輸出ivec中的元素 for (iterv=ivec.begin();iterv!=ivec.end();iterv+)cout*iterv ; coutendl; / 在deque容器的頭部插入ilist中的元素 deque ideq;copy (ilist.begin(), ilist.end(), / 源區(qū)間front_inserter(ideq); / 目標(biāo)位置deque:iterator iterd;/使用迭代器遍歷輸出ideq中的元素for (iterd=ideq.begin();iterd!=ideq.end();iterd+)cout*iterd ;coutendl;12.7 仿函數(shù)仿函數(shù) 仿函數(shù)是一個(gè)行為類似函數(shù)的對(duì)象。我們創(chuàng)建一個(gè)類的時(shí)候可以使用運(yùn)算符重載技術(shù)來重載運(yùn)算符operator()，這樣這個(gè)類的對(duì)象的行為就會(huì)類似函數(shù)，它也可以被當(dāng)成函數(shù)來使用。因?yàn)榉潞瘮?shù)是某個(gè)類的對(duì)象，所以每個(gè)仿函數(shù)都有自己的具體類型。在實(shí)現(xiàn)的過程中，仿函數(shù)通常比一般函數(shù)速度快。 STL中包含了許多預(yù)先定義的仿函數(shù)，我們可以通過其中用來做排序準(zhǔn)則的less來學(xué)習(xí)仿函數(shù)的使用。【例12-8】仿函數(shù)使用舉例/*12-8.c