前言：本篇主要简单记录一些平时遇到的好用的或者性能很特别的函数，持续更新中

1.关于全排列

(1)next_permutation()

头文件：

#include <algorithm>

函数原型：

bool next_permutation(iterator begin,iterator end)

用来求全排列的下一项（按字典序）

例：对于以下代码：

char ch[5]={'a','d','b','e','c'};
next_permutation(ch,ch+5);
cout << ch[0] << ch[1] << ch[2] << ch[3] << ch[4] << endl;

输出结果为：

adcbe

需要注意的是，这个函数返回值类型是\(bool\)，当数组已经完全倒序时，函数会返回\(false\)，根据这一原理，我们可以利用一个do-while循环，对一个按字典序排列好的数组进行全排列的遍历：

char ch[3]={'a','b','c'};
do{
	cout << ch[0] << ch[1] << ch[2] << endl;
}while(next_permutation(ch,ch+3));

注意这里一定要用do-while，否则不会有原先的排列顺序

输出结果为：

abc
acb
bac
bca
cab
cba

(2)prev_permutation()

头文件：

#include <algorithm>

函数原型：

bool prev_permutation(iterator begin,iterator end)

用来求全排列的上一项（按字典序）

与上面的next_permutation()类似，对于以下代码：

char ch[5]={'a','d','b','e','c'};
prev_permutation(ch,ch+5);
cout << ch[0] << ch[1] << ch[2] << ch[3] << ch[4] << endl;

输出结果为：

adbce

同理，当数组已经完全正序时，函数会返回\(false\)，我们同样可以利用一个do-while循环，对一个完全倒序的数组进行全排列的遍历：

char ch[3]={'c','b','a'};
do{
	cout << ch[0] << ch[1] << ch[2] << endl;
}while(prev_permutation(ch,ch+3));

输出结果为：

cba
cab
bca
bac
acb
abc

2.关于二分查找

(1)lower_bound()

头文件：

#include <algorithm>

函数原型：

iterator lower_bound(iterator begin,iterator end,const T& val);

用来求单调不减序列\([begin,end)\)中第一个数值\(\geq val\)的迭代器，其中传入的参数\(begin\)和\(end\)分别为序列开头和末尾的迭代器，特别地，如果序列中所有数值都\(< val\)，则会返回数组中下标为\(end\)的迭代器

例：对于以下代码

int a[5]={1,3,5,7,9};
cout << (lower_bound(a,a+5,1)-a) << " ";
cout << (lower_bound(a,a+5,2)-a) << " ";
cout << (lower_bound(a,a+3,8)-a) << " ";
cout << (lower_bound(a,a+5,10)-a) << endl;

输出结果为：

0 1 3 5

需要注意的是，这个函数内部实现利用了二分查找的原理，时间复杂度为\(O(\log n)\)，所以并不需要手写二分查找函数

(2)upper_bound()

头文件：

#include <algorithm>

函数原型：

iterator upper_bound(iterator begin,iterator end,const T& val);

用来求单调不减序列\([begin,end)\)中第一个数值\(> val\)的迭代器，其中传入的参数\(begin\)和\(end\)分别为序列开头和末尾的迭代器，特别地，如果序列中所有数值都\(\leq val\)，则会返回数组中下标为\(end\)的迭代器

例：对于以下代码

int a[5]={1,3,5,7,9};
cout << (upper_bound(a,a+5,1)-a) << " ";
cout << (upper_bound(a,a+5,2)-a) << " ";
cout << (upper_bound(a,a+3,8)-a) << " ";
cout << (upper_bound(a,a+5,10)-a) << endl;

输出结果为：

1 1 3 5

同理，这个函数内部实现也利用二分查找，时间复杂度\(O(\log n)\)

(3)equal_range()

头文件：

#include <algorithm>

函数原型：

pair<iterator,iterator> equal_range(iterator begin,iterator end,const T& val)

