C++ list

文章目录

  • list的介绍及使用
    • list的介绍
    • list的构造
    • list iterator的使用
    • list capacity
    • list element access
    • list modifiers
  • list模拟实现
    • list节点类
    • list迭代器类
    • list类
  • list深度剖析
    • list迭代器失效
    • list反向迭代器
  • list与vector对比

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的构造

构造函数（ (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

list iterator的使用

函数声明接口说明
begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

在这里插入图片描述

注意：

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

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节点类

template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}

list迭代器类

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)
		{}

		Ref operator*()
		{
			return _node->_data;
		}
		

		Ptr operator->()
		{
			return &_node->_data;
		}
		
		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 tmp;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

list类

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;


		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}


		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const
		{
			return _head;
		}

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		list()
		{
			empty_init();
		}

		// lt2(lt1)
		list(const list<T>& lt)
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		// 需要析构，一般就需要自己写深拷贝
		// 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}


		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());
		}

		void insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

			// prev newnode cur;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			_size--;

			return iterator(next);
		}

		size_t size() const
		{
			return _size;
		}

		bool empty()
		{
			return _size == 0;
		}

	private:
		Node* _head;
		size_t _size;
	};

list深度剖析

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())
 {
 cout<<*it<<" ";
 // erase()函数执行后，it所指向的节点已被删除，
 //因此it无效，在下一次使用it时，必须先给其赋值
 l.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())
 {
  cout<<*it<<" ";
 l.erase(it++); // it = l.erase(it);
 }
}

在这里插入图片描述
分析：erase删除当前元素后返回下一个元素的迭代器，所以只需用it来接收erase的返回值即可。改正前没有接收erase的返回值，导致迭代器it指向的空间释放了，访问已经释放的空间导致报错。
erase（it++）是先存下it的副本，再让it++（此时未删除节点，迭代器还是有效的）再把副本给erase完成删除步骤。

list反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭
代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行
包装即可。

template<class Iterator>
class ReverseListIterator
{
 // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
 // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
 // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
 typedef typename Iterator::Ref Ref;
 typedef typename Iterator::Ptr Ptr;
 typedef ReverseListIterator<Iterator> Self;
public:
 //
 // 构造
 ReverseListIterator(Iterator it): _it(it){}
 //
 // 具有指针类似行为
 Ref operator*(){
 Iterator temp(_it);
 --temp;
 return *temp;
 }
 Ptr operator->(){ return &(operator*());}
 //
 // 迭代器支持移动
 Self& operator++(){
--_it;
 return *this;
 }
 
 Self operator++(int){
 Self temp(*this);
 --_it;
 return temp;
 }
 
 Self& operator--(){
 ++_it;
 return *this;
 }
 
 Self operator--(int)
 {
 Self temp(*this);
 ++_it;
 return temp;
 }
 
 //
 // 迭代器支持比较
 bool operator!=(const Self& l)const{ return _it != l._it;}
 bool operator==(const Self& l)const{ return _it != l._it;}
 Iterator _it;
};

list与vector对比

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

vectorlist
底层结构动态顺序表，一段连续空间带头结点的双向循环链表
插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1）
空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高。底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低。
迭代器原生态指针对原生态指针(节点指针)进行封装
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响。
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

yolov5目标检测可视化界面pyside6源码（无登录版）

yolov5目标检测可视化界面pyside6源码（无登录版）

一、软件简介&#xff1a; 这是基于yolov5-7.0目标检测实现的的可视化目标检测源码 本套项目没有用户登录的功能&#xff0c;如需用户登录版&#xff0c;看另一篇文章&#xff1a;yolov5pyside6登录用户管理目标检测可视化源码_yolov5用户登入功能-CSDN博客 ①程序中图片和图标…
阅读更多...
2024年04月IDE流行度最新排名

2024年04月IDE流行度最新排名

点击查看最新IDE流行度最新排名&#xff08;每月更新&#xff09; 2024年04月IDE流行度最新排名 顶级IDE排名是通过分析在谷歌上搜索IDE下载页面的频率而创建的 一个IDE被搜索的次数越多&#xff0c;这个IDE就被认为越受欢迎。原始数据来自谷歌Trends 如果您相信集体智慧&am…
阅读更多...
02-JDK新特性-泛型

