算法 algorithm库

vector

list

string

deque

...

网址 www.cplusplus.com

struct和class没什么区别，struct默认public，class默认private

C++的struct可以写函数

引用

一个变量的引用相当于起了个别名

函数传参是使用引用可以避免拷贝，相当于直接操作实参

重载

模板template

减少冗余

竞赛过程，熟练运用C++自带的模板

头文件

<bits/stdc++.h>包含了所有的C++头文件，只写一个就可以

pair

pair是一个结构体，类似于模板。

pair<int,double> a;

这个情况下pair的int类数据叫first，double类的叫second。

pair<int,double> a(10,1.5);

或a = make_pair(3,6.5);

或a = {3 , 6.5};

pair重载了许多运算符，<,>,=;

<,>,=先比较first，若first相同再比较second;

利用pair<int , pair<int , int> > a;

可以构建三个都是int元素的结构体

tuple

比pair更多，可自行了解

algorithm

sort

用法：sort(首地址,尾地址的后一位);

如int a[5]={2,3,6,5,4};

sort(a,a+5);//郑旭输出

几个元素就+几

bool cmp(int a,int b)

{

return a>b;

}

sort ( a , a + 9 ,cmp)这样sort就是倒序

或者直接sort(a, a+9, greater())

sort第三个参数默认为less(),就是和great()相反

struct point { int x,y,z; }

bool cmp(const point &a, const point &b)

{

if(a.x != b.x) return a.x<b.x;

if(a.y != b.y) return a.y>b.y;

if(a.z != b.z) return a.z<b.z;

}

point p[3]={...}

sort(p,p+3,cmp)

这样可以直接按照一定规则对结构体进行排序

或者将小于号重载，就可以不写cmp

Lambda与匿名函数（了解）

sort(a, a+4, ->bool{return a<b;});

二分相关

lower_bound和upper_bound

传入一个区间（第一个位置和最后一个元素的下一个位置）和一个值

假定...

例：

int a[5] = {1,2,3,4,5}

//查找最后一个小于3的位置

cout << lower_bound(a, a+5, 3) - a<< endl; //输出为2

//"-a"是为了直观显示地址

//查找第一个大于3的位置

cout << upper_bound(a, a+5, 3) - a<< endl; //输出为4

unique

去重(相邻的重复元素，不相邻的不去重) //可以先sort，再unique

int a[7] = {1,2,3,3,3,4,4}

// {1,2,3,4}

unique(a,a+7)就去重了

int n=unique(a,a+7)-a;

这样n就是4，就是去重之后的新数组长度

revrese,min_element,max_element

用起来很爽

next_permutation

vector

vector是不定长数组容器，就相当于是动态数组，且比new好用，可以变长

vector a; //长度为0的数组；

vector a(10,3); //a={3,3,3,3,3,3,3...}

可以像数组一样用a[i];

然后用for(int =0;....)输出

变长的话可以直接用a.size()获得长度

a.push_back(5); //往a末尾增加元素5，a={3,3,3,3,3,3,3,3,3,3,5}

a.pop_back(); //删除最后一个元素

这两个时间复杂度都是O(1);

vector的遍历

实际上是迭代器

从begin到end，支持++，--自增，可以用->，*获取内容

for(vector::iterator i = a. begin(); i != a.end(); ++i)

{ cout<<*i<<" ";

}

或者

begin(),end()左闭右开

for(auto i = a. begin(); i != a.end(); ++i)

{ cout<<*i<<" ";

}

排序可以直接

sort(a.begin(), a.end());

for循环简洁：

for(auto &i : a)

{

cout<< i <<" ";

}

vector

a.insert(a.begin()+2, 0);//在a的第二个位置插入元素0

a.erase(a.begin + 2);//删除第二个元素

a.erase(区间)

list

链表容器。

老师说不好用，自己写也挺好；

deque

功能可以替代vector，但效率更优秀

string

string s;

s.c_str();//转换成char数组

字符串最好还是直接用 cin 输入

字符串比较按照“字典序”进行比较（？）

字符串 s += t; //在s后面直接加伤t字符串

s.substr(1,2);//截取第1-2个字符

s.substr(2);//从第二个字符往后截取；

关联容器

set s;

保证元素唯一性，即相同元素只能存在一个，看起来也类似于一个数组。

像是一个集合，元素无序但是默认按照从小到大；

遍历也是迭代器

for(auto i = s.begin(); i != s.end(); i++){

cout<< *i <<" ";

}

s.find(x) 查找元素

s.count(x) 计数x元素 //find，count时间复杂度都是log n

map

map<string, int> mp;

//键？ps：我觉得应该叫关键字

mp["sdu"] = 1;

mp["tpp"] = 2 ;

cout<< mp["sdu"] ;

可以通过迭代器遍历

for( auto i = mp.begin(); i != mp.end(); i++){

cout<< i->first <<" "<< i->second <<endl;

}

//关键字是唯一的

mp.erase("tpp"); //根据关键字删除

size()得到长度

empty()判断是否为空

也同样可以用find("关键字")查找元素 //find返回的都是位置，一般不能直接用

常量map

map和set底部都是红黑树

multimap/multiset

容器适配器

stack

stack也是有自带的？！

stack其实就是之前讲到的deque

queue队列

priority_queue是堆，默认大根堆

总结