C++實(shí)用教程[鄭阿奇主編]16

1、第16章 標(biāo)準(zhǔn)模板庫（STL）,16.1 迭代器,16.1.1 迭代器的由來,在STL中，迭代器是一種“特殊”的指針，用來指定或引用容器中元素的位置 正是因?yàn)閷Σ煌萜鞯牟僮骶哂邢嗤膶?shí)現(xiàn)代碼，所以才會形成STL的算法器及迭代器以優(yōu)化和簡化算法代碼。,16.1.2 迭代器的類型,STL提供了5種不同的迭代器：輸入、輸出、正向、雙向和隨機(jī)訪問迭代器,（1）輸入迭代器。它是一種單向迭代器，只可遞增，不可回退 （2）輸出迭代器。它是一種單向迭代器，只不過它是向容器中寫入元素。 （3）正向迭代器。它是輸入迭代器和輸出迭代器功能的組合，其操作元素總是向前移動（即支持+操作），與輸入迭代器或輸出迭代器不同

2、的是，它多次遍歷的順序都是相同的。 （4）雙向迭代器。它常用于reserse（逆序）等操作，支持指針的+和操作。 （5）隨機(jī)訪問迭代器。它具有雙向迭代器的所有功能，同時增加了直接訪問容器中任何元素的功能，即可向前、向后跳過任意多個元素，以及用于對元素排序的關(guān)系運(yùn)算等,16.2 容器類,容器是一個與數(shù)組類似的單元，可以存取若干元素 主要容器類有：deque （雙端隊(duì)列）、list（鏈表、列表）、queue（隊(duì)列）、stack（棧）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）,16.2.1 向量、鏈表和雙端隊(duì)列,1. 模型概述

3、向量、鏈表和雙端隊(duì)列都可以看成是順序存儲的線性表，只是鏈表不像向量和雙端隊(duì)列那樣具有隨機(jī)訪問的能力 2.deque、list和vector template class vector ; template class deque ; template class list ;,一旦建立了容器類vector、list或deque實(shí)例化類對象，就可以通過對象進(jìn)行下列常用操作 （1）元素的插入操作。用于元素插入操作的成員函數(shù)為insert、push_front和push_back （2）元素的刪除和清除操作。用于刪除元素操作的成員函數(shù)有erase、pop_front和pop_ back，clear用

4、于清除操作 （3）元素訪問操作。容器類vector和deque除了提供下標(biāo)運(yùn)算符“ ”來引用指定位置的對象元素的內(nèi)存空間外，還提供下列元素訪問操作 （4）迭代器和空間大小屬性操作。容器類vector、list和deque都提供下列有關(guān)迭代器和空間大小屬性的常用操作 （5）鏈表操作。與容器類vector和deque不同的是，容器類list自身還有不同的常用操作，如反序、排序、合并等,例Ex_Vector 向量容器類示例,#include #include / 向量容器類頭文件包含 #include / 迭代器頭文件包含 #include / 算法器頭文件包含 using namespace st

