@fcxxzux 2017-02-02T17:21:34.000000Z 字数 14274 阅读 1372

Learning a Part of C++(for ACM/ICPC) (6) STL算法

我们先来讲解STL的算法们。
先讲的原因比较简单，你可以在数组上直接使用，同时，实在是很省功夫啊。

1、最大和最小

在开始这个话题前，我们先讲一个关键点：

Tips 01

在STL中，任何涉及到大小比较的地方，都会使用<（小于号）以及其等效的，进行小于比较的函数来进行。

那么，我们写代码的时候，总要取最大值/最小值，有时要整个数组的最大值/最小值，欢迎来偷懒使用max()/min()/max_element()/min_element()

int a=5,b=3;
int max_ab=std::max(a,b); //5
int min_ab=std::min(a,b); //3
int arr[]={-5,8,3,4,9,2,-10};
int max_of_arr=*(std::max_element(arr, arr + 7)); //9
int min_of_arr=*(std::min_element(arr, arr + 7)); //-10

当然，我们也可以像用sort时一样，指定一个比较函数，比如说，呃，我们来求绝对值最小的：

bool abs_cmp(int a,int b){
    return abs(a)<abs(b);
}
int arr[]={-5,8,3,4,9,2,-10};
int max_of_arr=*(std::max_element(arr, arr + 7, abs_cmp)); //-10
int min_of_arr=*(std::min_element(arr, arr + 7, abs_cmp)); //2

顺带一提：

Tips 02

在STL中，涉及到一个（元素存储的）地址范围的，永远采取 左闭右开 的形式。
也就是说，开始迭代器指向第一个有效元素，结束迭代器指向最后一个有效元素之后。

2、有关排序

