content_views" class="htmledit_views">

前言

上一节我们讲解了list的基本功能࿰c;那么本节我们就结合底层代码来分析list是怎么实现的࿰c;那么废话不多说࿰c;我们正式进入今天的学习：）

c="https://i-blog.csdnimg.cn/direct/a795d2d7bddd4f82a7870cee0cd9a100.png" width="515" />

List的底层结构

我们先来看一下list的底层基本结构：

ckquote>

c="https://i-blog.csdnimg.cn/direct/857717053d484ac7b067213617f20bd1.png" width="1460" />

ckquote>

这里比较奇怪的一点是底层选择了void*来表示链表的指针࿰c;其实可以不用这么做

接下来是迭代器部分：

ckquote>

c="https://i-blog.csdnimg.cn/direct/51078ed406e7454aa2226ac1a8b106e3.png" width="1942" />

ckquote>

模拟实现链表难就难在实现迭代器࿰c;因为链表的color:#fe2c24">物理空间不是连续的࿰c;所以color:#fe2c24">不能简单的通过typedef一个指针变量来达到实现迭代器的目的

链表为空的初始化：

ckquote>

c="https://i-blog.csdnimg.cn/direct/0e53797570e140ebbff3ce5fa48e689e.png" width="1392" />

ckquote>

链表为空时不是简单的把所有的指针都赋空指针࿰c;而是color:#fe2c24">创建一个节点࿰c;让这个节点的next和prev指针都指向自己。这就是创造了一个头节点࿰c;这里涉及到数据结构阶段color:#fe2c24">双向带头链表的基本知识

c="https://i-blog.csdnimg.cn/direct/eb47a0d5ea9349f5a54c2ba8dc8de2c4.png" width="1914" />

get_node是申请节点࿰c;调用了内存池࿰c;由于我们还没有学习内存池࿰c;所以可以简单地将这里理解为malloc

下面是源代码中的头插尾插接口：

ckquote>

c="https://i-blog.csdnimg.cn/direct/97d22c2312504c5fae4e6a1ada9e0cf2.png" width="1836" />

ckquote>

通过这些࿰c;我们可以知道࿰c;单纯实现链表的功能是没有什么难度的࿰c;和我们之前实现string和vector差不多࿰c;难就难在理解迭代器的实现

既然底层结构已经看的差不多了࿰c;那我们现在就来实现一下list吧

List的模拟实现

节点的基本结构

首先要实现链表的基本结构࿰c;链表的基本结构是color:#fe2c24">节点：

<code class="language-cpp">	template<class T>struct list_node{list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}T _data;list_node<T>* _next;list_node<T>* _prev;};code>

链表的借本结构

构造函数 

先来实现一下构造函数࿰c;根据底层是color:#fe2c24">双向带头循环链表࿰c;写出代码如下：

<code class="language-cpp">	template<class T>class list{public:typedef list_node<T> Node;list(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}private:Node* _head;size_t _size;};code>

 size和empty函数

实现size和empty函数࿰c;由于代码很简单࿰c;就不做讲解了：

<code class="language-cpp">		size_t size(){return _size;}bool empty(){return _size == 0;}code>

迭代器

因为不是每一个STL的容器都是存储在连续的物理空间之中࿰c;所以并不是每一个容器都支持下标+[]访问࿰c;但是color:#fe2c24">所有的容器都有迭代器࿰c;都支持范围for࿰c;因此实现迭代器是很重要的一个步骤࿰c;我们来逐步分析迭代器的实现：

我们知道࿰c;对于一个节点而言࿰c;*解引用以后找到的不是节点的值࿰c;而是节点的地址；因为存储空间不连续࿰c;不能通过++来找到下一个节点࿰c;所以就不能仅通过typedef来实现迭代器࿰c;此时我们就应该考虑color:#fe2c24">封装+运算符重载来实现迭代器࿰c;主要内容就是重载 *  ++    != 等࿰c;让其满足与其他迭代器相同的作用

<code class="language-cpp">	template<class T>struct list_iterator{Node* _node;};code>

迭代器的构造函数

---

<code class="language-cpp">		list_iterator(Node* node):_node(node){}code>

重载*

<code class="language-cpp">		T& operator*(){return _node->_data;}code>

重载前置++、--

由于color:#fe2c24">++以后返回的数据类型依旧是迭代器࿰c;为了书写简便一点࿰c;调用typedef：

<code class="language-cpp">		Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}code>

重载后置++、-- 

因为后置++和--是将当前的值使用以后再执行++或者--࿰c;所以我们需要把原本的值拷贝一份࿰c;用于完成返回操作：

