C++之STL-list+模拟实现

目录

一、list的介绍和基本使用的方法

1.1 list的介绍

1.2 list的基本使用方法

1.2.1  构造方法

 1.2.2 迭代器

1.2.3 容量相关的接口

1.2.4 增删查改的相关接口

1.3 关于list迭代器失效的问题

二、模拟实现list

2.1 节点类

2.2 迭代器类

2.3 主类list类

2.3.1 成员变量的建立

 2.3.2 迭代器的建立和相关接口的实现

2.3.3 增删查改以及容量接口的实现

1.size()

 2.empty()

3.insert()

4.push_back()

5.pop_back()

6.erase()

7.clear()

8.swap()

2.3.4 构造函数和析构函数


一、list的介绍和基本使用的方法

1.1 list的介绍

同样的给大家上图。

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  3. . list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
  4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;(简单来说就是不支持随机访问)。

1.2 list的基本使用方法

1.2.1  构造方法

常用的构造方法主要是以下4种:

  1. list (size_type n, const value_type& val = value_type())   
    构造的list中包含n个值为val的元素
    list<int> st(10,1);
  2. list()
    构造空的list
    list<int>  st;
  3. list (const list& x)
    拷贝构造函数
    list<int>  l1(10,1);
    list<int>  l2(l1);
  4. list (InputIterator first, InputIterator last)
    用[first, last)区间中的元素构造list,即使用迭代器进行构造
    list<int>  l1(10,1);
    list<int>  l2(l1.begin(),l1.end());

 1.2.2 迭代器

       对于list的迭代器,我们可以暂且认为其是指向list中某个节点的指针,等到模拟实现的时候再给大家详细介绍。这里大概给大家画一下begin()和end()的指向。

1.2.3 容量相关的接口

  1. empty()
    检测list是否为空,是返回true,否则返回false
  2. size()
    返回list中有效节点的个数

1.2.4 增删查改的相关接口

  1. push_front()

    在list首元素前插入值为val的元素
  2.  pop_front()

    删除list中第一个元素

  3. push_back()
    在list尾部插入值为val的元素
  4. pop_back()
    删除list中最后一个元素
  5. insert()
    在list position 位置中插入值为val的元素
  6. erase()
    删除list position位置的元素
  7. swap()
    交换两个list中的元素
  8. clear()
    清空list中的有效元素

1.3 关于list迭代器失效的问题

       迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
 

二、模拟实现list

2.1 节点类

       这里采取的是带头双向列表,如果你不是很了解的话可以参考一下http://t.csdnimg.cn/uSKci
我的这篇文章。

       话不多说,上代码。

template<class T>struct ListNode{ListNode(const T& val = T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};

       由于不知道模板参数,所以我们的默认初始化不能定死,而是采用了一个匿名对象,原本内置类型是没有类似于 T() 这种构造方式的,但是为了方便我们类的定义,祖师爷们特意进行了添加。

2.2 迭代器类

        当大家看到这个标题的时候就可能会疑惑了,为什么要重新定义一个迭代器类呢,为什么不像vector一样,直接对节点重命名不久好了吗?这确实是一个值得我们探讨的问题,要回答这个问题,我们还是要回到迭代器的本质,我在上节就有提到过:

       迭代器提供了一种统一的访问数据结构(如容器、数组、集合等)元素的方式,使得我们能够以统一的接口遍历和操作数据结构中的元素,而不必关心底层数据结构的实现细节。

       如果要满足这个需求,简单的重命名可不好使呀,首先就是范围for你无法支持,vector可以是因为其在内存中是连续的,其++和--都不需要进行重载,而list就不行,因为list所存储数据的内存是不连续的,你要是用老一套的方法肯定是不行的,所以我们才需要将list的迭代器单独封装起来,这恰恰就体现了C++中面向对象的思想。
       解决这个问题之后,我们又迎来了新的问题,const 迭代器我们该怎么实现呢?这时你肯定会说直加个const不就行了吗,答案是显而易见的,肯定不行,不然我就不会问了。那么为什么呢,那是因为这个迭代器是我们封装实现的,我们在list类中直接加const的话,相当于是对我们做的迭代器实例化出来的对象加了个const,那就是对我们所封装的节点加了个const,但节点是指针啊,要清楚,并不是指针不能动(不然范围for又死了),而是所指向的数据域不能改变,那我们应该怎么办呢?这里就需要好好的使用我们的模板了,看我的解决方案。    

 template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self tmp(*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self operator--(int){Self tmp(*this);_pNode = _pNode->pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};

       可以看的我的模板有三个参数template<class T, class Ref, class Ptr> 那这玩意有什么用呢,这后面两个参数主要作用于该类有返回节点数据域的成员函数,const对象和非const对象最大的区别就是一个内容无法被修改一个不受限制,而我们通过对节点的封装,使得外界通过迭代器访问我们数据域时,就一定会访问我们返回节点数据域的重载函数,而这样恰恰给我们模板提供了机会,我们可以根据模板传参去重载我们的返回值,这样也就实现了我们const迭代器的建立。但是这不是最妙的地方,因为要实现这个要求我们也可以复制粘贴改一下条件多写一个类就可以了,可当我们使用了模板之后,你会发现这部分工作就交给编译器去做了,实现了我们的代码复用,这就是泛型编程的好处。

2.3 主类list类

2.3.1 成员变量的建立

       这里我们主要的成员变量就是我们的哨兵位节点和我们有效节点size,为了方便初始化,我还加了一个专门初始化头节点的成员函数。

        private:void CreateHead(){_pHead = new Node();_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}PNode _pHead;size_t _size;

 2.3.2 迭代器的建立和相关接口的实现

有关迭代器的主要内容已经在刚刚讲的差不多了,这里我就不在过多的讲解了,直接上代码。

 public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}

2.3.3 增删查改以及容量接口的实现

       这里接口的实现和我们双向链表以及vector的实现方式很像,我这里就不啰嗦了,有问题可以参考http://t.csdnimg.cn/uSKci和http://t.csdnimg.cn/N3bhY或者私信问我也是可以的哦。

1.size()
        size_t size()const{return _size;}
 2.empty()
        bool empty()const{return _size == 0;}
3.insert()
iterator insert(iterator pos, const T& val){PNode tmp = new Node(val);PNode cur = pos._pNode;PNode pre = pos._pNode->_pPre;tmp->_pNext = cur;tmp->_pPre = pre;pre->_pNext = tmp;cur->_pPre = tmp;_size++;return tmp;}
4.push_back()
        void push_back(const T& val) { insert(end(), val); }
5.pop_back()
        void pop_back(){ erase(--end()); }
6.erase()
        iterator erase(iterator pos){PNode Next = pos._pNode->_pNext;PNode pre = pos._pNode->_pPre;pre->_pNext = Next;Next->_pPre = pre;_size--;return Next;}
7.clear()
void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
8.swap()
        void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}

