这里,算法表现为一系列的函数模板。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数,大大提高了它作为通用型程序组件的适用性。
这些函数模板使用迭代子作为它的参数和返回值,以此在容器(序列)上进行各种操作。
本节进一步讨论算法的通用性。
函数对象
◆ 1、
函数对象的基本概念
:每个
泛型算法
(Generic Algorithm)的实现都于容器类型,它消除了算法对类型的依赖性。当一个算法应用于一个具体的容器时,它们之间如何正确建立联系?
在STL的泛型算法中采用“
函数对象
”(Function Object)来解决该问题。
函数对象是一个类对象,通常它仅有一个成员函数,该函数重载了
函数调用操作符
(operator())。该操作符封装了应该被实现为一个函数的操作。典型情况下,函数对象被作为实参传递给泛型算法。
和“引用”一样,“函数对象”很少使用。函数对象亦称拟函数对象(Function_Like Object)和函子(Functor)。
【例11.6】定义一个求和的函数对象,并测试。(
)
注意函数对象Sum能实例化为有限种类型,如:整型、实型、字符型等等,也能用于string类型,因为string重载了operator +。
◆
2、函数对象的应用
:函数对象主要是作为泛型算法的实参使用,通常用来改变默认的操作,如:
sort(vec.begin(),vec.end(),greater<int>());
这里把整数的
大于关系函数对象
作为实参,得降序排列。
如果是字符串,则有:
sort(svec.begin(),svec.end(),greater<string>());
只要改一下参数就又可用于字符串的排序。
函数对象greater<Type>()
中所包含的比较算法实际上在内置类型int,字符串类string中定义。由此可见函数对象并没有新东西,只是一个固定格式,用起来更方便。
◆
3、使用函数对象实现泛型算法
:以函数对象作为“求序列中最小值的函数模板”中的“数值比较算法”中的参数:
template<typename Type,typename Comp>
const Type& min(const Type*p,int size,Comp comp)
{
int minIndex=0;
//最小元素下标初值为0,即设0号元素最小
for(int i=1;i<size;i++)
if(comp(p[i],p[minIndex])) minIndex=i;
return p[minIndex];
}
例中Comp为比较函数对象类模板,对不同的数据类型,可以产生不同的比较函数,以实现泛型算法。
◆
4、函数对象的优点
:函数对象与函数指针相比较有三个优点:第一,函数指针是间接引用,不能作为内联函数,而函数对象可以,这样速度更快;第二,函数对象可以拥有任意数量的额外数据,用这些数据可以用来缓冲当前数据和结果,提高运行质量;第三,编译时对函数对象作类型检查。
◆
5、函数对象来源:
- 标准库预定义的一组算术,关系和逻辑函数对象;
- 预定义的一组函数适配器,允许对预定义的函数对象进行特殊化或扩展;
- 自定义函数对象。
◆
6、预定义函数对象
算术函数对象:
加法:plus<Type>
减法:minus<Type>
乘法:multiplies<Type> //不能用串,可用于复数和浮点数等
除法:divides<Type> //同乘法
求余:modulus<Type> //不能用于复数,浮点数,只能用于整数
取反:negate<Type> //同取余,但为单参数
逻辑函数对象:
这里Type必须支持逻辑运算,有两个参数。
逻辑与:logical_and<Type> //对应&&
逻辑或:logical_or<Type> //对应||
逻辑非:logical_not<Type> //对应!
关系函数对象:
它们的返回值为布尔量,两个参数,第一参数和第二参数相比:
等于:equal_to<Type>
不等于:not_equal_to<Type>
大于:great<Type>
大于等于:great_equal<Type>
小于:less<Type>
小于等于:less_equal<Type>
返回布尔值的函数对象称为
谓词
(predicate),默认的二进制谓词是小于比较操作符“<”,所以默认的排序方式都是升序排列,它采用小于比较形式。
泛型算法
◆
1、泛型算法分类为:
- 修改容器的算法,即变化序列算法(mutating-sequence algorithm),如copy()、remove()、replace()、swap()等;
- 不修改容器的算法,即非变化序列算法(non-mutating-sequence algorithm),如count()、find()等;以及数字型算法。
◆
2、泛型算法函数名后缀:
_if 表示函数采用的操作是在元素上,而不是对元素的值本身进行操作。如“find_if”算法表示查找一些值满足函数指定条件的元素;而“find”算法则查找特定的值。
_copy表示算法不仅操作元素的值,而且还把修改的值复制到一个目标范围中。例如"reverser"算法颠倒范围中元素的排列顺序,而"reverse_copy"算法同时把结果复制到目标范围中。
其它的后缀从英文意思上立即可以认出其意义。
◆
3、泛型算法的构造与使用方法:
所有泛型算法的前两个实参是一对iterator,通常称为first和last,它们标出要操作的容器或内置数组中的元素范围。元素的范围,包括first,但不包含last的左闭合区间。即:[first,last)
当first==last成立,则范围为空。
对iterator的属性,则要求在每个算法声明中指出,所声明的是最低要求。如find()算法的最低要求为:InputIterator;还可以传递更高级别的迭代子。如:ForwardIterator、BidirectonalIterator及RandomAccessInterator。但不能用OutputInterator。
◆
4、泛型算法分类: