1. 引言本期是 C 学习之路的第七期我们将深入探讨 STL 中非常重要的序列式容器——list。list 的底层结构是带头结点的双向循环链表与 vector 的动态顺序表结构截然不同这也决定了它在插入删除效率、随机访问能力以及迭代器失效规则等方面有着独特的特性。本文将从 list 的介绍与使用入手逐步过渡到底层模拟实现最后与 vector 进行系统对比帮助大家建立完整的知识体系。2. list 的介绍及使用2.1 list 的介绍list 是 STL 中的序列式容器其底层结构为带头结点的双向循环链表。与 vector 不同list 不支持随机访问但在任意位置进行插入和删除操作的效率非常高时间复杂度为 O(1)。list 的详细文档可参考 C 标准库官方文档。2.2 list 的使用list 中的接口比较多此处类似只需要掌握如何正确地使用然后再去深入研究背后的原理以达到可扩展的能力。以下为 list 中一些常见的重要接口。2.2.1 list 的构造构造函数constructor接口说明list (size_type n, const value_type val value_type())构造的 list 中包含 n 个值为 val 的元素list()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用 [first, last) 区间中的元素构造 listlist 的构造使用代码演示#include iostream #include list using namespace std; int main() { listint l1; // 构造空的 list listint l2(10, 5); // 10 个值为 5 的元素 listint l3(l2); // 拷贝构造 int array[] { 1, 2, 3, 4, 5 }; listint l4(array, array 5); // 用区间构造 return 0; }2.2.2 list iterator 的使用此处大家可暂时将迭代器理解成一个指针该指针指向 list 中的某个节点。函数声明接口说明begin end返回第一个元素的迭代器 返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的 reverse_iterator即 end 位置返回最后一个元素下一个位置的 reverse_iterator即 begin 位置注意begin 与 end 为正向迭代器对迭代器执行 操作迭代器向后移动。rbeginend与 rendbegin为反向迭代器对迭代器执行 操作迭代器向前移动。list 的迭代器使用代码演示#include iostream #include list using namespace std; int main() { int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; listint l(array, array sizeof(array) / sizeof(array[0])); // 正向迭代器遍历 auto it l.begin(); while (it ! l.end()) { cout *it ; it; } cout endl; // 反向迭代器遍历 auto rit l.rbegin(); while (rit ! l.rend()) { cout *rit ; rit; } cout endl; return 0; }2.2.3 list capacity函数声明接口说明empty检测 list 是否为空是返回 true否则返回 falsesize返回 list 中有效节点的个数2.2.4 list element access函数声明接口说明front返回 list 的第一个节点中值的引用back返回 list 的最后一个节点中值的引用2.2.5 list modifiers函数声明接口说明push_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中最后一个元素insert在 list position 位置中插入值为 val 的元素erase删除 list position 位置的元素swap交换两个 list 中的元素clear清空 list 中的有效元素list 的插入和删除使用代码演示#include iostream #include list using namespace std; int main() { listint l; l.push_back(1); l.push_back(2); l.push_front(0); l.pop_back(); l.pop_front(); auto pos l.begin(); l.insert(pos, 100); l.erase(pos); l.clear(); return 0; }list 中还有一些操作需要用到时大家可参阅 list 的文档说明。2.2.6 list 的迭代器失效前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表因此在 list 中进行插入时是不会导致 list 的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。下面是一个典型的迭代器失效示例void TestListIterator1() { int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; listint l(array, array sizeof(array) / sizeof(array[0])); auto it l.begin(); while (it ! l.end()) { // erase() 函数执行后it 所指向的节点已被删除因此 it 无效 // 在下一次使用 it 时必须先给其赋值 l.erase(it); it; } }改正后的写法void TestListIterator() { int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; listint l(array, array sizeof(array) / sizeof(array[0])); auto it l.begin(); while (it ! l.end()) { l.erase(it); // it l.erase(it); } }3. list 的模拟实现3.1 模拟实现 list要模拟实现 list必须要熟悉 list 的底层结构以及其接口的含义通过上面的学习这些内容已基本掌握现在我们来模拟实现 list。namespace mylist { // List 的节点结构 templateclass T struct ListNode { ListNodeT* _next; ListNodeT* _prev; T _data; ListNode(const T data T()) : _next(nullptr) , _prev(nullptr) , _data(data) {} }; // 正向迭代器 templateclass T, class Ref, class Ptr struct ListIterator { typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr Self; Node* _node; ListIterator(Node* node nullptr) : _node(node) {} Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } Self operator() { _node _node-_next; return *this; } Self operator(int) { Self temp(*this); _node _node-_next; return temp; } Self operator--() { _node _node-_prev; return *this; } Self operator--(int) { Self temp(*this); _node _node-_prev; return temp; } bool operator!(const Self l) const { return _node ! l._node; } bool operator(const Self l) const { return _node l._node; } }; // list 容器主体 templateclass T class list { typedef ListNodeT Node; public: typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; public: list() { _head new Node; _head-_next _head; _head-_prev _head; } iterator begin() { return iterator(_head-_next); } iterator end() { return iterator(_head); } void push_back(const T val) { Node* newnode new Node(val); Node* tail _head-_prev; tail-_next newnode; newnode-_prev tail; newnode-_next _head; _head-_prev newnode; } void push_front(const T val) { Node* newnode new Node(val); Node* first _head-_next; _head-_next newnode; newnode-_prev _head; newnode-_next first; first-_prev newnode; } void pop_back() { Node* tail _head-_prev; Node* prev tail-_prev; prev-_next _head; _head-_prev prev; delete tail; } void pop_front() { Node* first _head-_next; Node* next first-_next; _head-_next next; next-_prev _head; delete first; } iterator insert(iterator pos, const T val) { Node* cur pos._node; Node* prev cur-_prev; Node* newnode new Node(val); prev-_next newnode; newnode-_prev prev; newnode-_next cur; cur-_prev newnode; return iterator(newnode); } iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; return iterator(next); } void clear() { iterator it begin(); while (it ! end()) { it erase(it); } } ~list() { clear(); delete _head; _head nullptr; } private: Node* _head; }; }3.2 list 的反向迭代器通过前面例子知道反向迭代器的 就是正向迭代器的 --反向迭代器的 -- 就是正向迭代器的 因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对正向迭代器的接口进行包装即可。templateclass Iterator class ReverseListIterator { // 注意此处 typename 的作用是明确告诉编译器Ref 是 Iterator 类中的类型 // 而不是静态成员变量否则编译器编译时就不知道 Ref 是 Iterator 中的类型 // 还是静态成员变量因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的 public: typedef typename Iterator::Ref Ref; typedef typename Iterator::Ptr Ptr; typedef ReverseListIteratorIterator Self; public: // 构造 ReverseListIterator(Iterator it) : _it(it) {} // 具有指针类似行为 Ref operator*() { Iterator temp(_it); --temp; return *temp; } Ptr operator-() { return (operator*()); } // 迭代器支持移动 Self operator() { --_it; return *this; } Self operator(int) { Self temp(*this); --_it; return temp; } Self operator--() { _it; return *this; } Self operator--(int) { Self temp(*this); _it; return temp; } // 迭代器支持比较 bool operator!(const Self l) const { return _it ! l._it; } bool operator(const Self l) const { return _it l._it; } private: Iterator _it; };4. list 与 vector 的对比vector 与 list 都是 STL 中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下对比项vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率 O(1)不支持随机访问访问某个元素效率 O(N)插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为 O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为 O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针节点指针进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响