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

一、使用泛型算法

头文件

#include 
1

常用泛型算法

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

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

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

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

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

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

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

二、如何设计一个泛型算法

1. Function Object

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

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

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

标准库function object：

1. 六个算术运算：

• plus< type >,
• minus< type >,
• negate< type >,
• multiplies< type >,
• divides< type >,
• modules< type >

2. 六个关系运算：

• less< type >,
• less_equal< type >,
• greater< type >,
• greater_equal< type >,
• equal_to< type >,
• not_equal_to< type>

3. 三个逻辑运算：

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

• logical_and< type >,
• logical_or< type >,
• logical_not< type >

头文件：

#include ;
1

举例一：

//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>() );
1
2
3
4
5
6

举例二：

//实现fib数列每个元素和自身相加、自身相乘、被加到对应的Pell数列
transform(
	fib.begin(), fib.end(), //(1)元素范围
	pell.begin(),           //(2)应用位置
	fib_plus_pell.begin(),  //(3)存放结果的位置
	plus<int>());			//(4)所应用的转换操作
1
2
3
4
5
6

2. Function Object Adapter

• 适配器：对function object进行修改操作；
• binder adapter将function object的参数绑定为某指定值（二元转化为一元）。

标准库binder adapter：

1. bind1st 将指定值绑定第一个参数；
2. 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的第二个参数上
    //于是每个less都会与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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

泛型化比较

//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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结

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