STL库中list的迭代器实现痛点分析

前文

本篇文章准备换个模式,之前都是先详解模拟实现,但是模拟实现的基本逻辑大多数老铁都是明白的,所以我们这次主要讲解 STL库中list的独特性,也就是模拟实现中的重难点
文末有模拟实现的源码

一,list实现的特殊类

list实现和前面vector,string最大的区别莫过于单独封装了迭代器。
我们通常使用的迭代器分为两种:1. 原生指针作为迭代器。如vector,string。2. 自定义类型对原生指针进行封装,模拟指针的行为。如list。

vector:

list:

在list中,我们对原生指针进行封装,模拟指针的行为,因此我们需要在该类中实现 *(),->,前置++,后置++,前置--,后置--,!=,==等函数重载

这时候可能有的老铁对,迭代器模板中三个模板参数感到惊讶,下面我们就来讲解一下。

二,迭代器模板中的多个模板参数

如图,迭代器模板参数中定义了三个模板参数,这是为什么呢?要注意这里是list中模板 非常非常巧妙的一种用法
第一个T就不用多说了,和vector中的模板参数意义一样。我们重点说第二和第三个.

2.1 Ref模板参数

Ref模板参数的产生主要是因为 *()操作符重载
在实际的应用中,我们的list可能会被const修饰,导致里面的值只能读取不能修改,而如果用第一个模板参数我们则无法实现 const修饰返回值,因此我们专门写了第二个模板参数Ref来应对这种情况。
如上图所示,右边const修饰的list其中的值无法改变,我们会直接调用const_iterator迭代器进行模板实例化,这样Ref的值就为const T&,至此,我们就借助了第二个模板参数实现了正常迭代器和const修饰的迭代器的区分.

2.2 Ptr模板参数

Ptr模板参数是专门给 ->操作符重载准备的.

没有Ptr的话应该是这样

我们多一个模板参数的原因和Ref的原因一样,都是为了应对list被const修饰无法改变的情况
但是list迭代器中 ->操作符重载有一个 重要的特性。如下所示

图中第313行和314行代码不一样但执行效果却一样,为什么呢?
根据语法,313行想访问_a1,应该这样写it->->_a1,但it->_a1却也可以,为什么呢?
这是因为在这里我们为了 增强可读性,省略了一个->

三,源码

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace mjw
{
    
    template<class T>
    struct list_node
    {
        list_node<T>* _prev;
        list_node<T>* _next;
        T _data;

        list_node(const T& val=T())
            :_prev(nullptr)
            ,_next(nullptr)
            ,_data(val)
        {}
    };

    template<class T,class Ref,class Ptr>
    struct _list_iterator
    {
        typedef list_node<T> node;
        typedef _list_iterator<T, Ref,Ptr> iterator;
        node* _node;
        
        _list_iterator(node* n)
            :_node(n)
        {}

        //*()重载
        Ref operator*()
        {
            return _node->_data;
        }

        //->重载
        T* operator->()
        {
            return &_node->_data;
        }

        //前置++
        iterator& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        //后置++
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        //前置--
        iterator& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        //后置--
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        //!=重载
        bool operator!=(const iterator ls)
        {
            return _node != ls._node;
        }
        //==重载
        bool operator==(const iterator ls)
        {
            return _node == ls._node;
        }

    };

    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;

        
        void empty_init()
        {
            _head = new node;
            _head->_next = _head;
            _head->_prev = _head;

        }
        //构造
        list()
        {
            empty_init();
        }

        //区间构造
        //先初始化,然后一个一个尾插
        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            empty_init();

            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        void swap(list<T>& tmp)
        {
            std::swap(_head, tmp._head);
        }
        //拷贝构造
        list(const list<T>& lt)
        {
            empty_init();

            list<T> tmp(lt.begin(),lt.end());
            swap(tmp);
        }

        //赋值
        list<T>& operator=(list<T> lt)
        {
            swap(lt);
            return *this;
        }

        //析构
        ~list()
        {
            delete _head;
            _head = _head->_next = _head->_prev = nullptr;
        }
        //clear
        void clear()
        {
            iterator cur = begin();
            while (cur != end())
            {
                erase(cur++);
                
            }
        }

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

        //尾插
        void push_back(const T& val)
        {
            /*node* newnode = new node(val);
            node* next = _head;
            node* prev = _head->_prev;

            newnode->_next = next;
            newnode->_prev = prev;
            prev->_next = newnode;
            next->_prev = newnode;*/
            insert(end(), val);
        }
        //尾删
        void pop_back()
        {
            erase(--end());
        }
        //头插
        void push_front(const T& val)
        {
            insert(begin(), val);
        }
        //头删
        void pop_front()
        {
            erase(begin());
        }

        void insert(iterator pos, const T& val)
        {
            node* newnode = new node(val);
            node* next = pos._node;
            node* prev = next->_prev;
            
            newnode->_next = next;
            newnode->_prev = prev;
            prev->_next = newnode;
            next->_prev = newnode;
        }

        //为了防止迭代器失效,返回要删除的迭代器的下一个数据
        iterator erase(iterator pos)
        {
            assert(pos._node != _head);
            node* prev = pos._node->_prev;
            node* next = pos._node->_next;

            prev->_next = next;
            next->_prev = prev;
            delete pos._node;
            pos._node = nullptr;
            return iterator(next);
        }
    private:
        node* _head;
    };

}

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

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