5、d; / 演示iterator操作 void show(vector / 演示操作,#include #include / 向量容器類頭文件包含 #include / 迭代器頭文件包含 #include / 算法器頭文件包含 using namespace std; / 演示iterator操作 void show(vector ,程序運(yùn)行結(jié)果如下：,4. list示例,例Ex_List 鏈表容器類示例。 #include #include / 鏈表容器類頭文件包含 #include / 迭代器頭文件包含 using namespace std; / 演示iterator操作 void sho

6、w(list ,int main() list v; v.push_back( 20 );v.push_back( 40 );v.push_back( 5 );v.push_back( 7); list:iterator ip = v.begin(); ip = v.insert( ip, 13 ); v.insert( ip, -7 ); show( v );/ 輸出所有結(jié)點(diǎn)元素 v.remove(-7 );/ 移除-7結(jié)點(diǎn) v.reverse();show( v ); v.sort();show( v ); list l; l.push_back( 12 );l.push_back( 8

7、);l.push_back( 16 );l.push_back( 7); v.splice( v.end(), l ); show( v );show( l ); v.pop_back();v.pop_back();v.pop_back();v.pop_back(); show( v ); l.push_back( 1 );l.push_back( 8 );l.push_back( 16 ); v.merge( l ); show( v );show( l ); return 0; ,程序運(yùn)行結(jié)果如下：,16.2.2 棧和隊(duì)列,棧（stack）是一種“FILO”（先進(jìn)后出）或“LIFO”（后進(jìn)

8、先出）的線性表，它只允許在表的一端進(jìn)行插入和刪除操作。而隊(duì)列（queue）是一種“FIFO”（先進(jìn)先出）的線性表，與棧剛好相反。在隊(duì)列中，只允許在表的一端插入元素，而在另一端刪除元素。 定義對象時，它們都可以有下列簡單的形式： X v; X v;/ 使用向量容器來構(gòu)造 / 注意，vector的最后面是兩個大于符號，它們之間一定要有空格,說明 :,（1）ANSI/ISO C+類模板stack和deque中都有一個protected數(shù)據(jù)成員c，其定義如下： protected: Container c; 但在Visual C+ 2005中，該數(shù)據(jù)成員是公有的，因此可以在對象中通過c訪問構(gòu)造時指定的

9、容器類模板的成員。對于Visual C+ 6.0需要通過派生才能使用該數(shù)據(jù)成員c。 （2）另外，類模板stack和deque還都重載了運(yùn)算符=、=、=，用于兩個?；騼蓚€隊(duì)列之間的關(guān)系比較。,例Ex_Stack 棧類模板示例。,#include #include / 棧模板頭文件包含 #include / 向量容器類頭文件包含 #include / 迭代器頭文件包含 using namespace std; typedef stack STACK; class CStack : public STACK public: void show()/ 遍歷操作 if (empty() cout:ite

10、rator ip = c.begin();/ 定義指針 while (ip != c.end() cout*ip,t;ip+; coutendl; / 清棧操作 void clear() while (!empty() pop(); ;,int main() CStack v; v.push( 20 );v.push( 40 );v.push( 5 );v.push( 7); v.show(); v.top() = 8;v.show(); v.pop();v.show(); v.clear();v.show(); return 0; 程序運(yùn)行結(jié)果如下：,16.2.3 映像,1. 概述 與map

11、概念相同，關(guān)聯(lián)容器類multimap支持的是多對一關(guān)系，即一個鍵對應(yīng)于多個值。map和multimap都支持雙向迭代器，可以實(shí)現(xiàn)多路遍歷操作 2. map容器類 容器類map具有下列聲明： template , class Allocator = allocator class map;,一旦建立了容器類map的實(shí)例化對象，就可以通過實(shí)例化類對象進(jìn)行下列常用操作,（1）元素的插入操作。需要說明的是，這里操作的元素是指“鍵”和“值”的對子，簡稱鍵值對。在容器類map中，用于元素插入操作的成員函數(shù)為insert （2）元素的刪除和清除操作。容器類map用于刪除元素操作的成員函數(shù)是erase，用于清

12、除操作的是clear （3）元素訪問操作。容器類map只提供下標(biāo)運(yùn)算符“ ”來引用指定位置元素的內(nèi)存空間 （4）迭代器和空間大小屬性操作。 （5）映像操作 另外，容器類map還重載了運(yùn)算符=、=、=，用于兩個映像之間的關(guān)系比較,例Ex_Map 映像容器類示例,#pragma warning(disable:4786)/ 避免string使用中的警告出現(xiàn) #include #include / 映像容器類頭文件包含 #include / 迭代器頭文件包含 #include / 字符串類頭文件包含 using namespace std; typedefmap STR2INT;/ 定義類型名以便后

13、面使用 typedefSTR2INT:iterator POS;/ 定義類型名以便后面使用 / 輸出鍵值對 void showpair( POS pos) cout主鍵為：(*pos).first,t值為：(*pos).secondendl; / 遍歷輸出 void show(STR2INT / 顯示某范圍的鍵值對，演示lower_bound和upper_bound,void showu( STR2INT ,int main() STR2INT v; / 添加操作 v.insert( STR2INT:value_type(Zero, 0) ); v.insert( STR2INT:value_

14、type(One, 1) ); v.insert( STR2INT:value_type(Two, 2) ); v.insert( STR2INT:value_type(Three, 3) ); vFour = 4;vFive = 5; vSix = 6;vSeven = 7; vEight = 8; show(v); / 刪除操作 cout pp = v.equal_range( FIVE ); showpair( pp.first ); showpair( pp.second ); return 0; ,程序運(yùn)行結(jié)果如下：,16.2.4 集合,容器類set具有下列聲明： template

15、, class Allocator = allocator class set ;,例Ex_Set 集合容器類示例。,#pragma warning(disable:4786) #include #include / 映像容器類頭文件包含 #include / 迭代器頭文件包含 #include / 字符串類頭文件包含 using namespace std; typedefset STRSET;/ 定義類型以便后面使用 typedefSTRSET:iteratorPOS;/ 定義類型以便后面使用 / 遍歷輸出 void show(STRSET / 顯示某范圍的鍵值對，演示lower_boun

16、d和upper_bound,void showu( STRSET ,int main() STRSET v; / 添加操作 v.insert( Zero );v.insert( One );v.insert( Two ); v.insert( Three );v.insert( Four );v.insert( Five ); v.insert( Six ); show(v); / 刪除操作 cout pp = v.equal_range( FIVE ); cout*( pp.first )endl; cout*( pp.second )endl; return 0; ,程序運(yùn)行結(jié)果如下：,1

17、6.3 算法,16.3.1 概述 STL算法部分主要由頭文件、和組成。 16.3.2 copy和流迭代器 1. copy 函數(shù)模板copy將序列中某個范圍的元素復(fù)制到另一個序列中,例Ex_Copy copy函數(shù)使用示例,#include #include #include #include using namespace std; typedef vector IntVector ; int main() int arr10 = 2, 3, 7, 8, 4, 11, 5, 9, 1, 13 ; IntVector v(8); copy( arr, arr+8, v.begin() ); ost

18、ream_iterator out(cout, ); copy(arr, arr+10, out); cout endl ; copy(v.begin(), v.end(), out); cout endl ; return 0; 程序運(yùn)行結(jié)果如下：,2. 流迭代器,輸出流迭代器ostream_iterator是STL預(yù)定義的迭代器類模板，它具有下列定義： template class ostream_iterator: public iterator public: ostream_iterator(ostream_type,16.3.3 find,函數(shù)模板find用于查找，它的原型如下：

19、template InIt find(InIt first, InIt last, const T,例Ex_Find find函數(shù)使用示例。,#include #include #include #include using namespace std; typedef vector IntVector ; class USERDO public: bool operator()(int i)/ 運(yùn)算符“()”重載函數(shù) return (i5) ,int main() ostream_iterator out(cout, ); int a = 1, 3, 5, 6, 6, 7, 7, 7, 8,

20、 8, 8, 8 ;/ 整數(shù)數(shù)組a const int ANUM = sizeof(a) / sizeof(int); IntVector v(a, a+ANUM);/ A：構(gòu)造 copy(v.begin(), v.end(), out); cout(), 7) ); if ( it != v.end() cout找到 *it 的位置在：it-v.begin()endl; start = it + 1; while (it!=v.end(); cout-endl; start = v.begin();,do / C：循環(huán)找出所有大于7的數(shù) it = find_if( start, v.end(

21、), bind2nd(greater(), 7) ); if ( it != v.end() cout找到 *it 的位置在：it-v.begin()endl; start = it + 1; while (it!=v.end(); cout-endl; start = v.begin(); do / D：循環(huán)找出所有(5,8)的數(shù) it = find_if( start, v.end(), USERDO() );/ E if ( it != v.end() cout找到 *it 的位置在：it-v.begin()endl; start = it + 1; while (it!=v.end()

22、; return 0; ,程序運(yùn)行結(jié)果如下：,16.3.4 sort,函數(shù)模板sort用于為指定序列排序，它的原型如下： / sort, RanIt表示隨機(jī)訪問迭代器 template void sort(RanIt first, RanIt last); template void sort(RanIt first, RanIt last, BPred pred); 其功能是將first, last之間的序列按從小到大的升序進(jìn)行排序,例Ex_Sort sort函數(shù)使用示例,#include #include #include #include using namespace std; cla

23、ss C2Pred public: C2Pred(int a, int b) :first(a), second(b) void show() cout(first, second)endl; bool operator (const C2Pred ,int main() vector vect; int i; for(i = 0; i 5; i+) C2Pred ob(10-i, i*3); vect.push_back(ob); for(i = 0; i vect.size(); i+) vecti.show(); cout按first值從小到大排序:endl; sort(vect.beg

24、in(), vect.end(); for(i = 0; i vect.size(); i+) vecti.show(); cout按second值從小到大排序:endl; sort(vect.begin(), vect.end(), less_second); for(i = 0; i vect.size(); i+) vecti.show(); return 0 ; ,程序運(yùn)行結(jié)果如下：,16.4 綜合應(yīng)用實(shí)例,#include #include #include / 鏈表類頭文件包含 #include / 迭代器頭文件包含 #include #include #include using

25、 namespace std; class CStudent; ostream,class CStudent public: CStudent() CStudent(char* name, char* id, float s1, float s2, float s3); void print( int n = -1); char *GetName()return strName; friend ostream ,void CStudent:print( int n )/ n為序號，0) cout0) coutsetw(6)n; coutsetw(20)strNamesetw(10)strID setw(10)fScore0setw(10)fScore1setw(10)fScore2 setw(10)totalendl; ostream ,class CStuList public: voidAdd(CStudent stu);/ 添加記錄 intSeek(char* name, CStudent ,void