1、1第第14章章 標(biāo)準(zhǔn)模板庫(kù)標(biāo)準(zhǔn)模板庫(kù)C+語(yǔ)言程序設(shè)計(jì)中山大學(xué)信息科學(xué)與技術(shù)學(xué)院2主要內(nèi)容nSTL（Standard Template Library）n迭代器n容器n泛型算法31、STLn容器（container）：包含數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)n元素n棧、鏈表n迭代器（iterator）：相當(dāng)于指向元素對(duì)象的指針n算法（algorithm）：在各種容器中通用的標(biāo)準(zhǔn)算法n排序，插入42、迭代器n指針的抽象，一般化的指針n標(biāo)準(zhǔn)庫(kù)迭代器類別n輸入迭代器n輸出迭代器n正向迭代器n雙向迭代器n隨機(jī)訪問(wèn)迭代器所支持的操作不同（P371 表14-1）52、迭代器（續(xù)）n不同類型容器中定義的迭代器屬于不同的類別nvec

2、tor容器和deque容器的迭代器是隨機(jī)訪問(wèn)迭代器nlist容器的迭代器是雙向迭代器n關(guān)聯(lián)容器的迭代器是雙向迭代器n容器適配器不支持迭代器n算法對(duì)作為參數(shù)的迭代器的類別要求63、容器n順序容器（sequential container ）n按位置存儲(chǔ)和訪問(wèn)元素n關(guān)聯(lián)容器（associative container ）n元素按鍵（關(guān)鍵字）排序n容器適配器（container adaptor ）n使某種容器以另一種抽象類型的方式工作容器元素必須支持復(fù)制和賦值操作73、容器（續(xù)）n順序容器nvectorn在尾端插入和刪除 n支持隨機(jī)訪問(wèn) nListn雙鏈表，可在任意位置快速插入和刪除 nDequen

3、雙端隊(duì)列n在頭端和尾端快速插入和刪除n支持隨機(jī)訪問(wèn) 83、容器（續(xù)）n順序容器（續(xù)）n容器對(duì)象的定義及初始化(P371 表14-3)nC c; nC c(cx); nC c(b, e); nC c(n, t); nC c(n); 93、容器（續(xù)）n順序容器（續(xù)）n容器中定義的類型別名(P373 表14-4)niterator nsize_type nconst_iterator nreverse_iterator nconst_reverse_iterator ndifference_type nvalue_type nreference nconst_reference 103、容器（續(xù)）n

4、順序容器（續(xù)）n元素訪問(wèn)操作(P374 表14-5)nc.back() nc.front() ncindex nc.at(index) list無(wú)若index無(wú)效，則at操作會(huì)拋出out_of_range異常113、容器（續(xù)）n順序容器（續(xù)）n獲取迭代器的操作(P375 表14-6)nc.begin() nc.end() nc.rbegin() nc.rend 注：const容器對(duì)象的對(duì)應(yīng)迭代器為const_迭代器（只讀迭代器）123、容器（續(xù)）n順序容器（續(xù)）n增加元素的操作(P376 表14-7)nc.insert(iter, t) nc.insert(iter, n, t) nc.ins

5、ert(iter, b, e) nc.push_back(t) nc.push_front(t) 在iter所指元素前插入vector無(wú)133、容器（續(xù)）n順序容器（續(xù)）n刪除元素的操作(P378 表14-8)nc.clear() nc.erase(iter) nc.erase(b, e) nc.pop_back() nc.pop_front(t) vector無(wú)143、容器（續(xù)）n順序容器（續(xù)）n容器比較操作(P380 表14-9)n= n!= n nn= 結(jié)果取決于第一對(duì)不相等的對(duì)應(yīng)元素153、容器（續(xù)）n順序容器（續(xù)）n容器大小相關(guān)操作(P382 表14-10)nc.empty() nc

6、.size() nc.max_size() nc.resize(n) nc.resize(n, t) 163、容器（續(xù)）n順序容器（續(xù)）n容器的賦值與交換(P383 表14-11)nc1 = c2 nc.assign(b, e) nc.assign(n, t) nc1.swap(c2) 不移動(dòng)元素先刪除，再?gòu)?fù)制插入173、容器（續(xù)）n關(guān)聯(lián)容器n特點(diǎn)：通過(guò)鍵對(duì)元素進(jìn)行存儲(chǔ)和訪問(wèn)n標(biāo)準(zhǔn)庫(kù)關(guān)聯(lián)容器nmapnmultimapnsetnmultiset元素類型為pair類型（鍵-值對(duì)）以鍵本身為元素183、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）npair類型n中定義的模板類n具有兩個(gè)公有成員：first和secon

7、dn創(chuàng)建pair對(duì)象npair p npair p(v1, v2) nmake_pair(v1, v2) n比較pair對(duì)象nn=標(biāo)準(zhǔn)庫(kù)函數(shù)193、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nmap容器nmap對(duì)象的定義及初始化 nmap m; nmap m(mx); nmap m(b, e); nmap容器中定義的類型別名n表14-4nkey_typenmapped_typenvalue_typepair類型類型K必須提供操作203、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nmap容器（續(xù)）n訪問(wèn)元素 n使用下標(biāo)n下標(biāo)類型與鍵類型相同n副作用：導(dǎo)致增加新元素 n使用迭代器 213、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nmap容器（

