list的常用接口底层实现与介绍

目录

概念:

list的基本结构:

list的迭代器⭐❤: 

自定义类型的完善: 

const的迭代器:

insert 

erase:

size 

empty 

push_back 、push_front 、pop_back、pop_front 

swap 、operator=

析构函数、clear() 


 

概念:
  1. list是序列容器,允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作,并在两个方向进行迭代。
  2. list容器使用双链表实现;双链表将每个元素存储在不同的位置,每个节点通过next,prev指针链接成顺序表。
  3. list与其他标准序列容器(array,vector和deque)相比,list通常可以在容器内的任何位置插入、提取和移动元素。
  4. list与其他标准序列容器(array,vector和deque)相比,list和forward_list(单链表实现)的主要缺点是他们不能通过位置直接访问元素;例如,要访问列表中的第五个元素,必须从已知位置(开始或结束)迭代到该位置,需要哦线性时间开销。
  5. 存储密度低,list要使用一些额外的内容空间(next,prev)来保持与每个元素相关联(前后续的线性)的链接信息,从而导致存储小元素类型(如char,short,int等)的列表的存储密度低。

list的基本结构:
#include<iostream>
#include<assert.h>
using namespace std;
namespace bit {template <class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};template<class T>class list {typedef ListNode<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}private:Node* _head;size_t _size;};
}

通过list的概念我们可以得知,list在本质上就是一种带头的双向链表结构,所以在创建list类之前,我们首先要构建一个节点的结构体,其次在list的构造函数中,为了让list遵循它本质上的数据结构,以及通过之后的插入删除等等操作,利用带头双向链表结构的特点,我们将成员变量特地设置为头节点以及长度。

list的迭代器⭐❤: 

list的迭代器特殊之处: 

  • 迭代器的本质就是不管是什么类型的数据都可以进行访问!所以该如何使用迭代器遍历链表内的数据呢?是否能使用前驱、后继指针充当迭代器?答案是不能!
  • 如果使用前驱后继指针充当迭代器,那么就需要遇到一个问题,链表的各个节点是不同位置不同地址的!
  • 所以如果使用指针+1的方式并不能正确的遍历链表!
  • 其次,如果使用前驱后继指针当迭代器,那么解引用能得到节点内的数据吗?不能!因为Node * 解引用后上一个Node 是一个strcut结构体

所以对于list的迭代器,正确的解决方案是另外在设置一个类对迭代器进行分装操作! 

	template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> self;Node* _node;ListIterator(Node*node):_node(node){}};

在原先的原身指针 prev和next下,并不能解决迭代器遍历操作,以及解引用操作,因为节点的空间问题并不能使用指针+1的操作,以及解引用prev和next并不能直接获取到节点内部存储的数值元素,所以我们需要在这个封装操作中进行。

至于这个封装为什么是结构体呢?

在C++中,struct和class是非常相似的,唯一的区别是默认的访问权限不同。在struct中,成员默认是公共的(public),而在class中,默认是私有的(private)。因此,在C++中,struct内部是可以定义函数的。 

在这个结构体的内部我们需要解决迭代器的遍历、解引用、遍历修改、不等于 等运算符重载问题! 

		//*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;}slef& operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}

我们定义这些重载运算符的意义就在于为了之后我们在定义begin时,可以直接使用封装的重载运算符!

		typedef ListIterator<T> iteator;iterator begin(){iterator it(_head->_next);return it;}iterator end(){iterator it(_head);return it;}

自定义类型的完善: 

自定义类型的完善 ,因为我们写的是一个自定义类型,所以读取*it后解决完后还是一个自定义类型的数据结构,所以需要在使用数据结构的写法,表明其中内部的数据即可!

 

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

it->是需要进行拆解的,可以变成it.operator()->,这里其实是编译器的一种隐藏操作,之前的it++也是一种隐藏操作,可以变化为it.operator++()

而it->_a1这里隐藏的是另一个-> ,也就是图中第二个->,第一个->是属于it的重载运算符标识!

const的迭代器:

首先要记住const不能调用非const的成员函数!但是非const可以调用const的成员函数

为了让const修饰的类型能够使用迭代器,我们需要根据const不能修改内容的特点进行另外设置一共专门让const使用的迭代器封装,但是由于只是需要变动operator*()和operator->所以我们可以使用模板类解决这类问题! 

