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

C++ 学习系列 -- std::list

一  std::list 介绍

       list 是 c++ 中的序列式容器,其实现是双向链表,每个元素都有两个指针,分别指向前一个节点与后一个节点

      链表与数组都是计算机常用的内存数据结构,与数组连续内存空间不一样的地方在于,链表的空间是不连续的,链表是将一块块不连续的内存串联起来使用。

    正是由于链表的内存不连续这一特点,所以不能像数组一样,可以根据位置随机的访问每个元素,而链表我们压根不知道每个元素的实际位置到底在哪块内存区域。

     查找某个元素需要遍历整个链表,直到找到目标元素位置,时间复杂度是 O(n);

    在链表中插入一个元素与删除一个元素的时间复杂度是 O(1);

二   c++ 中 stl 链表结构

1. list 结构

   list  结构 (借用侯捷老师的一张图片来):

  

  由上面的结构上可以看出,list 是一个循环链表,链表的尾端是一个空节点,不存储任何数据。

三   c++ 中 stl 链表使用

 1  构造函数

构造函数说明
list()空构造函数
list( size_type count, const T& value)初始化一个元素数量为 count 个的 value 元素
list( std::initializer_list<T> init)利用列表初始化 list
list( InputIt first, InputIt last)利用迭代器的起始于终止位置初始化 list

 2   容器修改

函数说明
clear() 清空所有元素
insert在指定位置插入元素
emplace在指定位置插入元素, 可以通过直接传入元素类的构造参数实现原地构造
erase移除指定元素
push_backappend 元素到链表的尾部
pop_back将链表尾部元素弹出
push_frontappend 元素到链表的头部
pop_front将链表头部元素弹出
emplace_backappend 元素到链表的尾部, 可以通过直接传入元素类的构造参数实现原地构造
emplace_frontappend 元素到链表的头部, 可以通过直接传入元素类的构造参数实现原地构造

 3  容器访问

函数说明
begin返回头部元素的迭代器
end返回尾部元素的迭代器
rbegin返回尾部元素的迭代器
rend返回头部元素的迭代器
front返回头部元素的引用
back返回尾部元素的引用

4  容器容量

函数说明
empty判断 list是否为空
size返回 list 存储元素的个数
#include<iostream>
#include<list>int main()
{// 1. 构造函数std::list<int> list;auto iter = list.begin();std::cout << *iter << "--- " << std::endl;;// 2. 容器修改list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);list.push_front(11);list.push_front(22);list.pop_back();list.pop_front();list.insert(list.begin(), 666);// 3. 容器访问for(auto iter = list.begin(); iter != list.end();iter++){std::cout << *iter << " "; // 666 11 1 2 3 4}std::cout << "" << std::endl;for(auto iter = list.rbegin(); iter != list.rend();iter++){std::cout << *iter << " "; // 4 3 2 1 11 666}std::cout << "" << std::endl;std::cout << "first: " << list.front() << ", finish: " << list.back() << std::endl; // first: 666, finish: 4// 4. 容器容量std::cout << "empyt: " << list.empty() << std::endl; // 0std::cout << "size: "<< list.size() << std::endl; // 6list.clear();std::cout << "empyt: " << list.empty() << std::endl; // 1std::cout << "size: "<< list.size() << std::endl; // 0return 0;
}

四  简单实现

  