8、續(xù)）n增加元素 n使用下標(biāo)n使用insert操作 nm.insert(e) nm.insert(iter, e)nm.insert(begin, end) 鍵已存在，則不插入223、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nmap容器（續(xù)）n查找元素 nm.find(k)-返回指向k對(duì)應(yīng)元素的迭代器nm.count(k) -返回k在m中出現(xiàn)的次數(shù)n刪除元素nm.erase(k) nm.erase(iter) nm.erase(b, e) 233、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nmultimap容器（續(xù)）n鍵可以重復(fù)n注意與map容器的操作區(qū)別nm.lower_bound(k) nm.upper_bound(k)

9、 nm.equal_range(k) k不存在，則返回指向插入位置的迭代器243、容器（續(xù)）n關(guān)聯(lián)容器（續(xù)）nset容器n元素不是pair對(duì)象，而是鍵本身n不支持下標(biāo)操作nmultiset容器n鍵可以重復(fù)n注意與set容器的操作區(qū)別k不存在，則返回指向插入位置的迭代器254、容器適配器n基于順序容器實(shí)現(xiàn)nstacknqueuenpriority_dequen可根據(jù)基礎(chǔ)容器創(chuàng)建對(duì)象并初始化nA a(c)默認(rèn)用deque實(shí)現(xiàn)默認(rèn)用vector實(shí)現(xiàn)基礎(chǔ)容器對(duì)象適配器類型264、容器適配器（續(xù)）nstack典型操作npush(item)npop()ntop()nempty()nsize()274、容器

10、適配器（續(xù)）nqueue典型操作npush(item)npop()nfront()nback()nempty()nsize()284、容器適配器（續(xù)）npriority_queue典型操作npush(item)npop()ntop()nempty()nsize()29例bool palindrome(const string& text) / 功能：判斷文本text是否為回文/ 后置條件：若text為回文，則返回值為true；否則返回值為false stack cstack;size_t length = text.size();for (size_t i = 0; i length/

11、2; i+) / 文本text的前半部分入棧cstack.push(texti);/ 將文本text的后半部分逐個(gè)字符與前半部分的對(duì)應(yīng)字符進(jìn)行比較size_t comparePos;/ 比較位置/ 設(shè)定比較起點(diǎn)if (length % 2 = 0)comparePos = length / 2;elsecomparePos = length / 2 + 1;while (!cstack.empty() if (textcomparePos != cstack.top() / 對(duì)應(yīng)字符不相同break;cstack.pop();/ 對(duì)應(yīng)字符出棧comparePos+;/ 比較位置后移一個(gè)字符if

12、 (cstack.empty()/ 所有對(duì)應(yīng)字符都相同return true;elsereturn false;305、泛型算法n作用n對(duì)容器中的元素進(jìn)行某些一般性處理n特點(diǎn)n與具體容器類型無(wú)關(guān)n一般不依賴于元素類型n要求元素類型支持比較操作315、泛型算法（續(xù)）n分類n不修改序列的算法（non-modifying sequence algorithm）n變更序列的算法（mutating-sequence algorithm） n排序及相關(guān)算法（sorting and related algorithm） n泛化算術(shù)算法（generalized numeric algorithm） 325、泛

13、型算法（續(xù)）n形參規(guī)范nalg (first, last, otherParms);nalg (first, last, result, otherParms);nalg (first, last, first2, otherParms);nalg (first, last, first2, last2, otherParms);迭代器迭代器 valuecomp(比較函數(shù))pred(測(cè)試函數(shù))宜使用插入迭代器335、泛型算法（續(xù)）n使用插入迭代器調(diào)用算法 n標(biāo)準(zhǔn)庫(kù)插入迭代器類型ninsert_iterator 調(diào)用容器的insertnfront_insert_iterator 調(diào)用容器的pus

14、h_frontnback_insert_iterator 調(diào)用容器的push_backn創(chuàng)建插入迭代器的標(biāo)準(zhǔn)庫(kù)函數(shù)ninserter nfront_inserter nback_inserter 接受一個(gè)容器參數(shù)和一個(gè)指向插入起始位置的迭代器 例：P406，CoustomerManager:find的實(shí)現(xiàn)無(wú)須考慮目標(biāo)容器的容量345、泛型算法（續(xù)）n使用函數(shù)對(duì)象調(diào)用算法 n函數(shù)對(duì)象n是類對(duì)象n該類重載了函數(shù)調(diào)用操作符()n() 的形參個(gè)數(shù)與算法要求其pred形參所帶的形參個(gè)數(shù)一樣n需要增加的其他參數(shù)以類的數(shù)據(jù)成員的形式存在例：P403:class NoMatch及P406：CoustomerM

15、anager:find的實(shí)現(xiàn)突破算法對(duì)形參pred的參數(shù)限制35class BetweenCls public:BetweenCls(int ival1, int ival2): lowerBound(ival1), upperBound(ival2)bool operator() (const int& ival)/重載函數(shù)調(diào)用操作符return (ival lowerBound & ival upperBound);private:int lowerBound, upperBound;例使用形式：count_if(ivec.begin(), ivec.end(), BetweenCls(3, 5);count_if(ivec2.begin(), ivec2.end(), BetweenCls(8, 13)