list深度剖析一、list介绍与使用1.关于list2.list的使用3.迭代器相关说明二、list相关接口简述简要区分emplace_back与push_back关于splice接口简述迭代器失效三、源码剖析根据源码重构list1.结构分析2.节点类实现3.迭代器类实现3.1 成员变量3.2 构造函数3.3 operator*3.4 operator和operator- -3.5 operator和operator!3.6 operator-4.List实现4.1 成员变量4.2 构造函数4.3赋值重载4.4 析构函数4.5 插入删除5.const迭代器的实现6. 关于initializer_list一、list介绍与使用1.关于listlist即为链表而且还是双向带头循环链表其详细介绍参考C官网点我2.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)区间中的元素构造list3.迭代器相关说明迭代器类型- -n-n典型容器输入(Input)✅❌❌❌输入流输出(Output)✅❌❌❌输出流前向(Forward)✅❌❌❌forward_list双向(Bidirectional)✅✅❌❌list,set,map随机访问(Random)✅✅✅✅vector,deque,arraylist采用的是双向迭代器而vector采用的是随机访问迭代器因此list_iterator不支持 /-也不支持[]下标我们来看看sort显而易见算法库的sort要的参数是随机访问迭代器因此list不能使用sort但是list有它自己实现的sort二、list相关接口简述l.empty() // 是否为空 l.size() // 元素个数 l.max_size() // 最大容量一般不用 l.front() // 第一个元素 l.back() // 最后一个元素 l.push_back(10) //尾插10 l.push_front(20) //头插20 l.pop_back() //尾删 l.pop_front() //头删insert:指定位置插入erase:指定位置删除remove:按值删除removeif:条件删除unique:去重reverse:翻转merge:合并链表需要两链表有序类似于归并splice:剪切链表简要区分emplace_back与push_backlistA lt; A aa(1,1); lt.push_back(aa); lt.push_back(A(2,1)); //lt.push_back(2,2); 这是错误的 lt.emplace_back(aa); lt.emplace_back(A(2,1)); lt.emplace_back(2,2); //没有问题emplace_back和push_back前两种插入效率差不多但是emplace_back可以进行第三种方式进行插入且效率更高因为它只进行了构造而前两种进行了构造加拷贝关于splice接口splice就是把一个list的节点直接移动到另一个liststd::listint l1 {1,2,3}; std::listint l2 {4,5}; auto it l1.begin(); it; l1.splice(it, l2);结果l1: 1 4 5 2 3 l2: 空vector的insert可能会导致迭代器失效而splice并不会导致迭代器失效因为splice只是移动指针并没有发生扩容导致指针指向位置偏移并不会导致迭代器失效简述迭代器失效链表插入数据后并不会发生迭代器失效但在删除后可能发生插入数据后原来迭代器指向的位置不会发生改变故不会发生迭代器失效删除数据后若删除的是迭代器指向的数据那么该迭代器失效其他的迭代器不会产生任何影响三、源码剖析根据源码重构list1.结构分析要实现list必须包含三个类分别是节点类、迭代器类、链表类以下list均用List表示2.节点类实现//List节点类 templateclass T struct ListNode { ListNodeT* _prev; ListNodeT* _next; T _data; };list节点类包含指向前驱节点指针_prev、指向后继结点的指针_next、节点数据_data节点使用struct进行封装是因为后面的程序会频繁调用节点的成员ListNode(const T data T()) :_prev(nullptr), _next(nullptr), _data(data) { }这里需要一个节点的构造函数我们可以将其全部置空这里的dataT()对于内置类型也是兼容的3.迭代器类实现3.1 成员变量//List迭代器类 templateclass T struct ListIterator { typedef ListNodeT Node; typedef ListIterator self; Node* _pnode; };list的迭代器需要一个封装的指针因为list的空间不是连续的原生指针难以实现,- -,解引用等操作这些需要我们手动去执行3.2 构造函数ListIterator(Node* pnode nullptr) :_pnode(pnode) { }迭代器本身就是一个封装的指针因此浅拷贝足够不需要我们去实现3.3 operator*T operator*() { return _pnode-_data; }迭代器就是一个封装的指针解引用需要返回指针指向的数据3.4 operator和operator- -self operator() { _pnode _pnode-_next; return *this; } self operator(int) { auto tmp *this; _pnode _pnode-_next; return tmp; } self operator--() { _pnode _pnode-_prev; return *this; } self operator--(int) { auto tmp *this; _pnode _pnode-_prev; return tmp; }这里是前置、后置、前置- -、后置- -3.5 operator和operator!bool operator(const self s) const { return s._pnode _pnode; } bool operator!(const self s) const { return s._pnode ! _pnode; }直接比较指针是否相等3.6 operator-T* operator-() { return (_pnode-_data); }既然这个迭代器是指针那就有指针-的方式去访问节点数据举一个简单的例子class A { public: int _a; int _b; }; ListA lt; ListA::iterator itlt.begin(); //取it指向节点的_b元素 coutit-_bendl;取_b元素实际上是it.operator-()-_b4.List实现4.1 成员变量//List类 templateclass T class List { public: typedef ListNodeT Node; private: Node* _head; size_t _size; };List需要一个指向头结点的指针_head和一个_size便于统计长度4.2 构造函数接下来我们需要一个构造函数因为后面链表各种构造方式都需要一个空链表所以我们先实现一个空链表的构造先构造一个哨兵头结点将头结点的前驱和后继都指向自己将_size置零即可//空构造 void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; _size 0; } //构造 List(){ empty_init(); } //拷贝构造 list(const listT lt){ empty_init(); for (auto e : lt) push_back(e); }4.3赋值重载复制重载可以使用swap的方式完成这是一种经典且高效的写法它避免了一个个拷贝的时间消耗而是在自己的swap中调用库里的swapvoid swap(ListT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } ListT operator(ListT lt) { swap(lt); return *this; }4.4 析构函数先写一个clear函数清除节点再去实现析构注意析构要删除头结点clear不用void clear() { auto it begin(); while (it ! end()) { it erase(it); } _size0; } ~List() { clear(); delete _head; _head nullptr; }4.5 插入删除插入删除注意要保持双向链表的结构void insert(iterator pos,const T val) { Node* cur pos._pnode; Node* prev cur-_prev; Node* newnode new Node(val); newnode-_next cur; cur-_prev newnode; newnode-_prev prev; prev-_next newnode; _size; } void erase(iterator pos) { Node* node pos._pnode; if (node _head) return; Node* prev node-_prev; Node* next node-_next; prev-_next next; next-_prev prev; delete node; --_size; } void push_back(const T val) { insert(end(), val); } void pop_back() { if (!empty()) erase(--end()); } void push_front(const T val) { insert(begin(), val); } void pop_front() { if (!empty()) erase(begin()); }5.const迭代器的实现要实现const迭代器可以采用复制一份普通迭代器的方法来实现但是这样代码长度太长了接下来我们看一种stl库里实现的方法看ListIterator类我们对它的模板参数进行修改传三个参数第一个是类型第二、三个分别是类型的引用和指针将ListIteratorT, T, T*定义为iterator而const ListIteratorT, const T, const T*定义为const_iterator接下来把之后T改成RefT*改成Ptr即可这样编译器就能自动识别你要的是iterator还是const_iterator了//List迭代器类 templateclass T,class Ref,class Ptr struct ListIterator { typedef ListIteratorT, T, T* iterator; typedef const ListIteratorT, const T, const T* const_iterator; typedef ListNodeT Node; typedef ListIteratorT, Ref, Ptr self; Node* _pnode; }6. 关于initializer_liststl库支持这样的初始化listint lt{1,2,3,4,5};这是C11新增的初始化方式初始化列表初始化看看initializer_list是怎样的看看它的底层可见它的底层是_First和_Last两个指针_First指向第一个元素_Last指向最后一个元素的下一个位置因此我们可以写一个用initializer_list初始化的构造函数List(std::initializer_listT il) { empty_init(); for (auto i : il) { push_back(i); } } Listint lt({1,2,3,4}); //lt: 1-2-3-4