当前位置: 首页 > news >正文

C++:list使用以及模拟实现

list使用以及模拟实现

    • list介绍
    • list常用接口
      • 1.构造
      • 2.迭代器
      • 3.容量
      • 4.访问数据
      • 5.增删查改
      • 6.迭代器失效
    • list模拟实现
      • 1.迭代器的实现
      • 2.完整代码

list介绍

  1. list是一个类模板,加<类型>实例化才是具体的类
  2. list是可以在任意位置进行插入和删除的序列式容器。
  3. list的底层是双向循环链表结构,链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  4. 与其他序列式容器相比,list最大的缺陷是不支持任意位置的随机访问,比如访问第六个节点,必须从已知节点迭代到该节点。

双向链表图解:
双向链表图解



list常用接口

1.构造

函数功能
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的节点
list()构造空的list
list (const list& x)拷贝构造
list (InputIterator first, InputIterator last)迭代器区间初始化
(模板,可以传入其它容器的迭代器区间)

2.迭代器

函数功能
begin()加end()获取第一个数据位置的iterator/const_iterator,获取最后一个数据的下一个位置的iterator/const_iterator
rbegin()加rend()反向迭代器,获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

3.容量

函数功能
size()获取有效数据个数
empty()判断是否为空(size为0为空,返回true)

4.访问数据

函数功能
front()取到头节点数据的引用
back()返回尾节点数据的引用

5.增删查改

函数功能
push_front
(const value_type& val)
头插数据val
push_back
(const value_type& val)
尾删数据val
pop_front()头删
pop_back()尾删
insert (iterator position, const value_type& val)在position位置中插入值为val的元素
erase (iterator position)删除position位置的元素
swap(list& x)交换两个list
clear()清空有效数据

6.迭代器失效

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

#include<iostream>
#include<list>
using namespace std;//错误代码演示
int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后,it所指向的节点已被删除//因此it无效,在下一次使用it时,必须先给其赋值it = l.erase(it); //只需要去掉++it,这里修改成it = erase(it)即可++it;}return 0;
}



list模拟实现

1.迭代器的实现

      有别于vector,list的迭代器并不是一个原生的指针,因为使用者需要得到的是节点中的数据而不是整个节点,而且寻找下一个节点并不能通过指针简单的++,所以需要把迭代器单独封装成一个类,通过重载*等运算符来完成需求。

namespace MyList
{//节点设计成结构体,方便访问template<typename T>struct list_node{list_node(const T val = T()):_data(val), _next(nullptr), _prev(nullptr){}T _data;list_node<T>* _next;list_node<T>* _prev;};//迭代器//这里设计模板参数除了迭代器,还有Ref(引用)和Ptr(指针)//这样设计是为了同时生成普通迭代器和const对象的迭代器//普通对象(可读可写):iterator<T, T&, T*>//const对象(可读不可写):const_iterator<T, const T&, const T*>template<typename T, typename Ref, typename Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self; //要返回迭代器需要返回实例化对象,重命名一下Node* _node;__list_iterator(Node* p):_node(p){}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;}Ref operator*(){return _node->_data;}//返回指针可以让自定义类型自行打印,访问成员//->操作符,比较特殊,it->_num转换出来其实是it.operator->()->_numPtr operator->(){return &(_node->_data);}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//反向迭代器//反向迭代器需要进行封装,其实就是复用普通迭代器,然后++和--操作反过来//普通对象(可读可写):Reverse_iterator<iterator,T&,T*>//const对象(可读不可写):Reverse_iterator<const_iterator,const T&,const T*>template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> self;Iterator _it;//构造Reverse_iterator(Iterator it):_it(it){}self& operator++(){_it--;return *this;}self operator++(int){self tmp(*this);_it--;return tmp;}self& operator--(){_it++;return *this;}self operator--(int){self tmp(*this);_it++;return tmp;}Ref operator*(){return *_it;}Ptr operator->(){return _it;}bool operator!=(const self& s){return _it != s._it;}bool operator==(const self& s){return _it == s._it;}};
}

2.完整代码