<code class="language-cpp">		Self& operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}code>

重载!=、==

<code class="language-cpp">		bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}code>

重载-> 

先来分析一下为什么需要重载->这个符号：

接下来先构造一个使用->的情景：

假设有一个这样的结构体：

<code class="language-cpp">	struct AA{int _aa1 = 1;int _aa2 = 2;};code>

此时我们要在链表中存入这个结构体并且打印：

<code class="language-cpp">		list<AA> ltaa;ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << *itaa << " ";++itaa;}cout << endl;code>

c="https://i-blog.csdnimg.cn/direct/22772951a16d41aca73498628fa0af76.png" width="2074" />

此时运行以后发现编译不通过

这里面的itaa通过解引用会得到节点中的data࿰c;data的数据类型是T࿰c;也就是自定义类型AA。因为没有重载流插入࿰c;所以这里的自定义类型无法打印࿰c;要想解决这个问题有两种方法：

第一种方法：给AA重载流插入

第二种方法：逐一访问结构体中的元素

<code class="language-cpp">		list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << (*itaa)._aa1 << " and " << (*itaa)._aa2 << endl;++itaa;}cout << endl;code>

c="https://i-blog.csdnimg.cn/direct/0d08d53fa2874b929e8415ddff216838.png" width="2316" />

此时代码就成功运行了

但是这样写就很麻烦࿰c;此时就可以重载->这个运算符࿰c;这里先把代码写出来再对其进行分析：

<code class="language-cpp">		T* operator->(){return &_node->_data;}code>

<code class="language-cpp">		list<AA>::iterator itaa = ltaa.begin();while (itaa != ltaa.end()){cout << itaa->_aa1 << " and " << itaa->_aa2 << endl;++itaa;}cout << endl;code>

c="https://i-blog.csdnimg.cn/direct/87a9c78860084f24bc6a5b9953f3bdef.png" width="2261" />

---

疑难解答：为什么operator-> 操作符重载函数返回值 T* 而不是 T&

在 list_iterator 这个迭代器类模板中࿰c;operator-> 操作符重载函数设计为返回 T* 而不是 T&࿰c;这与 operator-> 操作符的特殊语义和 C++ 语言的规定有关：

在 C++ 中࿰c;operator-> 操作符有特殊的处理规则。当我们使用 -> 操作符时࿰c;编译器会尝试不断应用 -> 操作࿰c;直到得到一个color:#fe2c24">非指针类型的对象

简单地说就是：当你使用迭代器 it 调用 it->member 时࿰c;编译器会先调用 it.operator->()࿰c;如果 operator->() 返回的是一个指针࿰c;那么就直接访问该指针指向对象的成员；color:#fe2c24">如果返回的不是指针࿰c;编译器会再次对返回值应用 ->

我们可以分两点来说明返回 T* 的合理性：

1. 符合使用习惯

迭代器的 operator-> 操作符通常用于模拟指针的行为࿰c;返回 T* 可以让迭代器像指针一样使用

例如࿰c;对于一个存储自定义类型 MyClass 的链表࿰c;使用迭代器访问 MyClass 的成员时࿰c;我们希望能够像使用指针一样直接通过 -> 操作符访问成员࿰c;如下所示：

<code class="language-cpp">namespace xiaobai
{template<class T>struct list_node{list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr) {}T _data;list_node<T>* _next;list_node<T>* _prev;};template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node) : _node(node){}T& operator*() {return _node->_data;}Self& operator++() {_node = _node->_next;return *this;}bool operator!=(const Self& s) {return _node != s._node;}T* operator->() {return &_node->_data;}Node* _node;};
}int main() 
{xiaobai::list_node<MyClass> node(MyClass(10));xiaobai::list_iterator<MyClass> it(&node);// 使用迭代器的 -> 操作符访问成员std::cout << it->value << std::endl;return 0;
}code>

在这个例子中࿰c;it->value 能够正常工作࿰c;color:#fe2c24">因为 operator->() 返回的是 MyClass* 类型的指针࿰c;编译器可以直接通过该指针访问 value 成员

2. 避免额外的复杂度

如果 operator->() 返回 T&࿰c;编译器会再次对返回的引用应用 -> 操作࿰c;这会导致代码逻辑变得复杂࿰c;而且可能不符合用户的预期

例如：若T是一个自定义类型࿰c;由于T&不是指针类型࿰c;color:#fe2c24">编译器会尝试调用 T 类型的 operator->() 函数࿰c;这可能会引发编译错误或意外的行为