02-JDK新特性-泛型

泛型 什么是泛型 泛型是JDK5中引入的特性&#xff0c;它提供了编译时类型安全检测机制&#xff0c;该机制允许在编译是检测到非法的类型。 它的本质是参数化类型&#xff0c;也就是说操作的数据类型被指定为一个参数。 也就是将类型有原来的具体类型参数化&#xff0c;然后在…
阅读更多...
MySQL 优化及故障排查

MySQL 优化及故障排查

目录 一、mysql 前置知识点 二、MySQL 单实例常见故障 故障一 故障二 故障三 故障四 故障五 故障六 故障七 故障八 三、MySQL 主从故障排查 故障一 故障二 故障三 四、MySQL 优化 1.硬件方面 &#xff08;1&#xff09;关于 CPU &#xff08;2&#xff09;关…
阅读更多...
使用虚拟引擎为AR体验提供动力

使用虚拟引擎为AR体验提供动力

Powering AR Experiences with Unreal Engine ​​​​​​​ 目录 1. 虚拟引擎概述 2. 虚拟引擎如何为AR体验提供动力 3. 虚拟引擎中AR体验的组成部分是什么&#xff1f; 4. 使用虚拟引擎创建AR体验 5. 虚拟引擎中AR的优化提示 6. 将互动性融入AR与虚拟引擎 7. 在AR中…
阅读更多...
Java项目：83 springboot知识管理系统

Java项目：83 springboot知识管理系统

作者主页&#xff1a;源码空间codegym 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本知识管理系统有管理员和用户两个角色。 管理员功能有个人中心&#xff0c;用户管理&#xff0c;文章分类管理&#xff0c;文章信息管理&…
阅读更多...
Excel 数据-分列的三个经常用法

Excel 数据-分列的三个经常用法

Case 1 &#xff1a;有时候数据导出时如果没有电子表格的话&#xff0c;只能导出本地文件&#xff0c;如下图情况&#xff1a; 可以使用数据-分列处理数据&#xff1a; 原来是因为SAP导出数据没有完成的原因&#xff0c;或者关闭Excel重新打开试一下。 重新打开后可以输入了 C…
阅读更多...
NoSQL之 Redis配置

NoSQL之 Redis配置

目录 关系数据库与非关系型数据库 关系型数据库&#xff1a; ●非关系型数据库 关系型数据库和非关系型数据库区别&#xff1a; &#xff08;1&#xff09;数据存储方式不同 &#xff08;2&#xff09;扩展方式不同 对事务性的支持不同 非关系型数据库产生背景 Redis简介…
阅读更多...
C++初阶:5.STL简介(了解)

C++初阶:5.STL简介(了解)

STL简介&#xff08;了解&#xff09; 一.什么是STL STL(standard template libaray-标准模板库)&#xff1a;是C标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且是一个包罗数据结构与算法的软件框架。 二. STL的版本 原始版本 Alexander Stepan…
阅读更多...
绝地求生：Anti-ESP推进对于PUBG哪些影响？

绝地求生：Anti-ESP推进对于PUBG哪些影响？

大家好&#xff0c;我是闲游盒。近期&#xff0c;PUBG开发团队开发信介绍了反作弊团队讨论的新话题 - ESP&#xff08;Extra Sensory Perception&#xff09;。在详细看完开发信以后&#xff0c;今天跟大家简单聊聊关于Anti-ESP。 ESP是一种非法软件&#xff0c;允许玩家在游戏…
阅读更多...
MacBook 访达使用技巧【mac 入门】

MacBook 访达使用技巧【mac 入门】

快捷键 打开访达搜索窗口默认快捷键【⌥ ⌘ 空格键】可以在键盘【系统偏好设置 -> 键盘->快捷键->聚焦】修改 但是我不会去修改它&#xff0c;因为我不常用访达的搜索窗口&#xff0c;更多的是想快速打开访达文件夹窗口&#xff0c;可以通过第三方软件定义访达的快…
阅读更多...
计算机视觉新巅峰，微软牛津联合提出MVSplat登顶3D重建

计算机视觉新巅峰，微软牛津联合提出MVSplat登顶3D重建

