C++STL容器系列(三)list的详细用法和底层实现

目录

  • 一:介绍
  • 二:list的创建和方法
    • 创建list
    • 方法
  • 三:list的具体用法
    • 3.1 push_back、pop_back、push_front、pop_front
    • 3.2 insert() 和 erase()
    • 3.3 splice 函数
  • 四:list容器底层实现
    • 4.1 list 容器节点结构
    • 5.2 list容器迭代器的底层实现
    • 5.2 list容器的主体实现
  • 总结

对2024年航空航天与力学国际学术会议(ICAM 2024) 感兴趣的伙伴可以点击【click】

一:介绍

  • list是一种序列式容器。该容器的底层是用双向链表实现的, 在链表的任一位置进行元素的插入、删除操作都是快速的。

二:list的创建和方法

首先,使用vector时需包含头文件:

  • #include <list>

创建list

list本质是类模板,可以存储任何类型的数据。数组在声明前需要加上数据类型,而list则通过模板参量设定类型。

比如,声明一个int型的list列表。

list<A> listname;					// 一个空列表list<A> listname(size);				// 开辟size个空间,值默认为0list<A> listname(size, value);      // size个值为value的数组list<A> listname(elselist);         //  拷贝构造参数是其他listlist<A> listname(first, last);      // 迭代器初始化

方法

✨iterators(迭代器) \colorbox{pink}{✨iterators(迭代器)} ✨iterators(迭代器)

名字描述
begin返回指向容器中第一个元素的迭代器。
end返回指向容器最后一个元素所在位置后一个位置的迭代器
rbegin返回容器逆序的第一个元素的迭代器
rend返回容器逆序的最后一个元素的前一个位置的迭代器
cbegin和begin()功能相同,在其基础上增加了 const 属性,不能用于修改元素。
cend和end()功能相同,在其基础上增加了 const 属性,不能用于修改元素。
crbegin和rbegin()功能相同,在其基础上增加了 const 属性,不能用于修改元素。
crend和rend()功能相同,在其基础上增加了 const 属性,不能用于修改元素。

✨Capacity(容量) \colorbox{pink}{✨Capacity(容量)} ✨Capacity(容量)

名字描述
size返回实际元素的个数
empty判断list是否为空,为空返回true否则false
max_size返回元素个数的最大值。

✨Element access(元素访问) \colorbox{pink}{✨Element access(元素访问)} ✨Element access(元素访问)

名字描述
front返回第一个元素
back返回最后一个元素

✨Modifiers(修改器) \colorbox{pink}{✨Modifiers(修改器)} ✨Modifiers(修改器)

名字描述
push_back在容器的尾部插入元素
pop_back删除最后一个元素
push_front在容器的头部插入元素
pop_front删除第一个元素
erase删除元素
clear清除容器内容,size=0,存储空间不变
swap交换两个元素的所有内容
assign用新元素替换原有内容。
emplace_front插入元素,和insert实现原理不同,速度更快
emplace_back在容器的尾部插入元素,和push_back不同, 速度更快

三:list的具体用法

3.1 push_back、pop_back、push_front、pop_front

list<int> lt1;
for (int i = 0; i < 5; i++)
{lt1.push_back(i);lt1.push_front(i);
}
for (int i = 0; i < 5; i++)
{lt1.pop_back();lt1.pop_front();
}
  • emplace_back的效果和push_back一样,具体可以查看前一篇vector的博客

3.2 insert() 和 erase()

  • insert():在指定位置插入一个或多个元素(三个重载)
l1.insert(l1.begin(), 100);  在l1的开始位置插入100。l1.insert(l1.begin(), 2, 200);  在l1的开始位置插入2100。l1.insert(l1.begin(), l2.begin(), l2.end()); 在l1的开始位置插入l2的从开始到结束的所有位置的元素。
  • erase():删除一个元素或一个区域的元素(两个重载)
l1.erase(l1.begin());  	 将l1的第一个元素删除。l1.erase(l1.begin(), l1.end());  将l1的从 begin()end() 之间的元素删除。

3.3 splice 函数

  • splice函数是list中的一个转移函数,将另外一个list中的元素转移到本list中。共有3个重载:

1、list1.splice(position, list2): 将list2中的所有元素剪贴到list1的position位置;

2、list1.splice(position, list2, iter): 将list2中某个位置的迭代器iter指向的元素剪贴到list1中的position位置;

