#include<algorithm>

下面介绍的几个函数都作用在序列上，接受两个迭代器（或指针）$l,r$ ，对下标处于前闭后开区间 $[l,r)$ 中的元素执行一系列操作。

reverse 翻转

翻转一个 vector : reverse(a.begin(),a.end());

翻转一个数组，元素存放在下标 1~n : reverse(a+1,a+n+1);

unique 去重

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

把一个 vector 去重：

int m = unique(a.begin(),a.end()) - a.begin();

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

int m = unique(a+1,a+n+1) - (a+1);

random_shuffle 随机

​ 用法与 reverse 相同。

next_permutation 下一个排列

把两个迭代器（或指针）指定的部分看作一个排列，求出这些元素构成的全排列中，字典序排在下一个的排列，并直接在序列上更新。另外，若不存在排名更靠后的排列，则返回 false ，否则返回 true 。 同理，也有 prev_permutation 函数。

下面的程序按字典序输出 1~n 的 n! 种全排列：

for(int i = 1;i <= n ; i++)a[i]=i;
do{
    for(int i=1 ; i<n ; i++)cout<<a[i]<' ';
    cout<<a[n]<<'\n';
}while(next_permutation(a+1,a+n+1));

sort 快速排序

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

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

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

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

struct node{ int id,x,y; };
vector< node > a;
bool operator < (const node &a,const node &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 的最小整数的下标：

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

在有序 vector<int> 中查找小于等于 x 的最大整数（假设一定存在）：

int y=*--upper_bound(a.begin(),a.end(),x);

学习完毕

{{ select(1) }}

• YES
• NO