算法竞赛常用库函数整理

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

• 前言
• 一、#include < algorithm>头文件
• • sort排序
  • next_permutation()全排列
  • swap交换函数
  • reverse 翻转
  • unique 去重
  • max与min
  • lower_bound与upper_bound
• 二、#include< ctype.h>头文件
• • isalnum
  • isalpha
  • isdigit
  • islower
  • isupper
  • tolower
  • toupper
• 三、#include< iomanip>头文件
• • fixed
  • setprecision()
  • setw()
  • setfill
• 四、#include< cmath>
• 五、 #include< cstring>头文件
• • memset函数
• 六、include < numeric>头文件
• • iota函数
• 七、#include < ctime>头文件
• • random_shuffle 随机打乱
• 最后

学了半年算法以来总结的一些c/c++算法竞赛常用函数笔记
没有把每个函数讲的很详细，但是很实用

如果还有漏掉的函数，欢迎补充
其他一些属于STL的函数写在了STL专栏欢迎浏览
如果有错误，欢迎提出

另外，如果知道函数如何使用，但不知道属于哪个头文件
可以用#include 万能头文件（编译会慢一点点）

sort函数有三个参数：

（1）第一个是要排序的数组的起始地址。

（2）第二个是结束的地址（最后一位要排序的地址）

（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。

函数原型：sort(起始地址, 末尾地址, cmp),其中cmp是可以自己定义的函数名.

例如

