解密list的底层奥秘

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
金句分享:
✨即使人生还有无数次失望的可能性,✨
✨但我还是想活在理想主义的乌托邦里.✨

目录

  • 一、list底层框架
    • (1) 节点类
    • (2) 迭代器类
    • (3) list类
  • 二、构造函数
    • (1) 无参构造
    • (2) n个value构造
    • (3) 迭代器区间构造
    • (4) 拷贝构造
  • 三、迭代器
    • 迭代器的实现
      • ① 构造
      • ② `*`和`->`
      • ③ 前置++与后置++
      • ④ 前置--与后置--
      • ⑤ 比较运算符
    • list类中的迭代器
    • front和back
  • 四、Modifiers:
    • (1) insert()
    • (2) erase()
    • (3) push_back() 和 push_front()
    • (4) pop_back() 和 pop_front()
    • (5) clear()
    • (6) swap()
  • 结语

本篇通过模拟实现list的构造函数,迭代器,和部分成员函数以帮助大家更加深层的理解list的原理,希望看完这篇文章使得友友们对list有了更加深层的理解.

一、list底层框架

list的底层是一个带头双向循环链表.
在这里插入图片描述

(1) 节点类

因为list中节点可能存储各种类型的值,所以这里使用了一个模板参数T.

list <int>
list<doubel>

 	// List的节点类template<class T>struct list_node{list_node(const T& val = T()):_val(val){}//这里的 T() 表示使用类型 T 的默认构造函数创建一个对象,//它将调用 T 类型的默认构造函数来初始化 val。如果类型 T 没有提供默认构造函数,那么代码将无法编译通过。list_node<T>* _prev=nullptr;	//指向前驱结点list_node<T>* _next=nullptr;	//指向后继结点T _val;							//存储数据};

(2) 迭代器类

很多小伙伴会疑问,为什么一个迭代器类却使用了三个模板参数,是不是有些多余呢?
在这里插入图片描述

其实不然,牛牛依次为大家解释.

  1. class T: 是结点类的存储不同数据所需要使用的模板参数.该模板参数表示要处理的元素的类型。它可以是任意类型,例如整数、浮点数、自定义类等等。在模板实例化时,需要提供一个具体的类型。

  2. Ref: 该模板参数表示指向元素类型 T引用。它定义了对元素的引用类型,在实例化模板时,将使用指定的引用类型来操作元素。

  3. Ptr: 该模板参数表示指向元素类型 T指针。它定义了指向元素的指针类型,在实例化模板时,将使用指定的指针类型来操作元素。

template<class T, class Ref, class Ptr>
意味着
list_iterator<T, const T&, const T*>;

list的迭代器用来遍历链表中的元素,外部通过迭代器的++--进行链表的元素访问,这是一种封装,隐藏内部list的实现细节,外部只能通过迭代器的方式访问.

	//迭代器类template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;//self表示自己list_iterator(Node* node);	//构造list_iterator(const self& list);     //拷贝构造Ref operator*();Ptr operator->();//前置++self& operator++();  //后置++self operator++(int);//前置--self& operator--();//后置--self& operator--(int);bool operator!=(const self& list) const; bool operator==(const self& list);//成员变量Node* _node;};

(3) list类

  template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;list()//(无参构造)//n个value构造list(int n, const T& value = T());//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last);    //拷贝构造list(const list<T>& list);//各种成员函数/...//析构函数~list();iterator begin();       iterator end();//常属性迭代器const_iterator begin()const;const_iterator end()const; private:Node* _head;size_t _size;};

二、构造函数

对于带头双向循环链表,它的初始化操作是必须的,因为必须创建一个头指针.
在这里插入图片描述
对于list的构造函数,它是很多种方式的,例如:无参构造,nval构造,迭代器区间构造等.
对于每个构造,必须前进行最初的初始化操作,为了避免代码冗余,我们将这个部分单独写成一个初始化操作的函数.

