1. 基本构造
list的底层其实是一个带头双向循环的链表，所以在模拟实现之前可以看一下库里面怎么实现的：
namespace ywh { //链表结构 template<class T> struct list_node { T _data; //节点中的数据 list_node<T>* _prev; //指向前一个节点的指针 list_node<T>* _next; //指向后一个节点的指针 //构造 list_node(const T& x = T()) :_data(x) , _prev(nullptr) , _next(nullptr) {} }; //list结构 template<class T> class list { public: typedef list_node<T> Node; public: //空初始化 void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _next; } //构造 list() { empty_init(); } private: Node* _head; //链表的头节点 size_t _size; //节点个数 }; }
2. 正向迭代器
在使用list的阶段的迭代器使用方法和之前的string、vector一样，但是了解过链表的结构都知道，链表要访问下一个节点就是使用节点中的next指针指向下一个节点，需要访问里面的数据需要找到里面的data，++和解引用并不能访问链表的节点，那么迭代器的使用在底层肯定是封装加运算符重载。
在实现迭代器的时候也需要采用封装和运算符重载，运算符重载需要用到++、--、!=、==、*、->等运算符。迭代器分为const迭代器和非const迭代器，首先先来看看非const迭代器：
2.1 非const迭代器
迭代器的实现一般使用struct来进行封装：
namespace ljm { //链表结构 template<class T> struct list_node { T _data; //节点中的数据 list_node<T>* _prev; //指向前一个节点的指针 list_node<T>* _next; //指向后一个节点的指针 //构造 list_node(const T& x = T()) :_data(x) , _prev(nullptr) , _next(nullptr) {} }; //非const正向迭代器 template<class T> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T> self; Node* _node; //迭代器构造 __list_iterator(Node* node) :_node(node) {} //前置 //operator++ self& operator++() { return _node->_next; } //operator-- self& operator--() { return _node->_prev; } //后置 self operator++(int) { self* tmp(_node); _node = _node->_next; return tmp; } //operator-- self operator--(int) { self* tmp(_node); _node = _node->_prev; return tmp; } //operator* T& operator*() { return _node->_data; } //operator-> T* operator->() { return &_node->_data; } //operator!= bool operator!=(const self& s) { return _node != s._node; } //operator== bool operator==(const self& s) { return _node == s._node; } }; //list结构 template<class T> class list { public: typedef list_node<T> Node; public: //空初始化 void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; } //构造 list() { empty_init(); } ///正向迭代器 iterator begin() { return iterator(_head->_next); //使用匿名对象进行构造 } iterator end() { return iterator(_head); } private: Node* _head; //链表的头节点 size_t _size; //节点个数 }; }
2.2 const迭代器
迭代器中涉及到修改的就是*和->，const迭代器的作用是指向的内容不能修改，本身不能修改，所以需要重新进行封装：
namespace ljm { //链表结构 template<class T> struct list_node { T _data; //节点中的数据 list_node<T>* _prev; //指向前一个节点的指针 list_node<T>* _next; //指向后一个节点的指针 //构造 list_node(const T& x = T()) :_data(x) , _prev(nullptr) , _next(nullptr) {} }; //非const正向迭代器 //... //const正向迭代器 template<class T> struct __list_const_iterator { typedef list_node<T> Node; typedef __list_const_iterator<T> self; Node* _node; //迭代器构造 __list_const_iterator(Node* node) :_node(node) {} //前置 //operator++ self& operator++() { _node = _node->_next; return *this; } //operator-- self& operator--() { _node = _node->_prev; return *this; } //后置 self operator++(int) { self* tmp(_node); _node = _node->_next; return tmp; } //operator-- self operator--(int) { self* tmp(_node); _node = _node->_prev; return tmp; } //operator* const T& operator*() { return _node->_data; } //operator-> const T* operator->() { return &_node->_data; } //operator!= bool operator!=(const self& s) { return _node != s._node; } //operator== bool operator==(const self& s) { return _node == s._node; } }; //list结构 template<class T> class list { public: typedef list_node<T> Node; typedef __list_iterator<T> iterator; typedef __list_const_iterator<T> const_iterator; public: 基本构造/// //空初始化 void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; } //构造 list() { empty_init(); } ///正向迭代器 iterator begin() { return iterator(_head->_next); //使用匿名对象进行构造 } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } private: Node* _head; //链表的头节点 size_t _size; //节点个数 }; }
2.3 正向迭代器的改进优化
上面的这两种写法不难看出有很多代码都是重复出现的，使得代码非常冗余，那么怎么将这些冗余的代码进行合并呢？
我们可以看一下库里面如何实现：
采用泛型编程，使用模板，将这一转化的工作交给编译器，而我们只需传递const参数和非const参数即可：
namespace ywh { //链表结构 template<class T> struct list_node { T _data; //节点中的数据 list_node<T>* _prev; //指向前一个节点的指针 list_node<T>* _next; //指向后一个节点的指针 //构造 list_node(const T& x = T()) :_data(x) , _prev(nullptr) , _next(nullptr) {} }; //非const正向迭代器 // 类型模板参数 传递引用 传递指针 template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; //迭代器构造 __list_iterator(Node* node) :_node(node) {} //前置 //operator++ self& operator++() { _node = _node->_next; return *this; } //operator-- self& operator--() { _node = _node->_prev; return *this; } //后置 self operator++(int) { self* tmp(_node); _node = _node->_next; return tmp; } //operator-- self operator--(int) { self* tmp(_node); _node = _node->_prev; return tmp; } //operator* Ref operator*() { return _node->_data; } //operator-> Ptr operator->() { return &_node->_data; } //operator!= bool operator!=(const self& s) { return _node != s._node; } //operator== bool operator==(const self& s) { return _node == s._node; } }; //list结构 template<class T> class list { public: typedef list_node<T> Node; typedef __list_iterator<T, T&, T*> iterator; //非const迭代器 typedef __list_iterator<T, const T&, const T*> const_iterator; //const迭代器 public: 基本构造/// //空初始化 void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; } //构造 list() { empty_init(); } ///正向迭代器 iterator begin() { return iterator(_head->_next); //使用匿名对象进行构造 } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } private: Node* _head; //链表的头节点 size_t _size; //节点个数 }; }
3. 修改相关接口
3.1 insert、erase
在pos位置进行插入删除比较简单，需要进行链接新节点，改变节点中指针的指向即可，库里面对于插入和删除都带有返回值，那么我们在实现的时候也加上返回值：
///修改相关接口 //在pos位置插入节点 iterator insert(iterator pos, const T& x) { //创建新新节点 Node* newnode = new Node(x); //链接节点 Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //更新节点个数 ++_size; //返回新节点的位置 return iterator(newnode); } //删掉pos位置的节点 iterator erase(iterator pos) { //保存相对位置 Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; //链接节点 delete cur; prev->_next = next; next->_prev = prev; //更新节点个数 --_size; //返回pos的下一个位置 return iterator(next); }
在进行insert之后可以看到迭代器是不会失效的，但是在erase之后pos位置会被释放，因此erase之后迭代器会失效，在使用前先更新迭代器。
3.2 尾插、头插、尾删、头删、清理
当实现了insert和erase之后，实现这些接口直接复用即可：
//尾插 void push_back(const T& x) { insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); } //清理 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
4. 拷贝构造、赋值重载、析构
在这里我们都是采用现代写法：
拷贝构造直接使用迭代器依次遍历进行尾插。
//拷贝构造 list(const list<T>& lt) { //先创建空节点 empty_init(); //依次尾插即可 for (auto e : lt) { push_back(e); } } //operator= void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } //析构 ~list() { clear(); delete _head; _head = nullptr; _size = 0; }
5. 完整代码
头文件：List.h
#pragma once namespace ywh { //链表结构 template<class T> struct list_node { T _data; //节点中的数据 list_node<T>* _prev; //指向前一个节点的指针 list_node<T>* _next; //指向后一个节点的指针 //构造 list_node(const T& x = T()) :_data(x) , _prev(nullptr) , _next(nullptr) {} }; //非const正向迭代器 // 类型模板参数 传递引用 传递指针 template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; //迭代器构造 __list_iterator(Node* node) :_node(node) {} //前置 //operator++ self& operator++() { _node = _node->_next; return *this; } //operator-- self& operator--() { _node = _node->_prev; return *this; } //后置 self operator++(int) { self* tmp(_node); _node = _node->_next; return tmp; } //operator-- self operator--(int) { self* tmp(_node); _node = _node->_prev; return tmp; } //operator* Ref operator*() { return _node->_data; } //operator-> Ptr operator->() { return &_node->_data; } //operator!= bool operator!=(const self& s) { return _node != s._node; } //operator== bool operator==(const self& s) { return _node == s._node; } }; //list结构 template<class T> class list { public: typedef list_node<T> Node; typedef __list_iterator<T, T&, T*> iterator; //非const迭代器 typedef __list_iterator<T, const T&, const T*> const_iterator; //const迭代器 public: 基本构造/// //空初始化 void empty_init() { _head = new Node; _head->_prev = _head; _head->_next = _head; } //构造 list() { empty_init(); } //拷贝构造 list(const list<T>& lt) { //先创建空节点 empty_init(); //依次尾插即可 for (auto e : lt) { push_back(e); } } //operator= void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } //析构 ~list() { clear(); delete _head; _head = nullptr; _size = 0; } ///正向迭代器 iterator begin() { return iterator(_head->_next); //使用匿名对象进行构造 } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } ///修改相关接口 //在pos位置插入节点 iterator insert(iterator pos, const T& x) { //创建新新节点 Node* newnode = new Node(x); //链接节点 Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //更新节点个数 ++_size; //返回新节点的位置 return iterator(newnode); } //删掉pos位置的节点 iterator erase(iterator pos) { //保存相对位置 Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; //链接节点 delete cur; prev->_next = next; next->_prev = prev; //更新节点个数 --_size; //返回pos的下一个位置 return iterator(next); } //尾插 void push_back(const T& x) { insert(end(), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); } //清理 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } //节点个数 size_t size() { return _size; } private: Node* _head; //链表的头节点 size_t _size; //节点个数 }; }
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
