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

1、C+語言程序設(shè)計（第4版）第十章 泛型程序設(shè)計 與C+標(biāo)準(zhǔn)模板庫清華大學(xué) 鄭 莉C+語言程序設(shè)計（第4版），鄭莉，清華大學(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 綜合實(shí)例對個人銀行賬戶管理程序的改進(jìn)10.9 深度探索10.10 小結(jié)2C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.1.1 泛型程序設(shè)計的基本概念 編寫不依賴于具體數(shù)據(jù)類型的程序 將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的 C+的模板為泛型程序設(shè)計奠定了關(guān)鍵的基礎(chǔ) 幾個術(shù)語 概念（concept）：用來界定

2、具備一定功能的數(shù)據(jù)類型，如“支持運(yùn)算符”的數(shù)據(jù)類型構(gòu)成Comparable這一概念； 模型（model）：符合一個概念的數(shù)據(jù)類型稱為該概念的模型，如int型是Comparable概念的模型。 為概念賦予一個名稱，并使用該名稱作為模板參數(shù)名例如，我們將用這樣的方式表示insertionSort這樣一個函數(shù)模板的原型：template void insertionSort(Sortable a, int n); 事實(shí)上，很多STL的實(shí)現(xiàn)代碼就是使用概念來命名模板參數(shù)的。310.1 泛型程序設(shè)計及STL的結(jié)構(gòu)C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.1.2 STL簡介 標(biāo)準(zhǔn)模板庫（Standa

3、rd Template Library，簡稱STL）提供了一些非常常用的數(shù)據(jù)結(jié)構(gòu)和算法 STL程序?qū)嵗ɡ?0-1）：410.1 泛型程序設(shè)計及STL的結(jié)構(gòu)/包含的頭文件略去using namespace std;int main() const int N = 5;vector s(N); for (int i = 0; i si;transform(s.begin(), s.end(), ostream_iterator(cout, ), negate();cout endl;return 0;容器迭代器函數(shù)對象算法C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.1.2 STL簡介 tra

4、nsform算法的一種實(shí)現(xiàn)：template OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) for (;first != last; +first, +result)*result = op(*first);return result;5C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)STL的組成部分6 STL是泛型程序設(shè)計的一個范例 容器（container） 迭代器（iterator） 算法（algorithms） 函數(shù)對象（fu

5、nction object）容器容器(container)算法算法(algorithm)容器容器(container)迭代器迭代器(iterator)函數(shù)對象函數(shù)對象(functionobject)迭代器迭代器(iterator)10.1 泛型程序設(shè)計及STL的結(jié)構(gòu) 10.1.2 STL簡介 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.2.1輸入流迭代器和輸出流迭代器 輸入流迭代器 istream_iterator 以輸入流（如cin）為參數(shù)構(gòu)造 可用*(p+)獲得下一個輸入的元素 輸出流迭代器 ostream_iterator 構(gòu)造時需要提供輸出流（如cout） 可用(*p+) = x將

6、x輸出到輸出流 二者都屬于適配器 適配器是用來為已有對象提供新的接口的對象 輸入流適配器和輸出流適配器為流對象提供了迭代器的接口710.2 迭代器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-2從標(biāo)準(zhǔn)輸入讀入幾個實(shí)數(shù)，分別將它們的平方輸出/10_2.cpp#include #include #include using namespace std; /求平方的函數(shù)double square(double x) return x * x; int main() /從標(biāo)準(zhǔn)輸入讀入若干個實(shí)數(shù)，分別將它們的平方輸出 transform(istream_iterator(cin), istream_

7、iterator(),ostream_iterator(cout, t), square); cout 運(yùn)算符） 輸入迭代器 可以用來從序列中讀取數(shù)據(jù)，如輸入流迭代器 輸出迭代器 允許向序列中寫入數(shù)據(jù)，如輸出流迭代器 前向迭代器 既是輸入迭代器又是輸出迭代器，并且可以對序列進(jìn)行單向的遍歷 雙向迭代器 與前向迭代器相似，但是在兩個方向上都可以對數(shù)據(jù)遍歷 隨機(jī)訪問迭代器 也是雙向迭代器，但能夠在序列中的任意兩個位置之間進(jìn)行跳轉(zhuǎn)，如指針、使用vector的begin()、end()函數(shù)得到的迭代器1010.2 迭代器 10.2.2 迭代器的分類C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.2.3

