C--第十一章课件.ppt

1、C-第十一章课件11.1 标准模板库简介标准模板库简介 11.3 顺序容器顺序容器 11.2 迭代子类迭代子类 11.5 容器适配器容器适配器 11.7 VC+中的中的STL 11.6 泛型算法与函数对象泛型算法与函数对象 11.4 关联容器关联容器 第十一章第十一章 标准模板库（标准模板库（STL）11.1 标准模板库简介标准模板库简介容器类是管理序列的类，是容纳一组对象或对象集的类。通过容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返

2、回迭代子来删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。指定元素在序列中的位置。STL提供了一个标准化的模板化的对象容器库，包含多种数提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法据结构及其算法:迭代子是面向对象版本的指针迭代子是面向对象版本的指针，它提供了访问容器或序列中每，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。个对象的方法。这样就可以把算法用于容器所管理的序列。泛型算法不依赖于具体的容器，通用的算法更易于扩充。泛泛型算法不依赖于具体的容器，通用的算法更易于扩充。泛型算法中采用函数对象（型算法中采用函数对

3、象（function object）引入不同情况下）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使开销，使STL效率更高。效率更高。11.1 标准模板库简介标准模板库简介容器分为三大类：容器分为三大类：标准库容器类标准库容器类说明说明顺序容器顺序容器vector（参量）（参量）deque（双端队列）（双端队列）list（列表）（列表）从后面快速插入与删除，直接访问任何元素从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与

4、删除，双链表从任何地方快速插入与删除，双链表关联容器关联容器set（集合）（集合）multiset（多重集合）（多重集合）map（映射）（映射）multimap（多重映射（多重映射）快速查找，不允许重复值快速查找，不允许重复值快速查找，允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对一映射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器容器适配器stack（栈）（栈）queue（队列）（队列）priority_queue（优先级队列）（优先级队列）后进先出（后进先出（LIFO）先进先出

5、（先进先出（FIFO）最高优先级元素总是第一个出列最高优先级元素总是第一个出列表表11.111.1 标准模板库简介标准模板库简介顺序容器和关联容器称为第一类容器（顺序容器和关联容器称为第一类容器（first-class container）。另外有四种容器称为近容器（）。另外有四种容器称为近容器（near container）：）：C语言风格数组、字符串语言风格数组、字符串string、操作、操作1/0标志标志值的值的bitset和进行高速数学矢量运算的和进行高速数学矢量运算的valarray。它们虽然提供与第一类容器类似的功能，但没有全部功能它们虽然提供与第一类容器类似的功能，但没有全部功能

6、。STL也使容器提供类似的接口。许多也使容器提供类似的接口。许多基本操作是所有容器都适基本操作是所有容器都适用的用的，而有些操作则适用于类似容器的子集。这样就可以用新，而有些操作则适用于类似容器的子集。这样就可以用新的类来扩展的类来扩展STL。这些函数和运算符可通称为容器的接口。这些函数和运算符可通称为容器的接口。表表11.2 所有标准库容器共有的函数所有标准库容器共有的函数表表11.3 只在第一类中的函数只在第一类中的函数表表11.4 标准容器库的头文件标准容器库的头文件11.1 标准模板库简介标准模板库简介在有关数组、链表和二叉树等线性表和非线性表的讨论中，在有关数组、链表和二叉树等线性表

7、和非线性表的讨论中，若要访问其中一个元素（结点），访问方法最终要归于内存地若要访问其中一个元素（结点），访问方法最终要归于内存地址（指针）的获得，可以抽象为址（指针）的获得，可以抽象为面向对象版本的指针面向对象版本的指针迭代子迭代子（iterator）。）。迭代子与指针有许多相同处，但迭代子与指针有许多相同处，但迭代子保存所操作的特定容迭代子保存所操作的特定容器需要的状态信息器需要的状态信息，从而实现与每种容器类型相适应的迭代子。从而实现与每种容器类型相适应的迭代子。有些迭代子操作在所有容器中是一致的，如有些迭代子操作在所有容器中是一致的，如+运算符总是返运算符总是返回容器下一个元素的迭代子，

