C标准模块库STL及其程序设计PPT课件

1、第6章 C+标准模块库(STL)及其程序设计 6.1 STL简介 6.2 vectors 6.3 STL与模板 6.4 迭代器 6.5 算法 6.6 容器 6.7 总结 第1页/共301页6.1 STL 简 介 由于C/C+和Microsoft Windows控制的环境的声望不断扩大，许多第三方销售商以提供例行程序的方式发展极其有利可图的产品，这些库被设计用来存储和处理数据。为了继续维护C/C+的生存能力，使其成为值得选择的程序设计语言，ANSI/ISO C+通过严格控制C/C+语言和正规定义，使其不断发展，并增加了定义这些库的一个新方法，即标准模板库STL。第2页/共301页 6.1.1 初

2、识STL 简而言之，STL封装了C/C+的原始能力，再加上数据结构中讲的先进高效的算法，绑定成了一个简单实用的形式。 可以将STL看作一个可扩充的框架，其中包含一些组件，如语言支持、诊断程序、通用工具、字符串、本地化、容器、迭代符、算法、数值量和输入/输出。其中，容器、迭代符、算法是STL的核心。第3页/共301页 6.1.2 STL和HP公司 STL是由HP公司的Alexander Stepanov和Meng Lee开发的，STL被期望成为保存和处理数据的一个标准方法。主要编译器销售商正开始将STL结合到其产品中。STL不只是作为一个次要的部分添加到世界上最流行的程序设计语言中，它代表着一种

3、革命性和能力。STL为C+程序设计语言带来一组成熟得使人惊奇的类属容器和算法，为C/C+增加了新的一面。第4页/共301页 6.1.3 大众化的STL 从类属类到模板，然后再到最好的跨平台、可移植的标准模板STL，是一个越来越方便程序员的过程。STL越来越大众化。第5页/共301页 6.1.4 STL总览 尽管STL的规模很大，并且其语法初看上去有些令人生畏，但实际上一旦理解其构造以及使用的元素，STL是很容易使用的。STL的核心是三个基础项，它们分别称为容器(Container)、算法(Algoithm)和迭代器(Iterator)。这些库一起工作，可以以一种可移植的格式产生常用算法的解决方

4、案，比如创建数组、元素插入/删除、排序和元素输出。STL甚至还进一步提供了内部清晰、无缝、高效的输入/输出流(Iostream)集成和异常处理。 第6页/共301页 6.1.5 STL基本组件 在概念上，STL包含三个分开的算法问题求解工具，这三个最重要的部分是容器、算法和迭代器。容器是数据在内存中的组织方法，例如数组、堆栈、队列、链表或二叉树。然而，还有许多其他种类的容器，STL包括那些最有用的容器。STL容器是用模板类实现的，因此可以容易地定制它们以得到不同类型的容器。第7页/共301页 所有的容器有共同的管理成员函数，在其模板中定义insert( )、erase( )、begin( )、

5、end( )、size( )、capacity( )等，各容器有支持其自身需要的成员函数。 算法是应用在容器上以各种方法处理其内容的行为或能力。例如，有对容器内容排序、复制、检索和合并的算法。在STL中，算法是由模板函数表现的，这些函数不是容器类的成员函数，而是独立的函数。的确，STL的令人吃惊的特点之一就是其算法如此通用，不仅可以将其用于STL容器，而且可以用于普通的C+数组或任何其他应用程序指定的容器。第8页/共301页 一组标准的算法为容器中的对象提供了检索、复制、排序、变换和数值操作功能。同一算法可用来为所有的对象类型的所有容器执行某一项特别的操作。 一旦选定一种容器类型和数据行为，那

6、么下面惟一要做的是用迭代器使其相互作用。可以把迭代器看作一个指向容器中元素的普通指针，可以像递增一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL的一个关键部分，因为它将算法和容器连在一起。第9页/共301页 6.1.6 其他STL组件 除了容器、算法和迭代器之外，STL还定义了另外几种组件： (1) 分配算符：为单个容器管理内存分配。 (2) 谓词：它们在本质上是一元或二元的，即其作用于一个或两个操作数并总是返回“真”或“假”。 (3) 比较函数：一种独特的二元谓词，比较两个元素并只在第一个参数小于第二个时返回“真”。 (4) 函数对象：包括加、减、乘、除、取模、取反

7、、等于、不等于、大于、大于或等于、小于、小于或等于、逻辑与、逻辑或以及逻辑非。 第10页/共301页 6.1.7 完整的STL程序包 现将STL的结构组件在逻辑上归纳为以下3类。 (1) STL头文件可以分成三个主要的组织概念： 容器是支持普通数据组织方法的模板类，包括、和。 算 法 是 对 对 象 序 列 执 行 普 通 操 作 的 模 板 函 数 ， 包 括、和。 迭代器是把算法和容器粘在一起的黏合剂，包括、和。第11页/共301页 (2) 输入/输出包括以下各项内容的组件： 输入/输出流的向前声明； 预定义输入/输出流对象； 基输入/输出流类； 流缓冲； 流格式和操纵器、和； 字符串流；

