C++---list常用接口和模拟实现
list---模拟实现
- list的简介
- list函数的使用
- 构造函数
- 迭代器的使用
- list的capacity
- list element access
- list modifiers
- list的模拟实现
- 构造函数,拷贝构造函数和=
- 迭代器
- begin和end
- insert和erase
- clear和析构函数
- 源码
list的简介
list是用双向带头联表实现的一个容器,双向联表中每个元素存在互不相关的独立节点中,再节点中通过指针指向其前一个元素和后一个元素,并且可以再常数范围内再任意位置进行插入和删除的序列式容器。
list函数的使用
构造函数
构造函数( (constructor)) | 接口说明 |
---|---|
list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list() | 构造空的list |
list (const list& x) | 拷贝构造函数 |
list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
void ListTest2()
{std::list<int> a(4, 5);std::cout << "a的list" << ':';for (auto& e : a){std::cout << e << ' ';}std::cout << std::endl;std::list<int> b;//Emptystd::list<int> c(a.begin(), a.end());std::cout << "c的list" << ':';for (auto& e : c){std::cout << e << ' ';}}
迭代器的使用
函数声明 | 接口说明 |
---|---|
begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
rbegin + rend | 返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
std::list<int> a(4, 5);std::cout << "a的list" << ':';std::list<int>::iterator it = a.begin();while (it != a.end()){std::cout << *it << ' ';++it;}
list的capacity
函数声明 | 接口说明 |
---|---|
empty | 检测list是否为空,是返回true,否则返回false |
size | 返回list中有效节点的个数 |
list element access
函数声明 | 接口说明 |
---|---|
front | 返回list的第一个节点中值的引用 |
back | 返回list的最后一个节点中值的引用 |
list modifiers
函数声明 | 接口说明 |
---|---|
push_front | 在list首元素前插入值为val的元素 |
pop_front | 删除list中第一个元素 |
push_back | 在list尾部插入值为val的元素 |
pop_back | 删除list中最后一个元素 |
insert | 在list position 位置中插入值为val的元素 |
erase | 删除list position位置的元素 |
swap | 交换两个list中的元素 |
clear | 清空list中的有效元素 |
list的模拟实现
要想模拟实现list,首先我们可以定义一个节点类。为什么要定义一个节点类呢,想想数据结构中的双链表,每个元素都在独立的节点中,通过节点的前驱指针和后继指针指向前后位置。
list的模拟实现跟vector和string实现是不一样的,vector本质上是一个数组,数组本身就是一个迭代器,而list是一个个的节点,通过指针联系在一起,所以vector类不用对迭代器进行封装,可以直接使用,list不一样,节点++是什么是不清楚的,这个时候可以使用运算符重载,对++,–,*等进行重载。
template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};
再定义一个list类,再这个类中,完成其他函数的实现
template<class T>class list{public:private:Node* _head;size_t _size;};
构造函数,拷贝构造函数和=
list的构造函数实现,跟双链表中的初始化是一样的,将next指针和prev指针都指向头节点,形成一个环。
void EmptyInit(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}
拷贝构造函数再拷贝之前,要先开一个头节点的空间,然后再头节点后面依次把值进行尾插即可。
list(const list<T>& it){EmptyInit();for (auto& e : it){push_back(e);}}
赋值重载=和vector里面的写法是一样的。
list<T>& operator=(list<T> it){swap(it);return *this;}
通过传参创建出一个临时变量,然后将其交换。
迭代器
要想实现list的迭代器,需要将原生态指针进行封装。
list是由一个个的节点组成,节点++,解引用,–,等操作是找不到对应的数据的,所以需要用自定义类型对指针进行封装,从而完成一系列操作。
迭代器有一个const类型的迭代器,有一个无const类型的,再实现一个无const类型的迭代器之后,把代码赋值粘贴,也可以改成带const类型的迭代器,但这样显然是代码冗余的,重复的太多,这个时候,那些大佬们就通过增加模板参数,来解决代码冗余,根据参数的类型,实列化出不同的类。
//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T,const T&,const T*> const_iterator;
template<class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;//构造方法__list_iterator(Node* node):_node(node){}//对节点解引用,是找不到我们存储的数据的,因为节点里面存的是val,next和prev,重载的目是使其对迭代器解引用可以找到有效数据Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->val);}//指针++,到下一个位置,其实就是让节点向后移动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 *this;}bool operator !=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};
以上就是用自定义的类,对指针进行封装。
begin和end
对指针进行封装之后,就可以实现begin和end了。
begin只要返回头节点的下一个节点即可
end就是头节点
iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}
insert和erase
有一个insert,就可以完成再任意位置插入。
void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;return newnode;}
先找到当前节点cur和当前节点的上一个节点prev,再new出一个要插入的节点newnode,使得cur和newnode进行双向连接,prev和newnode进行双向连接。
删除一个节点,只需要让当前节点的上一个节点和下一个节点完成双向连接即可。
iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}
clear和析构函数
void clear(){iterator it = begin();while (it != end()){it = earse(it);}_size = 0;}~list(){}
源码
#pragma once#include <assert.h>
#include <algorithm>namespace HaiFan
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};template<class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}T* operator->(){return &(_node->val);}T& operator++(){_node = _node->_next;return *this;}T operator++(int){self tmp(*this);_node = _node->_next;return tmp;}T& operator--(){_node = _node->_prev;return *this;}T operator--(int){self tmp(*this);_node = _node->prev;return *this;}bool operator !=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};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;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}list(){EmptyInit();}list(const list<T>& it){EmptyInit();for (auto& e : it){push_back(e);}}list<T>& operator=(list<T> it){swap(it);return *this;}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}void clear(){iterator it = begin();while (it != end()){it = earse(it);}_size = 0;}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());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end());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;}void EmptyInit(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}~list(){}private:Node* _head;size_t _size;};
}
相关文章:

