一、C++ STL模板

1. Vector
1. vector为可变长数组（动态数组），定义的vector数组可以随时添加数值和删除元素。
2. 头文件是：#include <vector>
3. 一维初始化：
1. vector<int> a; //定义了一个名为a的一维数组,数组存储int类型数据 vector<double> b; //定义了一个名为b的一维数组，数组存储double类型数据 vector<node> c; //定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型
2. vector<int> v(n); // 定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1] vector<int> v(n, 1); // v[0] 到 v[n - 1]所有的元素初始值均为1 //注意：指定数组长度之后（指定长度后的数组就相当于正常的数组了）
4. 二维初始化
1. //初始化二维均可变长数组 vector<vector<int>> v;//定义一个行和列均可变的二维数组
2. vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
5. 方法函数
6. vector 里面有两个变量 size （指数组实际长度大小）和 capacity（指数组分配的内存空间容量大小）。
存在机制：当长度大于容量时，vector会自动进行扩容。 扩容规则为：vector会重新开辟新的内存空间（大小为原来的capacity的2倍），原来的vector中存储内容先copy到新的地址空间中，然后销毁原来的地址空间。

1. Stack
1. 栈为数据结构的一种，是STL中实现的一个先进后出，后进先出的容器。
2. 头文件是：#include<stack>
3. 方法函数
1. s.push(ele) 元素ele入栈，增加元素，O(1)
2. s.pop() 移除栈顶元素，O(1)
3. s.top() 取得栈顶元素（但不删除），O(1)
4. s.empty() 检测栈内是否为空，空为真，O(1)
5. s.size() 返回栈内元素的个数，O(1)
 

2. queue
1. 通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。
2. 头文件：#include <queue>
3. 方法函数
构造 queue<类型> que queue<int> que; 进队 .push(元素) que.push(1); 出队 .pop() que.pop(); 取队首 .front() int a = que.front(); 取队尾 .back() int a = que.back();
 

3. priority_queue
1. 提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。
2. 头文件：#include <queue>
3. 格式：priority_queue<类型, 容器, 比较器> pque
priority_queue<int> pque1; // 储存int的大顶堆 priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆
d. 方法函数

进堆	.push(元素)	que.push(1);
出堆	.pop()	que.pop();
取堆顶	.top()	int a = que.top();

1. set
1. 提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。
2. 头文件：#include <set>
3. 构造：set<类型, 比较器> st
set<int> st1; // 储存int的集合（从小到大） set<int, greater<int>> st2; // 储存int的集合（从大到小）
d. 方法函数

插入元素	.insert(元素)	st.insert(1);
删除元素	.erase(元素)	st.erase(2);
查找元素	.find(元素)	auto it = st.find(1);
判断元素是否存在	.count(元素)	st.count(3);

1. map
1. 提供对数时间的有序键值对结构。底层原理是红黑树。
2. 构造：map<键类型, 值类型, 比较器> mp
map<int, int> mp1; // int->int 的映射（键从小到大） map<int, int, greater<int>> st2; // int->int 的映射（键从大到小）
c. 方法函数

增 / 改 / 查元素	中括号	mp[1] = 2;
查元素（返回迭代器）	.find(元素)	auto it = mp.find(1);
删除元素	.erase(元素)	mp.erase(2);
判断元素是否存在	.count(元素)	mp.count(3);
ㅤ	ㅤ	ㅤ