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

1、C+語言程序設(shè)計(jì)（第4版） 第十章 泛型程序設(shè)計(jì) 與C+標(biāo)準(zhǔn)模板庫 清華大學(xué) 鄭 莉 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 目錄 10.1 泛型程序設(shè)計(jì)及STL的結(jié)構(gòu) 10.2 迭代器 10.3 容器的基本功能與分類 10.4 順序容器 10.5 關(guān)聯(lián)容器 10.6 函數(shù)對象 10.7 算法 10.8 綜合實(shí)例對個(gè)人銀行賬戶管理程序的改進(jìn) 10.9 深度探索 10.10 小結(jié) 2 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.1.1 泛型程序設(shè)計(jì)的基本概念 編寫不依賴于具體數(shù)據(jù)類型的程序 將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的 C+的模板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ) 幾個(gè)術(shù)語

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

3、10.1.2 STL簡介 標(biāo)準(zhǔn)模板庫（Standard Template Library，簡稱 STL）提供了一些非常常 用的數(shù)據(jù)結(jié)構(gòu)和算法 STL程序?qū)嵗ɡ?0-1）： 410.1 泛型程序設(shè)計(jì)及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ù)對象

4、算法 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.1.2 STL簡介 transform算法的一種實(shí)現(xiàn)： template OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) for (;first != last; +first, +result) *result = op(*first); return result; 5 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) STL的組成部分 6 STL是泛型程序設(shè)計(jì)的一個(gè)范例 容器

5、（container） 迭代器（iterator） 算法（algorithms） 函數(shù)對象（function object） 容器容器 (container) 算法算法 (algorithm) 容器容器 (container) 迭代器迭代器 (iterator) 函數(shù)對象函數(shù)對象 (function object) 迭代器迭代器 (iterator) 10.1 泛型程序設(shè)計(jì)及STL的結(jié)構(gòu) 10.1.2 STL簡介 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.2.1輸入流迭代器和輸出流迭代器 輸入流迭代器 istream_iterator 以輸入流（如cin）為參數(shù)構(gòu)造 可用*(p+)獲得

6、下一個(gè)輸入的元素 輸出流迭代器 ostream_iterator 構(gòu)造時(shí)需要提供輸出流（如cout） 可用(*p+) = x將x輸出到輸出流 二者都屬于適配器 適配器是用來為已有對象提供新的接口的對象 輸入流適配器和輸出流適配器為流對象提供了迭代器的 接口 710.2 迭代器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-2從標(biāo)準(zhǔn)輸入讀入幾個(gè)實(shí)數(shù)，分別 將它們的平方輸出 /10_2.cpp #include #include #include using namespace std; /求平方的函數(shù) double square(double x) return x * x; int ma

7、in() /從標(biāo)準(zhǔn)輸入讀入若干個(gè)實(shí)數(shù)，分別將它們的平方輸出 transform(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, t), square); cout 運(yùn)算符） 輸入迭代器 可以用來從序列中讀取數(shù)據(jù)，如輸入流迭代器 輸出迭代器 允許向序列中寫入數(shù)據(jù)，如輸出流迭代器 前向迭代器 既是輸入迭代器又是輸出迭代器，并且可以對序列進(jìn)行單向的遍歷 雙向迭代器 與前向迭代器相似，但是在兩個(gè)方向上都可以對數(shù)據(jù)遍歷 隨機(jī)訪問迭代器 也是雙向迭代器，但能夠在序列中的任意兩個(gè)位置之間進(jìn)行跳轉(zhuǎn)， 如指針、使用vector的

8、begin()、end()函數(shù)得到的迭代器 1010.2 迭代器 10.2.2 迭代器的分類 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.2.3 迭代器的區(qū)間 兩個(gè)迭代器表示一個(gè)區(qū)間：p1, p2) STL算法常以迭代器的區(qū)間作為輸入，傳遞輸入 數(shù)據(jù) 合法的區(qū)間 p1經(jīng)過n次(n 0)自增(+)操作后滿足p1 = p2 區(qū)間包含p1，但不包含p2 1110.2 迭代器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-3 綜合運(yùn)用幾種迭代器的示例 /10_3.cpp #include #include #include #include using namespace std; /將來

