文章目录

一：list介绍以及使用1.list介绍2.基本用法①list构造方式②list迭代器的使用③容量④元素访问⑤插入和删除⑥其他操作image.png

3.list与vector对比

二：list模拟实现1.基本框架2.节点结构体模板3.__list_iterator 结构体模板①模板参数说明②构造函数③迭代器类：拷贝构造、赋值操作、析构函数的说明④++运算符和--运算符⑤==和!=⑥*运算符⑦->运算符

4.list结构体模板①默认成员函数为什么不能传引用？

②迭代器③增删查改④其他操作

5.完整代码展示以及详细注释

一：list介绍以及使用

1.list介绍

文档在这里→官方文档←

list是可以在常数范围内（ 时间复杂度为O(1) ）在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代(双向迭代器)。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

2.基本用法

①list构造方式

<code> list<int> l1; // 构造空的l1

list<int> l2(4, 100); // l2中放4个值为100的元素

list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3

list<int> l4(l3); // 用l3拷贝构造l4

// 以数组为迭代器区间构造l5

int array[] = { 16,2,77,29 };

list<int> l5(array, array + sizeof(array) / sizeof(int));

// 列表格式初始化C++11

list<int> l6{ 1,2,3,4,5 };

②list迭代器的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

【注意】

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

<code>int main() {

// 创建一个整数列表，并初始化列表

list<int> mylist = { 1, 2, 3, 4, 5};

// 使用 begin() 和 end() 迭代器遍历列表

cout << "使用 begin() 和 end():" << endl;

for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it) {

cout << *it << " "; // 输出当前迭代器指向的元素

}

cout << endl;

// 使用 rbegin() 和 rend() 迭代器反向遍历列表

cout << "使用 rbegin() 和 rend():" << endl;

for (list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit) {

cout << *rit << " "; // 输出当前反向迭代器指向的元素

}

cout << endl;

return 0;

}

③容量

<code>list<int> v1;

if (v1.empty())

{

cout << "空";

}

cout << endl;

list<int> v2{ 1,2,3,4 };

cout << v2.size();

④元素访问

<code>

int main() {

// 创建一个整数列表，并初始化列表

list<int> mylist = { 10, 20, 30, 40, 50};

// 使用 front() 返回列表的第一个节点中值的引用

cout << "列表的第一个元素: " << mylist.front() << endl;

// 使用 back() 返回列表的最后一个节点中值的引用

cout << "列表的最后一个元素: " << mylist.back() << endl;

// 修改第一个和最后一个元素的值

mylist.front() = 100;

mylist.back() = 500;

// 输出修改后的列表

cout << "修改后的列表: ";

for (const auto& value : mylist) {

cout << value << " ";

}

cout << endl;

return 0;

}

⑤插入和删除

push_back/pop_back/push_front/pop_front

<code>void PrintList(const list<int>& l)

{

// 注意这里调用的是list的 begin() const，返回list的const_iterator对象

for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)

{

cout << *it << " ";

// *it = 10; 编译不通过

}

cout << endl;

}

// push_back/pop_back/push_front/pop_front

void TestList3()

{

int array[] = { 1, 2, 3 };

list<int> L(array, array + sizeof(array) / sizeof(array[0]));

// 在list的尾部插入4，头部插入0

L.push_back(4);

L.push_front(0);

PrintList(L);

// 删除list尾部节点和头部节点

L.pop_back();

L.pop_front();

PrintList(L);

}

insert/erase

<code>void TestList4()

{

int array1[] = { 1, 2, 3 };

list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

// 获取链表中第二个节点

auto pos = ++L.begin();

cout << *pos << endl;

// 在pos前插入值为4的元素

L.insert(pos, 4);

PrintList(L);

// 在pos前插入5个值为5的元素

L.insert(pos, 5, 5);

PrintList(L);

// 在pos前插入[v.begin(), v.end)区间中的元素

vector<int> v{ 7, 8, 9 };

L.insert(pos, v.begin(), v.end());

PrintList(L);

// 删除pos位置上的元素

L.erase(pos);

PrintList(L);

// 删除list中[begin, end)区间中的元素，即删除list中的所有元素

L.erase(L.begin(), L.end());

PrintList(L);

}

⑥其他操作

resize/swap/clear

<code>#include <iostream>

#include <list>

using namespace std;

int main() {

// 创建一个包含初始值的列表

list<int> mylist = { 10, 20, 30, 40, 50};

cout << "初始列表: ";

for (const auto& value : mylist) {

cout << value << " ";

}

cout << endl;

// 使用 resize 改变列表的大小

mylist.resize(3); // 将列表缩小到3个元素

cout << "使用 resize 缩小列表后: ";

for (const auto& value : mylist) {

cout << value << " ";

}

cout << endl;

mylist.resize(5, 100); // 将列表扩展到5个元素，新元素的值为100

cout << "使用 resize 扩展列表后: ";

for (const auto& value : mylist) {

cout << value << " ";

}

cout << endl;

// 创建另一个列表并交换内容

list<int> otherlist = { 1, 2, 3};

cout << "另一个列表: ";

for (const auto& value : otherlist) {

cout << value << " ";

}

cout << endl;

mylist.swap(otherlist); // 交换两个列表的内容

cout << "使用 swap 交换后，mylist: ";

for (const auto& value : mylist) {

cout << value << " ";

}

cout << endl;

cout << "使用 swap 交换后，otherlist: ";

for (const auto& value : otherlist) {

cout << value << " ";

}

cout << endl;

// 使用 clear 清空列表

mylist.clear();

cout << "使用 clear 清空列表后，mylist 为空，大小为: " << mylist.size() << endl;

return 0;

}

3.list与vector对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空<间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
场景使用	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

二：list模拟实现

1.基本框架

list模拟实现的代码由三部分组成，内容较多，为了便于理解这里先提前介绍大致框架，后面再对每一部分详细讲解。

分为以下几大部分：

节点结构体模板__list_iterator 结构体模板list结构体模板（由一个个节点组成）测试函数

1.首先，我们定义了一个节点结构体模板 ListNode，它包含：

ListNode* 类型的 _next 和 _prev 指针，分别指向前后节点。T 类型的 _data，存放节点的数据。ListNode 的构造函数初始化这些成员。

2.然后，我们定义了一个模板结构体 __list_iterator，用于实现链表的迭代器。这个迭代器包含：

一个指向当前节点的指针 _node。构造函数、前置和后置 ++、-- 运算符重载、解引用运算符、相等和不相等比较运算符等操作。

为了简化代码，__list_iterator 使用了两个 typedef：

将 ListNode 重命名为 Node。将 __list_iterator<T, Ref, Ptr> 重命名为 self。

3.接下来，我们实现了 list 结构体模板。

它包含一个带哨兵位的头结点 _head，类型为 Node* 。通过这个头结点以及迭代器指向的各个节点，形成一个带头的双向循环链表。在 list 中，我们将 __list_iterator<T, T&, T*> 重命名为 iterator，将 __list_iterator<T, const T&, const T*> 重命名为 const_iterator，一种是普通迭代器，一种是常量迭代器，以便用户更方便地使用迭代器。

通过这些定义，我们实现了一个功能完整的双向循环链表，并且提供了迭代器接口，使得用户可以方便地遍历和操作链表中的元素。