3、list1.splice(position, list2, iter1, iter2): 将list2中的某一段位置iter1 ~ iter2的元素剪贴到list1中的position位置

void list_splice()
{list<int>mylist1, mylist2;for (int i = 1; i <= 4; i++) mylist1.push_back(i);for (int i = 1; i <= 4; i++) mylist2.push_back(i * 10);std::list<int>::iterator it1 = mylist1.begin();it1++;mylist1.splice(it1, mylist2);  // 转移mylist2到it1位置之前// 注意:此时链表2就为空链表了 所以splice名字叫做转移for (auto& e : mylist1){cout << e << " ";}
}// 输出:1 10 20 30 40 2 3 4

四:list容器底层实现

容器的底层是用双向链表实现的,甚至一些 STL 版本中(比如 SGI STL),list 容器的底层实现使用的是双向循环链表。

头指针,使用链表存储数据,并不会将它们存储到一整块连续的内存空间中。恰恰相反,各元素占用的存储空间(又称为节点)是独立的、分散的,它们之间的线性关系通过指针来维持。

在这里插入图片描述

4.1 list 容器节点结构

双向链表的各个节点中存储的不仅仅是元素的值,还应包含 2 个指针,分别指向前一个元素和后一个元素。

template<class T>  
struct ListNode    // 当一个类不想要访问限定符限制的时候就用struct
{ListNode* _next;ListNode* _prev;T _data;ListNode(const T& data):_next(nullptr), _prev(nullptr), _data(data){}
};

注:为了方便阅读和理解,本文章所实现的list都省略了与本文核心内容不相关的内容,如果读者对此部分感兴趣,可查看 list 容器实现源码。

  • 本人的 gitee上具有本文实现的完整代码及测试代码,需要的可以自取【click】

5.2 list容器迭代器的底层实现

和 vector 这些容器迭代器的实现方式不同,由于 list 容器的元素并不是连续存储的,所以该容器迭代器中,必须包含一个可以指向 list 容器的指针,并且该指针还可以借助重载的 *、++、–、==、!= 等运算符,实现迭代器正确的递增、递减、取值等操作。

  • 所以我们就需要对迭代器进行封装!!

可以看到,迭代器的移动就是通过操作节点的指针实现的。

  • 注意:因为存在const迭代器 和 非const迭代器 所以这里我们的模版参数有三个一个为存储类型 一个为 引用返回类型 一个为 指针类型(const 和 非const)
// 通过模板,给不同的模板参数,让编译器帮我们实例化两个类
template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}Self& operator++()  // 迭代器++返回自己 所以typedef一下{_node = _node->_next;return *this;}Self operator++(int)   // 后置++ 不能用引用返回了 tmp会销毁{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;}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};
  • 接下来是reverse_iterator的实现 注意反向迭代器的实现可以对正向迭代器进行复用 具体代码如下:
// 此处的参数就是正向迭代器了
template<class iterator, class Ref, class Ptr>
struct Reverse_ListIterator
{typedef Reverse_ListIterator<iterator, Ref, Ptr> Self;iterator _it;Reverse_ListIterator(iterator it):_it(it){}Ref operator*(){iterator tmp = _it;return tmp._node->_prev;}// 作用是为pos这种结构体服务的Ptr operator->(){return &_it._node->_prev->_data;}Self& operator++(){_it._node = _it._node->_prev;return *this;}Self operator++(int){Self tmp(*this);_it._node = _it._node->_prev;return tmp;}Self& operator--(){_it._node = _it._node->_next;return *this;}Self operator--(int){Self tmp(*this);_it._node = _it._node->_next;return tmp;}bool operator!=(const Self& it){return _it._node != it._it._node;    // 复用的结果}bool operator==(const Self& it){return _it._node == it._node;}};

5.2 list容器的主体实现

