1.容器
1.1 vector数组
vector<类型>变量名(长度, 初值)
头文件#include<vector>
vector<int>abc(10,1) //长度为10,初值为1的整形数组
//vector的数据储存在堆空间中,不会爆栈
1.2 获取长度
.size() : 获取当前vector的长度
abc.size() //获取数组abc的长度
//常与for结合,用于遍历数组
1.3 清空
.clear() : 清空vector
abc.clear() //清空数组abc内的元素
1.4 判空
.empty() : 查询vector内有没有元素,返回布尔变量(true/flase)
abc.empty() //查询数组abc是否为空
//常与if结合,作为判定条件
1.5 尾接 & 尾删
.push_back(元素) :在vector尾部接一个元素,数组长度 +1
.pop_back() :删除vector尾部的一个元素,数组长度 −1
abc.push_back(1) //在数组abc尾部加上元素1
abc.pop_back() //删除数组abc尾部的一个元素
1.6 front & back
.front() : 返回vector的第一个元素
.back() : 返回vector的最后一个元素//等同于stack里的top
总结 : 由于数组的大小必须是一个常量表达式,当题目要求数组的长度非常大时
(如n=10000),a[10010]浪费内存会导致MLE,这时就要用vector<int>(n+10)
2.1 栈stack
头文件#include<stack>
stack<int>abc; //构建栈stack
abc.push(1); //进栈(添加)
abc.push(2);
abc.top(); //取栈顶,这里是2,因为栈是先进后出
abc.pop(); //出栈(删除)
abc.size(); //获取长度
abc.empty(); //查询栈stack能有没有元素
注意
1>栈stack没有clear()
总结 : 不能直接访问内部元素,剩下的和vector差不多
3.1 队列queue
头文件#include<queue>
注意
1>队列queuq没有clear()
总结 : 先进先出的栈,剩下的和vector差不多
4.1 优先队列priority_queue
优先队列是在正常队列的基础上加了优先级,每次从优先队列中取出的元素都是队列中优先级最大的一个
priority_queue<类型,容器,比较器>变量名 //容器默认为vector,比较器默认为less
头文件#include<queue>
优先级
大顶堆 : priority_queue<int>abc //从大到小排序
小顶堆 : priority_queue<int,vector<int>,greater<int>>abc //从小到大排序
abc.push(元素) //进堆
abc.pop() //堆顶元素出堆
abc.top() //访问堆顶元素
注意
1>优先队列只能通过.top()访问堆顶元素
2>堆中所有元素不可修改
3>优先队列没有clear()
4.1 集合set
set<类型,比较器>变量名 //set中的元素不重复且有序
//比较器默认为less
头文件#include<set>
优先级
set<int>abc //从小到大
set<int,greater<int>>abc //从大到小
abc.insert(1) //插入元素1
abc.erase(2) //删除元素2
abc.find(1) //查找元素1
abc.count(1) //返回元素1的个数
abc.begin() //返回第一个元素的地址
abc.end() //返回最后一个元素再后面一个位置的地址
适用情形
元素去重 : {1,2,2,3} → {1,2,3}
维护顺序 : {3,1,2} → {1,2,3}
set只能用迭代器进行遍历
for (set<int>::iterator it = abc.begin(); it != abc.end(); ++it)
cout << *it << endl;
注意
1>set不能用下标进行索引 //如abc[1]是错误的
2>set的迭代器取到的元素是只读的,不可修改其值
5.1 映射map
头文件#include<map>
类似于数学里的映射函数
map<键类型,值类型,比较器>变量名
map<int, int> abc // int->int 的映射(键从小到大)
map<int, int, greater<int>> abc // int->int 的映射(键从大到小)
使用
abc[1]=2 //访问不存在的map变量,其初值默认为0
abc.find(2) //查找键2
abc.earse(2) //删除键2及其对应的值
abc.count(2) //返回键2的个数
可使用迭代器进行遍历
for (map<int, int>::iterator it = abc.begin(); it != abc.end(); ++it)
cout << it->first << ' ' << it->second << endl;
注意
1>键和值是一一对应的关系,一个键仅可以在映射中出现一次
2>键是有顺序的(默认从小到大)
6.1 二元组 pair
头文件#include<utility>
pair<第一个值类型, 第二个值类型>abc
赋值 : pair<int,int>abc={1,2}
取值
取第一个值 :abc.first //这里是1
取第二个值 :abc.second //这里是2
注意
1>对pair使用sort排序默认会按照pair中第一个元素进行排序
2.常用函数
算法库
头文件#include<algorithm>
1.1 swap()
swap() : 交换两个变量的值
swap(变量a,变量b)
1.2 sort()
sort() : 快速排序
sort(abc.begin(),abc.end()) //从小到大排序
//等同于 sort(a,a+n)
sort(abc.begin(),abc.end(),greater<int>()) //从大到小排序
//等同于 sort(a,a+n,greater<int>())
1.3 lower_bound() & upper_bound()
lower_bound() : 寻找≥x的第一个元素的位置
upper_bound() : 寻找>x的第一个元素的位置
lower_bound(abc.begin(),abc.end(),x)
//等同于lower_bound(a,a+n,x)
upper_bound 同理
函数返回的是迭代器,如何转成下标索引呢?减去头迭代器即可,因为迭代器 - 迭代器=两个迭代器的距离
即 lower_bound(abc.begin(),abc.end(),x)-abc.begin()
1.4 reverse()
reverse() : 翻转数组
reverse(abc.begin(),abc.end())
//等同于reverse(a,a+n)
reverse(abc.begin()+2,abc.begin()+n) //翻转第2位到第n-1位
1.5 max() & min()
max() : 返回最大值
min() : 返回最小值
max({a,b,c,d,e}) //小括号只能比较两个数,大括号可以比较多个数
min 同理
1.6 unique()
unique() : 消除数组的重复相邻元素,数组长度不变,但是有效数据缩短,返回的是有效数据位置的结尾迭代器
实际使用
vector<int> abc{1, 2, 1, 4, 5, 4, 4};
sort(abc.begin(), abc.end()); //使重复元素相邻
arr.erase(unique(abc.begin(), abc.end()), abc.end()); //删除无效数据
数学库
头文件#include<cmath>
abs(x) //绝对值
exp(x) //以e为底的指数函数
log(x) //以e为底的对数函数
pow(底数,指数) //幂函数
sqrt(x) //开平方
ceil(x) //上取整
floor(x) //下取整
round(x) //四舍五入