文章目录：
  1. vector 变长数组
    1. 初始化
    2. 方法
    3. 访问
  2. stack 堆
  3. queue 队列
  4. deque 双向队列
  5. priority_queue 优先队列
    1. 常用方法
    2. 排序规则
  6. map 映射
再也不想上机的时候手写堆了。

万能头：

#include <bits/stdc++.h>

vector 变长数组

动态数组，可以变长。

头文件：

#include <vector>

初始化

// 一维
vector<int> a; // <>里面写数据类型
vector<int> v(n); // 指定长度为n，初始值均为0
vector<int> v(n, 114514); // 指定长度为n、初始值都是n-1
vector<int> a{1,2,3,4,5}; // 初始化，数组长度为5
// 拷贝初始化
vector<int> a(n, 1);
vector<int> b(a); // b也是长度为n、初始值为1的数组
vector<int> c = a; // 另一种拷贝初始化方法

// 二维
vector<int> v[5]; // 第一维固定长度5，第二位可变长
vector<vector<int>> v; // 二维长度均可变，可以直接push_back进去一个数组
vector<vector<int>> a(n, vector<int>(n, 0)); // 行列均长度n且初始值为0

方法

a.front(); // 第一个数
a.back(); // 第二个数
a.size(); // 返回数据个数
a.begin(); // 返回数组首地址迭代器
a.end(); // 返回数组尾地址迭代器（最后一个元素的下一个位置）
a.empty(); // 是否为空
a.assigm(beg, end); // 将另一个容器[x.begin(), x.end()]拷贝到a里面
a.pop_back(); // 删除最后一个元素
a.push_back(element); // 最后面加一个元素
a.insert(pos, x); // 向任意迭代器pos插入一个元素x
a.resize(n, v); // 改变数组大小为n，且赋值为v
a.erase(first, last); // 删除[first, last)之间的元素

访问

// 方法1: 下标
a[1]; // 第二个元素

// 方法2：迭代器
// 类似于指针，变量类型为vector<int>::iterator
vector<int>::iterator it = vi.begin(); //声明一个迭代器指向vi的初始位置
cout << *(it + 1) << endl; // 类似于指针，使用*解引用

// 方法3：使用auto
for(auto x: a){
    cout << x << endl;
}

stack 堆

栈。但不如直接模拟方便。

#include <stack>

stack<int> s;
s.push(element);
s.pop();
s.top(); // 获取堆顶元素
s.empty();
s.size();

queue 队列

队列。也是自己拿数组模拟更好。

#include <queue>

queue<int> que;
que.front(); // 获取队首元素
que.back(); // 获取队尾元素
//... 其他和stack一样

deque 双向队列

首尾均可插入删除

#include<deque>

deque<int> dq;
push_back(x); push_front(x); // 前后插入
back(); front(); // 返回前或后
pop_back(); pop_front();  // 删除首尾

priority_queue 优先队列

优先队列，可以定义大顶堆、小顶堆等，可以自定义比较规则。

#include <queue>
priority_queue<int> q;

常用方法

q.top();
q.push();
q.pop();
q.size();
q.empty();

排序规则

priority_queue<int, vector<int>, greater<int>> q; // 小顶堆

主要是排序比较函数的写法。比较函数返回1代表不满足规则，返回0代表不需要改变顺序。所以比较函数和正常的想法可能是反着的，比如return小于号得到的是一个大顶堆。

定义里面的cmp是一个struct结构体。有以下的定义方法：

// 单独定义一个比较结构体
struct cmp{
    bool operator()(const Point& a, const Point$ b){
        return a.x < b.x;
    }
}
priority_queue<Point, vector<Point>, cmp> q; // 对x的大顶堆

// 或者直接在数据的结构体里面写
struct Point {
    int x, y;
    friend bool operator < (Point a, Point b) {//为两个结构体参数，结构体调用一定要写上friend
        return a.x < b.x; //大根堆，按x从小到大排，x大的在堆顶
    }
}
priority_queue<Point> q; // 相当于给结构体写了一个自带比较方法

对于pair类型，先对first进行降序排序，再对second进行降序排序。

map 映射

未完待续…

参考： wyqz.top/p/870124582.html