前言

std::list 是STL提供的双向链表容器。与 vector 不同，list 不支持随机访问，但在任意位置的插入和删除操作都是O(1)的。本文将详细讲解 list 的用法、特有操作，以及何时该选择 list 而非 vector。

基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <list>

int main() {
    // 创建与初始化
    std::list<int> l1;                  // 空链表
    std::list<int> l2(5, 10);           // 5个10
    std::list<int> l3 = {1, 2, 3, 4};   // 列表初始化
    std::list<int> l4(l3.begin(), l3.end()); // 迭代器范围
    std::list<int> l5(l3);              // 拷贝构造

    // 添加元素
    l1.push_back(10);     // 尾部添加
    l1.push_front(20);    // 头部添加
    l1.insert(l1.begin(), 30);  // 在指定位置插入

    // 删除元素
    l1.pop_back();        // 尾部删除
    l1.pop_front();       // 头部删除
    l1.erase(l1.begin()); // 删除指定位置

    // 访问元素（不支持[]和at！）
    std::cout << l1.front() << std::endl;  // 首元素
    std::cout << l1.back() << std::endl;   // 尾元素

    // 大小
    std::cout << l1.size() << std::endl;
    std::cout << std::boolalpha << l1.empty() << std::endl;

    return 0;
}

注意：list 不支持 operator[] 和 at()，因为链表不支持O(1)随机访问。要访问第n个元素，需要遍历。

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <list>

int main() {
    std::list<int> l = {10, 20, 30, 40, 50};

    // 迭代器遍历
    for (auto it = l.begin(); it != l.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 范围for循环
    for (const auto& x : l) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 反向遍历
    for (auto it = l.rbegin(); it != l.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    // 输出: 50 40 30 20 10

    return 0;
}

特有操作

list 提供了一些其他序列容器没有的成员函数，这些操作利用了链表结构的优势。

splice：转移节点（O(1)）

splice 是 list 最强大的操作之一，它能在不拷贝数据的情况下将元素从一个链表转移到另一个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <list>

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

    // 将list2的全部元素插入到list1的第2个位置
    auto pos = list1.begin();
    std::advance(pos, 2);  // pos指向3
    list1.splice(pos, list2);

    std::cout << "list1: ";
    for (int x : list1) std::cout << x << " ";
    std::cout << std::endl;
    // list1: 1 2 10 20 30 3 4 5

    std::cout << "list2 size: " << list2.size() << std::endl;
    // list2 size: 0 （已被移空！）

    // 转移单个元素
    std::list<int> list3 = {100, 200};
    list1.splice(list1.begin(), list3, list3.begin());
    std::cout << "list1: ";
    for (int x : list1) std::cout << x << " ";
    std::cout << std::endl;
    // list1: 100 1 2 10 20 30 3 4 5

    return 0;
}

重点：splice 不涉及任何数据拷贝或内存分配，它只是修改指针。这是链表相对于数组的独特优势。

merge：合并有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <list>

int main() {
    std::list<int> l1 = {1, 3, 5, 7};
    std::list<int> l2 = {2, 4, 6, 8};

    l1.merge(l2);  // l2的元素被合并到l1中，l2变空
    // l1: {1, 2, 3, 4, 5, 6, 7, 8}

    std::cout << "合并后: ";
    for (int x : l1) std::cout << x << " ";
    std::cout << std::endl;

    // 自定义排序规则的merge
    std::list<int> a = {5, 3, 1};
    std::list<int> b = {4, 2};
    a.sort(std::greater<int>());  // 降序排列: {5, 3, 1}
    b.sort(std::greater<int>());  // {4, 2}
    a.merge(b, std::greater<int>());  // {5, 4, 3, 2, 1}

    std::cout << "降序合并: ";
    for (int x : a) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

sort：链表排序

list 提供了自己的 sort 成员函数（因为STL通用算法 std::sort 需要随机访问迭代器）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <list>

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

    l.sort();  // 默认升序
    std::cout << "升序: ";
    for (int x : l) std::cout << x << " ";
    std::cout << std::endl;

    l.sort(std::greater<int>());  // 降序
    std::cout << "降序: ";
    for (int x : l) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

其他特有操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <list>

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

    // remove - 删除所有等于指定值的元素
    l.remove(2);
    // l: {1, 3, 4, 5}

    // remove_if - 删除满足条件的元素
    l.remove_if([](int x) { return x % 2 == 0; });
    // l: {1, 3, 5}

    // unique - 删除相邻的重复元素
    std::list<int> l2 = {1, 1, 2, 2, 2, 3, 1, 1};
    l2.unique();
    // l2: {1, 2, 3, 1}

    // reverse - 反转
    l2.reverse();
    // l2: {1, 3, 2, 1}

    for (int x : l2) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

注意：unique 只删除相邻的重复元素。如果要删除所有重复，需要先排序再调用 unique。

迭代器失效

与 vector 不同，list 的插入操作不会使任何迭代器失效（除了被删除元素的迭代器）。这是一个重要优势：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <list>

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

    auto it = l.begin();
    std::advance(it, 2);  // it 指向 3

    l.insert(l.begin(), 0);  // 头部插入
    // it 仍然有效，仍然指向 3
    std::cout << *it << std::endl;  // 3

    l.erase(l.begin());
    // 仅被删除元素的迭代器失效，it仍然有效
    std::cout << *it << std::endl;  // 3

    return 0;
}

list vs vector：如何选择？

特性 vector list
随机访问 O(1) O(n)
尾部插入/删除 均摊O(1) O(1)
头部插入/删除 O(n) O(1)
中间插入/删除 O(n) O(1)（找到位置后）
内存连续 是 否
缓存友好 高 低
迭代器类型 随机访问 双向
额外内存开销 小 大（每个节点两个指针）

选择建议：

  1. **默认用 vector**：缓存命中率高，内存紧凑，随机访问快，现代CPU对此非常友好。
  2. 用 list 的场景：
    • 频繁在中间插入/删除且不需要随机访问
    • 需要 splice 操作转移节点
    • 元素很大，移动代价高（list 只修改指针）
  3. 避免用 list 的场景：
    • 需要排序（list::sort 性能不如 vector + std::sort）
    • 需要随机访问
    • 元素较小（指针开销占比大）

常见陷阱

1. 试图用下标访问

1
2
3
4
5
6
7
8
std::list<int> l = {1, 2, 3};
// l[0];  // 编译错误！list没有operator[]
// l.at(0);  // 编译错误！

// 正确做法
auto it = l.begin();
std::advance(it, 0);
std::cout << *it << std::endl;  // 1

2. 使用std::sort排序list

1
2
3
std::list<int> l = {3, 1, 2};
// std::sort(l.begin(), l.end());  // 编译错误！list迭代器不支持随机访问
l.sort();  // 正确：使用成员函数

3. unique不能去重所有元素

1
2
3
4
5
6
std::list<int> l = {1, 2, 1, 2, 1};
l.unique();  // 只删除相邻重复 -> {1, 2, 1, 2, 1}，没有任何变化！

// 正确去重方法
l.sort();
l.unique();  // 先排序再unique -> {1, 2}

小结

list 是双向链表的STL实现，它的强项在于任意位置的O(1)插入删除和 splice 操作。但在实际开发中，vector 由于缓存友好性，在大多数场景下性能更好。只有在明确需要链表特性时才选择 list。下一篇我们将介绍 deque——结合了 vector 和 list 部分优点的容器。