本文代码已同步Github一、底层源码分析1、源码剖析通过上一篇对vector的学习我们知道其底层是通过三个指针来充当迭代器下面我们来看一下list的底层是怎么设计的同样使用g中的SGI版本来观察先来看说明文档发现依据是多个头文件配合的形式那么核心文件便是stl_list.h我们来看一看发现和vector不同的是list里面有多个类比如list_node ,list_iterator,这些简单看一下类的名称及成员变量就会知道list_node是节点存储的是节点的信息看来底层确实是由一个双向链表来实现的list_iterator就是迭代器有一个list_node*的指针我们再往下看看还有没有其他的类还有一个类类名为list里面有一个list_node*的指针2、不同类之间的关系下面我们来理一理三个类之间的关系list用来控制整个链表无论是push_back还是insert等操作都通过list中的成员函数来实现而list_iterator是迭代器用来定位和访问通过重载–等操作符将迭代器封装成类似指针的效果最后的list_node就是一个一个的节点了好了根据上述对底层源码的简单分析之后我们来搭一下基础框架二、类模板框架搭建1、结构实现注意⚠️我们实现的仅仅是基础版为方便起见我们加入成员变量_sizenamespacestl{//节点templateclassTstructlist_node{list_node(constTdataT()):_data(data),_prev(nullptr),_next(nullptr){}T _data;list_nodeT*_prev;list_nodeT*_next;};//迭代器templateclassTstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorTSelf;list_iterator(Node*node):_node(node){}Node*_node;};templateclassTclasslist{public:typedeflist_nodeTNode;typedeflist_iteratorTiterator;private:Node*_head;size_t _size;public:};}下面我们来写list的默认构造函数分析首先要new一个节点这个节点即为哨兵位接着修改指针的指向并给_size赋值list(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}2、基础接口实现我们先来实现size和emptysize_tsize(){return_size;}boolempty(){return_size0;}接着来实现begin和end单参数构造函数可以进行隐式类型转换我们直接返回节点的地址即可iteratorbegin(){return_head-_next;}iteratorend(){return_head-_prev-_next;}三、迭代器实现1、iterator上一篇对list接口的介绍中我们知道list的迭代器是双向迭代器也就是说只能,--但是对于链表来说由于不是顺序存储因此对于普通指针无论是还是–之后都无法到达下一个节点此时我们就需要对运算符进行重载a、代码实现首先来分析怎样重载迭代器的遍历是通过解引用来得到信息因此需要重载*运算符函数返回类型是T分析逻辑在写list_iterator时迭代器类的构造函数就会将_node指向迭代器变量所指的位置那么直接返回_node-_data即可Toperator*(){return_node-_data;}对于–我们的目的是能够到达下一个节点返回的是节点的地址即T*而_node中就存储着前一个节点和下一个节点的地址直接返回即可Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}最后再来实现一下和!booloperator(constSelfs)const{return_nodes._node;}booloperator!(constSelfs)const{return_node!s._node;}b、测试为了便于测试我们先实现push_back分析先new节点接着修改指针指向即可templateclassTvoidlistT::push_back(constTval){Node*newnodenewNode(val);_head-_prev-_nextnewnode;newnode-_prev_head-_prev;newnode-_next_head;_head-_prevnewnode;_size;}下面来测试一下对于内置类型没有问题接着来测试一下自定义类型编译报错问题就在于这个*it解引用之后拿到的是A的对象或者引用因此需要用.来访问这样显得有点麻烦不如直接重载-运算符返回_data的地址这样直接返回一个指针再用一个-即可解决注意两个-会省略成一个-T*operator-(){return_node-_data;}2、const_iterator首先思考一下const迭代器和普通迭代器的区别是什么const迭代器到底是迭代器本身不能被修改还是所指向的内容不能被修改答案显然是所指向的内容不能被修改在前面的vector中我们直接在begin,end的返回值改成const_iterator通过const成员函数重载同时函数后面也加上const这样返回值的类型就是const T ptr const,返回一个只读引用解引用之后只读避免迭代器所指向内容被修改而在list中显然不能直接在begin,end前加上const了因为这两个函数返回的只是第一个有效位置和最后一个位置的下一个位置的迭代器就算加上const返回值类型为const iterator对迭代器访问没有作用关键在于*运算符限制*的返回类型即可避免迭代器所指向的内容被修改a、代码实现理解完const_iterator之后发现与iterator的不同就是*运算符的不同那么该怎么写呢我们可以选择封装一个const_iterator类里面将*的返回值加上const即可//const_iteratortemplateclassTstructlist_const_iterator{typedeflist_nodeTNode;typedeflist_const_iteratorTSelf;list_const_iterator(Node*node):_node(node){}Node*_node;constToperator*()const{return_node-_data;}constT*operator-()const{return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}booloperator(constSelfs)const{return_nodes._node;}booloperator!(constSelfs)const{return_node!s._node;}};b、测试我们通过一个打印容器的函数模板来测试templateclassConvoidprint_container(constConcon){for(constautoe:con){std::coute ;}std::coutstd::endl;}3、优化对于iterator类以及const_iterator类两个类大体上高度相似真的有必要再重新封装一个类吗我们来看源码是怎么做的发现源码将模板参数设计成了三个参数并且也没有额外的类此时我们来分析一下Ref表示引用Ptr表示指针也就是说给list_iterator类的参数不同就实例化出不同的类我们来分析为什么给普通迭代器传的是T,T,T*而const迭代器则是T,const T,const T*?通过成员函数来分析主要来看*和-如果是普通迭代器对于*,我们返回的是Ref,而此时Ref就是T对于-我们返回的是Ptr此时Ptr就是T*完全符合情况如果是const迭代器对于*,我们返回的是Ref,而此时Ref就是const T对于-我们返回的是Ptr此时Ptr就是const T*同样完全符合情况因此源码直接设计方式非常优雅简洁我们也同样采用这种方式需要注意的是在list中对不同参数均需做出声明//迭代器//templateclass TtemplateclassT,classRef,classPtrstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;typedeflist_iteratorT,Ref,PtrSelf;list_iterator(Node*node):_node(node){}Node*_node;Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}其他成员函数保持原样即可四、核心接口实现1、insert分析逻辑注意返回值是迭代器指向第一个被插入的元素接着pos是迭代器在pos之前插入数据templateclassTlistT::iteratorlistT::insert(iterator pos,constTval){Node*newnodenewNode(val);Node*curpos._node;Node*prevcur-_prev;newnode-_prevprev;newnode-_nextcur;cur-_prevnewnode;prev-_nextnewnode;_size;returnnewnode;}来测试一下2、erase接着来看eraseiteratorerase(iterator position);iteratorerase(iterator first,iterator last);分析删除pos位置的节点更改指针指向即可最后返回pos位置的下一个节点的迭代器templateclassTlistT::iteratorlistT::erase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;curnullptr;--_size;returnnext;}来测试一下3、push_front、pop_front、pop_back这几个均直接复用代码即可voidpush_front(constTval){insert(begin(),val);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}五、完善结构1、构造函数下面我们实现list里面的构造函数default (1)explicit list (const allocator_type alloc allocator_type());fill (2)explicit list (size_type n, const value_type val value_type(), const allocator_type alloc allocator_type());range (3)template class InputIterator list (InputIterator first, InputIterator last, const allocator_type alloc allocator_type());copy (4)list (const list x);目前只实现了默认构造函数我们依次来实现对于n个val构造注意⚠️先创建出哨兵位再复用push_back直接将创建哨兵位封装成函数voidempty_init(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}//n个val构造list(size_t n,constTvalT()){//先创建头节点empty_init();for(size_t i1;in;i){push_back(val);}}对于迭代器区间构造首先创建出哨兵位接着同样复用push_back//迭代器区间构造templateclassInputIteratorlist(InputIterator first,InputIterator last){//先创建头节点empty_init();autoitfirst;while(it!last){push_back(*it);it;}}对于拷贝构造同样先创建哨兵位接着复用push_back即可//拷贝构造list(constlistlt){//先创建头节点empty_init();for(autoe:lt){push_back(e);}}我们来测试一下2、赋值运算符voidswap(listlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}//现代写法listoperator(list lt){swap(lt);return*this;}来测试一下3、析构函数最后来看析构函数分析逐个节点释放最终释放哨兵位不妨将逐个节点释放封装成函数voidclear(){autoitbegin();while(it!end()){iterase(it);}}~list(){clear();delete_head;_headnullptr;_size0;}六、总结至此我们已经越过了STL的两座大山——vector和list下面我们来总结一下两者的区别vectorlist底层动态数组双向链表随机访问O(1)O(n)插入删除中间慢快空间连续不连续迭代器随机迭代器双向迭代器如果觉得有帮助可以关注Github项目持续更新 手撕STL：list底层结构与迭代器实现
本文代码已同步Github一、底层源码分析1、源码剖析通过上一篇对vector的学习我们知道其底层是通过三个指针来充当迭代器下面我们来看一下list的底层是怎么设计的同样使用g中的SGI版本来观察先来看说明文档发现依据是多个头文件配合的形式那么核心文件便是stl_list.h我们来看一看发现和vector不同的是list里面有多个类比如list_node ,list_iterator,这些简单看一下类的名称及成员变量就会知道list_node是节点存储的是节点的信息看来底层确实是由一个双向链表来实现的list_iterator就是迭代器有一个list_node*的指针我们再往下看看还有没有其他的类还有一个类类名为list里面有一个list_node*的指针2、不同类之间的关系下面我们来理一理三个类之间的关系list用来控制整个链表无论是push_back还是insert等操作都通过list中的成员函数来实现而list_iterator是迭代器用来定位和访问通过重载–等操作符将迭代器封装成类似指针的效果最后的list_node就是一个一个的节点了好了根据上述对底层源码的简单分析之后我们来搭一下基础框架二、类模板框架搭建1、结构实现注意⚠️我们实现的仅仅是基础版为方便起见我们加入成员变量_sizenamespacestl{//节点templateclassTstructlist_node{list_node(constTdataT()):_data(data),_prev(nullptr),_next(nullptr){}T _data;list_nodeT*_prev;list_nodeT*_next;};//迭代器templateclassTstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorTSelf;list_iterator(Node*node):_node(node){}Node*_node;};templateclassTclasslist{public:typedeflist_nodeTNode;typedeflist_iteratorTiterator;private:Node*_head;size_t _size;public:};}下面我们来写list的默认构造函数分析首先要new一个节点这个节点即为哨兵位接着修改指针的指向并给_size赋值list(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}2、基础接口实现我们先来实现size和emptysize_tsize(){return_size;}boolempty(){return_size0;}接着来实现begin和end单参数构造函数可以进行隐式类型转换我们直接返回节点的地址即可iteratorbegin(){return_head-_next;}iteratorend(){return_head-_prev-_next;}三、迭代器实现1、iterator上一篇对list接口的介绍中我们知道list的迭代器是双向迭代器也就是说只能,--但是对于链表来说由于不是顺序存储因此对于普通指针无论是还是–之后都无法到达下一个节点此时我们就需要对运算符进行重载a、代码实现首先来分析怎样重载迭代器的遍历是通过解引用来得到信息因此需要重载*运算符函数返回类型是T分析逻辑在写list_iterator时迭代器类的构造函数就会将_node指向迭代器变量所指的位置那么直接返回_node-_data即可Toperator*(){return_node-_data;}对于–我们的目的是能够到达下一个节点返回的是节点的地址即T*而_node中就存储着前一个节点和下一个节点的地址直接返回即可Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}最后再来实现一下和!booloperator(constSelfs)const{return_nodes._node;}booloperator!(constSelfs)const{return_node!s._node;}b、测试为了便于测试我们先实现push_back分析先new节点接着修改指针指向即可templateclassTvoidlistT::push_back(constTval){Node*newnodenewNode(val);_head-_prev-_nextnewnode;newnode-_prev_head-_prev;newnode-_next_head;_head-_prevnewnode;_size;}下面来测试一下对于内置类型没有问题接着来测试一下自定义类型编译报错问题就在于这个*it解引用之后拿到的是A的对象或者引用因此需要用.来访问这样显得有点麻烦不如直接重载-运算符返回_data的地址这样直接返回一个指针再用一个-即可解决注意两个-会省略成一个-T*operator-(){return_node-_data;}2、const_iterator首先思考一下const迭代器和普通迭代器的区别是什么const迭代器到底是迭代器本身不能被修改还是所指向的内容不能被修改答案显然是所指向的内容不能被修改在前面的vector中我们直接在begin,end的返回值改成const_iterator通过const成员函数重载同时函数后面也加上const这样返回值的类型就是const T ptr const,返回一个只读引用解引用之后只读避免迭代器所指向内容被修改而在list中显然不能直接在begin,end前加上const了因为这两个函数返回的只是第一个有效位置和最后一个位置的下一个位置的迭代器就算加上const返回值类型为const iterator对迭代器访问没有作用关键在于*运算符限制*的返回类型即可避免迭代器所指向的内容被修改a、代码实现理解完const_iterator之后发现与iterator的不同就是*运算符的不同那么该怎么写呢我们可以选择封装一个const_iterator类里面将*的返回值加上const即可//const_iteratortemplateclassTstructlist_const_iterator{typedeflist_nodeTNode;typedeflist_const_iteratorTSelf;list_const_iterator(Node*node):_node(node){}Node*_node;constToperator*()const{return_node-_data;}constT*operator-()const{return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}booloperator(constSelfs)const{return_nodes._node;}booloperator!(constSelfs)const{return_node!s._node;}};b、测试我们通过一个打印容器的函数模板来测试templateclassConvoidprint_container(constConcon){for(constautoe:con){std::coute ;}std::coutstd::endl;}3、优化对于iterator类以及const_iterator类两个类大体上高度相似真的有必要再重新封装一个类吗我们来看源码是怎么做的发现源码将模板参数设计成了三个参数并且也没有额外的类此时我们来分析一下Ref表示引用Ptr表示指针也就是说给list_iterator类的参数不同就实例化出不同的类我们来分析为什么给普通迭代器传的是T,T,T*而const迭代器则是T,const T,const T*?通过成员函数来分析主要来看*和-如果是普通迭代器对于*,我们返回的是Ref,而此时Ref就是T对于-我们返回的是Ptr此时Ptr就是T*完全符合情况如果是const迭代器对于*,我们返回的是Ref,而此时Ref就是const T对于-我们返回的是Ptr此时Ptr就是const T*同样完全符合情况因此源码直接设计方式非常优雅简洁我们也同样采用这种方式需要注意的是在list中对不同参数均需做出声明//迭代器//templateclass TtemplateclassT,classRef,classPtrstructlist_iterator{typedeflist_nodeTNode;typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;typedeflist_iteratorT,Ref,PtrSelf;list_iterator(Node*node):_node(node){}Node*_node;Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}其他成员函数保持原样即可四、核心接口实现1、insert分析逻辑注意返回值是迭代器指向第一个被插入的元素接着pos是迭代器在pos之前插入数据templateclassTlistT::iteratorlistT::insert(iterator pos,constTval){Node*newnodenewNode(val);Node*curpos._node;Node*prevcur-_prev;newnode-_prevprev;newnode-_nextcur;cur-_prevnewnode;prev-_nextnewnode;_size;returnnewnode;}来测试一下2、erase接着来看eraseiteratorerase(iterator position);iteratorerase(iterator first,iterator last);分析删除pos位置的节点更改指针指向即可最后返回pos位置的下一个节点的迭代器templateclassTlistT::iteratorlistT::erase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;curnullptr;--_size;returnnext;}来测试一下3、push_front、pop_front、pop_back这几个均直接复用代码即可voidpush_front(constTval){insert(begin(),val);}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}五、完善结构1、构造函数下面我们实现list里面的构造函数default (1)explicit list (const allocator_type alloc allocator_type());fill (2)explicit list (size_type n, const value_type val value_type(), const allocator_type alloc allocator_type());range (3)template class InputIterator list (InputIterator first, InputIterator last, const allocator_type alloc allocator_type());copy (4)list (const list x);目前只实现了默认构造函数我们依次来实现对于n个val构造注意⚠️先创建出哨兵位再复用push_back直接将创建哨兵位封装成函数voidempty_init(){_headnewNode;_head-_prev_head;_head-_next_head;_size0;}//n个val构造list(size_t n,constTvalT()){//先创建头节点empty_init();for(size_t i1;in;i){push_back(val);}}对于迭代器区间构造首先创建出哨兵位接着同样复用push_back//迭代器区间构造templateclassInputIteratorlist(InputIterator first,InputIterator last){//先创建头节点empty_init();autoitfirst;while(it!last){push_back(*it);it;}}对于拷贝构造同样先创建哨兵位接着复用push_back即可//拷贝构造list(constlistlt){//先创建头节点empty_init();for(autoe:lt){push_back(e);}}我们来测试一下2、赋值运算符voidswap(listlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}//现代写法listoperator(list lt){swap(lt);return*this;}来测试一下3、析构函数最后来看析构函数分析逐个节点释放最终释放哨兵位不妨将逐个节点释放封装成函数voidclear(){autoitbegin();while(it!end()){iterase(it);}}~list(){clear();delete_head;_headnullptr;_size0;}六、总结至此我们已经越过了STL的两座大山——vector和list下面我们来总结一下两者的区别vectorlist底层动态数组双向链表随机访问O(1)O(n)插入删除中间慢快空间连续不连续迭代器随机迭代器双向迭代器如果觉得有帮助可以关注Github项目持续更新