算法

cpp 评论

算法

算法基础

算法概述

算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。

<algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。

<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。

<functional>中则定义了一些模板类，用以声明函数对象。

STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。

#include <algorithm>

#include <numeric>

#include <functional>

STL中算法分类

  • 操作对象

    • 直接改变容器的内容
    • 将原容器的内容复制一份,修改其副本,然后传回该副本

  • 功能:

    • 非可变序列算法 指不直接修改其所操作的容器内容的算法

      • 计数算法 count、count_if
      • 搜索算法 search、find、find_if、find_first_of、…
      • 比较算法 equal、mismatch、lexicographical_compare

    • 可变序列算法 指可以修改它们所操作的容器内容的算法

      • 删除算法 remove、remove_if、remove_copy、…
      • 修改算法 for_each、transform
      • 排序算法 sort、stable_sort、partial_sort、

    • 排序算法 包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作

    • 数值算法 对容器内容进行数值计算

常用算法汇总

常用的查找算法：

adjacent_find()（ adjacent 是邻近的意思）,binary_search(),count(),

count_if(),equal_range(),find(),find_if()。

常用的排序算法：

merge(),sort(),random_shuffle()（shuffle是洗牌的意思） ,reverse()。

常用的拷贝和替换算法：

copy(), replace(),

replace_if(),swap()

常用的算术和生成算法：

accumulate()（ accumulate 是求和的意思）,fill(),。

常用的集合算法：

set_union(),set_intersection(),

set_difference()。

常用的遍历算法：

for_each(), transform()（ transform 是变换的意思）

算法中函数对象和谓词

函数对象和谓词定义

函数对象：

重载函数调用操作符的类，其对象常称为函数对象（function object），即它们是行为类似函数的对象。一个类对象，表现出一个函数的特征，就是通过“对象名+(参数列表)”的方式使用一个类对象，如果没有上下文，完全可以把它看作一个函数对待。

这是通过重载类的operator()来实现的。

“在标准库中，函数对象被广泛地使用以获得弹性”，标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为；

谓词：

一元函数对象：函数参数1个；

二元函数对象：函数参数2个；

一元谓词 函数参数1个，函数返回值是bool类型，可以作为一个判断式

​ 谓词可以使一个仿函数，也可以是一个回调函数。

二元谓词 函数参数2个，函数返回值是bool类型

一元谓词函数举例如下

1，判断给出的string对象的长度是否小于6

1
2
3
4
5
6
7
bool GT6(const string &s)

{

return s.size() >= 6;

}

2,判断给出的int是否在3到8之间

1
2
3
4
5
6
7
bool Compare( int i )

{

return ( i >= 3 && i <= 8 );

}

二元谓词举例如下

1，比较两个string对象，返回一个bool值，指出第一个string是否比第二个短

1
2
3
4
5
6
7
bool isShorter(const string &s1, const string &s2)

{

return s1.size() < s2.size();

}

一元函数对象案例

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
31
32
33
34
35
36
37
38
39
40
41
42
43
//1普通类 重载 函数调用操作符
template <typename T>
void FuncShowElemt(T &t)  //普通函数 不能像 仿函数那样记录状态
{
	cout << t << " ";
};

void showChar(char &t)
{
	cout << t << " ";
}

//函数模板 重载 函数调用操作符
template <typename T>
class ShowElemt
{
public:
	ShowElemt()
	{
		n = 0;
	}
	void operator()(T &t)
	{
		n++;
		cout << t << " ";
	}
	void printCount()
	{
		cout << n << endl;
	}
public:
	int n;
};

//1 函数对象 基本使用
void main11()
{
	int a = 100;
	FuncShowElemt<int>(a); //普通的函数调用

	ShowElemt<int> showElemt; //函数对象 
	showElemt(a); //函数对象调用 
}

一元谓词案例

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
31
32
33
34
35
//1元谓词 例子
template <typename T>
class Isdiv
{
public:
	Isdiv(const T &divisor) //
	{
		this->divisor = divisor;
	}
	bool operator()(T &t)
	{
		return (t%divisor == 0);
	}
protected:
private:
	T divisor;
};

void main13()
{
	vector<int> v2;
	for (int i=10; i<33; i++)
	{
		v2.push_back(i);
	}
	vector<int>::iterator it;
	int a = 4;
	Isdiv<int> mydiv(a);
	// _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)   //返回的是迭代器
	it = find_if(v2.begin(), v2.end(), Isdiv<int>(4));
	if (it != v2.end())
	{
		cout << "第一个被4整除的数是：" << *it << endl;
	}
}