排序的sort()其实我们在前面的运算符重载一章中提到过了(https://www.zybuluo.com/fcxxzux/note/292911)，这里不会对讲过的内容再次重复。但是还有一些东西我们要在这里提一下：

1 . 请一定要定义严格的小于号！请一定要定义严格的小于号！请一定要定义严格的小于号！
不然真的会出现包括超时、运行时错误（爆栈）等问题。
具体解释的话：
正常情况下，只有一个小于号，怎么知道2个数的关系呢？
通过2次小于比较：a < b和b < a

a < b	b < a	结论
True	False	a 小于 b
False	True	a 大于 b
False	False	a 等于 b
True	True	？？？？？？

两者都为真，算什么东西啊？然后这个排序函数自己就混乱了……
所以，请不要：

bool cmp(int a,int b){
    return a<=b;
}

请：

bool cmp(int a,int b){
    return a<b;
}

2 . sort()的时候，自定义函数，如果是结构体，请一定要传常引用，请一定要传常引用，请一定要传常引用
不然网络赛的时候超时了我不负责，我已经尽了告知义务了。

3 . 有关 stable_sort() 与排序稳定性：

有同学自己上网找，发现了stable_sort()这个函数，然后问为什么不用。
这个问题的话，主要问题是，stable_sort()在大部分情况下跑得没有sort()快（除非数据基本有序，两者运行时间可能stable_sort()好一点）。
那为什么STL要提供stable_sort()呢？
注意到，前面有个单词，stable，意思是，稳定的。
稳定的排序？
这就涉及到了排序稳定性的问题。

排序稳定性，不是说执行时间的确定性，而是指：
有多个同关键词的数据，在排序后，保证他们先后顺序不变的特性。

这么说有点抽象，不妨来做实验：

Exp 01

请执行以下代码，观察结果：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int n=100;
struct Person{
    int id;
    int score;
    Person(){}
    Person(int a,int b):id(a),score(b){}
    bool operator<(const Person& b) const{
        return score>b.score;
    }
}lista[n],listb[n];
int main()
{
    for(int i=0;i<n;i++){
        listb[i]=lista[i]=Person(i+1,rand()%10);
    }
    sort(lista,lista+n);
    stable_sort(listb,listb+n);
    for(int i=0;i<n;i++){
        printf("%d %d",lista[i].id,lista[i].score);
        printf("--%d %d\n",listb[i].id,listb[i].score);
    }
    return 0;
}

可以发现：
同一个score的情况下，sort排序出来的结果，id的顺序已经完全打乱，
而stable_sort得到的结果，id的顺序保持和原始给定的顺序一样。
这就是排序稳定性的意义。这个排序稳定性有时候做题进行排序的时候，是有必要保证的，这个要靠大家自己去甄别了。

4 .（扩展知识）使用C++11的lambda表达式来作为自定义排序规则。

如果你说：诶呀，我这个特定的比较规则可能只用一次，不想再回到前面专门写个函数，怎么办啊？

不用担心，C++11引入了一个新东西：lambda表达式。
我们可以这样写：

struct Person{
    int id;
    int score;
    Person(){}
    Person(int a,int b):id(a),score(b){}
}lista[n];
sort(a,a+n,[](const Person& a, const Person& b){
    return a.score>b.score; // 按分数从高到低排序
});
sort(a,a+n,[](const Person& a, const Person& b){
    return a.id<b.id; // 按id从小到大排序
})

注意到，我们的[](const Person& a, const Person& b){return a.id<b.id;}部分，就是所谓的lambda表达式了。
[]表示捕获变量，()中的为参数，sort需要2个参数（小于关系是二元谓词嘛，二元，就2个参数），{}中的为具体的代码了。
总体来讲，就是个不用取名、可以不用写返回值类型的函数（返回值类型在编译期间自动推导）。

注意：lambda 表达式是从C++11开始支持的，如果想在比赛中使用，请确定比赛平台的编译器支持C++11/你自己选择的提交语言是对应开启C++11支持的。

竞赛中所需的lambda表达式基本就是这样，如果想要了解更多，请参阅：
http://zh.cppreference.com/w/cpp/language/lambda
https://msdn.microsoft.com/zh-cn/library/dd293608.aspx

3、排序之后（1） —— 二分查找

一般我们排序之后要干嘛？
利用有序性，O(n)处理过去以外，
有时候我们需要通过二分查找，确定有没有某个数值/最小的大于特定值的数值等等等等。
STL贴心的考虑了我们的需求，提供了二分查找的函数们：lower_bound、upper_bound、binary_search、equal_range。

这三个函数的参数格式一模一样：
xxxxxx(开始位置, 结束位置, 待查找数值 [,自定义比较函数])
主要差别在返回值上了。

首先，binary_search：返回bool，表示待查找数值在这个查找范围内有没有存在，有就返回true，否则返回false。

其次：lower_bound和upper_bound返回一个迭代器，
lower_bound指向第一个大于等于这个待查找数值的迭代器
upper_bound指向第一个大于这个待查找数值的迭代器
……好难记啊。

没事，结合equal_range反而好记：
equal_range返回一个pair<迭代器, 迭代器>，
其中.first指向第一个大于等于待查找数值的地方，
.second指向最后一个等于待查找数值的地方之后一个位置，
或者说，假设equal_range(array, array + n, 10)的返回值为x，那么[x.first, x.second)这一段之内的东西的值都为10。（你看，还是左闭右开）
而且，x.first就是由lower_bound得到的，x.second就是由upper_bound得到的。

注意：lower_bound、upper_bound、equal_range 他们的返回值都是迭代器（或者一对迭代器），你要知道下标？和数组的开始位置做个减法。

Tips 03

大家应该都知道，二分查找要基于随机访问（通过下标直接跳转）。
那么，请不要把非随机访问迭代器给这些二分查找函数，不然会使用O(n)的算法去确定要查找的对象的，这样就慢飞了。
或者说，除了：数组指针、vector的迭代器、deque的迭代器、自定义的随机访问迭代器，其他的迭代器不要给这些二分查找函数。

还是很抽象？那就举例子吧：

Exp 02

请执行以下代码，观察结果：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main()
{
    int a[6]={0,1,2,2,2,3};
    printf("lower_bound: %d\n",lower_bound(a,a+6,2)-a); // 2
    printf("upper_bound: %d\n",upper_bound(a,a+6,2)-a); // 5
    return 0;
}

Tips 04

lower_bound、upper_bound、equal_range的返回值均是迭代器。
要得到下标，请把返回结果和首指针/首迭代器相减。
（如果只是想取值，直接用*解引用/->通过迭代器解引用+访问成员就行了）

Bonus 01
对自定义函数进行二分查找

一般情况下，我们都认为，这种lower_bound / upper_bound是没法用于函数的二分查找的。
比如下面这个题：

现在一种饮料在促销，3个瓶盖换1瓶新的饮料。（当然，每瓶只有1个瓶盖）
你现在想喝至少n瓶（ $n \le 10^9$ ），问在不能和别人借瓶盖的情况下，你最少要花钱买多少瓶饮料。

显然，很容易写出一个函数，表示买x瓶饮料，最后最多能喝到多少瓶。
然后我们用二分查找。好吧，手写一个

二分查找写多了，你会发现，其实这个东西很容易写错导致死循环……
然后要不死记硬背，要不偷懒：把数量缩小到很小的规模，然后就3~5个东西暴力枚举一下。
那么，我们有办法利用STL里的这些二分查找函数来找到解吗？

当然可以！就是，非常需要技巧……
（我目前只找到下面这个解决方案，如果你找到其他的，请告诉我）

大体思路：我们把这个需要二分查找的函数，包装成一个随机访问迭代器，然后我们可以喂给STL的二分查找函数了！
我的实现如下：

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct MyPtr:public std::iterator<std::random_access_iterator_tag, int/*这里是解引用后的值类型，或者说，迭代器指向的值类型，根据需要换掉*/>{
    MyPtr(int x=0):val(x){}
    int val;
    //这里是你自定义函数的地方
    int f(){
        int x=val,ans=val,left=0;
        while(x>=3){
            left=x%3;
            ans+=x/3;
            x/=3;x+=left;
        }
        return ans;
    }
    int operator*(){
        return f();
    }
    MyPtr operator+(const int x){
        return MyPtr(val+x);
    }
    MyPtr& operator++(){
        ++val;
        return *this;
    }
    int operator-(const MyPtr& x)const{
        return val-x.val;
    }
    MyPtr& operator+=(const int x){
        val+=x;
        return *this;
    }
};
int main(){
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",lower_bound(MyPtr(0),MyPtr(n+1),n).val);
    }
    return 0;
}

