### 第一部分：序列式容器与容器适配器
这一类容器主要关注数据的顺序存储与特定规则的访问。其中，`stack`、`queue` 和 `priority_queue` 被称为**容器适配器**，它们是对底层序列容器（如 `deque`、`vector`）的封装。

#### 1. `vector`（动态数组）
+ **特点**：连续内存存储，支持随机访问。尾部插入和删除效率高，而在中间或头部插入和删除需要移动元素，效率较低。
+ **常用方法**：
    - `push_back(val)` / `pop_back()`：尾部添加或删除元素。
    - `insert(pos, val)` / `erase(pos)`：在指定迭代器位置插入或删除元素（涉及元素移动）。
    - `front()` / `back()`：获取首尾元素引用。
    - `size()` / `empty()`：获取大小或判断是否为空。
    - `resize(sz,val)`：改变容器大小（会创建元素）。

#### 2. `deque`（双端队列）
+ **特点**：分段连续内存存储。支持随机访问，支持在头部和尾部进行高效的插入与删除。
+ **常用方法**：
    - `push_back(val)` / `pop_back()`：尾部添加或删除。
    - `push_front(val)` / `pop_front()`：头部添加或删除。
    - `size()` / `empty()` / `clear()`：获取大小、判空或清空容器。

#### 3. `stack`（栈）
+ **特点**：后进先出（LIFO）的容器适配器。默认底层使用 `deque` 实现。不支持迭代器遍历。
+ **常用方法**：
    - `push(val)`：压栈。
    - `pop()`：出栈（不返回元素）。
    - `top()`：获取栈顶元素。
    - `empty()` / `size()`：判空或获取大小。

#### 4. `queue`（队列）
+ **特点**：先进先出（FIFO）的容器适配器。默认底层使用 `deque` 实现。不支持迭代器遍历。
+ **常用方法**：
    - `push(val)`：入队。
    - `pop()`：出队（不返回元素）。
    - `front()`：获取队头元素。
    - `back()`：获取队尾元素。
    - `empty()` / `size()`：判空或获取大小。

#### 5. `priority_queue`（优先队列）
+ **特点**：默认是大顶堆（最大元素先出队）。底层通常基于 `vector`，并利用堆算法进行维护。不支持随机访问，不支持迭代器。
+ **常用方法**：
    - `push(val)`：插入元素并重构堆（时间复杂度 $ O(\log N) $）。
    - `pop()`：弹出堆顶元素并重构堆（时间复杂度 $ O(\log N) $）。
    - `top()`：获取堆顶元素（最大或最小元素）。
    - `empty()` / `size()`：判空或获取大小。
+ **定义最小堆写法**：

```cpp
priority_queue<int, vector<int>, greater<int>> min_heap;
```

---

#### 核心对比：`vector` vs `deque` vs 适配器
| 维度 | `vector` | `deque` | `stack` / `queue` | `priority_queue` |
| :--- | :--- | :--- | :--- | :--- |
| **底层结构** | 单块连续物理内存 | 多个分段连续内存块 | 默认 `deque` | 默认 `vector` (堆结构) |
| **随机访问** | 支持 ($ O(1) $) | 支持 ($ O(1) $，略慢于 `vector`) | 不支持 | 不支持 |
| **头部操作** | 慢 ($ O(N) $，需移动元素) | 快 ($ O(1) $) | `queue` 支持 `pop()` / `stack` 不适用 | 不支持单独头部操作 |
| **尾部操作** | 快 ($ O(1) $ 均摊) | 快 ($ O(1) $) | 支持 | 不适用 |
| **迭代器** | 支持，扩容时可能失效 | 支持，操作可能导致失效 | 不支持 | 不支持 |

##### 为什么 `stack` 和 `queue` 默认使用 `deque` 而非 `vector`？
1. **避免频繁的大块内存重分配**：`vector` 在扩容时需要重新分配整块内存并搬移所有元素；而 `deque` 只需申请一个新的数据块并将其指针加入中控器，扩容成本更低。
2. **释放内存更积极**：`deque` 的分段结构允许它在头部或尾部完全释放空闲的数据块，而 `vector` 的内存通常只能通过 `shrink_to_fit()` 手动释放。
3. **特定操作效率**：`queue` 需要高效的头部删除（`pop`），这在 `vector` 中是 $ O(N) $ 操作，而在 `deque` 中是 $ O(1) $。

