一. 思考关于list的迭代器的设计
首先关于list的迭代器设计上面，不再像vector那般的简单了，因为 List 不是连续的存储空间在存储着元素，元素的访问也就没有办法像 vector中原生指针那样直接的进行 ++ 操作去访问后序元素， 但是迭代器就是可以支持做 ++ -- * 操作的一个这样一个类, 我们需要可以通过 ++ 迭代器的操作 遍历访问整个容器中的元素
正因上述的需求，我们的 List 中的节点 LIstNode* pnode 便是需要专门为其设计一个迭代器类进行管理的，使得 pnode 可以通过 ++ 的操作去访问下一个的元素, -- 操作可以去访问上一个元素
所以大体上的思路出来了，一个struct iterator迭代器类封装管理一个ListNode* 的指针，功能就是一个智能指针类，管理一个ListNode* 指针, 对齐进行各种运算符重载：使得我们的ListNode* 指针可以通过 ++ -- 操作实现容器的遍历
- 结点类
- 迭代器类: 此处粘贴出来的仅仅只是迭代器的重要组件，理清楚思路，其他的迭代器的运算符重载函数的书写还是蛮easy的
- 首先：我们将迭代器设置成了三个模板参数，分别是T Ref Ptr, 这样做有什么必要吗？ 答案肯定是肯定的， STL源码中不可能无端设计出来三个模板参数呀
因为后序需要使用到ListIterator<T, Ref, Ptr> 还有 ListNode<T> 但是这样带着模板写有点略显麻烦了，所以起得别名, self别名 代表迭代器本体类型
上述问题的解决其实就是在此处了， 核心关键就是两种迭代器的产生, 一种是const_iterator 另外一个是 iterator ， 一旦我们将其设置成三个模板参数，我们传入const 的时候他会按照模板的模子自动帮我们生成一份const类，我们就不再需要重新单独的为const 再专门设计出来一个类了, 没有必要做这个手工花销，有模板不必再自己新手写一个const 迭代器管理类了
二. 重要函数原型分析理解,有了这些先写出来看看效果
迭代器框架必备函数刨析
- operator * 重载就是取出其中的数据
- opeartor-> 重载就是取出数据的地址
- != 和 == 大家都懂, 判断是否是一个迭代器
- ++ -- 操作迭代器必备的操作， 代表着前进和后退一个结点
List框架必备函数刨析
- 写默认构造很简单，一个没有数据的虚拟结点充当表头, 前后指针指向表头自身.
- 尾部插入一个结点, 三个过程
- 拿到尾部结点指针 pTail, 创建出新的newnode结点
- pTail和newnode 相连接, newnode 成为新的tail
- 要构成循环，newnode 尾部结点需要和 head 相互连接
- 上述简简单单的写一下for_each 使用迭代器作为模板参数，不为别的，只为了让大家感受一下为啥迭代器 就能做各种容器和算法之间的粘合剂，没有迭代器就无法支持容器的遍历。。。
因为没有迭代器管理对象指针，智能指针类，让其支持 ++ -- * 操作来泛型的遍历整个容器，且将容器中的元素进行算法func处理， (STL的哪些所有的遍历算法都没法实现了，都瘫痪了)
三. 搭出大体框架
#include <iostream> #include <list> #include <assert.h> using namespace std; namespace tyj { //链表节点的设计, 双向循环链表 template<class T> struct ListNode { ListNode(const T& _val = T()) : pre(nullptr) , next(nullptr) , val(_val) { } ListNode<T>* pre; ListNode<T>* next; T val; }; //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的 template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr > 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; } }; template<class T> class List { typedef ListNode<T> Node;// public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> 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;//头部指针指向头部结点 }; template<class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first++); } } template<class T> struct Print { void operator()(const T& val) const { cout << val << " "; } }; } template<class T> void PrintList(tyj::List<T>& lt) { tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>()); cout << endl; } int main() { tyj::List<int> 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); //换, 复用范围构造 }
- 赋值重载
//直接复用拷贝构造出来的lt List& operator=(List lt) { head = nullptr; swap(lt); return *this; }
- 纯纯的复用拷贝构造出来的lt对象，你反正是临时对象，出来作用域就要析构，我直接换掉你底层的堆区资源构造this，复用拷贝构造 (本质还是复用range构造)
- 移动构造(抢夺将亡对象的堆区资源进行构造)
List(List&& lt) { head = nullptr; swap(lt); }
移动构造，直接换，其他啥都不干，为啥它可以这样，拷贝构造都需要复用range范围构造构造构造出来一个tmp才能换, 但是移动构造是直接换,
核心原因：移动构造传入的参数是一个右值，啥叫作右值，将死对象，临时对象，既然参数本来就是将亡对象，我直接就可使用它的底层堆区资源来构造自身
- 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)总结就是三句话:
- 拿取pos前pre后next结点
- delete pos
- 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 <iostream> #include <list> #include <algorithm> #include <assert.h> using namespace std; namespace tyj { //链表节点的设计, 双向循环链表 template<class T> struct ListNode { ListNode(const T& _val = T()) : pre(nullptr) , next(nullptr) , val(_val) { } ListNode<T>* pre; ListNode<T>* next; T val; }; //分析一下三个模板??? 为啥要三个，其实这个是STL源码里面这样设计的 template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr > 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; } }; template<class T> class List { typedef ListNode<T> Node; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; //此处体现出来了 Ref Ptr模板化的好处了 List() : head(new Node) { head->pre = head->next = head;//双向链表的最初状态 } template<class InputIterator> List(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); //换, 复用范围构造 } //直接复用拷贝构造出来的lt List& 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; //新的结点连接pre newnode->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; //删除现在iterator delete 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;//头部指针指向头部结点 }; template<class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first++); } } template<class T> struct Print { void operator()(const T& val) const { cout << val << " "; } }; } template<class T> void PrintList(tyj::List<T>& lt) { tyj::for_each(lt.begin(), lt.end(), tyj::Print<T>()); cout << endl; } // 测试List的构造 void TestList1() { tyj::List<int> l1; int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; tyj::List<int> l3(array, array + sizeof(array) / sizeof(array[0])); PrintList(l3); tyj::List<int> l4(l3); PrintList(l4); l1 = l4; PrintList(l1); } void TestList2() { // 测试PushBack与PopBack tyj::List<int> 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与PopFront l.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<int> 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<int> lt; //for (int i = 0; i < 5; ++i) { // lt.push_back(i); //} //PrintList(lt); //int arr[5] = { 1, 2, 3, 4, 5 }; //tyj::List<int> lt2(arr, arr + 5); //PrintList(lt2); /*TestList1();*/ /*TestList2();*/ TestList3(); return 0; }
六. 总结
就list对比vector而言, list更能够体现出来迭代器的设计重要性
本质来说STL的list底层就是一个双向循环的链表(数据结构)而已, 其中最最有价值的部分是 iterator的设计上面. iterator是如何粘合 容器 + 算法的，这一点特别的重要
首先我们写链表需要先封装出来一个ListNode结构体:
我们需要管理ListNode* 的指针于是我们需要设计出ListIterator类来支持各种指针的运算符重载，来支持特定的容器遍历方式，粘合算法
写STL 或者写一些小东西的经验之谈
首先看是否存在一定的框架，或者官方文档，如果存在，将其总体框架分成组件，将重要组件分别设计实现，针对重要的接口进行文档阅读，分析实现.
写出框架简单测试，框架没有问题之后我们可以看见小小的效果，喜悦心理，然后再慢慢的一点一点的啃食重点接口。。写完接口要及时测试
最终，对于整体代码进行各种特别情景下的测试。。。 找debug
感谢你阅读完了小杰的本篇文章，小杰后序还会根据自身掌握水平持续推出一些STL的设计书写思路，如果您觉着小杰写的还不错，劳烦关注支持一下，非常感谢，最后还是祝福大家都学习的学业专业有成，工作的都升职加薪
