45、STL与数据结构：栈、队列、链表、二叉树、图在STL中的实现

数据结构这东西，说起来抽象，用起来实在。我早年刚入行时，总觉得「栈就是后进先出，队列就是先进先出」——背得滚瓜烂熟，真写代码时却总在纠结「到底该用 vector 还是 list」。后来做多了才明白，STL 已经把最常用的数据结构封装好了，你只需要知道「什么时候用哪个」就行。

这一章，咱们就把栈、队列、链表、二叉树、图这五种结构，在 STL 里的实现方式捋一遍。嗯，图在 STL 里没有现成的容器，但我们可以用组合的方式搭出来。

一、栈：std::stack

栈，说白了就是「后进先出」的容器。你想想看，浏览器后退、函数调用、括号匹配，全是栈的功劳。

STL 里的 std::stack 是一个容器适配器，默认底层用 deque。你也可以指定用 vector 或 list。

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "栈顶元素: " << s.top() << "\n"; // 30
    s.pop();
    std::cout << "弹出后栈顶: " << s.top() << "\n"; // 20

    return 0;
}
我的习惯： 如果只是做简单的 LIFO 操作，直接用 stack 就好。但如果你需要遍历栈内元素，那就别用 stack 了——它不提供迭代器。我一般会改用 deque 或 vector 自己管理。
我曾经踩过的坑： 调用 top() 或 pop() 前，一定要检查 empty()。空栈上调用 top() 是未定义行为，程序可能直接崩掉。

二、队列：std::queue

队列是「先进先出」的结构。任务调度、消息队列、BFS 遍历，都离不开它。

std::queue 同样是容器适配器，默认底层也是 deque。

#include <queue>
#include <iostream>

int main() {
    std::queue<std::string> q;

    q.push("任务A");
    q.push("任务B");
    q.push("任务C");

    std::cout << "队首: " << q.front() << "\n"; // 任务A
    q.pop();
    std::cout << "出队后队首: " << q.front() << "\n"; // 任务B

    return 0;
}

还有一个 std::priority_queue，它内部用堆实现，每次取出的都是优先级最高的元素。我在项目中用它做过一个简单的任务调度器，效果不错。

#include <queue>
#include <vector>

int main() {
    // 默认是大顶堆
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(2);

    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 4 3 2 1
        pq.pop();
    }

    return 0;
}

三、链表：std::list 和 std::forward_list

链表在 STL 里有两个版本：std::list（双向链表）和 std::forward_list（单向链表）。

我个人更常用 list，因为双向迭代器用起来方便。但如果你对内存敏感，forward_list 更省空间——每个节点少一个指针。

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 在中间插入
    auto it = lst.begin();
    std::advance(it, 2); // 指向第3个元素
    lst.insert(it, 99);

    for (int x : lst) {
        std::cout << x << " "; // 1 2 99 3 4 5
    }

    return 0;
}
什么时候用 list？ 频繁在中间插入/删除，且不需要随机访问。如果你需要随机访问，vector 才是正解。我见过有人用 list 存几万个元素然后挨个遍历——性能其实不如 vector。

四、二叉树：std::set / std::map 与底层红黑树

STL 没有直接暴露「二叉树」这个容器，但 std::set、std::map、std::multiset、std::multimap 的底层都是红黑树——一种自平衡的二叉搜索树。

说白了，你只要用有序关联容器，就是在用二叉树。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {5, 1, 9, 3, 7};

    // 自动排序
    for (int x : s) {
        std::cout << x << " "; // 1 3 5 7 9
    }

    // 查找 O(log n)
    if (s.find(3) != s.end()) {
        std::cout << "\n找到了 3\n";
    }

    return 0;
}

map 也是同理，只不过每个节点存的是 key-value 对。

#include <map>

int main() {
    std::map<std::string, int> ages;
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n";
    }

    return 0;
}
避坑指南： 用 operator[] 访问 map 时，如果 key 不存在，它会自动插入一个默认值。我曾经因为这个 bug 排查了半天——明明只是想查一下，结果数据被改了。建议用 at() 或 find()。

五、图：STL 中没有，但可以组合实现

图是唯一一个 STL 没有直接提供的常用数据结构。不过别担心，用 vector + list/map 就能搭出来。

最常用的两种表示法：邻接表和邻接矩阵。

邻接表（推荐）

#include <vector>
#include <list>
#include <iostream>

class Graph {
    int V;                     // 顶点数
    std::vector<std::list<int>> adj; // 邻接表

public:
    Graph(int v) : V(v), adj(v) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图
    }

    void print() {
        for (int i = 0; i < V; ++i) {
            std::cout << i << ": ";
            for (int x : adj[i]) {
                std::cout << x << " ";
            }
            std::cout << "\n";
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(3, 4);

    g.print();
    return 0;
}

邻接矩阵（适合稠密图）

#include <vector>

class GraphMatrix {
    int V;
    std::vector<std::vector<bool>> mat;

public:
    GraphMatrix(int v) : V(v), mat(v, std::vector<bool>(v, false)) {}

    void addEdge(int u, int v) {
        mat[u][v] = true;
        mat[v][u] = true;
    }

    bool hasEdge(int u, int v) {
        return mat[u][v];
    }
};
我的建议： 大多数场景用邻接表。邻接矩阵虽然查找边是 O(1)，但空间是 O(V²)，顶点一多就扛不住了。我在项目中处理过 10 万个顶点的图，邻接矩阵直接爆内存，换成邻接表就没事了。

六、知识体系总览

下面这张图把本章的核心内容串起来了。你可以看到每种数据结构在 STL 中的对应容器，以及它们的核心特性。

STL 中的数据结构实现 栈 std::stack 队列 std::queue / priority_queue 链表 std::list / forward_list 二叉树 set / map (红黑树) 图 vector + list / vector + vector 核心特性对比 栈：LIFO，无迭代器，适配器模式 队列：FIFO，priority_queue 基于堆 链表：双向/单向，中间插入快，无随机访问 二叉树：有序，O(log n) 查找，红黑树自平衡 图：组合实现，邻接表 vs 邻接矩阵

七、总结与选择建议

说了这么多，最后给个实用建议：

  • 需要 LIFO → 用 stack
  • 需要 FIFO → 用 queue
  • 需要按优先级取 → 用 priority_queue
  • 频繁中间插入/删除 → 用 list
  • 需要有序且快速查找 → 用 set / map
  • 需要表示图结构 → 用 vector<list<int>> 或 vector<vector<int>>

嗯，其实 STL 的设计哲学就是「不要重复造轮子」。你想想看，这些数据结构如果让你手写，光是调试红黑树就能耗掉一周。直接用 STL 现成的，既稳定又高效，何乐而不为？

我在项目中见过太多人「为了用数据结构而用数据结构」——明明 vector 就能搞定，非要用 list；明明 map 就够用，非要手写哈希表。记住一句话：先选对容器，再谈优化。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →