一，list的介绍
1，list初步
（1）list是 C++ 标准模板库 (STL) 中的一个双向链表容器。它允许在常数时间内进行任意位置的插入和删除操作，但不支持随机访问。
（2）list容器的底层数据结构为带头双向循环链表，list的元素可以存储在非相邻的内存中，所以list在插入和删除元素中有着独特的优势，其时间复杂度仅为常数。
注意：list还需要额外的存储空间来存储前一个元素和后一个元素
头文件：
#include<list>2，list的特点
优点：（1）list在插入和删除操作过程中不会使得迭代器失效，仍旧可以对迭代器遍历和操作。
（2）list可以动态的存储数据，可以有效地处理大量数据并且不会浪费过多的空间
补充：list和数据结构中的快速排序算法的平均时间复杂度是一样的，都是，但是快速排序的最坏情况的时间复杂度为
，比list要快。
缺点：（1）list在访问元素的时候需要从头遍历链表，时间复杂度为O（n），因此在随机访问元素时效率低下
（2）内存占用相比其他容器更大，list需要额外的指针维护链表
（3）list不支持指针算术运算，无法像指针那样给进行加减操作
3，list的底层
我们想要观察list的源代码，可以通过everything这个小软件打开
通过将这个文件拖拽到VS上就可以观察到list头文件的源代码
通过观察list头文件中的一些函数，我们可以发现list的底层，这里拿clear举例
我们通过这种方法，可以发现list的底层是一个带头双向循环链表
使用结点指针达不到迭代器的功能：当一个it是指向结点的指针的时候，对it解引用得到的是这个结点而不是值，同时it++也不可以保证到下一个位置，因为下一个位置我们无法确定其地址与本结点的大小
解决方案：用一个类型对结点指针进行封装，再对结点指针和++两个操作进行重载
insert的源代码
创建一个tmp新的结点，tmp结点中next指针指向pos结点，tmp结点中的pre指针指向pos结点中的pre指针（即前一个结点），同时将pos前一个结点的next指针指向tmp，pos处结点的pre指针指向tmp，完成插入一个新的元素。
这与链表中插入思想是一样的
补充：在链表底层中_prev和_next被定义为void*类型的，所以取节点指针时要先强转一下，所以才会出现（link_type(.....）这种情况。
4，迭代器分类
迭代器分类依据之一是其移动方式，与容器的底层结构有关。
迭代器正常下有五种：输入迭代器，输出迭代器，前向迭代器，双向迭代器，随机访问迭代器
这里我们有另一种迭代器分类方式：单向，双向和随机
单向迭代器（Forward Iterator）：仅仅支持++操作，不支持--和随机访问，同时单向迭代器是可读可写的（常量是只读）
双向迭代器（Bidirectional Iterator）：支持++和--操作，但是不支持随机访问，同时双向迭代器是可读可写的（常量是只读）
随机访问迭代器（Random Access Iterator）：支持+，-，+=，-=等算术运算，支持下标访问和双向迭代器的所有功能，同时还支持距离运算和比较运算
一些STL库的迭代器类型：
那么我们怎样知道这些容器的迭代器类型的呢？
string
list
vector
我们可以发现算法的迭代器参数类型，暗示了要求的迭代器类型。
二，list的定义
我们可以发现list的定义要求：
template <class T, class Allocator = allocator<T>>T是指存储的元素类型，如int,char，结构体或者STL容器等
allocator是内存分配器
代码例子：
list<int>lt;我们再通过调试观察其结构：
三，list容器的接口
1，list的构造
在标准库中定义图
（1）构造一个类型的空容器
list<int> lt; //构造int类型的空容器（2）构造一个含有n个val值的一个类型容器
list<int>lt(7,7)//构造含有7个元素为7的int类型容器（3）拷贝构造某类型容器
list<int>lt(lt1);//拷贝构造int类型的lt1容器(4)迭代器拷贝构造某一段数据
string v("Manchester United");
list<char> lt(v.begin(),v.end()); //构造string对象某段迭代器区间的内容(5)构造数组某段区间内容
int arr[] = { 1, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(arr[1]);
list<int> lt5(arr, arr + sz); //构造数组某一段数据(6)使用花括号构造内容
list<int> lt{ 1,2,3,4,5 }; // 直接使用括号进行构造在C++11中引入使用
2，list遍历
（1）迭代器
除此以外还有cbegin，drend等等，这些在vector中我们已经做过接触，这里就不再细述了
正向迭代器
反向迭代器
我们可以借用rbegin和rend来实现
（2）for循环
迭代器是一定支持范围for操作的
3，list的容量操作
（1）我们可以发现list容器中没有capacity()操作和reserve()操作，这是因为链表不需要提前分配内存
（2）list容量操作中resize时间复杂度为O(n)，其余操作时间复杂度为O(1)
size
empty
resize
resize 有两种重载方式
代码展示：
clear
4，list的成员接口
这些操作大家可以自己课下一一尝试，这里就不给大家挨个展示了，只展示重点接口
insert
我们可以发现这里insert的接口很多，这里只介绍三种经典的接口即第一个，第二个和第四个
（1）在指定位置插入单个元素
iterator insert(const_iterator pos, const T& value);代码展示：
（2）在指定位置插入多个相同元素
iterator insert(const_iterator pos, size_type count, const T& value);代码展示：
（3）在指定位置插入另一个容器的元素范围
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);代码展示：
erase
我们可以看到erase有两种接口
（1） 删除单个元素（通过迭代器）
iterator erase(const_iterator pos);代码展示：
（2）删除元素范围（通过迭代器范围）
iterator erase(const_iterator first, const_iterator last);代码展示：
注意：类似于begin和end这类区间都是左闭右开的
5，list容器的特殊操作
splice
（1）移动单个元素
void splice(const_iterator pos, list& other, const_iterator it);代码展示：
（2）移动元素范围
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);代码展示：
（3）移动整个链表
void splice(const_iterator pos, list& other);代码展示：
remove
（1）删除所有等于指定值的元素
void remove(const T& value);代码展示：
remove_if
（1）删除满足条件的元素
template <class Predicate>
void remove_if(Predicate pred);代码展示：
unique
（1）删除连续重复元素
void unique();代码展示：
（2）自定义去重规则
template <class BinaryPredicate>
void unique(BinaryPredicate pred);代码展示：
merge
（1）默认升序合并
void merge(list& other);代码示例：
（2）自定义排序规则合并
template <class Compare>
void merge(list& other, Compare comp);代码示例：
sort
（1）默认升序排序
void sort();代码展示：
（2）自定义排序规则
template <class Compare>
void sort(Compare comp);代码展示：
reverse
（1）反转链表元素顺序
void reverse();代码展示：
四，list的模拟实现
带头双向循环链表结点
一般定义一个类都用class，但是当我们不用访问限定符进行限制成员的时候，用struct
那么为什么？
因为在链表中我们在模拟实现中其实用到的不是结点的指针，而是通过一个迭代器访问这个链表的。
之所以不用指针，是因为不同平台对list中的链表规定不同
template<class T>
struct list_node
{
list_node* _prev;
list_node* _next;
T _data;
};链表的初始化
class list
{
typedef list_node<T> node;//将结点私有化，外界访问结点的时候只能通过上面的list_node访问
public:
list()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;//哨兵位头结点
};构造函数
list_node(const T& x=T())//要注意哨兵位初始化时的值的类型是不确定的，所以这里可以写成匿名对象或者全缺省
: _next(nullptr)
, _prev(nullptr)
, _data(x)
{ }链表迭代器模板类型框架
通过迭代器结构体模拟目标指针行为，从而遍历链表，再定义类型别名方便后续使用，随后node*_node来保存当前指向的链表节点的指针
template<class T>
struct list_iterator
{
typedef list_node<T>node;
node* _node;
};链表迭代器
template<class T> //模板声明，支持任意数据类型
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++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//重载前置++操作符
self& operator--()
{
_node = _node->_prev;
return *this;
}
//重载后置++操作符
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
//重载不等比较操作符
bool operator != (const self & s) const
{
return _node != s.node;
}
//重载相等运算符
bool operator==(const self& s) const
{
return _node == s._node;
}
};typedef list_iterator<T>iterator;//将底层迭代器起别名，这说明上层的迭代器相似，但其实底层迭代器实现方式是不同的
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}测试用例：
list<int>::iterator it = lt.begin(); //获取指向链表首元素的迭代器
while (it != lt.end()) { //循环直到链表末尾
*it += 10; //修改当前元素值
cout << *it << " "; //输出当前元素
++it; //移动到下一个元素
}图解：
这里的拷贝就是浅拷贝，不需要写析构函数了：
（1）链表迭代器本质就是对原生指针_node的封装，不能影响链表本身结点生命周期
（2）链表节点的创建和销毁由链表容器管理，如果迭代器释放会出现释放两次的情况，影响链表本身内存
push-back实现
思路：
找到尾结点，新增一个尾结点，将newnode的prev指向tail，next指向_head，同时tail的_next指向newnode,_head的prev指向newnode
这个方法优势是可以不必区分链表空或者非空
当链表为空的时候
按上述思路仍可以进行
代码展示：
提示：这串代码是不完整的，库函数，类的定义等等作者都忽略了，大家自己补充或者看后文的完整版代码即可。
void push_back(const T& x)
{
node* tail = _head->_prev;
node* newnode = new node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->next = _head;
_head->_prev = newnode;
}测试用例
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);insert实现
void insert(iterator pos, const T& x) {
node* cur = pos._node; //获取当前位置对应的节点指针
node* prev = cur->_prev; //找到前驱节点
node* newnode = new node(x); //创建新节点（假设node构造函数接受T值）
// 调整指针关系：
prev->_next = newnode; //前驱节点的next指向新节点
newnode->_prev = prev; //新节点的prev指向前驱
newnode->_next = cur; //新节点的next指向原节点
cur->_prev = newnode; //原节点的prev指向新节点
}insert不需要检查迭代器，因为所有结点都可以插入
借用insert实现头插，尾插等
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}erase实现
void erase(iterator pos) {
assert(pos != end()); //确保不删除尾哨兵节点
node* cur = pos._node; //获取要删除的节点
node* prev = cur->_prev; //前驱节点
node* next = cur->_next; //后继节点
// 调整指针：
prev->_next = next; //前驱节点直接指向后继
next->_prev = prev; //后继节点直接指向前驱
delete cur; //释放目标节点内存
}借用erase实现头删和尾删
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}上述的测试用例大家自己写自己测试即可。
那么list的插入和删除是否有迭代器失效的情况呢？
list的insert不存在迭代器失效，但是list的erase存在迭代器失效的问题。
因为insert只是进行链表的插入操作，修改局部结点的指针不会使得内存重新分配，因而不存在迭代器失效的问题。
erase会使被删除元素的迭代器失效，因为erase操作会删除结点，使得其前后结点的next和prev指针变成野指针，但是其仅仅影响被删除元素结点，不影响其他结点的地址和其他迭代器。
析构函数
~list()
{
clear();
delete _head;//哨兵位头结点也要释放掉
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())//哨兵位的头结点不清除
{
it = erase(it);
}
}size
size_t size()
{
return _size;
}这里要补充一个私有成员变量size，来完成size函数
同时要在insert和erase中对size进行更改
深拷贝构造函数
初始化链表
void empty_init() {
_head = new Node; //创建头哨兵节点（不存储有效数据）
_head->_next = _head; //next指向自己
_head->_prev = _head; //prev指向自己
_size = 0; //大小置零
}拷贝构造函数
// lt2(lt1)
//list(const list<T>& lt) 这里const对象要用const对象的迭代器
list(list<T>& lt)
{
empty_init(); //初始化空链表
for (auto& e : lt) { //遍历源链表
push_back(e); //逐个元素尾插
}
}
初始化列表构造链表
list(initializer_list<T> il) //初始化列表参数
{
empty_init(); //初始化空链表结构
for (auto& e : il) //遍历初始化列表
{
push_back(e); //将每个元素添加到链表尾部
}
}swap
void swap(list<T>& lt) {
std::swap(_head, lt._head); // 交换头指针
std::swap(_size, lt._size); // 交换元素计数
}交换的是当前链表*this和目标链表lt
拷贝赋值
list<T>& operator=(list<T> lt) //参数为值传递（会调用拷贝构造）
{
swap(lt); //交换当前对象与副本的内容
return *this; //返回当前对象的引用
}参数创建时会隐式调用拷贝构造函数创建lt
const对象
注意const迭代器不要在最前面加上const，这样修饰的是整个迭代器，但是我们要求的是const迭代器不是本身不能被修改，而是指向的内容不能被修改
所以我们要对operator*进行操作，使得其解引用不能被修改就可以达到目的
typedef list_const_iterator<T> const_iterator;同样在struct中也要随之改变
template<class T>
struct list_const_iterator
{
typedef list_node<T> node;
typedef list_const_iterator<T> self;
node* _node;
list_const_iterator(node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& s) const
{
return _node != s._node;
}
bool operator==(const self& s) const
{
return _node == s._node;
}
};但是我们发现两个类是有点冗余的，而且我们发现这个类只有个别的类型不同，所以我们可以考虑复用，借用Ref模板参数完成这项工作
同时，我们也有疑惑，就是箭头操作怎么重载？这里可以再添加一个模板参数，来接收和生成
// typedef list_iterator<T, T&, T*> iterator;
// typedef list_iterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T, Ref, Ptr> Self;
node* _node;
list_iterator(node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const self& s) const
{
return _node == s._node;
}
};通过复用我们就完成了一个通用的双向链表迭代器模板，实现了普通迭代器和常量迭代器的统一处理。
五，list失效问题
迭代器失效即迭代器所指向的节点的无 效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入 时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭 代器，其他迭代器不会受到影响。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}六，list的反向迭代器
反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++， 因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对 正向迭代器的接口进行包装即可。
template<class Iterator>
class ReverseListIterator
{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
// 构造
ReverseListIterator(Iterator it): _it(it){}
// 具有指针类似行为
Ref operator*(){
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->(){ return &(operator*());}
// 迭代器支持移动
Self& operator++(){
--_it;
return *this;
}
Self operator++(int){
Self temp(*this);
--_it;
return temp;
}
Self& operator--(){
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};七，list和vector的比较
