👉前言👈
上一篇博客介绍了 list 的基本使用，那么本篇博客就带着大家来模拟实现 list。模拟实现 list 之前需要注意几个问题：第一，为了避免和库函数产生命名冲突，我们需要将我们的代码封装在命名空间里。第二，我们模拟实现的 list 是带哨兵位头节点的双向循环链表。
👉节点的创建👈
链表是一个节点连接着一个节点的，所以我们首先要将节点创建出来。
namespace Joy { template <class T> struct list_node { list_node* _prev; list_node* _next; T _data; list_node(const T& val = T()) : _prev(nullptr) , _next(nullptr) , _data(val) {} }; }
注：因为节点存储的数据可以是内置类型，也可以是自定义类型，所以我们要讲节点定义成模板类。还有就是以下的代码都是封装在命名空间里。
👉list 的构建👈
list 的框架
我们已经将节点定义好了，那么我们现在就来搭建 list 的基本框架。因为我们实现的是带哨兵位头节点的双向循环链表，所以 list 的成员变量只需要哨兵位的头节点 _head就行了。
template <class T> class list { typedef list_node<T> node; private: node* _head; // 哨兵位头节点 };
注：为了方便使用list_node<T>，我们可以将其重命名为node。以下的函数接口均是 public 修饰。
无参的构造函数
无参的构造函数主要是申请哨兵位的头节点，然后该哨兵位头节点的
_prev和_next都指向自己。
// ... list() { _head = new node; // 申请一个哨兵位头节点 _head->_next = _head; _head->_prev = _head; } // ...
push_back 和 push_front
因为
_head->_prev就是尾结点，所以根据双向循环链表的特性，我们就很容易将尾插函数写出来。
// ... void push_back(const T& val) { node* tail = _head->_prev; node* newnode = new node(x); // _head tail newnode tail->_next = newnode; newnode->_prev = tail; _head->_prev = newnode; newnode->next = _head; } // ...
void push_front(const T& x) { node* head = _head->_next; node* newnode = new node(x); // _head newnode head _head->_next = newnode; newnode->_prev = _head; newnode->_next = head; head->_prev = newnode; }
正向迭代器
迭代器是类的内嵌类型，所以我们使用迭代器时需要指定类域。迭代器用起来像是指针，支持解引用，++ 和 - -
其底层的实现不一定是原生指针，而 vector 的正向迭代器的底层就是原生指针。因为 vector 的空间是连续的，++ 和 - - 就能够找到后一个数据和前一个数据 。而链表的空间是不连续的，那么 ++ 和 - - 就不能找到后一个数据和前一个数据了。但是，我们又想支持这样的使用方法，那怎么办呢？我们可以将迭代器封装成一个类，然后利用运算符重载来支持 ++ 和 - - 的用法。
以上的做法也是 stl 源码中的实现方式。
// 像指针一样的对象 template <class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; // Ref是T&，Ptr是T*，Self是迭代器 node* _pnode; // 正向迭代器的成员变量，_pnode是指向节点的指针 __list_iterator(node* pnode = nullptr) : _pnode(pnode) {} // 因为T有可能是自定义类型，所以返回值设置为引用Ref，可以减少拷贝构造 Ref operator*() const { return _pnode->_data; // 返回节点的数据 } // 比较节点的指针是否不相等即可 bool operator!=(const Self& it) const { return _pnode != it._pnode; } // 比较节点的指针是否相等即可 bool operator==(const Self& it) const { return _pnode == it._pnode; } // 返回节点数据的地址 Ptr operator->() { return &(operator*()); } // 因为链表是通过指针连接起来的，那么_pnode = _pnode->_next就相当于迭代器++ // ++it，前置++的返回值为++之后的值 Self& operator++() { _pnode = _pnode->_next; return *this; } // it++，后置++的返回值为++之前的值 Self operator++(int) { Self tmp(*this); _pnode = _pnode->_next; return *this; } // --it Self& operator--() { _pnode = _pnode->_prev; return *this; } // it-- Self operator--(int) { Self tmp(*this); _pnode = _pnode->_prev; return tmp; } };
因为链表中的节点是通过指针来建立联系的，所以正向迭代器的成员变量就可以是节点指针_pnode了。那么_pnode = _pnode->_next就相当于迭代器 ++。
为什么正向迭代器有三个模板参数？
正向迭代器有三个模板参数主要是为了避免代码冗余。因为除了实现没有const修饰的正向迭代器，我们还需要实现有const修饰的正向迭代器，所以我们只需要修改模板参数的类型就能同时实现两个迭代器了，从而避免代码的冗余。
const 迭代器的易错点
const T* p1和T* const p2，const 迭代器类似 p1 的行为，保护指向的对象不被修改，迭代器本身可以修改。
为什么要有operator->函数重载？
struct Pos { int _row; int _col; Pos(int row = 0, int col = 0) : _row(row) , _col(col) {} }; void listTest5() { list<Pos> lt; Pos p1(1, 1); lt.push_back(p1); lt.push_back(p1); lt.push_back(p1); lt.push_back(p1); lt.push_back(Pos(2, 2)); lt.push_back(Pos(3, 3)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it)._row << ':' << (*it)._col << endl; ++it; } cout << endl; }
有时候，链表的数据类型有可能是自定义类型。而我们想数据自定义类型的数据，这时候就可以通过流插入。如果不是使用流插入的话，可能会出现像上面(*it)._row和(*it)._col的写法。这样的写法并不好。那么为了解决这个问题，就需要借助operator->重载函数了。这个函数返回的是节点数据的地址。
迭代器是否需要析构函数？
默认生成的析构函数对于自定义类型，会调用该自定义类型的析构函数；而对于内置类型，编译器不做处理。知道了这个，那么迭代器需不需析构函数就显而易见了。迭代器不需要析构函数，如果有析构函数的话，就会把链表的节点给释放掉。这是我们不希望看到的。那如果我们不写析构函数，默认生成的析构函数会不会做出处理呢？也不会，因为迭代器的成员变量是指针（内置类型），它不会轻易地释放这个资源。
迭代器是否需要深拷贝
之前我们说过，需要自己写析构函数的自定义类型，都需要自己写拷贝构造（深拷贝）。那么，很明显迭代器不需要深拷贝。因为迭代器不需要写析构函数，浅拷贝也能够完成任务。
typedef list_node<T> node; typedef __list_iterator<T, T&, T*> iterator; // 正向迭代器 typedef __list_iterator<T, const T&, const T*> const_iterator; // const正向迭代器 const_iterator begin() const { // const_iterator it(head->_next); // return it // 匿名对象 return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); }
注：迭代器的begin就是_head->_next，而迭代器的end就是最后一个数据的下一个位置，也就是哨兵位头节点_head。
现在正向迭代器就实现完了，那么我们通过下面的测试用例来测试一下迭代器写得对不对。
void listTest1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); // 拷贝够，迭代器浅拷贝就可以了 while (it != lt.end()) { cout << *it << " "; // 调用operator*()函数 ++it; // 调用operator++()函数 } cout << endl; it = lt.begin(); while (it != lt.end()) { *it *= 2; ++it; } // 傻瓜式替换成迭代器，如果名字对不上就会报错 for (auto e : lt) { cout << e << " "; } cout << endl; }
注：比较迭代器最好使用 != 或者 ==，而只有string 和1 vector 能够使用 > 和 < 来比较迭代器，因为这两个容器的空间是连续的。vector 的正向迭代器也不一定是原生指针，sgi 版（g++）的 vector 迭代器是原生指针，而 pj 版（VS）的 vector 迭代器不是原生指针。
迭代器的价值
- 封装底层实现，不暴露底层的实现细节
- 提供统一的访问方式，降低使用成本
