1、第十章 C+標(biāo)準(zhǔn)模板庫C+語言程序設(shè)計2主要內(nèi)容泛型程序設(shè)計迭代器順序容器關(guān)聯(lián)容器函數(shù)對象算法深度探索3泛型程序設(shè)計編寫不依賴于具體數(shù)據(jù)類型的程序?qū)⑺惴◤奶囟ǖ臄?shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的C+的模板為泛型程序設(shè)計奠定了關(guān)鍵的基礎(chǔ)幾個術(shù)語概念（concept）：用來界定具備一定功能的數(shù)據(jù)類型，如“支持運算符”的數(shù)據(jù)類型構(gòu)成Comparable這一概念；模型（model）：符合一個概念的數(shù)據(jù)類型稱為該概念的模型，如int型是Comparable概念的模型。泛型程序設(shè)計STL程序?qū)嵗?例10-1)4/包含的頭文件略去using namespace std;int main() const int

2、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ù)對象算法迭代器泛型程序設(shè)計STL的組成部分STL是泛型程序設(shè)計的一個范例 容器（container）迭代器（iterator）算法（algorithms）函數(shù)對象（function object）5泛型程序設(shè)計容器(container)算法(algorithm)容器(container)迭代器(iterator)函數(shù)對象(functionob

3、ject)迭代器(iterator)輸入流迭代器和輸出流迭代器輸入流迭代器istream_iterator以輸入流（如cin）為參數(shù)構(gòu)造可用*(p+)獲得下一個輸入的元素輸出流迭代器ostream_iterator構(gòu)造時需要提供輸出流（如cout）可用(*p+) = x將x輸出到輸出流二者都屬于適配器適配器是用來為已有對象提供新的接口的對象輸入流適配器和輸出流適配器為流對象提供了迭代器的接口6迭代器例10-27/包含的頭文件略去using namespace std;double square(double x) return x * x;int main() transform(istrea

4、m_iterator(cin), istream_iterator(), ostream_iterator(cout, t), square); cout 運算符）輸入迭代器可以用來從序列中讀取數(shù)據(jù)，如輸入流迭代器輸出迭代器允許向序列中寫入數(shù)據(jù)，如輸出流迭代器前向迭代器既是輸入迭代器又是輸出迭代器，并且可以對序列進行單向的遍歷雙向迭代器與前向迭代器相似，但是在兩個方向上都可以對數(shù)據(jù)遍歷隨機訪問迭代器也是雙向迭代器，但能夠在序列中的任意兩個位置之間進行跳轉(zhuǎn)，如指針、使用vector的begin()、end()函數(shù)得到的迭代器迭代器迭代器的區(qū)間兩個迭代器表示一個區(qū)間：p1, p2)STL算法常以迭

5、代器的區(qū)間作為輸入，傳遞輸入數(shù)據(jù)合法的區(qū)間p1經(jīng)過n次(n 0)自增(+)操作后滿足p1 = p2區(qū)間包含p1，但不包含p210迭代器迭代器的輔助函數(shù)advance(p, n)對p執(zhí)行n次自增操作distance(first, last)計算兩個迭代器first和last的距離，即對first執(zhí)行多少次“+”操作后能夠使得first = last11迭代器12容器容器類是容納、包含一組元素或元素集合的對象。七種基本容器：向量（vector）、雙端隊列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）容 器容器的概念圖13

6、容 器容器(Container)隨機訪問容器(Random Access Container)可逆容器(Reversible Container)容器(Container)順序容器(Sequence)關(guān)聯(lián)容器(Associative Container)vectordequelistmultisetmultimapsetmap14容器的通用功能容器的通用功能用默認(rèn)構(gòu)造函數(shù)構(gòu)造空容器支持關(guān)系運算符：=、!=、=begin()、end()：獲得容器首、尾迭代器clear()：將容器清空empty()：判斷容器是否為空size()：得到容器元素個數(shù)s1.swap(s2)：將s1和s2兩容器內(nèi)容交換相

7、關(guān)數(shù)據(jù)類型（S表示容器類型）S:iterator：指向容器元素的迭代器類型S:const_iterator：常迭代器類型容 器可逆容器、隨機訪問容器可逆容器S:reverse_iterator：逆向迭代器類型S:const_reverse_iterator：逆向常迭代器類型rbegin() ：指向容器尾的逆向迭代器rend()：指向容器首的逆向迭代器隨機訪問容器sn：獲得容器s的第n個元素15容 器16順序容器順序容器的接口賦值assign插入函數(shù)insert， push_front（只對list和deque）， push_back刪除函數(shù)erase，clear，pop_front（只對lis

