C++ STL：玩转列表容器，解锁高效编程的秘密武器

C++ list 容器详解：从入门到精通

???? 欢迎讨论：学习过程中有问题吗？随时在评论区与我交流。你们的互动是我创作的动力！

???? 支持我：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友吧！

???? 一起成长：欢迎分享给更多对 C++ 感兴趣的小伙伴，让我们共同进步！

前言

C++ 标准模板库（STL）中的 list 容器是一个双向链表结构，它提供了高效的插入和删除操
作。与 vector 不同，list 中的元素不是连续存储的，因此可以在任何位置高效插入和删除元素，而无需移动其他元素。虽然它在随机访问方面不如 vector 高效，但在大量的插入和删除操作场景中具有不可替代的优势。

本文将通过详细的示例代码，从基础到进阶，逐步讲解如何使用 C++ 中的 list 容器，并探讨其特性与常用操作。

---

第一章：C++ list 容器简介

1.1 C++ STL 容器概述

C++ 提供了丰富的标准模板库 (STL)，其中包括顺序容器（如 vector、deque）和关联容器（如 map、set）。list 是一种链表结构的顺序容器，它的底层实现是双向链表。这使得 list 在插入和删除操作上比 vector 更加高效，但由于不支持随机访问，因此访问特定位置的元素时效率较低。

1.2 list 的特点

• 双向链表：list 底层是一个双向链表，能够高效地进行插入和删除操作。
• 不支持随机访问：由于链表的结构特点，list 只能顺序访问，随机访问效率低下。
• 动态增长：list 不需要预留空间，它会根据需要动态分配内存。

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> lst = {1, 2, 3, 4, 5};
    for (int val : lst) {
        cout << val << " ";
    }
    return 0;
}

---

第二章：list 的构造方法

2.1 常见构造函数

C++ list 提供了多种构造函数，允许用户根据不同需求初始化链表。

构造函数	功能
list()	构造一个空的 list
list(size_type n, const T& val)	构造一个包含 n 个值为 val 的元素的 list
list(const list& x)	拷贝构造函数，构造与 x 相同的 list
list(InputIterator first, InputIterator last)	使用 [first, last) 区间内的元素构造 list

2.1.1 示例：不同构造方法

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1;                      // 空 list
    list<int> lst2(5, 100);              // 5个值为100的元素
    list<int> lst3(lst2);                // 拷贝构造
    list<int> lst4 = {1, 2, 3, 4, 5};    // 初始化列表

    for (int val : lst4) {
        cout << val << " ";              // 输出: 1 2 3 4 5
    }
    return 0;
}

2.1.2 相关文档

• C++ Reference: list constructor

---

第三章：list 迭代器的使用

list 支持多种迭代器类型，允许我们遍历、访问和修改链表中的元素。迭代器可以看作指向 list 中节点的指针，遍历时可以用迭代器依次访问链表中的每一个节点。

3.1 常见迭代器

迭代器类型	功能
begin()	返回指向链表第一个元素的迭代器
end()	返回指向链表末尾的迭代器
rbegin()	返回指向链表最后一个元素的反向迭代器
rend()	返回指向链表第一个元素之前的反向迭代器
cbegin()	返回常量迭代器，不能修改元素
cend()	返回常量迭代器，指向链表末尾

3.1.1 示例：使用正向和反向迭代器遍历 list

#include <iostream>
#include <list>
using namespace std;

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

    // 使用正向迭代器遍历
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";  // 输出: 1 2 3 4 5
    }
    cout << endl;

    // 使用反向迭代器遍历
    for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
        cout << *rit << " ";  // 输出: 5 4 3 2 1
    }
    cout << endl;

    return 0;
}

3.1.2 相关文档

• C++ Reference: list iterator

---

第四章：list 的容量与大小操作

4.1 容量管理接口

list 提供了常用的容量管理接口，方便用户操作链表的大小和判断链表状态。

方法名	功能描述
empty()	检测 list 是否为空
size()	返回 list 中元素的数量
max_size()	返回 list 可容纳的最大元素数
resize(n)	调整 list 的大小为 n

4.1.1 示例：容量操作

#include <iostream>
#include <list>
using namespace std;

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

    cout << "Size: " << lst.size() << endl; // 输出当前元素个数
    cout << "Is empty: " << (lst.empty() ? "Yes" : "No") << endl; // 判断是否为空

    lst.resize(3); // 调整大小为3，保留前3个元素

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 3
    }

    return 0;
}

4.1.2 相关文档

• C++ Reference: list size

---

第五章：list 的元素访问

5.1 元素访问方法