（参考数据：输入 15084，输出 10047 ）

可以看到，我们继承了std::iterator<>，还声明自己是随机访问迭代器，返回值类型是int，然后实现了很多的运算符：+ 整数、 += 整数、前缀++ 、 - 自身、 * 解引用（计算结果）
……说实话，写完以后发现，好像太长了……
反正大家当看个热闹吧，如果觉得有用的同学可以学去。
（不过真的，和抄一个二分查找的函数相比，性价比太低了）

4、排序之后（2） —— 去重与离散化

当然，还有一类很重要、很常用的情况：

我要去掉重复元素
我不仅要去掉重复元素，还要保留第一个出现的

这没问题，STL里提供了一个函数，unique，能满足你的需要。

unique的参数为：unique(开始位置, 结束位置[, 自定义比较函数])
请注意，unique因为只关心2个元素是否一样，所以unique需要你实现

operator==，或者
自定义比较函数中，相等为true，不相等为false

这一点和sort、lower_bound等函数还是很不一样的。

还有就是，unique是有返回值，而且一般情况下都需要用到的。
unique的返回值是个迭代器，表示去重后剩下的元素的区间的结束位置。

举例：

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct People{
    People(int a=0,int b=0):id(a),val(b){}
    int val;
    int id;
    bool operator==(const People&b)const{
        return val==b.val;
    }
};
int main(){
    People a[8]={People(0,5),People(1,5),
                 People(2,6),People(3,6),People(4,6),
                 People(5,5),People(6,5),
                 People(7,4)};
    printf("unique item=%d\n",unique(a,a+8)-a);
    for_each(a,a+8,[](const People & x){printf("%d %d\n",x.id,x.val);}); 
    puts("");
    return 0;
}
/*
可能的输出：
unique item=4
0 5
2 6
5 5
7 4
4 6
5 5
6 5
7 4
*/

注意到：

unique对相邻的相等元素，只保留第一份，其他的都会丢弃。
但是unique不会记得前面出现过的，但是被其他元素隔开的相等元素的，4 5 4处理后仍然是4 5 4。
unique是不保证（被认为）重复了的元素的存在的，直接把后面不重复的元素，覆盖在前面的位置上，了事。

所以，unique的具体实现类似：

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return last;
  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first))
      *(++result)=*first;
  }
  return ++result;
}

所以，用unique的时候：

如果你需要确定整个数组只有1份某个东西，比如 4 5 4，我只要 4 5，请在用unique去重前排序。
unique只保留整段相同元素中的第一个，所以在排序时，如果要保留最先出现的元素，请使用stable_sort，或者排序时出现顺序也作为排序参数。

来2个例题吧：

例题A、CodeForces 631B Print Check

2种操作：整行涂某个颜色，或者整列涂某个颜色。
输出涂色完以后的图形情况。
其中：操作个数<=100000，行数、列数<=5000，行数*列数<=100000

