新竹县网站建设_网站建设公司_图标设计_seo优化

📚 一、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的场景：

• 需要频繁随机访问元素

• 元素数量变化不大，主要在尾部操作

• 对缓存性能要求高

• 需要与其他C函数或库交互（连续内存）

使用list的场景：

• 频繁在中间位置插入/删除元素

• 不需要随机访问，主要是顺序访问

• 元素较大，移动成本高

• 需要稳定的迭代器（不被插入操作影响）

💡 七、最佳实践

1. 优先选择vector：除非有明确的理由，否则vector通常是更好的选择

2. 考虑deque：如果需要头尾高效操作，考虑使用deque

3. 使用算法库：结合STL算法（如sort、find等）使用

4. 注意迭代器失效：特别是在循环中修改容器时

总结

list作为STL中的双向链表容器，在特定场景下具有不可替代的优势。理解其底层实现原理、迭代器机制以及与vector的区别，能够帮助我们在实际开发中做出更合理的选择。通过模拟实现list，我们能够更深入地理解STL容器的设计思想，提升C++编程能力。