主要作用是在单调不减区间\([begin,end)\)内，寻找\(val\)，返回值是一个\(pair\)，\(first\)指向\(val\)的起始位置，\(second\)指向\(val\)的末尾之后的位置，特别地，如果序列内不含\(val\)，会返回一个\(first\)和\(second\)都指向\(val\)应插入的位置

其实这个函数就是lower_bound()和upper_bound()的相加，\(pair\)的第一维就相当于lowerbound(begin,end,val)的值，第二维相当于upperbound(begin,end,val)的值

例：对于以下代码

int a[10]={1,2,2,3,3,3,5,5,7,7};
auto bounds=equal_range(a,a+10,3);
cout << bounds.first-a << " " << bounds.second-a << endl;
bounds=equal_range(a,a+10,4);
cout << bounds.first-a << " " << bounds.second-a << endl;

输出结果为：

3 6
6 6

同理，利用二分，时间复杂度\(O(n)\)

(4)binary_search()

头文件：

#include <algorithm>

函数原型：

bool binary_search(iterator start,iterator end,const T& val)

用来判断单调不减序列\([begin,end)\)中，是否存在\(val\)，若存在，返回\(true\)；若不存在，返回\(false\)

例：对于以下代码：

int a[5]={1,3,5,7,9};
if(binary_search(a,a+5,5)) cout << "Yes" << endl;
else cout << "No" << endl;
if(binary_search(a,a+5,6)) cout << "Yes" << endl;
else cout << "No" << endl;

输出结果为：

Yes
No

这个函数的内部实现同样利用了二分查找，时间复杂度\(O(\log n)\)

3.关于排序

(1)partial_sort()

头文件：

#include <algorithm>

函数原型：

void partial_sort(iterator begin,iterator middle,iterator end)

函数名称直译为“部分排序”，这个函数可以在无序的\([begin,end)\)区间内找到\((middle-begin)\)个最小的元素，并将它们置于数组的最前面，其余元素置于数组最后，但是要注意，其余元素的相对位置可能会改变，主要原因是内部实现利用大根堆进行比较

与sort()函数一样，我们也可以自定义比较函数，传参时写在\(end\)之后，就能以自定义排序规则进行部分排序

例：对于以下代码

//自定义升序规则
bool cmp(int a,int b){return a>b;} 
//以下在main函数中
int a[10];
srand(time(0));
for(int i=0;i<10;i++)
	a[i]=rand()%100;
cout << "随机赋值后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
partial_sort(a,a+5,a+10);
cout << endl;
cout << "局部排序后，a数组如下：" << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
partial_sort(a,a+10,a+10);
cout << endl;
cout << "全部排序后，a数组如下：" << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
partial_sort(a,a+5,a+10,cmp);
cout << endl;
cout << "自定义局部排序后，a数组如下：" << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
partial_sort(a,a+10,a+10,cmp);
cout << endl;
cout << "自定义全部排序后，a数组如下：" << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";

一组输出结果为：

随机赋值后，a数组如下：
49      16      36      52      17      83      60      51      14      27
局部排序后，a数组如下：
14      16      17      27      36      83      60      52      51      49
全部排序后，a数组如下：
14      16      17      27      36      49      51      52      60      83
自定义局部排序后，a数组如下：
83      60      52      51      49      14      16      17      27      36
自定义全部排序后，a数组如下：
83      60      52      51      49      36      27      17      16      14

值得一提的是，这个函数的时间复杂度为\(O(n\log m)\)，其中\(n\)表示整个区间长度，\(m\)表示从\(begin\)到\(middle\)的长度，对于算法竞赛可能较慢，建议谨慎使用

(2)nth_element()

头文件：

#include <algorithm>

函数原型：

void nth_element(iterator begin,iterator middle,iterator end)

这个函数可以在无序的\([begin,end)\)区间内找到第\((middle-begin+1)\)小的数，并将其置于正确的下标为\((middle-begin)\)的位置，且所有小于等于这个数的都在其左边，大于等于这个数的都在其右边 (但不保证整个序列单调不下降)

