万能的STL

一、nth_element()函数

一般格式

nth_element(begin,nth,end+1,compare);

假设数组a[]的第1~m个位置有数，现在要求第n大
代码如下
一定要注意，前三个参数全是地址，第三个参数是要排序的数值地址的下一位，也就是左闭右开区间进行排序

nth_element(a+1,a+n,a+m+1,cmp)

也可以不写cmp,不写的时候默认升序排列，有需要的话，可以手写cmp函数让他从大到小排列找第n小的数值
实现原理
内部实现就是一个快速排序，和sort不同的是，sort的时间复杂度是O(n*logn)，并且sort排完之后完全有序，而nth-element的时间复杂度是O(n)，排完之后第n个数的左边都小于等于它，右边的都大于等于它
示例
我们可以看到，对于这个例子我们求的是9个数中第4小的，和9个数中第4大的，还有用sort进行了非降序和非升序排列。很明显的可以看出nth_element函数和sort的区别

二、sort()函数

一般格式

sort(begin,end+1,compare)

假设数组a[]的第1~m个位置有数，现在要求非降序或非升序排列
一定要注意，前两个参数全是地址，第二个参数是要排序的数值地址的下一位，也就是左闭右开区间进行排序

sort(a+1,a+m+1);//默认非降序
sort(a+1,a+m+1,cmp);//自写cmp函数为非升序，那么就是非升序排列了

示例如下

三、low_bound()和upper_bound()函数

一般格式

low_bound(begin,end+1,num);
upper_bound(begin,end+1,num);
low_bound(begin,end+1,num,greater<type>());//type根据需要改成适当类型
upper_bound(begin,end+1,num,greater<type>());

作用
在从小到大（允许有相同值）排好序的数组中
low_bound(begin,end+1,num);是在区间【begin,end】通过二分查找找到最后一个小于num的数值的地址
upper_bound(begin,end+1,num);是在区间【begin,end】通过二分查找找到第一个大于num的数值的地址
在从大到小（允许有相同值）排好序的数组中
low_bound(begin,end+1,num,greater());是在区间【begin,end】通过二分查找找到最后一个小于num的数值的地址
upper_bound(begin,end+1,num,greater());是在区间【begin,end】通过二分查找找到第一个大于num的数值的地址
所以他们返回的都是地址，要想得到下标，需要再减去数组首地址
示例
我这里下标是从1开始的，所以可以直接对应了。示例所求的是与4有关的各个位置。简单来说就是我用4去替换排好序的数组中的数值，并保持原有的有序性，那我能替换的下标最小和最大是多少。比如第一个红线的意思是，我用4去换数组下标为5的数值4之后，还可以保持原有的有序性，这也是第一个我可以用4替换并保持有序性的数值。第二个红线的意思是，我用4去替换属猪下标为6的数组5之后还可以保持有序性，这也是最后一个我可以用4替换并保持有序性的数值。第三个第四个红线同理

代码

#include<bits/stdc++.h>
using namespace std;
int a[100];
bool cmp(int a,int b) {return a>b;}//非升序排列（可以简单理解为相等数值不影响正确性的降序排列）
int main()
{
    int m;
    cin>>m;
    for(int i=1;i<=m;++i) cin>>a[i];
    sort(a+1,a+m+1);//从小到大排序
    for(int i=1;i<=m;++i) cout<<a[i]<<" ";//排好序输出
    cout<<endl<<endl;
    int x;
    x=lower_bound(a+1,a+m+1,4)-a;
    cout<<x<<endl;
    x=upper_bound(a+1,a+m+1,4)-a;
    cout<<x<<endl;
    sort(a+1,a+m+1,cmp);//从大到小排序
    for(int i=1;i<=m;++i) cout<<a[i]<<" ";//排好序输出
    cout<<endl<<endl;
    x=lower_bound(a+1,a+m+1,4,greater<int>())-a;
    cout<<x<<endl;
    x=upper_bound(a+1,a+m+1,4,greater<int>())-a;
    cout<<x<<endl;
    cout<<endl<<endl;
    cout<<endl;
    system("pause");
    return 0;
}