二元函数对象案例

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
template <typename T>
struct SumAdd
{
	T operator()(T &t1, T &t2)
	{
		return t1 + t2;
	}
};

template <typename T>
void printE(T &t)
{
	for (vector<int>::iterator it = t.begin(); it!=t.end(); it++ )
	{
		cout << *it << " ";
	}
}

void printVector(vector<int> &v)
{
	for (vector<int>::iterator it = v.begin(); it!=v.end(); it++ )
	{
		cout << *it << " ";
	}
}

void  main14()
{
	vector<int> v1, v2 ;
	vector<int> v3;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);

	v2.push_back(4);
	v2.push_back(5);
	v2.push_back(6);

	v3.resize(10);

	//transform(v1.begin(), v1.end(), v2.begin(),v3.begin(), SumAdd<int>());
	/*
	template<class _InIt1,
	class _InIt2,
	class _OutIt,
	class _Fn2> inline
		_OutIt transform(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
	*/
	vector<int>::iterator it = transform(v1.begin(), v1.end(), v2.begin(),v3.begin(), SumAdd<int>());
	cout << *it << endl;
	printE(v3);	
}

二元谓词案例

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
void current(int &v)
{
	cout << v << " ";
}

bool MyCompare(const int &a, const int &b)
{
	return a < b;
}
void main15()
{
	vector<int> v(10);

	for (int i=0; i<10; i++)
	{
		v[i] = rand() % 100;
	}

	for_each(v.begin(), v.end(), current);
	printf("\n");
	sort(v.begin(), v.end(), MyCompare );

	printf("\n");
	for (int i=0; i<10; i++)
	{
		printf("%d ", v[i]);
	}
	printf("\n");
}

预定义函数对象和函数适配器

预定义函数对象基本概念：标准模板库STL提前定义了很多预定义函数对象，#include <functional> 必须包含。

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
//1使用预定义函数对象：
//类模板plus<> 的实现了： 不同类型的数据进行加法运算
void main41()
{
	plus<int> intAdd;
	int x = 10;
	int y = 20;
	int z = intAdd(x, y); //等价于 x + y 
	cout << z << endl;

	plus<string> stringAdd;
	string myc = stringAdd("aaa", "bbb");
	cout << myc << endl;

	vector<string> v1;
	v1.push_back("bbb");
	v1.push_back("aaa");
	v1.push_back("ccc");
	v1.push_back("zzzz");

	//缺省情况下，sort()用底层元素类型的小于操作符以升序排列容器的元素。
	//为了降序，可以传递预定义的类模板greater,它调用底层元素类型的大于操作符：
	cout << "sort()函数排序" << endl;;
	sort(v1.begin(), v1.end(), greater<string>() ); //从大到小
	for (vector<string>::iterator it=v1.begin(); it!=v1.end(); it++ )
	{
		cout << *it << endl;
	}
}

算术函数对象

1
2
3
4
5
6
7
8
9
10
11
12
预定义的函数对象支持加、减、乘、除、求余和取反。调用的操作符是与type相关联的实例
加法：plus<Types>
plus<string> stringAdd;
sres = stringAdd(sva1,sva2);
减法：minus<Types>
乘法：multiplies<Types>
除法divides<Tpye>
求余：modulus<Tpye>
取反：negate<Type>
negate<int> intNegate;
ires = intNegate(ires);
Ires= UnaryFunc(negate<int>(),Ival1);

关系函数对象

1
2
3
4
5
6
7
8
等于equal_to<Tpye>
equal_to<string> stringEqual;
sres = stringEqual(sval1,sval2);
不等于not_equal_to<Type>
大于 greater<Type>
大于等于greater_equal<Type>
小于 less<Type>
小于等于less_equal<Type>
1
2
3
4
5
6
7
8
9
10
11
12
13
void main42()
{
	vector<string> v1;
	v1.push_back("bbb");
	v1.push_back("aaa");
	v1.push_back("ccc");
	v1.push_back("zzzz");
	v1.push_back("ccc");
	string s1 = "ccc";
	//int num = count_if(v1.begin(),v1.end(), equal_to<string>(),s1);
	int num = count_if(v1.begin(),v1.end(),bind2nd(equal_to<string>(), s1));
	cout << num << endl;
}

逻辑函数对象

1
2
3
4
5
6
7
8
9
逻辑与 logical_and<Type>
logical_and<int> indAnd;
ires = intAnd(ival1,ival2);
dres=BinaryFunc( logical_and<double>(),dval1,dval2);
逻辑或		logical_or<Type>
逻辑非		logical_not<Type>
logical_not<int> IntNot;
Ires = IntNot(ival1);
Dres=UnaryFunc( logical_not<double>,dval1);