// my_list.h#include<memory>
#include<iostream>template<typename T>
struct _List_Node
{typedef _List_Node node;_List_Node(){prev = nullptr;next = nullptr;}_List_Node(T& da):data(da){prev = nullptr;next = nullptr;}_List_Node(T&& da):data(da){prev = nullptr;next = nullptr;}~_List_Node(){prev = nullptr;next = nullptr;}node* prev;node* next;T data;
};template<typename T>
struct _List_Iterator
{typedef T valueType;typedef T& refrence;typedef T* pointer;typedef  _List_Node<T> node;_List_Iterator(node* val):data(val){}_List_Iterator& operator++(){this->data = this->data->next;return *this;}_List_Iterator operator++(int){_List_Iterator tmp = *this;++(*this);return tmp;}_List_Iterator& operator--(){this->data = this->data->prev;return *this;}_List_Iterator operator--(int){_List_Iterator tmp = *this;--(*this);return tmp;}T& operator*(){return this->data->data;}bool operator != (_List_Iterator& other){return this->data != other->data;}bool operator == (_List_Iterator& other){return this->data == other.data;}bool operator != (_List_Iterator&& other){return this->data != other.data;}bool operator == (_List_Iterator&& other){return this->data == other.data;}node*  data;
};template<typename T>
class my_list
{typedef  _List_Node<T>  node;typedef  _List_Iterator<T> iterator;
public:my_list():count(0){next_curr = new node;pre_curr = next_curr;finish = new node;next_curr->next = finish;finish->next = next_curr;pre_curr->prev = finish;finish->prev = pre_curr;}~my_list(){node* tmp = pre_curr;while (tmp != nullptr) {node* tt = tmp->next;delete tmp;tmp = tt;}}void push_back(T& val){std::cout << "count: " << count << std::endl;if(count == 0)next_curr->data = val;else {node* tmp = new node(val);tmp->next = next_curr->next;tmp->next->prev = tmp;next_curr->next = tmp;tmp->prev = next_curr;next_curr = next_curr->next;}count++;}void push_back(T&& val){push_back(val);}void push_front(T& val){if(count == 0)pre_curr->data = val;else {node* tmp = new node(val);tmp->prev = pre_curr->prev;pre_curr->prev->next = tmp;tmp->next = pre_curr;pre_curr->prev = tmp;pre_curr = pre_curr->prev;}count++;}void push_front(T&& val){push_front(val);}void pop_back(){if(count == 0){return;} else{node* tmp = next_curr;next_curr->prev->next = next_curr->next;next_curr->next->prev = next_curr->prev;next_curr = next_curr->prev;delete tmp;count--;}}void pop_front(){if(count == 0){return;} else{node* tmp = pre_curr;finish->next = pre_curr->next;pre_curr->next->prev = finish;pre_curr = pre_curr->next;delete tmp;count--;}}int size(){return count;}iterator begin(){return iterator(pre_curr);}iterator end(){return iterator(finish);}iterator rbegin(){return iterator(finish->prev);}iterator rend(){return iterator(pre_curr->prev);}void insert(iterator pos, T& val){node* tmp = new node(val);pos.data->prev->next = tmp;tmp->prev = pos.data->prev;tmp->next = pos.data;pos.data->prev = tmp;if(pos.data == pre_curr){pre_curr = pre_curr->prev;}else if(pos.data == next_curr){next_curr = next_curr->next;}count++;}void insert(iterator pos, T&& val){insert(pos, val);}template<typename ... Args>void emplace(iterator pos, Args... args){node* tmp = new node(std::forward<Args>(args)...);pos.data->prev->next = tmp;tmp->prev = pos.data->prev->next;tmp->next = pos.data;pos.data->prev = tmp;count++;}void erase(iterator pos){node* tmp = pos.data;tmp->prev = tmp->next;delete tmp;count--;}void clear(){while (pre_curr->next != finish) {pop_back();}count = 0;}T& front(){return pre_curr->data;}T& back(){return next_curr->data;}bool empty(){return count == 0;}public:node* next_curr = nullptr;node* pre_curr = nullptr;node* finish = nullptr;int count;
};// main.cpp
#include<iostream>
#include<my_list.h>int main()
{// 1. 构造函数my_list<int> list;// 2. 容器修改list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);list.push_front(11);list.push_front(22);// 22 11 1 2 3 4 5list.pop_back();list.pop_front();list.insert(list.begin(), 666);// 3. 容器访问for(auto iter = list.begin(); iter != list.end();iter++){std::cout << *iter << " "; // 666 11 1 2 3 4}std::cout << "" << std::endl;for(auto iter = list.rbegin(); iter != list.rend();iter--){std::cout << *iter << " "; // 4 3 2 1 11 666}std::cout << "" << std::endl;std::cout << "first: " << list.front() << ", finish: " << list.back() << std::endl; // first: 666, finish: 4// 3. 容器容量std::cout << "empty: " << list.empty() << std::endl; // 0std::cout << "size: "<< list.size() << std::endl; // 6list.clear();std::cout << "empyt: " << list.empty() << std::endl; // 1std::cout << "size: "<< list.size() << std::endl; // 0return 0;
}