---

### 第二部分：关联式与无序关联式容器
这类容器主要用于存储键值对（Key-Value）或孤立键，重点在于高效的查找、插入和删除操作。

#### 1. 有序关联容器：`set` / `map`
+ **特点**：底层为**红黑树**（自平衡二叉搜索树）。元素自动按键值升序排序。
+ **常用方法**：
    - `insert(val / {key, val})`：插入元素并自动排序。
    - `erase(key)` / `erase(iterator)`：删除指定键或位置的元素。
    - `find(key)`：查找元素，返回迭代器。若未找到，返回 `end()`。
    - `count(key)`：返回包含该键的元素个数（对于 `set`/`map` 只能是 0 或 1）。
    - `lower_bound(key)` / `upper_bound(key)`：返回第一个 $ \ge $ 或 $ > $ 给定键的迭代器。
    - `operator[]` / `at(key)`（**仅限 **`map`）：访问或插入元素。
        * _注意：使用 _`operator[]`_ 时，若键不存在，会自动创建一个带默认值的元素。_

#### 2. 无序关联容器：`unordered_set` / `unordered_map`
+ **特点**：底层为**哈希表**（哈希桶数组 + 链表/红黑树解决冲突）。元素无序。
+ **常用方法**：
    - `insert()` / `erase()` / `find()` / `count()`：与有序版本类似。
    - `operator[]` / `at(key)`（**仅限 **`unordered_map`）。

---

##### 选型建议：
+ 若需要**遍历时保证有序**，或者需要进行**区间查找/范围查询**（例如：找出所有键在 $ [L, R] $ 之间的元素），应选用 `set`/`map`。
+ 若只需进行**单点查找、插入**，且不关心元素顺序，应优先选择 `unordered_set`/`unordered_map` 以获得平均 $ O(1) $ 的运行速度。

第一部分：序列式容器与容器适配器

这一类容器主要关注数据的顺序存储与特定规则的访问。其中，stack、queue 和 priority_queue 被称为容器适配器，它们是对底层序列容器（如 deque、vector）的封装。

1. `vector`（动态数组）

特点：连续内存存储，支持随机访问。尾部插入和删除效率高，而在中间或头部插入和删除需要移动元素，效率较低。
常用方法：
- push_back(val) / pop_back()：尾部添加或删除元素。
- insert(pos, val) / erase(pos)：在指定迭代器位置插入或删除元素（涉及元素移动）。
- front() / back()：获取首尾元素引用。
- size() / empty()：获取大小或判断是否为空。
- resize(sz,val)：改变容器大小（会创建元素）。

2. `deque`（双端队列）

特点：分段连续内存存储。支持随机访问，支持在头部和尾部进行高效的插入与删除。
常用方法：
- push_back(val) / pop_back()：尾部添加或删除。
- push_front(val) / pop_front()：头部添加或删除。
- size() / empty() / clear()：获取大小、判空或清空容器。

3. `stack`（栈）

特点：后进先出（LIFO）的容器适配器。默认底层使用 deque 实现。不支持迭代器遍历。
常用方法：
- push(val)：压栈。
- pop()：出栈（不返回元素）。
- top()：获取栈顶元素。
- empty() / size()：判空或获取大小。

4. `queue`（队列）

特点：先进先出（FIFO）的容器适配器。默认底层使用 deque 实现。不支持迭代器遍历。
常用方法：
- push(val)：入队。
- pop()：出队（不返回元素）。
- front()：获取队头元素。
- back()：获取队尾元素。
- empty() / size()：判空或获取大小。

5. `priority_queue`（优先队列）

特点：默认是大顶堆（最大元素先出队）。底层通常基于 vector，并利用堆算法进行维护。不支持随机访问，不支持迭代器。
常用方法：
- push(val)：插入元素并重构堆（时间复杂度 $ O(\log N) $）。
- pop()：弹出堆顶元素并重构堆（时间复杂度 $ O(\log N) $）。
- top()：获取堆顶元素（最大或最小元素）。
- empty() / size()：判空或获取大小。
定义最小堆写法：