相关文章

【pytorch】使用deepsort算法进行目标跟踪,原理+pytorch实现

目录deepsort流程一、匈牙利算法二、卡尔曼滤波车速预测例子动态模型的概念卡尔曼滤波在deepsort中的动态模型三、预测值及测量值的含义deepsort在pytorch中的运行deepsort流程 DeepSORT是一种常用的目标跟踪算法&#xff0c;它结合了深度学习和传统的目标跟踪方法。DeepSORT的…

WireShark如何抓包,各种协议(HTTP、ARP、ICMP)的过滤或分析,用WireShark实现TCP三次握手和四次挥手

WireShark一、开启WireShark的大门二、如何抓包 搜索关键字2.1 协议过滤2.2 IP过滤2.3 过滤端口2.4 过滤MAC地址2.5 过滤包长度2.6 HTTP模式过滤三、ARP协议分析四、WireShark之ICMP协议五、TCP三次握手与四次挥手5.1 TCP三次握手实验5.2 可视化看TCP三次握手5.3 TCP四次挥手5.…

PCL 使用ICP点云拼接

一、简介 ICP算法详解——我见过最清晰的解释_负壹的博客-CSDN博客 两个点集&#xff0c;source和target&#xff0c;target不变&#xff0c;source经过旋转&#xff08;Rotation&#xff09;和平移&#xff08;Translation&#xff09;甚至加上尺度&#xff08;Scale&#x…

大聪明教你学Java | 深入浅出聊 SpringBoot 中的 starter 机制

前言 &#x1f34a;作者简介&#xff1a; 不肯过江东丶&#xff0c;一个来自二线城市的程序员&#xff0c;致力于用“猥琐”办法解决繁琐问题&#xff0c;让复杂的问题变得通俗易懂。 &#x1f34a;支持作者&#xff1a; 点赞&#x1f44d;、关注&#x1f496;、留言&#x1f4…

网络安全横向移动指南

在网络安全方面&#xff0c;了解威胁参与者的工具、技术和思维过程非常重要。 一旦对手获得对网络的初始访问权限&#xff0c;横向移动允许他们通过破坏目标组织网络中的其他主机来扩展访问权限并保持持久性。 威胁行为者可以收集有关公司用户活动和凭据、重要数据位置的信息…

Spark - 继承 FileOutputFormat 实现向 HDFS 地址追加文件

目录 一.引言 二.源码浅析 1.RDD.saveAsTextFile 2.TextOutputFormat 3.FileOutputFormat 三.源码修改 1.修改文件生成逻辑 - getRecordWriter 2.允许目录存在 - checkoutputSpecs 3.全部代码 - TextOutputFormatV2 四.追加存储代码实战 五.总结 一.引言 Output d…

关于STM32用DMA传输UART空闲中断中接收的数据时无法接收数据问题以及解决办法

一、stm32 cube ide 配置 1、DMA串口接收数据的ide配置如下图所示 串口1相关的设置及printf函数的使用&#xff0c;这里没放&#xff0c;建议先实现串口打印功能 2、相关的知识点 普通模式和循环模式的区别在于&#xff0c;普通模式下&#xff0c;DMA只会接收一次数据&#x…

微前端(无界)

前言&#xff1a;微前端已经是一个非常成熟的领域了&#xff0c;但开发者不管采用哪个现有方案&#xff0c;在适配成本、样式隔离、运行性能、页面白屏、子应用通信、子应用保活、多应用激活、vite 框架支持、应用共享等用户核心诉求都或存在问题&#xff0c;或无法提供支持。本…

DS18B20温度传感器简介和1-Wire驱动程序

目录DS18B20简介DS18B20的两种供电方式64位ROM温度传感器1-Wire Bus简介DS18B20通信时序初始化ROM相关命令(后续包含任何数据交换的操作)功能相关命令(后续包含任何数据交换的操作)单个DS18B20读取温度值驱动多个DS18B20读取温度值驱动DS18B20简介 DS18B20数字温度计提供9位到…