相关文章:

C++ 学习系列 -- std::list

一 std::list 介绍 list 是 c 中的序列式容器&#xff0c;其实现是双向链表&#xff0c;每个元素都有两个指针&#xff0c;分别指向前一个节点与后一个节点 链表与数组都是计算机常用的内存数据结构&#xff0c;与数组连续内存空间不一样的地方在于&#xff0c;链表的空间是不…...

YOLOv8血细胞检测(6):多维协作注意模块MCA | 原创独家创新首发

💡💡💡本文改进:多维协作注意模块MCA,效果秒杀ECA、SRM、CBAM,创新性十足,可直接作为创新点使用。 MCA | 亲测在血细胞检测项目中涨点,map@0.5 从原始0.895提升至0.910 收录专栏: 💡💡💡YOLO医学影像检测:http://t.csdnimg.cn/N4zBP ✨✨✨实战医学影…...

FFmpeg横竖版视频互换背景模糊一键生成

视频处理是现代多媒体应用中常见的需求。其中横竖版视频互换和背景模糊是视频编辑中常见的操作。FFmpeg是一个功能强大的工具,适用于这些任务。 本文将详细介绍如何使用FFmpeg进行横竖版视频互换和背景模糊。 文章目录 操作命令与命令说明横版转竖版竖版转横版背景模糊处理横…...

Java 华为真题-小朋友分班

需求&#xff1a; 题目描述 幼儿园两个班的小朋友在排队时混在了一起&#xff0c;每位小朋友都知道自己是否与前面一位小朋友同班&#xff0c;请你帮忙把同班的小朋友找出来小朋友的编号是整数&#xff0c;与前一位小朋友同班用Y表示&#xff0c;不同班用N表示学生序号范围(0&…...

机器学习必修课 - 编码分类变量 encoding categorical variables

1. 数据预处理和数据集分割 import pandas as pd from sklearn.model_selection import train_test_split导入所需的Python库 !git clone https://github.com/JeffereyWu/Housing-prices-data.git下载数据集 # Read the data X pd.read_csv(/content/Housing-prices-data/t…...

ClickHouse进阶(二十二):clickhouse管理与运维-服务监控

进入正文前,感谢宝子们订阅专题、点赞、评论、收藏!关注IT贫道,获取高质量博客内容! 🏡个人主页:IT贫道_大数据OLAP体系技术栈,Apache Doris,Kerberos安全认证-CSDN博客 📌订阅:拥抱独家专题,你的订阅将点燃我的创作热情! 👍点赞:赞同优秀创作,你的点赞是对我创…...

Hadoop使用hdfs指令查看hdfs目录的根目录显示被拒

背景 分布式部署hadoop,服务机只有namenode节点,主机包含其他所有节点 主机关机后,没有停止所有节点,导致服务机namenode继续保存 再次开启主机hadoop,使用hdfs查看hdfs根目录的时候显示访问被拒 解决方案 1.主机再次开启hadoop并继续执行关闭 2.服务器再次开启hadoop并继…...

[Mac] 安装paddle-pipelines出现 ERROR: Failed building wheel for lmdb

今天在mac换了新系统&#xff0c;然后重新安装paddle-piplines的时候出现了下面的问题&#xff1a; xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/CommandLineTools/usr/bin/xcrunerror: comma…...

LED灯亮灭

.text .global _start _start: 设置GPIO寄存器的时钟使能  RCC_MP_AHB4ENSETR[4]->1 0x50000a28LDR R0,0x50000A28LDR R1,[R0] 从R0为起始地址的&#xff14;个字节数据取出放入R1中ORR R1,R1,#(0x1<<4) 第四位设置为1STR R1,[R0] 写回LDR R0,0x5000…...

Acwing.143 最大异或对(trie树)

