听课总结

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()
2>栈 : 先进后出

总结 : 不能直接访问内部元素，剩下的和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());   //删除无效数据

1.7 find()
find() : 用于在给定范围内查找与目标元素值相等的第一个元素,如果查找成功,返回一个指向找到的元素的迭代器,如果失败,则返回一个指向范围末尾的迭代器

find(abc,1)   //从abc中查找第一个出现的元素1
abc.find(1)   //从abc中查找第一个出现的元素1

1.8 erase()
erase() : 删除元素

erase(pos,1)   //删除从pos开始的第1个字符
erase(pos)   //删除pos处的一个字符
erase(2,10)   //删除从2到10之间的字符

1.9 substr()
substr() : 获取指定起始位置和指定长度的一串字符串

substr(abc,1,5)   //获取字符串abc从a[1]开始,长度为5的字串
abc.substr(1,5)   //获取字符串abc从a[1]开始,长度为5的字串

数学库

头文件#include<cmath>

abs(x)   //绝对值
exp(x)   //以e为底的指数函数
log(x)   //以e为底的对数函数
pow(底数，指数)   //幂函数
sqrt(x)   //开平方
ceil(x)   //上取整
floor(x)   //下取整
round(x)   //四舍五入

刷题总结

stack : 先出最后一个,用的比较少
queue : 先出第一个,用的最多
map : 不好用,不如自己直接定义类

把队列的第一个元素放到最后,以此循环队列
que.push(que.front())
que.pop

自定义sort函数从大到小比较学生成绩
struct student
{
    int sum;
    string name;
};
bool cmp (student a,student b)
{
    return a.sum>b.sum
}
sort (stu,stu+n,cmp);
//sort函数在cmp函数的返回值为真时,将其第一个元素放在前面

有些不要脸的题会要求末尾没有空格,这时就需要先输出空格
for (int i=0;i<n;i++)
    {
        if (i) cout<<" ";
        cout<<stu[i];
    }