【C++】泛型算法（五）泛型算法的使用与设计

一、使用泛型算法 头文件 #include<algorithm> 常用泛型算法

find() 用于搜索无序集合中是否存在某值; 搜索范围: iterator[first, last); 如果搜索到目标，find() 会返回一个iterator指向该值，否则返回一个interator指向last。

binary_search() 用于有序集合的搜索；（效率比find()高） 如果搜索到目标就返回true，否则返回false。

count() 返回数值相符的元素数目。

search() 比对某个容器内是否存在某个子序列； 例如给定序列{1，3，5，7，2，9}，如果搜寻子序列{5，7，2}，则search()会返回一个literator指向子序列起始处，如果子序列不存在，就返回一个iterator指向序列末尾。

max_element() 取得数列最大元素值； eg. max_element(vec.begin(), vec.end() );

copy() eg. copy(vec.begin(), vec.end(), temp.begin() ); 前两个泛型指针标出复制范围，第三个指向复制行为的目的地（也是个容器）的第一个元素，后续元素会被依次填入； 注意确保目标容器拥有足够的空间以放置每个即将到来的元素。

sort() 对新容器执行排序操作。 eg. sort( temp.begin(), temp.end() );

二、如何设计一个泛型算法 1. Function Object

标准库预先定义好许多的function object，实现了我们原本可能以独立函数加以定义的事务；

function object是某种class的实例对象，对function call运算符重载，可使function object被当做一般函数来使用；

目的：提高效率（运算符成为inline，从而消除“通过函数指针来调用函数”的过程）。

标准库function object： 六个算术运算： plus< type >,minus< type >,negate< type >,multiplies< type >,divides< type >,modules< type > 六个关系运算： less< type >,less_equal< type >,greater< type >,greater_equal< type >,equal_to< type >,not_equal_to< type> 三个逻辑运算：

分别对应：&&、||、！：

logical_and< type >,logical_or< type >,logical_not< type > 头文件： #include <functional>; 举例一： //sort()默认less-than即升序排列 //传入greater-than这个function object即降序排列 sort(vec.begin(), vec.end(), greater<int>()); //binary_search()默认less-than即升序排列 //为正确搜索vector，可调整排序如下： binary_search(vec.begin(), vec.end(), elem, greater<int>() ); 举例二： //实现fib数列每个元素和自身相加、自身相乘、被加到对应的Pell数列 transform( fib.begin(), fib.end(), //(1)元素范围 pell.begin(), //(2)应用位置 fib_plus_pell.begin(), //(3)存放结果的位置 plus<int>()); //(4)所应用的转换操作 2. Function Object Adapter 适配器：对function object进行修改操作；binder adapter将function object的参数绑定为某指定值（二元转化为一元）。 标准库binder adapter： bind1st 将指定值绑定第一个参数；bind2nd 将指定值绑定第二个参数。 举例 vector<int> filter(const vector<int> &vec, int val, less<int> &it) { vector<int> nvec; vector<int>::const_iterator iter = vec.begin(); //val绑定于less<int>的第二个参数上 //于是每个less<int>都会与val比较 while ( (iter = find_if(iter, vec.end(), bind2nd(it, val))) != vec.end() ) { //每当iter!=vec.end(),iter指向某个小于val的元素 nvec.push_back(*iter); iter++; } return nvec; } 泛型化比较 //non-template版本 vector<int> sub_vec( const vector<int> &vec, int val ) { vector<int> local_vec( vec ); sort ( local_vec.begin(), local_vec.end() ); vector<int>::iterator iter = find_if ( local_vec.begin(), local_vec.end(), bind2nd( greater<int>(), val )); local_vec.erase ( iter, local_vec.end() ); return local_vec; } //改为template //更加泛型化 template <typename InputIterator, typename OutputIterator, typename ElemType, typename Comp> OutputIterator sub_vec ( InputIterator first, InputIterator last, OutputIterator at, const ElemType &val, typename Comp) { while ( (first = find_if(first, last, bind2nd(pred, val) )) != last) //not1(bind2nd(pred, val))可以一元取反,not2二元取反 { //观察进行情况 cout << "found value: " << *first << endl; *at = *first++; } return at; } 总结

将最初的函数转化为泛型函数的呈现效果： 转化后的函数和元素类型无关、和比较操作无关、和容器类型无关，即可从消除函数和元素类型、容器类型、比较操作之间的关联入手，传入指针、进行元素类型和操作参数化等。