暴力做法：直接开个数组，然后把所有操作，按顺序做下去，再输出——铁定超时。

小小的优化：
显然，对某行/某列，只有最后一次操作是有效的。
而行数+列数，最多也就不超过10000个（其实最多是5000+20个），那就意味着，我不需要都做。我只要找到每行/每列上的最后一次操作，然后按顺序执行那些操作就行了。这样需要的计算量10000*5000，5千万，CF上没问题。

在具体实现这个思路的时候：
搞一个结构体，记录
执行的顺序、操作类型、操作的行号/列号，还有要涂的颜色

读入所有操作后，按
1、操作类型
2、操作的行号/列号
3、执行顺序的倒序
依次排序。
（这样，相同的操作在一起了，然后按执行顺序倒序排，这样最后的操作在最前面）
然后用unique去重，最后再次排序，对剩下的操作，恢复正确的操作顺序，并依次执行，即可。

这题的正解是：
开2个数组，记录某一行/某一列最后一次涂色是什么时候，涂了什么颜色。
之后在输出的时候，每个位置上的颜色，就是相应的行和列上最迟涂的颜色了。
当然，这里是强行展示unique的用处了。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
struct OP{
    int idx,o,x,c;
    void get(){
        scanf("%d%d%d",&o,&x,&c);
    }
    bool operator==(const OP &b)const{
        return o==b.o&&x==b.x;
    }
    bool operator<(const OP &b)const{
        if(o!=b.o)return o<b.o;
        if(x!=b.x)return x<b.x;
        return idx>b.idx;
    }
}op[100005];
bool cmp(const OP &a,const OP &b){
    return a.idx<b.idx;
}
int n,m,k;
int arr[5005][5005];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++){
        op[i].idx=i;
        op[i].get();
    }
    sort(op,op+k);
    int last_idx=unique(op,op+k)-op;
    sort(op,op+last_idx,cmp);
    for(int pid=0;pid<last_idx;pid++){
        if(op[pid].o==1){
            int x=op[pid].x;
            int c=op[pid].c;
            for(int j=1;j<=m;j++)arr[x][j]=c;
        }else{
            int x=op[pid].x;
            int c=op[pid].c;
            for(int j=1;j<=n;j++)arr[j][x]=c;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf(j==m?"%d\n":"%d ",arr[i][j]);
        }
    }
    return 0;
}

例题B、hihocoder #1368 积水的城市2

地址：（https://hihocoder.com/problemset/problem/1368）或者（http://blog.csdn.net/fcxxzux/article/details/52435342）

具体思路就不在这里展开了，看我的博客（http://blog.csdn.net/fcxxzux/article/details/52435342），有具体的解释。

主要说明一下：如何用STL的那些算法函数（sort、unique、lower_bound）来实现这个离散化。

这种2维的网格图，x轴和y轴分开离散化即可。
我们下面以x轴的离散化为例。

1、把所有要参与离散化的数值，放入数组。
2、把这个数组用sort进行排序，用unique进行去重，并记录下最后不重复元素的数量

//第74~75行
sort(axis,axis+cnt);
cnt=unique(axis,axis+cnt)-axis;

这样其实我们就完成了离散化的预处理操作。

至于查询的时候：
某个元素的新的坐标，就是这个元素，在这个数组里的下标。
如果我们想知道某个老坐标值的新的坐标，那使用lower_bound进行二分查找即可。

//第85行
lower_bound(axis,axis+cnt,val)-axis

如果我们想知道某个新坐标值对应的原来的老坐标值，更简单了，直接数组下标访问即可。

//第80行
length[i+1]=orilength[axis[i]]-orilength[axis[i-1]];
//其中axis[i]和axis[i-1]取到的均是原来的坐标值。