如下:

 void  Init_List(){_head = new Node;	//创建头指针_head->_prev = _head;_head->_next = _head;_size = 0;}

(1) 无参构造

调用Init_List();初始化函数即可.

 list()//初始化很重要(无参构造){Init_List();}

(2) n个value构造

  1. 进行初始化操作.
  2. 尾插nvalue.
	//n个value构造list(int n, const T& value = T()){Init_List();while (n--){push_back(value);}}

(3) 迭代器区间构造

  1. 进行初始化操作.
  2. 利用迭代器的特性,一次将区间中的数据尾插入链表.
//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last){Init_List();while (first != last){push_back(*first);++first;}}

(4) 拷贝构造

链表在物理空间上是不连续的,所以,对于参数是另一个链表的拷贝构造,只能遍历链表进行依次插入数据.

	//拷贝构造list(const list<T>& list){Init_List();auto it = list.begin();while (_size!=list._size){push_back(*it);it++;}}

三、迭代器

迭代器的实现

① 构造

迭代器本质就是一个 Node* _node;结点类的指针.
对于迭代器的构造函数,只需要将结点的地址传过来即可.

list_iterator(Node* node)			//默认构造:_node(node) {}
list_iterator(const self& list)     //拷贝构造:_node(list._node){}

*->

(1) *
*运算符重载,表示对迭代器进行解引用.
使用场景:

list<int>::iterator it = L1.begin();
int start=*it;

很明显,*运算符是需要获取结点所存储的数据.为了减少拷贝以及对数据进行修改,这里采用传引用(Ref )返回.

 Ref operator*() {return _node->_val;//获取该结点的数据}

(2) ->

上面链表中的数据是简单的类型int
在这里插入图片描述

Ptr operator->() {return &_node->_val;// 等价于 return &(_node->_val);}

③ 前置++与后置++

对于链表,迭代器++表示向后访问下一个(后继)结点.学过链表的友友们应该知道.
也就是 _node = _node->_next;

前置++,返回++后的结点的迭代器
后置++,返回++前的结点的迭代器

 //前置++self& operator++() {_node = _node->_next;return *this;}//后置++self operator++(int) {Node* tmp=_node;        //保存++之前的值_node = _node->_next;return tmp;             //返回++之前的值}

④ 前置–与后置–

同理,返回当前结点迭代器的前驱结点.
也就是:_node = _node->_prev;

前置–,返回–后的结点的迭代器
后置–,返回–前的结点的迭代器

 //前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self& operator--(int){Node* tmp = _node;          //保存 -- 之前的值_node = _node->_prev;return tmp;                 //返回 -- 之前的值}

⑤ 比较运算符

比较迭代器是否相等,实际就是比较迭代器所指向的结点是否相等.

 bool operator!=(const self& list) const{return _node != list._node;}bool operator==(const self& list){return _node == list._node;}

list类中的迭代器

在这里插入图片描述

iterator begin(): 返回第一个有效元素位置的迭代器
iterator end(): 返回最后一个有效元素位置的迭代器

	typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;//也可以强转一下//return iterator(_head->_next);}iterator end(){return _head;//也可以强转一下// return iterator(_head);}//常属性迭代器const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}

front和back

在这里插入图片描述

 T& front(){return _head->_next->_val;//返回值}const T& front()const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back()const{return _head->_prev->_val;}

四、Modifiers:

其实带头双向循环链表的增删改查较于单链表,更加简单,我们画图分析还是很容易实现的.

(1) insert()

在这里插入图片描述
(图片为博主原创,不得随意截图使用)


特殊情况:这是尾插:
在这里插入图片描述(图片为博主原创,不得随意截图使用)


代码示例

 // 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){//pos.node  而不是pos->nodeNode* newnode = new Node(val);Node* _prev_node = pos._node->_prev;      //pos位置结点的 原前置 结点Node* _cur_node = pos._node;             //pos位置的结点_prev_node->_next = newnode;newnode->_prev = _prev_node;_cur_node->_prev = newnode;newnode->_next = _cur_node;++_size;//有效数据的个数+1.return newnode;}

(2) erase()

在这里插入图片描述

  // 删除pos位置的节点,返回该节点的下一个位置iterator erase(iterator pos){Node* _prev_node = pos._node->_prev;             //pos位置结点的 原前置(prev) 结点Node* _next_node = pos._node->_next;            //pos位置结点的 原后置(next) 结点_next_node->_prev = _prev_node;_prev_node->_next = _next_node;delete pos._node;--_size;return _next_node;}

(3) push_back() 和 push_front()

 //尾插//void push_back(const T& val)//{//    Node* newnode = new Node(val);//    Node* _tail_node = _head->_prev;      // 原尾结点//    _tail_node->_next = newnode;//    newnode->_prev = _tail_node;//    _head->_prev = newnode;//    newnode->_next = _head;//    //    ++_size;//有效数据的个数+1.//}//复用insert更加方便void push_back(const T& val){insert(end(),val);//在头结点前面插入,即为尾插}//头插void push_front(const T& val) { insert(begin(), val);}

(4) pop_back() 和 pop_front()

复用即可,不过多介绍了.

  //尾删void pop_back() { erase(--end()); }//头删void pop_front() { erase(begin()); }

(5) clear()

clear:清除list中的有效数据
遍历链表进行依次删除结点,并将size置为0.

  void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}

(6) swap()

交换两个链表的成员变量即可.

 void swap(list<T>& list){swap(_head, list._head);swap(_size, list._size);}

结语

看完这篇文章,相信大家对list有了更加深层的理解,对于list的迭代器,它并不像前面的stringvector那种原生指针,而是封装成了类,使得链表的迭代器也可以执行++--等操作,因为迭代器类重载了这些运算符.

今天就分享到这里了,如果觉得有帮助的话,可以给牛牛来一个一键三连吗?谢谢支持!
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android之MediaMetricsService实现本质(四十二)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…

王江涛十天搞定考研词汇

学习目标&#xff1a; 考研词汇 学习内容&#xff1a; 2023-9-17 第一天考研词汇 学习时间&#xff1a; 开始:2023-9-17 结束:进行中 学习产出&#xff1a; 2023-9-17intellect智力&#xff1b;知识分子intellectual智力的&#xff1b;聪明的intellectualize使...理智化&a…

JsonUtils

1、工具类 package com.atguigu.utils;import com.fasterxml.jackson.annotation.JsonInclude; import com.fasterxml.jackson.core.JsonProcessingException; import com.fasterxml.jackson.core.type.TypeReference; import com.fasterxml.jackson.databind.Deserialization…

flink集群与资源@k8s源码分析-回顾

本章是分析系列最后一章,作为回顾,以运行架构图串联起所有分析场景 1 启动集群,部署集群(提交k8s),新建作业管理器组件 2 构建和启动flink master组件 3 提交作业,N/A

RocketMQ 消费者分类与分组

文章目录 消费者分类PushConsumerPushConsumer 内部原理使用注意事项 SimpleConsumerinvisibleDuration 消息不可见时间 消费者分组&#xff08;消费者负载均衡&#xff09;广播消费和共享消费负载均衡策略多个消费者消费顺序消息多消费者消费顺序消息示例 消费者分组管理关闭自…

IDEA最新激 20活23码

人狠话不多 大家好&#xff0c;最近Intelli Idea官方的校验规则进行了更新&#xff0c;之前已经成功激20活23的Idea可能突然无法使用了。 特地从网上整理了最新、最稳定的激20活23码分享给大家&#xff0c;希望可以帮助那些苦苦为寻找Idea激20活23码而劳累的朋友们。 本激23…

外国固定资产管理系统功能有哪些

很多公司都在寻找提高自己资产管理效益的方法。为了满足这一要求&#xff0c;国外的固定资产管理系统已经发展成多种形式。以下是国外一些常见的固定资产管理系统的特点:自动化和智能化:许多现代固定资产管理系统采用自动化和数字化技术&#xff0c;以简化流程&#xff0c;减少…

Windows本地mysql 的安装教程(一步一步进行安装)

目录 1 下载安装包2 安装 1 下载安装包 下载网址&#xff1a; https://dev.mysql.com/downloads/ 选择这个 2 安装 编写MySQL配置文件 在解压目录下新建my.ini文件 将下面文本拷贝进my,ini文件中 [mysqld] # 设置3306端口 port3306 # 设置mysql的安装目录 ----------…

18.备忘录模式(Memento)

意图&#xff1a;在不破坏封装性的前提下&#xff0c;捕获一个对象的内部状态&#xff0c;并在该对象之外保存这个状态&#xff0c;这样就可以在以后将该对象恢复到原先保存的状态。 上下文&#xff1a;某些对象的状态在转换过程中&#xff0c;可能由于某种需要&#xff0c;要求…

Qt重写QTreeWidget实现拖拽

介绍 此文章记录QTreeWidget的重写进度&#xff0c;暂时停滞使用&#xff0c;重写了QTreeWidget的拖拽功能&#xff0c;和绘制功能&#xff0c;自定义了数据结构&#xff0c;增加复制&#xff0c;粘贴&#xff0c;删除&#xff0c;准备实现动态刷新数据支持千万数据动态刷新&a…

Docker 容器数据卷

是什么 卷就是目录或文件&#xff0c;存在于一个或多个容器中&#xff0c;由docker挂载到容器&#xff0c;但不属于联合文件系统&#xff0c;因此能够绕过Union File System提供一些用于持续存储或共享数据的特性&#xff1a;卷的设计目的就是数据的持久化&#xff0c;完全独立…

[设计模式] 浅谈SOLID设计原则

目录 单一职责原则开闭原则里氏替换原则接口隔离原则依赖倒转原则 SOLID是一个缩写词&#xff0c;代表以下五种设计原则 单一职责原则 Single Responsibility Principle, SRP开闭原则 Open-Closed Principle, OCP里氏替换原则 Liskov Substitution Principle, LSP接口隔离原则 …

Linux 中的make/makefile

一&#xff1a;背景 make是一个命令工具&#xff0c;是一个解释makefifile中指令的命令工具&#xff0c;一般来说&#xff0c;大多数的IDE都有这个命令&#xff0c;比如&#xff1a;Delphi的make&#xff0c;Visual C的nmake&#xff0c;Linux下GNU的make。可见&#xff0c;mak…

【Xilinx】基于MPSoC的OpenAMP实现(一)

【Xilinx】基于MPSoC的OpenAMP实现&#xff08;一&#xff09; 一、开发环境1、开发思路2、下载官方bsp包 二、编译Linux1、配置petalinux环境变量2、创建工程3、进入目录4、设置缓存目录&#xff08;重点&#xff1a;可离线编译&#xff0c;加快编译速度&#xff09;5、配置u-…

JMeter断言之JSON断言

JSON断言 若服务器返回的Response Body为JSON格式的数据&#xff0c;使用JSON断言来判断测试结果是较好的选择。 首先需要根据JSON Path从返回的JSON数据中提取需要判断的实际结果&#xff0c;再设置预期结果&#xff0c;两者进行比较得出断言结果。 下面首先介绍JSON与JSON…

springboot01

目录 新建Maven工程&#xff0c;什么都不选 ​pom.xml加上 新建包top.cjz.controller 新建类HelloController ​新建类HelloApplication ​运行浏览器访问 新建Maven工程&#xff0c;什么都不选 pom.xml加上 <!--springboot工程需要继承的父工程--> <parent…

第六次面试、第一次复试

第六面&#xff1a; hr迟到&#xff0c;说是搞错了以为线下&#xff0c;我打电话过去才开始&#xff0c;问我想电话面还是视频&#xff0c;果断电话面 自我介绍 介绍了一下公司的工作 ................. 项目拷打&#xff1a; grpc数据如何传输的如何调用两个接口如何获取…

如何使用 Humata.ai:快速理解和总结文献

链接&#xff1a; Humata 简介 Humata.ai 是一个人工智能驱动的文献阅读助手&#xff0c;可以帮助用户快速理解和总结文献。它可以提取文献的关键信息&#xff0c;并以简洁易懂的语言生成摘要。此外&#xff0c;Humata.ai 还可以回答用户关于文献的问题&#xff0c;帮助用户…

用户与权限管理

文章目录 用户与权限管理1. 用户管理1.1 MYSQL用户1.2 登录MySQL服务器1.3 创建用户1.4 修改用户1.5 删除用户1.6 修改密码1. 修改当前用户密码2. 修改其他用户密码 1.7 MYSQL8密码管理 2. 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 3. 权限…

python快速实现带界面可点击的简易计算器

这篇文章将带你探索如何使用Python创建一个直观且实用的带界面计算器。我们将深入介绍如何利用Python的图形用户界面库&#xff0c;特别是Tkinter&#xff0c;来构建一个友好的用户界面&#xff0c;让你能够轻松进行数学运算。无论你是初学者还是有一定编程经验&#xff0c;本文…