1.什么是list类？
1.list是在常数范围内在任意位置进行插入删除的序列容器，并且该容器可以实现双向迭代
2.list类的底层是双向带头循环链表结构，每个元素都存储在互不相关的独立节点中，每个节点都有指向其前后节点的指针
3.该类与forward_list非常相似，但后者是单链表，适用性不如list类
4.与vector,array,deque相比，list通常在任意位置插入和删除的效率更好
5.list类的缺陷：和foward_list一样，不支持任意位置的随机访问只能进行遍历访问，消耗大量时间，list类还需要额外空间去存储元素的关联信息，当元素较小时显得效率低下
2.list类的节点
1.使用struct,标明公有属性，以便从外部调用
2.list是带头双向循环链表
template <class T>
struct ListNode
{
ListNode<T>*_prev;
ListNode<T>*_last;
T_val;
Listnode(const T&val=T):_prev(nullptr),_last(nullptr),_val(val)
{}
};3.迭代器
1.与vector不同，由于物理空间上的不连续，导致迭代器不能像string或者vector那样设计为指针，而需封装为一个类，以便完成*，->,++,--等操作
1.成员变量与默认构造函数
1.仍然使用struct，标明公有属性成员变量是一个结点的指针
template <class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr>self;
ListIterator(Node* ptr)
:Node(ptr)
{}
Node* _Node;
};2.operator*
Ref operator*()
{
return _Node->_val;
}与之前代码进行对比
T& operator[](const int i)
{
assert(i < size());
return *(_start + i);
}
const T& operator[](const int i)const
{
assert(i < size());
return *(_start + i);
}很明显，为了对const和非const对象进行访问需要对函数进行分类重载，但此时operator*并没有对const和非const进行分类重载。由于权限的放大缩小原则，传参可以写成一样的，那就只有返回值不同了，所以直接使用模板泛型编程，直接设计参数Ref，把它当作返回值就可以实现重载的效果，这里的返回值是val类型的引用分为const和非const
3.operator->
Ptr operator->()
{
return &_Node->val;
}与operator*的实现相同，这就是迭代器模板参数有三个的原因，返回值是val类型的指针，分为const和非const
4.operator++
为了区分前置与后置，后置参数加int（无实际意义），参数在前传引用，参数在后传值
self& operator++()
{
_Node = _Node->_last;
return _Node;
}
self operator++(int)
{
Node* tmp = _Node;
_Node = _Node->last;
return tmp;
}5.operator--(与++同理)
self operator--(int)
{
Node* tmp = _Node;
_Node = _Node->_prev;
return tmp;
}
self operator--()
{
_Node = _Node->_prev;
return _Node;
}6.operator==
bool operator==(self& s)
{
return _Node == s._Node;
}7.operator!=
bool operator!=(self& s)
{
return _Node != s._Node;
}4.list
1.成员变量（head是哨兵位）
template<class T>
class List
{
public:
typedef ListNode Node;
private:
Node* _head;
};2.对迭代器的处理
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&,const T*> const_iterator;1.begin与end为正向迭代器，对迭代器进行++操作，迭代器向后移动
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动，不常用
1.begin
返回值类型要强制类型转换，而且返回值是head的下一个，不是哨兵位
iterator begin()
{
return iterator(_head->_last);
}
const_iterator begin()const
{
return const_iterator(_head->_last);
}2.end
返回值要强制类型转换，返回的是哨兵位
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}3.默认成员函数
1.构造函数
1.创建哨兵位，缺省参数
List(T val=T())
:_head(new Node)
{
_head->_last = _head;
_head->_prev = _head;
_head->_val = val;
}2.迭代器区间构造
template <class InputIterator>
List(InputIterator first, InputIterator last)
{
_head=new Node;
_head->_last = _head;
_head->_prev = _head;
_head->_val = T();
while (first != last)
{
push_back(*first);
++first;
}
}2.析构函数
~List()
{
clear();
delete _head;
_head = nullptr;
}clear的作用是消除哨兵位以外的节点
3.拷贝构造函数
List(List<T>& l)
{
_head(new Node);
_head->_last = _head;
_head->_prev = _head;
_head->_val = T();
List<T>tmp(l.begin(), l.end());
swap(tmp);
}4.operator=
传参变为传值，这样就会拷贝构造出一个临时对象，再使用list中的swap,交换*this与tmp的值，完成赋值重载
List<T>& operator=(List<T>l)
{
swap(l);
return*this;
}4.修改
1.insert（迭代器不会失效，本来在这个位置的节点后移）
void intsert(iterator pos,T val)
{
Node* cur = pos._Node;
Node* prev = cur->_prev;
Node* NewNode = new Node(val);
NewNode->_prev = prev;
prev->_last = NewNode;
NewNode->_last = cur;
cur->_prev = NewNode;
}2.push_front（头插）
void push_front(T val)
{
Node* NewNode = new Node(val);
Node* last = _head->_last;
NewNode->_prev = _head;
NewNode->_last = last;
last->_prev = NewNode;
_head->_last = NewNode;
}3.push_back（尾插）
void push_back(T val)
{
Node* NewNode = new Node(val);
Node* tail = _head->_prev;
tail->_last = NewNode;
NewNode->_prev = tail;
NewNode->_last = _head;
_head->_prev = NewNode;
}4.erase（指定位置删除）
断言防止删除哨兵位，返回删除节点的下一位，防止迭代器失效
iterator erase(iterator pos)
{
assert(pos!=end());
Node* cur = pos._Node;
Node* prev = cur->_prev;
Node* last = cur->_last;
prev->_last =last;
last->_prev = prev;
delete cur;
return iterator(last);
}5.pop_front（头删）
void pop_front()
{
erase(begin());
}6.pop_back（尾删）
void pop_back()
{
erase(--end());
}7.clear（清除除哨兵位外的所有节点）
void clear()
{
Node* New = _head->_last;
while (New != _head)
{
Node* News = New->_last;
delete New;
New = News;
}
}8.swap（交换两个list的值）
调用std库中的swap函数，要带有std::，否则会被认为是自己写的swap，导致无限递归
void swap(List<T>&l)
{
std::swap(_head,l._head);
}9.迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针， 迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此 在 list 中进行插入时是不会导致 list 的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响 。
5.与vector的对比
