【C++】List模拟实现过程中值得注意的点

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

目录

前言

1.List迭代器

2.适配器

3.迭代器失效

4.模拟实现源码

前言

本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题，都是一些需要注意的细节问题，希望与大家共勉。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码：🌟fanfei_c的仓库🌟

=========================================================================

1.List迭代器

在之前模拟实现『 String和Vector』时，我们都采用的『 原生指针』实现迭代器，那么到List这里还可以么？

这我们就要搞清楚『 迭代器存在的意义』。

我们希望可以通过迭代器来实现对某一容器的遍历访问，例如对迭代器++或--；

迭代器：让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。

之前的String和Vector我们可以简单的利用原生指针实现迭代器是因为String和Vector底层的物理空间是连续的，所以++和--当然可以访问到对应的对象。

可到了List中，List的底层是带头双向循环链表，链表的物理空间并『 不连续』，所以我们需要对迭代器进行一定的『 封装』，让迭代器『 符合统一的迭代器使用规则』。

如何封装呢？

提示：比如重载各种运算符，++运算符的底层可以为链表的p=p->next；

注意：end迭代器是最后一个元素的下一个位置，所以end一般指向的是『 头节点』。 

  • 头节点不存储数据。

 

// List的节点类
template<class T>
struct ListNode
{
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;
    ListNode(const T& val = T())
        :_next(nullptr)
        , _prev(nullptr)
        , _data(val)
    {}
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class __list_iterator
{
public:
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> Self;
    Node* _node;
    __list_iterator(Node* x)
        :_node(x)
    {}

    Ref operator*()
    {
        return _node->_data;
    }
    Ptr 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;
    }
};

2.适配器

我们知道迭代器一般需要两个形式，一种为非const迭代器，一种为const迭代器用来满足不同的使用场景，但你有没有发现上面的代码，似乎只有一种形式？？？

其实并不是，如果我们按照以前的写法，应为：

//非const迭代器类
template<class T>
class __list_iterator
{
public:
    typedef ListNode<T> Node;
    typedef __list_iterator<T> Self;
    Node* _node;
    __list_iterator(Node* x)
        :_node(x)
    {}

    T& operator*()
    {
        return _node->_data;
    }
    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迭代器类
template<class T>
class __list_const_iterator
{
public:
	typedef ListNode<T> Node;
	typedef __list_const_iterator<T> self;
	Node* _node;
	__list_const_iterator(Node* x)
		:_node(x)
	{}

    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& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};

但这样看起来代码非常冗余，那么有没有什么方式来简化代码呢？

其实模板的用法不仅有vector<int>这类，还可以这么使用：

所以，编译器可以通过模板自动推演出当前使用场景为const迭代器还是非const迭代器。

这种方式可以唤作为『 适配器』，当然这部分后面还会有涉及。

3.迭代器失效

在之前学习vector时我们发现了迭代器失效的问题，对于vector来讲迭代器失效往往发生在扩容之后，那么对于List来讲，是不需要扩容的，那么List会不会发生迭代器失效的问题呢？

List可能会在『 erase』操作之后，迭代器失效。

我们来分析一下：

vector迭代器失效的原因是因为扩容导致迭代器使用前后底层指针位置发生了改变，换句话说就是开辟了新的空间，指针指向了新的地址，而迭代器没有更新从而导致迭代器失效。

而List并不会扩容，也不会开辟新的连续的空间，所以对于插入来说无从谈起迭代器失效，而erase是会导致迭代器失效的，因为删除了该位置的对象，迭代器底层指针成为野指针，但并不会影响其他迭代器，只需要重新赋值即可，比如设计为删除当前迭代器位置对象，并指向下一位置：

// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
    assert(pos != end());//list是带头双向循环链表，当pos是end()位置时，证明没有可删除的节点了

    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;

    delete cur;
    return next;
}

4.->操作符的重写

->操作符的重写是一个特例，大家只需要记住即可，因为这是STL设计者故意设计为这样的。

Ptr operator->()//为什么返回的是地址？？
{
    return &_node->_data;
}

那放在实际的场景中我们使用一下看看： 

