C++ std::list

std::list 是 C++ STL 中基于双向链表实现的序列容器，其设计目标是提供高效的任意位置插入 / 删除操作。

1、底层结构与核心原理

1.1 节点与链表结构

节点组成：每个元素存储在独立的节点中，节点包含三部分

template <typename T>
struct ListNode {T data;          // 元素值ListNode* prev;  // 指向前驱节点ListNode* next;  // 指向后继节点
};

容器内部指针：std::list 维护两个关键指针：

• head：指向第一个节点（首节点）。
• tail：指向最后一个节点（尾节点）。

1.2 核心特性

1. 非连续存储

   • 元素分散在内存的各个地方，不像vector或array是连续块。

2. 高效的插入与删除 (O(1))

   • 在任何已知位置（通过迭代器指定）的插入和删除操作都是常数时间复杂度。
   • 操作仅涉及指针的重新赋值，不需要移动任何其他元素。
     • 插入：新分配一个节点，然后调整相邻节点的指针指向这个新节点。
     • 删除：调整目标节点前后节点的指针，让它们彼此指向对方，然后释放目标节点的内存。

3. 迭代器稳定性

   • 这是list最强大的特性之一。插入操作不会使任何现有的迭代器、指针或引用失效。
   • 删除操作只会使指向被删除元素的迭代器、指针或引用失效，其他元素的迭代器仍然完全有效。
   • 这与vector和deque形成鲜明对比，后者在插入/删除时极易导致迭代器大面积失效。

4. 不支持随机访问 (O(n))

   • 无法使用[]运算符或at()方法直接访问第n个元素。
   • 访问某个特定位置的元素需要从begin()或end()开始逐步递增或递减迭代器，时间复杂度为线性O(n)。

2、常用操作与示例代码

2.1 初始化

#include <list>
#include <iostream>// 1. 空list
std::list<int> list1;// 2. 包含 n 个元素，每个元素使用默认值初始化 (int 为 0)
std::list<int> list2(5); // {0, 0, 0, 0, 0}// 3. 包含 n 个元素，每个元素都是 value
std::list<int> list3(5, 100); // {100, 100, 100, 100, 100}// 4. 通过初始化列表 (C++11)
std::list<int> list4 = {1, 2, 3, 4, 5};// 5. 通过迭代器范围（另一个容器的）
std::vector<int> vec = {6, 7, 8};
std::list<int> list5(vec.begin(), vec.end()); // {6, 7, 8}// 6. 拷贝构造函数
std::list<int> list6(list4); // {1, 2, 3, 4, 5}

2.2 元素访问

std::list<int> l = {10, 20, 30};// 访问第一个和最后一个元素
std::cout << l.front(); // 10
std::cout << l.back();  // 30// 错误！list不支持随机访问
// int a = l[1];
// int b = l.at(1);// 正确但低效的方法：使用迭代器步进
auto it = l.begin();
std::advance(it, 1); // 将迭代器 it 前进 1 步，现在指向 20
std::cout << *it;    // 20
// 注意：advance(it, n) 对于list是O(n)操作

2.3 增加元素

std::list<int> l = {1, 2, 3};// 在尾部添加
l.push_back(4);   // {1, 2, 3, 4} - 拷贝或移动
l.emplace_back(5); // {1, 2, 3, 4, 5} - 原地构造，更高效// 在头部添加
l.push_front(0);   // {0, 1, 2, 3, 4, 5}
l.emplace_front(-1); // {-1, 0, 1, 2, 3, 4, 5}// 在指定位置插入
auto it = l.begin();
std::advance(it, 3); // it 现在指向 2
l.insert(it, 99);    // 在 2 之前插入 99 -> {-1, 0, 1, 99, 2, 3, 4, 5}
l.emplace(it, 88);   // 同理，但原地构造 -> {-1, 0, 1, 99, 88, 2, 3, 4, 5}// 插入多个值或一个区间
l.insert(it, 3, 77); // 在 it 前插入 3 个 77
std::vector<int> v = {55, 66};
l.insert(it, v.begin(), v.end()); // 插入一个区间

2.4 删除元素

std::list<int> l = {-1, 0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5};// 删除头部元素
l.pop_front(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4, 5}// 删除尾部元素
l.pop_back(); // {0, 1, 77, 77, 77, 55, 66, 88, 2, 3, 4}// 删除指定位置的元素
auto it = l.begin();
std::advance(it, 3);
it = l.erase(it); // 删除第三个元素（第一个77），erase返回被删除元素的下一个元素的迭代器
// l: {0, 1, 77, 77, 55, 66, 88, 2, 3, 4}// 删除一个区间的元素 [first, last)
auto first = l.begin();
auto last = l.begin();
std::advance(first, 1);
std::advance(last, 4);
l.erase(first, last); // 删除 [第二个元素1, 第五个元素55) 之间的元素（左闭右开）
// l: {0, 55, 66, 88, 2, 3, 4}// 删除所有值等于特定值的元素
l.remove(88); // l: {0, 55, 66, 2, 3, 4}// 删除满足条件的所有元素（例如，删除所有偶数）
l.remove_if([](int n) { return n % 2 == 0; }); // 使用Lambda表达式
// l: {55, 3}// 删除所有元素
l.clear();

2.5 大小与容量操作

std::list<int> l = {1, 2, 3};
std::cout << l.size(); // 3
std::cout << l.empty(); // false (0)l.resize(5); // 将大小增大到5，新增的元素默认初始化为0 -> {1, 2, 3, 0, 0}
l.resize(2); // 将大小减小到2，尾部的元素被丢弃 -> {1, 2}
l.resize(4, 99); // 将大小增大到4，新增的元素初始化为99 -> {1, 2, 99, 99}// list 没有 capacity() 和 reserve() 概念，因为内存是动态按需分配的。

