常用STL
一.queue
简介： 是最常用的STL容器，需要加 <queue> 头文件
可用函数:
1.size //大小
2.empty //是否为空
3.push //队尾插入
4.pop //队首取出
5.front //队头元素
6.back //队尾元素
均可通过 " . + 函数名" 调用。
二.stack
简介: 是最常用的STL容器，需要加 <stack> 头文件
可用函数:
- size //大小
- empty //是否为空
- push //栈顶插入
- pop //栈顶取出
- top //栈顶元素
三.priority_queue
简介: 一个大/小根堆(默认大根堆)， 需加 <queue> 头文件
1.可用函数:
- size //大小
- empty //是否为空
- push //堆插入
- pop //堆顶取出
- top //堆顶元素
2.关于priority_queue中元素的比较：
模板申明带3个参数：priority_queue <Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。
Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector。
如果缺省后两个参数， 则默认大根堆。
3.将大根堆转化为小根堆
- 将三个参数全部填上， STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。
priority_queue<int, vector<int>, greater<int> > q; //一个小根堆
- 使用 pair 类型， pair 中first存所需比较元素的相反数，second中存放需要元素。
priority_queue < pair<int, int> > q;
- 使用结构体重载小于号转化，此方法可以存较多元素， 实现较复杂的操作。
struct node
{
int x;
bool operator < (const node & b) const
{
return x > b.x; //将小于号重载为大于号即可
}
};
priority_queue <node> q;
四.deque
简介: 一个双端队列， 需加 <deque> 头文件
可用函数:
- [] //随机访问
- begin/end //头/尾 迭代器
- front/back //头/尾 元素
- push_back //从队尾插入
- push_front //从队头插入
- pop_back //从队尾出队
- pop_front //从队头出队
- clear //将队列清空
五.vector
简介: 一个长度可变的数组， 需加 <vector> 头文件
1.可用函数:
- [] //随机访问
- size //大小
- empty //是否为空
- clear //将vector清空
- begin/end //头/尾 迭代器
- front/back //头/尾 元素
- push_back/pop_back //从尾插入/删
2.对vector中元素进行逐个访问:
使用iterator、auto 或 下标
vector <int> vec;
for (vector <int> ::iterator it = vec.begin(); it != vec.end(); ++ it)
{
cout << *it << endl;
}
for (auto a : vec)
{
cout << a << endl;
}
for (int i = 0; i < vec.size(); ++ i)
{
cout << vec[i] << endl;
}
五.set(multiset)
简介: 一个集合(封装好的平衡树(红黑树))， 需加 <set> 头文件
副： set 为有序集合， multiset 为有序多重集合， unordered_set(基于Hash表) 很少用，故不多赘述。
可用函数:
-
size //大小
-
empty //是否为空
-
clear //将集合清空
-
begin/end //头/尾 迭代器
-
front/back //头/尾 元素
-
insert //向集合中插入元素，时间复杂度$ O(log{n}) $ (副： multiset 可以重复插入元素)
-
find // s.find(x)会于集合中查找等于x的元素，并返回指向该元素的 迭代器 ， 若不存在，则返回 s.end(), 时间复杂度$ O(log{n}) $
-
lower_bound/upper_bound //用法与find类似。
s.lower_bound(x) 查找 $\geqslant x $ 的元素中最小的， 并返回指向该元素的迭代器
s.upper_bound(x) 查找 $> x $ 的元素中最小的， 并返回指向该元素的迭代器
-
erase // 删除
设it为一个迭代器， s.erase(it) 从s中删除迭代器it指向的元素， 时间复杂度$ O(log{n}) \( 设x为一个元素， s.erase(x) 从s中删除所有等于x的元素， 时间复杂度\) O(k + log{n}) $ (k 为被删除的元素个数)
如果想从multiset中删除掉至多1个等于x的元素，可以执行if((it = s.find(x)) != s.end()) s.erase(it); -
count // s.count(x) 返回集合s中等于x的元素个数， 时间复杂度$ O(k + log{n}) $ (k 为元素x的个数)
六. map(unordered_map)
简介: 一个键值对kay-value的映射(实现为一棵以key为关键码的红黑树)。map的key和value可以是任何类型， 其中k必须定义“\(<\)”运算符
副: multimap 与 map 的区别类似与 multiset 和 set, 只是在能否重复上不同，故不多赘述。
1.可用函数:
- size //大小
- empty //是否为空
- clear //将集合清空
- begin/end //头/尾 迭代器
- insert/erase // 插入/删除 与set类似, insert的参数为 pair <key_type,value_type>, erase的参数可以为pair或迭代器
- find // h.find(x) 在名为h的map中查找key为x的二元组， 并返回指向该二元组的迭代器。 若不存在，则返回 h.end()。时间复杂度$ O(log{n}) $
- "[ ]"操作符 //