C++的List
List的使用
构造


与vector的区别
与vector的区别在于不支持 [ ]
由于链表的物理结构不连续,所以只能用迭代器访问
vector可以排序,list不能排序(因为快排的底层需要随机迭代器,而链表是双向迭代器)
(算法库里的排序不支持)(需要单独的排序)
list存在vector不支持的功能

链表的排序
vector可以用算法库里的sort排序,list不能用算法库里的sort排序排序(因为快排的底层需要随机迭代器,而链表是双向迭代器)
(算法库里的排序不支持)(需要单独的排序)
链表的排序效率要远低于算法库里的快排,因此链表的sort很少使用
即使将list拷贝会vector排序再拷贝回来,效率依旧大于直接在list中排序

升序

降序

去重(unique)
去除多个重复的数据,每个值只留一个
但是去重有一个前提,需要先排序,否则去不全


迭代器访问链表

list的剪切
将一个链表的内容转移(剪切)到另一个链表


也可以自己剪切自己,来把某个节点向前或后移动

list变为"3 1 2 4"
List的实现(双向带头循环)
链表基础结构

_head是双向带头循环链表的哨兵位(不存储有效数据)
list的迭代器
与vector不同,list在物理上是不连续的
因此不能像vector一样

因为这样++iterator不能得到下一个节点
因此可以选择建立一个类来进行封装

可以在该类中重载 " ++ " 和 " * "等运算符
是迭代器可以实现作用


但是注意不需要重载 " + "和 " - " ,因为他们的效率很低
同时,迭代器类不需要写析构函数
因为节点不属于迭代器,只是需要用迭代器访问
节点是属于链表的
也不需要写拷贝构造(深拷贝),默认生成的浅拷贝就够了
因为没有写析构,所以也不存在析构两次的问题
->的重载
迭代器内还重载了 " -> "运算符
eg.
对于自定义类型



想要进行输出,又没有重载>>符号
方法一
比较原始的方法:

方法二

这里就是重载了 " -> "符号

从逻辑上讲
方法2应该有两个->,但是为了代码的可读性,省略了一个->

const迭代器

采用引用传参一般会给参数加const,就产生了const迭代器
但是注意

所以需要单独写一个类,让迭代器可以修改,但它指向的内容不能修改(控制返回值)
该类与之前写的迭代器的类非常相似,唯一的区别就是operator* 和operator->的返回值不同
迭代器不能修改的核心行为是operator* 和operator->

控制operator* 和operator->的返回值,从而达成不能修改的目的
但是,以上两个类重复度很高,重写一个类过于浪费
因此可以采取新添加两个模板参数

写一个类模板,传不同的模板参数,来控制返回值
这样相当于利用模板生成了两个类,交给编译器来完成
提高了开发效率
插入insert


链表里的insert不存在迭代器失效的问题,因为它不存在扩容
pos指向的位置也不会变
删除erase

erase存在迭代器失效的问题
是野指针失效
拷贝
默认的浅拷贝存在一定的问题
eg.

因为浅拷贝,指向同一块空间,会相互影响,析构两次
析构函数

这里用clear()清除数据
深拷贝

在范围for时,如果不确定遍历的类型,最好加引用&
赋值

直接交换两个链表的头节点就行
因为传入的参数不是引用,lt是lt3的临时拷贝,使用完后就会释放
交换头节点后,不仅实现了赋值,还顺便将原链表析构了
initializer_list
为了支持{ }赋值,需要写一个initializer_list

参数不用加引用&
因为initializer_list直接用{ }初始化,里面是常量数组
里面是直接用指针指向常量数组的开始和结束


