STL（标准模板库）中的各种容器和算法的使用方法。

推荐引入万能头文件：

#include <bits/stdc++.h>
using namespace std;//使用std命名空间

vector

创建vector

vector<int> v; // 创建一个空的vector，元素类型为int
vector<int> v1(10); // 创建一个含有10个元素的vector，所有元素默认初始化为0
vector<int> v2(10, 42); // 创建一个含有10个元素的vector，所有元素初始化为42
vector<int> v3 = {1, 2, 3, 4, 5}; // 使用列表初始化创建一个vector

访问元素

int x = v[0]; // 访问第一个元素
int y = v.at(1); // 使用at()函数访问第二个元素，at()会进行边界检查

修改元素

v[0] = 10; // 修改第一个元素，O(1)
v.push_back(20); // 在vector末尾添加一个元素，O(1)
v.pop_back();//删除末尾元素，O(1)，请注意保证vector非空

遍历vector

for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << ' ';
}
cout << endl;
// 或者使用范围for循环
for (int elem : v) {
    cout << elem << ' ';
}
cout << endl;
// 如果vector存储的是pair类型或结构体，C++17以上版本可以使用结构化绑定来枚举
vector<pair<int, int>> v_pair;
// &表示引用枚举，不加&就是默认拷贝枚举
for(const auto &[a, b] : v_pair){
  cout << x << ' ' << y << '\n';
}

查询vector的大小

int size = v.size(); // 返回vector中元素的数量
//判断vector是否为空
if(v.empty()) ...
if(v.size()) ...

清空vector

v.clear(); // 移除所有元素，size变为0，时间复杂度O(n)

stack

stack是栈，一种后进先出（Last In First Out）的容器，它仅维护栈顶，支持入栈（push）、查询栈顶（top）、出栈（pop）、查询大小（size）操作。

常用于“单调栈”、“括号匹配”、“dfs”、“Tarjan求强连通分量”、“波兰表达式（计算器）”等算法或数据结构中。

初始化

stack<int> stk;//创建一个空栈，栈不允许列表初始化或填充相同元素
//但是可以从已有的栈进行拷贝构造
stack<int> stk2(stk);
stack<int> stk3 = stk2;

入栈

stk.push(10);//stk = [10(top)]
stk.push(20);//stk = [10, 20(top)]
stk.push(50);//stk = [10, 20, 50(top)]
cout << stk.top() << '\n';//50, stk = [10, 20, 50(top)]

取出栈顶元素

在C++中，top()函数仅仅是取出栈顶元素，不会将栈顶元素pop()掉，请注意！

cout << stk.top() << '\n';//50, stk = [10, 20, 50(top)]

出栈

讲个笑话：如果你问一个人push的反义词是什么，如果他说是pop，那么他肯定是一个程序员。

//弹出栈顶元素，注意判断非空！
if(stk.size())stk.pop();//stk = [10, 20(top)]
cout << stk.top() << '\n';//20, stk = [10, 20(top)]

获取栈大小（元素个数），判空

cout << stk.size() << '\n';
if(stk.empty())...//栈为空

清空栈

while(stk.size())stk.pop();//时间复杂度O(n)

在stack中不允许遍历，但是如果我们手写栈（或者干脆用vector好了），就可以实现这个功能。

手写栈

手写栈非常简单，用一个top变量表示栈顶下标即可，以下标1作为栈底。

int stk[N], top = 0;
//入栈
stk[++ top] = x;
//出栈
top --;
//取出栈顶元素
cout << stk[top] << '\n';
//获取大小
cout << top << '\n';
//判断是否为空
if(top)...//栈非空
//遍历栈
for(int i = 1;i <= top; ++ i)...
//甚至可以在单调栈上进行二分

queue

queue提供了先进先出（First In First Out）的数据结构。队列在尾部添加元素，在头部删除元素。

常见应用有：模拟、约瑟夫环、bfs、分支限界搜索、单调队列等算法。

创建队列

queue<int> q; // 创建一个int类型的队列

添加元素（入队）

使用push()函数将元素添加到队列的尾部。

q.push(10); // 将10添加到队列尾部
q.push(20);
q.push(30);

删除元素（出队）

使用pop()函数删除队列的头部元素。

q.pop(); // 删除队列头部元素，即10

访问队列头部元素

使用front()函数获取队列头部元素的引用。

int frontElement = q.front(); // frontElement 现在是20

访问队列尾部元素

使用back()函数获取队列尾部元素的引用。

int backElement = q.back(); // backElement 现在是30

检查队列是否为空 / 获取队列大小

使用empty()函数检查队列是否为空。

if (q.empty()) {
    cout << "队列是空的" << endl;
} else {
    cout << "队列不是空的" << endl;
}
int size = q.size(); // size 现在是2

示例代码

以下是一个使用queue的完整示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    // 添加元素
    q.push(10);
    q.push(20);
    q.push(30);
    // 输出队列头部元素
    cout << "队列头部元素：" << q.front() << endl;
    // 删除队列头部元素
    q.pop();
    // 再次输出队列头部元素
    cout << "队列头部元素（删除后）：" << q.front() << endl;
    // 输出队列大小
    cout << "队列大小：" << q.size() << endl;
    return 0;
}

运行上述代码，输出结果如下：

队列头部元素：10
队列头部元素（删除后）：20
队列大小：2

queue和stack一样，不允许遍历。

deque

deque是queue的升级版，全称为double-ended queue，队头和队尾都支持入队和出队，同时还支持遍历，所有操作时间复杂度均为 O(1)。

常见应用是单调队列。

声明

deque<int> dq;

常用操作

dq.push_front(x);//在队头推入x
dq.push_back(x);//在队尾推入x
dq.front();//获取队头元素
dq.back();//获取队尾元素
//获取队列大小
dq.size();
//获取队列是否为空
dq.empty();
//以下两个操作注意判断队列非空
dq.pop_front();//弹出队头
dq.pop_back();//弹出队尾

遍历deque

//用迭代器遍历
for(auto it = dq.begin(); it != dq.end(); it ++)
{
  cout << *it << ' ';
}
//用基于范围的for循环
for(const auto &val : dq)cout << val << ' ';

priority_queue

优先队列，也叫做“堆”，仅维护最大/最小的元素，可以在较小的时间复杂度内获取某个元素集合的最大或最小值。

优先队列常用于贪心、优化dp、构造、dijkstra、prim等问题或算法中，应用非常广泛。

声明

//默认为大根堆
priority_queue<int> pq;
//改为小根堆
priority_queue<int, vector<int>, greater<int> > pq;
//自定义比较函数常用方法
//方法一：全局函数，传入函数指针用decltype转换
bool cmp(const int &u, const int &v){
  return u < v;//大根堆
}
priority_queue<int, vector<int>, decltype(&cmp) > pq(cmp);
//方法二：匿名函数用cmp变量存储，传入变量
auto cmp = [](const int &u, const int &v){
  return u < v;//大根堆
};
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
//方法三：struct重载()运算符
struct cmp{
    bool operator () (const int &u, const int &v){
      return u < v;//大根堆
    }
};
priority_queue<int, vector<int>, cmp> pq;

常规操作

//取出堆顶元素，时间复杂度O(1)
cout << pq.top() << '\n';//注意保证pq非空
//入堆，时间复杂度O(logn)，n为堆内元素个数
pq.push(x);
//出堆，时间复杂度O(logn)，n为堆内元素个数
pq.pop();//注意保证pq非空
//获取堆内元素个数，即堆的大小
cout << pq.size() << '\n';
优先队列为树形结构，不支持遍历（除非逐个出堆）。