8、间接引用符回容器下一个元素的迭代子，间接引用符*，总是表示迭代子指，总是表示迭代子指向的容器元素。向的容器元素。迭代子用来将迭代子用来将STL的各部分结合在一起。从本质上说，的各部分结合在一起。从本质上说，STL提供的提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。些模板实例化。迭代子可以包括指针，但又不仅是一个指针。迭代子可以包括指针，但又不仅是一个指针。11.1 标准模板库简介标准模板库简介STL最大的优点是提供能在各种容器中通用的算法，例如最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排

9、序等等。插入、删除、查找、排序等等。STL提供提供70种左右的标准算法。算法只是间接通过迭代子种左右的标准算法。算法只是间接通过迭代子操作容器元素。操作容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（器，所以称为泛型算法（generic algorithm）。）。算法分为：算法分为：修改容器的算法，即变化序列算法（修改容器的算法，即变化序列算法（mutating-sequence algorithm），如），如copy()、remove()、replace()、swap()等。等。不修改容器的算法，即非变化序列

10、算法（不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如），如count()、find()等。等。数字型算法。数字型算法。11.2 迭代子类迭代子类标准库定义迭代子的层次结标准库定义迭代子的层次结构，按这个层次，从上到下，功构，按这个层次，从上到下，功能越来越强。但不是继承！能越来越强。但不是继承！inputoutputforwardbidirectionalrandom access图图11.1 迭代子层次迭代子层次 C+标准库中标准库中有五种预定义迭代有五种预定义迭代子，其功能最强最子，其功能最强最灵活的是随机访问灵活的是随机访问迭代子

11、。迭代子。表表11.5 迭代子类别迭代子类别表表11.6 STL容器支持容器支持的迭代子类别的迭代子类别表表11.7 各种迭代子可各种迭代子可执行的操作执行的操作只有第一类容器能用只有第一类容器能用迭代子遍历。迭代子遍历。结合结合find()算法讨论迭代子与泛型算法的关系。算法讨论迭代子与泛型算法的关系。find()定义如下：定义如下：templateInputIterator find(InputIterator first,InputIterator last,count T value)for(;first!=last;+first)if(value=*first)return firs

12、t;return last可见，泛型算法不直接访问容器的元素，与容器无关。元素的可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都全部访问和遍历都通过迭代子实现通过迭代子实现。并不需要预知容器类型。并不需要预知容器类型。11.2 迭代子类迭代子类【例【例11.1】寻找数组元素。寻找数组元素。【例【例11.2】寻找寻找vector容器元素。容器元素。11.2 迭代子类迭代子类专用迭代子专用迭代子：反转型迭代子（反转型迭代子（reverse iterator）把一切都颠倒过来。把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上正向遍历一个第一类容器时，如果用

13、了反转迭代子，实际上实现的是反向遍历。第一类容器支持两对操作：实现的是反向遍历。第一类容器支持两对操作：begin()和和end()，分别返回指向容器首元素和容器的末元素的后继的迭分别返回指向容器首元素和容器的末元素的后继的迭代子；而代子；而rbegin()和和rend()支持反转型迭代子，分别返回指向支持反转型迭代子，分别返回指向容器末元素和容器的首元素的前导的迭代子。容器末元素和容器的首元素的前导的迭代子。vector veco;vector:reverse_iterator r_iter;for(r_iter=veco.rbegin();/将将r_iter指向到末元素指向到末元素 r_i

14、ter!=veco.rend();/不等于首元素的前导不等于首元素的前导 r_iter+)/实际是上是递减实际是上是递减如果要把升序的序列改为降序的序列，只要使用反转迭代子如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。就可以了。反转迭代子定义为随机迭代子。11.2 迭代子类迭代子类插入型迭代子（插入型迭代子（insertion iterator）：）：可以用输出迭代可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子：入迭代子：back_insert_iterator是输出

15、迭代子，用来将产生的元是输出迭代子，用来将产生的元素添加到类型为素添加到类型为Type的容器对象的末端。就象在一个字符串的容器对象的末端。就象在一个字符串末尾加一个串（末尾加一个串（strcat()）。）。front_insert_iterator是输出迭代子，用来将产生的元是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。于被控序列前端。insert_iterator也是输出迭代子，它用来将产生的也是输出迭代子，它用来将产生的元素插入到一个由迭代子（第二个参数元素插入到一个由迭代子（第二个参