这个结构通过 ListNode 实现了双向节点连接，通过 __list_iterator 实现了链表的遍历和操作接口，并通过 list 结构体模板实现了整体的双向循环链表功能。测试函数用于验证各部分的功能和接口是否正常运行。

---

节点类

<code>template<class T>//每个模板类或模板函数的定义都需要用 template<class T> 来声明。这样做的原因是为了告诉编译器这个类或函数是一个模板，且它是依赖于一个类型参数 T

struct ListNode

{

//成员函数

ListNode(const T& val = T()); //构造函数

ListNode<T>* _next;/// 指向下一个节点的指针

ListNode<T>* _prev;// 指向上一个节点的指针

T _data; // 节点存储的数据

};

迭代器类

template<class T, class Ref, class Ptr>

struct __list_iterator

{

typedef ListNode<T> Node;// 定义节点类型的别名

typedef __list_iterator<T, Ref, Ptr> self; // 定义迭代器类型的别名

//__list_iterator 被定义为一个模板结构体，并且引入了三个模板参数：T, Ref, 和 Ptr。

//通过不同的类型实例化 Ref 和 Ptr，我们可以区分出普通迭代器和常量迭代器。

//构造函数，接受一个节点指针

__list_iterator(Node* x);

// 前置++运算符重载，使迭代器指向下一个节点。

//++it

self& operator++();

//it++

self operator++(int);

self& operator--();

self operator--(int);

Ref operator*();

Ptr operator->();

bool operator!=(const self& s);

bool operator ==(const self& s);

Node* _node;// 指向链表节点的指针

};

list类

template<class T>

class list

{

public:

typedef ListNode<T> ListNode;

typedef _list_iterator<T, T&, T*> iterator;

typedef _list_iterator<T, const T&, const T*> const_iterator;

//默认成员函数

//构造

list();

list(size_t n, const T& val = T());

list(int n, const T& val = T());

template<class InputIterator>//取名为InputIterator说明可以用任意类型的迭代器构造

list(InputIterator first, InputIterator last);

//拷贝构造

list(const list<T>& lt);

//赋值运算符重载

list<T>& operator=(const list<T>& lt);

//析构

~list();

//迭代器相关函数

//正向迭代器

iterator begin();

iterator end();

const_iterator begin() const;

const_iterator end() const;

//访问容器相关函数

T& front();

T& back();

const T& front() const;

const T& back() const;

//插入、删除函数

iterator insert(iterator pos, const T& x);

iterator erase(iterator pos);

void push_back(const T& x);

void pop_back();

void push_front(const T& x);

void pop_front();

//其他函数

size_t size() const;

void resize(size_t n, const T& val = T());

void clear();

bool empty() const;

void swap(list<T>& lt);

private:

ListNode* _head; //指向链表头结点的指针

};

2.节点结构体模板

实现一个list实际上是实现一个带头双向循环链表。首先，需要定义一个结点类，每个结点应存储以下信息：数据、前驱指针和后继指针。

对于结点类的成员函数，只需实现一个构造函数即可，因为结点类的唯一职责是根据数据构造结点。结点的释放操作由list类的析构函数统一管理，不需要在结点类中单独实现。

原因如下：

结点类的析构函数

结点类不需要单独的析构函数，因为：

自动内存管理：C++的内存管理机制会自动调用析构函数来释放对象的内存。在结点类中，通常不涉及动态内存分配（如使用new创建成员），因此不需要特别的内存释放操作。链表类负责内存管理：链表类（如list）会在其析构函数中遍历所有结点并删除它们，确保所有结点的内存被正确释放。

结点的创建和销毁

在链表的操作中，结点的创建和销毁是由链表类控制的：

创建结点：在需要添加新结点时，链表类会使用结点类的构造函数创建新结点。销毁结点：在链表类的析构函数或其他删除操作中，会遍历所有结点并删除它们，从而调用每个结点的析构函数。

template<class T>

//每个模板类或模板函数的定义都需要用 template<class T> 来声明。

//这样做的原因是为了告诉编译器这个类或函数是一个模板，且它是依赖于一个类型参数 T

struct ListNode

{

//成员函数

ListNode(const T& val = T()) //构造函数

{

:_val(val)

,_prev(nullptr)

,_next(nullptr)

}

//使用默认参数 T() 初始化 _data，并将 _next 和 _prev 初始化为 nullptr

ListNode<T>* _next;/// 指向下一个节点的指针

ListNode<T>* _prev;// 指向上一个节点的指针

T _data; // 节点存储的数据

};

ListNode(const T& x = T()) 必须加上 =T() !!!

默认参数的提供：

构造函数中的 = T() 表示如果调用者在创建 ListNode 对象时没有提供参数 x，则会使用 T() 这个默认值来初始化 _data 成员变量。灵活性：这种构造函数提供了更大的灵活性。如果调用者提供了参数 x，则会使用提供的值来初始化节点的 _data 成员；如果没有提供参数 x，则会使用 T() 的默认构造函数生成一个默认值来初始化 _data。适用性：对于链表节点来说，可能存在需要默认构造的情况，例如默认构造一个空节点或者默认值为特定类型的情况。通过提供默认参数，可以简化在某些场景下节点的创建。

为什么ListNode* _prev; 要加？？？

模板类 ListNode 是一个通用类型，它可以被实例化为不同的数据类型。加上 是为了告诉编译器 _next 是一个指向相同类型的 ListNode 实例的指针。

这里，ListNode 是一个模板类，它可以用任何类型的 T 来实例化。例如，你可以有一个 ListNode 用于整数类型，或者一个 ListNode 用于浮点数类型。

ListNode* intNode;

ListNode* doubleNode;

在模板类的内部，也需要指定具体类型。例如，当定义 _next 指针时，需要明确它指向的是哪种类型的 ListNode，因此使用 ListNode*。如果不加 ，编译器将不知道 _next 是指向哪个具体实例化类型的 ListNode。比如：

ListNode<int> node;

node._next = new ListNode<int>(5); // 正确，_next 是指向 ListNode<int> 的指针

ListNode<double> dnode;

dnode._next = new ListNode<double>(3.14); // 正确，_next 是指向 ListNode<double> 的指针

结构体（struct）？？？

是一种自定义数据类型，用于将多个相关的变量组合在一起。结构体可以包含基本数据类型、指针、引用、其他结构体、类等成员。与类（class）的主要区别在于结构体的默认访问控制是公有的（public），而类的默认访问控制是私有的（private）。

带有构造函数的结构体：结构体可以包含构造函数，用于初始化成员变量。函数名就是结构体名

3.__list_iterator 结构体模板

迭代器有两种实现方式，根据容器底层的数据结构进行选择：

原生指针：例如，vector和string的底层是连续的物理内存空间。

vector和string的迭代器实际上是原生指针，因为它们的数据存储在连续的内存空间中。通过指针的自增、自减以及解引用操作，我们可以对相应位置的数据进行操作。 封装指针：对于不连续的存储结构，需要将原生指针封装成迭代器类。

由于迭代器的使用形式与指针完全相同，因此在自定义迭代器类中必须实现以下功能：

解引用：必须重载operator*()。成员访问：必须重载operator->()。向后移动：必须重载operator++()和operator++(int)。向前移动（如双向链表）：重载operator--()和operator--(int)。比较操作：需要重载operator==()和operator!=()。

