1.list的介绍
list的底层结构是双向带头循环链表，允许随机的插入和删除，但其内存空间不是连续的。随机访问空间能力差，需要从头到尾遍历节点，不像vector一样高效支持
2.list的使用
构造函数
1.默认构造函数：创建一个空链表
加()会被解析为函数声明而不是对象定义，不会调用默认构造。后面加{}同样可以正确初始化
2.填充构造函数
用于创建一个包含多个相同值的链表。
3.范围构造函数
用于从其他容器或范围中复制元素到新链表。
4.拷贝构造函数
用于通过拷贝另一个std::list对象来创建新链表
5.用数组来构造list
本质上也是利用迭代器来范围构造，数组的指针为原生迭代器
容量函数
1.检测list是否为空，是返回true，否则返回false
2.返回list中有效节点的个数,常用于循环，条件判断等
3.用于了解容器的最大容量限制，通常在需要预先分配大量内存或进行容量规划时使用。
元素访问
1.返回容器中第一个元素的引用。container.front()
2.返回容器中最后一个元素的引用。container.back()注意：
1.空容器检查：可通过empty检查，否则造成未定义行为
2.常量容器：需要返回常量引用（const T&）
3.适用容器：适用于大多数标准库容器，包括 std::list、std::vector、std::deque 等
因为是传引用返回，可直接修改返回值
修改操作函数
重点分析：
splice
翻译为链接，拼接，但理解为转移更好，将原容器中节点重新链接到目标容器中，不是复制元素，原容器中这些节点就相当于删除了，所以“转移”理解更贴切。
1.整个链表转移：
将整个列表x的内容移动到*this列表中，插入到position迭代器所指的位置之前。操作后，x将变为空列表。
2.单个元素转移：
将列表x中的单个元素i移动到*this列表中，插入到position迭代器所指的位置之前。操作后，i在x中将不再有效。
3.元素范围转移：
将列表x中从first到last（不包括last）的元素范围移动到*this列表中，插入到position迭代器所指的位置之前。操作后，first到last范围内的元素在x中将不再存在。
sort
list底层用的归并算法，vector底层用的快排适合sort算法。
原因：链表不支持随机访问，因此像快速排序这样依赖随机访问的算法效率较低。而合并排序在链表上的性能更优，因为它主要依赖顺序访问和合并操作。
性能测试：
void test_op()
{
srand(time(0));
const int N = 100000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt2.push_back(e);
lt1.push_back(e);
}
// 拷贝到vector排序，排完以后再拷贝回来
int begin1 = clock();
// 先拷贝到vector
for (auto e : lt1)
{
v.push_back(e);
}
// 排序
sort(v.begin(), v.end());
// 拷贝回去
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
步骤：
1.随机数生成和数据准备：
srand(time(0))：用当前时间初始化随机数生成器，定义一个常量N，表示要生成的随机数数量
vector v：创建一个vector，用于存储从list中拷贝出来的元素
v.reserve(N)：预先为vector分配足够的内存，避免在后续插入元素时频繁重新分配内存。
list lt1, lt2：创建两个list，lt1和lt2，用于存储相同的随机数序列。
2. 使用vector辅助排序list
begin1 = clock()：记录开始时间。
拷贝list到vector：将lt1中的所有元素拷贝到vector中。
排序vector：使用std::sort对vector进行快速排序。
拷贝排序结果回list：将排序后的vector中的元素拷贝回lt1。
end1 = clock()：记录结束时间。
3. 直接使用list的sort方法
begin2 = clock()：记录开始时间。
lt2.sort()：直接对lt2进行排序。
end2 = clock()：记录结束时间。
可以从结果看出，随着数据量的增大二者效率差别更大，但如果数据量较小的时候用起来差别不大，并且在容器中设计了这样一个函数，在特定情境使用起来也非常方便；如果数据量大的情况下根据需求选择合适的容器比如vector支持随机访问，底层快排实现，比list更好，就不用一定要使用list。
unique
1.无参数版本：
移除链表中所有连续重复的元素，只保留每个连续重复组的第一个元素。只有当一个元素与其前一个元素相等时才会被移除。因此，该函数特别适用于已排序的链表。
2.带参数版本：
使用自定义的二元谓词来确定元素是否应该被移除。
对于所有元素对（从第二个元素开始），如果二元谓词返回true，则移除该元素。
remove
移除特定值的元素：std::list::remove会从链表中移除所有等于val的元素。
调用析构函数：被移除的元素的析构函数会被调用。
减少容器大小：容器的大小（size）会减少被移除的元素的数.
与list::erase的区别：
list::erase通过迭代器指定位置来删除元素。
list::remove通过元素的值来删除元素。
迭代器失效
迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
解决办法：
只需要接收erase的返回值就好了，返回值为被删除节点的下一个位置。
3.list的模拟实现
结点定义为公有的，操作方便，成员函数中触碰不到结点，即使定义为公有，别人也不知道具体细节。用struct定义，跟库中保持一致，但此库非C语言中的库，而是类，默认公有。
封装节点
定义了一个类模板list_node,是一个双向链表节点的结构体，每个节点包含前指针和后指针以及存储值，用它进行传参和访问的时候更高效，包含多种数据信息。
迭代器类模板
//更加通用灵活的类模板迭代器
//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->_val;
}
//返回当前节点值指针
ptr operator->()
{
return &_node->_val;
}
//前置++
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& it)const
{
return _node != it._node;
}
//比较两个迭代器是否相等
bool operator==(const self& it)const
{
return _node == it._node;
}
};
这是一个更通用灵活的模板类，用于实现双向链表的迭代器。
为什么这样设计？
因为list不是一段连续的空间，原生的指针不能完成++或者解引用操作，而C++中对于内置类型无法完成的行为，可以用自定义类型去重载运算符来改变其行为，从而满足自身需求
功能解析：
1.模板参数
T：链表节点中存储的值的类型。
ref：解引用操作符返回的引用类型（例如 T& 或 const T&）。
ptr：箭头操作符返回的指针类型（例如 T* 或 const T*）
2.成员变量
_node：指向当前节点的指针。
3.构造函数
接受一个 Node* 类型的参数，初始化 _node
4.操作符重载：
注意：前置++和后置++重载都需要先拷贝构造一个临时对象，来保存节点当前状态用于返回，再进行操作，返回值不能传引用，因为临时变量具有常性，会造成权限放大的问题。
关于->操作符：
箭头操作符（->）在C++中用于访问指针指向的对象的成员。在迭代器的上下文中，箭头操作符通常被重载，以便能够方便地访问迭代器所指向的节点的值。
ptr 是模板参数，表示返回的指针类型（例如 T* 或 const T*）。
_node 是指向当前节点的指针。
_node->_val 是当前节点中存储的值。
返回 _node->_val 的地址，这样可以通过箭头操作符访问值的成员。
编译器会自动处理箭头操作符的链式调用，使得代码更加可读。
迭代器的职责
没有自定义实现调用默认生成的拷贝构造函数，发生浅拷贝，这是我们期望的，返回值也指向该结点
为什么没崩溃？因为没有自定义实现析构函数
为什么不析构？因为迭代器作用只是去访问结点而不是去管理，不需要自定义析构函数来释放节点的内存。当迭代器对象被销毁时，只是销毁指针本身，而不会影响节点的内存。容器类（如 list）负责管理节点的内存，包括分配和释放。
通过封装可以使stl中各容器的迭代器的使用方法都类似，而底层却千差万别，这就是魅力所在，对于内置类型指针是否需要深拷贝取决于实际需求，由自己控制
辨析
const迭代器设计思想
我们期望迭代器本身是能被修改的，进行重载之后的解引用，访问，自增和自减的操作。期望迭代器指向的内容不被修改。
按照之前的经验以及实现过的vector，会习惯于在类名前加一个const来修饰，但vector内存连续布局，原生指针就能很好满足迭代器需求，可以这么写；但list内存非连续，需要自定义迭代器来重载一些操作。typedef const __list_iterator<> const_iterator;
这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改这样设计是迭代器本身不能修改
typedef __list_const_iterator<> const_iterator;
这么设计在简单场景下有效，复杂场景下存在局限性，
1.无法处理 const 元素：
如果容器中的元素本身是 const 类型，_list_const_iterator<> 无法正确处理，因为它假设元素是可以修改的。
2.无法保证真正的不可修改性：
如果容器中的元素是复杂对象（例如包含指针或引用的类），_list_const_iterator<> 无法确保这些对象的内部状态不被修改。
所以需要使用上述模板类来解决
双向链表类模板list
迭代器定义
用一个模板类来定义节点，内部封装了实现细节。iterator：普通迭代器，用于读写操作。const_iterator：常量迭代器，用于只读操作。多个模板参数满足不同情况下的参数需求
构造函数
_size初始化为 0，表示链表为空。
拷贝构造
创建一个新的哨兵节点。深拷贝源链表的每个元素。
赋值运算符重载
参数 it 是一个 list<> 类型的对象，调用拷贝构造函数生成一个临时拷贝。
交换资源：通过 swap 函数交换当前对象和临时拷贝的资源。可以看作是深拷贝
返回引用：返回当前对象的引用，以便支持链式赋值。
插入和删除操作
//pos位置之前插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
//改变链接
cur->_prev = newnode;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
next->_prev = prev;
prev->_next = next;
delete cur;
_size--;
return next;
}
注意提前保存节点，这样不用担心链接顺序。插入函数中pos是一个模板类对象，创建指针cur来保存该对象中封装的节点，再通过箭头操作符来访问其中成员变量。
push和pop操作
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;
//复用insert函数
//insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
学会复用插入和删除操作
迭代器范围
iterator begin()
{
//return iterator(_head->next);
//可直接返回的原因是单参数构造函数支持隐式类型转换
return _head->_next;
}
iterator end()
{
//end指向尾结点下一个位置，即哨兵位头结点
//return iterator(_head);
return _head;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}
清空和析构
clear：删除链表中的所有元素。
析构函数：调用 clear 并释放哨兵节点
完整代码
#pragma once
#include<iostream>
#include<assert.h>
namespace ee
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_next(nullptr)
, _prev(nullptr)
, _val(val)
{}
};
//template<class T>
//struct _list_iterator
//{
// typedef list_node<T> Node;
// Node* _node;
// //构造函数
// _list_iterator(Node* node)
// :_node(node)
// {}
// T& operator*()
// {
// return _node->_val;
// }
// //前置++
// _list_iterator<T>& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// //后置++
// _list_iterator<T>& operator++(int)
// {
// _list_iterator<T> tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// bool operator!=(const _list_iterator<T>& it)
// {
// return _node != it._node;
// }
// bool operator==(const _list_iterator<T>& it)
// {
// return _node == it._node;
// }
//};
//更加通用灵活的模板类迭代器
//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->_val;
}
//返回当前节点值指针
ptr operator->()
{
return &_node->_val;
}
//前置++
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& it)const
{
return _node != it._node;
}
//比较两个迭代器是否相等
bool operator==(const self& it)const
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
//return iterator(_head->next);
//可直接返回的原因是单参数构造函数支持隐式类型转换
return _head->_next;
}
iterator end()
{
//end指向尾结点下一个位置，即哨兵位头结点
//return iterator(_head);
return _head;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}
//构造函数
list()
{
_head = new Node;
//将前后指针链接自己，可明确初始状态
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
//拷贝构造
list(const list<T>& lt)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
//深拷贝
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值运算符重载
list<T>& operator=(list<T> it)//传参过程调用拷贝构造
{
swap(it);
return *this;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
~list()
{
clear();
delete[] _head;
_head = nullptr;
}
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;
//复用insert函数
//insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
//pos位置之前插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
//改变链接
cur->_prev = newnode;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
next->_prev = prev;
prev->_next = next;
delete cur;
_size--;
return next;
}
size_t size()
{
return _size;
}
private:
Node* _head;//哨兵位节点
size_t _size;
};
}