🔥个人主页：Quitecoder
🔥专栏：c++笔记仓
朋友们大家好，本篇文章来到list有关部分，这一部分函数与前面的类似，我们简单讲解，重难点在模拟实现时的迭代器有关实现
目录
`1.List介绍``2.接口函数``operations` `3.模拟实现``3.1基本框架``3.2 list的基本函数``3.3迭代器的封装和实现``++等重载函数的实现``与list的关联` `3.4list函数完善``3.5迭代器进一步完善``const迭代器``合并两种迭代器`
1.List介绍
所以list本质就是我们的双向循环链表，我们接下来看它的接口函数
2.接口函数
构造函数
这里的构造函数与vector类似
std::list): std::list<int> myList1; // 创建一个空的整型链表std::list): std::list<int> myList2(5, 10); // 创建一个有5个元素的链表，每个元素都初始化为10std::list): std::vector<int> myVector{1, 2, 3, 4, 5};std::list<int> myList3(myVector.begin(), myVector.end()); // 使用vector的范围来初始化链表std::list 来构造一个新的 std::list, 是副本): std::list<int> myOriginalList{1, 2, 3, 4, 5};std::list<int> myList4(myOriginalList); // 使用另一个list来初始化这个新的list每个构造函数都有它们独特的用途，可以根据具体需要选择合适的构造函数进行对象的创建和初始化。
默认构造函数创建一个没有任何元素的空链表。填充构造函数允许创建一个包含特定数量相同值的元素的链表。范围构造函数可以从任何提供迭代器接口的其他容器复制元素。拷贝构造函数创建了一个当前list的副本。 填充构造函数前面的
explicit关键字表明这个构造函数不能用于隐式转换或复制初始化，它需要直接调用来构造对象。其他构造函数则根据是否带有explicit关键字来决定是否能用于隐式转换或复制初始化
迭代器
迭代器用来遍历链表，下面是迭代器的简单使用
list<int> lt = { 10,20,30,40,50 };list<int>::iterator i1 = lt.begin();while (i1 != lt.end()){cout << *i1 << " ";i1++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;容量操作
元素访问
内容操作
这里大多数函数我们在前面都讲解过，包括头插头删尾插尾删之类的
insert在这里不会出现迭代器失效
迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为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()){l.erase(it);++it;}}erase()函数执行后，it所指向的节点已被删除，因此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);}}l.erase(it++);这一行做了以下几件事情：
it++ 表达式返回 it 的当前值（我们来称它为“旧迭代器”），然后将 it 自增，指向下一个元素（现在 it 指向“新迭代器”）。l.erase(旧迭代器) 调用删除了旧迭代器当前指向的元素，并使这个旧迭代器失效。因为 it 已经自增，它现在指向原来被删除元素的下一个元素，因此循环可以继续。 请注意对于 std::list，这个行为是有效的，因为 erase 不会影响除了被删除元素之外的任何迭代器。但如果是其他类型的容器，如 std::vector 或 std::deque 中使用相同的技巧就可能会出问题，因为这些容器的 erase 操作可能会导致所有指向被删除元素之后元素的迭代器全部失效。因此，应谨慎地使用这种技术，并且要确认你了解容器的迭代器失效规则。
operations
std::list 提供了一些有用的成员函数，允许执行各种操作，如元素的合并、移除、排序和倒序。下面是这些函数的简要说明和使用示例：
std::list<int> list1 = {1, 2, 3};std::list<int> list2 = {4, 5, 6};list1.splice(list1.end(), list2); // 把list2的所有元素移动到list1的末尾std::list<int> myList = {1, 2, 3, 3, 4, 3, 5};myList.remove(3); // 移除所有值为3的元素std::list<int> myList = {1, 2, 3, 4, 5};myList.remove_if([](int n){ return n % 2 == 0; }); // 移除myList中所有偶数元素std::list<int> myList = {1, 1, 2, 2, 2, 3, 4, 4, 5, 5};myList.unique(); // 移除相邻重复的元素，列表变为1, 2, 3, 4, 5std::list<int> list1 = {1, 3, 5};std::list<int> list2 = {2, 4, 6};list1.merge(list2); // 合并两个列表为1, 2, 3, 4, 5, 6std::list<int> myList = {4, 3, 5, 2, 1};myList.sort(); // 排序列表为1, 2, 3, 4, 5std::list<int> myList = {1, 2, 3, 4, 5};myList.reverse(); // 反转后列表为5, 4, 3, 2, 1这些操作与 std::list 的双向链表特性和内部实现密切相关。例如，splice 不产生元素复制，因为链表中的节点可以简单地重新链接。对于排序操作，std::list 提供了特定的成员函数 sort 以优化排序算法，因为链表不支持随机访问，标准的排序算法（如 std::sort）不适用。
3.模拟实现
3.1基本框架
namespace own { template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T&x=T()) :_next(nullptr) , _prev(nullptr) , _data(x) {} }; template<class T> class list { typedef ListNode<T> Node; private: Node* _head; size_t _size; };}这段代码实现了一个简单双向链表的基础结构。让我们分两部分来解释这个代码：
namespace own：命名空间 own 用于封装代码，避免与其他库中的同名类型或函数冲突。在这个命名空间中，定义了模板类 ListNode 和模板类 list。
模板类 ListNode 的定义：
template<class T>struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& x=T()) : _next(nullptr), _prev(nullptr), _data(x) {}};这是一个结构体模板，它定义了双向链表的一个节点。每个 ListNode 包含三个成员：
_next 指向下一个 ListNode 的指针_prev 指向前一个 ListNode 的指针_data 存储节点的数据，其类型为模板参数 T ListNode 还有一个构造函数，它接受一个 const T& 类型的参数，如果构造函数没有提供参数，则会使用 T 类型的默认构造函数来初始化 _data。构造函数还将 _next 和 _prev 初始化为 nullptr，表示链表的下一个和前一个节点分别不存在
模板类 list 的定义：
template<class T>class list { typedef ListNode<T> Node;private: Node* _head; size_t _size;};这个类表示双向链表本身：
类型定义typedef ListNode<T> Node 是为了简化代码，使得在类 list 中可以直接使用 Node 来指代 ListNode<T>。_head 是一个指向链表头部节点的指针。_size 是一个 size_t 类型的值，用来存储链表的长度（即节点个数）。 3.2 list的基本函数
🔥list()
list(){ _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0;}带头双向循环链表，我们初始化时让它的头结点的前一个指针和后一个指针指向自身
🔥尾插push_back()
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; _size++;}
那我们完成了尾插工作，接下来如何实现下面的遍历呢？
void test1(){ list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_front(6); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl;}这部分来到本篇的重点，迭代器的封装和实现
3.3迭代器的封装和实现
我们思考一下，这里原生指针能否代替迭代器？
我这里的指针，只能是Node*，Node*++不会加到下一个节点，这里的++需要我们自己重载实现，解引用也取不到当前节点的位置，这些函数都需要我们自己重载实现，所以，我们需要对迭代器进行封装
template<class T>struct ListIterator{ typedef ListNode<T> Node; Node* _node; ListIterator(Node* node) :_node(node) {}};注意，我们迭代器实在list类域访问的:
list<int>::iterator it = lt.begin();这里我们就需要在list类里面进行嵌套
template<class T>class list {public: // 这是一个嵌套类型的别名定义。 typedef ListIterator<T> iterator; // ...};list<int>::iterator it = lt.begin(); 这一行涉及到了所谓的嵌套类型或者内嵌类型。
在C++中，当一个类型（比如 ListIterator<T>）是在另一个类型的作用域内部定义的（比如 list<T>）时，这个类型被称为嵌套类型。嵌套类型通常用于与外部类型紧密相关联的概念，例如迭代器、节点或其他辅助类。
在 list 类中定义了 iterator 类型作为 ListIterator<T> 类型的别名：
template<class T>class list {public: typedef ListIterator<T> iterator;};这里的 iterator 是 list 类的嵌套类型的别名，所以当我们在类外部引用它时，我们需要使用类的名称（在这个例子中是 list<int>），后跟两个冒号来限定作用域，然后是别名 iterator。因此 list<int>::iterator 指的是 ListIterator<int>，它是链接到特定的 list 实例化类型的迭代器类型
要点是，内嵌类型通常在类定义内部，并且与该类紧密关联。当我们在类外部谈到这些类型时，需要使用类的名称来限定这些类型，就像我们引用
list<int>::iterator一样。这种设计方式提供了良好的封装和组织结构，在集合和容器类（如list）中是一种常见做法
迭代器就是一个节点的指针，我们这个类的成员就是_node（节点指针）
typedef ListNode<T> Node; Node* _node; ListIterator(Node* node) :_node(node) {}这里用一个节点的指针就可以对迭代器进行初始化
++等重载函数的实现
这个封装类的关键就是对这进行重载函数
🔥operator++()与operator- -()
这里++加到下一个节点，改变节点指针：
前置++
typedef ListIterator<T> SelfSelf& 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;}🔥operator*()
这里解引用得到节点的值，需要我们自己手动重载实现：
T& operator*(){ return _node->_data;}这里返回的是引用值，是对原数据可直接修改的
🔥operator!=()
我们在循环中还有判断两个迭代器不相等，本质就是两个节点指针不相等
bool operator!=(const Self& it){ return _node != it._node;}基本完成类的封装后，我们需要把它和list连起来
与list的关联
这里begin和end只能由list提供
template<class T>class list { typedef ListNode<T> Node;public: typedef ListIterator<T> iterator; iterator begin() { return iterator(_head->_next);//匿名对象 } iterator end() { return iterator(_head);//最后一个位置的下一个位置 } '''''''''''''''''''''''''''''''''''' //其他函数 private: Node* _head; size_t _size;};begin返回第一个数据的迭代器，end返回最后一个数据的下一个位置
测试代码：
void test1(){ 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;}
由于我的外部代码使用了iterator别名，这里
typedef ListIterator<T> iterator;必须放在public下
3.4list函数完善
有了迭代器，我们就可以完善其他的list函数
🔥insert()
void insert(iterator pos, const T& val){ Node* cur = pos._node;//拿到这个位置的节点 Node* newnode = new Node(val); Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; _size++;}🔥erase()
iterator erase(iterator pos){ Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; --_size; return iterator(next);}erase删除返回的是下一个位置的迭代器
🔥头尾删插
有了insert和erase，我们这几个函数就可以直接进行复用
void push_front(const T& x){ insert(begin(), x);}void push_back(const T& x){ insert(end(), x);}void pop_back(){ erase(--end());}void pop_front(){ erase(begin());}与size相关函数：
size_t size()const{ return _size;}bool empty(){ return _size == 0;}🔥链表销毁
void clear(){ iterator it = begin(); while (it != end()) { it = erase(it); }}~list(){ clear(); delete _head; _head = nullptr;}3.5迭代器进一步完善
对于下面的这种类
struct A { int _a1; int _a2; A(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} };如果list存的是上面的自定义类型呢？
插入有以下几种方法：
void test_list2(){ list<A> lt; A aa1(1, 1); A aa2 = { 1, 1 }; lt.push_back(aa1); lt.push_back(aa2); lt.push_back(A(2, 2)); lt.push_back({ 3, 3 }); lt.push_back({ 4, 4 }); }上面代码使用不同方式来创建和插入 A 类型的对象到自定义的 list 容器中。下面是每种方式的详细说明以及它们所涉及的概念：
有名对象的直接插入:
A aa1(1, 1);lt.push_back(aa1);这里，首先创建了一个命名对象 aa1，使用了 A 的构造函数 A(int a1, int a2) 并为其提供了两个参数。然后，你将 aa1 作为参数传递给 lt.push_back() 函数。在这种情况下，aa1 是有名对象（也就是说，它有一个名称），并且 push_back 函数接受到的是 aa1 的一个副本
多参数隐式类型转换:
A aa2 = { 1, 1 };lt.push_back(aa2);aa2 通过列表初始化的方式被创建。这里的列表初始化允许直接用花括号 {} 来初始化对象。C++11 引入的列表初始化特性可以用来初始化任何对象，包括具有构造函数的对象。创建了 aa2 有名对象并将其插入到列表中
通过构造函数创建匿名对象并插入:
lt.push_back(A(2, 2));在这里，没有给新创建的 A 对象一个名字，因此它是一个匿名对象（也称作临时对象）。这个匿名的 A 对象是通过调用它的构造函数来直接初始化的，并立即被传递到 push_back 函数中。
通过隐式类型转换创建匿名对象并插入:
lt.push_back({ 3, 3 });与第三种方式类似，创隐式类型转换建了一个匿名的 A 对象，但这次是通过。初始化时没有使用相应类型的构造函数，而是依赖编译器生成的代码来创建一个具有给定初始化列表的对象，并将其传递给 push_back 函数。
在所有这些情况中，实际插入到 list 容器中的都是 A
现在我们来进行遍历：
list<A>::iterator it = lt.begin();while (it != lt.end()){ cout<<*it<<" "; ++it;}
A是自定义类型，不支持留插入，我们解引用得到的_data是A的对象
这里数据是公有的，解引用得到的可以通过.访问符进行访问
cout << (*it)._a1 << ":" << (*it)._a2 << endl;这种访问方式相当于这种形式：
A* ptr = &aa1;(*ptr)._a1;这种指针访问行为十分复杂，我们可以重载一个函数使实现这种访问方式：
ptr->_a1;在迭代器中重载->运算符
T* operator->(){ return &_node->_data;}这里返回的是_data的地址
我们就可以这样访问：
cout << it->_a1 << ":" << it->_a2 << endl;实际上它的访问方式如下：
cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;注意
这里隐藏了一个箭头，一个是重载，一个是原生指针的访问操作
实际上，并不需要在代码中写两次箭头。这是因为在 C++ 中，operator-> 有一个特殊的规则
当重载
operator->，不会直接返回成员的值，而是应该返回一个指针，这个指针指向的对象包含我们想要访问的成员。当使用->运算符时，C++ 会自动和透明地调用重载的operator->并继续 “链式” 访问成员，而不需要程序员显示地添加多余的箭头。
这是如何工作的：
如果有一个用户自定义类型的对象（比如迭代器）it，并且我们调用 it->member，编译器会查找这个类型是否有 operator->如果这个类型有一个 operator-> 的重载，编译器就调用 it.operator->()it.operator->() 应该返回一个指向对象的指针，这个对象有一个我们尝试访问的 member 成员编译器取得这个指针，并继续访问 member 这个流程只需要一个
->即可。编译器在背后处理了所有操作，直到访问到一个实际对象，然后这个对象的成员可以直接通过->运算符访问
因此，我们不需要手动写成 it->->member；只需写 it->member 即可。编译器会自动将其 “转换” 为 it.operator->()->member
在 ListIterator 示例里，it->_a1 意味着：
it.operator->() 拿到 ListNode 中 _data 成员的地址（这是一个 A 类型的对象）。使用返回的指针来访问 A 对象的 _a1 成员。 整个过程对于编程者来说是透明的，不需要编写多个 ->。这种处理方式使得重载 -> 可以更自然地使用，就像处理普通的指针一样。
const迭代器
我们上面写的迭代器对于const对象是无法编译成功的，const不能调用非const成员函数
对于const类迭代器，我们需要在list类里面重新增加重载：
typedef ConstListIterator<T> const_iterator;const_iterator begin() const{ return _head->_next;}const_iterator end() const{ return _head;}使普通版本调用普通版本，const调用const版本
这里的const迭代器不能是下面这种形式，而需单独创建版本：
const iterator end() const{ return _head;}因为const迭代器的本质是迭代器指向的内容不能修改，而不是迭代器本身不能修改
const iterator这样定义是迭代器不能修改，内容还是可以修改的
那我们如何实现const迭代器呢？
方法一：单独实现一个类，修改正常版本的迭代器
template<class T>struct ConstListIterator{ typedef ListNode<T> Node; typedef ConstListIterator<T> Self; Node* _node; ListIterator(Node* node) :_node(node) {} const T* operator->() { return &_node->_data; } 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& it) { return _node != it._node; }};我们目的是不修改指向的值，只需要在这两个函数前面加上const即可：
const T* operator->(){ return &_node->_data;}const T& operator*(){ return _node->_data;}
我们这两个类只有这两个函数不同，那么能不能将他们两个合并呢？
合并两种迭代器
这里仅是两种返回类型不同，这里我们利用模版来对这里内容进行合并
template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){return &_node->_data;}};我们只提取不同的部分，其他部分与原来相同
Ref代表引用，Ptr代表指针
让我们来看一下这个合并后的迭代器的模板参数：
T：列表节点存储的数据类型Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。Ptr：通过迭代器访问数据的指针类型，可以是T*或者const T*。 这样，我们可以创建一个常量迭代器，为Ref和Ptr参数指定常量类型，例如：
ListIterator<T, const T&, const T*> const_iterator;对于非常量迭代器，就简单地传递非常量类型的引用和指针：
ListIterator<T, T&, T*> iterator;在list类中，我们需要相应地声明两种类型的迭代器：
template<class T>class list { // ... 省略其他代码 ...public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; // ... 省略其他代码 ...};list类中的其他成员函数像begin、end需要按照是否接收常量类型来适配这两种迭代器。