2.3.4 构造函数和析构函数

废话不多说,直接开造!

list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);first++;}}list(const list<T>& l){CreateHead();for (auto ch : l){push_back(ch);}}list<T>& operator=(list<T> l) {CreateHead();swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}

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

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

相关文章

Java-字符集和字符编码-roadmap

1 需求 2 接口 3 示例 4 参考资料 「烫烫屯屯锟斤拷」揭秘ASCII、GBK、UTF-8&#xff0c;B站独家&#xff0c;一听就懂_哔哩哔哩_bilibili 非常详细的字符编码讲解&#xff0c;ASCII、GB2312、GBK、Unicode、UTF-8等知识点都有_哔哩哔哩_bilibili 你懂乱码吗&#xff1f;锟斤…

【智能算法】囊状虫群算法(TSA)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2020年&#xff0c;S Kaur等人受到囊状虫群自然行为启发&#xff0c;提出了囊状虫群算法&#xff08;Tunicate Swarm Algorithm, TSA&#xff09;。 2.算法原理 2.1算法思想 TSA模拟了囊状虫群在导…

【Linux】:文件查看 stat、cat、more、less、head、tail、uniq、wc

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Linux深造日志 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一、stat&#xff08;查看文件详细属性信息&#xff09;1.1 内容解析&#xff1a;1.2…

JavaSE字节缓冲流

欢迎来到 请回答1024 的博客 &#x1f353;&#x1f353;&#x1f353;欢迎来到 请回答1024的博客 关于博主&#xff1a; 我是 请回答1024&#xff0c;一个追求数学与计算的边界、时间与空间的平衡&#xff0c;0与1的延伸的后端开发者。 博客特色&#xff1a; 在我的博客中&a…

HTML中的文档声明

前言 什么是<!DOCTYPE>&#xff1f;是否需要在 HTML5 中使用&#xff1f;什么是严格模式与混杂模式&#xff1f; 文档声明概念 HTML 文档通常以文档声明开始&#xff0c;该声明的作用是帮助浏览器确定其尝试解析和显示的 HTML 文档类型。 <!DOCTYPE html>文档声…

不同交叉工具链编译程序引发的问题及解决思路

目录 一、问题描述二、应用程序使用buildroot的工具链三、lrzsz 移植使用原交叉工具链四、总结 一、问题描述 buildroot 未使用外部交叉编译工具&#xff0c;生成的文件系统运行原先的程序不能启动。解决办法&#xff1a; ①使用 buildroot的工具链 重新编译程序&#xff1b; …

从零入门区块链和比特币(第二期)

欢迎来到我的区块链与比特币入门指南&#xff01;如果你对区块链和比特币感兴趣&#xff0c;但不知道从何开始&#xff0c;那么你来对地方了。本博客将为你提供一个简明扼要的介绍&#xff0c;帮助你了解这个领域的基础知识&#xff0c;并引导你进一步探索这个激动人心的领域。…

