C++ 常用数据结构：从内存布局到 STL 选择（图解版）

为什么需要一张“全景图”

学习数据结构时，容易把 vector、链表、堆、哈希表分别记成一些零散 API。更实用的理解方式是先问三个问题：

数据在内存中如何摆放：连续、分散，还是按节点连接？
最常做的操作是什么：按下标访问、查找、两端增删、取最值，还是维护连接关系？
是否需要顺序、重复元素、稳定迭代器或最坏时间保证？

下面这张图给出常用数据结构及其 C++ 对应物。后文既介绍抽象结构，也说明工程中应该优先使用哪个 STL 容器。

C++ 常用数据结构全景图

本文复杂度中的 n 表示元素个数，图中的 V、E 分别表示顶点数和边数。“平均 O(1)”不能直接等同于“永远 O(1)”。

先看结论：该选哪一种

需求	首选	关键原因
固定长度、栈上小数组	`std::array<T, N>`	连续内存，无动态分配
默认的可变长序列	`std::vector<T>`	缓存友好、随机访问 O(1)
两端频繁增删并需要下标	`std::deque<T>`	两端 O(1)，支持随机访问
已知位置频繁插入删除	`std::list<T>`	迭代器位置处 O(1)，但缓存局部性差
后进先出	`std::stack<T>`	语义明确的容器适配器
先进先出	`std::queue<T>`	语义明确的容器适配器
随时取最大值或最小值	`std::priority_queue<T>`	堆顶 O(1)，插入/弹出 O(log n)
键有序、需要范围查询	`std::map` / `std::set`	通常为平衡树，操作 O(log n)
只关心快速查找	`std::unordered_map` / `std::unordered_set`	哈希表，平均 O(1)
前缀查询或自动补全	Trie（自行实现或第三方库）	查询与字符串长度相关
表示网络、依赖或道路	邻接表 `vector<vector<...>>`	稀疏图节省空间
判断动态连通性	并查集（自行实现）	近似 O(1) 的合并和查询

一个很实用的默认规则是：序列先考虑 vector，键值查询再在 map 与 unordered_map 之间选择。不要仅凭某个操作的理论复杂度就使用链表；连续内存带来的缓存优势经常使 vector 更快。

一、数组与动态数组

1. 原生数组与 `std::array`

数组把相同类型的元素放在一段连续内存中。第 i 个元素的地址可由首地址加偏移量直接算出，因此下标访问是 O(1)。

下标       0       1       2       3
地址     1000    1004    1008    1012       （假设 int 占 4 字节）
数据    [  8  ][  3  ][  6  ][  1  ]
                  ↑
               a[1]

现代 C++ 中，固定长度数组通常优先写成：

#include <array>

std::array<int, 4> values{8, 3, 6, 1};
values[1] = 10;                 // O(1)，不检查越界
int x = values.at(2);           // O(1)，越界时抛出异常

std::array 的长度是类型的一部分，不能在运行时改变。它可以使用 STL 迭代器和算法，比裸数组更容易组合。

2. `std::vector`：默认的动态序列

vector 同样使用连续内存，但会额外维护元素个数 size 和已分配空间 capacity。尾部空间不足时，它会申请更大的连续区域，把旧元素移动或复制过去，然后释放旧区域。

vector 扩容动画：等待片刻可看到元素搬移

#include <vector>

std::vector<int> nums;
nums.reserve(1000);             // 已知规模时提前预留，减少扩容
nums.push_back(10);             // 摊还 O(1)
nums.emplace_back(20);          // 原地构造元素
int first = nums[0];            // O(1)
nums.insert(nums.begin(), 5);   // O(n)，后续元素需要移动

必须分清：

reserve(n) 改变 capacity，不创建元素，size 不变；
resize(n) 改变 size，会创建或销毁元素；
扩容后，指向旧元素的指针、引用和迭代器通常全部失效；
尾部删除不会自动归还容量，shrink_to_fit() 也只是非强制请求。