8、t和deque） ，pop_back其他順序容器訪問函數(shù)front，back改變大小resize順序容器例10-417順序容器/包含的頭文件略去template void printContainer(const char* msg, const T& s) cout msg : ;copy(s.begin(), s.end(), ostream_iterator(cout, );cout endl;int main() deque s;for (int i = 0; i x;s.push_front(x);18printContainer(deque at first, s);/用s容器的內(nèi)

9、容的逆序構(gòu)造列表容器llist 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 a

10、t last, s);return 0;向量(vector)特點一個可以擴展的動態(tài)數(shù)組隨機訪問、在尾部插入或刪除元素快在中間或頭部插入或刪除元素慢向量的容量容量(capacity)：實際分配空間的大小s.capacity() ：返回當(dāng)前容量s.reserve(n)：若容量小于n，則對s進行擴展，使其容量至少為n19順序容器雙端隊列(deque)特點在兩端插入或刪除元素快在中間插入或刪除元素慢隨機訪問較快，但比向量容器慢20順序容器列表(list)特點在任意位置插入和刪除元素都很快不支持隨機訪問接合(splice)操作s1.splice(p, s2, q1, q2)：將s2中q1, q2)移動到

11、s1中p所指向元素之前21順序容器順序容器的插入迭代器插入迭代器用于向容器頭部、尾部或中間指定位置插入元素的迭代器包括前插迭代器（front_inserter）、后插迭代器（back_insrter）和任意位置插入迭代器（inserter）例：list s;back_inserter iter(s);*(iter+) = 5; /通過iter把5插入s末尾22順序容器順序容器的適配器以順序容器為基礎(chǔ)構(gòu)建一些常用數(shù)據(jù)結(jié)構(gòu)棧(stack)：最先壓入的元素最后被彈出隊列(queue)：最先壓入的元素最先被彈出優(yōu)先級隊列(priority_queue)：最“大”的元素最先被彈出23順序容器關(guān)聯(lián)容器的一

12、般特性關(guān)聯(lián)容器的特點每個關(guān)聯(lián)容器都有一個鍵(key)可以根據(jù)鍵高效地查找元素接口插入：insert刪除：erase查找：find定界：lower_bound、upper_bound、equal_range計數(shù)：count24關(guān)聯(lián)容器關(guān)聯(lián)容器概念圖25關(guān)聯(lián)容器(Associative Container)單重關(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)容器(P

13、air Asso-ciative Container)multisetmultimapsetmap關(guān)聯(lián)容器單重關(guān)聯(lián)容器與多重關(guān)聯(lián)容器單重關(guān)聯(lián)容器(set和map)鍵值是唯一的，一個鍵值只能對應(yīng)一個元素多重關(guān)聯(lián)容器(multiset和multimap)鍵值是不唯一的，一個鍵值可以對應(yīng)多個元素26關(guān)聯(lián)容器簡單關(guān)聯(lián)容器和二元關(guān)聯(lián)容器簡單關(guān)聯(lián)容器(set和multiset)容器只有一個類型參數(shù)，如set、multiset，表示鍵類型容器的元素就是鍵本身二元關(guān)聯(lián)容器(map和multimap)容器有兩個類型參數(shù)，如map、multimap，分別表示鍵和附加數(shù)據(jù)的類型容器的元素類型是pair，即由鍵類型和

14、元素類型復(fù)合而成的二元組27關(guān)聯(lián)容器例10-1028int main() map courses;/將課程名稱和學(xué)分插入courses映射中courses.insert(make_pair(CSAPP, 3);courses.insert(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é)分總和關(guān)聯(lián)容器29while (n 0) stri

15、ng 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 credit: sum endl;/輸出總學(xué)分return 0;函數(shù)對象函數(shù)對象一個行為類似函數(shù)的對象可以沒有參數(shù)，也可以帶有若干參數(shù)其功能是獲取一個值，或者改變操作的狀態(tài)。例普通函數(shù)就是函數(shù)對象重載了“()”運算符的類的實例

16、是函數(shù)對象30函數(shù)對象例10-13、例10-14使用兩種方式定義表示乘法的函數(shù)對象通過定義普通函數(shù)（例10-13）通過重載類的“()”運算符（例10-14）用到以下算法：templateType accumulate(InputIterator first, InputIterator last, Type val, BinaryFunction binaryOp);對first, last)區(qū)間內(nèi)的數(shù)據(jù)進行累“加”，binaryOp為用二元函數(shù)對象表示的“加”運算符，val為累“加”的初值31函數(shù)對象32#include #include /包含數(shù)值算法頭文件using namespace

17、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 multipling all elements in a is accumulate(a, a + N, 1, mult) endl;return 0;例10-13：使用普通函數(shù)33#include #include /包含數(shù)值算法頭文件using namespace std;class MultClass pub

