目录

前言.

一. 思考关于list的迭代器的设计

二. 重要函数原型分析理解,有了这些先写出来看看效果

迭代器框架必备函数刨析

List框架必备函数刨析

三. 搭出大体框架

四. 函数细节分块分析 (和vector差不大多)

区间范围range构造

swap: 非常纯粹简单的换, 将你的成员换给我, 我就成了你，你就成为了我

拷贝构造    (因为有了swap, 我自身初始化为nullptr 避免野指针, 然后将复用range构造代码构造出来的tmp对象换来构造自身)

赋值重载

移动构造(抢夺将亡对象的堆区资源进行构造)

写完insert() + erase()接口，相当于是写好了六个接口

insert()

push_back()  复用insert函数

push_front()  复用insert函数

erase();

pop_back() 复用erase

pop_front() 复用erase

五. 总体代码 + 测试

六. 总结

前言.

• 欢迎大家来到小杰的手写STL章节，小杰会长期根据自己所学和浅显理解，尽力以比较简单口语的方式带着大家分析STL中各种重要容器的函数接口迭代器等等组件的设计，希望大家可以支持小杰，万分感谢.  
• 如下附上精彩前文连接

分块刨析从函数原型到分块实现C++STL(vector)_小杰312的博客-CSDN博客分块刨析从函数原型到分块实现C++STL(vector)https://blog.csdn.net/weixin_53695360/article/details/123248476?spm=1001.2014.3001.5501

一. 思考关于list的迭代器的设计

• 首先关于list的迭代器设计上面，不再像vector那般的简单了，因为 List 不是连续的存储空间在存储着元素，元素的访问也就没有办法像 vector中原生指针那样直接的进行 ++ 操作去访问后序元素，  但是迭代器就是可以支持做 ++  -- * 操作的一个这样一个类, 我们需要可以通过 ++  迭代器的操作  遍历访问整个容器中的元素
• 正因上述的需求，我们的  List 中的节点  LIstNode* pnode  便是需要专门为其设计一个迭代器类进行管理的，使得  pnode 可以通过  ++  的操作去访问下一个的元素,  -- 操作可以去访问上一个元素
• 所以大体上的思路出来了，一个struct iterator迭代器类封装管理一个ListNode* 的指针，功能就是一个智能指针类，管理一个ListNode* 指针,  对齐进行各种运算符重载：使得我们的ListNode* 指针可以通过 ++  -- 操作实现容器的遍历
• 结点类

•  迭代器类:   此处粘贴出来的仅仅只是迭代器的重要组件，理清楚思路，其他的迭代器的运算符重载函数的书写还是蛮easy的

•  首先：我们将迭代器设置成了三个模板参数，分别是T  Ref   Ptr, 这样做有什么必要吗？   答案肯定是肯定的，  STL源码中不可能无端设计出来三个模板参数呀
• 因为后序需要使用到ListIterator 还有 ListNode 但是这样带着模板写有点略显麻烦了，所以起得别名, self别名 代表迭代器本体类型

•  上述问题的解决其实就是在此处了， 核心关键就是两种迭代器的产生, 一种是const_iterator  另外一个是  iterator ，  一旦我们将其设置成三个模板参数，我们传入const 的时候他会按照模板的模子自动帮我们生成一份const类，我们就不再需要重新单独的为const 再专门设计出来一个类了, 没有必要做这个手工花销，有模板不必再自己新手写一个const 迭代器管理类了

二. 重要函数原型分析理解,有了这些先写出来看看效果

迭代器框架必备函数刨析

• operator * 重载就是取出其中的数据
• opeartor-> 重载就是取出数据的地址
• != 和 == 大家都懂, 判断是否是一个迭代器

•  ++  -- 操作迭代器必备的操作， 代表着前进和后退一个结点

List框架必备函数刨析

• 写默认构造很简单，一个没有数据的虚拟结点充当表头, 前后指针指向表头自身.

• 尾部插入一个结点, 三个过程

1. 拿到尾部结点指针 pTail, 创建出新的newnode结点
2. pTail和newnode 相连接, newnode 成为新的tail
3. 要构成循环，newnode 尾部结点需要和 head 相互连接

•  上述简简单单的写一下for_each   使用迭代器作为模板参数，不为别的，只为了让大家感受一下为啥迭代器   就能做各种容器和算法之间的粘合剂，没有迭代器就无法支持容器的遍历。。。             
• 因为没有迭代器管理对象指针，智能指针类，让其支持  ++  --  * 操作来泛型的遍历整个容器，且将容器中的元素进行算法func处理，     (STL的哪些所有的遍历算法都没法实现了，都瘫痪了)

三. 搭出大体框架

#include #include #include using namespace std;namespace tyj {//链表节点的设计, 双向循环链表templatestruct ListNode {ListNode(const T& _val = T()): pre(nullptr), next(nullptr), val(_val) {}ListNode* pre;ListNode* next;T val;};//分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的templatestruct ListIterator {typedef ListNode Node;typedef ListIterator self;Node* pnode;//Iterator管理的指针ListIterator(Node* _pnode = nullptr): pnode(_pnode) { }Ref operator*() {return pnode->val;//*重载访问val}Ptr operator->() {//支持->访问return &pnode->val;}bool operator!=(const self& obj) const {return pnode != obj.pnode;}bool operator==(const self& obj) const {return pnode == obj.pnode;}self& operator++() {//前置++ -- 操作返回本体pnode = pnode->next;return *this;}self operator++(int) {self before(*this);//返回的是之前的pnode = pnode->next;return before;}self& operator--() {pnode = pnode->pre;return *this;}self operator--(int) {self before(*this);pnode = pnode->pre;return before;}};templateclass List {typedef ListNode Node;//public:typedef ListIterator iterator;typedef ListIterator const_iterator;//此处体现出来了  Ref  Ptr模板化的好处了List() : head(new Node) {head->pre = head->next = head;//双向链表的最初状态}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 push_back(const T& val) {Node* pTail = head->pre;Node* newnode = new Node(val);//连接到尾部pTail->next = newnode;newnode->pre = pTail;//成环连接到head上newnode->next = head;head->pre = newnode;}private:Node* head;//头部指针指向头部结点};templatevoid for_each(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first++);}}templatestruct Print {void operator()(const T& val) const {cout << val << " ";}};}templatevoid PrintList(tyj::List& lt) {tyj::for_each(lt.begin(), lt.end(), tyj::Print());    cout << endl;}int main() {tyj::List lt;for (int i = 0; i < 5; ++i) {lt.push_back(i);}PrintList(lt);return 0;}

四. 函数细节分块分析 (和vector差不大多)

• 区间范围range构造

•  vector  和 list 都是这种方式实现的, 遍历传入区间，然后调用push_back 复用代码实现传入，一种常用的套路方式.
• swap为复用代码做准备

void swap(List& lt) {::swap(head, lt.head);}

• swap: 非常纯粹简单的换, 将你的成员换给我, 我就成了你，你就成为了我

• 拷贝构造    (因为有了swap, 我自身初始化为nullptr 避免野指针, 然后将复用range构造代码构造出来的tmp对象换来构造自身)