struct AA
{
    int _a1;
    int _a2;

    AA(int a1 = 1, int a2 = 1)
        :_a1(a1)
        , _a2(a2)
    {}
};

void test_list5()
{
    list<AA> lt;
    AA aa1;
    lt.push_back(aa1);

    lt.push_back(AA());

    AA aa2(2, 2);
    lt.push_back(aa2);

    lt.push_back(AA(2, 2));

    list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << it->_a1 << ":" << it->_a2 << endl;
        //这里打印的是_a2的内容并不是_a2的地址
        ++it;
    }
    cout << endl;
}

正常来讲这里本来是应该有两个->的，第一个箭头是it->去调用重载的operator->返回AA* 的指针，第二个箭头是AA* 的指针去访问对象当中的成员变量_a2。

cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;//实际

但是为了程序可读性，所以编译器做了特殊识别处理，省略了一个箭头。 

5.模拟实现源码

#pragma once

#include<iostream>
#include<assert.h>

namespace F
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _data;
        ListNode(const T& val = T())
            :_next(nullptr)
            ,_prev(nullptr)
            ,_data(val)
        {}
    };


    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class __list_iterator
    {
    public:
        typedef ListNode<T> Node;
        typedef __list_iterator<T, Ref, Ptr> Self;
        Node* _node;
        __list_iterator(Node* x)
            :_node(x)
        {}

        Ref operator*()
        {
            return _node->_data;
        }
        Ptr 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;
        }
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
    public:
        ///
        // List的构造
        void empty_init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }
        list()
        {
            empty_init();
        }
        list(int n, const T& value = T())
        {
            empty_init();
            while (n--)
            {
                push_back(value);
            }
        }

        list(const list<T>& l)
        {
            empty_init();
            for (const auto& e : l)
            {
                push_back(e);
            }
        }
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }


        ///
        // List Iterator
        iterator begin()
        {
            return _head->_next;
        }
        iterator end()
        {
            return _head;
        }
        const_iterator begin() const
        {
            return _head->_next;
        }
        const_iterator end() const
        {
            return _head;
        }

        ///
        // List Capacity
        size_t size()const
        {
            size_t count = 0;
            const_iterator it = begin();
            while (it != end())
            {
                ++count;
                ++it;
            }
            return count;
        }
        bool empty()const
        {
            return _head->_next == _head;
        }


        
        // List Access
        T& front()
        {
            return *begin();
        }
        const T& front()const
        {
            return *begin();
        }
        T& back()
        {
            return *(--end());
        }
        const T& back()const
        {
            return *(--end());
        }


        
        // List Modify
        void push_back(const T& val) { insert(end(), val); }    
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(val);

            prev->_next = newnode;
            newnode->_next = cur;
            newnode->_prev = prev;
            cur->_prev = newnode;

            //return iterator(newnode);
            return newnode;//单参数的构造函数支持隐式类型转换
        }
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos != end());//list是带头双向循环链表，当pos是end()位置时，证明没有可删除的节点了

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;

            delete cur;
            return next;
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        void swap(list<T>& l)
        {
            std::swap(_head, l._head);
        }
    private:
        Node* _head;
    };
};

模拟实现的主要目的在于学习优秀的代码，比如这里适配器的使用、优秀的框架设计。

注意为了迭代器统一使用：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

这样我们就可以不需要知道迭代器的底层是如何实现的，只需要调用迭代器的接口就可以了，从而实现了通用的目的。

=========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/338085.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

AI对比：ChatGPT与文心一言的异同与未来

AI对比：ChatGPT与文心一言的异同与未来

文章目录 &#x1f4d1;前言一、ChatGPT和文心一言概述1.1 ChatGPT1.2 文心一言 二、ChatGPT和文心一言比较2.1 训练数据与知识储备2.2 语义理解与生成能力2.2 应用场景与商业化探索 三、未来展望3.1 模型规模与参数数量不断增加3.2 多模态交互成为主流3.3 知识图谱与大模型的结…
阅读更多...
Vue2移动端项目使用$router.go(-1)不生效问题记录