16、数Iter）指定的元素的前）指定的元素的前面。面。相关的相关的适配器函数适配器函数11.2 迭代子类迭代子类流迭代子流迭代子:输入流迭代子（输入流迭代子（istream_iterator）类支持在）类支持在istream及其派及其派生类（如生类（如ifstream）上的迭代子操作。声明方式为：）上的迭代子操作。声明方式为：istream_iterator迭代子标识符迭代子标识符(istream&);/Type为已定义了输入操作的类型为已定义了输入操作的类型,/实参可以是任意公有派生的实参可以是任意公有派生的istream的子类型的对象的子类型的对象输出流也有对应的输出流也有对应的ostream

17、_iterator类支持，其声明方式为：类支持，其声明方式为：ostream_iterator迭代子标识符迭代子标识符(ostream&)ostream_iterator迭代子标识符迭代子标识符(ostream&,char*)/第二参数为第二参数为C风格字符串风格字符串【例【例11.3】从标准输入读入一个整数集到从标准输入读入一个整数集到vector中。中。流缓冲迭代子。流缓冲迭代子。这是这是STL后添加的一对迭代子，用来后添加的一对迭代子，用来直接从一个流缓冲区（直接从一个流缓冲区（streambuffer）中插入或提取某种）中插入或提取某种类型（通常为类型（通常为char）的元素。）的元素

18、。11.3 顺序容器顺序容器 1.矢量（矢量（vector）类提供顺序表。下标运算符）类提供顺序表。下标运算符 有效。矢量有效。矢量的的内存用尽时内存用尽时，矢量，矢量自动分配更大的连续内存区自动分配更大的连续内存区，将，将原先的元原先的元素复制到新的内存区素复制到新的内存区，并，并释放旧的内存区释放旧的内存区。内存分配是由分配。内存分配是由分配子（子（allocator）完成。）完成。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持支持随机访问迭代子随机访问迭代子。vector的迭代子通常实现为的迭代子通常实现为vect

19、or元素的指针。所谓选元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。择容器类，实际上很大部分是在选择所支持的迭代子。C+标准模板库提供三种顺序容器：标准模板库提供三种顺序容器：vector，list和和deque。vector类和类和deque类是以数类是以数组为基础的，组为基础的，list类是以双向链表为基础的。类是以双向链表为基础的。11.3 顺序容器顺序容器使用使用矢矢量容器的声明如下：量容器的声明如下：#includevector vi;/定义存放整形序列的向量容器对象定义存放整形序列的向量容器对象vi，长度为，长度为0的空的空vectorvector vf;/存放

20、实型序列的向量容器存放实型序列的向量容器vector vch;/存放字符序列的向量容器存放字符序列的向量容器vectorvstr;/存放字符串序列的向量容器存放字符串序列的向量容器矢量容器有多种构造函数，包括构造一个有矢量容器有多种构造函数，包括构造一个有n个元素的矢量。个元素的矢量。还可以为每个元素用同一个对象来赋初值。还包括拷贝构造还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。这些构造函数还可以显式给出分配子素的构造函数。这些构造函数还可以显式给出分配子(alloca

21、tor)对象。对象。11.3 顺序容器顺序容器2.列表（列表（list）是由双向链表（）是由双向链表（doubly linked list）组成的。）组成的。它有两个指针域，支持的迭代子类型为双向迭代子。与双链表它有两个指针域，支持的迭代子类型为双向迭代子。与双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文类模板相似，但通用性更好，使用更方便。列表的定义在头文件件中。中。3.双端队列（双端队列（deque）（）（double-ended queue）类。双端队）类。双端队列允许在队列的两端进行操作。以顺序表为基础，支持随机访列允许在队列的两端进行操作。以顺序表为基础，支持随机访问迭

22、代子。问迭代子。双端队列放松了访问的限制，对象既可从队首进队，也可以从双端队列放松了访问的限制，对象既可从队首进队，也可以从队尾进队，同样也可从任一端出队。支持下标操作符队尾进队，同样也可从任一端出队。支持下标操作符“”。增加存储空间可在内存块中对增加存储空间可在内存块中对deque两端分别进行分配。新两端分别进行分配。新分配的存储空间保存为指向这些块的指针数组，可以利用不连分配的存储空间保存为指向这些块的指针数组，可以利用不连续内存空间。因此它的迭代子比续内存空间。因此它的迭代子比vector的迭代子更加智能化。的迭代子更加智能化。为双端队列分配的存储块删除双端队列时才释放。为双端队列分配的

