常用库函数

声明

都存在#include <algorithm>这个库中

reverse翻转

翻转一个vector：

1
reverse(a.begin(), a.end());

翻转一个数组，元素存放在下标1 ~ n：

1
reverse(a + 1, a + n + 1);

unique去重

返回去重（只去掉相邻的相同元素）之后的为迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。

去重一个vector

1
2
3
4
5
6
// a: 5 5 4 1 2 2 3
int m = unique(a.begin(), a.end()) - a.begin();
cout << m << endl;
// m = 5
for(int t : a) cout << t << " ";
// a: 5 4 1 2 3 2 3

去重一个数组，元素存放在下标1 ~ n：

1
2
3
4
5
6
7
int a[8] = {10, 5, 5, 4, 1, 2, 2, 3};
int n = 8;
int cnt = unique(a + 1, a + n + 1) - (a + 1);
cout << cnt << endl;
// cnt = 5
for(auto t : a) cout << t << " ";
// a : 0 5 4 1 2 3

random_shuffle随机打乱

用法与reverse相同。

sort

对两个迭代器（或指针）指定的部分进行快速排序。可以再第三个参数传入定义大小比较的函数，或者重载"小于号"运算符。

把一个int数组（数组存放在下标1 ~ n）从大到小排序，传入比较函数：

1
2
3
4
5
6
int a[MAX_SIZE];
bool cmp(int a, int b)
{
    return a > b;
}
sort(a + 1, a + n + 1, cmp);

把自定义的结构体vector排序，重载"小于号"运算符：

1
2
3
4
5
6
7
8
9
10
11
12
struct Rec
{
	int id, x, y;    
};

vector<Rec> a;

bool operator <(const Rec &a, const Rec &b)  // 重载小于号
{
    return a.x < b.x || a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());

lower_bound/upper_bound二分

lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。

upper_bound的用法和lower_bound大致相同，唯一的区间就是查找的第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

在有序int数组（元素放在下标1 ~ n）中查找大于等于x的最小整数的下标：

1
int i = lower_bound(a + 1, a + 1 + n, x) - a;