template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){return &_node->_data;}// ++itSelf& 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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};
insert 

 有了迭代器之后了,可以利用迭代器的操作进行insert的底层实现

void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode cur;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}

erase:

操作和insert一样都是对指针的方向的修改!但是pos会在后面失效,也就是迭代器会失效,所以需要改变类型!然后进行返回!这里的返回变成了的pos节点的后面一个节点的迭代器。

iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}
size 
        size_t size() const{return _size;}
empty 
        bool empty(){return _size == 0;}
push_back 、push_front 、pop_back、pop_front 
        void push_back(const T& x)//尾插{insert(end(), x);}void push_front(const T& x)//头插{insert(begin(), x);}void pop_back()//尾删{erase(--end());}void pop_front()//头删{erase(begin());}
swap 、operator=
        void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}
析构函数、clear() 
		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}

 

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

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

相关文章

【CSS】CSS三大特性、盒子模型

目录 CSS三大特性 1、层叠性 2、继承性 3、优先级 盒子模型 1、网页布局的本质 2、盒子模型&#xff08;Box Model&#xff09;组成 3、边框&#xff08;border&#xff09; 3.1、边框的使用 3.2、表格的细线边框 3.3、边框会影响盒子实际大小 4、内边距&#xff0…

Unity 九宫格

1. 把图片拖拽进资源文件夹 2.选中图片&#xff0c;然后设置图片 3.设置九宫格 4.使用图片&#xff0c;在界面上创建2个相同的Image,然后使用图片&#xff0c;修改Image Type 为Sliced

前端开发基础(HTML5 + CSS3)【第一篇】:HTML标签之文字排版、图片、链接、音频、视频 涵盖了两个综合案例 做到了基础学得会,实战写的出

点击前往前端开发基础专栏&#xff1a; 文章目录 HTML5 CSS3 开发一、开发环境搭建下载 VS Code1. 2 插件的下载1.3 项目和文件的下载 二、 什么是 HTML2.1 标签的语法2.2 代码演示&#xff1a;2.3 小结 三 、HTML基本骨架3.1 快捷键生成HTML骨架3.2 代码展示3.3 小结 四、标…

第十四讲:C语言字符函数和字符串函数

目录 1. 字符分类函数 2、字符转换函数 3. strlen的使⽤和模拟实现 4. strcpy 的使⽤和模拟实现 5. strcat 的使⽤和模拟实现 6. strcmp 的使⽤和模拟实现 7. strncpy 函数的使⽤ 8. strncat 函数的使⽤ 9. strncmp函数的使⽤ 10. strstr 的使⽤和模拟实现 11. strt…

Redis的持久化

目录 一、RDB&#xff08;Redis DataBase&#xff09; 二、AOF&#xff08;Append Only File&#xff09; Redis 是内存数据库&#xff0c;如果不将内存中的数据库状态保存到磁盘&#xff0c;那么一旦服务器进程退出&#xff0c;服务器中 的数据库状态也会消失。所以 Redis 提供…

从文字到思维:呆马GPT在人工智能领域的创新之旅

引言 生成式预训练变换器&#xff08;Generative Pre-trained Transformer&#xff0c;简称GPT&#xff09;领域是人工智能技术中的一大革新。自OpenAI推出第一代GPT以来&#xff0c;该技术经历了多代发展&#xff0c;不断提升模型的规模、复杂度和智能化程度。GPT模型通过在大…

【Linux】vim 编辑器

Linux 系统自带了 gedit 和 vi 编辑器&#xff0c;gedit 是图形化界面的操作&#xff0c;而 vi 由比较难用&#xff0c;所以建议安装 vim 编辑器&#xff0c;vim 是从 vi 发展出来的一个文本编辑器&#xff0c;相当于增强版的 vi &#xff0c;其代码补完、编译及错误跳转等功能…

从路由器syslog日志监控路由器流量

路由器是关键的网络基础设施组件&#xff0c;需要随时监控&#xff0c;定期监控路由器可以帮助管理员确保路由器通信正常。日常监控还可以清楚地显出通过网络的流量&#xff0c;通过分析路由器流量&#xff0c;安全管理员可及早识别可能发生的网络事件&#xff0c;从而避免停机…

负荆请罪将相和之后的廉颇蔺相如,下场如何?

