介绍：
C语言中我们学习过链表，链表其实就是多个节点通过指针连在一起，而list其实是一个双向循环链表,可以通过任意一个节点来找到所有节点。
与vector的用法大致相同，只不过两者的物理结构有所不同，一个是连续空间的存储，一个是非连续空间存储，二者的也有各自的优缺点。
用法：
由标准C++库中的list来学习：
如何定义一个list：
#include<list>
list<T> name; //定义一个类型为T，名字为name的空list
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5); // l1 : 1 2 3 4 5list<int>::iterator it = l1.begin(); // begin()表示l1的起始位置
for (; it != l1.end(); it++) { // end()表示l1的末尾位置cout << *it << " ";
}
cout << endl; // printf => 1 2 3 4 5list<int>::reverse_iterator rt = l1.rbegin(); // rbegin()表示l1的末尾位置
for (; rt != l1.rend(); rt++) { // rend()表示l1的起始位置cout << *rt << " ";
}
cout << endl; // printf => 5 4 3 2 1
上面的含义和用法与vector差不多，不再过多介绍
int main() {list<int> l1; // l1 ：1 2 3 4 5l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);list<int> l2; // l2：10 20 30 40 50l2.push_back(10);l2.push_back(20);l2.push_back(30);l2.push_back(40);l2.push_back(50);//将l2转移到l1的起始位置之前l1.splice(l1.begin(), l2); // l1 ：10 20 30 40 50 1 2 3 4 5// l2 ：(empty)//将l1的起始元素转移到l2的起始位置l2.splice(l2.begin(), l1, l1.begin());// l1 : 20 30 40 50 1 2 3 4 5// l2 : 10list<int>::iterator it1 = l1.begin();it1++;//可以将l1的一段迭代器区间转移给l2l2.splice(l2.end(), l1, it1, l1.end());// l1 : 20// l2 : 10 30 40 50 1 2 3 4 5//可以将l2自己的转移给l2自己，将l2的begin()位置的元素插入到l2的end()位置之前l2.splice(l2.end(), l2, l2.begin());// l2 : 30 40 50 1 2 3 4 5 10return 0;
}
int main(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);//l1 : 1 2 3 4 5l1.remove(3);// 移除l1中的元素3//l1 : 1 2 4 5return 0;
} 
int main() {list<int> l1;l1.push_back(5);l1.push_back(4);l1.push_back(3);l1.push_back(2);l1.push_back(1);// l1 : 5 4 3 2 1l1.sort();//sort在默认情况下是排顺序// l1 : 1 2 3 4 5l1.sort(greater<int>());//仿函数，可以让其更换排序方式// l1 : 5 4 3 2 1return 0;
}但是list的排序效率不高
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;void test_op1() {srand(time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0; i < N; i++) {auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort:" << (end1-begin1) << endl;cout << "list sort:" << (end2 - begin2) << endl;}int main() {test_op1();return 0;
}
list的排序底层是归并排序，由于list不像vector的数据是连续的，所以在排序的时候访问效率不高
list的模拟实现：
#pragma once // 确保头文件只被包含一次
#include<assert.h> // 引入断言库
#include<iostream> // 引入输入输出流库
//这里以我的名字首字母为类域名称
namespace zzj { // 定义一个命名空间zzjtemplate<class T> // 定义一个模板类//构造一个创造节点的模板struct ListNode { // 定义一个模板结构体ListNodeListNode<T>* _next; // 指向下一个节点的指针ListNode<T>* _prev; // 指向上一个节点的指针T _data; // 节点数据//初始化列表ListNode(const T& x = T()) // 构造函数，初始化节点数据:_next(nullptr) // 初始化_next为nullptr, _prev(nullptr) // 初始化_prev为nullptr, _data(x) // 初始化_data为x{}};//可以传类的模板参数template<class T, class Ref, class Ptr> // 定义一个模板类struct ListIterator { // 定义一个模板结构体ListIteratortypedef ListNode<T> Node; // 定义类型别名Nodetypedef ListIterator<T, Ref, Ptr> Self; // 定义类型别名SelfNode* _node; // 节点指针ListIterator(Node* node) // 构造函数:_node(node) // 初始化_node为node{}Ref operator*() { // 重载*运算符return _node->_data; // 返回节点数据}Ptr operator->() { // 重载->运算符return &_node->_data; // 返回节点数据的地址}//前置++Self& operator++() { // 重载前置++运算符_node = _node->_next; // _node指向下一个节点return *this; // 返回当前迭代器}//后置++Self operator++(int) { // 重载后置++运算符Self tmp(*this); // 保存当前迭代器_node = _node->_next; // _node指向下一个节点return tmp; // 返回保存的迭代器}Self& operator--() { // 重载前置--运算符_node = _node->_prev; // _node指向上一个节点return *this; // 返回当前迭代器}Self operator--(int) { // 重载后置--运算符Self tmp(*this); // 保存当前迭代器_node = _node->_prev; // _node指向上一个节点return tmp; // 返回保存的迭代器}bool operator!=(const Self& it) { // 重载!=运算符return _node != it._node; // 判断两个迭代器是否不相等}bool operator==(const Self& it) { // 重载==运算符return _node == it._node; // 判断两个迭代器是否相等}};//template<class T> // 注释掉的代码//struct ListConstIterator { // 注释掉的代码// ... // 注释掉的代码//};template<class T> // 定义一个模板类class list { // 定义一个模板类listtypedef ListNode<T> Node; // 定义类型别名Nodepublic:typedef ListIterator<T, T&, T*> iterator; // 定义类型别名iteratortypedef ListIterator<T, const T&, const T*> const_iterator; // 定义类型别名const_iteratorvoid empty_init() { // 初始化空链表_head = new Node; // 创建一个新节点作为头节点_head->_next = _head; // 头节点的_next指向头节点_head->_prev = _head; // 头节点的_prev指向头节点_size = 0; // 初始化_size为0}list() { // 构造函数empty_init(); // 调用empty_init函数初始化空链表}//lt2(lt1)//需要析构，就需要自己写深拷贝//不需要析构，一半就不需要写深拷贝list(const list<T>& lt) { // 拷贝构造函数empty_init(); // 调用empty_init函数初始化空链表for (auto& e : lt) { // 遍历ltpush_back(e); // 将元素e添加到当前链表的末尾}}void clear() { // 清空链表iterator it = begin(); // 获取链表的开始迭代器while (it != end()) { // 遍历链表it = erase(it); // 删除当前节点，并返回下一个节点的迭代器}}~list() { // 析构函数clear(); // 清空链表delete _head; // 删除头节点_head = nullptr; // 将_head设置为nullptr}void swap(list<T>& lt) { // 交换两个链表std::swap(_head, lt._head); // 交换头节点std::swap(_size, lt._size); // 交换_size}list<T>& operator=(list<T> lt) { // 赋值运算符重载swap(lt); // 交换当前链表和ltreturn *this; // 返回当前链表}void push_back(const T& x) { // 在链表末尾添加元素xinsert(end(), x); // 调用insert函数在链表末尾添加元素x}void push_front(const T& x) { // 在链表头部添加元素xinsert(begin(), x); // 调用insert函数在链表头部添加元素x}void pop_back() { // 删除链表末尾的元素erase(--end()); // 调用erase函数删除链表末尾的元素}void pop_front() { // 删除链表头部的元素erase(begin()); // 调用erase函数删除链表头部的元素}void insert(iterator pos, const T& val) { // 在迭代器pos指向的位置插入元素valNode* cur = pos._node; // 获取pos指向的节点Node* prev = cur->_prev; // 获取cur的前一个节点Node* newnode = new Node(val); // 创建一个新节点，并初始化其数据为valprev->_next = newnode; // 将prev的_next指向新节点newnode->_prev = prev; // 将新节点的_prev指向prevnewnode->_next = cur; // 将新节点的_next指向curcur->_prev = newnode; // 将cur的_prev指向新节点_size++; // _size加1}iterator erase(iterator pos) { // 删除迭代器pos指向的节点Node* cur = pos._node; // 获取pos指向的节点Node* next = cur->_next; // 获取cur的下一个节点Node* prev = cur->_prev; // 获取cur的前一个节点next->_prev = prev; // 将next的_prev指向prevprev->_next = next; // 将prev的_next指向nextdelete(cur); // 删除cur_size--; // _size减1return iterator(next); // 返回下一个节点的迭代器}size_t size() const { // 返回链表的大小return _size; // 返回_size}const_iterator begin() const { // 返回链表的开始迭代器（const版本）return _head->_next; // 返回头节点的_next}const_iterator end() const { // 返回链表的结束迭代器（const版本）return _head; // 返回头节点}iterator begin() { // 返回链表的开始迭代器return iterator(_head->_next); // 返回头节点的_next}iterator end() { // 返回链表的结束迭代器return iterator(_head); // 返回头节点}private:Node* _head; // 头节点指针size_t _size; // 链表大小};void test() { // 测试函数list<int> l1; // 创建一个int类型的listl1.push_back(1); // 在l1末尾添加元素1l1.push_back值得学习的是，模板的参数不止可以传一个，可以传多个然后由编译器生成对应的类。
