C++标准模板库STL——list的使用及其模拟实现


1.list的介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向
其前一个元素和后一个元素。
3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的基本结构图

2.list的使用

我们这里可以简单看一下文档里面关于list各种构造函数的介绍

2.1list的构造

目前我们只掌握这四种构造函数的使用方法

代码案例

#include<iostream>
#include<list>using namespace std;void test_list1()
{list<int> lt1;   //1.这里我们构造了一个空的list对象list<int> lt2(10, 100);  // 2.这里我们通过用构造了10个100的方式构造了lt2//由于list不支持随机访问,所以下面我们需要借助迭代器遍历一下lt2cout << "lt2中的元素遍历:" << endl;list<int>::iterator it = lt2.begin();while (it != lt2.end()){cout << *it << " ";it++;}cout << endl;cout << "lt3拷贝lt2构造后的元素遍历:" << endl;list<int> lt3(lt2);list<int>::iterator its = lt3.begin();while (its != lt3.end()){cout << *its << " ";its++;}cout << endl;list<int> lt4(lt3.begin(), lt3.end());cout << "lt4用lt3的迭代器区间构造后的元素遍历:" << endl;list<int>::iterator it1 = lt4.begin();while (it1 != lt4.end()){cout << *it1 << " ";it1++;}cout << endl;}int main()
{test_list1();return 0;
}

代码运行结果:

2.2 list 迭代器 iterator 的使用

迭代器分为正向迭代器和反向迭代器,像begin() 和end()返回的是正向迭代器,rbegin()和rend()返回的是反向迭代器,然后这两种迭代器又可以和const进行结合形成上面c++11新加的cbegin()和cend(),crbegin()和crend(),其对应的迭代器名称也要跟着变化,我们可以看一下文档中的这些函数的说明,

注意

iterator T* 可读可写

const_iterator T* 只读

const iterator 这样实现是迭代器本身不能修改

const_iterator  重新定义的一个类型,做到的是本身可以修改,但是指向的内容不能修改

下面我们通过代码举个例子

测试代码:

void test_list2()
{//迭代器的使用,我们就简单通过常用的正反向迭代器进行说明,//前面加了const的迭代器只需要记得不能修改迭代器所指向的内容//1.正向迭代器,我们用简单的遍历list元素来说明list<int> lt;lt.push_back(1);    //在list里面插入6个结点lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout << "正向迭代器的遍历:" << endl;list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;// 2.反向迭代器list<int>::reverse_iterator rit = lt.rbegin();cout << "反向迭代器的遍历:" << endl;while (rit != lt.rend()){cout << *rit << " ";rit++;}cout << endl;}

注意

1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

2.3 list的容量大小接口的使用

代码测试:

void test_list3()
{//empty()接口和size()接口的使用,你会发现跟vector相比没有capacity()list<int>  lt;cout << "empty():" << lt.empty() << endl;cout << "size():" << lt.size() << endl;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout << "插入三个元素之后" << endl;cout << "empty():" << lt.empty() << endl;cout << "size():" << lt.size() << endl;
}

运行结果:

2.4 list访问头尾元素的接口

测试代码:

void test_list4()
{//front()接口和 back()接口的测试list<int>  lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout << "遍历" << endl;list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << "第一个元素" << endl;cout << lt.front() << endl;cout << "最后一个元素" << endl;cout << lt.back() << endl;
}

测试结果:

这个list底层是一个双向循环链表,所以通过头结点访问到第一个元素和最后一个元素比较简单,但是中间的元素就不支持随机访问了。

2.5 list Modifiers

我们先了解下以下这几个接口的使用方法

//头插
void push_front (const value_type& val);//头删
void pop_front();//尾插
void push_back (const value_type& val);//尾删
void pop_back();//在pos位置插入元素val
single element (1)	
iterator insert (iterator position, const value_type& val);//在pos位置插入n个元素val
fill (2)	void insert (iterator position, size_type n, const value_type& val);//在pos位置插入一段迭代器区间的结点
range (3)	
template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);//删除pos位置的结点
iterator erase (iterator position);//删除一段迭代器区间的结点
iterator erase (iterator first, iterator last);//交换两个链表,实际上只需要将头结点的指针跟大小size进行交换即可
void swap (list& x);//将链表数据清空
void clear();

下面带大家来看看我们的使用案例

测试代码:

void test_list5()
{list<int> lt;//尾插for (int i = 0; i < 10; i++)//尾插后的结点值是0 1 2 3 4 5 6 7 8 9{lt.push_back(i);}//我们这里使用简单的范围for来进行遍历cout << "尾插后链表中的结点值为:" << endl;for (auto e : lt)//范围for借助迭代器自动推导e的类型,自动给e赋值,自动往后++{cout << e << " ";}cout << endl;//头插lt.push_front(10);lt.push_front(20);    //头插这两个结点后变成:20 10 0 1 2 3 4 5 6 7 8 9cout << "头插后的链表结点值为:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//头删lt.pop_front();lt.pop_front();lt.pop_front();     //头删之后变成:1 2 3 4 5 6 7 8 9cout << "头删之后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//尾删lt.pop_back();lt.pop_back();lt.pop_back();     //尾删之后变成: 1 2 3 4 5 6cout << "尾删之后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入一个值为val的结点list<int>::iterator it = lt.begin();it++;lt.insert(it, 20);  //此时变成 1 20 2 3 4 5 6cout << "在第2个结点位置插入一个20:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入n个值为val的结点it++;++it;lt.insert(it, 5, 30);//在第4个结点的位置插入5个30cout << "在第4个结点的位置插入5个30后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//在pos位置插入一段迭代器区间list<int> lt2(10, 100);lt.insert(it, lt2.begin(), lt2.end());//将lt2的10个值为100的结点从lt的第4个结点插入cout << "插入一段迭代器区间之后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//删除pos位置的结点   这里我们会涉及一个迭代器失效的问题,我们后面再说it = lt.erase(it);cout << "删除it位置的结点后:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//删除一段迭代器区间的结点it = lt.erase(it, lt.end());//我们将it以及之后的结点都删除cout << "将it后面位置的结点都删除了" << endl;for (auto e : lt){cout << e << " ";}cout << endl;//交换两个链表//我们先看看lt和lt2的两个链表结点的值,然后交换cout << "lt:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;//交换后lt.swap(lt2);cout << "交换后:" << endl;cout << "lt:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;//将链表数据清空cout << "将两个链表的数据都清空之后:" << endl;lt.clear();lt2.clear();cout << "lt:" << endl;for (auto e : lt){cout << e << " ";}cout << endl;cout << "lt2:" << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}

测试结果:

2.6 list的迭代器失效问题

前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

void TestListIterator1()
{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时,必须先给//其赋值l.erase(it);++it;}
}

运行这段代码之后,因为迭代器失效导致运行失败

所以当我们删除了某个结点之后,迭代器需要重新赋值,而为了解决这个问题,给erase这个函数添加了一个返回值,返回一个迭代器,返回被删除的结点的后一个结点的迭代器这样用it可以接受就可以使得迭代器it再次生效

将代码改正之后:

// 改正
void TestListIterator()
{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()){l.erase(it++); // it = l.erase(it);}
}

这样就没有什么大问题了

3. list 的模拟实现

#pragma once
#include<string>
#include<vector>
#include<iostream>using namespace std;
namespace mylist 
{template<class T>//链表的每个结点的结构struct list_node {T _data;            //存放数据list_node<T>* _prev;//指向前一个结点的指针list_node<T>* _next;//指向后一个结点的指针list_node(const T& val = T())  //构造一个结点对象:_data(val), _prev(nullptr), _next(nullptr){ }};// T T& T*// T cosnt T& const T*template<class T,class Ref,class Ptr>struct __list_iterator                   //list的迭代器结构{typedef list_node<T> Node;             //结点typedef __list_iterator<T,Ref,Ptr> _self; //_self就是一个实例化的迭代器Node* _node;                          //结点的指针__list_iterator(Node* node):_node(node){}Ref operator*()                //重载运算符* 通过*能够访问结点里面的数据{return _node->_data;}Ptr operator->()         //重载-> , 结构体指针访问成员可以用结构体对象->结构体成员{return &_node->_data;}_self& operator++()   //重载运算符前置++,返回下一个结点的迭代器{_node = _node->_next;return (*this);}_self& operator--()  //重载运算符前置--,返回前一个结点的迭代器{_node = _node->_prev;return (*this);}_self operator++(int)  //重载运算符后置++,返回当前结点的迭代器的拷贝再++{Node* tmp(_node);_node = _node->_next;return tmp;}_self operator--(int) //重载运算符前置--,返回当前一个结点迭代器的拷贝再--{Node* tmp(_node);_node = _node->_prev;return tmp;}bool operator!=(const _self& n)  //重载迭代器的比较运算符!={return this->_node != n._node;}bool operator==(const _self& n)  //重载迭代器的比较运算符=={return this->_node == n._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;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return (_head->_next);}iterator end(){return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(){empty_init();}//lt1(lt2)list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}list<int>& operator=(list<int>lt){swap(lt);return *this;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(const T& x){erase(--end());}void pop_front(const T& x){erase(begin());}iterator insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;--_size;return iterator(next);}size_t size(){return _size;}private:Node* _head; //list的头结点size_t _size;//list的大小};
}

4. list和vector的比较

vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同,其主要不同如下:

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

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

相关文章

【C++】开源:单元测试框架gtest配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍单元测试框架gtest配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff…

服务器性能测试监控平台export+prometheus(普罗米修斯)+grafana搭建

1. export 数据采集工具 简介&#xff1a; export是prometheus是的数据采集组件的总称&#xff0c;它可以将采集到的数据转为prometheus支持的格式 node_export: 用来监控服务器硬件资源的采集器&#xff0c;端口号为9100mysql_export: 用来监控mysql数据库资源的采集器&…

性能测试 —— Tomcat监控与调优:Jconsole监控

JConsole的图形用户界面是一个符合Java管理扩展(JMX)规范的监测工具&#xff0c;JConsole使用Java虚拟机(Java VM)&#xff0c;提供在Java平台上运行的应用程序的性能和资源消耗的信息。在Java平台&#xff0c;标准版(Java SE平台)6&#xff0c;JConsole的已经更新到目前的外观…

前端新轮子Nue,号称替代Vue、React和Svelte

新的简约前端开发工具集Nue.js 于周三发布。在 Hacker News 上介绍它时&#xff0c;前端开发者和Nue.js 的创作者Tero Piirainen表示&#xff0c;它是 React、Vue、Next.js、Vite、Svelte 和 Astro 的替代品。他在 Nue.js的 FAQ 中进一步解释说&#xff0c;它是为网站和响应式用…

力扣刷题-链表-两两交换链表中的节点

24.两两交换链表中的节点 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 解题思路 采用正常模拟的方法。 建议使用虚拟头结点&#xff0c;这样会方便很多&am…

【python爬虫】爬虫所需要的爬虫代理ip是什么?

目录 前言 一、什么是爬虫代理 IP 二、代理 IP 的分类 1.透明代理 2.匿名代理 3.高匿代理 三、如何获取代理 IP 1.免费代理网站 2.付费代理服务 四、如何使用代理 IP 1.使用 requests 库 2.使用 scrapy 库 五、代理 IP 的注意事项 1.代理 IP 可能存在不稳定性 2…

R语言贝叶斯非参数模型:密度估计、非参数化随机效应META分析心肌梗死数据...

全文链接&#xff1a;http://tecdat.cn/?p23785 最近&#xff0c;我们使用贝叶斯非参数&#xff08;BNP&#xff09;混合模型进行马尔科夫链蒙特卡洛&#xff08;MCMC&#xff09;推断&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 概述 相关视频 在这篇文…

坐标休斯顿,TDengine 受邀参与第九届石油天然气数字化大会

美国中部时间 9 月 14 日至 15 日&#xff0c;第九届石油天然气数字化大会在美国德克萨斯州-休斯顿-希尔顿美洲酒店举办。本次大会汇聚了数百名全球石油天然气技术高管及众多极具创新性的数据技术方案商&#xff0c;组织了上百场硬核演讲&#xff0c;技术专家与行业从业者共聚一…

12:STM32---RTC实时时钟

目录 一:时间相关 1:Unix时间戳 2: UTC/GMT 3:时间戳转化 二:BKP 1:简历 2:基本结构 三: RTC 1:简历 2: 框图 3:RTC基本结构 4:RTC操作注意 四:案例 A:读写备份寄存器 1:连接图 2: 步骤 3: 代码 B:实时时钟 1:连接图 2:函数介绍 3:代码 一:时间相关 1:Un…

虹科教您 | 可实现带宽计量和延迟计算的时间敏感网络测试工具RELY-TSN-LAB操作指南与基本功能测试

1. RELY-TSN-LAB产品概述 时间敏感网络(TSN)能够合并OT和IT世界&#xff0c;这将是真正确保互操作性和标准化的创新性技术。这项技术的有效开发将显著降低设备成本、维护、先进分析服务的无缝集成以及减少对单个供应商的依赖。为了在这些网络中实现确定性&#xff0c;需要控制…

如何取消显示Notepad++每行显示的CRLF符号

新电脑中重新安装了Nodepad&#xff0c;打开记事本后发现出现了许多黑底的CR|LF标记&#xff0c;特别碍眼。 如何取消呢&#xff1f; 视图 -> 显示符号 -> 取消勾选 显示行尾符操作步骤 预期效果

虹科案例 | LIN/CAN总线汽车零部件测试方案

文章来源&#xff1a;虹科汽车电子 点此阅读原文 虹科的LIN/CAN总线汽车零部件测试方案是一款优秀的集成套装&#xff0c;基于Baby-LIN系列产品&#xff0c;帮助客户高效完成在测试、生产阶段车辆零部件质量、功能、控制等方面的检测工作。 1、汽车零部件测试的重要性&#xf…

linux 防火墙iptables

iptables 是 Linux 中比较底层的网络服务&#xff0c;它控制了 Linux 系统中的网络操作&#xff0c;CentOS 中的 firewalld 和 Ubuntu 中的 ufw 都是在 iptables 之上构建的&#xff0c;只为了简化 iptables 的操作。同时&#xff0c;iptables 不仅仅是防火墙这么简单&#xff…

GO语言从入门到实战-Go语言简介:历史背景、发展现状及语言特性

一、简述Go语言背景和发展 1. 软件开发的新挑战 多核硬件架构超大规模分布式计算集群Web 模式导致的前所未有的开发规模和更新速度 2. Go的三位创始人 Rob Pike Unix 的早期开发者 UTF-8 创始人 Ken Thompson Unix 的创始人 C语言创始人 …

从零学习开发一个RISC-V操作系统(二)丨GCC编译器和ELF格式

本篇文章的内容 一、GCC&#xff08;GUN Compiler Collection&#xff09;1.1 GCC的命令格式1.2 GCC的主要执行步骤1.3 GCC涉及的文件类型 二、ELF简介2.1 ELF文件格式图2.2 ELF文件处理的相关工具2.3 练习 本系列是博主参考B站课程学习开发一个RISC-V的操作系统的学习笔记&…

【动手学深度学习-Pytorch版】门控循环单元GRU

关于GRU的笔记 支持隐状态的门控&#xff1a;这意味着模型有专门的机制来确定应该何时更新隐状态&#xff0c; 以及应该何时重置隐状态。 这些机制是可学习的&#xff0c;并且能够解决了上面列出的问题。 例如&#xff0c;如果第一个词元非常重要&#xff0c; 模型将学会在第一…

Docker文档阅读笔记-How to Commit Changes to a Docker Image with Examples

介绍 在工作中使用Docker镜像和容器&#xff0c;用得最多的就是如何提交修改过的Docker镜像。当提交修改后&#xff0c;就会在原有的镜像上创建一个新的镜像。 本博文说明如何提交一个新的Docker镜像。 前提 ①有一个可以直接访问服务器的运行终端&#xff1b; ②帐号需要r…

云计算安全:保护数字资产的前沿策略

文章目录 1. 云计算安全威胁1.1 数据泄露1.2 身份认证问题1.3 无法预测的网络攻击1.4 集中攻击 2. 云计算安全最佳实践2.1 身份和访问管理&#xff08;IAM&#xff09;2.2 数据加密2.3 安全审计和监控2.4 多重身份验证&#xff08;MFA&#xff09; 3. 安全自动化3.1 基础设施即…

springboot 获取参数

1.获取简单参数 2.实体对象参数

#倍增 #国旗计划

文章目录 题目&#xff1a;题解代码 题目&#xff1a; 国旗计划 题解 三个技巧&#xff1a; 断环成链&#xff1a; 具体而言就是&#xff1a; if(w[i].R < w[i].L) w[i].R m; m是环的长度&#xff1b; 贪心&#xff1a; 选择一个区间i后&#xff0c;下一个区间只能从左端…