结构和定义
list 的结构是一种带头双向循环链表，与单向不循环链表相比，双向循环链表找尾节点和进行节点操作时更方便快捷，哨兵位的设置也便于维护整个链表。
与单向链表相似，双向链表的物理结构是离散的，可以参考数据结构_单向链表。维护链表时，只需要维护头结点即可，即对于带头链表来说，只需要维护哨兵位节点即可。本文参考SGI STL模拟实现一个功能类似的 list 类，以达到深入学习的目的。
链表的节点定义和链表定义如下：
template<typename T>
struct list_node
{
typedef list_node<T> Node;
Node* _prev; //前驱指针
Node* _next; //后继指针
T _val;
//链表节点的构造函数
list_node(const T& val = T())
:_prev(nullptr),
_next(nullptr),
_val(val)
{ }
};
template<typename T>
class list
{
private:
typedef list_node<T> Node;
private:
Node* _head; //链表维护头结点
size_t _size;
/*…………*/迭代器
链表的物理结构是非连续的，所以其不能像 vector 那样直接使用普通指针作为迭代器。list 的迭代器必须可以指向 list 的某一个节点，同时可以进行递增、递减、取值和取址操作。对于链表来说，所谓的递增、递减操作其实是从指向当前节点转而指向下一个节点或前一个节点，而普通指针天生可以指向链表中的某个节点，所以 list 的迭代器可以通过封装普通指针实现。通过对指针的封装，并自定义迭代器递增、递减和进行其他操作时指针的行为，可以得到 list 的迭代器如下：
template<typename T, typename Ref, typename Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
//是对指向节点的指针_node的封装
Node* _node;
__list_iterator(Node* node)
:_node(node)
{ }
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
__list_iterator<T> tmp = *this;
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
__list_iterator<T> tmp = *this;
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template<typename T>
class list
{
private:
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
/*…………*/
//对于list，begin位置指向第一个有效数据节点，而end位置指向头结点
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
/*…………*/可以注意到，上面的迭代器声明中有三个模板参数，其中第一个模板参数针对的是链表存储数据的类型，而第二和第三个模板参数是为了区分普通对象和 const 对象，其中普通对象通过迭代器拿到的数据可读可写，const对象通过迭代器拿到的数据为只读，对节点数据的取址操作亦是如此，这两类对象迭代器实现的区别在于返回值的不同，将返回值设为模板可以避免多余的代码书写。
构造&析构和内存管理
对于 list 来说，只需要维护一个头结点即可，list 的构造即新建一个头结点，开始时该头结点的前驱指针和后继指针都指向头结点自己。对于析构函数，只需要逐个删除有效数据节点，并最终删除头结点即可。每次删除节点都会将节点的空间进行释放，当需要添加节点时，会申请一个新节点空间，并链接至链表中。
list()
{
empty_init();
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt) {
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
//为了减少重复代码，将空初始化组织成一个函数
void empty_init()
{
_head = new Node();
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
void clear()
{
while (!empty()) {
pop_back();
}
}
bool empty() const
{
return _size == 0;
}元素访问和操作
insert 和 erase 是进行链表元素增删的关键。为了正确将新节点插入链表，或者删除某个节点后保证链表形态的完整性，需要理清各个节点的指向关系。为了避免迭代器失效，需要设置 erase() 的返回值。规定 insert() 的返回值为指向第一个被插入节点的迭代器。
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
//创建新节点
Node* newNode = new Node(val);
Node* aimNode = pos._node; //目标节点
Node* preNode = aimNode->_prev; //记录目标节点的前驱节点
//将新节点接入链表
preNode->_next = newNode;
newNode->_prev = preNode;
newNode->_next = aimNode;
aimNode->_prev = newNode;
++_size; //修改_size
return newNode;
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
assert(!empty());
assert(pos != end()); //不允许删除头结点
Node* aimNode = pos._node;
Node* preNode = aimNode->_prev;
Node* nextNode = aimNode->_next;
delete aimNode; //删除目标节点
//重新组织原链表
preNode->_next = nextNode;
nextNode->_prev = preNode;
--_size;
return nextNode;
}
void push_back(const T& val)
{
insert(end(), val);
}
void pop_back()
{
assert(!empty());
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
assert(!empty());
erase(begin());
}
//交换链表，交换头结点和_size即可
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
size_t size()
{
return _size;
}对于 list 的赋值运算符重载，此处使用现代写法，将开辟空间和释放空间的工作交于构造函数和析构函数进行，利用 swap() 实现赋值。
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}迭代器失效问题
由于链表的物理空间是非连续的，各个节点独立占据一块空间，所以只有删除节点才会造成迭代器失效。当节点被删除后，所占物理空间被释放，该节点对应的迭代器失效。erase() 只会造成被删除节点的迭代器失效，而其他节点不受影响。