Vue2移动端项目使用$router.go(-1)不生效问题记录

目录 1、this.$router.go(-1) 改成 this.$router.back() 2、存储 from.path&#xff0c;使用 this.$router.push 3、hash模式中使用h5新增的onhashchange事件做hack处理 4、this.$router.go(-1) 之前添加一个 replace 方法 问题背景 &#xff1a; 在 Vue2 的一个移动端开发…
阅读更多...
JS-WebAPIs- Window对象(五)

JS-WebAPIs- Window对象(五)

• BOM(浏览器对象模型) BOM(Browser Object Model ) 是浏览器对象模型 window对象是一个全局对象&#xff0c;也可以说是JavaScript中的顶级对象像document、alert()、console.log()这些都是window的属性&#xff0c;基本BOM的属性和方法都是window的。所有通过var定义在全局…
阅读更多...
【web 编程技术】基于 B/S 架构的电商平台（java web）

【web 编程技术】基于 B/S 架构的电商平台（java web）

基于 B/S 架构的电商平台&#xff08;java web&#xff09; 课程设计实验目的课程设计实验环境课程设计功能概述课程设计需求分析三层架构图功能列表系统用例图系统活动图-用户端需求分析 课程设计详细设计实现过程数据库BaseServlet 的实现商品显示模块-分页显示所有商品、查看…
阅读更多...
《WebKit 技术内幕》之五（1）： HTML解释器和DOM 模型

《WebKit 技术内幕》之五（1）： HTML解释器和DOM 模型

第五章 HTML 解释器和 DOM 模型 1.DOM 模型 1.1 DOM标准 DOM &#xff08;Document Object Model&#xff09;的全称是文档对象模型&#xff0c;它可以以一种独立于平台和语言的方式访问和修改一个文档的内容和结构。这里的文档可以是 HTML 文档、XML 文档或者 XHTML 文档。D…
阅读更多...
MySQL 索引（下）

MySQL 索引（下）

&#x1f389;欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克&#x1f379; ✨博客主页&#xff1a;小小恶斯法克的博客 &#x1f388;该系列文章专栏&#xff1a;重拾MySQL-进阶篇 &#x1f379;文章作者技术和水平很有限&#xff0c;如果文中出现…
阅读更多...
【STM32调试】寄存器调试不良问题记录持续版

【STM32调试】寄存器调试不良问题记录持续版

STM32寄存器调试不良问题记录 低功耗管理NVIC&#xff08;内嵌的中断向量控制器&#xff09;EXTI&#xff08;外部中断/事件&#xff09; 记录一些stm32调试过程中&#xff1a;不易被理解、存在使用误区、不清不楚、是坑、使用常识等方面的一些记录。本记录只包含stm32的内核以…
阅读更多...
UE5 C++学习笔记 常用宏的再次理解

UE5 C++学习笔记 常用宏的再次理解

1.随意创建一个类&#xff0c;他都有UCLASS()。GENERATED_BODY()这样的默认的宏。 UCLASS() 告知虚幻引擎生成类的反射数据。类必须派生自UObject. &#xff08;告诉引擎我是从远古大帝UObject中&#xff0c;继承而来&#xff0c;我们是一家人&#xff0c;只是我进化了其他功能…
阅读更多...
动态规划——炮兵回城【集训笔记】

动态规划——炮兵回城【集训笔记】

题目描述 游戏盘面是一个m行n列的方格矩阵&#xff0c;将每个方格用坐标表示&#xff0c;行坐标从下到上依次递增&#xff0c;列坐标从左至右依次递增&#xff0c;左下角方格的坐标为(1,1)&#xff0c;则右上角方格的坐标为(m,n)。 游戏结束盘上只剩下一枚炮兵没有回到城池中&a…
阅读更多...
编曲学习：Cubase12导入Cubasis工程的方法！

编曲学习：Cubase12导入Cubasis工程的方法！

Steinberg 发布 Cubasis 3 项目导入器&#xff0c;可将 Cubasis 的项目导入到 Cubase 使用https://m.midifan.com/news_body.php?id35635 我偶然看到这个文章&#xff0c;不过发现Cubase12默认好像没有这个选项&#xff0c;心想着要是移动端能和PC端同步&#xff0c;感觉会挺…
阅读更多...
【网站项目】329网月科技公司门户网站