所以T* operator->() 是为了让迭代器能够像指针一样使用࿰c;符合用户的使用习惯࿰c;并且遵循了 C++ 中 operator-> 操作符的特殊语义。而 T& operator->() 会破坏这种语义࿰c;导致代码color:#fe2c24">逻辑复杂且不符合预期࿰c;因此通常不这样设计

---

这段代码初步看起来会很奇怪࿰c;它这里color:#fe2c24">实际应该是两个箭头࿰c;但是为了可读性省略了一个箭头

（具体细节请浏览上面的疑难解答） 

<code class="language-cpp">cout << itaa.operator->()->_aa1 << " and " << itaa.operator->()->_aa2 << endl;code>

第一个箭头是color:#fe2c24">运算符重载࿰c;返回的是color:#fe2c24">AA*类型的变量

第二个箭头是color:#fe2c24">原生指针࿰c;通过这个箭头就可以访问到list中的数据了

 迭代器代码初步集合

到这里我们就完成了迭代器：

<code class="language-cpp">	template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node):_node(node){}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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}T* operator->(){return &_node->_data;}Node* _node;};code>

此时再去链表的类中typedef迭代器࿰c;简化书写：

<code class="language-cpp">	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T> iterator;//.......private:Node* _head;size_t _size;};code>

---

重载打印容器以及对迭代器的修缮

实现了迭代器࿰c;就color:#fe2c24">满足了范围for遍历࿰c;此时就可以写一个访问容器的接口࿰c;因为所有容器都具有迭代器࿰c;所以这个接口也可以访问其他STL容器

<code class="language-cpp">	template<class Container>void print_container(const Container& con){for (auto e : con){cout << e << " ";}cout << endl;}code>

现在测试一下这个打印：

<code class="language-cpp">		list<int> lt;ltaa.push_back(1);ltaa.push_back(2);ltaa.push_back(3);ltaa.push_back(4);print_container(lt);code>

此时运行代码却发现编译报错了࿰c;为什么函数外面使用范围for可以打印࿰c;但是print_container函数里面使用范围for却打印不了࿰c;这是为什么呢？

因为函数里面的color:#fe2c24">参数是const参数࿰c;函数外面是普通的参数࿰c;我们还color:#fe2c24">没有实现const迭代器࿰c;所以这里就会报错

再来分析一下const迭代器的特征：先思考一下const迭代器为什么是const_iterator而color:#fe2c24">不是普通的iterator加上前置的const修饰?

要想想清楚这个问题࿰c;我们首先需要明白color:#fe2c24">const迭代器是自身不能修改还是指向的内容不能修改。这里我们结合指针不同位置的const意义来理解：

<code class="language-cpp">T* const ptr;
const T* ptr;code>

第一种：color:#fe2c24">指针本身不允许改变

第二种：color:#fe2c24">指针指向的内容不允许改变

很明显的࿰c;const迭代器是想完成第二种功能࿰c;如果是const iterator的话࿰c;const的作用是color:#fe2c24">确保iterator本身不被修改࿰c;color:#fe2c24">迭代器本身不能修改的话就无法实现遍历。const迭代器的产生是为了在color:#fe2c24">保证遍历的前提之下保证迭代器指向的内容也不被修改

那么该怎么修改代码来完成这一目的呢？

我们在实现迭代器这一个类时࿰c;对数据的修改接口是operator*以及operator->࿰c;对于const迭代器而言࿰c;返回类型就应该加上const：

<code class="language-cpp">		const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}code>

所以这里就需要color:#fe2c24">拷贝之前的普通迭代器代码࿰c;再在*和->的重载中加上const完成const迭代器

<code class="language-cpp">	template<class T>struct list_const_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;list_iterator(Node* node):_node(node){}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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}const T* operator->(){return &_node->_data;}Node* _node;};code>

此时在color:#fe2c24">重载一下begin和end函数࿰c;给一个const迭代器版本࿰c;并且在list类中typedef const迭代器：

（普通迭代器可以调用const迭代器的begin和end࿰c;因为color:#fe2c24">权限可以缩小；反之const迭代器无法调用普通迭代器的begin和end࿰c;因为color:#fe2c24">权限不能放大）

<code class="language-cpp">	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}//........private:Node* _head;size_t _size;};
code>

color:#ff9900">**************************************************************************************************************

在 list 类中重载 `begin` 和 `end` 函数（即提供 `const` 和非 `const` 版本）是为了支持对 `const` 对象和非 `const` 对象的迭代操作࿰c;下面详细解释原因：

1. 支持非 `const` 对象的迭代

当你有一个非 `const` 的 `list` 对象时࿰c;你可能希望能够修改列表中的元素。此时࿰c;你需要使用非 `const` 迭代器࿰c;因为非 `const` 迭代器color:#fe2c24">允许对其所指向的元素进行修改。非 `const` 版本的 `begin` 和 `end` 函数返回的就是非 `const` 迭代器