操作	数组 / `array`	`vector`
下标访问	O(1)	O(1)
尾部插入	不支持改变长度	摊还 O(1)
中间插入/删除	O(n)	O(n)
查找某个值	O(n)	O(n)

二、链表

链表的节点可以分散在内存各处，节点之间用指针连接。单链表只保存 next，双链表同时保存 prev 和 next。

单链表： head → [data|next] → [data|next] → [data|null]

双链表： null ← [prev|data|next] ⇄ [prev|data|next] → null

C++ 标准库提供：

std::forward_list<T>：单链表，内存开销较小，只能向前遍历；
std::list<T>：双链表，可以双向遍历和 O(1) 拼接。

#include <list>

std::list<int> xs{10, 20, 30};
auto pos = std::next(xs.begin());
xs.insert(pos, 15);             // 已经拿到 pos 时为 O(1)
xs.erase(pos);                  // 已经拿到 pos 时为 O(1)

“链表插入 O(1)”有一个经常被省略的前提：已经拥有插入位置的迭代器。如果先从头查找位置，查找仍是 O(n)。链表不能用 xs[i] 随机访问，而且每个节点都有指针开销，缓存局部性通常也弱于 vector。

更完整的节点实现与应用示例可参考已有笔记：链表。

三、栈、队列与双端队列

栈和队列描述的是受限制的访问规则，STL 用“容器适配器”提供它们：默认借助其他底层容器存储数据，而不暴露迭代器。

栈与队列操作动画

1. 栈 `std::stack`

栈遵循后进先出（LIFO），像一摞盘子。函数调用栈、撤销操作、括号匹配、DFS 都会用到它。

#include <stack>

std::stack<int> st;
st.push(10);                    // O(1)
st.push(20);
int x = st.top();               // 20，O(1)
st.pop();                       // 不返回被删除的值

2. 队列 `std::queue`

队列遵循先进先出（FIFO），适合任务调度、消息缓冲和 BFS。

#include <queue>

std::queue<int> jobs;
jobs.push(10);                  // 从队尾进入
jobs.push(20);
int x = jobs.front();           // 10，从队头观察
jobs.pop();                     // 删除 10

3. 双端队列 `std::deque`

deque 支持头尾 O(1) 插入删除，也支持 O(1) 下标访问。它通常由多个固定大小的连续块组成，并不保证所有元素处在同一整段内存中，所以不能把它当作连续数组传给只接受 T* 的接口。

#include <deque>

std::deque<int> q{2, 3};
q.push_front(1);
q.push_back(4);
q.pop_front();

四、树、集合与映射

树表达层次关系。每个节点除数据外，还保存到子节点的边。二叉树规定每个节点最多有两个孩子；二叉搜索树（BST）进一步规定左子树的键小于根，右子树的键大于根。

二叉搜索树、最小堆与哈希表对比

普通 BST 如果按 1, 2, 3, 4... 插入，会退化成链表，查找从 O(log n) 变成 O(n)。因此工程中通常使用自平衡树。std::set 和 std::map 一般由红黑树等平衡搜索树实现；标准只约束复杂度和行为，不强制具体实现。

#include <map>
#include <set>

std::set<int> ids{8, 3, 8, 1}; // 自动去重并按升序保存：1, 3, 8

std::map<std::string, int> age;
age["Alice"] = 20;             // 不存在时会插入默认值再赋值
age.insert_or_assign("Bob", 21);

auto it = age.lower_bound("B"); // 第一个不小于 "B" 的键，O(log n)

四种常见有序关联容器如下：

容器	键是否重复	保存内容	查找/插入/删除
`set`	否	键	O(log n)
`multiset`	是	键	O(log n)
`map`	否	键值对	O(log n)
`multimap`	是	键值对	O(log n)

需要范围查询、按键排序、lower_bound，或者需要稳定的最坏复杂度时，优先选择有序关联容器。

五、堆与优先队列