18、lic:int operator() (int x, int y) const 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, MultClass() endl;return 0;例10-14：重載“()”運算符函數(shù)對象概念圖34函數(shù)對象(Function)一元函數(shù)對象(Unary Function)二元函數(shù)對象(Bina

19、ry Function)產(chǎn)生器(Generator)一元謂詞(Unary Predicate)二元謂詞(Binary Predicate)函數(shù)對象STL提供的函數(shù)對象用于算術(shù)運算的函數(shù)對象：一元函數(shù)對象：negate二元函數(shù)對象：plus、minus、multiplies、divides、modulus用于關(guān)系運算、邏輯運算的函數(shù)對象一元謂詞：logical_not二元謂詞：equal_to、not_equal_to、greater、less、greater_equal、less_equal、logical_and、logical_or35函數(shù)對象函數(shù)適配器綁定適配器將n元函數(shù)對象的指定參數(shù)綁

20、定為一個常數(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_ref36函數(shù)對象例10-1737/包含的頭文件略去int main() int intArr = 30, 90, 10, 40, 70, 50, 20, 80 ;const int N = sizeof(intArr) / sizeof(i

21、nt);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;elsecout first element greater than 40 is: *p endl;return 0;函數(shù)對象算法STL算法本身是一種函數(shù)模版通過迭代器獲得輸入數(shù)據(jù)通過函數(shù)對象對數(shù)據(jù)進行處理通過迭代器將結(jié)果輸出STL算法是通用的，獨立于具體的數(shù)據(jù)類型、容器類型STL算法

22、分類不可變序列算法可變序列算法排序和搜索算法數(shù)值算法38算 法不可變序列算法不可變序列算法不直接修改所操作的容器內(nèi)容的算法用于查找指定元素、比較兩個序列是否相等、對元素進行計數(shù)等例：templateInputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);用于查找first, last)區(qū)間內(nèi)pred(x)為真的首個元素39算 法可變序列算法可變序列算法可以修改它們所操作的容器對象包括對序列進行復(fù)制、刪除、替換、倒序、旋轉(zhuǎn)、交換、變換、分割、去重、填充、洗牌的算法及生成一個序列的算法例

23、：templateInputIterator find_if(ForwardIterator first, ForwardIterator last, const T& x);把first, last)區(qū)間內(nèi)的元素全部改寫為x40算 法排序和搜索算法排序和搜索算法對序列進行排序?qū)捎行蛐蛄羞M行合并對有序序列進行搜索有序序列的集合操作堆算法例：template void sort(RandomAccessIterator first, RandomAccessIterator last, UnaryPredicate comp);以函數(shù)對象comp為“”，對 first, last)區(qū)間內(nèi)的數(shù)據(jù)

24、進行排序41算 法數(shù)值算法數(shù)值算法求序列中元素的“和”、部分“和”、相鄰元素的“差”或兩序列的內(nèi)積求“和”的“+”、求“差”的“-”以及求內(nèi)積的“+”和“”都可由函數(shù)對象指定例：templateOutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);對first, last)內(nèi)的元素求部分“和”（所謂部分“和”，是一個長度與輸入序列相同的序列，其第n項為輸入序列前n個元素的“和”），以函數(shù)對象op為“+”運算符，結(jié)果通過result

25、輸出，返回的迭代器指向輸出序列最后一個元素的下一個元素42算 法關(guān)于交換操作(swap)swap的一種通用實現(xiàn)template void swap(T &a, T &b) T tmp = a;a = b;b = tmp;當(dāng)T為vector等數(shù)據(jù)類型時，這種實現(xiàn)有什么問題？以上函數(shù)中，需要進行多次深拷貝執(zhí)行交換操作，有必要深拷貝嗎？43深度探索swap高效的執(zhí)行方式44342堆空間asizecapacityptr14?314257?68bsizecapacityptr交換前交換后以vector型對象為例深度探索對容器實現(xiàn)高效的swap每個容器都有一個成員函數(shù)swap，執(zhí)行高效的交換操作對于每個容

26、器，STL都對swap函數(shù)模版進行了重載，使之調(diào)用容器的成員函數(shù)，從而在對容器使用swap函數(shù)時，執(zhí)行的是高效的交換操作，如：template inline void swap(vector& a, vector& b) a.swap(b);45深度探索STL組件的類型特征思考在一個以迭代器為輸入的算法中，如何表示迭代器所指向元素的類型？類型特征通過類型特征可以獲得與一個類型相關(guān)聯(lián)的其它數(shù)據(jù)類型通過函數(shù)對象的類型特征可以得到函數(shù)對象的參數(shù)和返回值類型通過迭代器的類型特征可以得到迭代器指向元素的類型46深度探索函數(shù)對象的類型特征STL提供的二元函數(shù)對象皆繼承自以下結(jié)構(gòu)體：templatestruct binary_function typedef Arg1 first_argument_type;typedef Arg2 s