分类
Level3

头文件algorithm

algorithm 包含的函数有很多,下面只挑很重要的函数介绍。

reverse() 反转排序指定范围中的元素

char nzBuf[50] = "Hello world! Wu Xie Tong Xie";
reverse(nzBuf,nzBuf+strlen(nzBuf)); //字符数组从后往前排序了

sort() 排序,但默认参数下的排序是升序,而添加一个返回bool类型的函数如下cmp才可以实现降序,函数名或形参名可以任意更换,主要记住函数完成的功能室返回前一个参数大于后一个参数的判断值。而小于则是升序的排列

bool cmp(int a,int b){
    return a>b;  //大的排前面
}
int nData[10] = {1,3,4,2,5,8,1,2,10,2};
sort(nData,nData+10);    //升序排列
sort(nData,nData+10,cmp);//降序排列

next_permutation()/prev_permutation() 两者的功能返回分别为,给定范围中的元素组成的下一个按字典序的排列,以及返回给定范围中的元素组成的上一个按字典序的排列。由上面的性质,我们可以根据数据字典排序做升序或者降序的全排列。如下:

int arr[N] = {1,2,3,4}; //一定注意该处是最小排列情况,下面会详解原因
do{
     for(int i=0; i < N; i++)
          printf("%d ",arr[i]);
     putchar('\n');
}  while(next_permutation(arr,arr+N));  //升序

函数输入之所以要求必须是一个升序的排列,原因在于函数运行一次对输入的数组进行移动排列一次后,在函数退出前判断移动后的数组是否升序,如果升序则函数返回布尔变量false,否则返回true。这样当你输入的是一个升序的排列后,每运行一次函数就对数组进行一次移动得到一个新的排列,函数对数组的移动排列采用递归方式。当所有排列方式都遍历一遍后函数最后一次输出的又是一个升序的排列,也就是和你最先输入的数组一样的排列。
所以要做到函数实现字典的全排列,先要将数据进行排序,初始状态一定要是数据内部是升序的情况,才能依次迭代而打印出所有的全排列的结果。
同样的道理,降序排序则先让数据初始状态属于降序的给过:

int arr[N] = {4,3,2,1};
do{
    for(int i=0; i < N; i++)
        printf("%d ",arr[i]);
    putchar('\n');
} while(prev_permutation(arr,arr+N));  //降序

unique() 删除指定范围中的所有连续重复元素,仅仅留下每组等值元素中的第一个元素。注意两点,第一点,该函数仅是处理元素连续重复的情况,而不是整个指定范围中重复的元素。所以如果想移除整个整个范围重复元素,先进行排序然后再调用该函数。第二点,unique并不是真正的把重复的元素删除,其实是,该函数把重复的元素移到后面去了,然后依然保存到了原数组中。函数返回去重后最后一个元素的地址。

string str           = "abcdddddbccccd";
string::iterator rel = unique(str.begin(),str.end());  //rel=“dbccccd”,str =“abcdbcdbccccd”

二分查找函数
binary_search(a+begin, a+end, x, cmp);
二分查找 函数含义:在a数组的下标为[begin, end)区间内,按照cmp的排序规则,找元素x; 找到返回true,找不到返回false。
注意点:
(1)查找区间是左闭右开的:[begin, end),不包含结束位置;
(2)排序规则cmp不是必须的,但查找时的排序规则,必须和排序的规则是一致的;
(3)等于的含义:a等于b等价于a在b的前面,b在a的前面都不成立。

T* lower_bound(a+begin, a+end, x, cmp);
二分査找左边界 函数含义:在a数组的下标为[begin, end)区间内,按照cmp的排序规则,找元素x的 左边界(第一个 >= 元素的x的位置),返回位置指针;
注意点:
(1)基本注意点同binary_search;
(2)此处返回的不是下标的值,而是返回指针:T* p;
(3)如果找不到符合条件的元素位置,指向下标为end的元素位置;

T* upper_bound(a+begin, a+end, x, cmp);
二分查找右边界 函数含义:在a数组的下标为[begin, end)区间内,按照cmp的排序规则,找元素x的 右边界(第一个 > 元素的x的位置),返回位置指针;
注意点:同 lower_bound;