list 提供了几种常用的方法用于访问链表中的元素。

方法名	功能
front()	返回 list 的第一个元素
back()	返回 list 的最后一个元素

5.1.1 示例：访问第一个与最后一个元素

#include <iostream>
#include <list>
using namespace std;

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

    cout << "First element: " << lst.front() << endl; // 访问第一个元素
    cout << "Last element: " << lst.back() << endl;   // 访问最后一个元素

    return 0;
}

5.1.2 相关文档

• C++ Reference: list element access

---

第六章：list 的插入、删除与修改

6.1 插入操作

list 容器提供了多种插入操作，包括在前部、尾部插入元素，或在指定位置插入。与 vector 不同的是，list 插入时不需要移动其他元素，只修改指针，因此插入效率非常高。

方法名	功能描述
push_front()	在 list 的前部插入元素
push_back()	在 list 的末尾插入元素
insert(position, val)	在指定位置插入元素

6.1.1 示例：使用 push_back() 和 push_front() 插入元素

push_front() 和 push_back() 是将元素插入到链表前部和尾部的常用方法。由于 list 是双向链表，头部和尾部操作的效率都非常高，为 O(1)。

#include <iostream>
#include <list>
using namespace std;

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

    // 在前部插入元素
    lst.push_front(0);

    // 在末尾插入元素
    lst.push_back(4);

    for (int val : lst) {
        cout << val << " ";  // 输出: 0 1 2 3 4
    }

    return 0;
}

6.1.2 示例：使用 insert() 在指定位置插入元素

insert() 用于在链表中指定位置插入元素。该方法需要提供一个迭代器指向要插入的位置。

#include <iostream>
#include <list>
using namespace std;

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

    // 在第二个位置插入2
    auto it = lst.begin();
    ++it;
    lst.insert(it, 2);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 3 4 
    }

    return 0;
}

6.1.3 插入元素的常见问题

• 迭代器失效：在 list 中进行插入操作时，插入不会使已有迭代器失效，因为 list 是双向链表，插入时只修改指针。
• 尾部插入效率：在链表尾部插入元素的效率始终为 O(1)，无需移动其他元素，这点不同于 vector。
• 插入到特定位置的效率：虽然 insert() 操作本身是 O(1)，但查找特定插入位置的时间复杂度是 O(n)，这取决于你如何获取迭代器。

6.1.4 相关文档

• C++ Reference: list insertions

---

6.2 删除操作

list 提供了多种删除元素的方式，包括从前部和尾部删除，删除指定位置的元素，以及一次性清空整个链表。

方法名	功能描述
pop_front()	删除 list 的第一个元素
pop_back()	删除 list 的最后一个元素
erase()	删除指定位置的元素
clear()	清空 list

6.2.1 示例：删除 list 中的首尾元素

pop_front() 和 pop_back() 用于删除 list 中的第一个或最后一个元素。与插入操作类似，这两种操作的时间复杂度都是 O(1)，不会影响其他元素的指针。

#include <iostream>
#include <list>
using namespace std;

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

    // 删除第一个元素
    lst.pop_front();

    // 删除最后一个元素
    lst.pop_back();

    for (int val : lst) {
        cout << val << " ";  // 输出: 2 3 4
    }

    return 0;
}

6.2.2 示例：删除指定位置的元素

erase() 用于删除指定位置的元素。它需要提供一个指向该位置的迭代器。

#include <iostream>
#include <list>
using namespace std;

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

    // 查找要删除的元素
    auto it = lst.begin();
    advance(it, 2);  // 移动到第三个元素

    // 删除第三个元素
    lst.erase(it);

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 4 5
    }

    return 0;
}

6.2.3 示例：清空 list

clear() 是一种非常彻底的清除操作，它会删除 list 中的所有元素。值得注意的是，clear() 仅会删除有效节点，不会删除链表的头节点（即 list 对象本身）。

#include <iostream>
#include <list>
using namespace std;

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

    // 清空 list
    lst.clear();

    cout << "Size after clear: " << lst.size() << endl;  // 输出: 0
    cout << "Is list empty? " << (lst.empty() ? "Yes" : "No") << endl;  // 输出: Yes

    return 0;
}

6.2.4 删除操作的常见问题

• 迭代器失效：在 list 中，删除操作只会导致指向被删除元素的迭代器失效，其他迭代器不受影响。删除后如果需要继续使用迭代器，应该使用 erase() 的返回值，指向下一个有效元素。
• clear() 是否删除头节点：clear() 不会删除 list 的头节点。调用 clear() 后，list 对象依然存在，只是里面的所有元素被删除，list 的结构保持完好。