开篇&#xff1a;探索稀疏多视图图像的3D场景重建与新视角合成的挑战 3D场景重建和新视角合成是计算机视觉领域的一项基础挑战&#xff0c;尤其是当输入图像非常稀疏&#xff08;例如&#xff0c;只有两张&#xff09;时。尽管利用神经场景表示&#xff0c;例如场景表示网络&a…
阅读更多...
鸿蒙OS开发教学：【编程之重器-装饰器】

鸿蒙OS开发教学：【编程之重器-装饰器】

HarmonyOS 有19种装饰器 必须【2】 绘制一个页面&#xff0c;这两个肯定会用到 EntryComponent 可选【17】 StatePropLinkObjectLinkWatchStylesStoragePropStorageLinkProvideConsumeObservedBuilderBuilderParamLocalStoragePropLocalStorageLinkExtendConcurrent 如果…
阅读更多...
C# 排序的多种实现方式(经典)

C# 排序的多种实现方式(经典)

一、 对数组进行排序 最常见的排序是对一个数组排序&#xff0c;比如&#xff1a; int[] aArray new int[8] { 18, 17, 21, 23, 11, 31, 27, 38 }; 1、利用冒泡排序进行排序&#xff1a; &#xff08;即每个值都和它后面的数值比较&#xff0c;每次拿出最小值&#xff09; s…
阅读更多...
JavaEE初阶-线程3

JavaEE初阶-线程3

文章目录 一、线程安全问题-内存可见性二、等待通知2.1 wait()方法2.2 notify()方法 一、线程安全问题-内存可见性 import java.util.Scanner;public class Demo27 {private static int count0;//下面这段代码会出现内存的可见性问题//将从内存中读取count值的操作称为load 判…
阅读更多...
MySQL常见故障案例与优化介绍

MySQL常见故障案例与优化介绍

前言 MySQL故障排查的意义在于及时识别并解决数据库系统中的问题&#xff0c;确保数据的完整性和可靠性&#xff1b;而性能优化则旨在提高数据库系统的效率和响应速度&#xff0c;从而提升用户体验和系统整体性能。这两方面的工作都对于保证数据库系统稳定运行、提升业务效率和…
阅读更多...
总结：微信小程序中跨组件的通信、状态管理的方案

总结：微信小程序中跨组件的通信、状态管理的方案

在微信小程序中实现跨组件通信和状态管理,有以下几种主要方案: 事件机制 通过事件机制可以实现父子组件、兄弟组件的通信。 示例: 父组件向子组件传递数据: 父组件: <child binddata"handleChildData" /> 子组件: Component({..., methods: { handleChildData(…
阅读更多...
【经验分享】Ubuntu下如何解决问题arm-linux-gcc：未找到命令

【经验分享】Ubuntu下如何解决问题arm-linux-gcc：未找到命令

【经验分享】Ubuntu下如何解决问题arm-linux-gcc&#xff1a;未找到命令 前言问题分析解决方法 前言 在编译过程中发现一个问题&#xff0c;明明之前安装了gcc-4.6版本&#xff0c;版本信息都是正常显示的&#xff0c;刚安装上去的时候也是可以用的。但不知道什么原因突然不能…
阅读更多...
【LDLTS】拉普拉斯深能级瞬态光谱

【LDLTS】拉普拉斯深能级瞬态光谱

Laplace deep level transient spectroscopy&#xff08;拉普拉斯深能级瞬态光谱&#xff0c;简称LDLTS&#xff09;是一种用于分析和表征半导体材料中深层能级缺陷的技术。它是传统能级瞬态光谱&#xff08;DLTS&#xff09;方法的扩展和改进&#xff0c;特别适用于解决传统DL…
阅读更多...
穿山甲广告平台SDK接入效果怎么样？

穿山甲广告平台SDK接入效果怎么样？

广告收入是大多数开发者的应用变现收入来源&#xff0c;如何进行流流量变现是从应用设计之初就需要开发者思考的问题。 穿山甲广告平台作为国内第三方广告变现平台&#xff0c;是不少开发者选择的对接平台。 穿山甲广告平台的广告类型较多&#xff0c;有信息流&#xff0c;ba…
阅读更多...
最新文章

Copyright @ 2022~2023