C++常用算法

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 2.4k | 阅读时长 ≈ 10
C++常用算法

2

C++常用算法

  常用算法是C++刷题的重要法宝，有时需要查找某个元素的索引，有时需要进行排序，有时需要进行替换等等，虽然这些函数的实现并不困难，但是会降低我们的效率，而且C++给我们提供的算法都是非常高效的，我们要充分利用这一优势进行高效的coding。

常用算法介绍

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<numeric>
using namespace std;

void print(int val) {
	cout << val << " ";
}

class Print {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};

int square(int val) {
	return val * val;
}

class Cubic {
public:
	int operator()(int val) {
		return val * val * val;
	}
};

bool greater100(int val) {
	return val > 100;
}

class Greater50 {
public:
	bool operator()(int val) {
		return val > 50;
	}
};

bool myGreater(int a, int b) {
	return a > b;
}

int main() {

	vector<int> v0 = { 1,4,6,2,5,8,7 };
	vector<int> v1(12, 0);
	vector<int> v2(20, -1);

	// 遍历容器，for_each(_InIt _First, _InIt _Last, _Fn _Func)，从对迭代器中的每一个元素进行处理，其中第三个参数是处理方法，可以是普通函数也可以是仿函数
	// 通过普通函数遍历容器
	cout << "v0：";
	for_each(v0.begin(), v0.end(), print);
	cout << endl;

	// 通过仿函数遍历容器
	cout << "v0：";
	for_each(v0.begin(), v0.end(), Print());
	cout << endl;

	// 搬运操作，transform(const _InIt _First, const _InIt _Last, _OutIt _Dest, _Fn _Func)，对迭代器的每一个元素进行处理，然后放入某个迭代器中
	// 其中第三个参数为目标迭代器，第四个参数是处理方法，可以是普通函数也可以是仿函数
	// 通过普通函数搬运操作
	transform(v0.begin(), v0.end(), v1.begin(), square);
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 通过仿函数搬运操作
	transform(v0.begin(), v0.end(), v1.begin() + 3, Cubic());
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 查找元素，find(_InIt _First, const _InIt _Last, const _Ty& _Val)，对迭代器中的每一个元素进行查找，如果找到了目标元素则返回迭代器，否则返回终止迭代器，其中第三个参数是目标元素
	vector<int>::iterator it1 = find(v1.begin() + 1, v1.end(), 1);
	cout << "v1：";
	for_each(it1, v1.end(), print);
	cout << endl;

	// 按条件查找，find_if(_InIt _First, const _InIt _Last, _Pr _Pred)，对迭代器中的每一个元素进行寻找，如果满足条件则返回迭代器，否则返回终止迭代器
	// 其中第三个参数是查找条件，可以是普通函数也可以是仿函数
	// 通过普通函数查找操作
	vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), greater100);
	cout << "v1：";
	for_each(it2, v1.end(), print);
	cout << endl;

	// 通过仿函数查找操作
	vector<int>::iterator it3 = find_if(v1.begin(), v1.end(), Greater50());
	cout << "v1：";
	for_each(it3, v1.end(), print);
	cout << endl;

	// 查找相邻重复元素，adjacent_find(const _FwdIt _First, const _FwdIt _Last)，对迭代器中的每一个元素进行寻找，如果范围内存在相邻重复元素则返回迭代器，否则返回终止迭代器
	vector<int>::iterator it4 = adjacent_find(v1.begin(), v1.end());
	cout << "v1：";
	for_each(it4 - 2, v1.end(), print);
	cout << endl;

	// 统计元素个数，count(const _InIt _First, const _InIt _Last, const _Ty& _Val)，统计迭代器范围内，目标元素的个数，其中第三个参数是目标元素
	cout << "v1中1出现的个数为：" << count(v1.begin(), v1.end(), 1) << endl;

	// 按条件统计，count_if(_InIt _First, _InIt _Last, _Pr _Pred)，统计迭代器范围内，满足条件的元素个数，其中第三个参数是条件，可以是普通函数也可以是仿函数
	// 通过普通函数统计操作
	cout << "v1中大于100的元素个数为" << count_if(v1.begin(), v1.end(), greater100) << endl;
	// 通过仿函数统计操作
	cout << "v1中大于50的元素个数为" << count_if(v1.begin(), v1.end(), Greater50()) << endl;

	// 排序，sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred)，对迭代器范围内的元素进行排序，其中第三个参数是排序方式，可以是普通函数也可以是仿函数
	// 通过普通函数统计操作
	sort(v1.begin(), v1.end(), myGreater);
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 通过仿函数统计操作，因为存在内置关系仿函数，因此直接使用即可
	sort(v1.begin(), v1.end(), less<int>());
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 随机打乱，random_shuffle(_RanIt _First, _RanIt _Last)，对迭代器范围内的元素随机打乱
	random_shuffle(v1.begin(), v1.end());
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 合并两个有序容器，merge(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)，前两个参数为第一个容器的范围，中间两个参数为第二个容器的范围，最后一个参数为目标容器的迭代器
	// 要注意两个容器要是有序的，而且目标容器的剩余空间要大于等于两个容器空间之和。
	sort(v0.begin(), v0.end());
	sort(v1.begin(), v1.end());
	merge(v0.begin(), v0.end(), v1.begin(), v1.end(), v2.begin());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 逆序，reverse(const _BidIt _First, const _BidIt _Last)，对迭代器范围内的元素逆序排列
	reverse(v2.begin(), v2.end());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 拷贝，copy(_InIt _First, _InIt _Last, _OutIt _Dest)，对迭代器的每一个元素拷贝到另一个迭代器中，其中第三个参数为目标迭代器
	// 要注意目标容器的剩余空间要大于等于原容器。
	copy(v0.begin(), v0.end(), v2.begin());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 替换，replace(const _FwdIt _First, const _FwdIt _Last, const _Ty& _Oldval, const _Ty& _Newval)，将替换迭代器范围内所有旧元素都替换为新元素，其中第三个参数为旧元素，第四个参数为新元素。
	replace(v2.begin(), v2.end(), 8, -8);
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 按条件替换，replace_if(const _FwdIt _First, const _FwdIt _Last, _Pr _Pred, const _Ty& _Val)，将替换迭代器范围内所有符合条件的元素都替换为新元素
	// 其中第三个参数是条件，可以是普通函数也可以是仿函数，第四个参数为新元素。
	// 通过普通函数替换操作
	replace_if(v1.begin(), v1.end(), greater100, 80);
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);

	// 通过仿函数替换操作
	cout << endl;
	replace_if(v1.begin(), v1.end(), Greater50(), 30);
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	// 交换，swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right)，交换两个容器
	swap(v1, v2);
	cout << "v1：";
	for_each(v1.begin(), v1.end(), print);
	cout << endl;

	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 累加求和，accumulate(const _InIt _First, const _InIt _Last, _Ty _Val)，需要导入numeric头文件，计算迭代器范围内所有元素之和，并且加上初始元素，其中第三个元素为初始元素
	// 如果只需要计算迭代器范围内元素之和，则初始元素传入0即可
	cout << "v2的所有元素之和再加10为：" << accumulate(v2.begin(), v2.end(), 10) << endl;

	// 填充，fill(const _FwdIt _First, const _FwdIt _Last, const _Ty& _Val)，需要导入numeric头文件，将迭代器范围内所有元素都替换为目标元素，其中第三个参数为目标元素
	fill(v2.begin() + 5, v2.end(), 10);
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	cout << "v0：";
	for_each(v0.begin(), v0.end(), print);
	cout << endl;

	// 集合交集，set_intersection(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)，前两个参数为第一个容器的范围，中间两个参数为第二个容器的范围，最后一个参数为目标容器的迭代器
	// 要注意两个容器要是有序的，而且目标容器的剩余空间要满足条件。
	set_intersection(v0.begin() + 2, v0.end(), v0.begin(), v0.end() - 2, v2.begin());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 集合并集，set_union(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)，前两个参数为第一个容器的范围，中间两个参数为第二个容器的范围，最后一个参数为目标容器的迭代器
	// 要注意两个容器要是有序的，而且目标容器的剩余空间要满足条件。
	set_union(v0.begin() + 5, v0.end(), v0.begin(), v0.end() - 5, v2.begin());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);
	cout << endl;

	// 集合差集，set_difference(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)，前两个参数为第一个容器的范围，中间两个参数为第二个容器的范围，最后一个参数为目标容器的迭代器
	// 要注意两个容器要是有序的，而且目标容器的剩余空间要满足条件。
	set_difference(v0.begin() + 2, v0.end(), v0.begin(), v0.end() - 2, v2.begin());
	cout << "v2：";
	for_each(v2.begin(), v2.end(), print);

	cout << endl;

	return 0;
}

4

C++小结

  在这篇博客中介绍了很多常用的算法，现在想找一个满意的工作，刷题是非常重要的一个环节，而使用C++语言刷题的小伙伴们一定会使用得到，希望能对你起到一些帮助。

-------------本文结束感谢您的阅读-------------
0%