8、 文件流。 (3) 其余标准C+头文件包括语言支持、诊断、字符串、文化语言等组件。 第12页/共301页 语言支持包括： 在整个库中使用的普通类型定义的组件； 预定义类型、和的特征； 支持C+程序开始和结束的函数； 对动态内存管理的支持； 对动态类型标识符的支持； 对异常处理的支持； 其他运行时的支持、和。第13页/共301页 诊断包括以下各项内容的组件： 报告几种异常情况； 用文件证明程序断言； 错误数字代码的全局变量。 字符串包括以下各项内容的组件： 字符串类； 以NULL结尾的顺序工具、和。 文化语言组件包括字符分类和字符串校对，数字、货币和日期/时间的格式 和 分 析 ， 以 及 消

9、息 检 索 的 国 际 化 支 持 ， 这 可 以 使 用 和组件。第14页/共301页6.2 vectors 6.2.1 vector程序实例 让我们先看一个具体的例子，以此对容器、迭代器和算法有一些感性的认识，然后再逐步介绍STL。 #include #include #include 第15页/共301页 #include #include using namespace std; int main( ) vector ivec; cout size= ivec.size( ) endl; ivec.push_back(1); ivec.push_back(5);第16页/共301页 i

10、vec.push_back(9); ivec.push_back(3); ivec.push_back(7); cout size= ivec.size( ) endl; vector:iterator ite; for(ite=ivec.begin( ); ite!=ivec.end( );+ite) cout *ite ; cout endl;第17页/共301页 ite=find(ivec.begin( ), ivec.end( ), 9); if(ite!=0) ivec.insert(ite,11); cout size= ivec.size( ) endl; cout *ite ;

