C++【深入 STL--list 之 迭代器与反向迭代器】
接前面的手撕list(上)文章，由于本人对于list的了解再一次加深。本文再次对list进行深入的分析与实现。旨在再一次梳理思路，修炼代码内功。
1、list 基础架构
list底层为双向带头循环链表，问题是如何来搭建这个list类。可以进行下面的考虑：
| 1、list为带头双向循环链表，链表离不开节点。要能在list内部创建节点。 |
| 2、list内部没有数据时，也应该存在哨兵位头节点。 |
| 3、list内部的数据类型是未知的，需要写成类模板。 |
| 4、list支持迭代器访问数据，但是由于链表的结构来说，普通指针类型的迭代器不能实现++和解引用等基础访问操作，这就需要封装一个迭代器对象。 |
由于链表是双向的，所以节点的成员属性主要为三个：
- 节点指针类型的_next:指向该节点的下一个节点。
- 节点指针类型的_prev:指向该节点的前一个结点。
- 未知数据类型的数据_val:链表中存放的数据。
那么list的成员属性应该有什么？
- 头节点的指针_head: 作为链表的起始点，通过它可以访问链表的第一个元素和最后一个元素。在双向循环链表中，头节点的_next 指针指向链表的第一个有效节点，_prev指针指向链表的最后一个有效节点。
- 节点的个数_size:记录链表中有效节点的数量，方便快速获取链表的长度，而不需要遍历整个链表来计算。在插入和删除节点时，需要相应地更新这个计数器。
迭代器主要依赖于节点，利用节点才能找到节点当中的数据，并可以通过对运算符的重载实现迭代器本身的基础操作。故迭代器的成员属性为节点的指针。
由于在list当中要使用到节点当中的所有成员变量，所以这里直接就将节点类写为struct主要就是在内部的访问限定符默认为public，迭代器类型也是同样的道理。
namespace ltq
{
template<class T>
struct __list_node
{
__list_node<T>* _prev;
__list_node<T>* _next;
T _val;
};
template<class T>
struct __list_iterator
{
typedef __list_node<T> Node;
Node* _node;
};
template<class T>
class list
{
typedef __list_node<T> Node;
public:
typedef __list_iterator<T> iterator;
private:
Node* _head;
size_t _size;
};
}下面需要完善的就是三个类型的构造函数， 首先需要明确关系：list要使用的是节点类和迭代器类，在list类中创建了节点和迭代器对象就会去调用它们自己的构造函数。当然，在外部要是使用到list创建了对象，那么也会调用list自身的构造函数。
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}new先开辟空间，然后调用Node的构造函数，由于list的哨兵位节点中可以不用存放数据，所以直接调用Node的默认构造即可。下面就需要完善Node的默认构造。
template<class T>
struct __list_node
{
__list_node<T>* _prev;
__list_node<T>* _next;
T _val;
__list_node(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_val(x)
{}
};这里的默认构造使用缺省参数，当没有形参传过来时就创建T类型的匿名对象对节点中的数据进行初始化。
2、void push_back(const T& x)
双向带头循环链表的末尾插入需要找到末尾的节点，再创建新的节点进行链接。这里需要更新_size。
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newNode = new Node(x);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->_prev = newNode;
++_size;
}
3、迭代器
迭代器开始位置返回的是哨兵位头节点的下一个节点，迭代器的末尾返回的是哨兵位头节点的指针，这样设计就能实现左闭右开的区间。
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
在前面我故意没有写迭代器的构造函数，其实这里就会很明显的发现，不管是什么类型的迭代器在返回的时候都是传递节点的指针。由于单参数的构造函数支持隐式类型的转换，那么节点的指针就会通过迭代器的构造函数构造出一个迭代器对象并返回，这里需要注意的是，传值返回会生成临时对象，临时对象具有常性。
那么，我们现在来实现一下迭代器的构造函数。
template<class T>
struct __list_iterator
{
typedef __list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
};3.1、必要的运算符重载
T& operator*()
{
return _node->_val;
}
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
bool operator!=(const __list_iterator<T>& it)
{
return _node != it._node;
} 有了迭代器就支持范围for了，现在我们来测试一下目前的list是否可用：
3.2、箭头的重载
假如链表中存放的是结构体类型的数据，假设结构体为：
struct A
{
A(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1;
int _a2;
};
如果要访问A内部的数据，此时对迭代器进行解引用是不能访问到A内部的数据的。此时重载箭头，通过拿到A对象的地址，使用A的地址来达到访问内部数据的内容。重载箭头可以通过解引用再取地址的方式进行实现。
当然也可以通过使用对象+.的方式来进行访问。
4、iterator insert(iterator pos, const T& x)
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newNode = new Node(x);
newNode->_next = cur;
cur->_prev = newNode;
newNode->_prev = prev;
prev->_next = newNode;
++_size;
return newNode;
}虽然链表的插入不像vector的插入会产生扩容问题而引发迭代器失效，这里返回新插入节点的迭代器主要是方面插入之后的链式操作。其次与STL保持一致。
5、iterator erase(iterator pos)
删除当前迭代器位置，这里也不像vector，删除当前位置的数据并不影响后续节点的迭代器，但是当list删除当前节点时，会进行释放节点。那么当前节点的迭代器就会悬空，对悬空的迭代器进行操作就会引发错误，所以，在删除之后也会返回下一个节点的迭代器。
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}6、void clear()
内部调用erase函数对节点进行清除释放，但保留头节点。
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}7、拷贝构造
这里要进行深拷贝，先为新对象创建一个头结点，再使用范围for拿出目标链表中的每一个数据，直接进行push_back()操作即可。
list(const list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
for (auto& e:lt)
{
push_back(e);
}
}8、赋值重载
直接采用传值传参，传值传参调用拷贝构造，之后进行对象交换即可。
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}