【网站项目】329网月科技公司门户网站

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…
阅读更多...
深入理解JavaScript箭头函数

深入理解JavaScript箭头函数

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》、《krpano中文文档》 ​ ​ ✨ 前言 函数是JavaScript中非常重要的一个组成部分,可以封装代码逻辑,提高代…
阅读更多...
x-cmd pkg | jq - 命令行 JSON 处理器

x-cmd pkg | jq - 命令行 JSON 处理器

目录 简介首次用户功能特点类似工具进一步探索 简介 jq 是轻量级的 JSON 处理工具&#xff0c;由 Stephen Dolan 于 2012 年使用 C 语言开发。 它的功能极为强大&#xff0c;语法简洁&#xff0c;可以灵活高效地完成从 JSON 数据中提取特定字段、过滤和排序数据、执行复杂的转…
阅读更多...
Transformer and Pretrain Language Models3-2

Transformer and Pretrain Language Models3-2

transformer structure注意力机制的各种变体 第二种变体&#xff1a; 如果两个向量的维度不一样&#xff0c;我们就需要在中间加上一个权重矩阵&#xff0c;来实现他们之间的相乘&#xff0c;然后最后得到一个标量 第三种变体&#xff1a; additive attention 它和前面的有…
阅读更多...
顶顶通用户申请和安装 空号识别 模块流程

顶顶通用户申请和安装 空号识别 模块流程

一、申请 空号识别 授权 打开网址&#xff1a;http://my.ddrj.com&#xff0c;注册并登录。 点击“我的授权” -> “申请授权” &#xff08;根据负责人的要求选择“在线”或是“离线”&#xff09;。 找到名称为空号识别的授权并点击“加号”图标打开授权&#xff0c;然…
阅读更多...
JDK 动态代理（Spring AOP 的原理）（面试重点）

JDK 动态代理（Spring AOP 的原理）（面试重点）

代理模式 也叫委托模式.定义&#xff1a;为其他对象提供⼀种代理以控制对这个对象的访问.它的作⽤就是通过提供⼀个代理类,让我们 在调⽤⽬标⽅法的时候,不再是直接对⽬标⽅法进⾏调⽤,⽽是通过代理类间接调⽤&#xff0c;在某些情况下,⼀个对象不适合或者不能直接引⽤另⼀个对…
阅读更多...
geoserver pg_hba.conf 设置连接

geoserver pg_hba.conf 设置连接

geoserver pg_hba.conf 设置连接 在Postgre安装文件目录下的data文件夹中&#xff0c;修改pg_hba.conf文件&#xff0c;末尾添加重启postgresql的服务&#xff0c;应该就可以连了。
阅读更多...
基于无锁循环队列的线程池的实现

基于无锁循环队列的线程池的实现

目录 出处&#xff1a;B站码出名企路 应用场景 设计实现 等待策略模块 晚绑定 C 中的 override关键字 C中的 default 关键字 C中的 delete 关键字 C中的 explicit 关键字 C中 using 别名技巧 sleep 和 yield的区别 noexcept关键字 volatile关键字 无锁循环队列的…
阅读更多...
第十二站(20天):C++泛型编程

第十二站(20天):C++泛型编程

模板 C提供了模板(template)编程的概念。所谓模板&#xff0c;实际上是建立一个通用函数或类&#xff0c; 其 类内部的类型和函数的形参类型不具体指定 &#xff0c;用一个虚拟的类型来代表。这种通用的方式称 为模板。 模板是泛型编程的基础, 泛型编程即以一种独立于任何特定…
阅读更多...
JavaWeb-Listener

JavaWeb-Listener

一、概念 Listener表示监听器&#xff0c;是JavaWeb三大组件&#xff08;Servlet&#xff0c;Filter&#xff0c;Listener&#xff09;之一&#xff0c;监听器的监听对象可以是application, session, request三个对象&#xff0c;监听的事件是这些对象的创建或销毁&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023