C++---list常用接口和模拟实现
list---模拟实现 list的简介list函数的使用构造函数迭代器的使用list的capacitylist element accesslist modifiers list的模拟实现构造函数,拷贝构造函数和迭代器begin和endinsert和eraseclear和析构函数 源码 list的简介 list是用双向带头联表实现的一个容器&…...

[openCV]基于赛道追踪的智能车巡线方案V1
import cv2 as cv import os import numpy as npimport time# 遍历文件夹函数 def getFileList(dir, Filelist, extNone):"""获取文件夹及其子文件夹中文件列表输入 dir:文件夹根目录输入 ext: 扩展名返回: 文件路径列表""&quo…...

SpringIoc-个人学习笔记
Spring的Ioc、DI、AOP思想 Ioc Ioc思想:Inversion of Control,控制反转,在创建Bean的权利反转给第三方 DI DI思想:Dependency Injection,依赖注入,强调Bean之间的关系,这种关系由第三方负责去设…...
【一文搞懂泛型】
3.3泛型 3.3.1泛型出现的背景 泛型出现的背景有两点: 第一点是在集合容器中,如果没有指定对应类型的话,那么底层的元素就是object,要对容器中的元素进行存取的时候,取出来的同时需要进行类型转换,如果有…...
概念解析 | 利用MIMO雷达技术实现高性能目标检测的关键技术解析
注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:MIMO雷达目标检测技术 参考资料:何子述, 程子扬, 李军, 等. 集中式 MIMO 雷达研究综述[J]. 雷达学报, 2022, 11(5): 805-829. 利用MIMO雷达技术实现高性能目标检测的关键技术解…...

Grafana制作图表-自定义Flink监控图表
简要 有时候我们在官网的Grafana下载的图表是这样的,如下图 #算子的处理时间,就是处理数据的延迟数据抓取,这个的说明看下下面的文章 metrics.latency.interval: 60 metrics.reporter.promgateway.class: org.apache.flink.metrics.prometh…...

【TypeScript】初识TypeScript和变量类型介绍
TypeScript 1,TypeScript是什么?2,类型的缺失带来的影响3,Ts搭建环境-本博主有专门的文章专说明这个4,使用tsc对ts文件进行编译5,TS运行初体验简化Ts运行步骤解决方案1解决方案2(常见) 开始学习…...

