C++ std::list

std::list 是 C++ STL 中基于双向链表实现的序列容器，其设计目标是提供高效的任意位置插入 / 删除操作。
1、底层结构与核心原理

1.1 节点与链表结构

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

1. template <typename T>
2. struct ListNode {
3.     T data;          // 元素值
4.     ListNode* prev;  // 指向前驱节点
5.     ListNode* next;  // 指向后继节点
6. };

复制代码

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

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

1.2 核心特性

• 非连续存储
  
  
  
  • 元素分散在内存的各个地方，不像vector或array是连续块。
    
  
  
• 高效的插入与删除 (O(1))
  
  
  
  • 在任何已知位置（通过迭代器指定）的插入和删除操作都是常数时间复杂度。
    
  • 操作仅涉及指针的重新赋值，不需要移动任何其他元素。
    
    
    
    • 插入：新分配一个节点，然后调整相邻节点的指针指向这个新节点。
      
    • 删除：调整目标节点前后节点的指针，让它们彼此指向对方，然后释放目标节点的内存。
      
    
    
  
  
• 迭代器稳定性
  
  
  
  • 这是list最强大的特性之一。插入操作不会使任何现有的迭代器、指针或引用失效。
    
  • 删除操作只会使指向被删除元素的迭代器、指针或引用失效，其他元素的迭代器仍然完全有效。
    
  • 这与vector和deque形成鲜明对比，后者在插入/删除时极易导致迭代器大面积失效。
    
  
  
• 不支持随机访问 (O(n))
  
  
  
  • 无法使用[]运算符或at()方法直接访问第n个元素。
    
  • 访问某个特定位置的元素需要从begin()或end()开始逐步递增或递减迭代器，时间复杂度为线性O(n)。
    
  
  

2、常用操作与示例代码

2.1 初始化

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

复制代码

2.2 元素访问

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

复制代码

2.6 splice：转移元素的神器

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

复制代码

2.7 sort：成员函数排序

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

复制代码

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

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

复制代码

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

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

复制代码

2.10 循环

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

[code]#include #include int main() {    std::list numbers = {1, 2, 3, 4, 5};        // 只读访问    for (int num : numbers) {        std::cout