1. 整体架构预览STLstd::list底层是带头结点双向循环链表。 难点不在于链表增删节点而在迭代器封装原生指针Node*不符合迭代器规范需要封装迭代器类。为了避免普通迭代器、const 迭代器写两份几乎完全一样的代码我们利用模板参数Ref、Ptr实现代码复用。反向迭代器采用适配器模式不重新实现一套反向遍历逻辑包装正向迭代器复用已有所有迭代器运算符。组件清单list_nodeT链表节点数据 前驱指针 后继指针_list_iteratorT,Ref,Ptr正向迭代器模板一份代码生成普通迭代器 /const 迭代器li::listT容器本体封装构造、析构、插入删除等接口reverseiteratorIterator,Ref,Ptr迭代器适配器实现反向遍历2. list.h#pragma once #includeiostream #includelist #includevector #includereverse_iterator.h using namespace std; namespace li {};2.1 链表节点list_nodetemplateclass T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; // 节点构造函数 list_node(const T val T()) :_data(val) , _next(nullptr) , _prev(nullptr) {} };解析有哨兵位的双向链表节点每个节点保存数据、前驱、后继指针。构造函数给默认参数T()头结点就是调用这个构造头结点不存储有效数据仅占位统一头尾操作逻辑。2.2 正向迭代器 _list_iteratortemplateclass T, class Ref, class Ptr struct _list_iterator { typedef list_nodeT Node; typedef _list_iteratorT, Ref, Ptr Self; Node* _node; // 迭代器构造函数 _list_iterator(Node* node) :_node(node) {}解析迭代器本质就是封装节点指针。 模板参数说明T存储的数据类型Ref引用类型普通迭代器传Tconst 迭代器传const TPtr指针类型普通迭代器传T*const 迭代器传const T*// 解引用重载 *it Ref operator*() { return _node-_data; }解析返回引用普通迭代器可读可写const 迭代器只读。// -重载 it- Ptr operator-() { return _node-_data; }解析返回数据指针支持it-member访问。// 前置 it Self operator() { _node _node-_next; return *this; }解析迭代器移动到下一个节点返回自身引用支持连续 it。// 后置 it Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; }解析int 只是占位参数用来区分前置 / 后置。先保存旧迭代器节点后移返回旧状态。// 前置-- --it Self operator--() { _node _node-_prev; return *this; }解析迭代器向前移动到上一个节点。// 后置-- it-- Self operator--(int) { Self tmp(*this); _node _node-_prev; return tmp; }// ! 判断 bool operator!(const Self it)const { return _node ! it._node; } // 判断 bool operator(const Self it)const { return _node it._node; } };判断的是两个地址是否相等2.3 list 容器类逐个函数拆解templateclass T class list { typedef list_nodeT Node; public: // 类型重定义实例化两种正向迭代器 typedef _list_iteratorT, T, T* iterator; typedef _list_iteratorT, const T, const T* const_iterator; // 反向迭代器类型 typedef reverseiteratoriterator, T, T* reverse_iterator; typedef reverseiteratorconst_iterator, const T, const T* const_reverse_iterator;empty_init 初始化函数void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; }作用创建头结点构建空双向循环链表size 置 0。默认构造list() { empty_init(); }解析调用初始化函数创建空链表。析构函数~list() { clear(); delete _head; _head nullptr; }解析先释放全部有效节点再释放头结点防止内存泄漏。拷贝构造函数list(const listT l) { empty_init(); for (const auto e : l) { push_back(e); } }解析现代写法先初始化空链表遍历原 list 逐个尾插。initializer_list 构造list(initializer_listT l) { empty_init(); for (const auto e : l) { push_back(e); } }解析支持li::listint lt{1,2,3,4}这种花括号初始化。swap 交换函数void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); }解析O (1) 时间复杂度仅仅交换头结点指针和 size不拷贝节点。赋值重载现代写法list operator(list lt) { swap(lt); return *this; }解析参数传值自动调用拷贝构造生成临时对象swap 交换资源函数结束临时对象销毁带走旧内存。天然处理自赋值。clear 清空所有有效节点void clear() { iterator it begin(); while (it ! end()) { it erase(it); } }❌错误写法erase(it); it;erase 之后 pos 迭代器直接失效it 是未定义行为。✅正确it erase(it)erase 返回下一个有效迭代器。rbegin /rend 反向迭代器接口reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin()const { return const_reverse_iterator(end()); } const_reverse_iterator rend()const { return const_reverse_iterator(begin()); }解析反向迭代器适配器rbegin 包装正向 endrend 包装正向 begin。begin /end 正向迭代器接口iterator begin() { return iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(_head-_next); } const_iterator end()const { return const_iterator(_head); }解析begin ()指向第一个有效节点end ()指向头结点尾后迭代器不能解引用push_back 尾插void push_back(const T x) { insert(end(), x); }解析复用 insert在 end 前面插入节点就是尾插。push_front 头插void push_front(const T x) { insert(begin(), x); }pop_back 尾删void pop_back() { erase(--end()); }解析--end()拿到最后一个有效节点迭代器直接 erase 删除。pop_front 头删void pop_front() { erase(begin()); }insert 插入函数iterator insert(iterator pos, T val) { Node* newnode new Node(val); Node* pcur pos._node; Node* prev pcur-_prev; newnode-_next pcur; pcur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; return iterator(newnode); }解析STL 规定 insert 是在 pos 迭代器前面插入节点。 四步指针链接insert不会让任何迭代器失效。返回新节点迭代器。erase 删除函数iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; --_size; return iterator(next); }解析删除 pos 指向节点pos 迭代器失效其他迭代器保持有效。返回下一个节点迭代器。size 获取元素个数size_t size()const { return _size; } private: Node* _head; size_t _size 0; }; } //namespace li3. reverse_iterator.h 反向迭代器适配器逐函数拆分设计思路#pragma once templateclass Iterator, class Ref, class Ptr struct reverseiterator { typedef reverseiteratorIterator, Ref, Ptr Self; Iterator _it; // 构造函数 reverseiterator(Iterator it) :_it(it) {}// 解引用 Ref operator*() { Iterator tmp _it; --tmp; return *tmp; }解析底层正向迭代器是尾后迭代器不能直接解引用拷贝临时迭代器向前挪一位取值。// -重载 Ptr operator-() { return (operator*()); }// 反向迭代器 Self operator() { --_it; return *this; }解析反向迭代器 等价底层正向迭代器 --。// 反向迭代器 -- Self operator--() { _it; return *this; }解析反向迭代器 -- 等价底层正向迭代器 。bool operator!(const Self s) { return _it ! s._it; } bool operator(const Self s) { return _it s._it; } };核心原理反向迭代器不维护节点指针仅仅包装正向迭代器。 ❗面试考点为什么拷贝 tmp不能直接--_it如果直接修改_it会破坏反向迭代器底层保存的迭代器状态遍历逻辑错乱。只能临时拷贝一份再自减。4. main.cpp 测试代码#includelist.h int main() { li::listint lt{ 1,2,3,4,5 }; //正向遍历 li::listint::iterator it lt.begin(); while (it ! lt.end()) { cout *it ; it; } cout endl; //反向遍历 li::listint::reverse_iterator rit lt.rbegin(); while (rit ! lt.rend()) { cout *rit ; rit; } cout endl; lt.push_back(6); lt.push_front(0); lt.pop_back(); lt.pop_front(); for (auto x : lt) { cout x ; } return 0; }5、list 优缺点总结优点任意位置 O (1) 插入删除找到位置之后insert 不会迭代器失效缺点不支持随机访问不能l[0]不能 it 5查找是 O (N)节点碎片化内存不连续缓存命中率低注意迭代器不是原生指针是对 Node * 的包装类。模板三个参数T,Ref,Ptr的作用用来复用一份迭代器代码同时实现iterator和const_iteratoriteratorRefTPtrT*const_iteratorRefconst TPtrconst T*operator-返回元素地址支持it-member语法有特殊简化规则迭代器 / !比较内部节点指针不是比较元素it1 it2判断两个迭代器指向同一个节点不是元素相等。 /-- 修改迭代器内部_node前置返回引用后置返回值临时拷贝比较函数必须加constconst 迭代器调用不会报错。❗list 迭代器是双向迭代器只支持 、--不支持 it n /it - n不能随机访问总结成员变量Node* _head;哨兵头结点默认构造创建哨兵 headhead-_next head; head-_prev head;自循环析构先 clear再 delete _head不能漏删哨兵节点clear遍历删除所有有效节点不要删哨兵 head拷贝构造深拷贝新建哨兵循环把原链表每个元素 push_back 到新 list赋值重载现代写法swap简单安全注意自赋值问题