目录
一、list节点
list作为一个链表，每个节点中都存储着前一个节点、后一个节点的位置和存储元素。
将list类中的成员变量设置为表示节点的类，再将前后指针以及节点存储的对象设置为节点类的成员变量。这有利于增强代码的健壮性和可读性。
template<class T>
struct ListNode
{
T _data;
ListNode<T>* _next;
ListNode<T>* _prev;
};
template<class T>
class list
{
typedef ListNode Node;
private:
Node* _head;//哨兵位
};二、接口
1、insert
我们目前只看第一个模板，在指定位置插入元素。
void insert(iterator pos, const T& val)
{
Node* sur = pos._node;
Node* tmp = new Node(val);
tmp->_next = sur;
tmp->_prev = sur->_prev;
sur->_prev->_next = tmp;
sur->_prev = tmp;
_size++;
}2、erase
同样我们只看第一个模板，删除指定位置的节点。
iterator erase(iterator pos)
{
Node* tmp = pos._node;
Node* p = pos._node->_next;
tmp->_prev->_next= tmp->_next;
tmp->_next->_prev = tmp->_prev;
delete tmp;
tmp = nullptr;
_size--;
return p;
}3、头插/删、尾插/删
实现这些插入删除操作我们可以复用之前的insert和erase。
void push_back(const T&x)
{
insert(end(), x);
_size++;
}
void push_front(const T& x)
{
insert(begin(), x);
_size++;
}
void pop_back()
{
erase(--end());
_size--;
}
void pop_front()
{
erase(begin());
_size--;
}4、clear
list的clear与vector的不一样，list的clear需要将list的内部的元素全部销毁。
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
_size = 0;
}三、默认成员函数
1、构造函数
初始化的时候将节点的前后指针都指向自己。
list()
{
_head = new Node;//别忘了new会调用构造函数
//_node->_data = T();
_head->_next = _head->_prev = _head;
}2、拷贝构造
将被拷贝对象内部元素一个个的push_back过去。
list(const list<T>&x)
{
//先初始化一下
_head = new Node;
_head->_next = _head->_prev = _head;
for (const auto& e : x)//范围for里的e是元素值，不是迭代器！
{
push_back(e);
}
}3、赋值重载
赋值重载需要注意不要自己给自己赋值。
先将利用被赋值对象创建一个新类，再将新类与赋值对象进行自定义的swap交换。
void swap(list<T>& x)
{
std::swap(_head, x._head);
}
// 赋值运算符：先拷贝 x 得到临时对象，再与临时对象交换
list<T>& operator=(const list<T>& x)
{
if (this != &x)
{
list<T> tmp(x);
swap(tmp);
}
_size = x._size;
return *this;
}4、析构
注意销毁哨兵位。
~list()
{
clear();
delete _head;
_head = nullptr;
}四、迭代器
list中的迭代器可能会参与一些运算，这就需要进行运算符重载，所以迭代器和节点一样封装为类。
1、const迭代器和非const迭代器
在const迭代器中，需要迭代器能够实现遍历但又要求指向内容不能够修改。
在之前实现的vector中，迭代器都是使用指针来实现的，而在指针左边进行const修饰时，指针本身可以修改但是指向内容不能修改这一要求已经满足。
但是由于list使用类来封装迭代器就导致经const修饰后迭代器本身不能被修改，这样也就无法进行遍历。
这时候就需要额外实现const迭代器。
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;
在上面我们可以看到模板中有三个参数，后面两个参数是用来规范const迭代器中运算符重载的，下面继续说明。
2、迭代器中的运算符重载
先提前说明一下模板参Re数解决const迭代器问题；Ptr 表示list存储类型的模板。
下面看一段代码：
T& operator*()
{
return _node->_data;
}
Re operator*()const
{
return _node->_data;
}返回类型为T&的为非const * 运算符重载，返回值为Re的为const * 运算符重载。
再看下面这段代码：
Ptr operator->()
{
return &_node->_data;
}->运算符重载后得到的返回类型与list存储类型是否为const类型相关。
现在再来看这两段代码：
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T,const T&,const T*> const_iterator;template<class T,class Re ,class Ptr>
struct _list_iterator
{
typedef ListNode<T> Node;
Node* _node;//成员变量
_list_iterator(Node*node)
:_node(node)
{ }
T& operator*()
{
return _node->_data;
}
Re operator*()const
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};T、Re、Ptr这三个模板参数巧妙的实现const和非const迭代器。
3、++和--的重载
++和--的返回值都是返回迭代器类型，所以我们还需要给迭代器类型起个好用的别名。
typedef _list_iterator<T, Re ,Ptr> MySelf;
MySelf& operator++()
{
_node = _node->_next;
return *this;
}
MySelf& operator++(int)//后置++
{
MySelf old(_node);//拷贝构造
_node = _node->_next;
return old;
}
MySelf& operator--()
{
_node = _node->_prev;
return *this;
}
MySelf& operator--(int)
{
MySelf old(_node);
_node = _node->_prev;
return old;
}4、其它运算符重载
bool operator!=(const MySelf& it)const
{
return _node != it._node;
//_node是自定义类型，判断是否相等需要看其地址是否相等
//ListNode结构体也不用额外是实现运算符重载
}
bool operator==(const MySelf& it)const
{
return _node == it._node;
}