8、迭代器的區(qū)間 兩個迭代器表示一個區(qū)間：p1, p2) STL算法常以迭代器的區(qū)間作為輸入，傳遞輸入數(shù)據(jù) 合法的區(qū)間 p1經(jīng)過n次(n 0)自增(+)操作后滿足p1 = p2 區(qū)間包含p1，但不包含p21110.2 迭代器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-3 綜合運(yùn)用幾種迭代器的示例/10_3.cpp#include #include #include #include using namespace std; /將來自輸入迭代器p的n個T類型的數(shù)值排序，將結(jié)果通過輸出迭代器result輸出template void mySort(InputIterator first, Inp

9、utIterator last, OutputIterator result) /通過輸入迭代器p將輸入數(shù)據(jù)存入向量容器s中vector 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ū)間C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-3 （續(xù)）int main() /將s數(shù)組的內(nèi)容排序后輸出doubl

10、e a5 = 1.2, 2.4, 0.8, 3.3, 3.2 ;mySort(a, a + 5, ostream_iterator(cout, );cout endl;/從標(biāo)準(zhǔn)輸入讀入若干個整數(shù)，將排序后的結(jié)果輸出mySort(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, );cout endl;return 0;1310.2 迭代器 10.2.3 迭代器的區(qū)間運(yùn)行結(jié)果：0.8 1.2 2.4 3.2 3.32 -4 5 8 -1 3 6 -5-5 -4 -1 2 3 5 6 8C+語言程序設(shè)計（第4版），鄭

11、莉，清華大學(xué)10.2.4 迭代器的輔助函數(shù) advance(p, n) 對p執(zhí)行n次自增操作 distance(first, last) 計算兩個迭代器first和last的距離，即對first執(zhí)行多少次“+”操作后能夠使得first = last1410.2 迭代器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.3 容器的基本功能與分類 容器類是容納、包含一組元素或元素集合的對象。 七種基本容器： 向量（vector） 雙端隊(duì)列（deque） 列表（list） 集合（set） 多重集合（multiset） 映射（map） 多重映射（multimap）15C+語言程序設(shè)計（第4版），鄭莉，清華

12、大學(xué)10.3 容器的基本功能與分類（續(xù)）16容器(Container)隨機(jī)訪問容器(Random Access Container)可逆容器(Reversible Container)容器(Container)順序容器(Sequence)關(guān)聯(lián)容器(Associative Container)vectordequelistmultisetmultimapsetmapC+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)容器的通用功能 容器的通用功能 用默認(rèn)構(gòu)造函數(shù)構(gòu)造空容器 支持關(guān)系運(yùn)算符：=、!=、= begin()、end()：獲得容器首、尾迭代器 clear()：將容器清空 empty()：判斷容器是

13、否為空 size()：得到容器元素個數(shù) s1.swap(s2)：將s1和s2兩容器內(nèi)容交換 相關(guān)數(shù)據(jù)類型（S表示容器類型） S:iterator：指向容器元素的迭代器類型 S:const_iterator：常迭代器類型1710.3 容器的基本功能與分類C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)可逆容器、隨機(jī)訪問容器 可逆容器 S:reverse_iterator：逆向迭代器類型 S:const_reverse_iterator：逆向常迭代器類型 rbegin() ：指向容器尾的逆向迭代器 rend()：指向容器首的逆向迭代器 隨機(jī)訪問容器 sn：獲得容器s的第n個元素1810.3 容器的基本功

14、能與分類C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)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 順序容器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-4 順序容器的基本操作/10_4.cpp，包含的頭文件略去 /輸出指定的整型順序容器的元素template void printContain

