坚持用 清晰易懂的图解 + 代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”
【C++ 】STL详解（六）—手撸一个属于你的 list！
1.list文档参考----------请点击
2.list的接口使用----------请点击
摘要
🚀 欢迎来到《C++修炼之路》！
这里是C++程序员的成长乐园，带你领略从面向对象到现代C++的精彩世界。我们将>用简洁的代码和生动的案例，助你掌握C++核心精髓。
🔍 专栏亮点：
- 现代C++特性解析（C++11/14/17）
- STL源码剖析与实战应用
- 内存管理与性能优化技巧
💡 收获预期：
✔️ 写出更健壮的C++代码
✔️ 深入理解面向对象设计
✔️ 掌握模板编程基础📌 编程箴言：
“好的C++代码就像好酒，需要时间沉淀。”
（正文开始👇）----本文学习list的模拟实现
目录
一、std::list 容器及其实现原理
在 C++ 中，std::list 是一种常用的容器，它基于 双向链表 实现，提供了高效的插入、删除操作。由于链表结构的特点，std::list 不像数组那样具有随机访问功能，但它在插入和删除元素时表现出色。我们可以通过类模板（声明定义不分离写法）模拟实现一个简化版的 std::list，以下是该实现的一些关键点。
- 节点定义与类模板
std::list是由多个节点（Node）组成的，每个节点包含数据以及指向前后节点的指针。由于std::list是一个模板类，它存储的数据类型是动态的，可以根据需求选择任意类型。因此，节点定义为一个struct类模板，使其能够适应不同的数据类型。节点中包含的数据类型T可以是任何类型，包括内置类型（如int）和自定义类型。节点的指针prev和next用于连接链表中的元素，形成双向链表。- 空间配置器（Allocator）
std::list容器通常会使用 空间配置器（allocator<T>）来管理内存，避免频繁在堆上进行空间申请和释放。allocator是 C++ 的内存管理工具，能够有效减少内存碎片化，提高性能。尽管allocator具有重要作用，但在这个简化版实现中，我们将其忽略，直接使用new和delete来管理内存。- 节点的构造
在创建节点时，节点的data会使用传入的值进行初始化，而prev和next指针则初始化为nullptr。如果用户未提供数据，我们可以使用默认构造函数来初始化节点的数据，C++ 为内置类型和自定义类型提供了默认构造函数，使得节点能够方便地进行初始化。size优化
传统的链表在获取链表大小时，通常需要通过遍历整个链表来计算节点数，时间复杂度为O(N)。为了优化这个问题，我们在std::list容器中引入了一个成员变量_size来记录链表的当前大小。这样，当调用size()函数时，直接返回_size即可，时间复杂度降为O(1)。- 哨兵节点的存在
std::list是一个 双向循环链表，即使链表为空，它也会有一个哨兵节点。这个哨兵节点不存储有效数据，而是用于维护链表结构。哨兵节点的存在使得我们可以统一处理链表的插入、删除操作，无论链表是否为空。哨兵节点指向自己，形成一个循环链表，避免了对空链表的特殊处理。- 显示实例化
由于std::list是模板类，用户在使用时需要显式地指定存储的数据类型。例如，当我们想要创建一个存储int类型的链表时，可以使用list<int>，而存储其他类型时，只需更改模板参数即可。通过模板实例化，编译器会根据传入的数据类型T自动生成相应的类，并在内部使用Node<T>来存储数据。总结：
- 节点的定义：每个节点
Node<T>存储数据以及前后指针，形成双向链表。- 空间配置器：虽然在简化实现中忽略了
allocator，但实际应用中它有助于优化内存管理。- 节点构造：节点通过构造函数初始化数据，并默认将指针设为
nullptr。- 大小优化：通过
_size成员变量，避免了传统链表的O(N)大小计算，提升效率。- 哨兵节点：链表总是包含一个哨兵节点，用于统一处理链表的插入、删除等操作。
- 显示实例化：通过模板实例化，可以灵活创建不同类型的链表。
namespace dh
{
// 定义一个结构体来表示双向链表中的节点
template<class T>
struct list_node
{
T _data; // 存储节点的数据，类型由模板参数'T'指定，支持任意类型的数据。
list_node<T>* _next; // 指向下一个节点的指针。
list_node<T>* _prev; // 指向上一个节点的指针。
list_node(const T& x = T())
: _data(x) // 初始化节点数据为传入参数'x'，如果没有传入则默认初始化为T类型的默认值。
, _next(nullptr) // 初始化指向下一个节点的指针为nullptr（表示链表末尾）。
, _prev(nullptr) // 初始化指向上一个节点的指针为nullptr（表示链表头部）。
{}
};
//定义一个双向链表类
template<class T>
class list
{
typedef list_node<T> Node; // 为'list_node<T>'定义一个别名'Node'，简化代码书写。
public:
private:
Node* sentinel;//指向哨兵节点的指针，作为链表的头节点，形成环形链表。
size_t _size;
};
}
二、构造函数
当我们没有数据的时候 如何实现这个双线链表？（为了简化双向链表的实现，我们使用一个哨兵节点，该节点不存储实际数据，而是作为占位符，始终存在于链表中。哨兵节点的
prev和next指针都指向自己，形成一个环形链表结构。这样，无论链表是否为空，头尾操作都可以统一进行，避免了空链表和非空链表的特殊处理，从而简化了链表的插入、删除等操作逻辑。）
list()
{
// 创建哨兵节点,构造函数，初始化链表。
sentinel = new Node; // 创建一个新的节点作为哨兵节点，并为其动态分配内存。
sentinel->_next = sentinel; // 将哨兵节点的next指针指向自己，形成一个环形链表。
sentinel->_prev = sentinel; // 将哨兵节点的prev指针指向自己，形成环形链表。
}
push_back的实现
void push_back(const T& x)
{
// 在链表的尾部添加一个新的元素。
Node* newnode = new Node(x); // 创建一个新的节点 'newnode'，并初始化其数据为'x'。
Node* tail = sentinel->_prev; // 获取当前链表的尾节点（即哨兵节点的前一个节点），tail指向最后一个有效节点。
tail->_next = newnode; // 将尾节点的next指针指向新创建的节点 'newnode'，表示尾节点的后继节点是 'newnode'。
newnode->_prev = tail; // 将新节点的prev指针指向尾节点，表示新节点的前驱节点是 'tail'。
newnode->_next = sentinel; // 将新节点的next指针指向哨兵节点，表示新节点是链表的最后一个节点，形成环形结构。
sentinel->_prev = newnode; // 将哨兵节点的prev指针指向新节点 'newnode'，表示哨兵节点的前驱节点是 'newnode'，保持环形结构。
}
三、简单迭代器的模拟实现
- 迭代器模拟指针行为： 迭代器本质上就是模拟指针的行为，通过解引用 (
*) 获取数据，通过递增 (++) 向后迭代获取下一个元素。 通过指针解引用获取数据，使用++移动到下一个元素。std::list的迭代器与指针行为的差异：std::list是由多个独立的节点构成，每个节点包含数据和指向前后节点的指针。每个节点的物理位置是不连续的，因此不能像std::vector或std::string那样直接使用指针操作。在list中，迭代器指向的是 节点 而不是节点中的数据。通过解引用得到的是整个节点，而不是存储在节点中的数据。- 迭代器不能使用常规指针行为： 由于节点的内存位置不连续，使用
++操作符会导致访问到未知的空间，而不是简单地跳到下一个数据位置。由于std::list的节点在内存中分散，常规的指针行为（如*和++）无法直接工作，需要通过更复杂的方式来模拟指针行为。- 自定义结构体封装节点指针： 为了能够在
std::list的迭代器中模拟指针的行为，我们需要一个结构体来封装节点的指针。该结构体通过重载*和++运算符来模拟指针操作。我们使用struct而不是class，因为我们需要频繁访问结构体的成员，且希望通过结构体的默认公开成员避免过多的友元函数或访问成员函数。- 模板类迭代器的实现： 由于
std::list是一个模板类，存储的数据类型是动态的，因此我们需要为迭代器使用模板类__list_iterator<T>，而不是简单的__list_iterator。这种方式能够确保迭代器适应不同数据类型的std::list。
下面是你所要求的总结，并以点的形式接在前面的内容后面：- 避免命名冲突： 由于每个容器都可能有自己的迭代器类型，为了避免命名冲突，
std::list的迭代器被命名为__list_iterator，而不是简单使用iterator。如果容器使用统一的iterator名称，可能会与其他容器的迭代器类型产生冲突。因此，为了避免这种情况，std::list使用__list_iterator<T>来命名自己的迭代器类型，并通过typedef将其定义为iterator，提供给外部使用，确保与其他容器的迭代器不发生命名冲突。
template<class T>
struct __list_iterator
{
typedef list_node<T> Node; // 定义一个类型别名 Node，表示链表节点类型 list_node<T>，这样代码更简洁。
Node* _node; // 声明一个指针 _node，用于指向当前迭代器指向的节点。
// 构造函数，用于初始化迭代器，传入一个节点指针 node，并将其赋值给 _node。
// 该迭代器将用于遍历链表中的节点。
__list_iterator(Node* node)
: _node(node) // 将节点指针赋值给 _node
{ }
// 重载解引用操作符 `*`，使迭代器可以直接访问它当前指向的节点的数据。
// 返回当前节点存储的数据（类型为 T）。
T& operator*()
{
return _node->_data; // 返回当前节点（_node）中存储的数据。
}
// 前置递增操作符（`++`），用于将迭代器移动到链表中的下一个节点
__list_iterator<T>& operator++()
{
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return *this; // 返回更新后的迭代器对象，以支持链式调用
}
// 后置递增操作符（`++(int)`），用于将迭代器移动到下一个节点，但返回递增前的迭代器
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this); // 复制当前迭代器到临时迭代器 tmp
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return tmp; // 返回递增前的临时迭代器副本（即递增前的状态）
}
// 重载不等于操作符 `!=`，用于判断当前迭代器与另一个迭代器是否指向不同的节点。
// 当两个迭代器指向不同节点时返回 `true`，否则返回 `false`。
bool operator!=(const __list_iterator<T>& it) const
{
return _node != it._node; // 比较当前迭代器的节点指针 `_node` 与另一个迭代器 `it` 的 `_node` 是否相等
}
};
.在
list类中定义begin和end函数： 为了使std::list能像其他容器一样支持迭代器的遍历，我们实现了begin()和end()函数。begin()函数返回指向头节点下一个节点的迭代器，因为头节点本身不存储有效数据。end()函数返回指向链表中最后一个有效数据节点的下一个节点的迭代器，即指向头节点的位置，形成一个循环链表结构。这样，begin()和end()函数提供了获取链表起始和结束位置的方式，支持标准的迭代器操作。
四、迭代器的延伸
1.const_iterator迭代器
- 在 C++ 中，
const_iterator是专门用来遍历const对象的，它确保你不能修改遍历的内容。普通的iterator允许你修改数据。如果把const修饰符加到普通的迭代器上，就会阻止修改节点内容，但它也会导致一些功能失效，比如不能移动到下一个元素。所以我们不能对普通迭代器使用const。对于
const对象调用的const_iterator迭代器，我们不能使用const修饰普通迭代器（iterator<T>）。
- 为了保持迭代器的正常功能（比如能修改数据、能移动到下一个节点），我们不应该把
const修饰符加到普通迭代器上。否则，它会限制迭代器的行为，导致一些功能无法正常工作。因此，不能直接对普通迭代器进行
const修饰，以避免破坏迭代器的基本行为。
- 为了让迭代器可以在不同情况下（比如只读或可读写）进行工作，我们可以给迭代器类模板添加一个额外的参数
Ref。这个参数可以帮助我们控制是返回数据的常量引用（不能修改）还是普通引用（可以修改）。通过这种方式，我们就能在需要时区分const_iterator和普通的可修改迭代器。为了更好地控制
const_iterator和普通迭代器的行为，我们可以在迭代器类模板中引入一个额外的模板参数Ref。
template<class T, class Ref>
struct __list_iterator
{
typedef list_node<T> Node; // 定义一个类型别名 Node，表示链表节点类型 list_node<T>，这样代码更简洁。
Node* _node; // 声明一个指针 _node，用于指向当前迭代器指向的节点。
typedef __list_iterator<T, Ref> self;
// 构造函数，用于初始化迭代器，传入一个节点指针 node，并将其赋值给 _node。
__list_iterator(Node* node)
: _node(node) // 将节点指针赋值给 _node
{}
// 重载解引用操作符 `*`，使迭代器可以直接访问它当前指向的节点的数据。
// `Ref` 的类型是根据迭代器类型来决定的：
// - 对于普通迭代器 (`iterator`)，`Ref` 为 `T&`，返回可修改的引用。
// - 对于常量迭代器 (`const_iterator`)，`Ref` 为 `const T&`，返回不可修改的引用。
Ref operator*()
{
return _node->_data; // 返回当前节点（_node）中存储的数据（可修改或不可修改，取决于迭代器类型）。
}
// 前置递增操作符（`++`），用于将迭代器移动到链表中的下一个节点
self operator++()
{
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return *this; // 返回更新后的迭代器对象，以支持链式调用
}
// 后置递增操作符（`++(int)`），用于将迭代器移动到下一个节点，但返回递增前的迭代器
slef operator++(int)
{
__list_iterator<T> tmp(*this); // 复制当前迭代器到临时迭代器 tmp
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return tmp; // 返回递增前的临时迭代器副本（即递增前的状态）
}
// 重载不等于操作符 `!=`，用于判断当前迭代器与另一个迭代器是否指向不同的节点。
bool operator!=(const self& it) const
{
return _node != it._node; // 比较当前迭代器的节点指针 `_node` 与另一个迭代器 `it` 的 `_node` 是否相等
}
};
- 为什么
operator*()使用Ref参数？
operator*()是用来访问迭代器当前指向的节点的数据的。在迭代器中，operator*()的返回值表示 对数据的访问，而这个数据的访问权限（可修改还是不可修改）取决于你正在使用的迭代器类型：
- 为什么
operator!=()使用self参数？
operator!=()用来判断 两个迭代器是否指向不同的节点。在这里，我们需要比较 当前迭代器指向的节点 和 另一个迭代器指向的节点 是否相同。self用于确保比较的是两个 相同类型的迭代器，无论它们是否指向常量数据。这样做的好处是，
operator!=()可以用于 任何类型的迭代器，不管是常量迭代器还是普通迭代器，它们的类型都一致，所以可以进行比较。注意：迭代器的重命名也应该对应进行修改
代码验证
#include"list.h"
namespace dh
{
void print(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it+1 << " ";
++it;
}
cout << endl;
}
void test01()
{
dh::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
print(lt1);
}
}
int main()
{
dh::test01();
return 0;
}
运行结果如下：
2. ->运算符重载
假设我们有一个结构体：
struct A
{
int _a;
double _b;
};
如果链表中存储的是 A 对象，那么我们用迭代器访问时：
*it // 拿到 A 对象
(*it)._a // 访问成员
写起来比较麻烦。
理想情况是这样：
it->_a // 直接访问成员
此时我们就需要it->_a 直接访问成员
📌 核心原理
- 迭代器内部保存的是 Node*，节点里有 _data，即存储的 T 对象。
- 如果我们在迭代器里重载 operator->，返回 _node->_data 的地址（T* 或 const T*），就能支持 it->_a 这种写法。
- 注意：普通迭代器返回 T*，const_iterator 返回 const T*，所以要额外加一个模板参数 Ptr 来控制。
template<class T, class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> Node; // 定义一个类型别名 Node，表示链表节点类型 list_node<T>
Node* _node; // 声明一个指针 _node，用于指向当前迭代器指向的节点。
typedef __list_iterator<T, Ref,Ptr> self;
// 构造函数，用于初始化迭代器，传入一个节点指针 node，并将其赋值给 _node。
__list_iterator(Node* node)
: _node(node) // 将节点指针赋值给 _node
{}
// 重载解引用操作符 `*`，使迭代器可以直接访问它当前指向的节点的数据。
// `Ref` 的类型是根据迭代器类型来决定的：
// - 对于普通迭代器 (`iterator`)，`Ref` 为 `T&`，返回可修改的引用。
// - 对于常量迭代器 (`const_iterator`)，`Ref` 为 `const T&`，返回不可修改的引用。
Ref operator*() const
{
return _node->_data; // 返回当前节点（_node）中存储的数据（可修改或不可修改，取决于迭代器类型）。
}
// 前置递增操作符（`++`），用于将迭代器移动到链表中的下一个节点
self& operator++()
{
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return *this; // 返回更新后的迭代器对象，以支持链式调用
}
// 后置递增操作符（`++(int)`），用于将迭代器移动到下一个节点，但返回递增前的迭代器
self operator++(int)
{
self tmp(*this); // 复制当前迭代器到临时迭代器 tmp
_node = _node->_next; // 将当前迭代器的 _node 指针移动到下一个节点
return tmp; // 返回递增前的临时迭代器副本（即递增前的状态）
}
Ptr operator->() const
{
return &(_node->_data);//取结构体对象的地址进行返回，即返回结构体对象的指针
}
// 重载不等于操作符 `!=`，用于判断当前迭代器与另一个迭代器是否指向不同的节点。
bool operator!=(const self& it) const
{
return _node != it._node; // 比较当前迭代器的节点指针 `_node` 与另一个迭代器 `it` 的 `_node` 是否相等
}
};
也要记得修改list中的重命名
测试：
#include"list.h"
namespace dh
{
void test02()
{
struct A
{
A(int a = 0, int b = 0)
:_a(a)
, _b(b)
{}
int _a;
int _b;
};
list<A> lt1;
lt1.push_back(A(1, 1));
lt1.push_back(A(2, 2));
lt1.push_back(A(3, 3));
lt1.push_back(A(4, 4));
list<A>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << (*it)._a << ' ' << (*it)._b << endl;
it++;
}
cout << endl;
it = lt1.begin(); // 重置迭代器
while (it != lt1.end())
{
cout << it->_a << ' ' << it->_b << endl;
it++;
}
cout << endl;
it = lt1.begin(); // 重置迭代器
while (it != lt1.end())
{
cout << it.operator->()->_a << ' ' << it.operator->()->_b << endl;
it++;
}
cout << endl;
}
}
int main()
{
//dh::test01();
dh::test02();
return 0;
}
正常来说，我们在迭代器里重载了
->运算符，它返回的是结构体对象的指针。照理讲，如果想访问结构体的成员变量，应该写成lt->->_a才对，也就是“先通过迭代器的->得到指针，再通过这个指针访问成员”。但是在实际写代码时，我们直接用lt->_a就能访问成员变量，看起来好像少写了一个->。这是因为编译器在背后帮我们做了优化：当你调用迭代器的->时，编译器会自动再补上一次->，等价于(*lt).成员变量，所以最终能直接访问到结构体的成员。
3.迭代器的拷贝构造
有时候我们只想写个普通对象，编译器会根据返回类型去匹配最合适的函数。比如
lt.begin()返回的是 普通迭代器，而我们想用const_iterator去接收：
结果编译器直接报错，说两者类型对不上。原因很简单：
lt.begin()给的是一个普通迭代器对象；it想要的是一个const_iterator；- 默认情况下，编译器生成的 拷贝构造函数 只能在 同类型之间 拷贝。
所以这里就算我们用了
=，编译器也没办法把一个普通迭代器“拷贝”成一个const_iterator。
那我们要怎么办？答案是：手写一个拷贝构造函数，让 const 迭代器能接收普通迭代器。
- 我们要做的只是把普通迭代器里保存的“节点指针”拿过来。
- 因为我们不会修改被拷贝对象，所以参数写成
const iterator&。- 用初始化列表，把指针浅拷贝过来就行（不用深拷贝，因为迭代器本质就是个“指针封装”，不会涉及释放两次的问题）。
- 为了书写方便，我们通常会
typedef普通迭代器为iterator，然后就能轻松实现转换。
// 普通迭代器
typedef __list_iterator<T, T&, T*> iterator;
// const迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;
class __list_iterator
{
// ... 省略其它实现 ...
public:
// const_iterator 的拷贝构造，接收普通 iterator
__list_iterator(const iterator& it)
: _node(it._node)
{}
};
五、相关函数
insert
根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur之间的双向关系，最后建立新结点与prev之间的双向关系。
void insert(iterator pos, const T& val)
{
// 1. 获取当前迭代器 pos 对应的节点指针
Node* cur = pos._node;
// 2. 创建一个新节点，存放要插入的值 val
Node* newnode = new Node(val);
// 3. 找到 cur 的前驱节点
Node* prev = cur->_prev;
// 4. 前驱节点的 next 指针指向新节点
prev->_next = newnode;
// 5. 新节点的 next 指针指向当前节点
newnode->_next = cur;
// 6. 当前节点的 prev 指针指向新节点
cur->_prev = newnode;
// 7. 新节点的 prev 指针指回前驱节点
newnode->_prev = prev;
}
erase
根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系
iterator erase(iterator pos)
{
// 1. 获取当前要删除位置对应的节点指针
Node* cur = pos._node;
// 2. 保存当前节点的前驱节点
Node* prev = cur->_prev;
// 3. 保存当前节点的后继节点
Node* next = cur->_next;
// 4. 前驱节点的 next 指针直接指向后继节点
prev->_next = next;
// 5. 后继节点的 prev 指针直接指回前驱节点
next->_prev = prev;
// 6. 释放当前节点，回收内存
delete cur;
// 7. 返回一个指向删除位置“后一个元素”的迭代器
return iterator(next);
}
push_back 和 pop_back
- push_back和pop_back函数分别用于list的尾插和尾删，在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数。
- push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(end());
}
push_front 和 pop_front
当然，用于头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
拷贝构造
拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，我们先申请一个哨兵节点占位，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。
list(const list<T>& lt)
{
// 1. 创建一个新的哨兵节点（环形双向链表的核心）
sentinel = new node;
// 2. 初始化哨兵节点：让它的前后指针都指向自己
// 此时链表为空，但已经形成一个环
sentinel->_next = sentinel;
sentinel->_prev = sentinel;
// 3. 遍历传入的 lt 链表，把里面的元素依次插入到当前链表的尾部
for (const auto& e : lt)
{
push_back(e);
}
}
size
size函数用于获取当前容器当中的有效数据个数，因为list是链表，所以只能通过遍历的方式逐个统计有效数据的个数。
size_t size() const
{
size_t sz = 0; // 1. 定义计数器 sz，初始为 0
const_iterator it = begin(); // 2. 从链表的起始位置（第一个元素）开始遍历
while (it != end()) // 3. 遍历直到到达尾后迭代器 end()
{
++sz; // 4. 每经过一个元素，计数器 +1
++it; // 5. 迭代器向后移动
}
return sz; // 6. 返回最终计数结果
}
swap
swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换
void swap(list<T>& lt)
{
::swap(sentinel, lt._head); //交换两个容器当中的头指针即可
}
clear
clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。
void clear()
{
// 1. 从第一个有效元素开始
iterator cur = begin();
// 2. 遍历整个链表，依次删除每个节点
while (cur != end())
{
// erase 会返回 "被删节点的下一个位置"
// 所以这里直接用返回值更新 cur，继续循环
cur = erase(cur);
}
// 3. 所有节点删完后，元素个数置 0
_size = 0;
}
resize
具体规则：
- 如果当前
size < n
- 说明元素不够，需要在链表尾部不断插入新节点（通常填充默认值
T()），直到元素个数达到n。
- 如果当前
size > n
- 说明元素太多，需要删除多余的元素，只保留前
n个。
为什么不能直接调用
size()？
size()是通过遍历来统计链表长度的，时间复杂度 O(n)。- 如果
size > n，你还得再遍历一遍链表找到第n个节点并删除后续节点，就相当于 重复遍历两次，效率不高。
高效实现方法:
- 定义一个计数器
len = 0，用于记录当前已遍历的节点个数。- 从头开始遍历链表：
- 当
len >= n时，说明已经到达第n个节点，此时直接把后续所有节点释放掉。- 当链表遍历完毕 时，说明原来链表的长度小于
n，此时需要在尾部不断插入新节点，直到长度补齐到n。
void resize(size_t n, const T& val = T())
{
// 1. 获取第一个有效元素的迭代器
iterator i = begin();
// 2. len 用于记录当前已经遍历的有效元素个数
size_t len = 0;
// 3. 遍历链表，直到走到第 n 个元素，或者到达 end()
while (len < n && i != end())
{
++len; // 统计一个元素
++i; // 迭代器后移
}
// 4. 如果遍历结束时 len == n
// → 说明链表长度 >= n，需要删掉多余元素
if (len == n)
{
// 从第 n 个元素开始，一直删到链表尾
while (i != end())
{
i = erase(i); // erase 返回的是下一个有效元素的位置
}
}
else
{
// 5. 如果 len < n
// → 说明链表长度不足，需要尾插元素直到长度为 n
while (len < n)
{
push_back(val); // 尾插一个默认值 val
++len;
}
}
}
📢 如果你也喜欢这种“不呆头”的技术风格：
👁️ 【关注】 看一个非典型程序员如何用野路子解决正经问题
👍 【点赞】 给“不写八股文”的技术分享一点鼓励
🔖 【收藏】 把这些“奇怪但有用”的代码技巧打包带走
💬 【评论】 来聊聊——你遇到过最“呆头”的 Bug 是啥？
🗳️ 【投票】 您的投票是支持我前行的动力
技术没有标准答案，让我们一起用最有趣的方式，写出最靠谱的代码！ 🎮💻