学习系统编程No.7【进程替换】

引言&#xff1a; 北京时间&#xff1a;2023/3/21/7:17&#xff0c;这篇博客本来昨天晚上就能开始写的&#xff0c;但是由于笔试强训的原因&#xff0c;导致时间用在了做题上&#xff0c;通过快2个小时的垂死挣扎&#xff0c;我充分意识到了自己做题能力的缺陷和运用新知识的缺…

致远OA敏感信息泄露漏洞合集(含批量检测POC)

文章目录前言敏感信息泄露A6 status.jsp 信息泄露漏洞漏洞描述漏洞影响网络测绘漏洞复现POC 批量检测getSessionList.jsp Session泄漏漏洞漏洞描述网络测绘批量检测POC致远OA 帆软组件 ReportServer 目录遍历漏洞漏洞描述漏洞影响网络测绘POC(批量检测)A6 createMysql.jsp 数据…

Java stream性能比较

环境 Ubuntu 22.04IntelliJ IDEA 2022.1.3JDK 17CPU&#xff1a;8核 ➜ ~ cat /proc/cpuinfo | egrep -ie physical id|cpu cores physical id : 0 cpu cores : 1 physical id : 2 cpu cores : 1 physical id : 4 cpu cores : 1 physical id : 6 cpu cores : 1 physical id …

浏览器工作原理

一、JavaScript 的历史 JavaScript&#xff08;简称JS&#xff09;Web前端开发的脚本语言。 它诞生1995年&#xff0c;由网景公司的 Brendan Eich 开发。最初&#xff0c;JavaScript 被设计用于在网页上嵌入动态内容和交互式功能。 1996年&#xff0c;JavaScript 1.1 成为国…

C++虚函数与多态

C虚函数与多态虚函数抽象类纯虚函数虚析构函数多态虚函数的几个问题纯虚函数和ADT虚函数 virtual修饰的成员函数就是虚函数&#xff0c; 1.虚函数对类的内存影响&#xff1a;增加一个指针类型大小&#xff08;32位和64位&#xff09; 2.无论有多少个虚函数&#xff0c;只增加一…

【ansible】模块介绍超详解(下)

目录 六&#xff0c;软件包管理 1&#xff0c;yum_repository模块 &#xff08;1&#xff09;yum_repository模块常用选项 &#xff08;2&#xff09;yum_repository模块案例 2&#xff0c;mount模块 &#xff08;1&#xff09;mount模块选项 &#xff08;2&#xff09;mount模…

大数据简介

大数据概论和职业规划Linux服务器系统Hadoop概论HDFS分布式文件系统Hive数据仓库SparSQL指令Zepplin框架Sqoop框架Superset数据可视化大数据数仓实战-didi出行大数据概念大数据特点大数据应用场景大数据分析业务步骤大数据职业规划大数据学习路线。大数据概念数据&#xff1a;世…

基于YOLOv5的舰船检测与识别系统(Python+清新界面+数据集)

摘要&#xff1a;基于YOLOv5的舰船检测与识别系统用于识别包括渔船、游轮等多种海上船只类型&#xff0c;检测船舰目标并进行识别计数&#xff0c;以提供海洋船只的自动化监测和管理。本文详细介绍船舰类型识别系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实…

【系统开发】WebSocket + SpringBoot + Vue 搭建简易网页聊天室

文章目录一、数据库搭建二、后端搭建2.1 引入关键依赖2.2 WebSocket配置类2.3 配置跨域2.4 发送消息的控制类三、前端搭建3.1 自定义文件websocket.js3.2 main.js中全局引入websocket3.3 App.vue中声明websocket对象3.4 聊天室界面.vue3.5 最终效果一、数据库搭建 很简单的一个…

数据结构与算法——二叉树+带你实现表达式树(附源码)

&#x1f4d6;作者介绍&#xff1a;22级树莓人&#xff08;计算机专业&#xff09;&#xff0c;热爱编程&#xff1c;目前在c&#xff0b;&#xff0b;阶段&#xff0c;因为最近参加新星计划算法赛道(白佬)&#xff0c;所以加快了脚步&#xff0c;果然急迫感会增加动力>——…

ThreadLocal详解

一、什么是ThreadLocal 1、什么是ThreadLocal&为什么用ThreadLocal ThreadLocal&#xff0c;即线程本地变量&#xff0c;在类定义中的注释如此写This class provides thread-local variables。如果创建了一个ThreadLocal变量&#xff0c;那么访问这个变量的每个线程都会有…
最新文章