函数适配器

​ 函数适配器的理论知识

1625480849621

1625480873142

1625480877479

1625480882053

常用函数函数适配器

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

1绑定器（binder）: binder通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。C＋＋标准库提供两种预定义的binder适配器：bind1st和bind2nd，前者把值绑定到二元函数对象的第一个实参上，后者绑定在第二个实参上。

2取反器(negator) : negator是一个将函数对象的值翻转的函数适配器。标准库提供两个预定义的ngeator适配器：not1翻转一元预定义函数对象的真值,而not2翻转二元谓词函数的真值。

常用函数适配器列表如下：

bind1st(op, value)

bind2nd(op, value)

not1(op)

not2(op)

mem_fun_ref(op)

mem_fun(op)

ptr_fun(op)

3）常用函数适配器案例

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class IsGreat
{
public:
	IsGreat(int i)
	{
		m_num = i;
	}
	bool operator()(int &num)
	{
		if (num > m_num)
		{
			return true;
		}
		return false;
	}
protected:
private:
	int m_num;
};

void main43()
{
	vector<int>  v1;
	for (int i=0; i<5; i++)
	{
		v1.push_back(i+1);
	}

	for (vector<int>::iterator it = v1.begin(); it!=v1.end(); it ++)
	{
		cout << *it << " " ;
	}

	int num1 = count(v1.begin(), v1.end(), 3);
	cout << "num1:" << num1 << endl;

	//通过谓词求大于2的个数
	int num2 = count_if(v1.begin(), v1.end(), IsGreat(2)); 
	cout << "num2:" << num2 << endl;

	//通过预定义函数对象求大于2的个数   greater<int>() 有2个参数 
	//												param > 2
	int num3 = count_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 2 ) );
	cout << "num3:" << num3 << endl;

	//取模 能被2整除的数 求奇数
	int num4 = count_if(v1.begin(), v1.end(), bind2nd(modulus <int>(), 2 ) ); 
	cout << "奇数num4:" << num4 << endl;

	int num5 = count_if(v1.begin(), v1.end(), not1( bind2nd(modulus <int>(), 2 ) ) ); 
	cout << "偶数num5:" << num5 << endl;
	return ;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>

using namespace std;
#include<vector>
#include<algorithm>
#include<functional>

class MyPrint:public binary_function<int,int,void>
{
public:
	void operator()(int v, int start) const
	{
		cout << "v=" << v << "start=" << start << "v+start=" << v + start << endl;
	}
};

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++) 
	{
		v.push_back(i);
	}
	cout << "请输入一个起始值：" << endl;
	int num;
	cin >> num;

	//for_each(v.begin(), v.end(), bind2nd (MyPrint(),num));
	for_each(v.begin(), v.end(), bind1st(MyPrint(), num));

}
//第一步，绑定数据 bind2nd
//第二步，继承类 binary_function<参数类型1，参数类型2，返回值类型>
//第三步，加const修饰operator()

int main()
{

	test01();
	system("pause");
	return 0;
}

取反适配器

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class MyPrint:public binary_function<int,int,void>
{
public:
	void operator()(int v, int start) const
	{
		cout << "v=" << v << "start=" << start << "v+start=" << v + start << endl;
	}
};
   //取反适配器
class CreateThenFive:public unary_function<int,bool>
{
public:
	bool operator()(int v)const
	{
		return v > 5;
	}
};
    void test02()
    {
    	//一元取反
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}

	//查找大于5的数字
	//需求改为找小于5的数字
	//vector<int>::iterator pos=find_if(v.begin(), v.end(),not1 (CreateThenFive()));
	vector<int>::iterator pos=find_if(v.begin(), v.end(),not1(bind2nd(greater<int>(),5)));

	if (pos != v.end())
	{
		cout << "找到大于5的数字为：" <<*pos<< endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

//一元取反适配器 not1
//继承unary_fuction<类型1，返回值类型>
//const

10.3.2.8 STL的容器算法迭代器的设计理念

img

1） STL的容器通过类模板技术，实现数据类型和容器模型的分离。

2） STL的迭代器技术实现了遍历容器的统一方法；也为STL的算法提供了统一性

3） STL的函数对象实现了自定义数据类型的算法运算。（算法和）

4） 具体例子：transform算法的输入，通过迭代器first和last指向的元算作为输入；通过result作为输出；通过函数对象来做自定义数据类型的运算。

YanChen

Personal profile