上一篇说到，list 其实就是带哨兵位循环双向链表而已，这种链表虽然结构复杂，
但是实现起来反而是最简单的，我们在数据结构与算法专栏中有过详细的讲解：
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现_GR C的博客-CSDN博客
当时我们是用C语言实现，这里对 list 的实现其实也是大同小异的。
当然，我们重点还是倾向于去理解它的底层实现原理，
所以我们将对其实现方式进行进一步地简化，并且按照我们自己习惯的命名风格去走。
我们之前已经模拟实现过 string 和 vector 了，这是本专栏 STL 的第三个模拟实现，
因此在讲解的时，出现重复的知识点我们就一笔带过。我们将重点去讲解迭代器的实现！
本章我们要对迭代器有一个新的认知，迭代器不一定就是一个原生指针，
也有可能是一个自定义类型。
本章我们将通过自定义类型的运算符重载去控制我们的迭代器的 "行为"。
1. list 的基本框架
我们还是参考《STL源码剖析》，既然是要实现链表，我们首先要做的应该是建构结点。
此外，为了和真正的 list 进行区分，我们这里仍然在自己的命名空间内实现。
1.1 list 的结点
C语言写的： 
C++的代码：
template<class T> struct list_node { T _data; list_node* _prev; list_node* _next; };
C++中对象里的成员如果全是共有的还是比较习惯用 struct 的
我们知道，结构体 struct 在 C++ 中升级成了类，因此它也有调用构造函数的权利。
也就是说，在创建结构体对象的时会调用构造函数。
既然如此，结点的初始化工作，可以考虑写一个构造函数去初始化：
template<class T> struct list_node { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} };
设计成全缺省，给一个匿名对象 T() 。如此一来，如果没有指定初识值，
它就会按模板类型去给对应的初始值了。
1.2 list 构造函数
设计好结点后，我们现在可以开始实现 list 类了。
考虑到我们刚才实现的 "结点" ListNode 类型比较长，为了美观我们将其 typedef 成 Node
因为是带头（哨兵位）双向循环链表，我们先要带个头。
我们先要把头结点 _pHead 给设计出来，而 _prev 和 _next 是默认指向头结点的。
到这里 list.h 就是这样：
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T> class list // 定义list类 { typedef list_node<T> Node; public: list() { _head = new Node; _head->_prev = _head; _head->_next = _head; } private: Node* _head; // 哨兵位头结点 }; }
1.3 push_back
我们先去实现一下最经典的 push_back 尾插，好让我们的 list 先跑起来。
尾插思路和以前写过的思路一样，后面很多接口也是，不懂的回去看啊，别逼我求你，
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现_GR C的博客-CSDN博客
直接放代码了：
void push_back(const T& x) { Node* tail = _head->_prev; Node* NewNode = new Node(x); // 思路图：head tail NewNode tail->_next = NewNode; NewNode->_prev = tail; _head->_prev = NewNode; NewNode->_next = _head; }
我们想要打印的话就只能自己实现迭代器了：
2. list 迭代器的实现
list 的重点是迭代器，因为这里的迭代器的实现和我们之前讲的实现方式都不同。
我们之前讲的 string 和 vector 的迭代器都是一个原生指针，实现起来是非常简单的。
但是 list 是一个链表，你的迭代器还能这样去实现吗？在空间上不是连续的，如何往后走？
而这些所谓的 "链接" 其实都是我们想象出来的，实际上根本就不存在。
而这些链接的含义只是 "我存的就是你的地址" ，所以我可以找到你的位置。
而我要到下一个位置的重点是 —— 解引用能取到数据，++ 移动到下一位。
而自带的 解引用* 和 ++ 的功能，是没法在链表中操作的。
但是，得益于C++有运算符重载的功能，我们可以用一个类型去对结点的指针进行封装，
然后重载运算符 operator++ 和 operator* ，
是不是就可以控制其解引用并 ++ 到下一个位置了？
所以，我们首先要做的是对这两个运算符进行重载：
2.1 迭代器的构造
代码：只需要用一个结点的指针
template<class T> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T> iterator; // STL规定的命名，且公有 Node* _node; iterator(Node* node) :_node(node) {} };
这里命名是参考源码的，__list_iterator 前面是两个下划线。
我们想要打印的话应该是这样的：
list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl;
所以我们来实现这几个操作
2.2 begin() 和 end()
代码：在 list 类中设计 begin 和 end
template<class T> class list // 定义list类 { typedef list_node<T> Node; public: typedef __list_iterator<T> iterator; // STL规定的命名，且公有 iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } list() { _head = new Node; _head->_prev = _head; _head->_next = _head; } void push_back(const T& x) { Node* tail = _head->_prev; Node* NewNode = new Node(x); // 思路图：head tail NewNode tail->_next = NewNode; NewNode->_prev = tail; _head->_prev = NewNode; NewNode->_next = _head; } private: Node* _head; // 哨兵位头结点 };
2.3 重载 != 和 * 和 ++
operator!=
如何判断是否相等呢？
如果两个迭代器结点的指针指向的是同一个结点，那就说明是相等的迭代器：
bool operator!=(const iterator& it) { return _node != it._node; }
operator*
解引用就是取结点 _node 里的数据，并且 operator* 和指针一样，不仅仅能读数据，还能写数据。
为了使 operator* 能支持修改的操作，我们这里用引用返回 & （返回 _node 中 _data 的别名）
T& operator*() { return _node->_data; // 返回结点的数据 }
operator++
加加分为前置和后置，我们这里先实现前置++：
iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 }
因为前置是直接改变本体，我们直接 return *this 即可。
因为出了作用域还在，所以可以用引用返回， __list_iterator&
对应的，后置++ 我们可以拷贝构造出一个 tmp 存储原来的值，这样虽然改变本体了，
但是返回的还是之前的值，这就实现了后置++。此外，因为前置++后置++都是 operator++，
区分方式是后置++用占位符 (int) 占位，这些知识点在之前讲解日期类的时候都说过。
后置++的实现：（注意后置++不能用引用返回）
iterator operator++(int) { __list_iterator<T> tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->next; return tmp; // 返回加加前的值 }
2.4 遍历测试：
至此，可以遍历打印我们的代码了，而且范围for也能用了：
list.h
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T> iterator; // STL规定的命名，且公有 Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) { return _node != it._node; } T& operator*() { return _node->_data; // 返回结点的数据 } iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 } iterator& operator++(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->next; return tmp; // 返回加加后的值 } }; template<class T> class list // 定义list类 { typedef list_node<T> Node; public: typedef __list_iterator<T> iterator; // STL规定的命名，且公有 iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } list() { _head = new Node; _head->_prev = _head; _head->_next = _head; } void push_back(const T& x) { Node* tail = _head->_prev; Node* NewNode = new Node(x); // 思路图：head tail NewNode tail->_next = NewNode; NewNode->_prev = tail; _head->_prev = NewNode; NewNode->_next = _head; } private: Node* _head; // 哨兵位头结点 }; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_push_back() { 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 << " "; ++it; } cout << endl; for (const auto& e : lt) { cout << e << " "; } cout << endl; } } int main() { rtx::Test_push_back(); return 0; }
2.6 operator->
迭代器是像指针一样的，所以要重载两个解引用。
为什么？指针如果指向的类型是原生的普通类型，要取对象是可以用解引用，
但是如果指向而是一个结构，并且我们又要取它的每一个成员变量，
比如我们想打印坐标：
void Test_arrow() { struct Pos { int _a1; int _a2; Pos(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; Pos aa; Pos* p2 = &aa; p2->_a1; p2->_a2; list<Pos> lt; lt.push_back(Pos(10, 20)); lt.push_back(Pos(10, 21)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it)._a1 << "，" << (*it)._a2 << endl; //cout << it->_a1 << "，" << it->_a2 << endl; ++it; } cout << endl; }
虽然能用解引用+点操作符，但用箭头还是方便的，而且你模拟实现总不能不给别人用吧，
所以我们这里可以去实现一下箭头操作符 operator->，如果不是很熟练应该是不会的。
我们直接看一下源代码是怎么实现的，抄下来用用然后思考下：
T& operator*() { return _node->_data; // 返回结点的数据 } T* operator->() { return &(operator*()); //即 return &(_node->_data); }
void Test_arrow() { struct Pos { int _a1; int _a2; Pos(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; Pos aa; Pos* p2 = &aa; p2->_a1; p2->_a2; list<Pos> lt; lt.push_back(Pos(10, 20)); lt.push_back(Pos(10, 21)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1 << "，" << (*it)._a2 << endl; cout << it->_a1 << "，" << it->_a2 << endl; //实际要写，it->->_a1，但是编译器优化了一个箭头 ++it; } cout << endl; }
第一个指针是operator->，第二个指针是原生指针的箭头，但是编译器为了可读性：
所有类型重载 operator-> 时都会省略一个箭头。
从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器（中）：https://developer.aliyun.com/article/1521342