模拟实现
#pragma once
#include <iostream>
using namespace std;
namespace bit
{template<class T>struct ListNode//定义一个链表节点的结构体//因为结构体内的东西全部公有,所以选择结构体,而不是类//一个类有公有私,用class,全部公有,用struct{ListNode<T>* _next;ListNode<T>* _prev;//结构体指针后加<T>模板,否则结构体指针就无法指向该类型的数据T _data;ListNode(const T& data = T())//初始化: _next(nullptr), _prev(nullptr), _data(data)//初始化列表{}};template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;public://++itListIterator(Node* node):_node(node){}Self& operator++()//前置{_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int)//后置{Self tmp = *this;_node = _node->_next;return tmp;}Self operator--(int){Self tmp = *this;_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}};//template<class T>//class ListConstIterator//{// typedef ListNode<T> Node;// typedef ListConstIterator<T> Self;// Node* _node;//public:// //++it// ListIterator(Node* node)// :_node(node)// {}// Self& operator++()//前置// {// _node = _node->_next;// return *this;// }// Self& operator--()// {// _node = _node->_prev;// return *this;// }// Self operator++(int)//后置// {// Self tmp = *this;// _node = _node->_next;// return tmp;// }// Self operator--(int)// {// Self tmp = *this;// _node = _node->_prev;// return tmp;// }// const T& operator*()// {// return _node->_data;// }// const T* operator->()// {// return &_node->_data;// }// bool operator!=(const Self& it)// {// return _node != it._node;// }//};template<class T>class list//链表{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&,const T*> const_iterator;/* typedef ListConstIterator<T> const_iterator;*/iterator begin(){return iterator(_head->_next);//传入匿名对象构造一个iterator类型的变量来返回}iterator end(){return iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}list(){/*_head = new Node(T());_head->_next = _head;_head->_prev = _head;*/empty_init();} list(initializer_list<T> il){for (const auto& e : il){push_back(e);}}//lt2(lt1)list(const list<T>& It)//深拷贝构造{empty_init();for (const auto& e : lt){push_back(e);}}//lt1 = lt3list<T>& operator=(list<T> lt){swap(_head, lt._head);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}void erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};void test_list1(){list<int> It1;It1.push_back(1);It1.push_back(2);It1.push_back(3);It1.push_back(4);list<int>::iterator it = It1.begin();while (it != It1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;}
}
相关文章:
C++的List
List的使用 构造 与vector的区别 与vector的区别在于不支持 [ ] 由于链表的物理结构不连续,所以只能用迭代器访问 vector可以排序,list不能排序(因为快排的底层需要随机迭代器,而链表是双向迭代器) (算法库里的排序不支持)(需要单独的排序) list存在vector不支持的功能 链…...
网易有道QAnything使用CPU模式和openAI接口安装部署
网易有道QAnything可以使用本地部署大模型(官网例子为qwen)也可以使用大模型接口(OPENAI或者其他大模型AI接口 )的方式,使用在线大模型API接口好处就是不需要太高的硬件配置。 本机环境windows11 首先安装WSL环境, 安装方法参考https://zhuan…...
量子加速超级计算简介
本文转载自:量子加速超级计算简介(2024年 3月 13日) By Mark Wolf https://developer.nvidia.cn/zh-cn/blog/an-introduction-to-quantum-accelerated-supercomputing/ 文章目录 一、概述二、量子计算机的构建块:QPU 和量子位三、量子计算硬件和算法四、…...
Unity3D 基于YooAssets的资源管理详解
前言 Unity3D 是一款非常流行的游戏开发引擎,它提供了丰富的功能和工具来帮助开发者快速创建高质量的游戏和应用程序。其中,资源管理是游戏开发中非常重要的一部分,它涉及到如何有效地加载、管理和释放游戏中的各种资源,如模型、…...
Linux 自动化升级Jar程序,指定Jar程序版本进行部署脚本
文章目录 一、环境准备二、脚本1. 自动化升级Jar程序2. 指定Jar程序版本进行部署总结一、环境准备 本文在 CentOS 7.9 环境演示,以springboot为例,打包后生成文件名加上版本号,如下打包之后为strategy-api-0.3.2.jar: pom.xml<?xml version="1.0" encoding=&…...
python练习五
Title1:请实现一个装饰器,每次调用函数时,将函数名字以及调用此函数的时间点写入文件中 代码: import time time time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()) # 获取当前的时间戳 # 定义一个有参装饰器来实…...
YOLOv1深入解析与实战:目标检测算法原理
参考: https://zhuanlan.zhihu.com/p/667046384 https://blog.csdn.net/weixin_41424926/article/details/105383064 https://arxiv.org/pdf/1506.02640 1. 算法介绍 学习目标检测算法,yolov1是必看内容,不同于生成模型,没有特别…...
Apache Calcite - 自定义标量函数
前言 上一篇文章中我们介绍了calcite中内置函数的使用。实际需求中会遇到一些场景标准内置函数无法满足需求,这时候就需要用到自定义函数。在 Apache Calcite 中添加自定义函数,以便在 SQL 查询中使用自定义的逻辑。这对于执行特定的数据处理或分析任务…...
STM32作业实现(四)光敏传感器
目录 STM32作业设计 STM32作业实现(一)串口通信 STM32作业实现(二)串口控制led STM32作业实现(三)串口控制有源蜂鸣器 STM32作业实现(四)光敏传感器 STM32作业实现(五)温湿度传感器dht11 STM32作业实现(六)闪存保存数据 STM32作业实现(七)OLED显示数据 STM32作业实现(八)触摸按…...
HTML+CSS 文本动画卡片
效果演示 实现了一个图片叠加文本动画效果的卡片(Card)布局。当鼠标悬停在卡片上时,卡片上的图片会变为半透明,同时显示隐藏在图片上的文本内容,并且文本内容有一个从左到右的渐显动画效果,伴随着一个白色渐…...
MongoDB CRUD操作: 在本地实例进行文本搜索查询
MongoDB CRUD操作: 在本地实例进行文本搜索查询 文章目录 MongoDB CRUD操作: 在本地实例进行文本搜索查询举例创建集合创建文本索引精准搜索排除短语结果排序 在本地实例运行文本搜索查询前,必须先在集合上建立文本索引。MongoDB提供文本索引…...
文档智能开源软件
文档智能介绍: 文档智能通常指的是利用人工智能技术来处理和分析文档内容,以实现自动化、智能化的文档管理。文档智能的应用领域非常广泛,包括但不限于: 1. **文档识别**:使用OCR(光学字符识别࿰…...
[C][可变参数列表]详细讲解
目录 1.宏含义及使用2.宏原理分析1.原理2.宏理解 1.宏含义及使用 依赖库stdarg.hva_list 其实就是char*类型,方便后续按照字节进行指针移动 va_start(arg, num) 使arg指向可变参数部分(num后面) va_arg(arg, int) 先让arg指向下个元素,然后使用相对位置…...
54. 螺旋矩阵【rust题解】
题目 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 示例 1 输入:matrix [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5] 示例 2 输入:matrix [[1,2,3,4],[5,6,…...
学习笔记——网络参考模型——TCP/IP模型(传输层)
四、TCP/IP模型-传输层 一、TCP 1、TCP定义 TCP(Transmission Control Protocol,传输控制协议)∶为应用程序提供可靠的面向连接的通信服务。目前,许多流行的应用程序都使用TCP。 连接:正式发送数据之前,提前建立好一种虚拟的&…...
Java中的Instant
在Java中,Instant 是 java.time 包中的一个类,用于表示时间轴上的一个瞬时点,通常以纳秒精度表示。它通常用于表示机器可读的时间戳,而不是人类可读的时间表示(如日期和时间)。 Instant 主要用于时间计算和…...
PostgreSQL的锁介绍
PostgreSQL的锁介绍 PostgreSQL 中的锁机制是一种用于控制数据并发访问的手段,确保数据库的完整性和一致性。在实际应用中,合理使用锁可以避免数据不一致和减少死锁的发生。 锁类型 PostgreSQL 提供了多种锁类型,以下是一些常见的锁&#…...
4分之1外螺纹怎么编程:挑战与策略解析
4分之1外螺纹怎么编程:挑战与策略解析 在机械制造领域,螺纹编程是一项至关重要的技术任务。当面对如4分之1外螺纹这样的具体需求时,编程人员需要综合运用专业知识与编程技巧,以确保螺纹的精确度和生产效率。本文将围绕四个方面、…...
运用selenium爬取京东商品数据储存到MySQL数据库中
使用Selenium爬取京东商品数据并存储到MySQL数据库中的过程可以分为几个步骤: 1. 准备工作 安装所需库 确保你已经安装了Python环境以及以下库: selenium:用于自动化浏览器操作。pymysql 或 mysql-connector-python:用于连接M…...
K8S SWCK SkyWalking全链路跟踪工具安装
官方参考:如何使用java探针注入器? 配置两个demo,建立调用关系, 首先创建一个基础镜像dockerfile from centos 先安装java 参考: linux rpm方式安装java JAVA_HOME/usr/java/jdk1.8.0-x64 CLASSPATH.:$JAVA_HOME/lib/tools.jar PATH…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...


