C++实用教程[郑阿奇主编]16

1、第16章 标准模板库（STL）,16.1 迭代器,16.1.1 迭代器的由来,在STL中，迭代器是一种“特殊”的指针，用来指定或引用容器中元素的位置 正是因为对不同容器的操作具有相同的实现代码，所以才会形成STL的算法器及迭代器以优化和简化算法代码。,16.1.2 迭代器的类型,STL提供了5种不同的迭代器：输入、输出、正向、双向和随机访问迭代器,（1）输入迭代器。它是一种单向迭代器，只可递增，不可回退 （2）输出迭代器。它是一种单向迭代器，只不过它是向容器中写入元素。 （3）正向迭代器。它是输入迭代器和输出迭代器功能的组合，其操作元素总是向前移动（即支持+操作），与输入迭代器或输出迭代器不同

2、的是，它多次遍历的顺序都是相同的。 （4）双向迭代器。它常用于reserse（逆序）等操作，支持指针的+和操作。 （5）随机访问迭代器。它具有双向迭代器的所有功能，同时增加了直接访问容器中任何元素的功能，即可向前、向后跳过任意多个元素，以及用于对元素排序的关系运算等,16.2 容器类,容器是一个与数组类似的单元，可以存取若干元素 主要容器类有：deque （双端队列）、list（链表、列表）、queue（队列）、stack（栈）、vector（向量）、map（映像）、multimap（多重映像）、set（集合）和multiset（多重集合）,16.2.1 向量、链表和双端队列,1. 模型概述

3、向量、链表和双端队列都可以看成是顺序存储的线性表，只是链表不像向量和双端队列那样具有随机访问的能力 2.deque、list和vector template class vector ; template class deque ; template class list ;,一旦建立了容器类vector、list或deque实例化类对象，就可以通过对象进行下列常用操作 （1）元素的插入操作。用于元素插入操作的成员函数为insert、push_front和push_back （2）元素的删除和清除操作。用于删除元素操作的成员函数有erase、pop_front和pop_ back，clear用

4、于清除操作 （3）元素访问操作。容器类vector和deque除了提供下标运算符“ ”来引用指定位置的对象元素的内存空间外，还提供下列元素访问操作 （4）迭代器和空间大小属性操作。容器类vector、list和deque都提供下列有关迭代器和空间大小属性的常用操作 （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 ,程序运行结果如下：,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 );/ 输出所有结点元素 v.remove(-7 );/ 移除-7结点 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; ,程序运行结果如下：,16.2.2 栈和队列,栈（stack）是一种“FILO”（先进后出）或“LIFO”（后进

8、先出）的线性表，它只允许在表的一端进行插入和删除操作。而队列（queue）是一种“FIFO”（先进先出）的线性表，与栈刚好相反。在队列中，只允许在表的一端插入元素，而在另一端删除元素。 定义对象时，它们都可以有下列简单的形式： X v; X v;/ 使用向量容器来构造 / 注意，vector的最后面是两个大于符号，它们之间一定要有空格,说明 :,（1）ANSI/ISO C+类模板stack和deque中都有一个protected数据成员c，其定义如下： protected: Container c; 但在Visual C+ 2005中，该数据成员是公有的，因此可以在对象中通过c访问构造时指定的

9、容器类模板的成员。对于Visual C+ 6.0需要通过派生才能使用该数据成员c。 （2）另外，类模板stack和deque还都重载了运算符=、=、=，用于两个栈或两个队列之间的关系比较。,例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; 程序运行结果如下：,16.2.3 映像,1. 概述 与map

11、概念相同，关联容器类multimap支持的是多对一关系，即一个键对应于多个值。map和multimap都支持双向迭代器，可以实现多路遍历操作 2. map容器类 容器类map具有下列声明： template , class Allocator = allocator class map;,一旦建立了容器类map的实例化对象，就可以通过实例化类对象进行下列常用操作,（1）元素的插入操作。需要说明的是，这里操作的元素是指“键”和“值”的对子，简称键值对。在容器类map中，用于元素插入操作的成员函数为insert （2）元素的删除和清除操作。容器类map用于删除元素操作的成员函数是erase，用于清

12、除操作的是clear （3）元素访问操作。容器类map只提供下标运算符“ ”来引用指定位置元素的内存空间 （4）迭代器和空间大小属性操作。 （5）映像操作 另外，容器类map还重载了运算符=、=、=，用于两个映像之间的关系比较,例Ex_Map 映像容器类示例,#pragma warning(disable:4786)/ 避免string使用中的警告出现 #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; ,程序运行结果如下：,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; ,程序运行结果如下：,1

17、6.3 算法,16.3.1 概述 STL算法部分主要由头文件、和组成。 16.3.2 copy和流迭代器 1. copy 函数模板copy将序列中某个范围的元素复制到另一个序列中,例Ex_Copy copy函数使用示例,#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; 程序运行结果如下：,2. 流迭代器,输出流迭代器ostream_iterator是STL预定义的迭代器类模板，它具有下列定义： template class ostream_iterator: public iterator public: ostream_iterator(ostream_type,16.3.3 find,函数模板find用于查找，它的原型如下：

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

20、 8, 8, 8 ;/ 整数数组a const int ANUM = sizeof(a) / sizeof(int); IntVector v(a, a+ANUM);/ A：构造 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：循环找出所有大于7的数 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：循环找出所有(5,8)的数 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; ,程序运行结果如下：,16.3.4 sort,函数模板sort用于为指定序列排序，它的原型如下： / sort, RanIt表示随机访问迭代器 template void sort(RanIt first, RanIt last); template void sort(RanIt first, RanIt last, BPred pred); 其功能是将first, last之间的序列按从小到大的升序进行排序,例Ex_Sort sort函数使用示例,#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 ; ,程序运行结果如下：,16.4 综合应用实例,#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