15、er(const char* msg, const T& s) cout msg : ;copy(s.begin(), s.end(), ostream_iterator(cout, );cout endl; int main() /從標(biāo)準(zhǔn)輸入讀入10個整數(shù)，將它們分別從s的頭部加入deque s;for (int i = 0; i x;s.push_front(x);2010.4 順序容器 10.4.1 順序容器的基本功能C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-4 （續(xù)）printContainer(deque at first, s);/用s容器的內(nèi)容的逆序構(gòu)造列表容器llist

16、 l(s.rbegin(), s.rend();printContainer(list at first, l);/將列表容器l的每相鄰兩個容器順序顛倒list:iterator iter = l.begin();while (iter != l.end() int v = *iter;iter = l.erase(iter);l.insert(+iter, v);printContainer(list at last, l);/用列表容器l的內(nèi)容給s賦值，將s輸出s.assign(l.begin(), l.end();printContainer(deque at last, s);retu

17、rn 0;2110.4 順序容器 10.4.1 順序容器的基本功能C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-4 （續(xù)） 運(yùn)行結(jié)果如下： 0 9 8 6 4 3 2 1 5 4 deque at first: 4 5 1 2 3 4 6 8 9 0 list at first: 0 9 8 6 4 3 2 1 5 4 list at last: 9 0 6 8 3 4 1 2 4 5 deque at last: 9 0 6 8 3 4 1 2 4 52210.4 順序容器 10.4.1 順序容器的基本功能C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.4.2 三種順序容器的特性 向量（

18、Vector） 特點(diǎn) 一個可以擴(kuò)展的動態(tài)數(shù)組 隨機(jī)訪問、在尾部插入或刪除元素快 在中間或頭部插入或刪除元素慢 向量的容量 容量(capacity)：實(shí)際分配空間的大小 s.capacity() ：返回當(dāng)前容量 s.reserve(n)：若容量小于n，則對s進(jìn)行擴(kuò)展，使其容量至少為n2310.4 順序容器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)雙端隊(duì)列（deque） 特點(diǎn) 在兩端插入或刪除元素快 在中間插入或刪除元素慢 隨機(jī)訪問較快，但比向量容器慢2410.4 順序容器 10.4.2 三種順序容器的特性C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-5 奇偶排序 先按照從大到小順序輸出奇數(shù)，

19、再按照從小到大順序輸出偶數(shù)。2510.4 順序容器 10.4.2 三種順序容器的特性/ 頭部分省略int main() istream_iterator i1(cin), i2;/建立一對兒輸入流迭代器 vector s1(i1, i2);/通過輸入流迭代器從標(biāo)準(zhǔn)輸入流中輸入數(shù)據(jù) sort(s1.begin(), s1.end();/將輸入的整數(shù)排序 deque s2; /以下循環(huán)遍歷s1 for (vector:iterator iter = s1.begin(); iter != s1.end(); +iter) if (*iter % 2 = 0)/偶數(shù)放到s2尾部 s2.push_ba

20、ck(*iter);else/奇數(shù)放到s2首部 s2.push_front(*iter); /將s2的結(jié)果輸出 copy(s2.begin(), s2.end(), ostream_iterator(cout, ); cout endl; return 0;C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)列表(list) 特點(diǎn) 在任意位置插入和刪除元素都很快 不支持隨機(jī)訪問 接合(splice)操作 s1.splice(p, s2, q1, q2)：將s2中q1, q2)移動到s1中p所指向元素之前2610.4 順序容器 10.4.2 三種順序容器的特性C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例1

21、0-6列表容器的splice操作/ 頭部分省略int main() string names1 = Alice, Helen, Lucy, Susan ;string names2 = Bob, David, Levin, Mike ;list s1(names1, names1 + 4); /用names1數(shù)組的內(nèi)容構(gòu)造列表s1list s2(names2, names2 + 4); /用names2數(shù)組的內(nèi)容構(gòu)造列表s2 /將s1的第一個元素放到s2的最后s2.splice(s2.end(), s1, s1.begin();list:iterator iter1 = s1.begin();

22、 /iter1指向s1首advance(iter1, 2); /iter1前進(jìn)2個元素，它將指向s1第3個元素list:iterator iter2 = s2.begin(); /iter2指向s2首+iter2; /iter2前進(jìn)1個元素，它將指向s2第2個元素2710.4 順序容器 10.4.2 三種順序容器的特性C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-6 （續(xù)）28 list:iterator iter3 = iter2; /用iter2初始化iter3 advance(iter3, 2); /iter3前進(jìn)2個元素，它將指向s2第4個元素 /將iter2, iter3)范圍內(nèi)

23、的結(jié)點(diǎn)接到s1中iter1指向的結(jié)點(diǎn)前 s1.splice(iter1, s2, iter2, iter3); /分別將s1和s2輸出 copy(s1.begin(), s1.end(), ostream_iterator(cout, ); cout endl; copy(s2.begin(), s2.end(), ostream_iterator(cout, ); cout endl; return 0;10.4 順序容器 10.4.2 三種順序容器的特性運(yùn)行結(jié)果：Helen Lucy David Levin SusanBob Mike AliceC+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)三

24、種順序容器的比較 STL所提供的三種順序容器各有所長也各有所短，我們在編寫程序時應(yīng)當(dāng)根據(jù)我們對容器所需要執(zhí)行的操作來決定選擇哪一種容器。 如果需要執(zhí)行大量的隨機(jī)訪問操作，而且當(dāng)擴(kuò)展容器時只需要向容器尾部加入新的元素，就應(yīng)當(dāng)選擇向量容器vector； 如果需要少量的隨機(jī)訪問操作，需要在容器兩端插入或刪除元素，則應(yīng)當(dāng)選擇雙端隊(duì)列容器deque；、 如果不需要對容器進(jìn)行隨機(jī)訪問，但是需要在中間位置插入或者刪除元素，就應(yīng)當(dāng)選擇列表容器list。2910.4 順序容器 10.4.2 三種順序容器的特性C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.4.3 順序容器的插入迭代器 插入迭代器 用于向容器頭部

25、、尾部或中間指定位置插入元素的迭代器 包括前插迭代器（front_inserter）、后插迭代器（back_insrter）和任意位置插入迭代器（inserter） 例：list s;back_inserter iter(s);*(iter+) = 5; /通過通過iter把把5插入插入s末尾末尾3010.4 順序容器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.4.4 順序容器的適配器 以順序容器為基礎(chǔ)構(gòu)建一些常用數(shù)據(jù)結(jié)構(gòu) 棧(stack)：最先壓入的元素最后被彈出 隊(duì)列(queue)：最先壓入的元素最先被彈出 優(yōu)先級隊(duì)列(priority_queue)：最“大”的元素最先被彈出3110.

26、4 順序容器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-7 利用棧反向輸出單詞/10_7.cpp， 省略頭部分int main() stack s;string str;cin str;/從鍵盤輸入一個字符串/將字符串的每個元素順序壓入棧中for (string:iterator iter = str.begin(); iter != str.end(); +iter)s.push(*iter);/將棧中的元素順序彈出并輸出while (!s.empty() cout s.top();s.pop();cout endl;return 0;3210.4 順序容器 10.4.4 順序容器的適

27、配器運(yùn)行結(jié)果如下：congratulationssnoitalutargnocC+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)優(yōu)先級隊(duì)列 優(yōu)先級隊(duì)列也像棧和隊(duì)列一樣支持元素的壓入和彈出，但元素彈出的順序與元素的大小有關(guān)，每次彈出的總是容器中最“大”的一個元素。 template class T, class Sequence = vector class priority_queue; 例10-8 細(xì)胞分裂模擬 一種細(xì)胞在誕生（即上次分裂）后會在500到2000秒內(nèi)分裂為兩個細(xì)胞，每個細(xì)胞又按照同樣的規(guī)律繼續(xù)分裂。3310.4 順序容器 10.4.4 順序容器的適配器C+語言程序設(shè)計（第4版），鄭莉

28、，清華大學(xué)/ 10.8.cpp, 頭部分省略const int SPLIT_TIME_MIN = 500; /細(xì)胞分裂最短時間const int SPLIT_TIME_MAX = 2000; /細(xì)胞分裂最長時間 class Cell;priority_queue cellQueue; class Cell /細(xì)胞類private:static int count;/細(xì)胞總數(shù)int id;/當(dāng)前細(xì)胞編號int time;/細(xì)胞分裂時間public:Cell(int birth) : id(count+) /birth為細(xì)胞誕生時間/初始化，確定細(xì)胞分裂時間time = birth + (rand

29、() % (SPLIT_TIME_MAX - SPLIT_TIME_MIN) + SPLIT_TIME_MIN;int getId() const return id; /得到細(xì)胞編號int getSplitTime() const return time; /得到細(xì)胞分裂時間bool operator s.time; /定義“” 34例10-8（續(xù)）10.4 順序容器 10.4.4 順序容器的適配器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)/細(xì)胞分裂void split() Cell child1(time), child2(time);/建立兩個子細(xì)胞cout time s: Cell #

30、 id splits to # child1.getId() and # child2.getId() endl;cellQueue.push(child1);/將第一個子細(xì)胞壓入優(yōu)先級隊(duì)列cellQueue.push(child2);/將第二個子細(xì)胞壓入優(yōu)先級隊(duì)列;int Cell:count = 0; int main() srand(static_cast(time(0);int t; /模擬時間長度cout t;cellQueue.push(Cell(0);/將第一個細(xì)胞壓入優(yōu)先級隊(duì)列while (cellQueue.top().getSplitTime() = t) cellQueu

31、e.top().split();/模擬下一個細(xì)胞的分裂cellQueue.pop();/將剛剛分裂的細(xì)胞彈出return 0;35例10-8（續(xù)）10.4 順序容器 10.4.4 順序容器的適配器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-8（續(xù)） 運(yùn)行結(jié)果如下：Simulation time: 5000971s: Cell #0 splits to #1 and #21719s: Cell #1 splits to #3 and #41956s: Cell #2 splits to #5 and #62845s: Cell #6 splits to #7 and #83551s: Ce

32、ll #3 splits to #9 and #103640s: Cell #4 splits to #11 and #123919s: Cell #5 splits to #13 and #144162s: Cell #10 splits to #15 and #164197s: Cell #8 splits to #17 and #184317s: Cell #7 splits to #19 and #204686s: Cell #13 splits to #21 and #224809s: Cell #12 splits to #23 and #244818s: Cell #17 spl

33、its to #25 and #263610.4 順序容器 10.4.4 順序容器的適配器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.5.1 關(guān)聯(lián)容器分類和的基本功能 關(guān)聯(lián)容器的特點(diǎn) 每個關(guān)聯(lián)容器都有一個鍵(key) 可以根據(jù)鍵高效地查找元素 接口 插入：insert 刪除：erase 查找：find 定界：lower_bound、upper_bound、equal_range 計數(shù)：count3710.5 關(guān)聯(lián)容器C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)關(guān)聯(lián)容器概念圖3810.5 關(guān)聯(lián)容器 10.5.1 關(guān)聯(lián)容器的分類和基本功能關(guān)聯(lián)容器(Associative Container)單重

34、關(guān)聯(lián)容器(Unique Asso-ciative Container)多重關(guān)聯(lián)容器(Multiple Asso-ciative Container)關(guān)聯(lián)容器(Associative Container)簡單關(guān)聯(lián)容器(Simple Asso-ciative Container)二元關(guān)聯(lián)容器(Pair Asso-ciative Container)multisetmultimapsetmapC+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)四種關(guān)聯(lián)容器 單重關(guān)聯(lián)容器(set和map) 鍵值是唯一的，一個鍵值只能對應(yīng)一個元素 多重關(guān)聯(lián)容器(multiset和multimap) 鍵值是不唯一的，一個鍵值可以對

35、應(yīng)多個元素 簡單關(guān)聯(lián)容器(set和multiset) 容器只有一個類型參數(shù)，如set、multiset，表示鍵類型 容器的元素就是鍵本身 二元關(guān)聯(lián)容器(map和multimap) 容器有兩個類型參數(shù)，如map、multimap，分別表示鍵和附加數(shù)據(jù)的類型 容器的元素類型是pair，即由鍵類型和元素類型復(fù)合而成的二元組3910.5 關(guān)聯(lián)容器 10.5.1 關(guān)聯(lián)容器的分類和基本功能C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.5.2 集合（set） 集合用來存儲一組無重復(fù)的元素。由于集合的元素本身是有序的，可以高效地查找指定元素，也可以方便地得到指定大小范圍的元素在容器中所處的區(qū)間。 例10-9

36、 輸入一串實(shí)數(shù)，將重復(fù)的去掉，取最大和最小者的中值，分別輸出小于等于此中值和大于等于此中值的實(shí)數(shù)4010.5 關(guān)聯(lián)容器 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)/10_9.cpp, 頭部分省略int main() set s;while (true) double v;cin v;if (v = 0) break;/輸入0表示結(jié)束pairset:iterator, bool r = s.insert(v); /嘗試將v插入if (!r.second)/如果v已存在，輸出提示信息 cout v is duplicated endl;set:iterator iter1 = s.begin();

37、/得到第一個元素的迭代器set:iterator iter2 = s.end();/得到末尾的迭代器double medium = (*iter1 + *(-iter2) / 2;/得到最小和最大元素的中值/輸出小于或等于中值的元素cout = medium: copy(s.begin(), s.upper_bound(medium), ostream_iterator(cout, );cout endl;/輸出大于或等于中值的元素cout = medium: ;copy(s.lower_bound(medium), s.end(), ostream_iterator(cout, );cout

38、 endl;return 0;4110.5 關(guān)聯(lián)容器 10.5.2 集合（set） 例10-9（續(xù)）C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-9（續(xù)） 運(yùn)行結(jié)果如下： 1 2.5 5 3.5 5 7 9 2.5 0 5 is duplicated 2.5 is duplicated = medium: 5 7 94210.5 關(guān)聯(lián)容器 10.5.2 集合（set） C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.5.3 映射（map） 映射與集合同屬于單重關(guān)聯(lián)容器，它們的主要區(qū)別在于，集合的元素類型是鍵本身，而映射的元素類型是由鍵和附加數(shù)據(jù)所構(gòu)成的二元組。 在集合中按照鍵查找一個元素時

39、，一般只是用來確定這個元素是否存在，而在映射中按照鍵查找一個元素時，除了能確定它的存在性外，還可以得到相應(yīng)的附加數(shù)據(jù)。 例10-10 有五門課程，每門都有相應(yīng)學(xué)分，從中選擇三門，輸出學(xué)分總和4310.5 關(guān)聯(lián)容器 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)/10_10.cpp, 頭部分省略int main() map courses;/將課程信息插入courses映射中courses.insert(make_pair(CSAPP, 3);courses.insert(make_pair(C+, 2);courses.insert(make_pair(CSARCH, 4);courses.ins

40、ert(make_pair(COMPILER, 4);courses.insert(make_pair(OS, 5);int n = 3;/剩下的可選次數(shù)int sum = 0; /學(xué)分總和while (n 0) string name;cin name;/輸入課程名稱map:iterator iter = courses.find(name);/查找課程if (iter = courses.end() /判斷是否找到cout name is not available second;/累加學(xué)分courses.erase(iter);/將剛選過的課程從映射中刪除n-;cout Total cr

41、edit: sum endl;/輸出總學(xué)分return 0;4410.5 關(guān)聯(lián)容器 10.5.3 映射（map） 例10-10（續(xù)）C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-10（續(xù)） 運(yùn)行結(jié)果如下：C+COMPILERC+C+ is not availableCSAPPTotal credit: 94510.5 關(guān)聯(lián)容器 10.5.3 映射（map） C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-11統(tǒng)計一句話中每個字母出現(xiàn)的次數(shù)/ 10_11.cpp, 頭部分省略int main() map s;/用來存儲字母出現(xiàn)次數(shù)的映射char c;/存儲輸入字符do cin c;/輸入下

42、一個字符if (isalpha(c) /判斷是否是字母c = tolower(c);/將字母轉(zhuǎn)換為小寫sc+;/將該字母的出現(xiàn)頻率加1 while (c != .);/碰到“.”則結(jié)束輸入/輸出每個字母出現(xiàn)次數(shù)for (map:iterator iter = s.begin(); iter != s.end(); +iter)cout first second ;cout endl;return 0;4610.5 關(guān)聯(lián)容器 10.5.3 映射（map） C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.5.4 多重集合（multiset）與多重映射（multimap） 多重集合是允許有重復(fù)元素的

43、集合，多重映射是允許一個鍵對應(yīng)多個附加數(shù)據(jù)的映射。 多重集合與集合、多重映射與映射的用法差不多，只在幾個成員函數(shù)上有細(xì)微差異，其差異主要表現(xiàn)在去除了鍵必須唯一的限制。 例10-12 上課時間查詢4710.5 關(guān)聯(lián)容器 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)/10_12.cpp#include #include #include #include using namespace std;int main() multimap courses;typedef multimap:iterator CourseIter; /將課程上課時間插入courses映射中courses.insert(mak

44、e_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ù)string name;int count;4810.5 關(guān)聯(lián)容器 10.5.4 多重集合與多重映射例10-12（續(xù)）C+語言程序設(shè)計（第4版），鄭莉

45、，清華大學(xué)do cin name;count = courses.count(name);if (count = 0)cout Cannot find this course! endl; while (count = 0);/輸出每周上課次數(shù)和上課時間cout count lesson(s) per week: ;pair range = courses.equal_range(name);for (CourseIter iter = range.first; iter != range.second; +iter)cout second ;cout endl;return 0;4910.5

46、 關(guān)聯(lián)容器 10.5.4 多重集合與多重映射例10-12（續(xù)）運(yùn)行結(jié)果如下：JAVACannot find this course!OS3 lesson(s) per week: 1-2 4-1 5-5C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)10.6.1 函數(shù)對象 函數(shù)對象 一個行為類似函數(shù)的對象 可以沒有參數(shù)，也可以帶有若干參數(shù) 其功能是獲取一個值，或者改變操作的狀態(tài)。 例 普通函數(shù)就是函數(shù)對象 重載了“()”運(yùn)算符的類的實(shí)例是函數(shù)對象5010.6 函數(shù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)函數(shù)對象概念圖5110.6 函數(shù)對象 10.6.1 函數(shù)對象函數(shù)對象(Function)一元

47、函數(shù)對象(Unary Function)二元函數(shù)對象(Binary Function)產(chǎn)生器(Generator)一元謂詞(Unary Predicate)二元謂詞(Binary Predicate)C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-13、例10-14 使用兩種方式定義表示乘法的函數(shù)對象 通過定義普通函數(shù)（例10-13） 通過重載類的“()”運(yùn)算符（例10-14） 用到以下算法：templateType accumulate(InputIterator first, InputIterator last, Type val, BinaryFunction binaryOp);

48、對first, last)區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行累“加”，binaryOp為用二元函數(shù)對象表示的“加”運(yùn)算符，val為累“加”的初值5210.6 函數(shù)對象 10.6.1 函數(shù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)#include #include /包含數(shù)值算法頭文件using namespace std;/定義一個普通函數(shù)int mult(int x, int y) return x * y; ;int main() int a = 1, 2, 3, 4, 5 ;const int N = sizeof(a) / sizeof(int);cout The result by multipl

49、ing all elements in a is accumulate(a, a + N, 1, mult) endl;return 0;5310.6 函數(shù)對象 10.6.1 函數(shù)對象例10-13（續(xù)）C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)/10_14.cpp#include #include /包含數(shù)值算法頭文件using namespace std; class MultClass /定義MultClass類public:int operator() (int x, int y) const return x * y; /重載操作符operator(); int main() int

50、a = 1, 2, 3, 4, 5 ;const int N = sizeof(a) / sizeof(int);cout The result by multipling all elements in a is accumulate(a, a + N, 1, MultClass()/將類multclass傳遞給通用算法 endl;return 0;5410.6 函數(shù)對象 10.6.1 函數(shù)對象例10-14（續(xù)）C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)STL提供的函數(shù)對象 用于算術(shù)運(yùn)算的函數(shù)對象： 一元函數(shù)對象：negate 二元函數(shù)對象：plus、minus、multiplies、div

51、ides、modulus 用于關(guān)系運(yùn)算、邏輯運(yù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ù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-15 利用STL標(biāo)準(zhǔn)函數(shù)對象/10_15.cpp#include #include /包含數(shù)值算法頭文件#include /包含標(biāo)準(zhǔn)函數(shù)對象頭文件using namespace std;int main() int a = 1, 2,

52、3, 4, 5 ;const int N = sizeof(a) / sizeof(int);cout The result by multipling all elements in A is “ accumulate(a, a + N, 1, multiplies() endl; /將標(biāo)準(zhǔn)函數(shù)對象傳遞給通用算法return 0;5610.6 函數(shù)對象 10.6.1 函數(shù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-16利用STL中的二元謂詞函數(shù)對象/ 10_16.cpp, 省略頭部分int main() int intArr = 30, 90, 10, 40, 70, 50, 20

53、, 80 ;const int N = sizeof(intArr) / sizeof(int);vector a(intArr, intArr + N); cout before sorting: endl;copy(a.begin(), a.end(), ostream_iterator(cout, t);cout endl; sort(a.begin(), a.end(), greater(); cout after sorting: endl;copy(a.begin(), a.end(), ostream_iterator(cout, t);cout endl;return 0;57

54、10.6 函數(shù)對象 10.6.1 函數(shù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)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ù)對象C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-17

55、 bind2nd產(chǎn)生binder2nd函數(shù)適配器實(shí)例/10_17.cpp#include #include#include#includeusing namespace std; int main() int intArr = 30, 90, 10, 40, 70, 50, 20, 80 ;const int N = sizeof(intArr) / sizeof(int);vector a(intArr, intArr + N);vector:iterator p = find_if(a.begin(), a.end(), bind2nd(greater(), 40);if (p = a.e

56、nd()cout no element greater than 40 endl;elsecout first element greater than 40 is: *p y; int main() int intArr = 30, 90, 10, 40, 70, 50, 20, 80 ;const int N = sizeof(intArr) / sizeof(int);vector a(intArr, intArr + N); vector:iterator p;p = find_if(a.begin(), a.end(), bind2nd(ptr_fun(g), 40);if (p =

57、 a.end()cout no element greater than 40 endl;elsecout first element greater than 40 is: *p endl;6010.6 函數(shù)對象 10.6.2 函數(shù)適配器 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)6110.6 函數(shù)對象 10.6.2 函數(shù)適配器 p = find_if(a.begin(), a.end(), not1(bind2nd(greater(), 15);if (p = a.end() cout no element is not greater than 15 endl;else cout fir

58、st element that is not greater than 15 is: *p endl; p = find_if(a.begin(), a.end(), bind2nd(not2(greater(), 15);if (p = a.end() cout no element is not greater than 15 endl;elsecout first element that is not greater than 15 is: *p endl;return 0;例10-17（續(xù)）C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)例10-19 成員函數(shù)適配器實(shí)例/10_19.cpp

59、#include #include #include #include using namespace std; struct Car int id;Car(int id) this-id = id; void display() const cout car id endl; ; int main() vector pcars;vector cars;6210.6 函數(shù)對象 10.6.2 函數(shù)適配器 C+語言程序設(shè)計（第4版），鄭莉，清華大學(xué)6310.6 函數(shù)對象 10.6.2 函數(shù)適配器 for (int i = 0; i 5; i+)pcars.push_back(new Car(i);

60、for (int i = 5; i 10; i+)cars.push_back(Car(i);cout elements in pcars: endl;for_each(pcars.begin(), pcars.end(), std:mem_fun(&Car:display);cout endl; cout elements in cars: endl;for_each(cars.begin(), cars.end(), std:mem_fun_ref(&Car:display);cout endl; for (size_t i = 0; i pcars.size(); +i)delete p