对于list来说，其各个结点在内存中的位置是随机的，并非连续存储。因此，不能通过简单的指针自增、自减和解引用操作对结点进行操作。

迭代器的意义在于，让用户可以不必关心容器的底层实现，通过统一的方式访问容器内的数据。因为list的结点指针不满足迭代器的定义，我们需要对结点指针进行封装，对各种运算符进行重载。

总结：list的迭代器实际上就是对结点指针的封装，通过重载各种运算符，使得结点指针的行为看起来和普通指针一样。例如，对结点指针自增后可以指向下一个结点p = p->next。

①模板参数说明

template<class T, class Ref, class Ptr>

typedef __list_iterator<T, Ref, Ptr> self; // 定义迭代器类型的别名

__list_iterator 被定义为一个模板结构体，并且引入了三个模板参数：T, Ref, 和 Ptr。通过不同的类型实例化 Ref 和 Ptr，我们可以区分出普通迭代器和常量迭代器。

对于普通迭代器，Ref 是 T& ，所以 operator*() 返回节点数据的引用，允许修改数据。对于常量迭代器，Ref 是 const T& ，所以 operator*() 返回节点数据的常量引用，不允许修改数据。对于普通迭代器，Ptr 是 T* ，所以 operator->() 返回指向节点数据的指针，允许通过指针修改数据。对于常量迭代器，Ptr 是 const T* ，所以 operator->() 返回指向节点数据的常量指针，不允许通过指针修改数据。

②构造函数

<code>//构造函数，接受一个节点指针

__list_iterator(Node* x)

:_node(x)

{ }

__list_iterator 的构造函数接受一个指向 ListNode 的指针 x，然后将 _node 成员变量初始化为 x。因此，每个 __list_iterator 对象都包含一个指向 ListNode 的指针 _node。

另外：构造函数的名字必须与类的名字完全相同，不能使用类型的别名代替构造函数的名字。 上面self(Node* x) 是错的

③迭代器类：拷贝构造、赋值操作、析构函数的说明

拷贝构造函数、赋值操作符和析构函数的必要性

在迭代器类中，拷贝构造函数、赋值操作符和析构函数的实现通常取决于迭代器的成员变量类型。如果迭代器的成员变量是指针（或者其他内置类型），且不需要进行复杂的资源管理，通常可以依赖编译器自动生成的默认版本。

拷贝构造函数：拷贝构造函数的作用是创建一个新的迭代器对象，该对象是另一个迭代器对象的副本。在迭代器中，成员变量是指针（内置类型），默认生成的拷贝构造函数将进行浅拷贝（即直接复制指针的值）。这种浅拷贝在大多数情况下足够，因为迭代器通常只是指向某个容器内的结点，不管理结点的生命周期。赋值操作符：赋值操作符用于将一个迭代器对象的值赋给另一个迭代器对象。由于迭代器的成员变量是指针，默认生成的赋值操作符也会进行浅拷贝，这样的行为是合适的。析构函数：析构函数负责清理对象使用的资源。由于迭代器只负责访问和修改链表的结点，而结点的内存管理是由链表（list）负责的，因此迭代器本身不需要释放这些结点的内存。链表的析构函数会处理结点的释放。因此，迭代器的析构函数可以留给编译器自动生成的默认版本。

拷贝构造函数的应用示例

list<int>::iterator it = lt.begin();

这里的it是通过拷贝构造函数创建的。lt.begin()返回一个迭代器对象，这个迭代器对象指向链表的第一个结点。it通过拷贝构造函数从lt.begin()初始化。因为迭代器内部包含的只是指针（浅拷贝足够），所以默认的拷贝构造函数是适用的。

3. 注意点

链表的结点与迭代器的关系：迭代器仅用于访问和修改链表的结点，不负责管理结点的内存。链表的析构函数会负责释放结点的内存。return *this与return this：

return *this：返回当前对象的克隆（值），通常用于返回迭代器对象的副本。return this：返回当前对象的地址（指针），用于返回当前迭代器对象的指针。这在需要直接操作对象地址时使用。

**类型别名 **self

typedef list_iterator<T, Ref, Ptr> self;

在迭代器类中，我们可能会定义self类型别名，以便在代码中更简洁地引用当前迭代器的类型。self代表了当前迭代器类的自身类型，这样可以使代码更加清晰和易于维护。

④++运算符和–运算符

前置++

// 前置++运算符重载，使迭代器指向下一个节点。

//++it

self& operator++()

{

_node = _node->_next;

return *this;

}

为什么返回引用？

这里的前置++运算符重载返回的是一个引用，即 self & 。它的作用是使迭代器向前移动到下一个节点，并返回移动后的迭代器对象自身。这种形式的重载通常在使用时会直接对迭代器进行修改，并返回修改后的对象的引用，以便支持链式操作。

前置++运算符不需要任何参数，只需将迭代器移动到下一个位置并返回自身的引用即可。具体来说，它会将迭代器所指向的节点指针 _node 移动到下一个节点 _next，然后返回当前对象自身的引用 (*this)。

后置++

//后置++运算符重载，使迭代器指向下一个节点，并返回之前的迭代器

//it++

self operator++(int)

{

// 1. 创建一个名为 tmp 的临时迭代器对象，它通过调用 __list_iterator 的拷贝构造函数，用当前迭代器 *this 进行初始化。

self tmp(*this);// 创建一个临时迭代器对象，保存当前迭代器的状态

// 2. 将当前迭代器移动到下一个节点

_node = _node->_next;

// 3. 返回之前的迭代器状态

return *this;

}

后置++为什么有(int)？？？

后置++运算符重载接受一个额外的 int 参数（这里没有实际使用它，只是为了区分前置和后置++），并返回一个值而不是引用。

C++中的后置++运算符必须在参数列表中声明一个int类型的参数，以便与前置++运算符进行区分。这种参数实际上并没有用处，只是为了在编译器中区分前置和后置++运算符的不同。没有参数的后置++运算符将会与前置++运算符具有相同的参数列表，这会导致编译器无法正确区分它们，从而导致编译错误。

前置–

self& operator--()

{

_node = _node->_prev;

return *this;

}

后置–

self operator--(int)

{

self tmp(*this);

_node = _node->_prev;

return tmp;

}

⑤==和!=

bool operator!=(const self& s)

{ //_node 是指向当前节点的指针，比较 _node 和 s._node 是否相等，如果不相等返回 true，否则返回 false。

return _node != s._node;

}

bool operator ==(const self& s)

{ //s是另一个迭代器对象,

return _node == s._node;

}

⑥*运算符

//这个重载函数的目的是允许通过迭代器访问当前节点的数据。

//Ref：表示解引用运算符返回的类型。

//

Ref operator*()

{

return _node->_data;

//是指向当前节点存储数据的成员变量 _data。通过返回 _data 的引用，允许用户通过

//迭代器解引用（使用 *it）来访问和修改节点中存储的数据。

}

⑦->运算符

//Ptr：表示指针访问运算符返回的类型。

//返回节点数据的地址

Ptr operator->()

{

return &_node->_data;

}

应用：

class Date

{

public:

Date(int year = 0, int month = 0, int day = 0)

{

_year = year;

_month = month;

_day = day;

}

int _year;

int _month;

int _day;

};

int main()