#pragma once
#include<iostream>
using namespace std;namespace MyList
{//节点设计成结构体,方便访问template<typename T>struct list_node{list_node(const T val = T()):_data(val), _next(nullptr), _prev(nullptr){}T _data;list_node<T>* _next;list_node<T>* _prev;};//迭代器//这里设计模板参数除了迭代器,还有Ref(引用)和Ptr(指针)//这样设计是为了同时生成普通迭代器和const对象的迭代器//普通对象(可读可写):iterator<T, T&, T*>//const对象(可读不可写):const_iterator<T, const T&, const T*>template<typename T, typename Ref, typename Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self; //要返回迭代器需要返回实例化对象,重命名一下Node* _node;__list_iterator(Node* p):_node(p){}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;}Ref operator*(){return _node->_data;}//返回指针可以让自定义类型自行打印,访问成员//->操作符,比较特殊,it->_num转换出来其实是it.operator->()->_numPtr operator->(){return &(_node->_data);}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//反向迭代器//反向迭代器需要进行封装,其实就是复用普通迭代器,然后++和--操作反过来//普通对象(可读可写):Reverse_iterator<iterator,T&,T*>//const对象(可读不可写):Reverse_iterator<const_iterator,const T&,const T*>template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{typedef Reverse_iterator<Iterator, Ref, Ptr> self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}self& operator++(){_it--;return *this;}self operator++(int){self tmp(*this);_it--;return tmp;}self& operator--(){_it++;return *this;}self operator--(int){self tmp(*this);_it++;return tmp;}Ref operator*(){return *_it;}Ptr operator->(){return _it;}bool operator!=(const self& s){return _it != s._it;}bool operator==(const self& s){return _it == s._it;}};template<typename 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;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator< const_iterator, const T&, const T*> reverse_const_iterator;//迭代器部分iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}reverse_iterator rbegin(){return (--end());//_head->_prev}reverse_iterator rend(){return (end());//_head}reverse_const_iterator rbegin()const{return (--end());//_head->_prev}reverse_const_iterator rend()const{return (end());//_head}/// ///// private://不希望外界调用,设计成私有void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}public://构造、析构部分list(){empty_init();}list(size_t n, const T& value = T()){empty_init();while (n--){push_back(value);}}//重载给内置类型使用,整形默认是int,不写这个会优先匹配list(Iterator first, Iterator last)list(int n, const T& value = T()){empty_init();while (n--){push_back(value);}}//迭代器区间初始化template <class Iterator>list(Iterator first, Iterator last){empty_init();while(first != last){push_back(*first);first++;}}list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}//其它void swap(list<T> lt){std::swap(_size, lt._size);std::swap(_head, lt._head);}//使用传之传参,直接拷贝一份交换操作的底层空间就好list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}/// ////访问头,尾数据T& front(){return _head->_next->_data;}const T& front()const{return _head->_next->_data;}T& back(){return _head->_prev->_data;}const T& back()const{return _head->_prev->_data;}/// ///// //增加删除部分void push_back(const T& val){insert(end(), val);}void push_front(const T& val){insert(begin(), val);}iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;cur->_prev = newnode;newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;++_size;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}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 next;}//获取有效数据量size_t size(){return _size;}private:Node* _head;  //这里存储卫兵节点,因为底层是双向循环链表,可以找到头和尾size_t _size; //只需要在insert和erase里面加减就可以};}

相关文章:

C++:list使用以及模拟实现

list使用以及模拟实现 list介绍list常用接口1.构造2.迭代器3.容量4.访问数据5.增删查改6.迭代器失效 list模拟实现1.迭代器的实现2.完整代码 list介绍 list是一个类模板&#xff0c;加<类型>实例化才是具体的类。list是可以在任意位置进行插入和删除的序列式容器。list的…...

深度学习基础知识-pytorch数据基本操作

1.深度学习基础知识 1.1 数据操作 1.1.1 数据结构 机器学习和神经网络的主要数据结构&#xff0c;例如 0维&#xff1a;叫标量&#xff0c;代表一个类别&#xff0c;如1.0 1维&#xff1a;代表一个特征向量。如 [1.0&#xff0c;2,7&#xff0c;3.4] 2维&#xff1a;就是矩…...

Springboot使用QueryDsl实现融合数据查询

SpringbootQueryDsl技术 1、添加依赖 <!--基于JPA--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-jpa</artifactId> </dependency> <!--QueryDSL支持--> <dependenc…...

解决方案 | 电子签打通消费电子行业数智化经营通路

技术迭代不断驱动产业快速增长&#xff0c;从PC电脑到手机平板、再到可穿戴设备的兴起&#xff0c;每一次设备的迭代都代表着技术为产品注入了新的发展动能。与此同时&#xff0c;消费电子设备迭代更新周期的不断缩短&#xff0c;市场增长疲缓等因素&#xff0c;也对行业的流转…...

JVM理论知识

一、JVM内存结构 java的内存模型主要分为5个部分&#xff0c;分别是&#xff1a;JVM堆、JVM栈、本地栈、方法区还有程序计数器&#xff0c;他们的用途分别是&#xff1a; JVM堆&#xff1a;新建的对象都会放在这里&#xff0c;他是JVM中所占内存最大的区域。他又分为新生区还…...

idea - 报错 Mybatis提示Tag name expected的问题< 小于号 无法识别

问题&#xff1a;Mybatis提示Tag name expected 原因&#xff1a; 当我们在mapper中编写sql语句的时候会发现使用"<“符号会提示一个Tag name expected。这是因为xml文件中不识别”<"符号和“&”符号。防止与xml本身的元素命名混淆&#xff0c;导致无法解…...

合宙Air724UG LuatOS-Air LVGL API--对象

对象 概念 在 LVGL 中&#xff0c;用户界面的基本构建块是对象。例如&#xff0c;按钮&#xff0c;标签&#xff0c;图像&#xff0c;列表&#xff0c;图表或文本区域。 属性 基本属性 所有对象类型都共享一些基本属性&#xff1a; Position (位置) Size (尺寸) Parent (父母…...

Java将PDF文件转为Word文档

Java将PDF文件转为Word文档 一、创建Springboot Maven项目 二、导入依赖信息 <repositories><repository><id>com.e-iceblue</id><url>https://repo.e-iceblue.cn/repository/maven-public/</url></repository></repositories&g…...

vite创建项目命令

1.第一步运行创建命令&#xff08;npm&#xff09; npm create vitelatest也可以使用yarn yarn create vite还可以 pnpm create vite注意的地方&#xff1a;首次创建的时候会出现这个 Need to install the following packages:create-vitelatest Ok to proceed? (y) 直接y就…...

解决Pandas KeyError: “None of [Index([...])] are in the [columns]“问题

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

前端加springboot实现Web Socket连接通讯以及测试流程(包括后端实现心跳检测)

【2023】前端加springboot实现Web Socket连接通讯&#xff08;包括后端实现心跳检测&#xff09; 一级目录二级目录三级目录 前言一、Web Socket 简绍1 为什么用 websocket&#xff1f; 二、代码实现1、前端&#xff08;html&#xff09;1.1、无前端向后端发送消息1.2、有前端向…...

node使用高版本的oracledb导致连接oracle的Error: NJS-138异常

异常信息如下 Error: NJS-138: connections to this database server version are not supported by node-oracledb in Thin mode 我的oracle版本是11g&#xff0c;之前的使用正常&#xff0c;今天却报错了&#xff0c;显示不支持thin模式&#xff0c;后面回退版本就可以了。...

RabbitMQ手动签收消息

RabbitMQ手动签收消息 这里讲解SpringBoot使用RabbitMQ进行有回调的用法和消费者端手动签收消息的用法。 1、pom依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"h…...

Unity 3d角色展示脚本(旋转 平移 缩放)展示界面

不考虑性能 很简陋的一个功能&#xff0c;主要是用于角色渲染的观察用&#xff0c;比simplecontroller要好用一点 using System; using UnityEngine;public class CharacterViewer : MonoBehaviour {public Transform target; // 人物模型的Transformpublic float rotationSpee…...

Spring Boot 将 Word 转换为 PDF

首先&#xff0c;确保项目中添加了对Apache POI和Apache PDFBox的依赖。可以在你的 pom.xml 文件中添加以下依赖&#xff1a; <dependencies><!-- Apache POI --><dependency><groupId>org.apache.poi</groupId><artifactId>poi</arti…...

【PHP面试题82】system和exec是用来做什么的?有什么区别

文章目录 &#x1f680;一、前言&#xff0c;PHP中system和exec命令的作用&#x1f680;二、system()函数&#x1f680;三、exec()函数&#x1f680;四、区别和应用场景&#x1f50e;4.1 使用system()函数的应用场景&#x1f50e;4.2 使用exec()函数的应用场景&#x1f50e;4.3…...

05-微信小程序常用组件-表单组件

05-微信小程序常用组件-表单组件 文章目录 表单组件button 按钮案例代码 form 表单案例代码 image 图片支持长按识别的码案例代码 微信小程序包含了六大组件&#xff1a; 视图容器、 基础内容、 导航、 表单、 互动和 导航。这些组件可以通过WXML和WXSS进行布局和样式设…...

Lucky player —— Java 项目(Spring Boot)

一、项目介绍 项目名称&#xff1a;lucky player 项目的主要功能&#xff1a;本系统主要功能为构建了一个用户分享音乐的平台&#xff0c;普通用户不进行登录即可收听其他用户已经发布的专辑中的音乐。 作为博主则可以在该平台上传音频&#xff0c;以及在线音频录制上传。音频上…...

ios 声网agora 音视频直播场景下的集成总结

文章目录 一、前言二、视频会议场景2.1 场景描述2.2 功能列表三、电商直播场景3.1 场景描述3.2 功能列表3.3 技术方案四、声网iOS SDK集成4.1 集成4.2 示例demo4.3 核心代码4.3.1 初始化4.3.2 加入频道4.3.3 切换身份4.4.4 连麦4.4 相关问题4.4.1 监听观众角色用户事件五、相关…...

mysql 、sql server 临时表、表变量、

sql server 临时表 、表变量 mysql 临时表 创建临时表 create temporary table 表名 select 字段 [&#xff0c;字段2…&#xff0c;字段n] from 表...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...