堆是一棵完全二叉树，通常紧凑地存进数组。最小堆只保证“父节点不大于孩子”，最大堆则相反；它不保证左右子树之间整体有序。

数组下标从 0 开始时，节点 i 的关系为：

父节点：(i - 1) / 2
左孩子：2 * i + 1
右孩子：2 * i + 2

STL 的 priority_queue 默认是最大堆：

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<int> max_heap;
max_heap.push(3);
max_heap.push(8);
max_heap.push(5);
int largest = max_heap.top();   // 8，O(1)

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(3);
min_heap.push(8);
min_heap.push(5);
int smallest = min_heap.top();  // 3

堆适合 Top-K、任务优先级、Dijkstra 算法。它擅长取极值，却不适合查找任意元素：任意值查找仍可能是 O(n)。

六、哈希表

哈希表通过哈希函数把键映射到桶（bucket）。理想情况下，查找、插入和删除平均为 O(1)；不同键落到同一个桶时会发生冲突，容器需要用链式结构或其他策略处理。

#include <string>
#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores.reserve(1000);           // 可减少反复 rehash
scores["Alice"] = 95;

if (auto it = scores.find("Alice"); it != scores.end()) {
    int score = it->second;
}

unordered_map 不维护排序，遍历顺序也不应被依赖。元素增多触发 rehash 时，桶会重建，迭代器可能失效。自定义键需要同时给出相等判断和哈希函数。

struct Point {
    int x;
    int y;
    bool operator==(const Point&) const = default;
};

struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t h1 = std::hash<int>{}(p.x);
        std::size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);
    }
};

std::unordered_map<Point, std::string, PointHash> labels;

特性	`map`	`unordered_map`
内部逻辑	平衡搜索树	哈希表
顺序	按键有序	无序
查找	O(log n)	平均 O(1)，最坏 O(n)
范围查询	支持	不支持
自定义键要求	严格弱序比较	相等判断 + 哈希

七、Trie 前缀树

Trie 把字符串的每个字符放在一层节点上，共享相同前缀。查找复杂度主要取决于字符串长度 L，约为 O(L)，而不是已存单词数。

root
 ├─ c ─ a ─ t*       cat
 │       └─ r*       car
 └─ d ─ o ─ g*       dog

* 表示一个完整单词在此结束

简化实现如下，字符集很大或节点稀疏时，可把定长孩子数组换成 unordered_map<char, unique_ptr<Node>>：

#include <array>
#include <memory>
#include <string_view>

class Trie {
    struct Node {
        std::array<std::unique_ptr<Node>, 26> child{};
        bool is_word = false;
    };
    Node root_;

public:
    void insert(std::string_view word) {
        Node* p = &root_;
        for (char c : word) {
            auto& next = p->child[c - 'a'];
            if (!next) next = std::make_unique<Node>();
            p = next.get();
        }
        p->is_word = true;
    }

    bool contains(std::string_view word) const {
        const Node* p = &root_;
        for (char c : word) {
            const auto& next = p->child[c - 'a'];
            if (!next) return false;
            p = next.get();
        }
        return p->is_word;
    }
};

Trie 适合自动补全、词典和路由前缀匹配，代价是节点及孩子指针可能消耗较多内存。

八、图：邻接表与邻接矩阵

图由顶点（vertex）和边（edge）组成，可表示道路、社交关系、机器人状态转移、软件依赖等。边可以有向或无向，也可以带权重。

图的 BFS 分层遍历动画

1. 邻接表

邻接表为每个顶点保存其邻居，空间复杂度为 O(V + E)，适合大多数稀疏图。

#include <queue>
#include <vector>

using Graph = std::vector<std::vector<int>>;

std::vector<int> bfs(const Graph& graph, int start) {
    std::vector<int> order;
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> pending;

    visited[start] = true;       // 入队时标记，避免重复入队
    pending.push(start);

    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        order.push_back(u);

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                pending.push(v);
            }
        }
    }
    return order;
}

2. 邻接矩阵