2. 支持 `const` 对象的迭代

当你有一个 `const` 的 `list` 对象时࿰c;你color:#fe2c24">不应该修改列表中的元素࿰c;因为这违反了 `const` 限定的语义。此时࿰c;你需要使用 `const` 迭代器࿰c;`const` 迭代器color:#fe2c24">只能用于访问元素࿰c;而不能修改元素。`const` 版本的 `begin` 和 `end` 函数返回的就是 `const` 迭代器

3. 函数重载的实现

通过函数重载࿰c;编译器会根据对象是否为 `const` 来选择合适的 `begin` 和 `end` 函数版本。如果对象是 `const` 的࿰c;编译器会调用 `const` 版本的 `begin` 和 `end` 函数࿰c;返回 `const` 迭代器；如果对象是非 `const` 的࿰c;编译器会调用非 `const` 版本的 `begin` 和 `end` 函数࿰c;返回非 `const` 迭代器。

重载 `begin` 和 `end` 函数是为了提供对 `const` 对象和非 `const` 对象的一致迭代接口࿰c;同时保证 `const` 对象的元素不被意外修改࿰c;遵循了 C++ 的 `const` 正确性原则࿰c;使得代码更加安全和灵活。

color:#ff9900">**************************************************************************************************************

 此时用一个color:#ffd900">很特别的用例来测试一下代码（这里修改了一下print_container函数）：

<code class="language-cpp">	template<class Container>void print_container(const Container& con){list<int>::const_iterator it = con.begin();while(it != con.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl;}void test_list01(){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;}code>

c="https://i-blog.csdnimg.cn/direct/fa9c9491444b446cba60a456efd52efe.png" width="1635" />

可以看到࿰c;这里非常奇怪࿰c;明明我们color:#ff9900">故意在打印容器代码里面修改了const迭代器指向的内容࿰c;想让它报错࿰c;但是代码却成功运行了࿰c;这是为什么呢？

这就涉及到我们之前提及的color:#fe2c24">按需实例化࿰c;这里的代码color:#fe2c24">存在着编译错误࿰c;' *it += 10 ' 中的*it返回的数据类型应该是const T&࿰c;对其进行+=10操作本身是应该编译报错的࿰c;但是这里非但没有报错反而还运行成功了

之所以产生这样的结果࿰c;是因为color:#fe2c24">模板和类模板都会走按需实例化。模板不能被直接调用࿰c;模板用于将对应类型的代码实例化出来࿰c;实例化出来的代码才能够使用

因为我们在主函数中没有使用print_container函数࿰c;color:#fe2c24">编译器在编译的过程中就不会去实例化print_container函数里面的内容࿰c;而没有实例化的代码编译器color:#fe2c24">只会对其进行很简单的语法检查࿰c;比如：语句结束没加分号࿰c;对于细枝末节的操作编译器不会检查。

此时如果color:#fe2c24">使用print_container函数就会报错：

<code class="language-cpp">        list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;print_container(lt);code>

c="https://i-blog.csdnimg.cn/direct/59b9c0c2ee99405f82f999fee6ceaa01.png" width="2078" />

对迭代器代码的简化

刚才那种实现方式我们的确能成功的完成任务࿰c;但是const迭代器和普通迭代器除了operator*和->的代码有区别以外࿰c;其他地方的代码一模一样࿰c;这么设计的话在代码长度上就会非常的冗余࿰c;我们去底层观察一下是怎么实现迭代器的：

ckquote>

c="https://i-blog.csdnimg.cn/direct/100c29c72fbb42e3a52b0955f19abae8.png" width="1702" />

c="https://i-blog.csdnimg.cn/direct/72e84a4106734c318e45e8aa818d97af.png" width="1586" />

c="https://i-blog.csdnimg.cn/direct/0bdc213b092d4d4eaf40934844a90512.png" width="1344" />

c="https://i-blog.csdnimg.cn/direct/a138058787484d0185000b4079a8eb76.png" width="1438" />

ckquote>

可以看到࿰c;它没有将迭代器和const迭代器定义为两个类࿰c;而是同一个类模板。而且它除了传入了 T ࿰c;color:#fe2c24">还传入了 T& 和 T* 这两个参数

如果是普通迭代器࿰c;它的中的参数是color:#fe2c24"> T T& T* ࿰c;分别传给了参数 color:#fe2c24">T Ref Ptr ࿰c;而 Ref 和 Ptr 分别被重命名为 reference 和 pointer ࿰c;而 reference 和 pointer 分别又color:#fe2c24">是 operator* 和 operator-> 的返回值；

如果是const迭代器࿰c;它的中的参数是 T 、color:#fe2c24">const T&、 const T* ࿰c;分别传给了参数 T Ref Ptr ࿰c; Ref 和 Ptr 分别被重命名为 reference 和 pointer ࿰c;而 reference 和 pointer 分别又color:#fe2c24">是 operator* 和 operator-> 的返回值；

通过这种形式就控制住了operator*和->的返回值

虽然这两种写法在本质上没有区别࿰c;只是之前的写法是自己写了两个类࿰c;而这种方法是实现了一个类模板并且传了不同的模板参数给编译器࿰c;通过编译器来实例化出两个类。通过这样的方法࿰c;我们就可以color:#fe2c24">实现精简代码的需求

那么就根据底层实现的原理来完善一下原来的代码吧：

<code class="language-cpp">	template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//.......Node* _node;};
code>

<code class="language-cpp">	template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//.......private:Node* _head;size_t _size;};code>

 迭代器代码的最终整合

<code class="language-cpp">	template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;list_iterator(Node* node):_node(node){}Ref 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& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}Ptr operator->(){return &_node->_data;}Node* _node;};code>

