📚 一、list容器介绍
1.1 基本概念
list是C++标准模板库(STL)中的一个序列容器，底层实现为带头节点的双向循环链表。这种结构使得list在任意位置插入和删除元素都具有很高的效率。
1.2 核心特性
双向访问：可以从前后两个方向遍历
动态内存：每个元素独立分配内存（节点）
迭代器类型：双向迭代器（支持++和--操作）
内存不连续：元素在内存中不是连续存储的
🔧 二、list的基本使用
2.1 构造函数
cpp
#include <list> #include <iostream> void test_construction() { // 1. 默认构造 - 空list std::list<int> list1; // 2. 构造包含n个相同元素的list std::list<int> list2(5, 100); // 5个100 // 3. 范围构造 int arr[] = {1, 2, 3, 4, 5}; std::list<int> list3(arr, arr + 5); // 4. 拷贝构造 std::list<int> list4(list3); // 5. 初始化列表构造（C++11） std::list<int> list5 = {1, 2, 3, 4, 5}; }2.2 迭代器使用
cpp
void test_iterator() { std::list<int> lst = {1, 2, 3, 4, 5}; // 正向迭代器 std::cout << "正向遍历: "; for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 反向迭代器 std::cout << "反向遍历: "; for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) { std::cout << *rit << " "; } std::cout << std::endl; // C++11范围for循环 std::cout << "范围for遍历: "; for (int val : lst) { std::cout << val << " "; } std::cout << std::endl; }2.3 容量操作
cpp
void test_capacity() { std::list<int> lst = {1, 2, 3}; std::cout << "是否为空: " << lst.empty() << std::endl; std::cout << "元素个数: " << lst.size() << std::endl; // list没有capacity()方法，因为链表不需要预分配空间 }2.4 元素访问
cpp
void test_element_access() { std::list<int> lst = {1, 2, 3, 4, 5}; if (!lst.empty()) { std::cout << "第一个元素: " << lst.front() << std::endl; std::cout << "最后一个元素: " << lst.back() << std::endl; } // list不支持随机访问，所以没有operator[]和at()方法 // 要访问第n个元素，需要遍历 }2.5 修改操作
cpp
void test_modifiers() { std::list<int> lst; // 头部操作 lst.push_front(10); // 头部插入 lst.pop_front(); // 头部删除 // 尾部操作 lst.push_back(20); // 尾部插入 lst.pop_back(); // 尾部删除 // 中间插入 auto it = lst.begin(); ++it; // 移动到第二个位置 lst.insert(it, 30); // 在第二个位置插入30 // 删除 it = lst.begin(); lst.erase(it); // 删除第一个元素 // 清空 lst.clear(); }⚠️ 三、迭代器失效问题
3.1 错误示例
cpp
// 错误写法：迭代器失效 void wrong_example() { std::list<int> lst = {1, 2, 3, 4, 5}; auto it = lst.begin(); while (it != lst.end()) { lst.erase(it); // 错误！删除后it失效 ++it; // 使用失效的迭代器，未定义行为 } }3.2 正确写法
cpp
// 正确写法1：使用返回值更新迭代器 void correct_example1() { std::list<int> lst = {1, 2, 3, 4, 5}; auto it = lst.begin(); while (it != lst.end()) { it = lst.erase(it); // erase返回下一个有效迭代器 } } // 正确写法2：后置递增 void correct_example2() { std::list<int> lst = {1, 2, 3, 4, 5}; auto it = lst.begin(); while (it != lst.end()) { lst.erase(it++); // 先传递it，然后递增 } }注意：对于list，只有指向被删除元素的迭代器会失效，其他迭代器不受影响。
🔨 四、list的模拟实现
4.1 节点结构
cpp
template<class T> struct ListNode { ListNode<T>* _prev; ListNode<T>* _next; T _data; ListNode(const T& val = T()) : _prev(nullptr) , _next(nullptr) , _data(val) {} };4.2 list类框架
cpp
template<class T> class List { private: ListNode<T>* _head; // 头节点（哨兵节点） public: // 迭代器类 class iterator { private: ListNode<T>* _node; public: iterator(ListNode<T>* node = nullptr) : _node(node) {} // 前置++ iterator& operator++() { _node = _node->_next; return *this; } // 后置++ iterator operator++(int) { iterator temp(*this); _node = _node->_next; return temp; } // 解引用 T& operator*() { return _node->_data; } // 箭头运算符 T* operator->() { return &_node->_data; } // 比较运算符 bool operator!=(const iterator& it) { return _node != it._node; } bool operator==(const iterator& it) { return _node == it._node; } }; // 构造函数 List() { _head = new ListNode<T>(); _head->_prev = _head; _head->_next = _head; } // 析构函数 ~List() { clear(); delete _head; _head = nullptr; } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } // 插入、删除等其他方法... };4.3 反向迭代器实现
cpp
template<class Iterator> class ReverseIterator { private: Iterator _it; public: ReverseIterator(Iterator it) : _it(it) {} // 前置++ ReverseIterator& operator++() { --_it; return *this; } // 后置++ ReverseIterator operator++(int) { ReverseIterator temp(*this); --_it; return temp; } // 解引用（注意反向迭代器的特殊处理） typename Iterator::reference operator*() { Iterator temp = _it; --temp; return *temp; } // 其他必要操作... };📊 五、list与vector对比
| 特性 | vector | list |
|---|---|---|
| 底层结构 | 动态数组，连续内存 | 双向链表，非连续内存 |
| 随机访问 | O(1)（支持） | O(n)（不支持） |
| 插入/删除 | 尾部O(1)，其他位置O(n) | 任意位置O(1)（已知位置） |
| 内存使用 | 连续，缓存友好，空间利用率高 | 碎片化，缓存不友好，每个元素额外开销 |
| 迭代器类型 | 随机访问迭代器 | 双向迭代器 |
| 迭代器失效 | 插入/删除可能导致全部迭代器失效 | 只有被删除元素的迭代器失效 |
| 适用场景 | 需要随机访问，尾部操作频繁 | 频繁在任意位置插入/删除 |
🎯 六、选择指南
使用vector的场景：
需要频繁随机访问元素
元素数量变化不大，主要在尾部操作
对缓存性能要求高
需要与其他C函数或库交互（连续内存）
使用list的场景：
频繁在中间位置插入/删除元素
不需要随机访问，主要是顺序访问
元素较大，移动成本高
需要稳定的迭代器（不被插入操作影响）
💡 七、最佳实践
优先选择vector：除非有明确的理由，否则vector通常是更好的选择
考虑deque：如果需要头尾高效操作，考虑使用deque
使用算法库：结合STL算法（如sort、find等）使用
注意迭代器失效：特别是在循环中修改容器时
总结
list作为STL中的双向链表容器，在特定场景下具有不可替代的优势。理解其底层实现原理、迭代器机制以及与vector的区别，能够帮助我们在实际开发中做出更合理的选择。通过模拟实现list，我们能够更深入地理解STL容器的设计思想，提升C++编程能力。
