泛型算法

第十二章 泛型算法

12.1 概述

1.范型算法与被应用的容器类型以及被查找的值的类型无关算法的要求如下：

(1) 我们需要某种遍历集合的方式这包括向前移到下一个元素以及识别下一元素是

否是末元素的概念

泛型算法用iterator 抽象来解决这个问题。对容器的遍历iterator 提供了对指针的一

个泛化，它至少支持下列操作符：递增操作符以用来访问下一个元素、解引用操作符用来访问实际的元素、以及等于和不等于操作符用来判定两个iterator 是否相等。

（2）我们需要能够对容器中的元素与被查找元素进行比较

为每个算法提供两个版本：一个使用元素底层类型的等于操作符，另一个使用函数对象或函数指针来实现比较。

12.3 函数对象

1. 函数指针的主要性能缺点是它的间接引用使其不能被内联。

2. 函数指针的替代策略是函数对象。

函数对象是一个类，它重载了函数调用操作符operator()。 该操作符封装了通常应该被实现为一个函数的动作。典型情况下，函数对象被作为实参传递给泛型算法，当然我们也可以定义独

立的函数对象。

3. 函数对象与函数指针相比较，有两个方面的优点:

(1) (内联性能好)如果被重载的调用操作符是inline函数，则编译器能够执行内联编译提供可能的性能好处。

(2) (缓冲中间数据)函数对象可以拥有任意数目的额外数据，用这些数据可以缓冲结果，也可以缓冲有助于当前操作的数据。

4．泛型算法一般支持两种形式来应用操作：使用内置或可能是被重载的操作符和使

用函数指针或函数对象执行操作。

5. 函数对象的三个来源

（1）标准库预定义的一组算术、关系和逻辑函数对象

(2) 一组预定义的函数适配器允许我们对预定义的函数对象甚至于任何函数对象

进行特殊化或者扩展

(3) 自定义的函数对象，或将其应用函数适配器。

12.3.1 预定义函数对象

预定义函数对象被分成算术、关系和逻辑操作，每个对象都是一个类模板其中操作数

的类型被参数化，头文件为

每个类对象都可以作为有名对象，也可以作为无名对象传递给一个函数。

12.3.2 算术函数对象

预定义的算术函数对象支持：加、减、乘、除、求余和取反。调用的操作符是与Type 相

关联的实例。

加法plus

减法minus

乘法multiplies

除法divides

求余modulus

取反negate

12.3.3 关系函数对象

预定义的关系函数对象支持：等于、不等于、大于、大于等于、小于和小于等于。

等于equal_to

不等于not_equal_to

大于greater

大于等于greater_equal

小于less

小于等于less_equal

12.3.4 逻辑函数对象

预定义的逻辑函数对象支持逻辑与、逻辑或、逻辑非。

逻辑与logical_and

逻辑或logical_or

逻辑非 logical_not

12.3.5 函数对象的函数适配器

标准库还提供了一组函数适配器，用来特殊化或者扩展一元和二元函数对象。适配器是

一种特殊的类，它被分成下面两类：

1. 绑定器binder 通过把二元函数对象的一个实参绑定到一个特殊的值上，

将其转换成一元函数对象。

两种预定义的binder 适配器bind1st 和bind2nd

例如：bind2nd( less_equal(), 10 )

2. 取反器negator是一个将函数对象的值翻转的函数适配器。

两个预定义的negator 适配器not1 和not2。not1翻转一元预定义函数对象的真值，而not2 翻转二元谓词函数的真值。