C++_list

目录1.引言2.list的介绍与使用2.1.list的介绍2.2.list的使用构造析构赋值运算符重载迭代器容量相关接口元素访问对象修改专属接口spliceremoveremove_ifuniquemergesort拓展仿函数reverse3.list模拟实现3.1.list源码观察3.2.list模拟实现迭代器初步实现代码重构insertpush_back和push_front析构erasepop_back和pop_front-运算符重载const迭代器初步实现迭代器优化迭代器失效clear赋值运算符重载源码拓展5.结语1.引言这篇讲list的使用和模拟实现在学list前需要掌握这些内容C_类和对象上-CSDN博客C_类和对象中-CSDN博客C_类和对象下-CSDN博客C_模板初阶-CSDN博客C_内存管理_c内存管理要如何做-CSDN博客那么话不多说直接进入正文——————2.list的介绍与使用2.1.list的介绍list容器和我们先前讲的vector容器一样都是模板list底层涉及的数据结构就是链表我们还是照着这个文档进行讲解顺序依旧是能用明理能扩展list - C Reference在讲list之前我先讲下list结构因为链表有很多种list底层的链表是带哨兵位的双向循环链表这个我会在看list底层的时候也讲2.2.list的使用经过string和vector的讲解和模拟实现其实现在看list可以发现很多接口基本都知道是实现什么功能的了所以这边我就一个个快速过下去了构造这构造就和vector一样的四种构造第一个是默认构造第二个是构造同时插入n个数据为val的对象第三个就是迭代器构造构造同时插入[first,last)这些位置的对象第四个就是拷贝构造没什么好说的析构赋值运算符重载迭代器这些迭代器就正向反向const跟之前的也都一样过一眼就好注意这里需要注意的是从list开始遍历就不能用【】下标的遍历方式了因为从list往后的那些容器全都不是顺序表了那么这个时候如果用[]下标遍历的话成本会很高就比如说从begin()到end()的所有数据输出一遍vector和string的时间复杂度是O(N)但是如果这种非顺序表的话时间复杂度就会到O(N^2)了因为比如链表想找第10个数据那就要从头往后跳10次因为成本太高了所以从list就没有operator[]重载我们看如下图他是这么跳的这里的迭代器其实就和我们先前讲的vectorstring的迭代器不一样了因为这不是连续的空间所以list的迭代器就肯定不是原生指针了迭代器其实有三种我们先前所讲的vector和string的迭代器是属于随机迭代器而list是双向迭代器单向迭代器forward_list、unordered_map、unordered_set 支持双向迭代器 list、map、set... 支持,--随机迭代器vector、string、deque.. 支持,--,,-迭代器的性质是由底层的结构决定的我们可以在这里看容器的迭代器是哪个类型的容量相关接口因为链表是一个个插入想插入时候就创建个新对象然后更新下指向就好了所以链表和vectorstring这种不一样没有扩容的概念所以这里接口不多empty()就是判空size()就是返回有几个数据max_size返回可行最大容量这也快速过了元素访问list的元素直接访问就只能获取到头和尾也就是这俩个接口这俩个返回的是引用也就是可以修改对象修改这些接口全在前面讲过了这里就看一眼过就行拓展这里讲下emplace相关接口的用法拿emplace_back举例这个和push_back相比在某些场景下会更高效就如下面代码#include iostream #include list using namespace std; struct A { A(int a1 1, int a2 1) :_a1(a1) , _a2(a2) { cout A(int a1 1, int a2 1) endl; } A(const A x) { _a1 x._a1; _a2 x._a2; cout A(const A x) endl; } ~A() { cout ~A() endl; } private: int _a1; int _a2; }; int main() { listA lt; A aa1(1, 1); lt.push_back(aa1); lt.push_back(A(2,2)); lt.push_back(2, 2); lt.emplace_back(aa1); lt.emplace_back(A(2,2)); lt.emplace_back(2, 2); }我们可以发现如果用push_back,传22是会报错的但是emplace_back不会如下图emplace_back可以拿值直接传过去构造就会少一次拷贝构造这就是emplace_back的优势如下图如果我们要传A类型的2,2的话用emplace_back就不用像push_back一样传匿名对象了直接传值就行了传匿名对象会有构造和拷贝构造但是传值的话他会只有一次构造就提高了很多效率这里只要了解就行具体会在C11部分讲专属接口splice这个接口的作用是转移数据第一条——把x内的所有节点全部转移到pos位置之前第二条——把x内迭代器 i 所指向位置的单个节点转移到pos位置之前第三条——把x的迭代器指向从[first,last的所有元素全部转移到pos位置之前注意转移之后原先那些就全消除了就比如第一条转移完x就为空了这个接口还可以调整自己链表的位置顺序remove这个接口就是用来删除数据找val删找到就删除找不到也不会报错注意他是从头遍历到尾所以如果有多个val他会全部删除remove_if这个接口就是配合一个条件进行删除这个得传仿函数全局函数静态函数或者匿名lambda现在了解就行不用会用unique这个接口的功能是去重去重的前提也是链表要有序merge这个接口的功能是将俩个链表进行合并链表合并的前提是俩个链表必须是有序的这个合并的底层原理其实就是取小的尾插需要注意的是比如lt1.merge(lt2)这就是lt2合并到lt1去了这个时候lt2其实就空了这里需要注意sort算法库里也是有sort的但是算法库的sort底层是快排堆排三路划分的融合这些都要基于顺序表才可以实现所以算法库的sort只能接收随机迭代器所以list无法用算法库的sort实现排序功能我们可以看下算法库的sort这个类型名是RandomAccess也就是随机即代表随机迭代器那自然是不支持双向迭代器的所以list自己实现了一个sort这个sort和算法库实现的sort效果一样默认就是升序排序但是 list的sort接口的底层是通过归并排序实现的数据量大的情况下不要用list的排序效率很低可以先拷贝给vector排完序再拷贝回来拓展仿函数那么如果想要降序排序的话就要用到仿函数仿函数就是重载了括号运算符-operator()的类的实例化这里就教怎么用首先有俩个类模板less和greaterless就是用来排升序的greater就是用来排降序的样例如下#include iostream #include list #include algorithm using namespace std; void test3() { listint lt; lt.push_back(2); lt.push_back(1); lt.push_back(3); lt.push_back(0); lt.push_back(5); lessint ls; greaterint lg; lt.sort(ls);//升序 for (auto x : lt) cout x ; cout endl; lt.sort(lg);//降序 for (auto x : lt) cout x ; cout endl; } int main() { test3(); }那既然是类自然就可以写匿名对象了,比如这样lt.sort(greaterint());//降序reverse这个reverse的效果就和算法库algorithm里的那个reverse实现效果一样就是逆置我们看算法库的reverse如下图算法库中的reverse是个函数模板Bidirectional就是双向也就是说我们可以通过类型名来推断他支持什么这个明显就是支持双向迭代器既然支持双向迭代器自然也就支持随机迭代器。那么list的迭代器是双向迭代器调用这个就可以完成list的逆置了我们可以俩个reverse都测一下#include iostream #include list #include algorithm using namespace std; void test2() { listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto x : lt) cout x ; cout endl; lt.reverse(); for (auto x : lt) cout x ; cout endl; reverse(lt.begin(), lt.end()); for (auto x : lt) cout x ; cout endl; } int main() { test2(); }运行可以发现都是没问题的注意虽然这俩个reverse实现的效果一样但是底层效率而言是完全不一样的算法库里的reverse是交换俩个迭代器的数据而list里自己实现的reverse是直接交换next和prew指针指向前一个和后一个的指针。这么一看其实效率就天差地别了所以其实这个reverse设计不冗余3.list模拟实现3.1.list源码观察这边扒源码的方式就和vector部分看源码的方式一样也是在那个文件夹里我们先找到list打开核心的毋庸置疑就是stl_list.h我们找到这个文件去打开我们先找到list类我们可以发现这个类内的成员变量就一个那就是node然后这个link_type是什么类型呢我们跳转过去看我们可以发现是list_node*类型接下来我们再去看list_node是什么类型可以发现是__list_nodeT类型的接下来我们接着跳转所以node其实就是指向__list_nodeT对象的指针我们可以通过图来理解这几个命名关系我们观察__list_node类模板可以发现里面有三个成员data存数据next指向下一个节点prev指向上一个节点接下来我们来看下list的构造因为是默认构造此时list内部还没有结构所以node-next和node-prev都指向自己我们再看get_node()内部这其实就是向空间配置器申请一块内存用来新建节点其实就和我们上次实现vector的时候用裸内存定位new的方式中裸内存一样就是给你一块裸空间不创建对象这个节点的data成员并没有赋值所以我们可以猜想这个可能会作为哨兵位接下来我们来看下push_back首先push_back会调用insert随后iinsert一开始进去会新创建一个节点这个节点是通过create_node得到的create_node就是像空间配置器申请一块空间后调用construct函数来给p-data初始化construct先前vector部分我们讲过里面就是定位new初始化然后初始化完后就返回p给tmp接收随后在更新prev和next的指向其实从这里我们就能看出list底层实现的时候是带有哨兵位的我们通过图来更清晰的看那么知道list的成员变量知道list的链表是带哨兵位的双向循环链表后我们就可以开始模拟实现list了3.2.list模拟实现这里我们依旧创建一个头文件——list.h接下来我们先搭个简单的结构之后再修改润色这边我为了方便多加了个_size来统计节点个数#pragma once #include iostream namespace qiu { templateclass T struct list_node { T data; list_nodeT* next; list_nodeT* prev; }; templateclass T class list { public: typedef list_nodeT* iterator; typedef const list_nodeT* const_iterator; void push_back(const T x); list() :_size(0) { node (iterator)::operator new(sizeof(list_nodeT)); node-next node; node-prev node; } size_t size() const { return _size; } bool empty() const { return size() 0; } iterator begin() { return node-next; } iterator end() { return node; } const_iterator begin() const { return node-next; } const_iterator end() const { return node; } private: iterator node; size_t _size; }; templateclass T void listT::push_back(const T x) { iterator new_node (iterator)::operator new(sizeof(list_nodeT)); new_node-data x; iterator old_node node-prev; new_node-prev old_node; new_node-next node; old_node-next new_node; node-prev new_node; _size; } }接下来我们测试一下没有什么大问题#define _CRT_SECURE_NO_WARNINGS #include list.h int main() { qiu::listint lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); qiu::listint::iterator it lt.begin(); while (it ! lt.end()) { std::cout it-data ; it it-next; } return 0; }在上面我们虽然用迭代器成功遍历了list但是list是有解引用重载这些的但是list内部的成员变量存的是我们这个链表的哨兵位这是不能改的那么我们就需要为了迭代器在外部实现一个类如下迭代器初步实现templateclass T struct list_iterator { typedef list_nodeT* Node; typedef list_iteratorT iterator; list_iterator(Node _node) :node(_node) { } iterator operator() { node node-next; return *this; } iterator operator(int) { iterator _node(node); node node-next; return _node; } iterator operator--() { node node-prev; return *this; } iterator operator--(int) { iterator _node(node); node node-prev; return _node; } T operator*() { return node-data; } bool operator!(const iterator it) const { return node ! it.node; } bool operator(const iterator it) const { return node it.node; } Node node; };那么我们上面所写的简单的结构就可以重构变成如下代码代码重构#pragma once #include iostream namespace qiu { templateclass T struct list_node { T data; list_nodeT* next; list_nodeT* prev; }; templateclass T struct list_iterator { typedef list_nodeT* Node; typedef list_iteratorT iterator; list_iterator(Node _node) :node(_node) { } iterator operator() { node node-next; return *this; } iterator operator(int) { iterator _node(node); node node-next; return _node; } iterator operator--() { node node-prev; return *this; } iterator operator--(int) { iterator _node(node); node node-prev; return _node; } T operator*() { return node-data; } bool operator!(const iterator it) const { return node ! it.node; } bool operator(const iterator it) const { return node it.node; } Node node; }; templateclass T class list { public: typedef list_nodeT* Node; typedef list_iteratorT iterator; void push_back(const T x); list() :_size(0) { node (Node)::operator new(sizeof(list_nodeT)); node-next node; node-prev node; } size_t size() const { return _size; } bool empty() const { return size() 0; } iterator begin() { return iterator(node-next); } iterator end() { return iterator(node); } private: Node node; size_t _size; }; templateclass T void listT::push_back(const T x) { Node new_node (Node)::operator new(sizeof(list_nodeT)); new (new_node-data) T(x); Node old_node node-prev; new_node-next node; new_node-prev old_node; old_node-next new_node; node-prev new_node; _size; } }inserttemplateclass T typename listT::iterator listT::insert(iterator pos, const T x) { Node new_node (Node)::operator new(sizeof(list_nodeT)); new (new_node-data) T(x); new_node-next pos.node; new_node-prev pos.node-prev; new_node-next-prev new_node; new_node-prev-next new_node; _size; return new_node; }insert实现后我们其实push_back和push_front就可以复用这块代码了能减少很多重复代码push_back和push_fronttemplateclass T void listT::push_back(const T x) { insert(end(), x); } templateclass T void listT::push_front(const T x) { insert(begin(), x); }析构因为我们采用的方式是operator new加定位new只构造了data对象所以我们只需要自己手动销毁data的那块数据即可所以在节点层面我们不用写析构函数来销毁节点数据只需要在list地方写个析构函数来销毁节点即可代码如下~list() { while (!empty()) pop_back(); ::operator delete(node); }erasetemplateclass T typename listT::iterator listT::erase(iterator pos) { assert(pos ! end()); iterator it pos.node-next; pos.node-prev-next pos.node-next; pos.node-next-prev pos.node-prev; pos.node-data.~T(); ::operator delete(pos.node); --_size; return it; }erase实现好了后尾删头删也就没问题了pop_back和pop_fronttemplateclass T void listT::pop_back() { erase(node-prev); } templateclass T void listT::pop_front() { erase(node-next); }-运算符重载T* operator-() { return node-data; }直接看这个可能看不懂我们先从我们之前表层运用来看就比如a1是一个结构体指针我们想要访问里面其中一个成员变量就会这样访问a1-a;然后a1就是我们这里list里的data成员所以我们正常实现是node-data这样就可以得到结构体的指针然后想要访问结构体内部的成员变量在node-data的基础上-a1。这里主要难理解是因为我们调用的时候直接就是 it-a但其实这里不止一个-完整的其实是这样的it.operator-()-a也就和我们上面的思路一样即(node-data)-a只是为了可读性省略了一个-省略的-是后面的那个-拓展operator-拥有递归消解机制如果operator-返回的还是一个具备operator-的对象编译器会继续调用它的operator-()直到返回原生指针才停止递归使用原生指针的-访问成员。const迭代器初步实现首先const迭代器意味就是指向的内容不能修改那么我们来找找迭代器里哪些部分的操作可能会影响到指向的空间可以发现就这俩个所以我们只需要在实现const迭代器的时候给这俩个 加上限制其余拷贝过去即可templateclass T struct list_const_iterator { typedef list_nodeT* Node; typedef list_const_iteratorT const_iterator; list_const_iterator(Node _node) :node(_node) { } const_iterator operator() { node node-next; return *this; } const_iterator operator(int) { const_iterator _node(node); node node-next; return _node; } const_iterator operator--() { node node-prev; return *this; } const_iterator operator--(int) { const_iterator _node(node); node node-prev; return _node; } const T operator*() const { return node-data; } const T* operator-() const { return node-data; } bool operator!(const const_iterator it) const { return node ! it.node; } bool operator(const const_iterator it) const { return node it.node; } Node node; };迭代器优化但是这么实现的话太冗余了因为这俩个相似度太高了就*运算符重载和-运算符重载不一样这个时候我们可以给模板多几个参数然后优化合并到一起如下templateclass T,class Ptr,class Re struct list_iterator { typedef list_nodeT* Node; typedef list_iteratorT, Ptr, Re Self; list_iterator(Node _node) :node(_node) { } Self operator() { node node-next; return *this; } Self operator(int) { Self _node(node); node node-next; return _node; } Self operator--() { node node-prev; return *this; } Self operator--(int) { Self _node(node); node node-prev; return _node; } Re operator*() { return node-data; } Ptr operator-() { return node-data; } Re operator*() const { return node-data; } Ptr operator-() const { return node-data; } bool operator!(const Self it) const { return node ! it.node; } bool operator(const Self it) const { return node it.node; } Node node; };所以之后如果遇到高度相似仅有类型不同的可以想方设法变为同一个类模板迭代器失效接下来我们来看下迭代器失效问题首先是insertinsert不会有迭代器失效问题因为list内部元素是一个一个节点就算是用户使用一个迭代器插入之后那个迭代器所指向的空间里的数据也是不会变的其次是erase这个会有迭代器失效问题因为erase会销毁pos位置的节点如果用户有迭代器指向pos位置那么就会有迭代器失效问题cleartemplateclass T void listT::clear() { iterator it begin(); while (it ! end()) it erase(it); }这个clear就可以复用到析构上~list() { clear(); ::operator delete(node); }赋值运算符重载templateclass T void listT::swap(listT x) { std::swap(node, x.node); std::swap(_size, x._size); } templateclass T listT listT::operator(listT x) { swap(x); return *this; }至此list主要的一些接口就实现完成了接下来赋源码顺便拓展点东西源码#pragma once #include iostream #include cassert namespace qiu { templateclass T struct list_node { T data; list_nodeT* next; list_nodeT* prev; }; templateclass T,class Ptr,class Re struct list_iterator { typedef list_nodeT* Node; typedef list_iteratorT, Ptr, Re Self; list_iterator(Node _node) :node(_node) { } Self operator() { node node-next; return *this; } Self operator(int) { Self _node(node); node node-next; return _node; } Self operator--() { node node-prev; return *this; } Self operator--(int) { Self _node(node); node node-prev; return _node; } Re operator*() { return node-data; } Ptr operator-() { return node-data; } Re operator*() const { return node-data; } Ptr operator-() const { return node-data; } bool operator!(const Self it) const { return node ! it.node; } bool operator(const Self it) const { return node it.node; } Node node; }; templateclass T class list { public: typedef list_nodeT* Node; typedef list_iteratorT, T*, T iterator; typedef list_iteratorT, const T*, const T const_iterator; void push_back(const T x); void push_front(const T x); iterator insert(iterator pos, const T x); iterator erase(iterator pos); void pop_back(); void pop_front(); void clear(); void swap(listT x); listT operator(listT x); list() :_size(0) { node (Node)::operator new(sizeof(list_nodeT)); node-next node; node-prev node; } list(const listT lt) :_size(0) { node (Node)::operator new(sizeof(list_nodeT)); node-next node; node-prev node; const_iterator it lt.begin(); while (it ! lt.end()) { push_back(*it); it; } } ~list() { clear(); ::operator delete(node); } size_t size() const { return _size; } bool empty() const { return size() 0; } iterator begin() { return iterator(node-next); } iterator end() { return iterator(node); } const_iterator begin() const { return const_iterator(node-next); } const_iterator end() const { return const_iterator(node); } private: Node node; size_t _size; }; templateclass T void listT::push_back(const T x) { insert(end(), x); } templateclass T void listT::push_front(const T x) { insert(begin(), x); } templateclass T typename listT::iterator listT::insert(iterator pos, const T x) { Node new_node (Node)::operator new(sizeof(list_nodeT)); new (new_node-data) T(x); new_node-next pos.node; new_node-prev pos.node-prev; new_node-next-prev new_node; new_node-prev-next new_node; _size; return new_node; } templateclass T typename listT::iterator listT::erase(iterator pos) { assert(pos ! end()); iterator it pos.node-next; pos.node-prev-next pos.node-next; pos.node-next-prev pos.node-prev; pos.node-data.~T(); ::operator delete(pos.node); --_size; return it; } templateclass T void listT::pop_back() { erase(node-prev); } templateclass T void listT::pop_front() { erase(node-next); } templateclass Container void Print_Contaiiner(const Container v) { for (auto x : v) std::cout x ; std::cout std::endl; } templateclass T void listT::clear() { iterator it begin(); while (it ! end()) it erase(it); } templateclass T void listT::swap(listT x) { std::swap(node, x.node); std::swap(_size, x._size); } templateclass T listT listT::operator(listT x) { swap(x); return *this; } }拓展我们在使用STL的时候还有这种写法listint lt {1,2,3,4,5};这种是C11才开始有的如下图C11开始就可以把{}括起来的类型认为是initializer_list然后这个其实就是一个类模板我们看下他的接口可以发现他也是支持迭代器的然后这个东西的底层其实就是俩个指针一个指向数据开头一个指向数据结尾的下一个位置我们可以用sizeof看下是不是64位在俩个指针16字节没问题那么既然这个类也支持迭代器自然支持范围for我们实现这个就很简单了如下list(std::initializer_listT il) { init(); for (auto x : il) push_back(x); }所以其实使用这个构造是有三种写法的qiu::listint lt0({ 1,2,32,34,32,4,324,23,43242,423,432 }); qiu::listint lt { 1,2,32,34,32,4,324,23,43242,423,432 }; const qiu::listint lt1 { 1,2,32,34,32,4,324,23,43242,423,432 };像第三种就是引用临时对象5.结语那么CSTL部分list的内容就全部讲解完毕啦希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。