list是链表的意思，由一个个节点组成

一、基本接口使用：

（1）与vector相同，有个尾插，也可以使用迭代器遍历：

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;//假如要删除指定位置的数据：//it = lt.begin();//lt.erase(it + 3);//物理空间不连续找不到指定位置
}

（2）emplace_back：也是插入，但是和尾插有区别：

假设有一个类A：

struct A
{
public:A(int a1 = 1, int a2 = 1):_a1(a1),_a2(a2){}int _a1;int _a2;};

插入A对象的数据：

void test_list2()
{list<A> lt1;A aa1(1, 1);lt1.push_back(aa1);lt1.push_back(A(2,2));lt1.emplace_back(aa1);lt1.emplace_back(A(2, 2));
}

但是emplace_back支持直接传构造A对象的参数，push_back不支持：

void test_list2()
{list<A> lt1;A aa1(1, 1);lt1.push_back(aa1);lt1.push_back(A(2,2));lt1.emplace_back(aa1);lt1.emplace_back(A(2, 2));//lt.push_back(3, 3);//不支持这样写lt1.emplace_back(3, 3);
}

（3）查询某个值并删除：

void test_list3()
{list<int> lt;lt.push_back(1);lt.emplace_back(2);lt.emplace_back(3);lt.emplace_back(4);for (auto e : lt){cout << e << " ";}cout << endl;//删除某个值：int x;cin >> x;//找到x：auto it = find(lt.begin(), lt.end(), x);if (it != lt.end()){lt.erase(it);}for (auto e : lt){cout << e << " ";}cout << endl;
}

（4）排序：sort()默认是升序，要实现降序可以使用仿函数greater<int> ls，less<int> ls用于升序。lt.sort(ls)，这样就可以实现降序。也可以直接传匿名对象lt.sort(greater<int>())。

void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(20);lt.push_back(3);lt.push_back(5);lt.push_back(4);lt.push_back(6);lt.push_back(1);for (auto e : lt){cout << e << " ";}cout << endl;//排序：lt.sort();//默认实现升序for (auto e : lt){cout << e << " ";}cout << endl;//降序，使用仿函数//less<int> ls;//用于升序//greater<int> ls;//用于降序//两个都是类模板//lt.sort(ls);//这样就实现了降序//也可以直接传匿名对象：lt.sort(greater<int>());for (auto e : lt){cout << e << " ";}cout << endl;
}

（5）两个链表合并：使用merge函数传合并的对象，最后传的对象内部会空。

void test5()
{//两个链表合并：list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();second.sort();//合并：first.merge(second);//取小的尾插，second最后空了
}

（6）去重：

void test_list6()
{list<int> lt;lt.push_back(1);lt.push_back(20);lt.push_back(5);lt.push_back(5);lt.push_back(4);lt.push_back(6);lt.push_back(1);for (auto e : lt){cout << e << " ";}cout << endl;//去重，先排序：lt.sort();lt.unique();for (auto e : lt){cout << e << " ";}cout << endl;
}

 （7）剪切：有两个链表对象1和2，将2的值剪切到1里面去，最后2会空。

void test_list7()
{list<int> mylist1,mylist2;list<int>::iterator it;for (int i = 1; i <= 4; i++)mylist1.push_back(i);for (int i = 1; i <= 4; i++)mylist2.push_back(i * 10);it = mylist1.begin();it++;mylist1.splice(it, mylist2);//将2的所有值剪切到1里面去for (auto e : mylist1){cout << e << " ";}cout << endl;
}

二、实现一个链表：

（1） 一个链表需要一个类来表示节点，还要一个类来实现链表的链接。

template <class T>
struct list_node//节点
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};
template <class T>
class list
{typedef list_node<T> Node;
public:list(){empty_init();}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}size_t size()const {return _size;}bool empty()const{return _size == 0;}
private:Node* _head;size_t _size;
};

用_size来记录节点的个数。

（2）基本的实现：

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;
}void push_front(T& x)
{insert(begin(), x);
}void 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;}void pop_back()
{erase(--end());
}void front_back()
{erase(begin);
}

（3）迭代器实现：由于链表在内存内部是不连续的，所以用迭代器的指针无法去直接++或者--，想要实现迭代器的基本功能必须对其他的运算符进行重载。需要写一个专门的类去封装迭代器。使用struct去定义类默认的成员都是公有，这样可以省事很多，方便之后的调用。

首先是重载*，需要返回内部的值，++则是返回下一个节点，--则是返回前一个节点。++和--分为前置和后置，后置则要返回原来的值。

struct list_iterator//默认是公有
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*()//重载*{return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}T* operator->(){return &_node->_data;}bool operator !=(const Self& s)//两个迭代器比较{return _node != s._node;}
};