2.6 splice：转移元素的神器

// 将另一个list的元素转移到本list中，不涉及元素的拷贝或移动，只改变指针。
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};auto it = list1.begin();
std::advance(it, 1); // it 指向 2// 1. 转移整个list2到list1的it位置之前
list1.splice(it, list2);
// list1: {1, 4, 5, 6, 2, 3}
// list2: (空)// 2. 转移另一个list中的单个元素
std::list<int> list3 = {7, 8, 9};
auto it3 = list3.begin(); // it3 指向 7
list1.splice(list1.begin(), list3, it3); // 将list3的it3元素转移到list1开头
// list1: {7, 1, 4, 5, 6, 2, 3}
// list3: {8, 9}// 3. 转移另一个list中的一个元素范围
std::list<int> list4 = {10, 11, 12, 13};
auto first4 = list4.begin(); // 10
auto last4 = first4;
std::advance(last4, 2); // 12
list1.splice(list1.end(), list4, first4, last4); // 转移[10, 11)（左闭右开）
// list1: {7, 1, 4, 5, 6, 2, 3, 10, 11}
// list4: {12, 13}

2.7 sort：成员函数排序

std::list<int> l = {3, 1, 4, 1, 5};
l.sort(); // 默认升序 -> {1, 1, 3, 4, 5}
l.sort(std::greater<int>()); // 传入比较函数，降序 -> {5, 4, 3, 1, 1}
// 使用成员函数sort而不是std::sort，因为它通过修改指针链接而非移动元素来排序，对list更高效。

2.8 merge：合并两个已排序的list

std::list<int> listA = {1, 3, 5};
std::list<int> listB = {2, 4, 6};
listA.merge(listB); // 将listB合并到listA中，两个list都必须已按升序排序。
// listA: {1, 2, 3, 4, 5, 6}
// listB: (空)

2.9 unique：去除连续的重复元素

std::list<int> l = {1, 1, 2, 3, 3, 3, 2, 1};
l.sort(); // 先排序 -> {1, 1, 1, 2, 2, 3, 3, 3}
l.unique(); // 去除连续的重复元素 -> {1, 2, 3}
// 可以传入自定义的二元谓词来判断两个元素是否“重复”

2.10 循环

2.10.1 范围-based for 循环 (C++11+)

#include <iostream>
#include <list>int main() {std::list<int> numbers = {1, 2, 3, 4, 5};// 只读访问for (int num : numbers) {std::cout << num << " ";}// 输出: 1 2 3 4 5// 修改元素for (int& num : numbers) {num *= 2; // 每个元素乘以2}// 再次输出for (int num : numbers) {std::cout << num << " ";}// 输出: 2 4 6 8 10return 0;
}

2.10.2 使用迭代器循环

#include <iostream>
#include <list>int main() {std::list<std::string> fruits = {"Apple", "Banana", "Cherry"};// 正向迭代器for (auto it = fruits.begin(); it != fruits.end(); ++it) {std::cout << *it << " ";}// 输出: Apple Banana Cherry// 常量迭代器for (auto cit = fruits.cbegin(); cit != fruits.cend(); ++cit) {std::cout << *cit << " ";}return 0;
}

3、常见问题

1. list 和 vector 的区别？各自的适用场景？

• vector：
  • 优点：连续存储，支持快速随机访问(O(1))，缓存友好（ locality of reference ）。
  • 缺点：在非尾部位置插入删除效率低(O(n))，动态扩容有性能成本。
  • 场景：需要高效随机访问，不经常在中间插入删除，元素数量变化相对可预测。
• list：
  • 优点：在任何位置插入删除都是常数时间(O(1))，操作不会使其他迭代器失效（除了被删除的）。
  • 缺点：不支持随机访问（访问需要O(n)），内存开销大（每个元素都需要额外的指针空间），缓存不友好。
  • 场景：需要频繁在任意位置进行插入删除，且不需要随机访问（如实现链表结构、频繁调整的序列）。

2. 为什么 list 有自己的 sort 成员函数？
   标准算法std::sort要求随机访问迭代器（因为它需要像begin() + n这样的操作），而list的迭代器是双向迭代器，不支持随机访问。因此，list提供了自己的sort成员函数，它使用归并排序的变体，只通过迭代器的增量和递减来操作，时间复杂度也是O(n log n)。

3. std::list 为什么不支持 operator[]？
   因为 std::list 是双向链表，元素存储在非连续内存中，无法通过指针算术直接计算第 n 个元素的地址，必须从表头/表尾遍历（O(n) 时间），不符合 operator[] 预期的 O(1) 效率，因此 STL 设计时未提供该操作。

4. std::list 的 size() 方法时间复杂度是 O(1) 吗？

   • C++11 之前：部分实现（如 GCC）中 size() 需遍历链表计数（O(n)），因维护一个 size 成员会增加插入/删除的开销。
   • C++11 之后：标准强制要求 size() 为 O(1)，实现中通过一个 size_t 成员变量实时记录元素数量。

5. std::list 与 std::forward_list 的区别？

   • std::list 是双向链表，支持双向遍历和首尾操作。
   • std::forward_list 是单向链表（C++11 新增），仅支持正向遍历，内存开销更小（每个节点仅 1 个指针），但功能更有限（无 back()、pop_back() 等）。

6. 如何选择 std::list 与 std::vector？
   核心看操作类型：

   • 若以随机访问或尾部操作为主：选 vector。
   • 若以任意位置插入/删除为主：选 list。
   • 若元素数量固定：优先选 std::array 或 vector（空间效率更高）。