C++算法库

发表于 | 阅读次数:

目前主要介绍我所接触到的C++11中新增的算法

判断：谓词

C++11新增了三个用于判断的算法all_of，any_of，none_of

all_of

1
2
template< class InputIt, class UnaryPredicate >
bool all_of( InputIt first, InputIt last, UnaryPredicate p );

检查区间[first, last)中是否所有的元素都满足一元判断式p，所有的元素都满足条件返回true，否则返回false

any_of

1
2
template< class InputIt, class UnaryPredicate >
bool any_of( InputIt first, InputIt last, UnaryPredicate p );

检查区间[first, last)中是否至少有一个元素都满足一元判断式p，只要有一个元素满足条件就返回true，否则返回true

none_of

1
2
template< class InputIt, class UnaryPredicate >
bool none_of( InputIt first, InputIt last, UnaryPredicate p );

检查区间[first, last)中是否所有的元素都不满足一元判断式p，所有的元素都不满足条件返回true，否则返回false

实例

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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(int argc, char**argv) {
	vector<int> v = { 1,3,5,7,9 };
	auto isEven = [](int i) { return i % 2 != 0; };

	bool isAllOdd = std::all_of(v.begin(), v.end(), isEven);
	if (isAllOdd) {
		// true
		cout << "all is odd" << endl;
	}

	bool isNoneEven = std::none_of(v.begin(), v.end(), isEven);
	if (isNoneEven) {
		// false
		cout << "none is even" << endl;
	}

	vector<int> v1 = { 1, 3, 5, 7, 8, 9 };
	bool anyof = std::any_of(v1.begin(), v1.end(), isEven);
	if (anyof) {
		// true
		cout << "at least one is even" << endl;
	}
	
	return 0;
}

查找

find_if_not

含义与find_if 相反，查找不符合某个条件的元素

find_if也可以实现相同的功能，但是借助find_if_not，就不必再写否定的判断式了，也提升了可读性

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc, char**argv) {
	vector<int> v = { 1, 3, 5, 7, 9, 4 };
	auto isEven = [](int i) { return i % 2 == 0; };
	auto firstEven = std::find_if(v.begin(), v.end(), isEven);
	if (firstEven != v.end())
		cout << "the first even is " << *firstEven << endl;

	//用find_if来查找奇数则需要重新写一个否定含义的判断式
	auto isNotEven = [](int i) {return i % 2 != 0; };
	auto firstOdd = std::find_if(v.begin(), v.end(), isNotEven);

	if (firstOdd != v.end()) {
		cout << "the first odd is " << *firstOdd << endl;
	}

	//用find_if_not来查找奇数则无需新定义判断式
	auto odd = std::find_if_not(v.begin(), v.end(), isEven);
	if (odd != v.end()) {
		cout << "the first odd is " << *odd << endl;
	}

	return 0;
}

输出：

1
2
3
the first even is 4
the first odd is 1
the first odd is 1

copy_if

代码中缩减vector值得学习一下

实际上是对每一个元素应用一个谓词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char**argv) {
	vector<int> v = { 1, 3, 5, 7, 9, 4 };
	std::vector<int> v1(v.size());
	//根据条件拷贝
	auto it = std::copy_if(v.begin(), v.end(), v1.begin(), [](int i) {return i % 2 != 0; });
	//缩减vector到合适大小
	v1.resize(std::distance(v1.begin(), it));
	for (int i : v1){
		cout << i << " ";
	}
	return 0;
}

有序序列：iota

用于生成有序序列，比如我们需要一个定长数组，数组中的元素都是在某一个数值的基础之上递增的

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
#include <numeric>
#include <array>
#include <vector>
#include <iostream>
using namespace std;

int main(int argc,char**argv){
	vector<int> v(4);
	//循环遍历赋值来初始化数组
	//for(int i=1; i<=4; i++){
	//    v.push_back(i);
	//}

	//直接通过iota初始化数组，更简洁
	std::iota(v.begin(), v.end(), 1);
	for (auto n : v) {
		cout << n << " ";
	}
	cout << endl;

	std::array<int, 4> array;
	std::iota(array.begin(), array.end(), 1);
	for (auto n : array) {
		cout << n << " ";
	}
	cout << endl;

	// 输出：
	// 1 2 3 4
	// 1 2 3 4

	return 0;
}

相比遍历赋值更简洁，需要注意iota初始化的序列需要指定大小

max&min

获取最大值和最小值可以分别使用max_element和max_element算法

算法库新增了minmax_element用于同时获取最大值和最小值，将两者的迭代器放到一个pair中返回

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc, char**argv) {
	vector<int> v = { 1, 2, 5, 7, 9, 4 };
	auto result = minmax_element(v.begin(), v.end());
	// pair
	cout << *result.first << " " << *result.second << endl;
	// 1 9 
	return 0;
}

判断：排序

is_sort用于判断某个序列是否是排好序的

is_sort_until则用于返回序列中前面已经排好序的部分序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc,char**argv) {
	vector<int> v = { 1, 2, 5, 7, 9, 4 };
	auto pos = is_sorted_until(v.begin(), v.end());

	for (auto it = v.begin(); it != pos; ++it){
		cout << *it << " ";
	}
	cout << endl;
	// 1 2 5 7 9

	bool is_sort = is_sorted(v.begin(), v.end());
	cout << is_sort << endl;
	// 0
	
	return 0;
}