登录以参加训练计划

“基础数据结构与 STL 的运用” 是 C++ 选手在 CSP-J/S 及 NOIP 比赛中最强大的“武器库”。

掌握了这些，你就不用再徒手写几百行的堆排序或哈希表，而是可以直接调用 C++ 标准模板库（STL）中封装好的容器。这能极大提升你的代码编写速度和准确率。

下面我为你全方位拆解这些知识点，重点放在 “竞赛怎么考” 和 “怎么用” 上。

---

一、 Vector (动态数组)

1. 核心概念 一个可以自动改变大小的数组。

• 优点：支持随机访问（v[i]），尾部插入删除快 $O(1)$。
• 缺点：在中间或头部插入删除非常慢 $O(N)$（因为要移动后面的元素）。

2. 常用操作

• push_back(x): 尾部添加。
• pop_back(): 尾部删除。
• size(): 获取长度。
• clear(): 清空。
• resize(n): 重新设定大小。

3. 竞赛实战

• 邻接表存图：vector<int> adj[N] 用来存图极其方便。
• 不定长数据：当你不确定输入有多少个数时，先用 vector 存下来。
• 高精度计算：每一位数字存 vector 里。

---

二、 队列 (Queue)

1. 核心概念 先进先出 (FIFO)。就像食堂排队，先来的先打饭。

2. 变体与用法

• 普通队列 (queue)：
  • push(x): 入队。
  • pop(): 出队（注意：不返回值）。
  • front(): 查看队首。
  • 必考场景：BFS（广度优先搜索）。
• 双端队列 (deque)：
  • 头尾都能进能出 (push_front, push_back)。
  • 支持下标访问 d[i]。
  • 必考场景：单调队列优化 DP、滑动窗口最大值。

---

三、 栈 (Stack)

1. 核心概念 后进先出 (LIFO)。就像往箱子里放书，最后放进去的先拿出来。

2. 常用操作

• push(x): 入栈。
• pop(): 出栈。
• top(): 查看栈顶。

3. 竞赛实战

• 符号匹配：括号序列合法性判断。
• 表达式求值：中缀转后缀表达式。
• 单调栈：找“左边/右边第一个比我大/小的数”（高频考点，如“接雨水”问题）。
• 模拟递归：防止爆系统栈时，手写栈模拟 DFS。

---

四、 链表 (Linked List)

1. 核心概念 内存不连续，通过指针相连。

• STL list：双向链表。但在竞赛中很少直接用，因为指针操作慢且不支持随机访问。
• 静态链表（数组模拟）：这是竞赛重点！

2. 数组模拟链表（必会） 使用数组 val[N], nxt[N], pre[N] 来模拟。

• 优势：速度极快，内存可控。
• 实战场景：
  • 链式前向星：存图的最主流方式。
  • 频繁删除/插入：比如“约瑟夫问题”的优化，或者“跳舞链”算法。

---

五、 堆 / 优先队列 (Heap / Priority Queue)

1. 核心概念 不管怎么插入，队首永远是最大值（或最小值）。底层是完全二叉树。

2. 语法细节

• 大根堆（默认）：priority_queue<int> q; （大的在 top）。
• 小根堆：priority_queue<int, vector<int>, greater<int>> q; （小的在 top）。

3. 竞赛实战

• 贪心算法：比如“合并果子”，每次合并最小的两堆。
• Dijkstra 算法：堆优化最短路，$O(E \log V)$。
• 动态维护中位数：对顶堆（一个大根堆+一个小根堆）。

---

六、 Map 与 Set (关联容器)

这两者底层通常是 红黑树 (Red-Black Tree)，操作复杂度稳定在 $O(\log N)$。

1. Set (集合)

• 特性：自动排序 + 自动去重。
• 用法：
  • insert(x): 插入。
  • find(x) / count(x): 查找是否存在。
  • lower_bound(x): 二分查找第一个 $\ge x$ 的元素。

2. Map (映射)

• 特性：键值对 key-value。相当于一个下标可以是任意类型的超级数组。
• 用法：
  • map<string, int> mp;
  • mp["apple"] = 5;
• 实战：统计字符串出现的次数、离散化（把大整数映射为小整数）。

⚠️ 教练提示：Unordered 系列 C++11 还有 unordered_map 和 unordered_set，底层是哈希表，平均 $O(1)$。

• 优点：快。
• 致命坑点：在 CF 或 NOIP 比赛中，可能会被出题人针对（构造哈希冲突数据），导致退化成 $O(N)$ 超时。建议优先用普通的 map/set，除非这就差那一点点时间。

---

总结速查表

数据结构	特性	核心用途	复杂度
Vector	动态数组	存图、不定长存储	访问 $O(1)$
Queue	先进先出	BFS、缓冲	$O(1)$
Stack	后进先出	单调栈、递归、匹配
List	插入删除快	链式前向星(数组模拟)	删/插 $O(1)$
Priority Queue	自动排序	贪心、Dijkstra	进/出 $O(\log N)$
Set	去重+排序	找前驱后继、去重	$O(\log N)$
Map	键值映射	离散化、字符串统计

把这些 STL 用熟练，你的代码量会减少一半，且 Bug 会大大减少！加油！