23、存储块删除双端队列时才释放。使用双端队列，必须包含头文件使用双端队列，必须包含头文件。11.4 关联容器关联容器关联容器（关联容器（associative container）能通过关键字（）能通过关键字（search key）直接访问）直接访问(存储和读取元素存储和读取元素)。四个关联容器为：集合。四个关联容器为：集合（set），多重集合（），多重集合（multiset），映射（），映射（map）和多重映射）和多重映射（multimap）。）。集合和多重集合类提供了控制数值集合的操作，其中数集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。值是关

24、键字，即不必另有一组值与每个关键字相关联。多重集合允许重复的关键字（多重集合允许重复的关键字（key），而集合不允许。），而集合不允许。元素的顺序由比较器函数对象（元素的顺序由比较器函数对象（comparator function object）确定。如对整型）确定。如对整型multiset，只要用比较器函数对象，只要用比较器函数对象less排序关键字，元素即可按升序排列。排序关键字，元素即可按升序排列。multiset和和set通常实现为通常实现为红黑二叉排序树。红黑二叉排序树。红黑二叉排红黑二叉排序树是实现平衡二叉排序树的方法之一。序树是实现平衡二叉排序树的方法之一。【例【例11.4】整型

25、多重集合关联容器类整型多重集合关联容器类11.4 关联容器关联容器映射和多重映射类提供了操作与关键字相关联的映射值映射和多重映射类提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。映射只允许存放与映射值一一对应的单一关键字。多重映射和映射关联容器类用于快速存储和读取关键字与多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字相关值（关键字/数值对，数值对，key/v

26、alue pair）。如果保存）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件能重复，使用多重映射更为合适。使用时要用头文件。11.5 容器适配器容器适配器STL提供了三个容器适配器（提供了三个容器适配器（container adapter）：栈，队）：栈，队列和优先级队。所谓适配器并不独立，它依附在一个顺序容列和优先级队。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的

27、字符型堆栈，声明如下：器上。如要声明一个用矢量实现的字符型堆栈，声明如下：stackvector sk;优先级队列（优先级队列（priority_queue）适配器实现优先级队列。元素）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。常用矢量为基础容器。缺省时级队列中取出。常用矢量为基础容器。缺省时priority_queue用用vector为基础数据结构。为基础数据结构。然后它可以象顺序容器一样使用。但是它没有自己的构造和析然后它可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其

28、实现类（如构函数，它使用其实现类（如vector）的构造和析构函数。队）的构造和析构函数。队列（列（queue）缺省用）缺省用deque为基础，栈（为基础，栈（stack）可用）可用vector或或deque为基础。为基础。【例【例11.5】优先级队列类演示优先级队列类演示11.6 泛型算法与函数对象泛型算法与函数对象算法表现为一系列的函数模板。它们完整定义在算法表现为一系列的函数模板。它们完整定义在STL头文头文件中。使用者可以用很多方式来件中。使用者可以用很多方式来特化每一个模板函数特化每一个模板函数，大大提，大大提高了它作为通用型程序组件的适用性。这些函数模板使用迭代高了它作为通用型程序

29、组件的适用性。这些函数模板使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操子作为它的参数和返回值，以此在容器（序列）上进行各种操作。本节进一步讨论作。本节进一步讨论算法的通用性算法的通用性。11.6.1 函数对象函数对象 11.6.2 泛型算法泛型算法 11.6.1 函数对象函数对象在在C+中，为了使程序的安全性更好，采用中，为了使程序的安全性更好，采用“引用引用”来代替来代替指针作为函数的参数或返回值。在指针作为函数的参数或返回值。在C+的泛型算法中类似地的泛型算法中类似地采用了采用了“函数对象函数对象”（function object）来代替函数指针。）来代替函数指针。函数对

