list高级应用：splice、unique与forward_list对比

说实话，list 在 STL 里算是个「老古董」了。很多人觉得它不如 vector 好用，甚至有人说「能用 vector 就别用 list」。但我不这么看。

我在项目中遇到过几次必须用 list 的场景——比如需要频繁在中间插入删除，或者要合并两个链表。这时候 splice 和 unique 就派上大用场了。今天咱们就聊聊这两个操作，再跟 forward_list 做个对比。

一、splice：链表的「乾坤大挪移」

splice 是 list 独有的操作。它的核心思想是：把一段链表「粘」到另一个链表上。注意，不是拷贝，是直接转移节点。所以它非常快——O(1) 时间复杂度。

关键点：splice 不拷贝元素，只调整指针。源链表中的节点会被移除。

我刚开始用 splice 时犯过一个错：以为 splice 之后源链表还在。结果调试了半天才发现节点被「偷」走了。嗯，这里要注意。

splice 的三种形式

#include <list>
#include <iostream>

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

    // 形式1：将 list2 全部转移到 list1 末尾
    list1.splice(list1.end(), list2);
    // list1: 1 2 3 4 5 10 20 30
    // list2: 空

    // 形式2：将 list2 的单个元素转移到 list1 的指定位置
    std::list<int> list3 = {100, 200};
    auto it = list1.begin();
    std::advance(it, 2);  // 指向 3
    list1.splice(it, list3, list3.begin());
    // list1: 1 2 100 3 4 5 10 20 30
    // list3: 200

    // 形式3：将 list2 的一段范围转移到 list1
    std::list<int> list4 = {1000, 2000, 3000};
    auto start = list4.begin();
    auto end = list4.end();
    std::advance(start, 1);  // 指向 2000
    list1.splice(list1.begin(), list4, start, end);
    // list1: 2000 3000 1 2 100 3 4 5 10 20 30
    // list4: 1000

    return 0;
}

我的习惯：在需要合并两个有序链表时，我通常先用 splice 把元素「搬」过来，再调用 sort。比一个个 insert 快得多。

二、unique：去除连续重复元素

unique 的作用很简单：删除链表中连续重复的元素。注意是「连续重复」，不是「所有重复」。比如 [1, 1, 2, 1] 调用 unique 后变成 [1, 2, 1]——中间的 1 被去掉了，但末尾的 1 保留。

为什么会这样？因为 unique 只比较相邻元素。如果你想去掉所有重复，得先排序。

#include <list>
#include <iostream>

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

    // 默认版本：使用 operator==
    lst.unique();
    // lst: 1 2 3 1 4

    // 带谓词版本：自定义比较规则
    std::list<int> lst2 = {1, 2, 3, 4, 5, 6};
    lst2.unique([](int a, int b) {
        return (a % 2) == (b % 2);  // 相邻奇偶性相同则删除
    });
    // lst2: 1 2 3 4 5 6  (因为相邻元素奇偶性都不同，所以没变化)

    return 0;
}

我曾经踩过的坑：unique 不会改变链表大小，它只是把「被删除」的元素移到链表末尾，然后返回一个指向新末尾的迭代器。如果你不关心这些元素，可以直接 erase。否则它们还在那里。

三、list vs forward_list：一图看懂区别

先看一张结构对比图，我画了张 SVG 帮你理解：

std::list（双向链表） prev data next prev data next prev data next 双向遍历 std::forward_list（单向链表） data next data next data next 只能单向遍历 核心区别 特性 list forward_list 内存开销 每个节点 3 个指针 每个节点 2 个指针

从图上能看出来，list 每个节点有 prev 和 next 两个指针，而 forward_list 只有 next 指针。这带来几个关键区别：

特性 std::list std::forward_list
内存开销 每个节点 3 个指针（prev, data, next） 每个节点 2 个指针（data, next）
遍历方向 双向（前向 + 反向） 单向（只能前向）
size() 方法 有，O(1) 没有，需要自己遍历计数
插入/删除 任意位置 O(1) 只能在当前元素之后 O(1)
splice 支持 完整支持 有限支持（只有 splice_after）
适用场景 需要双向遍历、频繁在中间操作 内存敏感、只需单向遍历

我的建议：如果你不确定用哪个，默认选 list。forward_list 的「坑」比较多——没有 size()、只能在当前元素之后插入、splice 只能用 splice_after。除非你明确知道内存是瓶颈，否则别为了省那一点内存给自己找麻烦。

四、实战：用 splice 和 unique 处理数据

最后分享一个我在项目中用过的场景：合并两个有序链表并去重。

#include <list>
#include <iostream>

int main() {
    std::list<int> listA = {1, 3, 5, 7, 9};
    std::list<int> listB = {2, 3, 5, 8, 10};

    // 先把 listB 全部 splice 到 listA 末尾
    listA.splice(listA.end(), listB);

    // 排序
    listA.sort();

    // 去重（连续重复）
    listA.unique();

    // 输出：1 2 3 5 7 8 9 10
    for (int x : listA) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

你看，splice 负责「搬家」，sort 负责「排序」，unique 负责「去重」。三个操作配合起来，处理链表数据非常顺手。

注意：unique 只去除「连续重复」。如果链表没排序，重复元素可能分散在各处，unique 不会全部去掉。所以先排序再 unique 是常见套路。

好了，关于 list 的 splice、unique 以及和 forward_list 的对比，就聊到这儿。说白了，list 是个「老派但可靠」的工具，splice 和 unique 是它的看家本领。forward_list 则是个「轻量级选手」，适合特定场景。你想想看，你的项目里有没有可以用 splice 优化的地方？

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

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