9、自輸入迭代器p的n個(gè)T類型的數(shù)值排序，將結(jié)果通過輸出迭代器result輸出 template void mySort(InputIterator first, InputIterator 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序列通過輸出

10、迭代器輸出 1210.2 迭代器 10.2.3 迭代器的區(qū)間 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-3 （續(xù)） int main() /將s數(shù)組的內(nèi)容排序后輸出 double a5 = 1.2, 2.4, 0.8, 3.3, 3.2 ; mySort(a, a + 5, ostream_iterator(cout, ); cout endl; /從標(biāo)準(zhǔn)輸入讀入若干個(gè)整數(shù)，將排序后的結(jié)果輸出 mySort(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, ); cout endl; return 0;

11、 1310.2 迭代器 10.2.3 迭代器的區(qū)間 運(yùn)行結(jié)果： 0.8 1.2 2.4 3.2 3.3 2 -4 5 8 -1 3 6 -5 -5 -4 -1 2 3 5 6 8 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.2.4 迭代器的輔助函數(shù) advance(p, n) 對p執(zhí)行n次自增操作 distance(first, last) 計(jì)算兩個(gè)迭代器first和last的距離，即對first執(zhí)行多 少次“+”操作后能夠使得first = last 1410.2 迭代器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.3 容器的基本功能與分類 容器類是容納、包含一組元素或元素集合的

12、對象。 七種基本容器： 向量（vector） 雙端隊(duì)列（deque） 列表（list） 集合（set） 多重集合（multiset） 映射（map） 多重映射（multimap） 15 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.3 容器的基本功能與分類（續(xù)） 16 容器(Container) 隨機(jī)訪問容器 (Random Access Container) 可逆容器 (Reversible Container) 容器(Container) 順序容器 (Sequence) 關(guān)聯(lián)容器 (Associative Container) vector deque list multiset mu

13、ltimap set map C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 容器的通用功能 容器的通用功能 用默認(rèn)構(gòu)造函數(shù)構(gòu)造空容器 支持關(guān)系運(yùn)算符：=、!=、= begin()、end()：獲得容器首、尾迭代器 clear()：將容器清空 empty()：判斷容器是否為空 size()：得到容器元素個(gè)數(shù) s1.swap(s2)：將s1和s2兩容器內(nèi)容交換 相關(guān)數(shù)據(jù)類型（S表示容器類型） S:iterator：指向容器元素的迭代器類型 S:const_iterator：常迭代器類型 1710.3 容器的基本功能與分類 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 可逆容器、隨機(jī)訪問容器 可逆容器

14、S:reverse_iterator：逆向迭代器類型 S:const_reverse_iterator：逆向常迭代器類型 rbegin() ：指向容器尾的逆向迭代器 rend()：指向容器首的逆向迭代器 隨機(jī)訪問容器 sn：獲得容器s的第n個(gè)元素 1810.3 容器的基本功能與分類 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.4.1 順序容器的基本功能 順序容器的接口 賦值 assign 插入函數(shù) insert， push_front（只對list和deque）， push_back 刪除函數(shù) erase，clear，pop_front（只對list和deque） ，pop_back 其

15、他順序容器訪問函數(shù) front，back 改變大小 resize 1910.4 順序容器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-4 順序容器的基本操作 /10_4.cpp，包含的頭文件略去 /輸出指定的整型順序容器的元素 template void printContainer(const char* msg, const T copy(s.begin(), s.end(), ostream_iterator(cout, ); cout endl; int main() /從標(biāo)準(zhǔn)輸入讀入10個(gè)整數(shù)，將它們分別從s的頭部加入 deque s; for (int i = 0; i x

16、; s.push_front(x); 2010.4 順序容器 10.4.1 順序容器的基本功能 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-4 （續(xù)） printContainer(deque at first, s); /用s容器的內(nèi)容的逆序構(gòu)造列表容器l list l(s.rbegin(), s.rend(); printContainer(list at first, l); /將列表容器l的每相鄰兩個(gè)容器順序顛倒 list:iterator iter = l.begin(); while (iter != l.end() int v = *iter; iter = l.eras

17、e(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); return 0; 2110.4 順序容器 10.4.1 順序容器的基本功能 C+語言程序設(shè)計(jì)（第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

18、 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 5 2210.4 順序容器 10.4.1 順序容器的基本功能 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.4.2 三種順序容器的特性 向量（Vector） 特點(diǎn) 一個(gè)可以擴(kuò)展的動(dòng)態(tài)數(shù)組 隨機(jī)訪問、在尾部插入或刪除元素快 在中間或頭部插入或刪除元素慢 向量的容量 容量(capacity)：實(shí)際分配空間的大小 s.capacity() ：返回當(dāng)前容量 s.reserve(n)：若容量小于n，則對s進(jìn)行擴(kuò)展，使其 容量至少為n 23

19、10.4 順序容器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 雙端隊(duì)列（deque） 特點(diǎn) 在兩端插入或刪除元素快 在中間插入或刪除元素慢 隨機(jī)訪問較快，但比向量容器慢 2410.4 順序容器 10.4.2 三種順序容器的特性 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-5 奇偶排序 先按照從大到小順序輸出奇數(shù)，再按照從小到大順序輸出偶數(shù)。 2510.4 順序容器 10.4.2 三種順序容器的特性 / 頭部分省略 int main() istream_iterator i1(cin), i2;/建立一對兒輸入流迭代器 vector s1(i1, i2);/通過輸入流迭代器從標(biāo)準(zhǔn)輸入流

20、中輸入數(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_back(*iter); else/奇數(shù)放到s2首部 s2.push_front(*iter); /將s2的結(jié)果輸出 copy(s2.begin(), s2.end(), ostream_iterator(cout, ); cout endl; return 0; C+語言

21、程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 列表(list) 特點(diǎn) 在任意位置插入和刪除元素都很快 不支持隨機(jī)訪問 接合(splice)操作 s1.splice(p, s2, q1, q2)：將s2中q1, q2)移動(dòng)到s1中 p所指向元素之前 2610.4 順序容器 10.4.2 三種順序容器的特性 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-6列表容器的splice操作 / 頭部分省略 int main() string names1 = Alice, Helen, Lucy, Susan ; string names2 = Bob, David, Levin, Mike ; list s

22、1(names1, names1 + 4); /用names1數(shù)組的內(nèi)容構(gòu)造列表s1 list s2(names2, names2 + 4); /用names2數(shù)組的內(nèi)容構(gòu)造列表s2 /將s1的第一個(gè)元素放到s2的最后 s2.splice(s2.end(), s1, s1.begin(); list:iterator iter1 = s1.begin(); /iter1指向s1首 advance(iter1, 2); /iter1前進(jìn)2個(gè)元素，它將指向s1第3個(gè)元素 list:iterator iter2 = s2.begin(); /iter2指向s2首 +iter2; /iter2前進(jìn)1個(gè)

23、元素，它將指向s2第2個(gè)元素 2710.4 順序容器 10.4.2 三種順序容器的特性 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-6 （續(xù)） 28 list:iterator iter3 = iter2; /用iter2初始化iter3 advance(iter3, 2); /iter3前進(jìn)2個(gè)元素，它將指向s2第4個(gè)元素 /將iter2, iter3)范圍內(nèi)的結(jié)點(diǎn)接到s1中iter1指向的結(jié)點(diǎn)前 s1.splice(iter1, s2, iter2, iter3); /分別將s1和s2輸出 copy(s1.begin(), s1.end(), ostream_iterator(co

24、ut, ); 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 Susan Bob Mike Alice C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 三種順序容器的比較 STL所提供的三種順序容器各有所長也各有所短， 我們在編寫程序時(shí)應(yīng)當(dāng)根據(jù)我們對容器所需要執(zhí) 行的操作來決定選擇哪一種容器。 如果需要執(zhí)行大量的隨機(jī)訪問操作，而且當(dāng)擴(kuò)展容 器時(shí)只需要向容器尾部加入新的

25、元素，就應(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è)計(jì)（第4版），鄭莉，清華大學(xué) 10.4.3 順序容器的插入迭代器 插入迭代器 用于向容器頭部、尾部或中間指定位置插入元素的迭 代器 包括前插迭代器（front_inserter）、后插迭代器 （back_insrter）和任意位置插入迭代器 （inserter） 例： list s; ba

26、ck_inserter iter(s); *(iter+) = 5; /通過通過iter把把5插入插入s末尾末尾 3010.4 順序容器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.4.4 順序容器的適配器 以順序容器為基礎(chǔ)構(gòu)建一些常用數(shù)據(jù)結(jié)構(gòu) 棧(stack)：最先壓入的元素最后被彈出 隊(duì)列(queue)：最先壓入的元素最先被彈出 優(yōu)先級隊(duì)列(priority_queue)：最“大”的元素最先被 彈出 3110.4 順序容器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-7 利用棧反向輸出單詞 /10_7.cpp， 省略頭部分 int main() stack s; string

27、 str; cin str;/從鍵盤輸入一個(gè)字符串 /將字符串的每個(gè)元素順序壓入棧中 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 順序容器的適配器 運(yùn)行結(jié)果如下： congratulations snoitalutargnoc C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 優(yōu)先級隊(duì)列 優(yōu)先

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

29、短時(shí)間 const int SPLIT_TIME_MAX = 2000; /細(xì)胞分裂最長時(shí)間 class Cell; priority_queue cellQueue; class Cell /細(xì)胞類 private: static int count;/細(xì)胞總數(shù) int id;/當(dāng)前細(xì)胞編號 int time;/細(xì)胞分裂時(shí)間 public: Cell(int birth) : id(count+) /birth為細(xì)胞誕生時(shí)間 /初始化，確定細(xì)胞分裂時(shí)間 time = birth + (rand() % (SPLIT_TIME_MAX - SPLIT_TIME_MIN) + SPLIT_TIM

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

31、d2.getId() endl; cellQueue.push(child1);/將第一個(gè)子細(xì)胞壓入優(yōu)先級隊(duì)列 cellQueue.push(child2);/將第二個(gè)子細(xì)胞壓入優(yōu)先級隊(duì)列 ; int Cell:count = 0; int main() srand(static_cast(time(0); int t; /模擬時(shí)間長度 cout t; cellQueue.push(Cell(0);/將第一個(gè)細(xì)胞壓入優(yōu)先級隊(duì)列 while (cellQueue.top().getSplitTime() = t) cellQueue.top().split();/模擬下一個(gè)細(xì)胞的分裂 cellQ

32、ueue.pop();/將剛剛分裂的細(xì)胞彈出 return 0; 35 例10-8（續(xù)） 10.4 順序容器 10.4.4 順序容器的適配器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-8（續(xù)） 運(yùn)行結(jié)果如下： Simulation time: 5000 971s: Cell #0 splits to #1 and #2 1719s: Cell #1 splits to #3 and #4 1956s: Cell #2 splits to #5 and #6 2845s: Cell #6 splits to #7 and #8 3551s: Cell #3 splits to #9 a

33、nd #10 3640s: Cell #4 splits to #11 and #12 3919s: Cell #5 splits to #13 and #14 4162s: Cell #10 splits to #15 and #16 4197s: Cell #8 splits to #17 and #18 4317s: Cell #7 splits to #19 and #20 4686s: Cell #13 splits to #21 and #22 4809s: Cell #12 splits to #23 and #24 4818s: Cell #17 splits to #25 a

34、nd #26 3610.4 順序容器 10.4.4 順序容器的適配器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.5.1 關(guān)聯(lián)容器分類和的基本功能 關(guān)聯(lián)容器的特點(diǎn) 每個(gè)關(guān)聯(lián)容器都有一個(gè)鍵(key) 可以根據(jù)鍵高效地查找元素 接口 插入：insert 刪除：erase 查找：find 定界：lower_bound、upper_bound、equal_range 計(jì)數(shù)：count 3710.5 關(guān)聯(lián)容器 C+語言程序設(shè)計(jì)（第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) 單重關(guān)聯(lián)

35、容器 (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) multiset multimap set map C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 四種關(guān)聯(lián)容器 單重關(guān)聯(lián)容器(set和map) 鍵值是唯一的，一個(gè)鍵值只能對應(yīng)一個(gè)元素 多重關(guān)聯(lián)容器(multiset和multimap

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

37、指定大小范圍的元素在容器中所 處的區(qū)間。 例10-9 輸入一串實(shí)數(shù)，將重復(fù)的去掉，取最大和 最小者的中值，分別輸出小于等于此中值和大于 等于此中值的實(shí)數(shù) 4010.5 關(guān)聯(lián)容器 C+語言程序設(shè)計(jì)（第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

38、endl; set:iterator iter1 = s.begin();/得到第一個(gè)元素的迭代器 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(me

39、dium), s.end(), ostream_iterator(cout, ); cout endl; return 0; 4110.5 關(guān)聯(lián)容器 10.5.2 集合（set） 例10-9（續(xù)） C+語言程序設(shè)計(jì)（第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 9 4210.5 關(guān)聯(lián)容器 10.5.2 集合（set） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.5.3 映射（map） 映射與集合同屬于單重關(guān)聯(lián)容器，它們的主要區(qū) 別在

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

41、make_pair(C+, 2); courses.insert(make_pair(CSARCH, 4); courses.insert(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 no

42、t available second;/累加學(xué)分 courses.erase(iter);/將剛選過的課程從映射中刪除 n-; cout Total credit: sum endl;/輸出總學(xué)分 return 0; 4410.5 關(guān)聯(lián)容器 10.5.3 映射（map） 例10-10（續(xù)） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-10（續(xù)） 運(yùn)行結(jié)果如下： C+ COMPILER C+ C+ is not available CSAPP Total credit: 9 4510.5 關(guān)聯(lián)容器 10.5.3 映射（map） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-11統(tǒng)計(jì)

43、一句話中每個(gè)字母出現(xiàn)的次數(shù) / 10_11.cpp, 頭部分省略 int main() map s;/用來存儲字母出現(xiàn)次數(shù)的映射 char c;/存儲輸入字符 do cin c;/輸入下一個(gè)字符 if (isalpha(c) /判斷是否是字母 c = tolower(c);/將字母轉(zhuǎn)換為小寫 sc+;/將該字母的出現(xiàn)頻率加1 while (c != .);/碰到“.”則結(jié)束輸入 /輸出每個(gè)字母出現(xiàn)次數(shù) for (map:iterator iter = s.begin(); iter != s.end(); +iter) cout first second ; cout endl; return

44、 0; 4610.5 關(guān)聯(lián)容器 10.5.3 映射（map） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.5.4 多重集合（multiset）與多重映 射（multimap） 多重集合是允許有重復(fù)元素的集合，多重映射是 允許一個(gè)鍵對應(yīng)多個(gè)附加數(shù)據(jù)的映射。 多重集合與集合、多重映射與映射的用法差不多， 只在幾個(gè)成員函數(shù)上有細(xì)微差異，其差異主要表 現(xiàn)在去除了鍵必須唯一的限制。 例10-12 上課時(shí)間查詢 4710.5 關(guān)聯(lián)容器 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) /10_12.cpp #include #include #include #include using namespac

45、e std; int main() multimap courses; typedef multimap:iterator CourseIter; /將課程上課時(shí)間插入courses映射中 courses.insert(make_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(mak

46、e_pair(OS, 5-5); /輸入一個(gè)課程名，直到找到該課程為止，記下每周上課次數(shù) string name; int count; 4810.5 關(guān)聯(lián)容器 10.5.4 多重集合與多重映射 例10-12（續(xù)） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) do cin name; count = courses.count(name); if (count = 0) cout Cannot find this course! endl; while (count = 0); /輸出每周上課次數(shù)和上課時(shí)間 cout count lesson(s) per week: ; pair range

47、 = courses.equal_range(name); for (CourseIter iter = range.first; iter != range.second; +iter) cout second ; cout endl; return 0; 4910.5 關(guān)聯(lián)容器 10.5.4 多重集合與多重映射 例10-12（續(xù)） 運(yùn)行結(jié)果如下： JAVA Cannot find this course! OS 3 lesson(s) per week: 1-2 4-1 5-5 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.6.1 函數(shù)對象 函數(shù)對象 一個(gè)行為類似函數(shù)的對象 可以沒有參

48、數(shù)，也可以帶有若干參數(shù) 其功能是獲取一個(gè)值，或者改變操作的狀態(tài)。 例 普通函數(shù)就是函數(shù)對象 重載了“()”運(yùn)算符的類的實(shí)例是函數(shù)對象 5010.6 函數(shù)對象 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 函數(shù)對象概念圖 5110.6 函數(shù)對象 10.6.1 函數(shù)對象 函數(shù)對象 (Function) 一元函數(shù)對象 (Unary Function) 二元函數(shù)對象 (Binary Function) 產(chǎn)生器 (Generator) 一元謂詞 (Unary Predicate) 二元謂詞 (Binary Predicate) C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-13、例10-14 使用兩

49、種方式定義表示乘法的函數(shù)對象 通過定義普通函數(shù)（例10-13） 通過重載類的“()”運(yùn)算符（例10-14） 用到以下算法： template Type accumulate(InputIterator first, InputIterator last, Type val, BinaryFunction binaryOp); 對first, last)區(qū)間內(nèi)的數(shù)據(jù)進(jìn)行累“加”， binaryOp為用二元函數(shù)對象表示的“加”運(yùn)算符， val為累“加”的初值 5210.6 函數(shù)對象 10.6.1 函數(shù)對象 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) #include #include /包含數(shù)值算

50、法頭文件 using namespace std; /定義一個(gè)普通函數(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 multipling 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è)計(jì)（第4版），鄭莉，清華大

51、學(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 a = 1, 2, 3, 4, 5 ; const int N = sizeof(a) / sizeof(int); cout The result by multipling all elements in a is accum

52、ulate(a, a + N, 1, MultClass()/將類 multclass傳遞給通用算法 endl; return 0; 5410.6 函數(shù)對象 10.6.1 函數(shù)對象 例10-14（續(xù)） C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) STL提供的函數(shù)對象 用于算術(shù)運(yùn)算的函數(shù)對象： 一元函數(shù)對象：negate 二元函數(shù)對象：plus、minus、multiplies、 divides、modulus 用于關(guān)系運(yùn)算、邏輯運(yùn)算的函數(shù)對象 一元謂詞：logical_not 二元謂詞：equal_to、not_equal_to、greater、 less、greater_equal、less

53、_equal、 logical_and、logical_or 5510.6 函數(shù)對象 10.6.1 函數(shù)對象 C+語言程序設(shè)計(jì)（第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, 3, 4, 5 ; const int N = sizeof(a) / sizeof(int); cout The result by multipling all elements in A

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

55、fore 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; 5710.6 函數(shù)對象 10.6.1 函數(shù)對象 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 10.6.2 函數(shù)適配器 綁定適配器 將n元函數(shù)對象的指定參數(shù)綁定為一個(gè)

56、常數(shù)，得到 n-1元函數(shù)對象：bind1st、bind2nd 組合適配器 將指定謂詞的結(jié)果取反：not1、not2 指針函數(shù)適配器 對一般函數(shù)指針使用，使之能夠作為其它函數(shù)適配 器的輸入：ptr_fun 成員函數(shù)適配器 對成員函數(shù)指針使用，把n元成員函數(shù)適配為n + 1 元函數(shù)對象，該函數(shù)對象的第一個(gè)參數(shù)為調(diào)用該成 員函數(shù)時(shí)的目的對象：ptr_fun、ptr_fun_ref 5810.6 函數(shù)對象 C+語言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué) 例10-17 bind2nd產(chǎn)生binder2nd函數(shù)適 配器實(shí)例 /10_17.cpp #include #include #include #incl

57、ude using 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.end() cout no element greater than 40 endl; else cout first el

58、ement 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 = a.end() cout no element greater than 40 endl; else co

59、ut first element greater than 40 is: *p endl; 6010.6 函數(shù)對象 10.6.2 函數(shù)適配器 C+語言程序設(shè)計(jì)（第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 first element that is not greater than 15 is: *p e

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