List的模拟实现（2）

news/2025/2/26 2:28:52
cle class="baidu_pl">
cle_content" class="article_content clearfix">
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的模拟实现

ckground-color:transparent">节点的基本结构

首先要实现链表的基本结构࿰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中的数据了

ckground-color:transparent"> 迭代器代码初步集合

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

<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>
ckground-color:transparent">重载打印容器以及对迭代器的修缮

实现了迭代器࿰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" />

ckground-color:transparent">对迭代器代码的简化

刚才那种实现方式我们的确能成功的完成任务࿰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>

ckground-color:transparent">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;我们将会分析迭代器失效。那么本节的内容就到此结束了࿰c;谢谢您的浏览！！！！！！！！！

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


http://www.niftyadmin.cn/n/5867086.html

相关文章

DeepSeek等LLM对网络安全行业的影响

DeepSeek等LLM对网络安全行业的影响

大家好，我是AI拉呱，一个专注于人工智领域与网络安全方面的博主，现任资深算法研究员一职，兼职硕士研究生导师；热爱机器学习和深度学习算法应用，深耕大语言模型微调、量化、私域部署。曾获多次获得AI竞赛大奖，拥有多项发明专利和学术论文。对于AI算法有自己独特见解和经验…
阅读更多...
开源嵌入式实时操作系统uC/OS-II介绍

开源嵌入式实时操作系统uC/OS-II介绍

一、uC/OS-II的诞生&#xff1a;从开源实验到行业标杆 背景与起源 uC/OS-II&#xff08;Micro-Controller Operating System Version II&#xff09;诞生于1992年&#xff0c;由嵌入式系统先驱Jean J. Labrosse开发。其前身uC/OS&#xff08;1991年&#xff09;最初作为教学工…
阅读更多...
Linux与自动化的基础

Linux与自动化的基础

Linux简介 Linux是一种开源的类Unix操作系统&#xff0c;广泛应用于服务器、桌面和嵌入式设备。常见的Linux发行版包括 Ubuntu、CentOS 和 Debian&#xff0c;它们各有特色&#xff0c;但都以稳定性和安全性著称。 与图形界面相比&#xff0c;Linux的**命令行界面&#xff08…
阅读更多...
【刷题】贪心算法

【刷题】贪心算法

贪心算法通常用于那些可以通过局部最优解达到全局最优解的问题&#xff0c;也就是说每一步都选择当前看起来最好的选项&#xff0c;从而希望最终的结果是最优的。 基础概念 [分配问题]&#xff1a;局部最优满足需求&#xff0c;排序后贪心分配 分发饼干 分发糖果 [区间问题]…
阅读更多...
Android 老项目 jcenter 库失效

Android 老项目 jcenter 库失效

最近重新维护了一些老项目发现大部分jcenter库失效了&#xff0c; Could not resolve com.xx:2.1.3. 如果你也遇到了&#xff0c;不妨试试 替换为 aliyun的jcenter服务&#xff0c;就不用一个个找代替库了。 project 下的 build.gradle 文件添加&#xff1a; maven { url htt…
阅读更多...
python爬虫——爬取全年天气数据并做可视化分析

python爬虫——爬取全年天气数据并做可视化分析

一、主题页面的结构与特征分析 1&#xff0e;主题页面的结构与特征分析 目标内容界面&#xff1a; 2. Htmls 页面解析 3&#xff0e;节点查找方法与遍历方法 查找方法&#xff1a;find(): 查找第一个匹配到的节点。find_all(): 查找所有匹配到的节点&#xff0c;并返回一个列…
阅读更多...
IRI 2016 模型在线版 MATLAB

IRI 2016 模型在线版 MATLAB

IRI官网&#xff1a;International Reference Ionosphere IRI-2016在线计算&#xff1a;IRI 2016 | CCMC 官方提供的MATLAB代码需要联网读取IRI网页数据&#xff1a; 下载需要注册账号&#xff0c;没有注册账号的自行注册&#xff0c;下载好后解压是这样的&#xff1a; 下载I…
阅读更多...
【Rust中级教程】2.8. API设计原则之灵活性(flexible) Pt.4：显式析构函数的问题及3种解决方案

【Rust中级教程】2.8. API设计原则之灵活性(flexible) Pt.4：显式析构函数的问题及3种解决方案

喜欢的话别忘了点赞、收藏加关注哦&#xff08;加关注即可阅读全文&#xff09;&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 说句题外话&#xff0c;这篇文章一共5721个字&#xff0c;是我截至目前写的最长的一篇文章&a…
阅读更多...
最新文章

Copyright @ 2022~2023