11、 for(ite=ivec.begin( ); ite!=ivec.end( );+ite) cout *ite ; cout endl;第18页/共301页 ite=find(ivec.begin( ), ivec.end( ), 3); if(ite!=0) cout *(ivec.erase(ite) endl; for(ite=ivec.begin( ); ite!=ivec.end( );+ite) cout *ite ; cout endl; sort(ivec.begin( ), ivec.end( ),greater( ); for(ite=ivec.begin( ); ite

12、!=ivec.end( );+ite) cout *ite ;第19页/共301页 cout endl; return 0; 程序的输出结果为： size=0 size=5 1 5 9 3 7 size=6 11 1 5 11 9 3 7 7 1 5 11 9 7 11 9 7 5 1第20页/共301页 STL的vector是一个简单的容器。在计算中，vector对应数组。vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问效率很高，因为每次访问离vector的起始处的位移都是固定的。但是，在不是vector末尾的任意位置插入或删除元素，效率很低。由此

13、可见，vector类提供了与数组类似的操作，即可以创建vector对象，将一个vector对象赋给另一个vector对象，并使用 操作符来访问vector元素。要使类成为通用的，应将它设计成模板类。这正是STL的工作，即在头文件vector中定义了一个vector模板。第21页/共301页 6.2.2 初始化 要创建vector模板对象，可用通常的表示法来指出要使用的类型。在节的程序中创建了int类型的 vector对象ivec： vector ivec; 现在我们有了一个vector容器，可以使用它来装东西了。vector的成员函数push_back( )把一个对象放到一个vector对象的

14、后面。现在，对象ivec中有了5个元素，它们是1、5、9、3、7。第22页/共301页 另外，vector模板使用动态内存分配，因此可以用参数来创建vector对象，例如： #include #include using namespace std; vector ivec(5); /有5个整型元素的向量 vector svec(24, tiger); /有24个字符串的向量第23页/共301页 各种STL容器模板都要接受一个可选的模板参数，该参数用于指定使用哪个分配器对象来管理内存。例如，vector模板的开头与以下代码类似： template class T, class Allocato

15、r class vector.； 如 果 省 略 该 模 板 参 数 的 值 ， 则 容 器 模 板 将 默 认 使 用allocator类。这个类以标准方式使用new和delete。第24页/共301页 6.2.3 vector容器的方法 所有的STL容器都提供了一些基本的方法，其中包括：size( )返回容器中元素的数目；swap( )交换两个容器的内容；begin( )返回一个指向容器中第一个元素的迭代器；end( )返回一个表示超过容器尾的迭代器。但是，并非所有的STL容器都具有方法push_back( )，稍后我们还会提及。 什么是迭代器呢？简单地说，它是一个广义指针。事实上，它可以

16、是指针，也可以是一个可对其执行类似指针操作的对象(如operator*( )和operator+( )。第25页/共301页 对指向容器的指针进行广义化，使得STL能够为各种不同的容器类(包括那些简单指针无法处理的类)提供统一的接口。每个容器类都定义了一个合适的迭代器，该迭代器的类型是一个名为iterator的typedef，其作用域为整个类。要使用迭代器，必须包含头文件。在节中的程序中为ivec声明了一个int类型的迭代器： vector:iterator ite; 正如在程序中所见到的，迭代器的行为就像指针。第26页/共301页 注意：容器的end( )函数会返回一个指向容器结束点的ite

17、rator。结束点在最后一个元素之后，程序运行到此就停止操作，所有的STL容器都要这样做。这样的迭代器又称作逾尾(past-the-end)迭代器。容器的begin( )和end( )函数如图6-1所示。第27页/共301页图6-1 容器的begin( )和end( )函数 begin( )end( )第28页/共301页 由图6-1可以看出，begin( )和end( )形成了一个半开区域，从第一个元素开始，到最后一个元素的下一个位置结束。半开区域有以下优点： (1) 为访问元素时的循环结束时机提供了一个简单的判断依据。只要尚未达到end( )，循环就可以继续进行下去。 (2) 不必对空区间

18、采取特殊处理手法。空区间begin( )就等于end( )。 在节的程序中，每一次执行for循环，都重复引用ite得到我们打印的容器中的元素。第29页/共301页 还有一个erase方法，它用于删除vector中给定区间的元素。它接受两个迭代器参数，这些参数定义了要删除的区间。 Insert( )方法的功能与erase( )方法相反。它接受两个参数，第一个参数指定了新元素的插入位置，第二个参数定义了被插入的元素；或者接受3个参数，第一个参数指定了新元素的插入位置，第二个参数和第三个参数定义了被插入区间，该区间通常是另一个对象的一部分。例如： 第30页/共301页 例如： vector one;

19、 vector two; one.insert(one.begin( ), two.begin( )+1, two.end( ); 将对象two中除第一个元素外的所有元素插入到one的第一个元素的前面。第31页/共301页 6.2.4 对vector可执行的其他操作 程序员通常要对数组执行很多操作，如搜索、排序和随机排序等。vector模板类并没有包含执行这些常见操作的方法。STL从更广泛的角度定义了非成员函数来执行这些操作，即不是为每个容器类定义find( )成员函数，而是定义了一个适用于所有容器类的非成员函数find( )。这种设计理念省去了大量重复的工作，例如，假设有8个容器类，需要支持

20、10种操作，如果每个类都有自己的成员函数， 第32页/共301页 则需要定义80个成员函数，但采用STL方式时，只需定义10个非成员函数即可。在定义新的容器类时，只要遵循正确的指导思想，则它也可以使用已有的非成员函数来执行查找、排序等操作。 节的程序中使用了具有代表性的STL算法：sort( )。sort( )算法要求容器支持随机访问。该算法有两个版本，第一个版本接受两个定义区间的迭代器参数，并使用为存储在容器中的类型元素定义的“”操作符，对区间中元素进行操作。 第33页/共301页 例如，执行代码 sort(ivec.begin( ), ivec.end( ); 将按升序对ivec的元素进行

21、排序，排序使用内置的“”操作符对值进行比较。 在第二个版本中，用户可以使用已定义的能够处理该类型对象的函数对象(或指向函数的指针)，返回值可转换为bool的false。就如同在节的程序中，sort( )接受3个参数，前两个参数是指向区间的迭代器，最后一个参数就是要使用的函数对象(或指向函数的指针)：第34页/共301页 sort(ivec.begin( ), ivec.end( ), greater( ); 该语句的执行结果是将ivec中的对象按升序排列。 通过前面的介绍，我们对STL有了初步的了解，STL旨在编写独立于数据类型的代码。在C+中，完成通用程序的工具是模板。当然，模板使得能够按通

22、用类型定义函数或类，而STL通过通用算法使得完成计算更方便。第35页/共301页6.3 STL 与 模 板 STL出色地利用了指针、函数重载和运算符重载，另外，它还十分依赖于模板。在查看一个STL实例之前，先看下面这一简明易懂的C代码段，它使用了#define和连接符(#)预处理语句定义了一个二叉树节点。第36页/共301页 C example #define BINARY_TREE( t ) typedef struct _tree_#t t data; struct _tree_#t *left; struct _tree_#t *right; BINARY_TREE_#;第37页/共30

23、1页 应注意预处理器是如何用用户选择的数据类型替换参数t的，例如： BINARY_TREE( int ); BINARY_TREE( float ); BINARY_TREE( my_structure ); 然后，程序完全重定义了这一节点。例如，对于int数据类型，二叉树节点的定义将变为： typedef struct_tree_int int data;第38页/共301页 struct_tree_int *left; struct_tree_int *right; BINARY_TREE_int; 这只是个有关C/C+语言提供的固有模块性的例子。上面的几个例子在C中都是合法的，不需要附加

24、C+的任何语法。第39页/共301页 尽管上例解决了节点能存放不同类型数据的问题，但是仍然有缺点：与可以产生宏的内联(inline)函数不同，#define定义的宏没有错误检查能力。#define语句所做的是由C/C+的两次编译之一严格地完成字符串查找和替换操作。显然，为了产生可靠和可移植的代码，必须有一些其他的方法，以产生可靠的定义，这一方法就是C+模板。第40页/共301页 6.3.1 template关键字 模板是在ANSI/ISO C+标准中的高级特性之一。正如Bjarne Stroustrup(C+的作者之一)说的那样，“模板被认为是设计适当的容器类所必需的”。对许多人来说，C+最大

25、的一个问题是缺少可扩展的标准库。为产生这样的库，最大的问题是C+没有提供一个充分通用的工具用于定义诸如列表、向量和联合数组这样的“容器类”。将模板结合到C+语言中直接导致了STL的出现，STL是使用模板类和模板函数的容器类和算法的标准化库。第41页/共301页 6.3.2 模板语法 作为一个程序员，一定要理解函数和函数调用的概念。函数包含一个模块化设计、可重复使用和求解单一问题的算法。在执行调用程序的算法时，函数调用为正在执行的程序传递需要的实际参数。 C+模板以完全新的方式使用参数：创建新函数和类。与为函数传递参数不同，模板是在编译而不是运行时创建这些新函数和类的。第42页/共301页 模板

26、的语法为： template declaration 程序员在关键字template和参数列表(argument_list)之后提供模板声明。在此处，定义参数化的类或函数的版本。在使用模板时，由C+编译器根据传递给模板的参数负责产生类或函数的不同版本。第43页/共301页 6.3.3 模板函数 要理解模板如何在STL中发挥作用，需要知道两种类型的模板：类模板和函数模板。函数模板产生函数，而类模板产生类。 下面的程序定义了一个求任何数据类型的数据平方的函数模板。 template Type squareIt( Type x ) return x*x; /函数模板第44页/共301页 可以为函数模

27、板squareIt( )传递任何合适的数据类型，例如： void main( void ) cout The square of the integer 9 is: squareIt(9); c o u t T h e s q u a r e o f t h e u n s i g n e d i n t 2 5 5 i s : squareIt(255u); cout The square of the float 10 is: squareIt(10.0); /. 第45页/共301页 这三条语句使编译器在编译时产生如下三个独立的函数体，一个是整型数据的实例，另一个是无符号整型的实例，第三

28、个是浮点型的实例： int square( int x ) return x*x; unsigned int square( unsigned int x ) return x*x; double square( double x ) return x*x; 第46页/共301页 6.3.4 模板类 第二类模板是类模板，下面的程序定义了一个数组容器类模板。第47页/共301页 template class Array protected: Type *pTypeArray; public: Array( ) pTypeArray=new Type MAX_ELEMENT ; Array( )

29、delete pTypeArray; /. ;第48页/共301页 这一模板类定义创建了一个任意类型的数组容器类。模板的第一个参数用于定义数组存放的元素的类型，第二个参数用于定义数组保存的元素的个数。这一数组的类型可以是任意的，从标准C+的简单数据类型(如int)到应用程序指定的复杂的结构。 程序实例化一个实际模板类定义的实例时，使用几乎与函数一样的语法：第49页/共301页 void main (void) Array fArray; Array iArray; Array strucArray; Array strucArray; /. 第50页/共301页 6.3.5 STL与模板的比较

30、 理论上，C+模板满足了对容易使用的容器类的需要，但在实际中，尚有几个问题存在。首先是模板容器类的实现中固有的问题，基于模板的容器可能明显比对应的基于C的慢。例如，许多基于模板的容器类依赖于继承性，而某些继承性可能显著地减慢程序。 另一个问题是兼容性。如果碰巧使用的是来自不同销售商的两个模板，可能在其间有兼容性冲突，因为模板没有标准。第51页/共301页 而兼容性问题比定制代码的问题还要小。在某种程度上，定制代码是使用模板编程的一个正常部分。以一个VehicleSaleRecord类为例，该类将使用链表模板工作。对于这一类，不得不定义诸如小于()这样的操作，提供这些操作对于每个类，都将使用模板

31、类作为开销。第52页/共301页 要使用模板类，程序员必须定制容器中的对象，而不是容器模板本身。当需要改变模板的工作方式时，问题就会出现，例如，假设需要定制项目的排序方法。要使用基于模板的类，就必须理解模板的初始代码，修改此原码，并重新编译程序，当然条件是假设有进入最初的模板定义的途径(也可能没有这种途径)，但是修改了代码的模板可能不会保持其原来的功能。 总之，由于基于模板的容器类内在地要慢一些，并且模板在历史上没有形成标准, 又不容易定制，因此需要有更好的方法，这是STL应运而生的原因之一。第53页/共301页6.4 迭 代 器 无论何时，应用程序在容器的元素中移动时，都要使用迭代器。什么是

32、迭代器呢？可把迭代器理解为用来访问个别数据项的指针。事实上，iterator可以定义为：提供一种方法，使之能访问某个容器所含的各个元素，而又无需暴露该容器的内部表述方式。第54页/共301页 6.4.1 迭代器的使用 理解迭代器是学习STL的关键所在。模板使得算法独立于存储的数据类型，而迭代器使得算法独立于使用的容器类型。 为了了解为何需要使用迭代器，我们来看如何为两种不同数据表示实现find( )函数，然后再看如何推广这种方法。下面是一个在int数组中搜索特定值的函数。第55页/共301页 int *find_ar(int *ar, int n, const int &val) fo

33、r(int i=0; ip_next) if(start-elem=val) return start; return 0; 第59页/共301页 同样也可以使用模板将这种算法推广到包含“=”操作符的、任意类型的链表。尽管如此，这种算法仍与一种特定的数据结构(链表)关联在一起。 从实现细节上看，这两个find函数的算法是不同的：一个使用数组索引来遍历元素，另一个则将start重置为start-p_next。不过从广义上说，这两种算法是相同的：将值依次与容器中的每个值进行比较，直到找到匹配的为止。第60页/共301页 STL旨在使用同一个find函数来处理数组、链表或任何其他容器类型。即算法不仅

34、独立于容器中存储的数据类型，而且独立于容器本身的数据结构。模板提供了存储在容器中的数据类型的通用表示，因此还需要遍历容器中的值的通用表示，迭代器正是这样的通用表示。 要实现find算法，迭代器应具备哪些特征呢？下面是一个简短的特征列表。 应能够对迭代器执行解除引用的操作，以便能够访问它引用的值。即如果p是一个迭代器，则应明显地对*p进行定义。第61页/共301页 应能够将一个迭代器赋给另一个。即如果p和q都是迭代器，则应对表达式p=q进行定义。 应能够将一个迭代器与另一个进行比较，看它们是否相等。即如果p和q都是迭代器，则应对p=q和p!=q进行定义。 应能够使用迭代器遍历容器中的所有元素，这

35、可以通过为迭代器p定义+p和p+来实现。 迭代器也可以完成其他操作，但有上述功能就足够了，至少对find( )算法是如此。实际上，STL按功能强弱定义了多种级别的迭代器，这将在后面介绍。顺便说一句，常规指针就能满足迭代器的要求。因此，可以这样重新编写find_ar( )函数。 第62页/共301页 typedef int *iterator; int find_ar(iterator ar, int n, const int &val) for(int i=0; iitem; iterator& operator+( ) /定义+iterator pt=pt-p_next; r

36、eturn *this 第67页/共301页 iterator& operator+(int) /定义iterator+ iterator tmp=*this; pt=pt-p_next; return tmp; /.operator=( ),operator!=( )等 ;第68页/共301页 为 区 分 “ + + ” 操 作 符 的 前 缀 版 本 和 后 缀 版 本 ， C + + 将operator+作为前缀版本，将ioperator(int)作为后缀版本，其中的参数永远也不会被用到，因此不必指定其名称。 这里重点不是如何定义iterator类，而是有了这样的类后，第二个fi

37、nd函数就可以这样编写：第69页/共301页 iterator find_ll(iterator head, const int &val) iterator start; for(start=head; start!=0; +start) if(*start=val) return start; return 0; 第70页/共301页 这和find_ar( )几乎相同，差别在于如何判断已到达最后一个值：find_ar( )函数使用逾尾迭代器，而find_ll( )使用存储在最后一个节点中的空值。除了这种差别外，这两个函数完全相同。例如，可以要求链表的最后一个元素后面还有一个额外的元

38、素，即让数组和链表都有逾尾元素，并在迭代器到达逾尾位置时搜索结束。这样，find_ar( )和find_ll( )检测数据尾的方式将相同，从而成为相同的算法。注意，增加逾尾元素后，对迭代器的要求变成了对容器类的要求。第71页/共301页 STL遵循上面介绍的方法。首先，每个容器类(vector、list、deque等)定义了相应的迭代器类型。对于其中的某个类，迭代器可能是指针，而对于另一个类，则可能是对象。不管实现的方式如何，迭代器都将提供所需的操作，如operator *r和operator+(有些类需要的操作可能比其他类多)。其次，每个容器类都有一个逾尾标记，当迭代器递增到超越容器的最后一

39、个值后，这个值将被赋给迭代器。begin( )和end( )方法返回一个指向容器的第一个元素和逾尾位置的迭代器。使用+操作，让迭代器从第一个元素逐步指向逾尾位置，就可以遍历容器中的每个元素。第72页/共301页 使用容器类时，无需知道其迭代器是如何实现的，也无需知道逾尾是如何实现的，而只需知道它有迭代器，其begin( )返回一个指向第一个元素的迭代器，end( )返回一个指向逾尾位置的迭代器即可。例如： vector:iterator pr; for(pr=scores.begin( ); pr!=scores.end( ); pr+) cout *pr endl;第73页/共301页 其中

40、代码行 vector:iterator pr; 将 p r 的 类 型 声 明 为 v e c t o r 类 的 迭 代 器 。 如 果 要 使 用list类模板来存储分数，则代码如下： list:iterator pr; for(pr=scores.begin( ); pr!=scores.end( ); pr+) cout *pr endl;第74页/共301页 惟一不同的是pr的类型。因此，STL通过为每个类定义适当的迭代器，并以统一的风格设计类，能够对内部表示绝然不同的容器编写相同的代码。 实际上，就风格方面而言，最好避免直接使用迭代器，而应尽可能使用STL函数(如for_each(

41、 )来处理细节。第75页/共301页 6.4.2 迭代器类型 在STL中，迭代器用一个迭代器类的对象表示。可以用C/C+增量运算符“+”递增一个迭代器，将其移入下一个元素的地址；也可以使用取内容运算符“*”访问当前项目中的个别成员，专门的迭代器能够记住指定容器元素的位置。可以把迭代器看作一种smart pointer，它能够把指向下一个元素的意图转换成合适的操作。第76页/共301页 不同的算法对迭代器的要求不同。例如，查找算法需要定义“+”操作符，以便迭代器能够遍历整个容器；它要求能够读取数据，但不要求能够写数据(它只是查看数据，而并不修改数据)，而排序算法要求能够随机访问，以便能够交换两个

42、不相邻的元素。如果iter是一个迭代器，则可以通过定义“+”操作符来实现随机访问，这样就可以使用像iter+10这样的表达式了。另外，排序算法要求能够读写数据。第77页/共301页 STL定义了几种不同的迭代器类，它们必须与特定的容器一起使用。主要的三个迭代器类是向前、双向和随机存取迭代器。另外，STL定义了两个专用迭代器，即输入和输出迭代器。 (1) 向前迭代器(Forward Iterator)在容器中只能向前进，使用“+”操作符来遍历容器，每次一个项目。向前迭代器不能向后移动，也不能被更新以指向容器中间的任何位置。向前迭代器既可以使其能够读取和修改数据，也可以使其只能读数据，代码如下：第

43、78页/共301页 int *pirw;/读写迭代器 const int *pir;/只读迭代器 使用向前迭代器算法的代码如下： template void replace(ForwardIterator first，ForwardIterator last，const Type& old_value，const Type& new_value );第79页/共301页 (2) 向后迭代器(Backward Iterator)的工作方式与对应的向前迭代器类似，只是向后移动。 (3) 双向迭代器(Bidirectional Iterator)可以向前或向后移动，而不能被赋值或更新

44、以指向容器中间的任何元素。双向迭代器具有向前迭代器的所有特性，同时支持两种(前缀和后缀)递减操作符。第80页/共301页 使用双向迭代器算法的代码如下： template BidirectionalIterator partition(BidirectionalIterator first，BidirectionalIterator last，UnaryPredicate pred)； partition( )用于对first,last范围内的元素进行重新排序。当它传递一个一元谓词操作pred时，所有计算结果为true的元素都被放在结果为false的元素前面。第81页/共301页 (4) 随机

45、存取迭代器(Random Access Iterator)比双向迭代器功能更强，它允许应用程序在容器内执行任意的位置跳转。随机访问迭代器具有双向迭代器的所有特性，同时添加了支持随机访问的操作(如指针增加运算)和用于对元素进行排序的关系操作符。 使用随机存取迭代器的sort( )算法的一个版本如下： template void sort(RandomAccessIterator first, RandomAccessIterator last);第82页/共301页 (5) 输入和输出迭代器可以指向特定的设备。例如：一个输入迭代器可以指向用户指定的一个文件，如cin，然后将其顺序读入容器；同样，

46、一个输出迭代器可以指向用户指定的一个输出文件，如cout，并执行相反的逻辑操作顺序输出容器的元素。 输入迭代器(Input Iterator)和输出迭代器(Output Iterator)不像向前、向后、双向和随机存取迭代器那样能保存其当前地址。向前、向后、双向和随机存取迭代器中必须存放有元素地址，以便于知道其在容器中的位置。而由于输入和输出迭代器是指向设备的指针，在结构上不表现同样类型的信息，因此没有地址记忆功能。第83页/共301页 使用输入和输出迭代器的代码如下： template OutputIterator transform(InputIterator first，InputIte

47、rator last，OutputIterator result， Unaryoperation op);第84页/共301页 Transform( )将op作用在first,last范围内的每一个元素上，从而产生一个新的序列。 设计算法时，如果可能，我们尽量针对某种迭代器提供一个明确的定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同的情况下提供最大效率。表6-1总结了主要的迭代器功能。 第85页/共301页表6-1 迭 代 器 功 能 迭代器功能输入输出向前双向随机访问解除引用读取有无有有有解除引用写入无有有有有固定和可重复排序无无有有有+i， i+有有有有有i, i无无无有有i

48、n无无无无有i+n无无无无有in无无无无有i+=n无无无无有i=n无无无无有第86页/共301页 iterator有很好的定义继承性，它们非常有用。某些iterator仅支持对一个容器只读，某些仅支持写，有一些仅能向前指，有一些是双向的，还有一些支持对一个容器的随机存取。 STL算法需要某个iterator作为“动力”，如果一个容器不提供iterator作为“动力”，那么这个算法将无法编译。例如，list容器仅提供双向的iterator。通常的sort( )算法需要随机存取的iterator，这就是为什么我们需要一个特别的list成员函数sort( )。 第87页/共301页 要在实际中合适地

49、使用STL，需要仔细学习各种不同的iterator；需要知道每种容器都支持哪类iterator；需要知道算法需要哪种iterator；也需要懂得可以有哪种iterator。 STL倾向于自动把代码组织成清晰的控制和支持模块，并通过小心使用函数对象给它们起有意义的名字。第88页/共301页6.5 算 法 6.5.1 算法的定义 算法不是作为类的方法，而是作为独立的模板函数实现的。也就是说，STL中最类似于传统函数库的那一部分就是算法。STL中算法的主要特点在于：算法是一些模板函数。它们并不是作为预先编译好的对象模块组成的可链接库来提供的。确切地说，它们一般都完整地定义在STL头文件中。我们可以以

50、众多的方式来特化每一个模板函数，以此极大地提升它作为泛型程序组件的适用性。第89页/共301页 算法与迭代器的配合：除了少量的例外情况外，这些模板函数都使用迭代器作为其参数，在序列上进行各种操作。 算法与容器的配合：算法和STL容器之间合作得非常好。实际上，许多容器模板类的成员函数为突出其优势而使用算法，但是，对容器的理解并不是算法所必需的。算法并不直接使用STL容器。确切地说，算法通过使用这些容器对象的成员函数提供的迭代器来操作容器对象所管理的序列。可以在不知道容器的前提下理解算法，但在一点也不了解算法的前提下想把容器描述清楚就不那么简单了。第90页/共301页 算法在两个头文件和中定义。另

51、外，还有一个头文件，在它里面定义了许多用于描述函数对象的模板类，很多算法可以使用这些函数对象以发挥其优势。 算法为容器提供了实例化、排序、检索和数据变换功能。在迭代器的协助下，算法可以应用于任意容器之上。有趣的是，由于算法不是作为类的方法，而是作为独立的模板函数实现的，因此，算法不仅作用于STL容器，而且作用于标准C+数组或程序员自己创建的容器类。典型的算法包括：第91页/共301页 (1) 查找算法。13个查找算法为判断容器中是否存在一个值提供了各种策略。这13个算法是adjacent_find( )、binary_search( )、count( )、count_if( )、equal_r

52、ange( )、find( )、find_end( )、find_first( )_of( )、find_if( )、lower_bound( )、upper_bound( )、search( )和search_n( )。其中，equal_range( )、lower_bound( )和upper_bound( ) 3个算法提供了二分查找的形式，它们指出了一个值应该被插入容器中的哪个位置，同时保留容器的排列顺序。 第92页/共301页 ( 2 ) 排 序 和 通 用 排 序 算 法 。 1 4 个 排 序 ( S o r t i n g ) 和 通 用 整 序(Ordering)算法为容器中元

53、素的排序提供了各种策略。分割(Parting)算法把容器分成两组：第一组由满足某个条件的元素组成，第二组则由不满足条件的元素组成。例如，我们可以根据元素是奇是偶，或单词是否以大写字母开头分割一个容器。稳定(Stable)算法维持了相等或同等地满足某个条件的元素的相对关系。例如，给出序列 pshew，honey，Tigger，Pooh 第93页/共301页 根据单词是否以大小写开头的稳定分割将生成下面的序列(其中相等的类别中的原有相对顺序被保留下来)： Tigger，Pooh，pshew，honey 算法的非稳定实例并不能保证这一点(注意排序算法不能被用在list或联合容器上，如set或map)

54、。这14个排序算法是inplace_merge( )、merge( )、nth_element( )、partial_sort( )、partial_sort_copy( )、partition( )、random_shuffle( )、reverse( )、reverse_copy( )、r o t a t e ( ) 、 r o t a t e _ c o p y ( ) 、 s o r t ( ) 、 s t a b l e _ s o r t ( ) 和stable_partition( )。第94页/共301页 (3) 删除和替换算法。15个删除和替换算法为去掉一个或一组元素提供了各

55、种策略。unique( )用于去掉相邻的相等元素；iter_swap( )交换由一对iterator指向的元素的值，但它不交换iterator本身。这15个算法是copy( )、copy_backwards( )、iter_swap( )、remove( )、remove_copy( )、remove_if( )、remove_copy_if( )、replace( )、replace_copy( )、replace_if( )、replace_copy_if( )、swap( )、swap_range( )、unique( )和unique_copy( )。第95页/共301页 (4) 排列

56、组合算法。由三个字符a，b，c组成的序列有六种可能的排列：abc、acb、bac、bca、cab和cba。而且，这些排列根据less_than小于操作符做一个排序。即abc是第一排列，因为每一个元素都小于它后面的元素。acb是下一个排列，因为a是最小的元素，它被固定了。类似地以b开头的排列要小于所有以c开头的排列。对于排列bac和bca，bac小于bca，因为ac小于ca。对于排列bca，我们可以说它的上一个排列是bac，下一个排列是cab。abc没有上一个排列，而cba没有下一个排列。 排列组合算法包括next_permutation( )和prev_mutation( )。 第96页/共3

57、01页 (5) 算术算法。accunulate( )、partial_sum( )、inner_product( )和adjacent_difference( ) 4个算法用于提供对容器的算术操作，为了使用它们，必须包含头文件。 (6) 生成和异变算法。6个生成和异变算法用一组值填充一个新序列 或 替 换 现 有 的 序 列 。 它 们 是 f i l l ( ) 、 f i l l _ n ( ) 、 f o r _ e a c h ( ) 、generate( )、generate_n( )和transform( )。 (7) 关系算法。7个关系算法为比较两个容器提供了各种策略(min(

58、)和max( )只是比较两个元素)。lexicographical_compare( )提供了一个字典排序操作。 第97页/共301页 (8) 集合算法。4个集合(Set)算法提供了对于任何容器类型的通用集合操作。并(Union)算法创建一个包含两个容器中所有元素的有序序列。交(Intersection)算法创建了一个包含“在两个容器中都出现的元素”的有序序列。差(Difference)算法创建了“在一个容器中存在而在第二个容器中不存在的元素”的有序序列。对称差(Symmetric Difference)算法创建了一个“在两个容器之一中存在，但不同时出现在两个容器中的元素”的有序序 列 。 这

59、 4 个 集 合 算 法 是 s e t _ u n i o n ( ) 、 s e t _ i n t e r s e c t i o n ( ) 、set_difference( )和set_symmetric_difference( )。第98页/共301页 (9) 堆算法。堆是以“数组来表示二叉树”的一种形式。STL提供了最大堆(Max-Heap)表示，它里面的每个节点的键值大于等于其子节点的键值。堆算法包括make_heap( )、pop_heap( )、push_heap( )和sort_heap( )。第99页/共301页 6.5.2 算法的使用 下面我们看一下STL算法的强大威

60、力。考虑如下的程序设计任务：我们想写一本儿童书，希望知道适用于这本书的词汇层次。我们的想法是先阅读一定数量的儿童书籍，把其中的文本存储在string vector中，然后我们要做的是： (1) 拷贝每个vector； (2) 把5个vector合并成一个大的vector； (3) 以字母顺序排列大的vector； (4) 去掉所有重复的单词；第100页/共301页 (5) 再按单词的长度排序； (6) 计数超过6个字符的词的个数(长度是一个测量复杂度的依据，至少词汇是这样)； (7) 去掉任何没有语义的中性词(如and、if、or、but等)； (8) 打印vector。 这看起来像是一个比较大的工作，但是使用STL算法，我们的工作会变得相当简单。我们的参数的实参是一个string v