例：对于以下代码：

int a[10];
srand(time(0));
for(int i=0;i<10;i++)
	a[i]=rand()%100;
cout << "随机赋值后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
nth_element(a,a+4,a+10);
cout << endl;
cout << "找到下标为4的元素后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";

一组输出结果为：

随机赋值后，a数组如下：
61      83      9       62      41      13      92      51      95      42
找到下标为4的元素后，a数组如下：
42      13      9       41      51      61      92      83      95      62

值得一提的是，这个函数的时间复杂度为\(O(n)\)，其中\(n\)为序列长度，在无序序列中求第\(k\)小(大)等类似题目中是比较优秀的时间复杂度，与上面的partial_sort()函数相比，nth_element()函数可能可以处理更多的实际问题

(3)stable_sort()

头文件：

#include <algorithm>

函数原型：

void stable_sort(iterator begin,iterator end)

与sort()函数类似，这个函数也是对\([begin,end)\)区间内的序列进行排序(默认升序)

但是这两个函数的不同点是：sort()函数的内部实现主要依靠快速排序的思想，还外加了插入排序和堆排序，而stable_sort()函数的内部实现依靠归并排序的思想，它能保证排序后相同元素的相对位置不改变，是一种稳定排序，但是相比而言，sort()函数比stable_sort()函数时间复杂度要低一些

同理，我们也可以自定义比较函数，与sort()函数一样传入参数，使其按照自定义的排序规则排序

(4)is_sorted()

C++11的新函数，算法竞赛勿用

头文件：

#include <algorithm>

函数原型：

bool is_sorted(iterator begin,iterator end)

这个函数会判断\([begin,end)\)区间内序列是否有序(默认判断是否升序)，若已有序返回\(true\)，反之返回\(false\)，特别地，如果序列内只有\(1\)个元素，也会返回\(true\)

同理，我们也可以自定义比较函数传入参数，使其按照自定义的排序规则判断是否有序

内部实现是\(for\)循环暴力判断相邻两个是否有序，时间复杂度\(O(n)\)

4.关于序列操作

(1)fill()

头文件：

#include <algorithm>

函数原型：

void fill(iterator begin,iterator end,const T& val)

主要作用是将序列内\([begin,end)\)区间内的值全部赋为\(val\)

~~(其实就是省个for循环而已)~~

例：对于以下代码

int a[10];
srand(time(0));
for(int i=0;i<10;i++)
	a[i]=rand()%100;
cout << "随机赋值后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
fill(a,a+5,111);
cout << endl; 
cout << "填充前五个元素为111后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";

一组输出结果为：

随机赋值后，a数组如下：
29      54      83      2       68      79      71      6       81      55
填充前五个元素为111后，a数组如下：
111     111     111     111     111     79      71      6       81      55

(2)fill_n()

头文件：

#include <algorithm>

函数原型：

void fill_n(iterator begin,const T& count,const T& val)

主要作用是将序列内从\(begin\)开始，长度为\(count\)的区间内的值全部赋为\(val\)

~~(其实也还是省个for循环而已)~~

例：对于以下代码

int a[10];
srand(time(0));
for(int i=0;i<10;i++)
	a[i]=rand()%100;
cout << "随机赋值后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";
fill_n(a,5,111);
cout << endl; 
cout << "填充前五个元素为111后，a数组如下："  << endl;
for(int i=0;i<10;i++)
	cout << a[i] << "\t";

一组输出结果为：

随机赋值后，a数组如下：
38      37      14      27      10      57      61      3       85      29
填充前五个元素为111后，a数组如下：
111     111     111     111     111     57      61      3       85      29

(3)unique()

头文件：

#include <algorithm>

函数原型：

iterator unique(iterator begin,iterator end)

主要作用是把一个有序数组去重，并返回首个不重复的元素的迭代器

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。