30、象是一个类，它函数对象是一个类，它重载了函数调用操作符重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。操作。典型情况下，函数对象被作为实参传递给泛型算法。和和“引用引用”一样，一样，“函数对象函数对象”独立使用比较少。函数对象独立使用比较少。函数对象亦称拟函数对象（亦称拟函数对象（function_like object）和函子（）和函子（functor）为了消除算法的类型依赖性，可采用函数指针为参数，类似于为了消除算法的类型依赖性，可采用函数指针为参数，类似于6.8节附

31、录中库函数快速排序节附录中库函数快速排序qsort()的处理方法，这种方法更的处理方法，这种方法更适合函数模板。适合函数模板。11.6.1 函数对象函数对象【例【例11.6】求和函数对象的定义和测试。求和函数对象的定义和测试。以函数对象作为以函数对象作为“数值比较算法数值比较算法”的求序列中最小值的函数模板：的求序列中最小值的函数模板：templateconst Type&min(const Type*p,int size,Comp comp)int minIndex=0;/最小元素下标初值为最小元素下标初值为0,即设即设0号元素最小号元素最小 for(int i=1;isize;i+)if(

32、comp(pi,pminIndex)minIndex=i;return pminIndex;例中例中Comp为比较函数对象类，对不同的数据类型，可以定义不为比较函数对象类，对不同的数据类型，可以定义不同的函数对象。重载的同的函数对象。重载的()，参数表可有任意数目的参数。，参数表可有任意数目的参数。11.6.1 函数对象函数对象函数对象与函数指针相比较有函数对象与函数指针相比较有三个优点三个优点：第一，函数：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额这样速度更快；第二，函数对象可

33、以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检就是一个额外数据；第三，编译时对函数对象作类型检查。查。函数对象有多种来源函数对象有多种来源1.标准库预定义的一组算术，关系和逻辑函数对象；标准库预定义的一组算术，关系和逻辑函数对象；2.预定义的一组函数适配器，允许对预定义的函数对象进预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展；行特殊化或扩展；3.自定义函数对象。自定义函

34、数对象。11.6.1 函数对象函数对象 预定义函数对象分算术、关系和逻辑操作。每个对象都是一个预定义函数对象分算术、关系和逻辑操作。每个对象都是一个类模板，以操作数类型为模板参数。使用时要包含头文件：类模板，以操作数类型为模板参数。使用时要包含头文件：#include以加法为例，讨论名为以加法为例，讨论名为plus的类模板，对整数的用法实例如下：的类模板，对整数的用法实例如下：plusintAdd;int ival1=30,ival2=15;int sum=intAdd(ival1,ival2);/等效于等效于:sum=ival1+inval2但是函数对象主要是作为泛型算法的但是函数对象主要是

35、作为泛型算法的实参实参使用，通常用来改变使用，通常用来改变缺省的操作，比如在【例缺省的操作，比如在【例11.3】中有：】中有：sort(vec.begin(),vec.end(),greater();这就是把整数的这就是把整数的大于关系函数对象大于关系函数对象作为实参，得降序排列。如作为实参，得降序排列。如果是字符串，则有：果是字符串，则有：sort(svec.begin(),svec.end(),greater();只要改一下参数就又可用于字符串的排序。只要改一下参数就又可用于字符串的排序。11.6.1 函数对象函数对象greater的的 比较算法在内置类型比较算法在内置类型int，字符串类

36、，字符串类string中中定义。譬如可以自定义整数类定义。譬如可以自定义整数类Int，其中重载了，其中重载了“”运算符：运算符：class Intpublic:Int(int ival=0):_val(ival)int operator-()return-_val;/负数符号重载负数符号重载 int operator%(int ival)return _val%ival;/求余符号重载求余符号重载 bool operator(int ival)return _valival;/小于符号重载小于符号重载 bool operator!()return _val=0;/逻辑非符号重载逻辑非符号重载p

37、rivate:int _val;每个类对象都可以作为有名或无名对象传递给函数，同时也把每个类对象都可以作为有名或无名对象传递给函数，同时也把所需重载的算法传递过去了。所需重载的算法传递过去了。11.6.1 函数对象函数对象下面给出各种预定义的函数对象及其使用方法：参数和返回值。下面给出各种预定义的函数对象及其使用方法：参数和返回值。为方便说明，定义以下变量（对象）：为方便说明，定义以下变量（对象）：vectorsvec;string sval1,sval2,sres;complex cval1,cval2,cres;int ival1,ival2,ires;Int Ival1,Ival2,Ir

38、es;double dval1,dval2,dres;同时为了用实例来说明使用方法，再定义一个可用单参数函数对象同时为了用实例来说明使用方法，再定义一个可用单参数函数对象(一元一元函数对象函数对象)的函数模板和一个可用双参数函数对象（二元函数对象）的函的函数模板和一个可用双参数函数对象（二元函数对象）的函数模板：数模板：templateType UnaryFunc(FuncObject fob,const Type&val)return fob(val);templateType BinaryFunc(FuncObjectfob,const Type&val1,const Type&val2)

39、return fob(val1,val2);11.6.1 函数对象函数对象算术函数对象：算术函数对象：加法：加法：plusplusintPlus;ires=intPlus(ival1,ival2);dres=BinaryFunc(plus(),dval1,dval2);sres=BinaryFunc(plus(),sval1,sval2);减法：减法：minus/同加法同加法乘法：乘法：multiplies/不能用串，可用于复数和浮点数等不能用串，可用于复数和浮点数等multiplies intMulti;ires=intMulti(ival1,ival2);cres=BinaryFunc(m

40、ultiplies(),cal1,cal2);dres=BinaryFunc(multiplies(),dval1,dval2);除法：除法：divides/同乘法同乘法求余：求余：modulus/不能用于复数不能用于复数,浮点数浮点数,只能用于整数只能用于整数modulusIntModulus;/Int 自定义类型自定义类型Ires=IntModulus(Ival1,Ival2);ires=BinaryFunc(modulus(),ival1,ival2);取反：取反：negate/同取余同取余,但为单参数但为单参数ires=UnaryFunc(negate(),Ival1);11.6.1

41、函数对象函数对象逻辑函数对象逻辑函数对象，这里，这里Type必须支持逻辑运算，有两个参数。必须支持逻辑运算，有两个参数。逻辑与：逻辑与：logical_and/对应对应&逻辑或：逻辑或：logical_or/对应对应|逻辑非：逻辑非：logical_not/对应对应!关系函数对象关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二，它们的返回值为布尔量，两个参数，第一参数和第二参数相比：参数相比：等于：等于：equal_to不等于：不等于：not_equal_to大于：大于：great大于等于：大于等于：great_equal小于：小于：less小于等于：小于等于：less_equal

42、返回布尔值的函数对象称为返回布尔值的函数对象称为谓词谓词（predicate），默认的二进制），默认的二进制谓词谓词是小于比较操作符是小于比较操作符“”，所以默认的排序方式都是升序排列，它，所以默认的排序方式都是升序排列，它采用小于比较形式。采用小于比较形式。11.6.1 函数对象函数对象和容器类一样，函数对象也可以由函数适配器来特殊化或扩和容器类一样，函数对象也可以由函数适配器来特殊化或扩展一元（单参数）或二元（双参数）函数对象：展一元（单参数）或二元（双参数）函数对象：1绑定器（绑定器（binder）：把二元函数对象中的一个参数固定：把二元函数对象中的一个参数固定（绑定），使之转为一元函数

43、，（绑定），使之转为一元函数，C+标准库提供标准库提供两种预定义两种预定义的的binder适配器适配器：bind1st和和bind2nd，分别绑定了第一或，分别绑定了第一或第二个参数。第二个参数。2取反器（取反器（negator）：把函数对象的值翻转的适配器，：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。如原来为小于，用了它后就变成了大于。C+标准库也提供标准库也提供了了两种两种negator适配器适配器：not1和和not2。not1用于一元预定用于一元预定义函数对象；义函数对象；not2用于二元预定义函数对象。用于二元预定义函数对象。11.6.2 泛型算法泛型算法在在C

44、+标准库中给出了标准库中给出了70余种算法，泛型算法函数余种算法，泛型算法函数名都加有后缀，这些后缀的意思如下：名都加有后缀，这些后缀的意思如下：_if表示函数采用的操作是在元素上，而不是表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如对元素的值本身进行操作。如find_if算法表示查找一些算法表示查找一些值满足函数指定条件的元素，而值满足函数指定条件的元素，而find查找特定的值。查找特定的值。_copy表示算法不仅操作元素的值，而且还把修表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。改的值复制到一个目标范围中。reverser算法颠倒范围算法颠倒范围中元素的

45、排列顺序，而中元素的排列顺序，而reverse_copy算法同时把结果复算法同时把结果复制到目标范围中。制到目标范围中。其它的后缀从英文意思上立即可以认出其意义，对其它的后缀从英文意思上立即可以认出其意义，对照附录照附录C*在泛型算法中有一种习惯用语，不说满足某条件的元素，在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足指定二进制而讲满足指定二进制谓词谓词规则的元素，因为谓词是返回布规则的元素，因为谓词是返回布尔值的函数对象，满足则返回尔值的函数对象，满足则返回true，即与满足指定条件是，即与满足指定条件是同样意思。同样意思。11.6.2 泛型算法泛型算法其次我们介绍泛型算法的构造

46、与使用方法。所有泛型算法的其次我们介绍泛型算法的构造与使用方法。所有泛型算法的前两个实参是一对前两个实参是一对iterator，通常称为，通常称为first和和last，它们标出，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括要操作的容器或内置数组中的元素范围。元素的范围，包括first，但不包含，但不包含last的左闭合区间。即：的左闭合区间。即：first,last)当当first=last成立，则范围为空。成立，则范围为空。对对iterator的类，则要求在每个算法声明中指出（的类，则要求在每个算法声明中指出（5个基本类个基本类别），所声明的是最低要求。别），所声明的是最低

47、要求。如如find()最低要求为最低要求为InputIterator，可以传递更高级别的迭代子。如：，可以传递更高级别的迭代子。如：ForwardIterator、BidirectonalIterator及及RandomAccessInterator。但不能用。但不能用OutputInterator。11.6.2 泛型算法泛型算法泛型算法分以下几类：泛型算法分以下几类：1查找算法查找算法：有：有13种查找算法用各种策略去判断容器中是否种查找算法用各种策略去判断容器中是否存在一个指定值。存在一个指定值。equal_range()、lower_bound()和和upper_bound()提供对半查

48、找形式。提供对半查找形式。2排序和通用整序算法排序和通用整序算法：共有：共有14种排序（种排序（sorting）和通用整）和通用整序（序（ordering）算法，为容器中元素的排序提供各种处理方法。）算法，为容器中元素的排序提供各种处理方法。所谓整序，是按一定规律分类，如分割（所谓整序，是按一定规律分类，如分割（partition）算法把容）算法把容器分为两组，一组由满足某条件的元素组成，另一组由不满足器分为两组，一组由满足某条件的元素组成，另一组由不满足某条件的元素组成。某条件的元素组成。3删除和代替算法删除和代替算法：有：有15种删除和代替算法。种删除和代替算法。4排列组合算法排列组合算法

49、：有：有2种算法。排列组合是指全排列。如：三种算法。排列组合是指全排列。如：三个字符个字符a，b，c组成的序列有组成的序列有6种可能的全排列：种可能的全排列：abc，acb，bac，bca，cab，cba；并且六种全排列按以上顺序排列，认；并且六种全排列按以上顺序排列，认为为abc最小，最小，cba最大，因为最大，因为abc是全顺序（从小到大）而是全顺序（从小到大）而cba是全逆序（从大到小）。是全逆序（从大到小）。11.6.2 泛型算法泛型算法5生成和改变算法生成和改变算法：有：有6种，包含生成（种，包含生成（generate），填充（），填充（fill）等）等等。等。6关系算法关系算法：有

50、：有7种关系算法，为比较两个容器提供了各种策略，包括种关系算法，为比较两个容器提供了各种策略，包括相等（相等（equal()），最大（），最大（max()），最小（），最小（min()）等等。）等等。7集合算法集合算法：4种集合（种集合（set）算法提供了对任何容器类型的通用集合）算法提供了对任何容器类型的通用集合操作。包括并（操作。包括并（union），交（），交（intersection），差（），差（difference）和）和对称差（对称差（symmetric difference）。）。8.堆算法堆算法：有：有4种堆算法。堆是以数组来表示二叉树的一种形式。标准种堆算法。堆是以数组来表