使用STL算法函数sort、unique、lower_bound实现的离散化处理的本题，参考代码如下：

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int di[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct Point{
    int x,y;
    Point(){}
    Point(int a,int b):x(a),y(b){}
    Point go(int i){
        return Point(x+di[i][0],y+di[i][1]);
    }
    bool check(int n,int m){
        return x>=1&&y>=1&&x<=n&&y<=m;
    }
};
int Alength[1005];
int Blength[1005];
int K;
int cross[35][2];
int xaxis[105],xcnt=0;
int yaxis[105],ycnt=0;
ll dis[105][105];
bool walk[105][105];
int colLength[105];
int rowLength[105];
ll solve(int xa,int ya,int xb,int yb){
    int n=xcnt,m=ycnt;
    dis[xa][ya]=0;
    queue<Point> q;
    q.push(Point(xa,ya));
    while(!q.empty()){
        Point x=q.front();q.pop();
        ll disx=dis[x.x][x.y],disy;
        for(int i=0;i<4;++i){
            Point y=x.go(i);
            if(y.check(n,m)&&walk[y.x][y.y]){
                switch(i){
                    case 0:disy=disx+colLength[y.x+1];break;
                    case 1:disy=disx+colLength[y.x];break;
                    case 2:disy=disx+rowLength[y.y];break;
                    case 3:disy=disx+rowLength[y.y+1];break;
                }
                if(disy<dis[y.x][y.y]){
                    dis[y.x][y.y]=disy;
                    q.push(y);
                }
            }
        }
    }
    return dis[xb][yb]==(ll)INT_MAX*100000?-1:dis[xb][yb];
}
void addPoint(int v,int* axis,int& cnt){
    axis[cnt++]=v;
    axis[cnt++]=v+1;
}
void fix(int* axis,int& cnt,int n,int *orilength,int *length){
    axis[cnt++]=1;
    sort(axis,axis+cnt);
    cnt=unique(axis,axis+cnt)-axis;
    while(axis[cnt-1]>n) --cnt;
    fill(length,length+105,0);
    for(int i=1;i<cnt;i++){
        length[i+1]=orilength[axis[i]]-orilength[axis[i-1]];
    }
}
int getIndex(int* axis,int cnt,int val){
    return lower_bound(axis,axis+cnt,val)-axis+1;
}
inline void out(ll x) {
    if(x<0){
        putchar('-');
        out(-x);
        return;
    }
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;++i) scanf("%d",&Alength[i]),Alength[i]+=Alength[i-1];
    for(int i=2;i<=m;++i) scanf("%d",&Blength[i]),Blength[i]+=Blength[i-1];
    scanf("%d",&K);
    for(int i=0;i<K;++i) scanf("%d%d",&cross[i][0],&cross[i][1]);
    int Q,xa,ya,xb,yb;
    for(scanf("%d",&Q);Q--;){
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        xcnt=ycnt=0;
        addPoint(xa,xaxis,xcnt);
        addPoint(xb,xaxis,xcnt);
        addPoint(ya,yaxis,ycnt);
        addPoint(yb,yaxis,ycnt);
        for(int i=0;i<K;++i){
            addPoint(cross[i][0],xaxis,xcnt);
            addPoint(cross[i][1],yaxis,ycnt);
        }
        fix(xaxis,xcnt,n,Alength,colLength);
        fix(yaxis,ycnt,m,Blength,rowLength);
        fill(dis[0],dis[100]+101,(ll)INT_MAX*100000);
        memset(walk,1,sizeof(walk));
        for(int i=0;i<K;++i){
            int xid=getIndex(xaxis,xcnt,cross[i][0]);
            int yid=getIndex(yaxis,ycnt,cross[i][1]);
            walk[xid][yid]=0;
        }
        out(solve(getIndex(xaxis,xcnt,xa),getIndex(yaxis,ycnt,ya),
                    getIndex(xaxis,xcnt,xb),getIndex(yaxis,ycnt,yb)));
        puts("");
    }
    return 0;
}

5、还有那些随手就用的STL算法函数

下面还有一些我平时随手就用的STL算法函数，就都整理在这一节了：

fill(开始位置, 结束位置, 待填元素)
这货就是一个高级memset好吗？把[开始位置, 结束位置)中的所有元素全部用待填元素替换。——问题是，他不是按字节填充的！你每个元素是什么类型，他会整个元素整个元素的替换掉！
于是你可以：

#include <limits.h> //定义了INT_MAX和INT_MIN，int的最大值和最小值
int distance[100005];
//distance[0]到distance[n+1]之间的，全部用INT_MAX/2填充
fill(distance, distance+n+1, INT_MAX/2);

这样，你的初始值想要什么随你高兴！（最短路的时候，初始化每个点的距离，全部填上你需要的INF很有用！）

swap(元素a, 元素b)
这个倒是没什么好说的，就是交换元素a和元素b的值（用这个的话，不用写交换的中间变量了）

int a=5,b=6;
printf("%d %d\n",a,b); // 5 6
swap(a,b);
printf("%d %d\n",a,b); // 6 5

