二分查找函数

二分查找适用于有序序列。

lower_bound()函数

    返回第一次出现大于等于那个要查找的数的地址

upper_bound()函数

    返回的是第一个比要查找的数大的数的地址  （注意  这里是大于  不包括等于）

//返回一个迭代器，表示第一个大于等于val的元素，如果不存在这样的元素，则返回end。
lower_bound(beg, end, val);

lower_bound(beg, end, val, comp);//自定义重载运算符


//返回一个迭代器，表示第一个大于val的元素，如果不存在这样的元素，则返回end。
upper_bound(beg, end, val);

upper_bound(beg, end, val, comp);//自定义重载运算符

注意 返回的是一个迭代器  也就是指针  所以  我们一般这样写

 

 

去重函数

unique()

unique()是C++标准库函数里面的函数，其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序

原理 

它并没有将重复的元素删除，而是把重复的元素放到数组的最后面藏起来了 返回给你一个指向不重复序列的最后一个数字的迭代器，所以要用返回的迭代器减去a的首地址  就得到了 去重后的数组长度

使用方法：对于长度为n数组a，unique(a,a+n) - a   返回的是去重后的数组长度

 

全排列的函数

next_permutation（start,end），和prev_permutation（start,end）。

这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1.

 

对于next_permutation函数，其函数原型为：

     #include <algorithm>

     bool next_permutation(iterator start,iterator end)

当当前序列不存在下一个排列时，函数返回false，否则返回true

看具体用法：


例题  51nod1384http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1384

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    char ch[50];
    scanf("%s",ch);
    int l=strlen(ch);
    sort(ch,ch+strlen(ch));
    do{
        puts(ch);
    }while(next_permutation(ch,ch+l));
    return 0;
}