  • 以下是主体实现
template<class T>
class list
{typedef ListNode<T> Node;// 不符合迭代器的行为,无法遍历 无法进行++和*操作 所以我们要将迭代器封装成一个类进行运算符重载即可// typedef Node* iterator;
public:typedef ListIterator<T, T&, T*> iterator;   //规范迭代器typedef ListIterator<T, const T&, const T*> const_iterator;   // 通过模板,给不同的模板参数,让编译器帮我们实例化两个类// list的const迭代器是有东西的typedef Reverse_ListIterator<iterator, T&, T*> reverse_iterator;typedef Reverse_ListIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return iterator(_head->_next);    // 匿名对象}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);    // 匿名对象}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());    // 匿名对象}reverse_iterator rend(){return reverse_iterator(begin());}list()   // 初始化哨兵卫的头节点{_head = new Node(T());   // 没有合适的默认构造函数可用 这里用匿名对象初始化_head->_next = _head;_head->_prev = _head;}void empty_init(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}// 这里的赋值重载是现代写法list<T>& operator=(list<T> lt){swap(_head, lt._head);return *this;}~list(){clear();delete _head;}void push_back(const T& x){Node* newnode = new Node(x);    // 就不需要专门写个CreatNewNode的了   自动调用Node的构造函数/*newnode->_next = _head;newnode->_prev = _head->_prev;_head->_prev->_next = newnode;_head->_prev = newnode;*/insert(end(), x);}iterator insert(iterator pos, const T& x){Node* node = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;node->_next = cur;node->_prev = prev;prev->_next = node;cur->_prev = node;return iterator(node);}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;return iterator(next);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void clear(){list<T>::iterator it = begin();while (it != end()){it = erase(it);}}private:Node* _head;
};

总结

list的详细用法和底层实现就介绍到这里了如果有任何疑问都可以私信我,希望我们共同进步, 有错误还请在评论区指正!

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

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

相关文章

基于51单片机的交通灯设计

一.硬件方案 本设计能模拟基本的交通控制系统&#xff0c;用红绿黄灯表示禁行&#xff0c;通行和等待的信号发生&#xff0c;还能进行倒计时显示。按键可以控制禁行、深夜模式、复位、东西通行、南北通行、时间加、时间减、切换等功能。共四个二位阴极数码管&#xff0c;东南西…

人工智能初识

&#x1f31e;欢迎来到人工智能基础的世界 &#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f4c6;首发时间&#xff1a;&#x1f339;2024年5月1…

C#多线程同步lock、Mutex

C#使用多线程可以通过System.Threading命名空间下的Thread类来实现 lock和Mutex用于实现线程同步的机制&#xff1a; 上代码&#xff1a; class People{public People(int idd){id idd;}public int id;public int age;}class TestHelper{public TestHelper() { }List<Peo…

uniapp h5项目切换导航栏及动态渲染按钮颜色

1.效果图 2.html,动态渲染按钮样式---三元判断 <!-- 切换栏 --><view class"statusList"><block v-for"(item,index) in list" :key"index"><view class"swiper-tab-list" :class"current item.id?activ…

【STL】C++ stack(栈) 基本使用

目录 一 stack常见构造 1 空容器构造函数&#xff08;默认构造函数&#xff09; 2. 使用指定容器构造 3 拷贝构造函数 二 其他操作 1 empty 2 size 3 top 4 push && pop 5 emplace 6 swap 三 总结 一 stack常见构造 1 空容器构造函数&#xff08;默认构造…

西储大学数据集学习

数据集下载地址&#xff1a;CWRU凯斯西储大学轴承数据数据集——附&#xff1a;下载链接_西储大学轴承数据集下载-CSDN博客 最近研究故障诊断&#xff0c;先对使用比较多的西储大学数据集研究。以资料【1】中的内容展开研究。 1、轴承的结构 轴承分为外圈、内圈、保持架和滚珠…

202474读书笔记|《我自我的田渠归来》——愿你拥有向上的力量,一切的好事都应该有权利发生

202474读书笔记|《我自我的田渠归来》——愿你拥有向上的力量 《我自我的田渠归来》作者张晓风&#xff0c;被称为华语散文温柔的一支笔&#xff0c;她的短文很有味道&#xff0c;角度奇特&#xff0c;温柔慈悲而敏锐。 很幸运遇到了这本书&#xff0c;以她的感受重新认识一些事…

端口扫描利器--nmap

目录 普通扫描 几种指定目标的方法 TCP/UDP扫描 端口服务扫描 综合扫描 普通扫描 基于端口连接并响应(真实) ​ nmap -sn 网段(0/24)-sn 几种指定目标的方法 单个IP扫描 IP范围扫描 扫描文件里的IP 扫描网段,(排除某IP) 扫描网段(排除某清单IP) TCP/UDP扫描 -sS …

windows系统电脑外插键盘驱动出现感叹号或者显示未知设备,键盘无法输入的解决办法

笔记本外插的键盘不能用&#xff0c;鼠标可以使用。 查找故障&#xff0c;结果打开设备管理器看到键盘那项里是一个的黄色惊叹号显示未知设备&#xff01;[图片]如下图所示 其实解决办法很简单&#xff0c;不要相信网上的一些博主说删除什么注册表&#xff0c;我开始跟着他们操…

C++笔试强训day36

目录 1.提取不重复的整数 2.【模板】哈夫曼编码 3.abb 1.提取不重复的整数 链接https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId37&tqId21232&ru/exam/oj 按照题意模拟就行&#xff0c;记得从右往左遍历 #include <iostream> usi…

React基础知识笔记

Reat简介 React&#xff1a;用于构建用户界面的 JavaScript 库。由 Facebook 开发且开源。是一个将视图渲染为html视图的开源库 第一章&#xff1a;React入门 相关js库 react.development.js &#xff1a;React 核心库react-dom.development.js &#xff1a;提供 DOM 操作的…

【分享】3种方法取消PPT的“限制保护”

PPT如果设置了有密码的“只读方式”&#xff0c;每次打开PPT&#xff0c;都会出现对话框&#xff0c;提示需要输入密码才能修改文件&#xff0c;否则只能以“只读方式”打开。 以“只读方式”打开的PPT就会被限制&#xff0c;无法进行编辑修改等操作。那如果后续不需要“限制保…

【Linux进程篇】Linux进程管理——进程创建与终止

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; 目录 进程创建 fork函数初识 写时拷贝 fork常规用法 fork调用失败的原因 进程终止 进程退出场景 _exit函数 exit函数 return退出 进程创建 fork函数初识 在linux中fork函数时非常重要的函数&#xff0c;它从已…

Python Selenium 详解:实现高效的UI自动化测试

落日余辉&#xff0c;深情不及久伴。大家好&#xff0c;在当今软件开发的世界中&#xff0c;自动化测试已经成为保障软件质量和快速迭代的重要环节。而在自动化测试的领域中&#xff0c;UI自动化测试是不可或缺的一部分&#xff0c;它可以帮助测试团队快速验证用户界面的正确性…

huggingface的self.state与self.control来源(TrainerState与TrainerControl)

文章目录 前言一、huggingface的trainer的self.state与self.control初始化调用二、TrainerState源码解读(self.state)1、huggingface中self.state初始化参数2、TrainerState类的Demo 三、TrainerControl源码解读(self.control)总结 前言 在 Hugging Face 中&#xff0c;self.s…

Kong网关的负载均衡

安装java环境 查询 java安装包 196 yum list java* 安装java8197 yum install -y java-1.8.0-openjdk.x86_64 检验java8是否安装成功。198 java -version2个tomcat准备 另外一个tomcat区别在于&#xff1a;配置文件。conf/server.xml 启动tomcat [rootlocalhost bin]# ./…

JDBC使用步骤-小白入门

一.JDBC开发流程 加载并注册JDBC驱动创建数据库连接创建Statement对象遍历查询结果关闭连接,释放资源 import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement;public class StandardJDBCSample {public static …

【busybox记录】【shell指令】unlink

目录 内容来源&#xff1a; 【GUN】【unlink】指令介绍 【busybox】【unlink】指令介绍 【linux】【unlink】指令介绍 使用示例&#xff1a; 删除文件 - 默认 常用组合指令&#xff1a; 指令不常用/组合用法还需继续挖掘&#xff1a; 内容来源&#xff1a; GUN &#x…

element-ui 实现输入框下拉树组件(2024-05-23)

用element-ui的 el-input&#xff0c;el-tree&#xff0c;el-popover组件组合封装 import url("//unpkg.com/element-ui2.15.14/lib/theme-chalk/index.css"); <script src"//unpkg.com/vue2/dist/vue.js"></script> <script src"//…

单链表经典算法题理解

目录 1. 前言&#xff1a; 2. 移除链表元素 3. 反转链表 4. 合并两个有序链表 5. 链表的中间节点 6. 环形链表的约瑟夫问题 7. 分割链表 1. 前言&#xff1a; 当我们学习了单链表之后&#xff0c;我能可以尝试的刷一下题了&#xff0c;以下分享一下几道题的解法 2. 移…