题目 在给定的N个整数A1&#xff0c;A2 . …Ax中选出两个进行xor(异或)运算&#xff0c;得到的结果最大是多少? 输入格式 第一行输入一个整数N。 第二行输入N个整数A1~AN。 输出格式 输出一个整数表示答案。 数据范围 1 ≤N ≤105,0≤A<231 输入样例: 3 1 2 3输出样…...

day10.8ubentu流水灯

流水灯 .text .global _start _start: 1.设置GPIOE寄存器的时钟使能 RCC_MP_AHB4ENSETR[4]->1 0x50000a28LDR R0,0X50000A28LDR R1,[R0] 从r0为起始地址的4字节数据取出放在R1ORR R1,R1,#(0x1<<4) 第4位设置为1STR R1,[R0] 写回2.设置PE10管脚为输出模式 G…...

transformer系列5---transformer显存占用分析

Transformer显存占用分析 1 影响因素概述2 前向计算临时Tensor显存占用2.1 self-attention显存占用2.2 MLP显存占用 3 梯度和优化器显存占用3.1 模型训练过程两者显存占用3.2 模型推理过程两者显存占用 1 影响因素概述 模型训练框架&#xff1a;例如pytorch框架的cuda context…...

Docker项目部署

目录 一、前端项目部署 1、上传文件 2、开启容器 3、测试 二、后端项目部署 1、打包java项目 2、将jar包和Dockerfile文件长传到Linux系统 3、构建镜像 4、开启容器 5、测试 三、DockerCompose快速部署 基本语法 一、前端项目部署 1、上传文件 里面包括页面和配置文…...

vue3实现文本超出鼠标移入的时候文本滚动

判断文本长度是否大于容器长度 鼠标移入的时候判断&#xff0c;此处使用了tailwindcss&#xff0c;注意一下要设置文本不换行。 <divref"functionsItems"mouseenter"enterFunctionsItem($event, index)"><img class"w-5 h-5" :src&quo…...

光伏系统MPPT、恒功率控制切换Simulink仿真

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

mysql双主互从通过KeepAlived虚拟IP实现高可用

mysql双主互从通过KeepAlived虚拟IP实现高可用 在mysql 双主互从的基础上&#xff0c; 架构图&#xff1a; Keepalived有两个主要的功能&#xff1a; 提供虚拟IP&#xff0c;实现双机热备通过LVS&#xff0c;实现负载均衡 安装 # 安装 yum -y install keepalived # 卸载 …...

​苹果应用高版本出现:“无法安装此app,因为无法验证其完整性”是怎么回事?竟然是错误的?

最近经常有同学私聊我问苹果应用签名后用落地页下载出现高版本是什么意思&#xff1f;我一脸懵&#xff01;还有这个操作&#xff1f;高版本是个啥玩意&#xff01;所以我就上了一下科技去搜索引擎搜索了下&#xff0c;哈哈哈&#xff0c;然后了解下来发现是这样的首先我们确定…...

AF_UNIX和127.0.0.1(AF_INET)回环地址写数据速度对比

在linux下&#xff0c;存在着这样的情况&#xff0c;本地的进程间通信&#xff0c;并且其中一个是服务端&#xff0c;另外的都是客户端。 服务端通过绑定端口&#xff0c;客户端往127.0.0.1的对应端口发送&#xff0c;即可办到&#xff0c;不过这样会浪费一个端口&#xff0c;同…...

我在 NPM 发布了新包: con-colors

链接地址&#xff1a;npmjs.com con-colors 安装依赖 yarn add con-colors使用 导入&#xff1a; import { print } from "con-colors";使用&#xff1a; print.succ("成功的消息"); print.err("失败的消息")例子&#xff1a; import { p…...

【python数据建模】Scipy库

常用模块列表 模块名功能scipy.constants数学常量scipy.fft离散傅里叶变换scipy.integrate积分scipy.interpolate插值scipy.interpolate线性代数scipy.cluster聚类分析、向量量化scipy.io数据输入输出scipy.misc图像处理scipy.ndimagen维图像scipy.odr正交距离回归scipy.optim…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...