“将相和”的故事相信许多人都听说过&#xff0c; 这个故事来自于司马迁的《史记》&#xff0c;并被许多版本的语文教科书所收录&#xff0c;而“完璧归赵”“负荆请罪”等成语也都是出自这个故事。但是这个故事并没有讲“将相和”之后的内容&#xff0c;实际上&#xff0c;蔺相…

C语言面试题之合法二叉搜索树

合法二叉搜索树 实例要求 实现一个函数&#xff0c;检查一棵二叉树是否为二叉搜索树&#xff1b; 示例 1: 输入:2/ \1 3 输出: true 示例 2: 输入:5/ \1 4/ \3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 &#xff0c;但是其右子节点值为 4 …

VS2022使用属性表快速设置OpenCV工程属性

1.创建C控制台应用 2.配置工程 3.打开工程后,为工程添加属性表 打开属性管理器窗口,选择Debug|x64 然后右击选择添加新的项目属性表 并命名为opencv490_debug_x64 点击添加 Debug版本属性表添加成功 使用相同方法添加Release版本属性表 双击debug版本属性表并添加包含目录 添…

90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装)

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…

Github第一Star数的国产免费开源防火墙--雷池社区版初步体验

前言 近期准备搭建一个博客网站&#xff0c;用来存储工作室同学们的学习笔记。服务器准备直接放在公网上&#xff0c;方便大家随时随地的上传和浏览&#xff0c;为了防止网站被人日穿成为肉鸡&#xff0c;一些防御措施还是要部署的。 首先明确自己的需求&#xff1a; 零成本…

【Python】控制台进度条

在Python开发中&#xff0c;有时需要向用户展示一个任务的进度&#xff0c;以提供更好的交互体验。下面我将展示如何使用Python来创建一个简单的控制台进度条。 效果&#xff1a; 代码&#xff1a; import time import sys def print_progress_bar(completed, total, length…

Windows搭建Jellyfin影音服务结合内网穿透实现公网访问本地视频文件

文章目录 1. 前言2. Jellyfin服务网站搭建2.1. Jellyfin下载和安装2.2. Jellyfin网页测试 3.本地网页发布3.1 cpolar的安装和注册3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5. 结语 1. 前言 随着移动智能设备的普及&#xff0c;各种各样的使用需求也被开发出来&…

【Web】NSSRound#1-20 Basic 刷题记录(全)

目录 [NSSRound#1 Basic]basic_check [NSSRound#1 Basic]sql_by_sql [NSSCTF 2nd]php签到 [NSSCTF 2nd]MyBox [NSSCTF 2nd]MyBox(revenge) [NSSCTF 2nd]MyHurricane [NSSCTF 2nd]MyJs [NSSRound#3 Team]This1sMysql [NSSRound#3 Team]path_by_path [NSSRound#…

二叉树应用——最优二叉树(Huffman树)、贪心算法—— Huffman编码

1、外部带权外部路径长度、Huffman树 从图中可以看出&#xff0c;深度越浅的叶子结点权重越大&#xff0c;深度越深的叶子结点权重越小的话&#xff0c;得出的带权外部路径长度越小。 Huffman树就是使得外部带权路径最小的二叉树 2、如何构造Huffman树 &#xff08;1&#xf…

【Python-MP4文体提取】

Python-MP4文体提取 ■ pip 和 setuptools工具■ OpenCV和Tesseract■ Tesseract OCR V5.0安装教程&#xff08;Windows&#xff09;■ 1. 运行程序出现如下问题&#xff1a;我们需要安装Tesseract OCR■ 2. 下载Tesseract-OCR■ 3. 安装Tesseract-OCR■ 4. 添加到环境变量的系…

Golang中的上下文-context包的简介及使用

文章目录 简介context.Background()上下文取消函数上下文值传递建议Reference 简介 Go语言中的context包定义了一个名为Context的类型&#xff0c;它定义并传递截止日期、取消信号和其他请求范围的值&#xff0c;形成一个链式模型。如果我们查看官方文档&#xff0c;它是这样说…

Ollama利用嵌入模型实现RAG应用

Ollama支持embedding models嵌入模型&#xff0c;从而支持RAG&#xff08;retrieval augmented generation&#xff09;应用&#xff0c;结合文本提示词&#xff0c;检索到文档或相关数据。嵌入模型是通过训练生成向量嵌入&#xff0c;这是一长串数字数组&#xff0c;代表文本序…