详解list容器

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();// 先拷贝到vectorfor (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;};}