List(const List& lt) : head(nullptr) {List tmp(lt.begin(), lt.end());swap(tmp);//换, 复用范围构造}

• 赋值重载

//直接复用拷贝构造出来的ltList& operator=(List lt) {head = nullptr;swap(lt);return *this;}

• 纯纯的复用拷贝构造出来的lt对象，你反正是临时对象，出来作用域就要析构，我直接换掉你底层的堆区资源构造this，复用拷贝构造  (本质还是复用range构造) 

• 移动构造(抢夺将亡对象的堆区资源进行构造)

List(List&& lt) {    head = nullptr;swap(lt);}

• 移动构造，直接换，其他啥都不干，为啥它可以这样，拷贝构造都需要复用range范围构造构造构造出来一个tmp才能换,  但是移动构造是直接换,   
• 核心原因：移动构造传入的参数是一个右值，啥叫作右值，将死对象，临时对象，既然参数本来就是将亡对象，我直接就可使用它的底层堆区资源来构造自身

• 写完insert() + erase()接口，相当于是写好了六个接口

• insert()

• insert(pos, val);  在pos迭代器位置的前面插入一个值为val的结点newnode

• push_back()  复用insert函数

void push_back(const T& val) {insert(end(), val);    //在end()前插入一个newnode结点}

• push_front()  复用insert函数

void push_front(const T& val) {insert(begin(), val);    //在begin前插入一个newnode结点    }

• erase();

erase(pos)总结就是三句话:

1. 拿取pos前pre后next结点
2. delete pos
3. pre 和 next结点相连 

• pop_back() 复用erase

void pop_back() {erase(--end());    //删除end()前一个迭代器    //end() == head     //--end() == head->pre == pTail}

• pop_front() 复用erase

void pop_front() {erase(begin());    //begin() head->next;    //head->next == firstnode    //head是一个空头结点, firstnode才是真实的第一个元素}

五. 总体代码 + 测试

#include #include #include #include using namespace std;namespace tyj {//链表节点的设计, 双向循环链表templatestruct ListNode {ListNode(const T& _val = T()): pre(nullptr), next(nullptr), val(_val) {}ListNode* pre;ListNode* next;T val;};//分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的templatestruct ListIterator {typedef ListNode Node;typedef ListIterator self;Node* pnode;//Iterator管理的指针ListIterator(Node* _pnode = nullptr): pnode(_pnode) { }Ref operator*() {return pnode->val;//*重载访问val}Ptr operator->() {//支持->访问return &pnode->val;}bool operator!=(const self& obj) const {return pnode != obj.pnode;}bool operator==(const self& obj) const {return pnode == obj.pnode;}self& operator++() {//前置++ -- 操作返回本体pnode = pnode->next;return *this;}self operator++(int) {self before(*this);//返回的是之前的pnode = pnode->next;return before;}self& operator--() {pnode = pnode->pre;return *this;}self operator--(int) {self before(*this);pnode = pnode->pre;return before;}};templateclass List {typedef ListNode Node;public:typedef ListIterator iterator;typedef ListIterator const_iterator;//此处体现出来了  Ref  Ptr模板化的好处了List() : head(new Node) {head->pre = head->next = head;//双向链表的最初状态}templateList(InputIterator first, InputIterator last): head(new Node) {head->pre = head->next = head;while (first != last) {push_back(*first++);}}void swap(List& lt) {::swap(head, lt.head);}List(const List& lt): head(nullptr) {List tmp(lt.begin(), lt.end());swap(tmp);//换, 复用范围构造}//直接复用拷贝构造出来的ltList& operator=(List lt) {head = nullptr;swap(lt);return *this;}List(List&& lt) {swap(lt);}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);//虚拟头部结点}//在pos位置插入一个val void insert(iterator pos, const T& val) {assert(pos.pnode);//先断言结点位置存在, 不存在就无法插入Node* cur = pos.pnode;//先拿取到结点指针Node* pre = cur->pre;Node* newnode = new Node(val);//创建新的结点pre->next = newnode;newnode->pre = pre;//新的结点连接prenewnode->next = cur;cur->pre = newnode;//新的结点连接cur}void push_back(const T& val) {//Node* pTail = head->pre;//Node* newnode = new Node(val);连接到尾部//pTail->next = newnode;//newnode->pre = pTail;成环连接到head上//newnode->next = head;//head->pre = newnode;insert(end(), val);} void push_front(const T& val) {insert(begin(), val);}void pop_front() {erase(begin());}void pop_back() {erase(--end());}//删除pos迭代器位置元素返回下一个元素iterator erase(iterator pos) {assert(pos.pnode);//存在才可以做删除操作assert(pos != end());//拿取到前面一个结点和后一个结点Node* pre = pos.pnode->pre;Node* next = pos.pnode->next;//删除现在iteratordelete pos.pnode;pre->next = next;next->pre = pre;return iterator(next);}void clear() {Node* p = head->next, *q;while (p != head) {q = p->next;delete p;p = q;}delete head;}size_t size() {size_t ans = 0;Node* p = head->next;while (p != head) {ans += 1;p = p->next;}return ans;}~List() {if (head != nullptr)clear();head = nullptr;}private:Node* head;//头部指针指向头部结点};templatevoid for_each(InputIterator first, InputIterator last, Function f) {while (first != last) {f(*first++);}}templatestruct Print {void operator()(const T& val) const {cout << val << " ";}};}templatevoid PrintList(tyj::List& lt) {tyj::for_each(lt.begin(), lt.end(), tyj::Print());cout << endl;}// 测试List的构造void TestList1(){tyj::List l1;int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };tyj::List l3(array, array + sizeof(array) / sizeof(array[0]));PrintList(l3);tyj::List l4(l3);PrintList(l4);l1 = l4;PrintList(l1);}void TestList2(){// 测试PushBack与PopBacktyj::List l;l.push_back(1);l.push_back(2);l.push_back(3);PrintList(l);l.pop_back();l.pop_back();PrintList(l);l.pop_back();cout << l.size() << endl;// 测试PushFront与PopFrontl.push_front(1);l.push_front(2);l.push_front(3);PrintList(l);l.pop_front();l.pop_front();PrintList(l);l.pop_front();cout << l.size() << endl;}void TestList3(){int array[] = { 1, 2, 3, 4, 5 };tyj::List l(array, array + sizeof(array) / sizeof(array[0]));auto pos = l.begin();l.insert(l.begin(), 0);PrintList(l);++pos;l.insert(pos, 2);PrintList(l);l.erase(l.begin());l.erase(pos);PrintList(l);// pos指向的节点已经被删除，pos迭代器失效cout << *pos << endl;auto it = l.begin();while (it != l.end()){it = l.erase(it);}cout << l.size() << endl;}int main() {//tyj::List lt;//for (int i = 0; i < 5; ++i) {//lt.push_back(i);//}//PrintList(lt);//int arr[5] = { 1, 2, 3, 4, 5 };//tyj::List lt2(arr, arr + 5);//PrintList(lt2);/*TestList1();*//*TestList2();*/TestList3();return 0;}

六. 总结

• 就list对比vector而言, list更能够体现出来迭代器的设计重要性
• 本质来说STL的list底层就是一个双向循环的链表(数据结构)而已,  其中最最有价值的部分是  iterator的设计上面.   iterator是如何粘合  容器 + 算法的，这一点特别的重要
• 首先我们写链表需要先封装出来一个ListNode结构体:    
• 我们需要管理ListNode* 的指针于是我们需要设计出ListIterator类来支持各种指针的运算符重载，来支持特定的容器遍历方式，粘合算法
•  写STL 或者写一些小东西的经验之谈
• 首先看是否存在一定的框架，或者官方文档，如果存在，将其总体框架分成组件，将重要组件分别设计实现，针对重要的接口进行文档阅读，分析实现.
• 写出框架简单测试，框架没有问题之后我们可以看见小小的效果，喜悦心理，然后再慢慢的一点一点的啃食重点接口。。写完接口要及时测试
• 最终，对于整体代码进行各种特别情景下的测试。。。 找debug

感谢你阅读完了小杰的本篇文章，小杰后序还会根据自身掌握水平持续推出一些STL的设计书写思路，如果您觉着小杰写的还不错，劳烦关注支持一下，非常感谢，最后还是祝福大家都学习的学业专业有成，工作的都升职加薪