五、next_permutation()和prev_permutation()函数

一般格式

next_permutation(arr, arr+size);//求下一个排列组合
prev_permutation(arr, arr+size);//求上一个排列组合

next_permutation(arr, arr+size);求下一个排列组合
a.函数模板：next_permutation(arr, arr+size);
b.参数说明：
　　arr： 数组名
　　size：数组元素个数
c.函数功能： 返回值为bool类型，当当前序列不存在下一个排列时，函数返回false，否则返回true，排列好的数在数组中存储

d.注意：在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。
比如，如果数组num初始化为2,3,1，那么输出就变为了：{2 3 1} {3 1 2} {3 2 1}

prev_permutation：求上一个排列组合

a.函数模板：prev_permutation(arr, arr+size);
b.参数说明：
　　arr： 数组名
　　size：数组元素个数
c.函数功能： 返回值为bool类型，当当前序列不存在上一个排列时，函数返回false，否则返回true
d.注意：在使用前需要对欲排列数组按降序排序，否则只能找出该序列之后的全排列数。
示例

代码

#include<bits/stdc++.h>
using namespace std;
int a[100];
bool cmp(int a,int b) {return a>b;}//非升序排列（可以简单理解为相等数值不影响正确性的降序排列）
int main()
{
    int m;
    cin>>m;
    for(int i=1;i<=m;++i) cin>>a[i];
    sort(a+1,a+m+1);//从小到大排序
    for(int i=1;i<=m;++i) cout<<a[i]<<" ";//排好序输出
    cout<<endl<<endl;
    do
   {
      for(int i=1;i<=m;++i) cout<<a[i]<<" ";
      cout<<endl;
   } while (next_permutation(a+1,a+m+1));
   cout<<endl;
    sort(a+1,a+m+1,cmp);//从大到小排序
    for(int i=1;i<=m;++i) cout<<a[i]<<" ";//排好序输出
    cout<<endl<<endl;
    do
   {
      for(int i=1;i<=m;++i) cout<<a[i]<<" ";
      cout<<endl;
   } while (prev_permutation(a+1,a+m+1));
    cout<<endl<<endl;
    cout<<endl;
    system("pause");
    return 0;
}

六、最大公约数gcd和最小公倍数lcm

之前写过，链接如下
最大公约数gcd和最小公倍数lcm
简单来说就是

七、数值操作

对浮点型进行四舍五入double round(double d);
统计数字位数 count = (int)log10(number) + 1;//统计一共几位
对数值a取绝对值 double b=fabs(a);或者double b=abs(a);

对数操作

以下返回值默认为double
以10为底   log10(100)==2;    以2为底  	  		   log2(8)==3；
以e为底 log(10)=2.多    以m为底，求log n   double a=log(n)/log(m);

保留小数位数 setprecision(n)

返回二进制的最低位 int lowbit(int x){return x&(-x);}
const int maxn=(int)2e4+1000;
int 型的最大值 int min_p = INT_MAX;
π的值 const double pi=acos(-1);
e的x次方 const double e=exp(x) （x为double型）
const int mod=(int)1e9+7;
const double eps=1e-10;
初始化无穷大 const int inf=0x3f3f3f3f;
初始化负无穷大 const int inf=0xcfcfcfcf
初始化无穷大 const ll linf = 0x3f3f3f3f3f3f3f3f;

八、字符判断

以下全部返回值为int ，参数为int型
isalnum判断一个字符是否是字母或数字。
isalpha检测一个字符是否是字母。
isblank检测一个字符是否是空白符。包括空格和\t
isspace检测一个字符是否是空白符。包括空格,\t,\n,\f换页,\r回车,\v垂直制表符
isdigit判断一个字符是否是十进制数字。(0－9)
islower判断一个字符是否是小写字母。
isupper判断一个字符是否是大写字母。
ispunct判断一个字符是否是标点符号。
tolower将大写字母转换为小写字母。
toupper将小写字母转换为大写字母。