常用数据结构

这篇是整个教程中最重要的一篇。算法题的本质就是对数据结构进行操作，如果你不熟悉 C++ 标准库提供的这些数据结构，看算法代码就会一头雾水。

好消息是，C++ 的标准模板库（STL）提供了非常丰富的容器，开箱即用，不用自己造轮子。你也不需要记住每个容器的所有 API，只需要掌握最常用的那几个方法就够了。用多了自然就记住了，忘了随时可以回来查。

有一点需要提前说明：不同数据结构的同一个操作，效率可能差很多。比如 vector 按索引取值很快，但在头部插入元素就很慢；list 正好反过来。选错数据结构或者调错方法，算法题可能会超时。

不过本篇先专注于用法，不深入讲时间复杂度。具体的复杂度分析和底层实现原理，会在后面的数据结构章节详细展开。

¶动态数组 vector

vector 是 C++ 中最常用的容器，相当于一个自动扩容的数组。

¶初始化方式

vector 有好几种初始化方式，下面列出最常用的几种：

#include <vector>
using namespace std;

// 空 vector
vector<int> v1;

// 指定大小，默认值为 0
vector<int> v2(5);       // {0, 0, 0, 0, 0}

// 指定大小和初始值
vector<int> v3(5, -1);   // {-1, -1, -1, -1, -1}

// 初始化列表
vector<int> v4 = {1, 2, 3, 4, 5};

// 二维 vector：3 行 4 列，初始值为 0
vector<vector<int>> grid(3, vector<int>(4, 0));

¶常用操作

insert 和 erase 的参数都是迭代器（可以理解为指向容器中某个元素的指针），不是索引。nums.begin() 指向第一个元素，nums.begin() + i 就是索引 i 的位置。这两个操作需要搬移元素，效率不高，尽量少用。

¶二维 vector

二维 vector 在表示矩阵、网格时非常常用：

¶字符串 string

string 是 C++ 标准库提供的字符串类，支持自动扩容、拼接、比较等操作，非常好用。

¶常用方法

注意 find 找不到时返回的是 string::npos，不是 -1。虽然它的值通常等于 -1 的无符号表示，但最好用 string::npos 来判断，这是标准写法。

¶字符串与数字转换

¶字符判断与转换

<cctype> 提供了一组判断和转换单个字符的函数，在处理字符串的算法题中经常用到：

¶双链表 list

list 是双向链表，在任意位置插入和删除都很快，但不支持下标随机访问。关于链表的底层原理，后面的 链表基本原理 会详细讲解。算法题中用得不多，但偶尔会遇到需要在中间频繁增删的场景。

list 没有 [] 运算符，不能像 vector 那样通过下标访问，只能通过迭代器遍历。这是链表的天然限制。

¶哈希表 unordered_map

unordered_map 是 C++ 中最常用的哈希表，存储键值对，增删查改效率都很高。关于哈希表的底层原理，后面的 哈希表核心原理 会详细讲解。

¶常用操作

unordered_map 在算法题中最常见的用途就是统计频率：

// 统计每个字符出现的次数
unordered_map<char, int> count;
string s = "hello";
for (char c : s) {
    count[c]++;
}

¶特别注意：访问不存在的键会自动插入

这是 C++ 新手最容易踩的坑之一。 用 [] 访问一个不存在的 key，unordered_map 会自动插入这个 key，value 为默认值（int 类型默认为 0）。

记住：想查 key 是否存在，用 contains()（或 count()）；想安全地取值，先判断再用 [] 取。 如果只是做计数（map[key]++），那自动插入 0 反而是好事，直接用就行。

¶有序表 map

map 和 unordered_map 的 API 基本一样，区别是 map 的 key 是有序的（按照 key 的自然顺序排列），并且额外提供了 lower_bound 和 upper_bound 来利用有序性。

map 的增删查改比 unordered_map 慢一些（底层是红黑树），但在需要有序性的场景下非常有用。关于红黑树和有序表的原理，后面的 二叉搜索树的应用 会详细讲解。

简单记：lower_bound(k) 找的是 >= k 的最小 key，upper_bound(k) 找的是 > k 的最小 key。

¶哈希集合 unordered_set

unordered_set 存储不重复的元素，主要用来去重和快速判断元素是否存在。

¶有序集合 set

set 和 unordered_set 的关系类似 map 和 unordered_map：set 中的元素是有序的，也提供了 lower_bound 和 upper_bound 方法。

¶队列 queue

队列是先进先出（FIFO）的数据结构，BFS（广度优先搜索）中必用。关于栈和队列的底层原理，后面的 队列/栈基本原理 会详细讲解。

注意：queue 的 pop() 没有返回值，如果想取出队头元素，需要先 front() 再 pop()。

¶双端队列 deque

deque 是双端队列，两头都可以进出，还支持下标随机访问。

¶栈 stack

栈是后进先出（LIFO）的数据结构，括号匹配、单调栈等算法题中大量使用。

和 queue 一样，stack 的 pop() 也没有返回值，想取栈顶元素要先 top() 再 pop()。

¶优先队列 priority_queue

priority_queue 基于二叉堆实现，每次 top() 取出的都是当前优先级最高的元素。默认是大顶堆（最大的在顶部），在 Dijkstra 最短路径、合并 K 个有序链表等算法题中大量使用。关于二叉堆的底层原理，后面的 二叉堆核心原理 会详细讲解。

小顶堆的声明 priority_queue<int, vector<int>, greater<int>> 比较长，但这是固定写法，记住就行。三个模板参数分别是：元素类型、底层容器、比较函数。

¶pair 与结构化绑定

¶pair 基本用法

pair 把两个值打包成一对，在算法题中经常用来存储坐标、键值对等。

¶结构化绑定 auto [k, v]

C++17 引入了结构化绑定，可以把 pair（以及其他结构）的成员直接拆开到独立变量中。遍历 map 的时候特别好用：

比起 entry.first、entry.second 这种写法，auto& [key, value] 清晰太多了，强烈建议用这种写法。

¶小结

把这篇的数据结构和它们的核心方法汇总一下：

不需要一次记住所有方法，用多了自然就熟了。下一篇会讲一些算法题中的实用技巧，比如排序、类型转换等。