priority_queue<int, vector<int>, greater<int>> min_heap;

核心对比：`vector` vs `deque` vs 适配器

维度	`vector`	`deque`	`stack` / `queue`	`priority_queue`
底层结构	单块连续物理内存	多个分段连续内存块	默认 `deque`	默认 `vector` (堆结构)
随机访问	支持 ($ O(1) $)	支持 ($ O(1) $，略慢于 `vector`)	不支持	不支持
头部操作	慢 ($ O(N) $，需移动元素)	快 ($ O(1) $)	`queue` 支持 `pop()` / `stack` 不适用	不支持单独头部操作
尾部操作	快 ($ O(1) $ 均摊)	快 ($ O(1) $)	支持	不适用
迭代器	支持，扩容时可能失效	支持，操作可能导致失效	不支持	不支持

为什么 `stack` 和 `queue` 默认使用 `deque` 而非 `vector`？

避免频繁的大块内存重分配：vector 在扩容时需要重新分配整块内存并搬移所有元素；而 deque 只需申请一个新的数据块并将其指针加入中控器，扩容成本更低。
释放内存更积极：deque 的分段结构允许它在头部或尾部完全释放空闲的数据块，而 vector 的内存通常只能通过 shrink_to_fit() 手动释放。
特定操作效率：queue 需要高效的头部删除（pop），这在 vector 中是 $ O(N) $ 操作，而在 deque 中是 $ O(1) $。

第二部分：关联式与无序关联式容器

这类容器主要用于存储键值对（Key-Value）或孤立键，重点在于高效的查找、插入和删除操作。

1. 有序关联容器：`set` / `map`

特点：底层为红黑树（自平衡二叉搜索树）。元素自动按键值升序排序。
常用方法：
- insert(val / {key, val})：插入元素并自动排序。
- erase(key) / erase(iterator)：删除指定键或位置的元素。
- find(key)：查找元素，返回迭代器。若未找到，返回 end()。
- count(key)：返回包含该键的元素个数（对于 set/map 只能是 0 或 1）。
- lower_bound(key) / upper_bound(key)：返回第一个 $ \ge $ 或 $ > $ 给定键的迭代器。
- operator[] / at(key)（仅限 map）：访问或插入元素。
  - 注意：使用 operator[] 时，若键不存在，会自动创建一个带默认值的元素。

2. 无序关联容器：`unordered_set` / `unordered_map`

特点：底层为哈希表（哈希桶数组 + 链表/红黑树解决冲突）。元素无序。
常用方法：
- insert() / erase() / find() / count()：与有序版本类似。
- operator[] / at(key)（仅限 unordered_map）。

核心对比：有序关联（红黑树） vs 无序关联（哈希表）

维度	`set` / `map`	`unordered_set` / `unordered_map`
底层实现	红黑树（平衡二叉树）	哈希表
元素顺序	有序（默认升序）	无序
查找/插入/删除	$ O(\log N) $（性能相对稳定）	平均 $ O(1) $，最坏 $ O(N) $（哈希冲突严重时）
自定义类型支持	需要重载 `operator<`	需要提供哈希函数（`hash`）和重载 `operator==`
空间开销	较低（每个节点额外存储指针和颜色）	较高（需维护哈希桶数组及冲突链表/树）
区间查找	支持（使用 `lower_bound` 等）	不支持

选型建议：

若需要遍历时保证有序，或者需要进行区间查找/范围查询（例如：找出所有键在 $ [L, R] $ 之间的元素），应选用 set/map。
若只需进行单点查找、插入，且不关心元素顺序，应优先选择 unordered_set/unordered_map 以获得平均 $ O(1) $ 的运行速度。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

常用STL容器方法总结

第一部分：序列式容器与容器适配器

1. vector（动态数组）

2. deque（双端队列）

3. stack（栈）

4. queue（队列）

5. priority_queue（优先队列）

核心对比：vector vs deque vs 适配器

为什么 stack 和 queue 默认使用 deque 而非 vector？