邻接矩阵用 matrix[u][v] 表示两点是否相连或边权，判断一条边是否存在为 O(1)，但空间固定为 O(V²)，适合顶点较少且边很密集的图。

操作	邻接表	邻接矩阵
空间	O(V + E)	O(V²)
判断 `(u,v)` 是否有边	O(deg(u))	O(1)
遍历 `u` 的邻居	O(deg(u))	O(V)
适合	稀疏图	稠密图、小图

BFS 使用队列，适合无权图最短步数；DFS 使用递归或显式栈，适合连通性、环检测、拓扑相关问题。两者遍历邻接表图的复杂度均为 O(V + E)。

九、并查集（Disjoint Set Union）

并查集维护若干互不相交的集合，支持两个核心操作：查询某个元素属于哪个集合，以及合并两个集合。它适合动态连通性、Kruskal 最小生成树和网格连通区域问题。

#include <numeric>
#include <vector>

class DisjointSet {
    std::vector<int> parent_;
    std::vector<int> size_;

public:
    explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int find(int x) {
        if (parent_[x] != x) {
            parent_[x] = find(parent_[x]); // 路径压缩
        }
        return parent_[x];
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size_[a] < size_[b]) std::swap(a, b);
        parent_[b] = a;                   // 小树挂到大树下
        size_[a] += size_[b];
        return true;
    }

    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};

同时使用路径压缩与按大小合并后，单次操作的均摊复杂度为 O(α(n))；反阿克曼函数 α(n) 增长极慢，工程上可近似理解为常数。

十、复杂度速查表

数据结构	随机访问	查找	头部增删	尾部增删	已知位置增删
`array`	O(1)	O(n)	不改变长度	不改变长度	不改变长度
`vector`	O(1)	O(n)	O(n)	摊还 O(1)	O(n)
`deque`	O(1)	O(n)	O(1)	O(1)	O(n)
`list`	O(n)	O(n)	O(1)	O(1)	O(1)
`set` / `map`	不适用	O(log n)	不适用	不适用	O(log n)
`unordered_set` / `unordered_map`	不适用	平均 O(1)	不适用	不适用	平均 O(1)

这里 list 的“已知位置增删”指已经持有有效迭代器；unordered_* 的复杂度是平均情况；vector 尾插是均摊复杂度。

十一、容易混淆的几个结论

数据结构不等于 STL 容器。 栈、队列是抽象访问规则；std::stack、std::queue 是其标准库接口。
O(1) 不代表一定更快。 哈希计算、内存分配、缓存未命中和常数项都会影响真实速度。
list 的插入并非无条件 O(1)。 找位置需要 O(n)，只有拿到位置后链接节点是 O(1)。
priority_queue 不是完全排序的数组。 只能保证 top() 是极值。
map 与 unordered_map 不只是 O(log n) 和 O(1) 的差别。 是否有序、是否范围查询、内存开销、最坏情况保证都不同。
不要依赖 unordered_map 的遍历顺序。 插入或 rehash 后顺序可能变化。
避免手写裸 new / delete 管理节点。 学习实现时可以练习，工程代码应优先使用标准容器或智能指针明确所有权。

十二、建议的学习顺序

可以用同一组小任务逐层练习：

用 array 和 vector 完成遍历、查找、插入；
手写一次单链表以理解指针，再回到 list 对比；
用 stack 做括号匹配，用 queue 做层序遍历；
用 map 统计有序词频，再换成 unordered_map 比较；
用 priority_queue 做 Top-K；
用邻接表实现 BFS 和 DFS；
最后实现 Trie 与并查集，体会“针对特殊查询设计结构”。

进一步了解 STL 容器的接口和示例，可继续阅读：C++ 中的容器。

参考资料

cppreference：C++ 标准库容器与复杂度说明；
《数据结构（C++ 语言版）》——邓俊辉；
《数据结构与算法图解》——Jay Wengrow；
Hello 算法：数组、链表、树、堆、图等章节。