@[TOC]
底层说明：list的底层实现为带头的双向链表
成员变量
代码语言：javascript复制cpp template<class T>
struct Node
{
Node* prve;
Node* next;
T data;
Node(const T &x=T())
:prve(nullptr)
,next(nullptr)
,data(x)
{}
};
template<class T>
class list
{
typedef Node<T> Node;
Node* head;
}构造函数
代码语言：javascript复制为什么会加一个
empty_init函数呢？因为对于一些含参的构造或者是拷贝构造，都需要初始化，不能让head为野指针。
cpp void empty_init()
{
head = new Node;
head->prve = head;
head->next = head;
}
list()
{
empty_init();
}
template<class Iterator>
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first;
}
}
list(int n, const T& x = T())
{
empty_init();
while (n--)
{
push_back(x);
}
}拷贝构造
代码语言：javascript复制cpp list(const list<T>& it)
{
empty_init();
list<T> temp;
const_iterator cur = it.begin();
while (cur != it.end())
{
temp.push_back(*cur);
cur;
}
swap(temp);
}析构函数
代码语言：javascript复制cpp ~list()
{
clear();
delete head;
head = nullptr;
}迭代器
代码语言：javascript复制cpp template<class T,class ref,class ptr>
struct __iterator
{
typedef Node<T> Node;
typedef __iterator<T, ref, ptr> Self;
Node* node;
__iterator(Node* cur)
:node(cur)
{}
Self operator ()
{
node = node->next;
return *this;
}
Self operator (int)
{
Node* temp = node;
node = node->next;
return Self(temp);
}
Self operator--()
{
node = node->prve;
return *this;
}
Self operator--(int)
{
Node* temp = node;
node = node->prve;
return Self(temp);
}
ref operator*()
{
return node->data;
}
ptr operator->()
{
return &(node->data);
}
bool operator!=(Self x)
{
return node != x.node;
}
};任意位置插
代码语言：javascript复制cpp iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos.node;
Node* pcur = cur->prve;
pcur->next = newnode;
newnode->prve = pcur;
newnode->next = cur;
cur->prve = newnode;
return iterator(newnode);
}任意位置删
代码语言：javascript复制cpp iterator erase(iterator pos)
{
Node* cur = pos.node;
Node* pcur = cur->prve;
Node* _next = cur->next;
pcur->next = cur->next;
cur->next->prve = pcur;
delete cur;
return iterator(_next);
}元素获得
获得尾元素
代码语言：javascript复制cpp T& back()
{
return head->prve->data;
}获得首元素
代码语言：javascript复制cpp T& front()
{
return head->next->data;
}是否为空
代码语言：javascript复制cpp bool empty()
{
return head->next == head;
}
