本文主要介绍list 的常用接口的使用实例具体的看官方文档list文档接着简单模拟实现一个list更好的了解底层。1.list 的使用有了前面vector的使用再看list的使用就会比较简单list底层是一个带头节点的双向循环链表。1.1list的构造构造函数常用的接口代码示例listint l1; listint l2(5, 1); listint l3(l2.begin(), l2.end()); listint l4(l3); listint l5 { 1,2,3,4,5 };赋值运算符重载常用接口代码示例在已经有上面的构造l4 l5; l3 { 1,2,3,4,5 };析构函数的理解就比较简单自己调用即可。1.2 list iterator 的使用这里暂时理解他底层还是指针该指针指向list的某个节点。说明上面四个迭代器都实现了const版本在调用的时候自动调用。begin与end为正向迭代器对迭代器执行操作迭代器向后移动。rbegin(end)与rend(begin为反向迭代器对迭代器执行操作迭代器向前移动。代码示例auto it l5.begin(); while (it ! l5.end()) { cout (*it) ; it; } cout endl; auto rit l5.rbegin(); while (rit ! l5.rend()) { cout (*rit) ; rit; }1.3 list capacity1.4 list element access1.5 list modifiers上面函数接口直说明了一种情况还有更多的修改操作对应的看文档。代码示例:给出对应具体接口的使用情况// 创建listint容器l1包含3个元素每个元素初始值为1即 l1 {1,1,1} listint l1(3, 1); // 创建listint容器l2列表初始化元素为 1,2,3,4,5 listint l2 { 1,2,3,4,5 }; // assign区间赋值用l2的[begin,end)区间元素替换l1全部原有元素 //l1.assign(l2.begin(), l2.end()); // assign填充赋值把l1全部元素替换为5个1 //l1.assign(5, 1); // assign初始化列表赋值用{1,2,3,4,5}替换l1全部元素 //l1.assign({ 1,2,3,4,5 }); // 在l1容器尾部插入元素2 l1.push_back(2); // 在l1容器尾部插入元素2 l1.push_back(2); // 在l1容器头部插入元素10 l1.push_front(10); // 在l1容器头部插入元素10 l1.push_front(10); // 删除l1容器尾部的一个元素 l1.pop_back(); // 删除l1容器尾部的一个元素 l1.pop_back(); // 删除l1容器头部的一个元素 l1.pop_front(); // 删除l1容器头部的一个元素 l1.pop_front(); // find算法在l2的begin到end范围内查找值等于3的迭代器位置pos auto pos find(l2.begin(), l2.end(), 3); // insert在迭代器pos位置前面插入单个元素100 //l2.insert(pos, 100); // insert在pos位置前面插入2个值为100的元素 //l2.insert(pos, 2,100); // insert在pos位置前面插入[l1.begin(), l1.end())区间内所有元素 //l2.insert(pos, l1.begin(), l1.end()); // insert在pos位置前面插入初始化列表{100,100}中的元素 //l2.insert(pos, { 100,100 }); // erase删除迭代器pos指向的单个元素 //l2.erase(pos); // erase删除[pos, l2.end())区间内所有元素 //l2.erase(pos, l2.end()); // swap交换l2和l1两个list容器的全部内容效率很高只交换内部指针 //l2.swap(l1); // resize把l2容器大小调整为10多出的新位置填充值1 //l2.resize(10, 1); // resize把l2容器大小调整为2多余尾部元素直接删除 //l2.resize(2); // clear清空l2容器所有元素size变为0 //l2.clear(); // splice拼接把整个l1容器所有元素移动到l2的pos迭代器位置之前l1变为空 //l2.splice(pos,l1); // splice拼接把l1中l1.begin()指向的单个元素移动到l2的pos位置之前 //l2.splice(pos, l1,l1.begin()); // remove删除l2容器中所有值等于3的元素list自带成员函数不是算法 //l2.remove(3); // reverselist成员函数反转容器内部元素顺序 l2.reverse(); // 获取l2的起始迭代器 auto it l2.begin(); // 迭代遍历迭代器不等于尾后迭代器就继续循环 while (it ! l2.end()) { // 输出迭代器指向的元素值后面跟空格 cout (*it) ; // 迭代器向后移动一位指向下一个元素 it; } // 输出换行 cout endl;1.6迭代器失效的问题前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。2.list 的模拟实现有了上面对list的使用基础接下来模拟实现STL list的底层逻辑复刻源代码的核心架构链表节点泛型迭代器双向循环链表核心接口拷贝构造赋值重载析构函数有助于更好的了解底层。2.1 list底层存储结构STLlist本质是带头结点的双向循环链表存在一个哨兵头结点head不存储有效数据统一空链表和非空链表的操作逻辑。最后一个节点的next指向headhead的prev指向最后一个节点形成闭环。每个节点包含数据域、前驱指针、后继指针。2.2整体代码架构分析本次模拟实现分为三大核心架构1.list_node节点结构体封装链表节点数据和指针2.list_iterator迭代器结构体封装链表迭代器实现遍历、加减、解引用等操作3.list容器类封装链表所有对外接口、构造析构、增删查改、拷贝赋值2.3链表节点list_node节点是链表的最小存储单元采用泛型设计支持存储任意类型数据。每个节点保存数据、前驱节点指针、后继节点指针。template class T struct list_node { // 数据域 T _data; // 后继节点指针 list_nodeT* _next; // 前驱节点指针 list_nodeT* _prev; // 构造函数初始化数据指针置空 list_node(const T x T()) :_data(x) , _next(nullptr) , _prev(nullptr) { } };采用默认构造参数T()支持无参创建节点适配空节点初始化场景。2.4迭代器list_iteratorlist 的迭代器和 vector 完全不同vector 迭代器是原生指针而 list 迭代器是封装节点指针的自定义类型。因为链表节点不连续无法通过指针偏移实现遍历必须封装迭代器行为。采用三模板参数设计同时支持普通迭代器和 const 迭代器T节点数据类型Ref:数据引用类型T/const TPtr:数据指针类型T* / const T*template class 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) { } // 解引用返回节点数据引用 Ref operator*() { return _node-_data; } // - 重载返回数据指针支持迭代器-成员访问 Ptr operator-() { return (_node-_data); } // 前置指向后继节点 Self operator() { _node _node-_next; return *this; } // 后置先返回当前再后移 Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } // 前置--指向前驱节点 Self operator--() { _node _node-_prev; return *this; } // 后置-- Self operator--(int) { Self tmp(*this); _node _node-_prev; return tmp; } // 迭代器比较 bool operator!(const Self it) { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } };迭代器的移动本质是节点指针的跳转operator-重载支持it-xxx访问自定义类型成员符合 STL 规范区分前置/后置自增自减适配不同遍历场景2.5list容器核心类容器类对外提供所有接口封装底层节点和迭代器对用户屏蔽底层指针操作符合STL std::list 使用方式。1.类型从定义和迭代器接口为了后续接口使用的方便对接点类型typedef,同时保持迭代器接口的一致性对普通迭代器结构体typedef成iterator,const迭代器结构体typedef成const_iteratortemplate class T class list { typedef list_nodeT Node; public: // 普通迭代器、const迭代器类型重定义 typedef list_iteratorT,T,T* iterator; typedef list_iteratorT, const T,const T* const_iterator; // 起始迭代器指向第一个有效节点 iterator begin() { return iterator(_head-_next); } const_iterator begin() const { return const_iterator(_head-_next); } // 末尾迭代器指向头结点循环链表终点 iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); } }2.初始化和构造函数空链表初始化是核心创建哨兵头结点让头结点自环next和prev都指向自身。// 空链表初始化 void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; } // 默认构造 list() { empty_init(); } // 拷贝构造深拷贝 list(const listT lt) { empty_init(); // 遍历原链表逐个尾插数据 for (const auto e : lt) { push_back(e); } } // 初始化列表构造支持 list{1,2,3,4} list(initializer_listT il) { empty_init(); for (const auto e : il) { push_back(e); } }构造函数主要实现了 默认构造拷贝构造和初始化列表构造拷贝构造实现深拷贝新链表独立开辟节点和原链表内存完全隔离避免浅拷贝析构重复释放问题上面复用的接口push_back在后面会给出具体代码。3.赋值重载采用传值交换法实现赋值重载代码简洁且天然解决自赋值问题。// 交换两个链表的头结点指针 void swap(listT lt) { std::swap(_head, lt._head); } // 赋值重载现代写法 listT operator(listT lt) { swap(lt); return *this; }原理传入参数为临时拷贝交换当前对象和临时对象的头指针当前对象接管临时对象的有效数据临时对象析构时自动释放旧数据。4.析构函数和清空链表接口// 清空所有有效节点 void clear() { auto it begin(); while (it ! end()) { iterase(it); } } // 析构函数 ~list() { // 清空有效节点 clear(); // 释放哨兵头结点 delete _head; _head nullptr; }5.核心的增删接口插入insert和删除(erase)接口的实现和数据结构的双向循环链表的实现一样修改对应的指针即可。所有头尾插入删除接口全部复用insert和erase核心接口减少代码冗余统一逻辑。// 任意位置插入节点 iterator insert(iterator pos, const T val) { Node* cur pos._node; // 创建新节点 Node* newnode new Node(val); // 调整指针指向 newnode-_next cur; newnode-_prev cur-_prev; cur-_prev-_next newnode; cur-_prev newnode; return iterator(newnode); } // 任意位置删除节点 iterator erase(iterator pos) { Node* cur pos._node; Node* next cur-_next; // 跳过当前节点重构链表连接 cur-_prev-_next cur-_next; cur-_next - _prev cur-_prev; // 释放节点内存 delete cur; // 返回下一个有效迭代器 return iterator(next); } // 尾插 void push_back(const T x) { insert(end(), x); } // 头插 void push_front(const T x) { insert(begin(), x); } // 尾删 void pop_back() { erase(--end()); } // 头删 void pop_front() { erase(begin()); }本次模拟实现list的底层原理更好的理解的list 的底层逻辑同时厘清了自定义迭代器的实现原理对比原生指针。3.模拟实现的完整代码#pragma once namespace gxy { // 链表节点结构体 template class T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T x T()) :_data(x) ,_next(nullptr) , _prev(nullptr) { } }; // 迭代器结构体 template class 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) { } Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } Self operator() { _node _node-_next; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--() { _node _node-_prev; return *this; } Self operator--(int) { Self tmp(*this); _node _node-_prev; return tmp; } bool operator!(const Self it) { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } }; // list 容器类 template class T class list { typedef list_nodeT Node; public: typedef list_iteratorT,T,T* iterator; typedef list_iteratorT, const T,const T* const_iterator; iterator begin() { return iterator(_head-_next); } const_iterator begin() const { return const_iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); } void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; } list() { empty_init(); } list(const listT lt) { empty_init(); for (const auto e : lt) { push_back(e); } } list(initializer_listT il) { empty_init(); for (const auto e : il) { push_back(e); } } void swap(listT lt) { std::swap(_head, lt._head); } listT operator(listT lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head nullptr; } void clear() { auto it begin(); while (it ! end()) { iterase(it); } } bool empty() { return begin() end(); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T val) { Node* cur pos._node; Node* newnode new Node(val); newnode-_next cur; newnode-_prev cur-_prev; cur-_prev-_next newnode; cur-_prev newnode; return iterator(newnode); } iterator erase(iterator pos) { Node* cur pos._node; Node* next cur-_next; cur-_prev-_next cur-_next; cur-_next - _prev cur-_prev; delete cur; return iterator(next); } private: Node* _head; }; }