阿里云瑶池 PolarDB 开源官网焕新升级上线
导读近日,阿里云开源云原生数据库 PolarDB 官方网站全新升级上线。作为 PolarDB 开源项目与开发者、生态伙伴、用户沟通的平台,将以开放、共享、促进交流为宗旨,打造开放多元的环境,以实现共享共赢的目标。 立即体验全新官网&…...
泡水书为什么不能再出售
近日,京津冀持续强降雨,多家出版机构位于涿州等地的图书库房受到影响。 中图网11日发文称,其位于涿州的仓储中心被洪水淹了,一库房有400多万册的书籍。 网友纷纷在文章下暖心留言:注意人身安全,泡水的书也…...
Mac 执行 .sh命令报错 command not found
使用终端执行.sh命令,可输入: ./FileName.sh如果提示 Permission denied 权限不足,可增加sudo,命令如下: sudo ./FileName.sh如果提示 command not found 可以这样: chmod ux *.sh sudo ./FileName.sh...

postgresql 使用之 存储架构 触摸真实数据的存储结构以及组织形式,存入数据库的数据原来在这里
存储架构 专栏内容: postgresql内核源码分析 手写数据库toadb 并发编程 个人主页:我的主页 座右铭:天行健,君子以自强不息;地势坤,君子以厚德载物. 概述 postgresql 数据库服务运行时,数据在磁…...

Node.Js安装与配置教程
目录 1.下载官网 2.选择安装路径 3.添加环境变量 4.验证是否安装成功 5.修改模块下载位置 (1)查看npm默认存放位置 6.在node.js安装目录下,创建两个文件夹 7.修改默认文件夹 8.测试默认位置是否更改成功 9.安装报错解决办法 10.路径未更改成功解决办法 …...

Element-Plus DatePicker获取时间戳
文章目录 0、先上答案1、渔?1-1 Element-Plus 官网1-2 溯源 Day.js 0、先上答案 <!-- 秒 --><el-date-pickerv-model"timeStamp"type"datetime"value-format"X"/><!-- 毫秒 --><el-date-pickerv-model"tim…...
【算法第十五天7.29】513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树
链接力扣513-找树左下角的值 思路 class Solution {public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue new LinkedList<>();queue.offer(root);int res 0;while(!queue.isEmpty()){int size queue.size();for(int i 0; i < size; i)…...

Java thymeleaf bug排查记录
刚学Java 做项目时报了一个错误 一时间看的莫名其妙 EL1008E: Property or field createTime cannot be found on object of type java.util.HashMap - maybe not public or not valid? 随即向上排查至第一个报错,发现是thymeleaf渲染时报错。 Exception proces…...

互感和励磁电感(激磁电感)的关系
互感器,变压器,他们之间有着千丝万缕的联系,自感,互感,激磁电感,漏感、耦合系数、理想互感器、理想变压器,这些东西的概念理解和相互之间的关系式。都搞明白了吗?...
stdexcept和exception,两个头文件的区别?
stdexcept和exception是C标准库中的两个头文件,它们的区别如下: 1. 引用方式:stdexcept是exception的父类,引用时可以通过引用stdexcept来自动引用exception,也可以直接引用exception。 2. 异常处理:std…...
openCV图像的读写操作
文章目录 一、数组下标二、指针 void QuickDemo::pixel_visit_demo(cv::Mat &image) {int w image.cols;int h image.rows;int dim image.channels();for (int row 0; row < h; row){for (int col 0; col < w; col){if (dim 1)//灰度图像{int pv image.at<…...

Android平台GB28181设备接入端如何降低资源占用和性能消耗
背景 我们在做GB28181设备接入模块的时候,考虑到好多设备性能一般,我们一般的设计思路是,先注册设备到平台侧,平台侧发calalog过来,获取设备信息,然后,设备侧和国标平台侧维持心跳,…...

Android Studio安装AI编程助手Github Copilot
csdn原创谢绝转载 简介 文档链接 https://docs.github.com/en/copilot/getting-started-with-github-copilot 它是个很牛B的编程辅助工具,装它,快装它. 支持以下IDE: IntelliJ IDEA (Ultimate, Community, Educational)Android StudioAppC…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...