---

begin、end函数

begin函数用于color:#fe2c24">返回链表第一个元素：

<code class="language-cpp">		iterator begin(){iterator it(_head->_next);return it;}code>

也可以用返回color:#fe2c24">匿名对象来简化代码：

<code class="language-cpp">			return iterator(_head->_next);code>

还有一种更加简单的写法：

<code class="language-cpp">			return _head->_next;code>

因为这里返回的是一个节点的指针࿰c;节点的指针是可以隐式类型转换成iterator的࿰c;color:#fe2c24">单参数的构造函数支持隐式类型的转换

---

end函数同理：

<code class="language-cpp">		iterator end(){return _head->_prev;}code>

---

到这里࿰c;我们来测试一下：

<code class="language-cpp">		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;code>

c="https://i-blog.csdnimg.cn/direct/b61a540d6a6841699adb6d3ead7fd419.png" width="1972" />

这里迭代器的设计相当完美࿰c;假设链表为空࿰c;此时就只有一个哨兵位的头节点。由于begin是_head的next࿰c;此时它指向的还是自己。end是_head࿰c;color:#fe2c24">也同样指向自己࿰c;此时it = begin() == endcolor:#fe2c24">在条件判断的时候就不会进入循环࿰c;造成非法访问

我们在实现迭代器的时候没有写拷贝构造函数࿰c;这就意味着指针在与指针的拷贝的时候进行的是浅拷贝࿰c;那么浅拷贝会不会出现问题呢？

答案是不会࿰c;我们就以上面的测试代码为例࿰c;我们给it赋了头节点࿰c;此时我们期望的就是it也指向原来的头节点࿰c;color:#fe2c24">就是需要浅拷贝࿰c;而不是开一个新的链表࿰c;指向新的链表中的头节点

这里的迭代器只是一个color:#fe2c24">访问和遍历链表的工具࿰c;它不像vector、string等容器一样࿰c;它所指向的资源并不是属于它自己的࿰c;它指向的资源是属于list的。所以它也不要写析构函数࿰c;它不能去释放list的空间

---

insert函数

insert函数用于在pos位置之前插入数据࿰c;要想实现这个功能还是比较简单的࿰c;仅需要通过简单的修改指针指向即可：

<code class="language-cpp">		void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;}code>

---

push_back和push_front函数

可以通过color:#fe2c24">复用insert函数完成这两个函数：

<code class="language-cpp">		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}code>

---

erase函数

erase函数用于color:#fe2c24">删除pos位置的节点࿰c;这个函数的实现也很简单࿰c;也是只需要修改指针指向再释放节点即可：

注意erase不能删除哨兵位的头节点࿰c;在这里加上assert断言

<code class="language-cpp">		void erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;}code>

---

pop_back和pop_front函数

通过color:#fe2c24">复用erase即可实现这两个函数：

<code class="language-cpp">		void pop_back(iterator pos){erase(--end());}void pop_front(iterator pos){erase(begin());}code>

结尾

因为链表很多接口的实现非常简单࿰c;这里就没有把所有接口的实现代码一一列举出来了࿰c;下一节我们接着分析链表࿰c;我们将会分析迭代器失效并且完善list。那么本节的内容就到此结束了࿰c;谢谢您的浏览！！！！！！！！！

c="https://i-blog.csdnimg.cn/direct/7d4abdba29234498a817a623b7fafec5.png" width="300" />