#include
#include
using namespace std;
int main()
{
	int a[10]= {7,6,12,8,5,15,17,4,1,0};
	for(int i=0; i<10; i++)
		cout< 
输出
 7 6 12 8 5 15 17 4 1 0
 0 1 4 5 6 7 8 12 15 17
 
sort时间复杂度为n*log 2(n)，执行效率较高！
 
实现原理：sort并不是简单的快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和推排序。系统会根据你的数据形式和数据量自动选择合适的排序方法，这并不是说它每次排序只选择一种方法，它是在一次完整排序中不同的情况选用不同方法，比如给一个数据量较大的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，他会选择推排序。
 
默认从小到大排序
 如果需要从大到小排序，那么可以加个greater() 或者自写cmp 函数
 
sort(A,A+100,greater());//降序排列
sort(A,A+100,less());//升序排列
 
自定义比较函数
 
数组排列
 
int A[100];
bool cmp1(int a,int b)//int为数组数据类型
{
    return a>b;//降序排列
    //return a 
结构体排序
 
Student Stu[100];
bool cmp2(Student a,Student b)
{
    return a.id>b.id;//按照学号降序排列
    //return a.id 
如果想要先按x从大到小排序(即一级排序)，但当x相等的情况下，按照y的大小从小到大排序(即二级排序)。
 那么cmp的写法是:
 
bool cmp(student a,student b)
{
	if(a.x==b.x)//x值相等时按y从小到大排 
	{
		return a.yb.x;//按x值从大到小对结构体排序 
}
或
bool cmp(student a,student b)
{
	if(a.x != b.x)//x值不相等时按x从大到小排 
    return a.x>b.x;
	else 
	return a.y 
想要按照score的大小从大到小排序，如果score相同按照名字的字典序从小到大排序：
 
bool cmp(node x1,node x2)
{
    if(x1.score==x2.score)
        return x1.namex2.score; 
}
 
将string的长度从大到小输出
 
bool cmp(string a,string b)
{
return a.length()>b.length();
}
 
在STL标准容器中，只有vector、string、deque是可以使用sort的。
 这是因为像set、map这种容器是用红黑树实现的(了解即可)，元素本身有序，故不允许使用sort排序。
 
#include 
#include 
#include 
using namespace std;
int main()
{
    vectora({1,3,2,5,2});
    sort(a.begin(),a.end(),greater());
    for(auto x:a) cout << x <<' ';
    return 0;
}
 
next_permutation()全排列 
介绍：next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列，直到整个序列为降序为止。
 
使用方法：next_permutation(数组头地址，数组尾地址);
 若下一个排列存在，则返回真，如果不存在则返回假
 若求上一个排列，则用prev _permutation
 
#include
#include//注意添加头文件
using namespace std;

int q[10];//1 ~ 9最多9个数字 
int n;
int main()
{
    cin>>n;
    //输入数字 1 ~ n
    for(int i = 0 ; i
        //输出更大的排列
        for(int i = 0 ; i 
输出
 3
 1 2 3
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1
 
next_permutation 自定义比较函数
 
//题目中要求的字典序是
#include //poj 1256 Anagram
#include
#include
using namespace std;
int cmp(char a,char b) 
{
   if(tolower(a)!=tolower(b))//tolower 是将大写字母转化为小写字母.
       return tolower(a)
    char ch[20];
    int n;
    cin>>n;
    while(n--)
{
    scanf("%s",ch);
    sort(ch,ch+strlen(ch),cmp);
 do
{
    printf("%sn",ch);
}while(next_permutation(ch,ch+strlen(ch),cmp));
}
 return 0;
}
 
输入
 1
 adv
 输出
 adv
 avd
 dav
 dva
 vad
 vda
 
char 类型的next_permutation
 
#include 
#include 
#include 
using namespace std;
int main()
{
   char ch[205];
   cin >> ch;
   sort(ch, ch + strlen(ch) );
//该语句对输入的数组进行字典升序排序。如输入9874563102 cout<
     cout<< ch << endl;
}while(next_permutation(first, last));
   return 0;
}
//这样就不必事先知道ch的大小了，是把整个ch字符串全都进行排序
//若采用 while(next_permutation(ch,ch+5)); 如果只输入1562，就会产生错误，因为ch中第五个元素指向未知
//若要整个字符串进行排序，参数5指的是数组的长度，不含结束符

 
string 类型的next_permutation
 
#include 
#include 
#include 
using namespace std;

int main()
{
   string line;
   while(cin>>line&&line!="#")
  {
   sort(line.begin(),line.end());//全排列
   cout< 
swap交换函数 
swap(a,b);
 交换a，b的值
 
#include 
#include 
using namespace std;
int main( )
{
    int a = 10;
    int b = 5;
  swap(a,b);
    cout << "a = " << a << ", b = " << b << endl;
}
 
输出
 a = 5, b = 10
 
reverse 翻转 
 reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值
 
函数原型，该函数等价于通过调用iter_swap来交换元素位置
 
template 
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
    while ((first!=last)&&(first!=--last))
    {
        std::iter_swap (first,last);
        ++first;
    }
 
例如：
 
#include 
#include 
#include 
using namespace std;
int main()
{
    vectora({1,2,3,4,5});
    reverse(a.begin(),a.end());
    for(auto x:a) cout << x <<' ';
    return 0;
}
 
输出
 5 4 3 2 1
 
unique 去重 
需要保证相同元素在一起才行，个人建议先sort
 m=unique(begin,end)-begin //m为不重复的个数
 或者a. erase(unique(begin,end),end)
 
例如：
 
#include 
#include 
#include 
using namespace std;
int main()
{
    vectora({1,2,2,3,3,4,4,4});//vector赋初值时不要等号
    int m=unique(a.begin(),a.end())-a.begin();
    cout << m < 
输出
 4
 1 2 3 4
 
max与min 
max(x,y)
 返回两个中较小的一个
 min(x,y)
 返回两个中较大的一个
 
#include 
#include 
using namespace std;
int main()
{
	int a=max(2,5);
	int b=min(4,3);
	cout< 
lower_bound与upper_bound 
头文件： #include< algorithm >
 集成了二分的函数
 
 
 
函数lower_bound()
 //lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。
 功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置.
 注意：如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！
 
 
 
 
函数upper_bound()
 //upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。
 功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置
 注意：返回查找元素的最后一个可安插位置，也就是“元素值>查找值”的第一个元素的位置。同样，如果val大于数组中全部元素，返回的是last。(注意：数组下标越界)
 
 
lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。
 upper_bound(val): 返回容器中第一个值【大于】
 
//当然这个区间内的数应当是有序的。这两个函数返回值都是地址，所以说使用方法如下：

int pos=lower_bound(a+1,a+1+n,5)-a; 
cout<())-a; 
cout<
    vector t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    t.push_back(4);
    t.push_back(6);
    t.push_back(7);
    t.push_back(8);


    int low=lower_bound(t.begin(),t.end(),5)-t.begin();//end()返回的却是末尾元素再下一个元素的迭代器
    int upp=upper_bound(t.begin(),t.end(),5)-t.begin();
    cout< 
#include

using namespace std;

int main(){
    vector vec = {1,1,2,3,3,4,4,5};
    auto pos1 = lower_bound(vec.begin(), vec.end(), 2) - vec.begin();
    auto pos2 = upper_bound(vec.begin(), vec.end(), 2) - vec.begin();
    auto flag = binary_search(vec.begin(), vec.end(), 2);
    cout << "第一个大于等于2的位置是" << pos1 << endl;
    cout << "第一个大于2的位置是" << pos2 << endl;
    cout << "查找2返回的结果:" << flag << endl;
    return 0;
}
 
输出
 第一个大于等于2的位置是2
 第一个大于2的位置是3
 查找2返回的结果:1
 
二、#include< ctype.h>头文件 
包含的常用函数如下：
 
isalnum 
函数原型: int isalnum(int ch);

函数功能: 检查ch是否是字母或数字

函数返回: 是字母或数字返回非0,否则返回0//字母返回4，数字返回2
 
isalpha 
函数原型: int isalpha(char ch);

函数功能: 检查ch是否是字母.

函数返回: 是字母返回非0（在vs2015中为2） ,否则返回 0.//字母返回2
 
isdigit 
函数原型: int isdigit(char ch);

函数功能: 检查ch是否是数字(0-9)//返回1

函数返回: 是返回非0,否则返回0
 
islower 
函数原型: int islower(int ch);

函数功能: 检查ch是否小写字母(a-z)

函数返回: 是返回非0,否则返回0//返回2
 
isupper 
函数原型: int isupper(int ch);

函数功能: 检查ch是否是大写字母(A-Z)

函数返回: 是返回非0,否则返回0//返回1
 
tolower 
函数原型: int tolower(int ch);

函数功能: 将ch字符转换为小写字母

函数返回: 返回ch所代表的字符的小写字母
 
toupper 
函数原型: int toupper(int ch);

函数功能: 将ch字符转换成大写字母

函数返回: 与ch相应的大写字母    
 
三、#include< iomanip>头文件 
iomanip在c++程序里面经常见到的头文件#include < iomanip>，io代表输入输出，manip是manipulator(操纵器)的缩写(在c++上只能通过输入缩写才有效)
 
包含的主要函数如下：
 dec设置整数为十进制
 hex设置整数为十六进制
 oct设置整数为八进制
 
int n;
cout<<___< 
fixed 
那么如何消除浮点数的科学计数法呢？
 答案是用fixed。
 
//类型一：整数位很多
double x=12345678;
//类型二：小数位很多，有效小数位少
double y=0.00001234;

cout< 
setprecision() 
setprecision( n ) 设显示有效数字为n位
 
fixed与setprecision(n)连用可以控制小数点后的位数，现在就可以理解因为那是定点数记数法。
 
如果没有fixed的话，就是浮点数记数法了，那么它控制的应该就是有效数字的位数（包括小数点前的）！！！！！
 
大家应该很清楚了，但还是举个例子吧。
 
double x = 0.123456;
double y = 1.123456;

cout  << x << endl;
cout << y << endl;

//0.123456
//1.12346
 
setw() 
setw( n ) 设域宽为n个字符
 
//若想用setw(int n)呢，要加头文件 < iomanip > [io+manipulator的意思]
//其控制后面输出的长度，默认右对齐，输出内容长度不够用空格补齐，输出内容长度超过则正常输出。
//注：1. setw()只对后面紧跟的输出有限制。
//    2. 标点符号占一位！
	double x = 0.1;
	double y = 0.123456;

	cout  < 
setfill 
setfill(char c) 用法 : 就是在预设宽度中如果已存在没用完的宽度大小，则用设置的字符c填充
 
cout< 
setw只作用于紧随其后的部分，例如
 
cout<')<123456
 这里setfill('')<**123,456作为另一部分随后输出。
 
四、#include< cmath> 
头文件cmath或math.h中包含的常用数学函数
 
1.开平方
 
double sqrt(double x);
 
2.求常数e的x次方
 
double exp(double x);
 
3.求x的y次方
 
double pow(double x, double y);
 
4.求对数ln(x)
 
double log(double x);
 
求对数lg(x)
 
double log10(double x);
 
其他用换底公式
 
5.求x绝对值
 
int abs(x);

long int abs(long int x);

double fabs(double x);
 
6.三角函数
 
   求正弦 

double sin(double x);

   求余弦

double cos(double x);

   求正切

double tan(double x);

   反正切

double atan(double x);
 
7.取整函数
 
   向上取整

double ceil(double x);

   向下取整

double floor(double x);
 
8.产生随机数 0~32767
 
函数原型：int rand(void);

功能和返回值：返回一个 0 ~ RAND_MAX 的随机数 
 
五、 #include< cstring>头文件 
其他相关函数点这里
 
memset函数 
// 头文件
#include//C语言
#include//c++
当初始化一个字节单位的数组时，可以用memset把每个数组单元初始化成任何你想要的值，比如，
int a[MAXN];
memset(a, 0, sizeof(a));//数组中的所有元素全为0
memset(a, -1, sizeof(a));//数组中的所有元素全为-1
memset(a, 127, sizeof(a));//数组中的所有元素全为2139062143（可以将其视为INF）
memset(a,0x3f,sizeof(a));//数组中的所有元素全为0x3f3f（可以将其视为INF）
 
六、include < numeric>头文件 
iota函数 
iota函数对一个范围数据进行赋值：
 
//用法
// iota example
#include      // std::cout
#include       // std::iota    头文件
using namespace std;
int main () {
  int numbers[10];

  iota (numbers,numbers+10,100);

  cout << "numbers:";
  for (int& i:numbers) cout << ' ' << i;
 cout< 
//输出
numbers: 100 101 102 103 104 105 106 107 108 109
 
相当于
 
//iota(p,p+10010,0);
	for(int i=1;i<=10000;i++)
    {
        p[i]=i;
    }
 
七、#include < ctime>头文件 
random_shuffle 随机打乱 
注：可通过更改随机种子，让随机数变得不同
 
include 
srand(time(0));//随机种子
 
输出10000个随机数
 
#include 
#include 
using namespace std;
int main()
{
	srand(time(0));//time函数返回的是自UTC时间1970年1月1日0点以来经过的秒数。
	for(int i=0;i<10000;i++)
	{
		cout< 
#include 
#include 
#include 
using namespace std;
int main()
{
	multisets;
	srand(time(0));
	for(int i=0;i<10000;i++)
	{
	//	cout< 
在我这个时间戳输出：
 994
 973
 1005
 986
 979
 1041
 1023
 940
 1054
 1005
 
 
最后 
莫言真理无穷尽，寸进自有寸进欢