std::list 详解：双向链表的实现、插入删除操作、splice 合并操作、与 vector 的对比

说实话，很多 C++ 开发者对 list 又爱又恨。爱它是因为插入删除真的快，恨它是因为……嗯，你随便遍历一下都可能踩坑。我刚开始用 STL 那会儿，也犯过不少低级错误。今天咱们就把 list 彻底聊透。

一、双向链表的核心特性

std::list 底层是双向链表。每个节点都存着指向前一个和后一个节点的指针。这意味着什么？

  • 插入和删除是 O(1) —— 只要你有迭代器指向那个位置
  • 随机访问是 O(n) —— 没有下标，只能一个个走
  • 迭代器不会失效 —— 除非你删了那个元素本身

我个人习惯把 list 想象成一串珠子。你可以在任意位置加一颗或取下一颗，但想找第 10 颗？得一颗颗数过去。

核心结论：list 适合频繁插入删除、但不需要随机访问的场景。比如任务队列、事件调度、或者某些缓存淘汰算法。

二、插入删除操作实战

先看一个简单的例子。我当年做网络消息队列时，就大量用了 list 来管理待处理的消息包。

#include <list>
#include <iostream>

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

    // 在头部插入
    lst.push_front(0);

    // 在尾部插入
    lst.push_back(6);

    // 在中间插入 —— 需要先找到位置
    auto it = lst.begin();
    std::advance(it, 3);  // 走到第 3 个位置
    lst.insert(it, 99);

    // 删除某个元素
    lst.remove(3);  // 删除所有值为 3 的元素

    // 删除某个迭代器指向的元素
    auto it2 = lst.begin();
    std::advance(it2, 2);
    lst.erase(it2);

    for (int v : lst) {
        std::cout << v << " ";
    }
    return 0;
}

这里有个坑，我必须要说。用 std::advance 走迭代器时，如果步数很大，性能会差。因为 list 的迭代器只能一步一步挪。我曾经在项目里写过 std::advance(it, 100000)，结果那行代码跑了快一秒……后来改成用 vector 了。

避坑指南：list 的 insert 和 erase 不会使其他迭代器失效（除了被删的那个）。这一点和 vector 完全不同。vector 插入可能导致所有迭代器失效，而 list 很安全。但注意，如果你在遍历时删除了当前元素，一定要先保存下一个迭代器。

三、splice 合并操作

splice 是 list 独有的杀手锏。它可以把一个 list 的节点直接「剪」到另一个 list 上，不需要拷贝数据，只是改改指针。效率极高。

我做过一个实时数据合并模块，需要把多个子线程的中间结果合并到主线程的 list 里。用 splice 几乎零开销，比 copy 快了一个数量级。

#include <list>
#include <iostream>

int main() {
    std::list<int> list1 = {1, 2, 3, 4, 5};
    std::list<int> list2 = {10, 20, 30};

    // 把 list2 的所有元素拼接到 list1 的末尾
    list1.splice(list1.end(), list2);

    // 此时 list2 为空
    std::cout << "list1: ";
    for (int v : list1) std::cout << v << " ";
    std::cout << "\nlist2 size: " << list2.size() << std::endl;

    // 也可以只拼接单个元素或一段范围
    std::list<int> list3 = {100, 200, 300};
    auto it = list3.begin();
    std::advance(it, 1);
    list1.splice(list1.begin(), list3, it, list3.end());

    std::cout << "after splice: ";
    for (int v : list1) std::cout << v << " ";
    return 0;
}

注意 splice 之后，源 list 中的节点就没了。它是转移，不是复制。如果你需要保留源数据，那就别用 splice。

小技巧：splice 的第三个重载版本可以只转移一个元素。比如你想把某个 list 中的特定节点移到另一个 list 的头部，用 splice 一步到位，比 erase + insert 快得多。

四、与 vector 的对比

这是面试高频题，也是实际选型时必须想清楚的问题。我直接画个表，一目了然。

特性 std::list std::vector
底层结构 双向链表 动态数组
随机访问 O(n)，不支持下标 O(1)，支持下标
头部插入 O(1) O(n)，需要移动所有元素
中间插入 O(1)（有迭代器） O(n)
尾部插入 O(1) O(1) 均摊
内存占用 每个节点额外两个指针 连续内存，几乎无额外开销
迭代器失效 仅被删的失效 插入/删除可能导致全部失效
缓存友好性 差（节点分散） 极好（连续内存）

你看完这个表，应该能明白：没有哪个容器是万能的。我见过有人用 list 存几百万个整数，结果遍历一次慢到怀疑人生。也见过有人用 vector 频繁在头部插入，性能惨不忍睹。

选型时问自己三个问题：

  1. 我需要随机访问吗？—— 需要就用 vector
  2. 我主要在头部或中间插入删除吗？—— 是就用 list
  3. 我关心内存和缓存吗？—— 关心就用 vector

五、知识体系结构图

下面这张图帮你理清 list 的核心知识点和决策逻辑。

std::list 双向链表结构 插入删除 O(1) 迭代器不失效 push_front/push_back insert / erase splice 合并 与 vector 对比：场景决定选择 频繁插入删除 → list | 随机访问 → vector

我的建议：如果你不确定用哪个，默认选 vector。等真的遇到性能瓶颈了，再考虑换成 list。因为 vector 的缓存友好性在现代 CPU 上优势太大了。我见过太多人一开始就用 list，结果遍历慢得离谱。

好了，list 的核心内容就这些。记住它的强项和弱项，选型时就不会纠结了。下一节咱们聊 deque，它是个很有意思的容器，兼具 list 和 vector 的部分优点。

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

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