reverse(开始位置, 结束位置)
把整个范围内的元素反转。

int a[3]={1,2,3};
printf("%d %d %d\n",a[0],a[1],a[2]);
reverse(a,a+3);
printf("%d %d %d\n",a[0],a[1],a[2]); // 3 2 1

rotate(开始位置, 需要提到开始位置的位置 , 结束位置)
对整个范围内的元素进行循环移位。具体来说，将第二个参数指向的元素提到最前面的位置。
我们还是看例子比较好……

//需要C++11编译来执行输出语句
//当然你可以自己写这个输出a数组的语句
int a[5]={1,2,3,4,5};
for_each(a,a+5,[](int x){printf("%d ",x);});
puts("");
rotate(a,a+3,a+5);
for_each(a,a+5,[](int x){printf("%d ",x);}); // 4 5 1 2 3
puts("");

random_shuffle(开始位置, 结束位置)

将范围内的所有数随机打乱（或者说，随机洗牌）。

int a[10];
for (int i=1; i<10; ++i)a[i]=i;
random_shuffle(a, a+10);
//然后会被打乱，变成随机排列的数组，比如：
//3 4 1 6 0 8 9 2 7 5

next_permutation(开始位置, 结束位置)/prev_permutation(开始位置, 结束位置)

打表找规律时的神器。用于生成所有的排列。
对next_permutation，返回值为bool类型，如果当前传入的序列是字典序最大的排列，返回false，并变成字典序最小的排列，否则返回true，变成字典序下一大的排列。
而perv_permutation类似，只不过是尽量变成字典序恰好小1的排列。

 #include <iostream>     // std::cout
 #include <algorithm>    // std::next_permutation, std::sort
int main () {
  int myints[] = {1,2,3};
  std::sort (myints,myints+3);
  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );
  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  return 0;
}
/*
输出：
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3
*/

nth_element(开始位置, 分割位置, 结束位置[, 自定义比较函数])

功能：

字面意义上是，找到第n大（由第二个参数决定）的元素，放到相应位置上。
但是实际上还要强一些：不仅能找到第n大，还能让第n个位置前面的元素都比第n大还小，后面的元素都比第n大还大 (有可能有要灵活运用的地方哦~)，而且期望时间复杂度是 $O(n)$

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
    int a[9]={4,2,5,7,6,9,1,3,8};
    nth_element(a,a+2,a+9);
    for_each(a,a+9,[](int x){printf("%d ",x);}); 
    puts("");
    return 0;
}
/*
可能的输出：
1 2 3 6 4 5 9 7 8
*/

原理：

这实际上是快速排序中的划分阶段拎出来的一个应用，叫 快速选择算法。
一趟的快速排序（一层递归，或者叫，一次划分）中，我们会：
- 选择一个参考值
- 比参考值小的放前面，比参考值大的放后面

那么，在这里，我们随便选个参考值，完成一次划分，确定参考值的位置：
- 恰好是第n，不继续了，直接返回
- 小于预期的n，那么那个待查找的值在后面部分，只对后面部分继续处理
- 大于预期的n，那么那个待查找的值在前面部分，只对前面部分继续处理

所以其期望时间复杂度（一般认为，每次排除一半）为 $O(n+n/2+n/4+n/8+ \dots)=O(2n)=O(n)$

Bonus 02
如何正确的手写一个rotate和random_shuffle

不用STL，实现这两个函数的功能，是经典的企业面试题了。这里简单介绍一下这个解法。

rotate：
这里只介绍我自己唯一记得住的方法：

字符串旋转一定的位数，等价于：
把串A和串B组成的串AB变成串BA
定义符号： $A^r$ ，表示A的反串，比如 $X=abc$ ，那么 $X^r=cba$
先把AB整个反转，得到 $(AB)^r=B^rA^r$
——显然只需要再把B的部分和A的部分各自做一次翻转即可。
所以，这种方法是，三次翻转法。

有关rotate的更详细的讨论（包括其他的实现方法，以及各种实现方法的实际效率问题），请参见：http://www.cnblogs.com/flyinghearts/archive/2011/05/27/2060265.html

random_shuffle：
有一种非常有名的算法：Fisher–Yates shuffle
大致的实现思想：从前到后每一个位置枚举过去，这张牌随机和之后未确定位置的牌（包括这张牌自己）中，随机选择一张，放到这个位置上。
伪代码如下：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

更多有关随机洗牌的讨论，参见：
http://coolshell.cn/articles/8593.html
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle