【笔记】C++之Algorithm头文件下的常用函数

使用这些函数前要加上include <algorithm>和using namespace std;。

文章目录

1 max()、min()、abs()2 swap()3 reverse()4 next_permutation()5 fill()6 sort()6.1 使用方式6.2 如何实现比较函数cmp 7 lower_bound()、upper_bound()

1 max()、min()、abs()

max(x,y)、min(x,y)分别返回x和y中的最大、小值。如果要返回x、y、z中的最大值，可用``max(x,max(y,z))`

abs(x)返回x的绝对值，x必须是整数。 浮点数的绝对值用math头函数下的fabs(x)。

2 swap()

swap(x,y)交换x和y的值。

3 reverse()

reverse(it,it2)可将数组指针在[it, it2)之间的元素或容器的迭代器在[it, it2)之间的元素进行反转。

#include <stdio.h> #include <algorithm> using namespace std; int main(void){ int a[10] = {10, 11, 12, 14, 15, 16}; reverse(a, a + 3); for(int i = 0; i < 6; i++) { printf("%d ", a[i]); } return 0; }

输出结果：

12 11 10 14 15 16

容器（如string）：

#include <stdio.h> #include <algorithm> #include <string> using namespace std; int main(void){ string str = "abcdefg"; reverse(str.begin() + 3, str.begin() + 7); for(int i = 0; i < 7; i++) { printf("%c ", str[i]); } return 0; }

输出结果：

a b c g f e d

4 next_permutation()

permutation为排列的意思。

next_permutation()给出一个序列在全排列中的下一个序列。返回bool类型。

例如，当n==3时的全排列为：

123 132 213 231 //231的下一个序列就是312 312 321 #include <stdio.h> #include <algorithm> using namespace std; int main(void){ int a[10] = {1, 2, 3}; do{ printf("%d%d%d\n", a[0], a[1], a[2]); }while(next_permutation(a, a + 3)); return 0; }

输出结果：

123 132 213 231 312 321

5 fill()

fill()可以把数组或容器某一段区间赋为某个相同的值。和memset不同，这里的赋值可以是数组类型对应范围中的任意值。

#include <stdio.h> #include <algorithm> using namespace std; int main(void){ int a[10] = {1, 2, 3, 4, 5}; fill(a, a + 5, 33); for(int i = 0; i < 5; i++) { printf("%d ", a[i]); } return 0; }

输出结果：

33 33 33 33 33

6 sort()

6.1 使用方式

定义：

sort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数（非必填）);

如果不写比较函数，默认对给出区间进行递增排序。

对int型数组排序： #include <stdio.h> #include <algorithm> using namespace std; int main(void){ int a[6] = {4, 2, 44, 1, 23, -2}; sort(a, a + 4); // 将a[0]~a[3]从小到大排序 for(int i = 0; i < 6; i++) { printf("%d ", a[i]); } printf("\n"); sort(a, a + 6); // 将a[0]~a[5]从小到大排序 for(int i = 0; i < 6; i++) { printf("%d ", a[i]); } return 0; }

输出结果：

1 2 4 44 23 -2 -2 1 2 4 23 44 对double型数组排序： #include <stdio.h> #include <algorithm> using namespace std; int main(void){ double a[] = {1.3, -2.1, 4}; sort(a, a + 3); for(int i = 0; i < 3; i++) { printf("%.1f ", a[i]); } return 0; }

输出结果：

-2.1 1.3 4.0 对char型数组排序（默认为字典序）： #include <stdio.h> #include <algorithm> using namespace std; int main(void){ char a[] = {'T', 'a', 'W', 'A'}; sort(a, a + 4); for(int i = 0; i < 4; i++) { printf("%c ", a[i]); } return 0; } A T W a

6.2 如何实现比较函数cmp

结构体本身没有大小关系，需要人为定制比较的规则，用compare函数（一般写作cmp函数），实现这个规则。

基本数据类型数组的排序：

如果想要从大到小排序，要使用cmp“告诉”sort何时要交换元素。

#include <stdio.h> #include <algorithm> using namespace std; bool cmp(int a, int b) { return a > b; // 可以理解为当a > b时把a放b前面 } int main(void){ int a[6] = {4, 2, 44, 1, 23, -2}; sort(a, a + 6, cmp); // 将a[0]~a[5]从大到小排序 for(int i = 0; i < 6; i++) { printf("%d ", a[i]); } return 0; }

输出结果：

44 23 4 2 1 -2

double型、char类型数据同理。

结构体数组的排序

#include <stdio.h> #include <algorithm> using namespace std; struct node{ int x, y; }ssd[10]; bool cmp(node a, node b) { // 先将x按从大到小排序，当x相等的情况下，按照y的大小按 从大到小排序 if(a.x != b.x) return a.x > b.x; else return a.y > b.y; } int main(void){ ssd[0].x = 2; ssd[0].y = 2; ssd[1].x = 1; ssd[1].y = 3; ssd[2].x = 2; ssd[2].y = 1; sort(ssd, ssd + 3, cmp); for(int i = 0; i < 3; i++) { printf("%d %d\n", ssd[i].x, ssd[i].y); } return 0; }

输出结果：

2 2 2 1 1 3

容器的排序

STL容器中，只有vector、string、deque是可以使用sort的。这是因为想set、map这种容器是用红黑树实现的（了解即可），元素本身有序。

vector

#include <stdio.h> #include <vector> #include <algorithm> using namespace std; bool cmp(int a, int b) { return a > b; //按从大到小排序 } int main(void){ vector<int> vi; vi.push_back(3); vi.push_back(1); vi.push_back(2); sort(vi.begin(), vi.end(), cmp); // 对整个vector排序 for(int i = 0; i < 3; i++) { printf("%d ", vi[i]); } return 0; }

输出结果：

3 2 1

string

#include <iostream> #include <string> #include <algorithm> using namespace std; bool cmp(string a, string b) { return a.length() < b.length(); // 按string的长度从小到大排序 } int main(void){ string str[] = {"bbbbbbb", "aaa", "ccccc"}; sort(str, str + 3, cmp); for(int i = 0; i < 3; i++) { cout << str[i] << endl; } return 0; }

输出结果：

aaa ccccc bbbbbbb

7 lower_bound()、upper_bound()

lower_bound()、upper_bound()需要用在一个有序数组或容器中。

lower_bound(first, last, val)：寻找在在数组或容器的[first, last)范围内的第一个值大于等于val元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

upper_bound(first, last, val)：寻找在在数组或容器的[first, last)范围内的第一个值大于val元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

如果数组或容器中没有需要寻找的元素，则lower_bound()、upper_bound()均返回可以插入该元素的位置的指针和迭代器。

#include <cstdio> #include <algorithm> using namespace std; void findPos(int a[], int n, int value){ int* lowerPos = lower_bound(a, a + n, value); int* upperPos = upper_bound(a, a + n, value); printf("%d, %d\n", lowerPos - a, upperPos - a); } int main(void){ int a[10] = {1, 2, 2, 3, 3, 3, 5, 5, 5, 5}; // 寻找-1 findPos(a, 10, -1); // 寻找1 findPos(a, 10, 1); // 寻找3 findPos(a, 10, 3); // 寻找4 findPos(a, 10, 4); // 寻找6 findPos(a, 10, 6); return 0; }

输出结果：

0, 0 0, 1 3, 6 6, 6 10, 10