{

mylist::list<Date> lt;

Date d1(2023, 10, 11);

Date d2(2024, 6, 13);

lt.push_back(d1);

lt.push_back(d2);

auto it = lt.begin();

while (it != lt.end())

{

//cout << (*it)._year <<" "<<(*it)._month<< " "<< (*it)._day<<endl;

cout << it->_year << " " << it->_month << " " << it->_day << endl;

it++;

}

}

`(*it)：

it 是一个迭代器，*it 使用解引用运算符 * 来获取迭代器所指向的 Date 对象。(*it) 是一个 Date 对象的引用。

(*it)._year、(*it)._month、(*it)._day：

通过 (*it) 获取的 Date 对象，可以访问其成员变量 _year、_month 和 _day。这三部分分别获取 Date 对象的年、月和日。

也可以用->直接访问成员

C++ 编译器在处理 <code>it-> (相当于it.operator->())这个表达式时，会进行以下操作：

首先，it-> 调用 operator->() 方法。这个方法返回一个 Date 对象的指针（Date*）。其次，返回的 Date* 指针用于访问 Date 对象的成员，比如 it->_year。

为了使代码更加简洁和可读，C++ 编译器允许我们直接使用 it-> 来访问数据成员，而无需显式地进行两次箭头运算。这个处理方式避免了冗余的箭头操作，使得代码更为直观。

4.list结构体模板

①默认成员函数

构造函数1. 默认构造函数

先构造一个头结点，然后让_next和_prev都指向自己就行了

<code> //这个以后会经常用到

void empty_init()

{

//用于创建一个新的链表节点对象，并将 _head 指针指向这个新创建的节点。

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

}

//构造函数

list()

{

empty_init();

}

构造函数2. 用n个相同的值初始化

list(size_t n, const T& val = T())

{

empty_init();

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

构造函数3.迭代器区间初始化

//使用迭代器区间初始化

template<class InputIterator>//取名为InputIterator说明可以用任意类型的迭代器构造

list(InputIterator first, InputIterator last)

{

empty_init();

while (first != last)

{

push_back(*first);//复用push_back

first++;

}

}

template<class InputIterator>

目的: 声明一个模板函数，允许使用任意类型的迭代器来初始化 list 对象。解释: InputIterator 是一个模板参数，表示输入迭代器类型。这样，构造函数可以接受各种支持迭代器接口的类型（如指针、标准库中的迭代器等）。

list(InputIterator first, InputIterator last)

目的: 定义一个构造函数，该构造函数接收两个迭代器 first 和 last，表示一个迭代器区间。解释: 这两个迭代器标识了区间的起始位置 first 和结束位置 last。构造函数会从 first 开始，直到 last 之前的位置，依次将区间内的元素插入到 list 中。

构造函数2. 用n个相同的值初始化 和 构造函数3.迭代器区间初始化 在某些情况下可能会发生冲突

void test_list()

{

mylist::list<int> lt(6,3);

for(auto e:lt)

{

cout<<e<<" ";

}

cout<<endl;

}

当你写下如下代码：

mylist::list<int> lt(6,3);

你希望使用的是构造函数2，即创建一个包含 6个值 3 的 list。但是，由于 6 和 3 也可以被视为两个迭代器，编译器可能会错误地选择构造函数3（迭代器区间初始化），因为两个整数也可以被视为迭代器范围。此时会导致编译错误或者运行时错误。

为了避免这种冲突，可以为用 n 个相同的值初始化的构造函数增加一个额外的参数（比如 int 类型的参数），使其更加明确。修改后的构造函数如下：

list(int n, const T& val = T())

{

empty_init();

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

构造函数4.初始化列表初始化

方法1：迭代器遍历插入

手动遍历初始化列表，通过迭代器逐个插入元素到列表中。实现简单，易于理解，但略显冗长。

list(initializer_list<T> ilt)

{

//使用初始化列表的迭代器进行遍历，从头到尾一个一个元素地插入到列表中。

//push_back 函数会将元素添加到列表的末尾。

empty_init();

initializer_list<T>::iterator it = ilt.begin();

while(it != ilt.end())

{

push_back(*it); // 复用 push_back 函数

it++;

}

}

initializer_list<T> 是 C++11 引入的一种标准库类型，用于支持初始化列表语法。它使得可以用花括号括起来的逗号分隔列表来初始化对象，如数组、容器或其他类。

initializer_list<T> 的概念

initializer_list<T> 是一个模板类，允许你传递一个类型为 T 的常量数组，并通过迭代器遍历该数组的元素。它主要用于让类或函数能够接受一个花括号包围的元素列表。

使用 initializer_list<T>

方法2：范围 for 循环：

使用范围 for 循环遍历初始化列表并插入元素。语法更加简洁，易读性更高。

list(initializer_list<T> ilt)

{

empty_init();

for (auto& e : ilt)

{

push_back(e);

}

//使用范围 for 循环遍历初始化列表中的所有元素，

//并使用 push_back 函数将每个元素添加到列表的末尾。这种方式比迭代器遍历更加简洁和易读。

}

方法3：现代写法：

利用迭代器初始化的构造函数和 std::swap 进行优化。代码简洁高效，但需要对临时对象和 std::swap 的用法有所了解。

list(initializer_list<T> ilt)

{

empty_init();

list<T> tmp(ilt.begin(), ilt.end()); // 复用迭代器初始化的函数，构造出临时对象

std::swap(_head, tmp._head); // 交换哨兵位节点指针

}

利用已有的迭代器区间初始化的构造函数，创建一个临时 list 对象 tmp。这个临时对象 tmp 会包含初始化列表中的所有元素。

交换当前对象的哨兵节点和临时对象 tmp 的哨兵节点。通过这种交换，当前对象的 list 就会包含初始化列表中的所有元素，而 tmp 的哨兵节点会变为空列表的哨兵节点。当 tmp 被销毁时，它的哨兵节点将指向空列表，从而避免访问非法内存。

拷贝构造函数

传统写法：

//l1(l2);

//拷贝构造(深拷贝) 一个节点一个节点的拷贝

list(list<T>& lt)

{

empty_init();

for (const auto& e : lt)

{

push_back(e);

}

}

//深拷贝的关键步骤：

//节点复制：

//每次调用 push_back(e) 时，都创建一个新的 ListNode 对象，

//并将 e 的值复制到新节点的 data 成员中。

现代写法：

// 拷贝构造 - 现代写法

// lt2(lt1)

list(const list<T>& lt) {

empty_init();

list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造

std::swap(_head, tmp._head); // 交换哨兵位指针

}

解释：

list<T> tmp(lt.begin(), lt.end()); 这行代码使用迭代器区间 [lt.begin(), lt.end()) 来构造一个临时的 list 对象 tmp。这个临时对象包含了 lt 中的所有元素。

std::swap(_head,tmp._head);这行代码使用 std::swap 函数交换当前对象的哨兵节点 _head 和临时对象 tmp 的哨兵节点 tmp._head。

std::swap 交换两个指针的值，这意味着现在 tmp._head 指向了新创建的哨兵节点，而当前对象的 _head 指向了包含 lt 元素的节点链表。

这一步是关键，因为这样一来，当前对象就获得了 tmp 中的所有元素，而临时对象 tmp 在出作用域时会被销毁，其原来的哨兵节点会被释放。

赋值运算符重载函数

//l1=l2

list<T> operator=(list<T>& lt)

{

if(this!=&lt)

{

clear();

for(const auto&e :lt)

{

push_back(e);

}

}

}

为什么返回类型是 list &的引用？？？

链式调用

返回对当前对象的引用（* this），可以实现链式调用。链式调用允许多个赋值操作连在一起写。例如：

list<int> lt1;

list<int> lt2;

list<int> lt3;

lt1 = lt2 = lt3;

在上面的代码中，lt2 = lt3 返回的是 lt2 的引用，接着 lt1 = lt2 也可以正常工作。这种方式使得代码更简洁和直观。

提高代码效率

返回引用避免了不必要的对象拷贝。在赋值运算符函数中，返回 * this 的引用，而不是返回一个新的对象，可以减少对象拷贝，提升代码的性能和效率。

符合 C++ 的惯例

在 C++ 中，赋值运算符通常返回左值引用，以符合语言习惯和标准库的设计。这样做使得自定义类型的行为与内置类型一致，从而提高代码的可读性和可维护性。

现代写法

同样也是用swap

void swap(list<T>& tmp)

{

std::swap(_head, tmp._head);

}

list<T> operator=(list<T> lt)//不能用引用

{

swap(lt);

return *this;

}

为什么不能传引用？

当我们使用传值时，函数参数 lt 会在函数调用时被复制。这个复制操作会创建一个临时对象（拷贝副本），该对象在函数体内可以安全地操作。传值的好处是：

异常安全性：如果在复制对象时发生异常，原对象不会受到影响，因为赋值操作还没有进行。自我赋值：通过传值，我们不需要额外检查自我赋值（如 a = a），因为我们在函数体内操作的是拷贝副本。简洁的实现：传值和使用 swap 技术相结合，使得赋值运算符的实现非常简洁明了。

如果我们传引用，可能会引发一些问题，比如：

异常安全性：传引用时，如果在赋值过程中发生异常，原对象的状态可能会变得不一致或部分修改。自我赋值检测：需要额外的代码来检测和处理自我赋值的情况。

析构函数

void clear()

{

iterator it = begin();

while (it != end())

//begin() 和 end() 方法是属于包含这些方法的类的成员函数，它们在不传递参数的情况下会被假定为作用于当前对象（即 this 指针指向的对象）。

{

it = erase(it);//erase 会返回被删除节点的下一个节点

}

}//erase 会有迭代器失效问题

//析构函数

//注意析构需要把带哨兵位的头结点也要去掉.和清空不一样

~list()

{

clear();

delete _head;

_head = nullptr;

}

②迭代器

iterator begin()

{

//return iterator(_head->_next); 下面这个也可以，因为可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数？？？

return _head->_next;

}

iterator end()

{

return _head;

//对于带头节点的双向循环链表，_head 节点实际上是链表的“尾部”。

//因为链表的最后一个有效节点的下一个节点是 _head，所以返回 _head 可以表示链表的末尾位置。

}

const_iterator begin() const

{

return _head->_next;

}

const_iterator end() const

{

return _head;

}

return _head->_next 和 return iterator(_head->_next) 在某些情况下可以看起来是一样的，但它们的行为是不同的，具体取决于上下文和类型的隐式转换。

/*return _head->_next 和 return iterator(_head->_next) 在某些情况下可以看起来是一样的，但它们的行为是不同的，具体取决于上下文和类型的隐式转换。

return _head->_next

假设 _head->_next 是一个 Node * 类型的指针。如果 iterator 类型的构造函数接受 Node * 类型的参数，并且在返回时能够自动转换，那么 return _head->_next 可以看起来像是在返回一个 iterator 对象。实际上，如果 iterator 的构造函数接受 Node * ，_head->_next 会通过这个构造函数隐式地转换为 iterator 类型。

return iterator(_head->_next)

这是一个显式的构造函数调用，它直接创建一个 iterator 对象，使用 Node * 参数 _head->_next 来初始化它。这里明确地调用了 iterator 的构造函数来创建一个新的 iterator 实例。

③增删查改

//获取第一个数据的内容

T& front()

{

return *begin();//返回第一个数据的引用

}

const T& front() const

{

return *begin(); //返回第一个数据的const引用

}

//获取最后一个数据的内容

T& back()

{

return *(--end());//返回尾结点数据的引用

}

const T& back() const

{

return *(--end()); //返回最后一个有效数据的const引用

}

//头删

void pop_front()

{

//erase(_head->_next);

erase(begin());

}

//尾删

void pop_back()

{

//erase(_head->_prev);

erase(--end());

}

//为何用--end()？？？

//end() 函数：

//end() 函数返回的是指向链表结尾的迭代器，通常是指向哨兵节点（尾后节点）的迭代器。

//--end() 操作：

//end() 返回的迭代器通常指向链表的尾后位置，即哨兵节点的位置。--end() 操作将这个迭代器前移一个位置，

// 指向链表中最后一个实际节点的位置。

//头插

void push_front(const T& x)

{

insert(begin(), x);

}

//尾插

void push_back(const T& x)

{

//insert(end(), x); //复用insert的版本

//画图看就比较清晰了

Node* newnode = new Node(x);

Node* tail = _head->_prev; //head的前一个节点是尾节点，下一个节点是头结点

tail->_next = newnode;

newnode->_prev = tail;

newnode->_next = _head;

_head->_prev = newnode;

}

//在pos位置插入数据

// vector insert会导致迭代器失效

// list会不会？不会

iterator insert(iterator pos, const T& x)//返回： 可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数

//push_back 就可以复用insert了

{

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* newnode = new Node(x);

// head------>prev---->cur--->node1--->node2 向右是next 向左是prev

// newnode

prev->_next = newnode;

newnode->_prev = prev;

newnode->_next = cur;

cur->_prev = newnode;

//return interator(newnode); 也可以 ，为什么？？？

return newnode;

}

//删除pos位置的数据

iterator erase(iterator pos)

{

Node* cur = pos._node;

//. 用于对象，而 -> 用于指针。

//pos 是一个迭代器对象，它不是指针。因此我们使用 . 操作符来访问迭代器对象的成员变量 _node。

Node* prev = cur->_prev;

Node* next = cur->_next;

prev->_next = next;

next->_prev = prev;

delete cur;

return next;

}

④其他操作

size:获取有效数据的个数

//长度

size_t size()

{

//遍历统计

size_t sz = 0;

iterator it = begin();

while (it != end())

{

++sz;

++it;

}

return sz;

}

clear：清空链表内容

void clear() {

// 检查链表是否为空，如果为空则直接返回

if (begin() == end()) {

return;

}

//begin() 和 end() 方法是属于包含这些方法的类的成员函数，它们在不传递参数的情况下会被假定为作用于当前对象（即 this 指针指向的对象）。

iterator it = begin();

while (it != end()) {

// 调用 erase 方法并将 it 更新为被删除节点的下一个节点

it = erase(it);

//erase 会返回被删除节点的下一个节点

}

// 哨兵节点重新指向自己，确保后续插入操作不会出错

_head->_prev = _head;

_head->_next = _head;

}

empty:判断链表是否为空

bool empty() const

{

return begin()==end();

}

swap

swap函数用于交换两个list,list容器当中的成员变量只有指向哨兵位结点的指针,我们将这两个容器当中的哨兵位指针交换即可,

void swap(list<T>& lt)

{

::swap(_head, lt._head);//直接交换两个容器的哨兵位即可,此处用的是全局域std命名空间里面的swap函数

}

resize

void resize(size_t n, const T& val = T())

{

// 新大小大于当前大小，添加新节点

if (n > size())

{

for (size_t i = size(); i < n; i++)

{

push_back(val);

}

}

// 新大小小于当前大小，删除多余的节点

else if (n < size())

{

iterator it = begin();

size_t pos = 0;

// 遍历到需要删除的位置

while (pos < n && it != end())

{

++it;

++pos;

}

// 从当前位置删除到链表末尾

while (it != end())

{

it = erase(it);

}

}

}

5.完整代码展示以及详细注释

#pragma once

#include<assert.h>

//这节 简单讲了一下使用，然后大部分是模拟实现。

//1. 有个地方要有合适的 构造函数

//2.迭代器如何实现+1 如何自动跳到下一个节点的？

//———————————————————————————————————————————————————以下部分为便于理解整体逻辑框架结构而写的

//分为以下几大部分：

//节点结构体模板、__list_iterator 结构体模板、list结构体模板（由一个个节点组成）、测试函数。

//

//———————————————————————————————————————————————————以下部分为便于理解整体逻辑框架结构而写的

//分为以下几大部分：

//节点结构体模板

//__list_iterator 结构体模板

//list结构体模板（由一个个节点组成）

//测试函数

//首先，我们定义了一个节点结构体模板 ListNode，它包含：

//

//ListNode* 类型的 _next 和 _prev 指针，分别指向前后节点。

//T 类型的 _data，存放节点的数据。

//ListNode 的构造函数初始化这些成员。

//然后，我们定义了一个模板结构体 __list_iterator，用于实现链表的迭代器。这个迭代器包含：

//

//一个指向当前节点的指针 _node。

//构造函数、前置和后置 ++、-- 运算符重载、解引用运算符、相等和不相等比较运算符等操作。

//为了简化代码，__list_iterator 使用了两个 typedef：

//将 ListNode<T> 重命名为 Node。

//将 __list_iterator<T, Ref, Ptr> 重命名为 self。

//接下来，我们实现了 list 结构体模板。它包含一个带哨兵位的头结点 _head，类型为 Node* 。通过这个头结点以及迭代器指向的各个节点，形成一个带头的双向循环链表。

//

//在 list 中，我们将 __list_iterator<T, T&, T*> 重命名为 iterator，将 __list_iterator<T, const T&, const T*> 重命名为 const_iterator，

//一种是普通迭代器，一种是常量迭代器，以便用户更方便地使用迭代器。

//

//通过这些定义，我们实现了一个功能完整的双向循环链表，并且提供了迭代器接口，使得用户可以方便地遍历和操作链表中的元素。

//

//这个结构通过 ListNode 实现了双向节点连接，通过 __list_iterator 实现了链表的遍历和操作接口，并通过 list 结构体模板实现了整体的双向循环链表功能。测试函数用于验证各部分的功能和接口是否正常运行。

//

// 声明一个命名空间 mylist

namespace mylist

{

// 定义一个模板结构体 ListNode，表示链表的节点

template<class T>//每个模板类或模板函数的定义都需要用 template<class T> 来声明。这样做的原因是为了告诉编译器这个类或函数是一个模板，且它是依赖于一个类型参数 T

struct ListNode

{

// 构造函数，使用默认参数 T() 初始化 _data，并将 _next 和 _prev 初始化为 nullptr

ListNode(const T& x = T())

:_next(nullptr)

, _prev(nullptr) //记得加上 ,

, _data(x)

{ }

ListNode<T>* _next;/// 指向下一个节点的指针

ListNode<T>* _prev;// 指向上一个节点的指针

T _data; // 节点存储的数据

};

//ListNode(const T& x = T()) 必须加上 =T() !!!

//默认参数的提供：

//构造函数中的 = T() 表示如果调用者在创建 ListNode 对象时没有提供参数 x，则会使用 T() 这个默认值来初始化 _data 成员变量。

//灵活性：

//这种构造函数提供了更大的灵活性。如果调用者提供了参数 x，则会使用提供的值来初始化节点的 _data 成员；如果没有提供参数 x，则会使用 T() 的默认构造函数生成一个默认值来初始化 _data。

//适用性：

//对于链表节点来说，可能存在需要默认构造的情况，例如默认构造一个空节点或者默认值为特定类型的情况。通过提供默认参数，可以简化在某些场景下节点的创建。

//结构体（struct）？？？

//是一种自定义数据类型，用于将多个相关的变量组合在一起。结构体可以包含基本数据类型、指针、引用、其他结构体、类等成员。与类（class）的主要区别在于结构体的默认访问控制是公有的（public），

//而类的默认访问控制是私有的（private）。

//带有构造函数的结构体：

//结构体可以包含构造函数，用于初始化成员变量。函数名就是结构体名

//为什么ListNode<T>* _prev; 要加<T>???

//模板类 ListNode 是一个通用类型，它可以被实例化为不同的数据类型。加上 <T> 是为了告诉编译器 _next 是一个指向相同类型的 ListNode 实例的指针。

//这里，ListNode 是一个模板类，它可以用任何类型的 T 来实例化。例如，你可以有一个 ListNode<int> 用于整数类型，或者一个 ListNode<double> 用于浮点数类型。

//ListNode<int>* intNode;

//ListNode<double>* doubleNode;

//在模板类的内部，也需要指定具体类型。例如，当定义 _next 指针时，需要明确它指向的是哪种类型的 ListNode，因此使用 ListNode<T>*。如果不加 <T>，编译器将不知道 _next 是指向哪个具体实例化类型的 ListNode。

//比如：

//ListNode<int> node;

//node._next = new ListNode<int>(5); // 正确，_next 是指向 ListNode<int> 的指针

//ListNode<double> dnode;

//dnode._next = new ListNode<double>(3.14); // 正确，_next 是指向 ListNode<double> 的指针

//定义一个模板结构体 __list_iterator，用于实现链表的迭代器

template<class T, class Ref, class Ptr>

struct __list_iterator

{

typedef ListNode<T> Node;// 定义节点类型的别名

typedef __list_iterator<T, Ref, Ptr> self; // 定义迭代器类型的别名

//__list_iterator 被定义为一个模板结构体，并且引入了三个模板参数：T, Ref, 和 Ptr。通过不同的类型实例化 Ref 和 Ptr，我们可以区分出普通迭代器和常量迭代器。

Node* _node; // 指向链表节点的指针

//构造函数，接受一个节点指针

__list_iterator(Node* x)

:_node(x)

{ }

//__list_iterator 的构造函数接受一个指向 ListNode<T> 的指针 x，然后将 _node 成员变量初始化为 x。因此，每个 __list_iterator<T> 对象都包含一个指向 ListNode<T> 的指针 _node。

//另外：构造函数的名字必须与类的名字完全相同，不能使用类型的别名代替构造函数的名字。 上面self(Node* x) 是错的

// 前置++运算符重载，使迭代器指向下一个节点。

//++it

self& operator++()

{

_node = _node->_next;

return *this;

}

//为什么返回引用

//这里的前置++运算符重载返回的是一个引用，即 self & 。它的作用是使迭代器向前移动到下一个节点，并返回移动后的迭代器对象自身。这种形式的重载通常在使用时会直接对迭代器进行修改，并返回修改后的对象的引用，以便支持链式操作。

//前置++运算符不需要任何参数，只需将迭代器移动到下一个位置并返回自身的引用即可。具体来说，它会将迭代器所指向的节点指针 _node 移动到下一个节点 _next，然后返回当前对象自身的引用 (*this)。

//后置++运算符重载，使迭代器指向下一个节点，并返回之前的迭代器

//it++

self operator++(int)

{

// 1. 创建一个名为 tmp 的临时迭代器对象，它通过调用 __list_iterator 的拷贝构造函数，用当前迭代器 *this 进行初始化。

self tmp(*this);// 创建一个临时迭代器对象，保存当前迭代器的状态

// 2. 将当前迭代器移动到下一个节点

_node = _node->_next;

// 3. 返回之前的迭代器状态

return *this;

}

//后置++为什么有(int)？？？

//后置++运算符重载接受一个额外的 int 参数（这里没有实际使用它，只是为了区分前置和后置++），并返回一个值而不是引用。

//C++中的后置++运算符必须在参数列表中声明一个int类型的参数，以便与前置++运算符进行区分。这种参数实际上并没有用处，只是为了在编译器中区分前置和后置++运算符的不同。没有参数的后置++运算符将会与前置++运算符具有相同的参数列表，这会导致编译器无法正确区分它们，从而导致编译错误。

self& operator--()

{

_node = _node->_prev;

return *this;

}

self operator--(int)

{

self tmp(*this);

_node = _node->_prev;

return tmp;

}

//这个重载函数的目的是允许通过迭代器访问当前节点的数据。

//Ref：表示解引用运算符返回的类型。

//

Ref operator*()

{

return _node->_data;//是指向当前节点存储数据的成员变量 _data。通过返回 _data 的引用，允许用户通过迭代器解引用（使用 *it）来访问和修改节点中存储的数据。

}

//有点难理解

//Ptr：表示指针访问运算符返回的类型。

//返回节点数据的地址

Ptr operator->()

{

return &_node->_data;

}

//上面俩的解释：

//对于普通迭代器，Ref 是 T& ，所以 operator*() 返回节点数据的引用，允许修改数据。

//对于常量迭代器，Ref 是 const T& ，所以 operator*() 返回节点数据的常量引用，不允许修改数据。

//对于普通迭代器，Ptr 是 T* ，所以 operator->() 返回指向节点数据的指针，允许通过指针修改数据。

//对于常量迭代器，Ptr 是 const T* ，所以 operator->() 返回指向节点数据的常量指针，不允许通过指针修改数据。

bool operator!=(const self& s)

{ //_node 是指向当前节点的指针，比较 _node 和 s._node 是否相等，如果不相等返回 true，否则返回 false。

return _node != s._node;

}

bool operator ==(const self& s)

{ //s是另一个迭代器对象,

return _node == s._node;

}

//迭代器为什么不提供析构函数

};

template<class T>

class list

{

public:

typedef ListNode<T> Node;

/*typedef __list_iterator<T> iterator;*/

typedef __list_iterator<T, T&, T*> iterator; //定义普通迭代器

typedef __list_iterator<T, const T&, const T*> const_iterator; //定义常量迭代器

//这样，iterator 和 const_iterator 都使用同一个 __list_iterator 结构体模板，只是通过不同的模板参数实例化，分别实现普通迭代器和常量迭代器的功能。

//第一个 三个参数 T,Ref，Ptr分别就是，T,T&,T*.

//第二个 三个参数 T,Ref，Ptr分别就是 T,const T&,const T*

// 反向迭代器

//typedef ReverseListIterator<iterator> reverse_iterator;

//typedef ReverseListIterator<const_iterator> const_reverse_iterator;

//访问

iterator begin()

{

//return iterator(_head->_next); 下面这个也可以，因为可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数？？？

return _head->_next;

}

iterator end()

{

return _head;

//对于带头节点的双向循环链表，_head 节点实际上是链表的“尾部”。因为链表的最后一个有效节点的下一个节点是 _head，所以返回 _head 可以表示链表的末尾位置。

}

/*return _head->_next 和 return iterator(_head->_next) 在某些情况下可以看起来是一样的，但它们的行为是不同的，具体取决于上下文和类型的隐式转换。

1. return _head->_next

假设 _head->_next 是一个 Node * 类型的指针。如果 iterator 类型的构造函数接受 Node * 类型的参数，并且在返回时能够自动转换，那么 return _head->_next 可以看起来像是在返回一个 iterator 对象。实际上，如果 iterator 的构造函数接受 Node * ，_head->_next 会通过这个构造函数隐式地转换为 iterator 类型。

2. return iterator(_head->_next)

这是一个显式的构造函数调用，它直接创建一个 iterator 对象，使用 Node * 参数 _head->_next 来初始化它。这里明确地调用了 iterator 的构造函数来创建一个新的 iterator 实例。*/

const_iterator begin() const

{

return _head->_next;

}

const_iterator end() const

{

return _head;

}

void empty_init()

{

//用于创建一个新的链表节点对象，并将 _head 指针指向这个新创建的节点。

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

}

//构造函数

list()

{

empty_init();

}

list(size_t n, const T& val = T())

{

empty_init();

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

list(int n, const T& val = T())

{

empty_init();

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

template<class InputIterator>

list(InputIterator first, InputIterator last)

{

empty_init();

while (first != last)

{

push_back(*first);

first++;

}

}

list(initializer_list<T> ilt)

{

//使用初始化列表的迭代器进行遍历，从头到尾一个一个元素地插入到列表中。

//push_back 函数会将元素添加到列表的末尾。

empty_init();

initializer_list<T>::iterator it = ilt.begin();

while (it != ilt.end())

{

push_back(*it); // 复用 push_back 函数

it++;

}

}

list(initializer_list<T> ilt)

{

empty_init();

for (auto& e : ilt)

{

push_back(e);

}

//使用范围 for 循环遍历初始化列表中的所有元素，

//并使用 push_back 函数将每个元素添加到列表的末尾。这种方式比迭代器遍历更加简洁和易读。

}

list(initializer_list<T> ilt)

{

empty_init();

list<T> tmp(ilt.begin(), ilt.end()); // 复用迭代器初始化的函数，构造出临时对象

std::swap(_head, tmp._head); // 交换哨兵位节点指针

}

//拷贝构造(深拷贝) 一个节点一个节点的拷贝

list(list<T>& lt)

{

empty_init();

for (const auto& e : lt)

{

push_back(e);

}

}

//深拷贝的关键步骤：

//节点复制：

//每次调用 push_back(e) 时，都创建一个新的 ListNode 对象，并将 e 的值复制到新节点的 data 成员中。

// 拷贝构造 - 现代写法

// lt2(lt1)

//list(const list<T>& lt) {

//empty_init();

//list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造

//std::swap(_head, tmp._head); // 交换哨兵位指针

//}

// 拷贝构造函数，接受一个常量引用链表对象作为参数

//list(const list<T>& lt)

//{

//// 初始化新链表为空链表

//empty_init();

//// 获取给定链表的第一个节点的迭代器

//const_iterator it = lt.begin();

//// 遍历给定链表的所有节点

//while (it != lt.end())

//{

//// 将节点的数据插入到新链表的末尾

////这里的end和lt.end()不一样

//insert(end(), *it);

//// 移动到下一个节点

//++it;

//}

//}

//list(list<T>& lt) 是一个非常规的构造函数，接受一个非常量引用的链表对象。这样可以在需要对传入的链表进行修改的情况下使用。

//list(const list<T>& lt) 是一个标准的拷贝构造函数，接受一个常量引用的链表对象。这样可以确保不会对传入的链表进行修改。

//赋值运算符（普通写法）

// lt1=lt2

list <T>& operator =(list<T>& lt)

{

if (this != &lt)

{

clear();//先让lt1清空

for (const auto& e : lt) //再让lt2的数据尾插到lt1中

{

push_back(e);

}

}

}

//为什么返回类型是 list <T>&的引用？？？

//链式调用

//返回对当前对象的引用（* this），可以实现链式调用。链式调用允许多个赋值操作连在一起写。例如：

//list<int> lt1;

//list<int> lt2;

//list<int> lt3;

//lt1 = lt2 = lt3;

//在上面的代码中，lt2 = lt3 返回的是 lt2 的引用，接着 lt1 = lt2 也可以正常工作。这种方式使得代码更简洁和直观。

//提高代码效率

//返回引用避免了不必要的对象拷贝。在赋值运算符函数中，返回 * this 的引用，而不是返回一个新的对象，可以减少对象拷贝，提升代码的性能和效率。

//符合 C++ 的惯例

//在 C++ 中，赋值运算符通常返回左值引用，以符合语言习惯和标准库的设计。这样做使得自定义类型的行为与内置类型一致，从而提高代码的可读性和可维护性。

//赋值运算符（现代写法）

//list& operator=(list lt) // （也可以不写模板参数）也可以这样写，但仅限在类里面， 类型的时候就不行

void swap(list<T>& tmp)

{

std::swap(_head, tmp._head);

}

list<T> operator=(list<T> lt)//不能用引用

{

swap(lt);

return *this;

}

void clear() {

// 检查链表是否为空，如果为空则直接返回

if (begin() == end()) {

return;

}

//begin() 和 end() 方法是属于包含这些方法的类的成员函数，它们在不传递参数的情况下会被假定为作用于当前对象（即 this 指针指向的对象）。

iterator it = begin();

while (it != end()) {

// 调用 erase 方法并将 it 更新为被删除节点的下一个节点

it = erase(it);

//erase 会返回被删除节点的下一个节点

}

// 哨兵节点重新指向自己，确保后续插入操作不会出错

_head->_prev = _head;

_head->_next = _head;

}

//erase 会有迭代器失效问题

//析构函数

//注意析构需要把带哨兵位的头结点也要去掉.和清空不一样

~list()

{

clear();

delete _head;

_head = nullptr;

}

void pop_front()

{

//erase(_head->_next);

erase(begin());

}

void pop_back()

{

//erase(_head->_prev);

erase(--end());

}

//为何用--end()？？？

//end() 函数：

//end() 函数返回的是指向链表结尾的迭代器，通常是指向哨兵节点（尾后节点）的迭代器。

//--end() 操作：

//end() 返回的迭代器通常指向链表的尾后位置，即哨兵节点的位置。--end() 操作将这个迭代器前移一个位置，指向链表中最后一个实际节点的位置。

void push_front(const T& x)

{

insert(begin(), x);

}

void push_back(const T& x)

{

//insert(end(), x); //复用insert的版本

//画图看就比较清晰了

Node* newnode = new Node(x);

Node* tail = _head->_prev; //head的前一个节点是尾节点，下一个节点是头结点

tail->_next = newnode;

newnode->_prev = tail;

newnode->_next = _head;

_head->_prev = newnode;

}

// vector insert会导致迭代器失效

// list会不会？不会

iterator insert(iterator pos, const T& x)//返回： 可以简单点写，因为隐式类型转换， 迭代器是单参数的构造函数

//push_back 就可以复用insert了

{

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* newnode = new Node(x);

// head------>prev---->cur--->node1--->node2 向右是next 向左是prev

// newnode

prev->_next = newnode;

newnode->_prev = prev;

newnode->_next = cur;

cur->_prev = newnode;

//return interator(newnode); 也可以 ，为什么？？？

return newnode;

}

iterator erase(iterator pos)

{

Node* cur = pos._node;

//. 用于对象，而 -> 用于指针。

//pos 是一个迭代器对象，它不是指针。因此我们使用 . 操作符来访问迭代器对象的成员变量 _node。

Node* prev = cur->_prev;

Node* next = cur->_next;

prev->_next = next;

next->_prev = prev;

delete cur;

return next;

}

//补充

size_t size()

{

//遍历统计

size_t sz = 0;

iterator it = begin();

while (it != end())

{

++sz;

++it;

}

return sz;

}

void resize(size_t n, const T& val = T())

{

// 新大小大于当前大小，添加新节点

if (n > size())

{

for (size_t i = size(); i < n; i++)

{

push_back(val);

}

}

// 新大小小于当前大小，删除多余的节点

else if (n < size())

{

iterator it = begin();

size_t pos = 0;

// 遍历到需要删除的位置

while (pos < n && it != end())

{

++it;

++pos;

}

// 从当前位置删除到链表末尾

while (it != end())

{

it = erase(it);

}

}

}

private:

Node* _head;

//，__list_iterator 结构体模板内的 typedef 定义了一些别名（alias），这些别名在 list 结构体模板中得以继续使用是因为它们是 __list_iterator 类型的一部分。当 list 使用 __list_iterator 时，这些别名也随之可用

};

//这种情况下就需要const迭代器，这是很常见的现象。

//const迭代器：自己可以修改所以不是const对象（需要it++）

//指向的内容不能修改

void print_list(const list<int>& lt)

{

list<int>::const_iterator it = lt.begin();

while (it != lt.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

void test_list1()

{

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())

{

*it += 3;

cout << *it << " ";

++it;

}

cout << endl;

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

}

void test_list2()

{

list<int> lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

//1 2 3 4

lt.pop_back();

lt.pop_front();

lt.push_front(99);

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

//2 3 99

lt.clear();

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

}

void test_list3()

{

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();

lt.insert(it, 985);

//插入完后it仍然指向1

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;//985 1 2 3 4

++it;

//it指向2,在2前插入211

lt.insert(it, 211);

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;//985 1 211 2 3 4

}

void test_list4()

{

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();

it = lt.insert(it, 985);

//因为it返回的是新插入的节点的迭代器，所以it指向第一个元素985

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;//985 1 2 3 4

++it;

//it指向1,在1前插入211

lt.insert(it, 211); // it仍然指向1

//it=lt.insert(it, 211); //it指向211

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;//985 1 211 2 3 4

}

//讲解拷贝构造

//默认的浅拷贝 会析构两次 出现问题

void test_list5()

{

//list<int> lt;

//lt.push_back(1);

//lt.push_back(2);

//lt.push_back(3);

//lt.push_back(4);

list<int> copy(lt);

//for (auto e : copy)

//{

//cout << e << " ";

//}

}

void test_list6()

{

}

}

📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，

本人也很想知道这些错误，恳望读者批评指正！