priority_queue优先队列
优先队列，具有队列的所有特性和基本操作，只是在这基础上添加了内部的一个排序，它本质是由堆实现
头文件#include<queue>
数据结构
队首元素一定是优先级最高的一个
声明
priority_queue<int> a默认为大顶堆，降序
访问
只能通过a.top() 访问队顶元素
优先级设置
priority_queue<typename, container, functional>完整的定义方式
container容器默认为vector，functional默认为less<int>
- 基本数据类型的优先级
less<int>表示数字大的优先级越大，即降序排列，大顶堆
greater<int>表示数字小的优先级越大，即升序排列，小顶堆
- 结构体的优先级
需要用到重载运算符（
操作
和queue队列操作基本相同
a.top() 访问队头元素，无a.front()，a.back()
a.push(x)将x进行入队（时间复杂度为O(log n))
a.pop()令队首元素出队（时间复杂度为O(log n))
应用
贪心
queue
头文件#include<queue>
数据结构
先进先出，queue容器允许从一端新增元素，从另一端移除元素。
queue无迭代器。
声明
queue<int> a;新建一个queue容器
访问
只能通过a.front()，a.back()来访问队首，队尾元素
操作
a.push(x)将x进行入队（时间复杂度为O(1))
a.pop()令队首元素出队
a.front()获取队首元素
a.back()获取队尾元素
应用
广搜
map
头文件include<map>
我们可以把array数组理解为int到int的映射
map可以将任意数据类型(包括STL)映射到任意数据类型(包括STL)
声明
map<typename1,typename2> atypename1和typename2分别为键值，实值
map<string,int> a字符串到整型的映射，必须使用string，不能用char
访问
- 通过键值访问：
比如当建立了map<char,int> a的map时，可以直接使用a['c']这样的方式来访问它对应的int
注意：map中的键值是唯一的。
- 通过迭代器访问：
map<key,value>::iterator it1;
it1 -> first; //访问当前映射的键值
it1 -> second; //访问当前映射的实值
迭代器
map<key,value>::iterator it1;双向访问迭代器，解引用后得到一个二元组pair
数据结构
map会按照键值的字典序由小到大自动排序，这是因为map内部是用红黑树实现的
操作
a.find(key)返回键值为key的映射的迭代器，O(log n)
a.erase(it) 删除单个元素，it为需要删除元素的迭代器，O(1)
a.erase(key) 删除单个元素，key为所需要删除元素的键值，O(log n)
a.erase(l,r)删除一个区间内的所有元素，l为区间的起始迭代器，r为区间末尾迭代器的下一个地址
a.size()获取map内映射的对数
a.clear()以下同set
a.begin()
a.end()
a.empty()
应用
处理大整数或其他类型数据的题目
需要建立字符或字符串到整数的映射
multimap
Multimap和map的操作类似，唯一区别multimap键值可重复。
Map和multimap都是以红黑树为底层实现机制。
stack
头文件include<stack>
后进后出的容器。
无迭代器，不能遍历。
声明
stack<int> a
访问
只能通过top()来访问栈顶元素
操作
a.push(x)将x入栈
a.top()获取栈顶元素
a.pop()弹出栈顶元素
a.empty()
a.size()
数据结构
后进后出
应用
实现某些递归
pair
头文件#include<map>或#include<utility>
<map>中包含<utility>
pair可以把两个元素绑在一起作为一个合成元素
pair可以看作一个内部有两个元素的结构体
声明
pair<typename1,typename2> a其中typename1，typename2可以是任意基本数据类型或容器
pair<typename1,typename2> a(value1,value2)声明并进行初始化
a = pair<string,int>("asd",123)在代码中临时构建一个pair
a = make_pair("asd",123)使用自带函数在代码中临时构建一个pair
访问
按结构体的方式访问
a.first访问第一个元素
a.second访问第二个元素
操作
两个pair类型数据可以直接使用==，!= ，<，<=，>，>=比较大小，规则是先以first的大小为标准，若first相等再判断second
pair<int,int> a(10,10);
pair<int,int> b(5,5);
a>b;
应用
代替二元结构体
作为map的键值进行插入：
map<string,int> a;
a.insert(make_pair("c",123));
list
头文件#include<list>
数据结构
-
list容器为双向链表
-
链表是一种在物理内存空间中非连续，非顺序的存储结构
-
元素的逻辑顺序通过链表中的指针链接次序实现
-
链表中的元素称为节点，一个节点包括两部分：数据域(存数据)和指针域(存下个节点的地址)
-
链表为动态内存分配，每次插入或者删除一个元素，就会配置或者释放一个元素的空间
-
链表灵活，但是空间和时间额外耗费较大，随机访问较慢
迭代器
-
list为双向迭代器,不支持随机访问
-
插入和删除操作都不会造成原有list迭代器的失效。
声明
list<int> a
访问
- 使用迭代器
list<int> a;
for(list<int>::iterator it = a.begin(); it != a.end(); it++)
{
cout<<*it;
}
- 通过函数
front() 和 back()
操作
a.push_back(x) 在容器尾部加入一个元素x
a.push_front(x) 在容器开头插入一个元素x
a.pop_back() 删除容器中最后一个元素
a.pop_front()移除容器中第一个元素
a.remove(x) 删除容器中所有与x值匹配的元素
a.assign(l,r) 将[l,r)中的数据赋值给本身
a.swap(c) 将c与本身的元素互换
a.front()返回第一个元素
a.back() 返回最后一个元素
a.insert()，a.erase()，a.clear()，a.size() ，a.empty()
和其他容器的用法相同