6.2.5 相关文档

• C++ Reference: list clear
• C++ Reference: list erase
• C++ Reference: list pop_back

---

6.3 修改操作

通过迭代器或者 list 提供的访问接口，用户可以直接修改链表中的元素。由于 list 不支持随机访问，所以修改操作通常需要遍历元素。

方法名	功能描述
front()	返回 list 中第一个元素
back()	返回 list 中最后一个元素
迭代器	通过迭代器访问修改元素

6.3.1 示例：修改 list 中的首尾元素

通过 front() 和 back()，可以分别访问并修改 list 中的第一个和最后一个元素。修改操作的时间复杂度为 O(1)。

#include <iostream>
#include <list>
using namespace std;

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

    // 修改第一个元素
    lst.front() = 10;

    // 修改最后一个元素
    lst.back() = 20;

    for (int val : lst) {
        cout << val << " ";  // 输出: 10 2 3 4 20
    }

    return 0;
}

6.3.2 示例：通过迭代器修改 list 中的元素

由于 list 不支持随机访问，修改中间位置的元素需要通过迭代器遍历找到目标位置。

#include <iostream>
#include <list>
using namespace std;

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

    // 使用迭代器修改第三个元素
    auto it = lst.begin();
    advance(it, 2);  // 移动到第三个元素
    *it = 30;

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 30 4 5
    }

    return 0;
}

6.3.3 修改操作的常见问题

• 效率问题：由于 list 是链表结构，访问中间元素时无法像 vector 一样通过下标随机访问，而是必须通过迭代器进行遍历，时间复杂度为 O(n)。
• advance() 函数用于将迭代器向前或向后移动指定的距离，这是 list 中最常用的访问与修改元素方式之一。由于 list 不能通过下标随机访问，迭代器的使用显得尤为重要。
• 避免无效访问：通过迭代器进行修改时，确保在修改过程中没有删除操作，否则迭代器可能失效，导致未定义行为。

---

第七章：list 的迭代器失效问题

list 的底层实现为双向链表，因此与 vector 不同，list 的插入和删除操作不会导致整体迭代器失效。具体来说：

• 插入操作：不会导致现有迭代器失效。
• 删除操作：仅导致被删除元素的迭代器失效，其他迭代器不会受影响。

7.1 删除操作导致的迭代器失效

删除操作会使指向被删除元素的迭代器失效，如果在删除元素后继续使用失效的迭代器，将会导致程序的未定义行为。因此，在执行删除操作后，我们必须重新更新迭代器。

7.1.1 示例：删除元素时正确的迭代器处理

#include <iostream>
#include <list>
using namespace std;

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

    // 查找并删除元素3
    auto it = lst.begin();
    while (it != lst.end()) {
        if (*it == 3) {
            it = lst.erase(it);  // 删除元素并获取下一个有效迭代器
        } else {
            ++it;  // 继续遍历
        }
    }

    for (int val : lst) {
        cout << val << " ";  // 输出: 1 2 4 5
    }

    return 0;
}

在上面的代码中，erase() 函数会返回一个指向被删除元素之后的迭代器，因此我们使用该返回值继续遍历。这是一种常见的迭代器删除操作的最佳实践，可以避免迭代器失效问题。

7.1.2 错误示例：删除后不更新迭代器

#include <iostream>
#include <list>
using namespace std;

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

    auto it = lst.begin();
    while (it != lst.end()) {
        if (*it == 3) {
            lst.erase(it);  // 删除元素，但未更新迭代器
            ++it;           // 错误：it 已经失效，导致未定义行为
        } else {
            ++it;
        }
    }

    return 0;
}

在这个错误的示例中，删除操作使 it 失效，但我们在下一个循环中继续使用了失效的 it，这会导致未定义行为，可能会引发程序崩溃。

7.1.3 相关文档

• C++ Reference: list erase

---

第八章：list 常见的其他修改操作

8.1 splice() 操作

splice() 是 list 特有的操作，它允许我们将一个 list 中的元素直接拼接到另一个 list 中，而不会重新分配内存或复制元素。该操作非常高效，因为它仅修改链表的指针。

方法名	功能描述
splice(position, x)	将 list x 的所有元素插入到当前 list 中
splice(position, x, it)	将 list x 中的 it 指定的元素插入到当前 list 中
splice(position, x, first, last)	将 x 中 [first, last) 区间的元素插入当前 list

8.1.1 示例：使用 splice() 操作

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst1 = {1, 2, 3};
    list<int> lst2 = {4, 5