华为云服务器windowsserver镜像部署tomcat提供外网访问

记录一下实现步骤 1.服务器中安装jdk 1.8 2.服务器中安装了mysql5.5版本 3.把tomcat8拷贝到服务器中 4.在云服务器的控制台的安全组中添加一个安全组&#xff0c;由于我tomcat默认用的8080端口 所有我还新增了一个8080端口的配置 如下图 5.虽然设置了安全组&#xff0c;但是你…

DaVinci Resolve Studio 19(达芬奇19调色剪辑)win/mac激活版

DaVinci Resolve Studio是一个结合专业的8k 编辑&#xff0c;颜色混合&#xff0c;视觉效果和音频后期制作的软件。只需点击一下&#xff0c;你就可以立即在编辑、混音、特效和音频流之间切换。此外&#xff0c;达芬奇解决(达芬奇)是一个多用户协作的解决方案&#xff0c;使编辑…

python使用opencv对图像的基本操作(2)

13.对多个像素点进行操作&#xff0c;使用数组切片方式访问 img[i,:] img[j,:] #将第j行的数值赋值给第i行 img[-2,:]或img[-2] #倒数第二行 img[:,-1] #最后一列 img[50:100,50:100] #50-100行&#xff0c;50-100列&#xff08;不包括第100行和第100列&#xff09; img[:100…

一、路由基础

1.路由协议的优先级 路由器分别定义了外部优先级和内部优先级&#xff08;越小越优&#xff09; 路由选择顺序&#xff1a;外部优先级>>内部优先级&#xff08;相同时&#xff09; ①外部优先级&#xff1a;用户可以手工为各路由协议配置的优先级 ②内部优先级&#xf…

uniapp制作分页查询功能

效果 代码 标签中 <uni-pagination change"pageChanged" :current"pageIndex" :pageSize"pageSize" :total"pageTotle" class"pagination" /> data中 pageIndex: 1, //分页器页码 pageSize: 10, //分页器每页显示…

Kubernetes学习-核心概念篇(一) 初识Kubernetes

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Kubernetes渐进式学习-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 1. 前言 2. 什么是Kubernetes 3. 为什么需要Kubernetes 3.1. 应…

Java面试八股文-2024

面试指南 TMD&#xff0c;一个后端为什么要了解那么多的知识&#xff0c;真是服了。啥啥都得了解 MySQL MySQL索引可能在以下几种情况下失效&#xff1a; 不遵循最左匹配原则&#xff1a;在联合索引中&#xff0c;如果没有使用索引的最左前缀&#xff0c;即查询条件中没有包含…

ArcGIS批量寻找图层要素中的空洞

空洞指的是图层中被要素包围所形成的没有被要素覆盖的地方&#xff0c;当图层要素数量非常庞大时&#xff0c;寻找这些空洞就不能一个一个的通过目测去寻找了&#xff0c;需要通过使用工具来实现这一目标。 一、【要素转线】工具 利用【要素转线】工具可以将空洞同图层要素处于…

实现SpringMVC底层机制(一)

文章目录 1.环境配置1.创建maven项目2.创建文件目录3.导入jar包 2.开发核心控制器文件目录1.流程图2.编写核心控制器SunDispatcherServlet.java3.类路径下编写spring配置文件sunspringmvc.xml4.配置中央控制器web.xml5.配置tomcat&#xff0c;完成测试1.配置发布方式2.配置热加…

URL路由基础与Django处理请求的过程分析

1. URL路由基础 对于高质量的Web应用来讲&#xff0c;使用简洁、优雅的URL设计模式非常有必要。Django框架允许设计人员自由地设计URL模式&#xff0c;而不用受到框架本身的约束。对于URL路由来讲&#xff0c;其主要实现了Web服务的入口。用户通过浏览器发送过来的任何请求&am…

HarmonyOS 鸿蒙下载三方依赖 ohpm环境搭建

前言 ohpm&#xff08;One Hundred Percent Mermaid &#xff09;是一个集成了Mermaid的命令工具&#xff0c;可以用于生成关系图、序列图、等各种图表。我们可以使用ohpm来生成漂亮且可读性强的图表。 本期教大家如何搭建ophm环境&#xff1a; 一、在DevEco Studio中&#…

Faust勒索病毒:了解变种faust,以及如何保护您的数据

导言&#xff1a; 近年来&#xff0c;网络安全问题日益严峻&#xff0c;其中勒索病毒成为了一种日益猖獗的威胁。在众多勒索病毒中&#xff0c;.faust勒索病毒以其高度的隐秘性和破坏性引起了广泛关注。本文91数据恢复将深入剖析.faust勒索病毒的威胁特点&#xff0c;并提出相…

Spark-机器学习(5)分类学习之朴素贝叶斯算法

在之前的文章中&#xff0c;我们学习了回归中的逻辑回归&#xff0c;并带来简单案例&#xff0c;学习用法&#xff0c;并带来了简单案例。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵…