[C++入门]---List的使用及模拟实现

2023-09-16 11:32:39

文章目录

1.list的介绍

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

2.list的使用

template < class T, class Alloc = allocator<T> > class list;
//list的使用需要使用显示实例化才能使用

2.1list的构造函数

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

eg：

void testlist1()
{
	list<int> lt1;
	list<int> lt2(10, 6);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout<<endl;
	list<int> lt3(lt2);
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;
	list<int> lt4(lt3.begin(), lt3.end());
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码运行结果为：

2.2list modifiers

void push_front (const value_type& val);
//在首元素前插入值为val的元素
void pop_front();
//删除val的第一个元素
void push_back (const value_type& val);
//在list的尾部插入值为val的
void pop_back();
//删除list中最后一个元素
single element (1)	
iterator insert (iterator position, const value_type& val);
//在list position位置插入值为val的元素
fill (2)	
    void insert (iterator position, size_type n, const value_type& val);
//在list position的位置插入n个值为val的元素
range (3)	
template <class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);
//在list position的位置插入[first,last]区间的元素
iterator erase (iterator position);
//删除position位置的值
iterator erase (iterator first, iterator last);
//删除[first,last)区间的元素
void swap (list& x);
//交换两个list中的元素
void clear();
//清空list中的数据

eg1：

void testlist2()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.pop_front();
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.push_front(100);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.pop_back();
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述
eg2：

void testlist3()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	list<int>::iterator it = lt1.begin();
	//在it位置插入99
	lt1.insert(it, 99);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	it = lt1.begin();
	//在it位置插入5个6
	lt1.insert(it, 5, 6);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	it = lt1.begin();
	list<int> lt2(6, 5);
	lt1.insert(it, lt2.begin(), lt2.end());
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述
eg3：

void testlist4()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	list<int>::iterator it = lt1.begin();
	lt1.erase(it);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.erase(lt1.begin(), lt1.end());
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述
eg4：

void testlist5()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	list<int> lt2(5, 6);
	printf("lt1的当前元素:");
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	printf("lt2的当前元素:");
	for (auto& e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	swap(lt1, lt2);
	printf("lt1的当前元素:");
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	printf("lt2的当前元素:");
	for (auto& e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述
eg5：

void testlist6()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	//清空lt1原有数据后插入66
	lt1.clear();
	lt1.push_back(66);
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述

2.3list capacity

bool empty() const;
//检测list是否为空，是返回true，否则返回false
size_type size() const;
//返回list中有效节点的个数

2.4list elment access

reference front();
const_reference front() const;
//返回list的第一个节点中值的引用
reference back();
const_reference back() const;
//返回list的最后一个节点中值的引用

eg1：

void testlist7()
{
	list<int> lt1;
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt1.push_back(50);
	lt1.push_back(60);
	cout << "list头部元素为:" << lt1.front() << endl;
	cout << "list尾部元素为:" << lt1.back() << endl;	
}

代码运行的结果为：
在这里插入图片描述

2.5iterator的使用

iterator begin();
const_iterator begin() const;
//返回第一个元素的迭代器
iterator end();
const_iterator end() const;
//返回最后一个元素下一个位置的迭代器
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
//返回第一个元素的reverse_iterator,即end位置
reverse_iterator rend();
const_reverse_iterator rend() const;
//返回最后一个元素下一个位置的reverse_iterator,即begin位置

list容器使用迭代器

void testlist8()
{
	list<int> lt1(5, 6);
	list<int>::iterator it = lt1.begin();	
	while (it != lt1.end())
	{
		cout << *it <<" ";
		it++;
	}
	cout << endl;
}

代码运行的结果为：
在这里插入图片描述
迭代器分类：

input iterator//输入迭代器
output iterator//输出迭代器
forward iterator//单向迭代器可以++ 适用forward_list/unorderd_xxx容器
bidirectional iterator//双向迭代器可以++/-- 适用list/map/set容器
random access iteartor//任意迭代器可以++/--/+/- 适用于vector/string/deque容器

在这里插入图片描述

随机迭代器可以使用双向迭代器，反之双向迭代器不可以使用随机迭代器！较多功能的容器迭代器可以使用适配较少功能的迭代器的算法接口函数，反之则不可以！

栗子：
list的迭代器为：
在这里插入图片描述
算法接口函数为：
在这里插入图片描述
在这里插入图片描述

void testlist9()
{
	list<int> lt1;
	lt1.push_back(16);
	lt1.push_back(8);
	lt1.push_back(99);
	lt1.push_back(18);
	lt1.push_back(36);
	lt1.push_back(6);
	//不可以使用algorithm
	//sort(lt1.begin(), lt1.end());
	//可以使用list自己的sort进行排序
	lt1.sort();
	for (auto& e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

代码编译运行的结果为：
在这里插入图片描述

list的迭代器为双向迭代器，不能使用算法接口函数中适配任意迭代器的sort函数，只能使用list的sort函数。

3.list的模拟实现

3.1list的源码

#pragma once
#include<iostream>
using namespace std;
namespace newspace
{
	template<class T>
	struct list_node
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _val;

		list_node(const T& val = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}
	};
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		Node* _node;
		typedef __list_iterator<T, Ref, Ptr> self;
		__list_iterator(Node* node)
			:_node(node)
		{}

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

		Ptr operator->()
		{
			return &_node->_val;
		}
		
		//__list_iterator<T,Ref,Ptr>& operator++()
		self& operator++()
		{
			_node = _node->_next;

			return *this;
		}
		__list_iterator<T, Ref, Ptr> operator++(int)
		//self operator++(int)
		{
			//__list_iterator<T, Ref, Ptr> tmp(*this);
			self tmp(*this);
			_node = _node->_next;

			return tmp;
		}
		__list_iterator<T, Ref, Ptr>& operator--()
		//self& operator--(int)
		{
			_node = _node->_prev;

			return *this;
		}
		//__list_iterator<T, Ref, Ptr> operator--(int)
		self operator--(int)
		{
			//__list_iterator<T, Ref, Ptr> tmp(*this);
			self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}
		bool operator==(const __list_iterator<T, Ref, Ptr>& it)
		{
			return _node == it._node;
		}
		bool operator!=(const __list_iterator<T, Ref, Ptr>& it)
		{
			return _node != it._node;
		}
	};
	//template<class T>
	//struct __list_const_iterator
	//{
	//	typedef list_node<T> Node;
	//	Node* _node;

	//	__list_const_iterator(Node* node)
	//		:_node(node)
	//	{}

	//	const T& operator*()
	//	{
	//		return _node->_val;
	//	}

	//	__list_const_iterator<T>& operator++()
	//	{
	//		_node = _node->_next;

	//		return *this;
	//	}
	//	__list_const_iterator<T>& operator++(int)
	//	{
	//		__list_const_iterator<T> tmp(*this);
	//		_node = _node->_next;

	//		return *this;
	//	}
	//	bool operator==(const __list_const_iterator<T>& it)
	//	{
	//		return _node == it._node;
	//	}
	//	bool operator!=(const __list_const_iterator<T>& it)
	//	{
	//		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;
		//这样设计太冗余了
		//typedef __list_const_iterator<T> const_iterator;
		
		//这样设计const迭代器是不行的，因为const迭代器期望修饰内容不被修改
		//这样设计迭代器本身不能修改
		//typedef const _list_iterator<T> const_iterator;
		//如何设计const对象的iterator
		//const T* ptr1;//ptr1本身不能修改
		//T* const ptr2;//ptr2指向的内容不能修改
		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->_prev = _head;
			_head->_next = _head;
			_size = 0;
		}
		//构造函数
		list()
		{
			empty_init();
		}
		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);
		}
		const list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		void clear()
		{
			if (_head != nullptr)
			{
				iterator it = begin();
				while (it != end())
				{
					it = erase(it);
				}
				_size = 0;
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}
		//void push_back(const T& x)
		//{
		//	Node* tail = new Node(x);
		//	tail->_prev = _head->_prev;
		//	tail->_prev->_next = tail;

		//	_head->_prev = tail;
		//	tail->_next = _head;
		//}
		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);
			//newnode->_prev = tail;
			//tail->_next = newnode;

			//_head->_prev = newnode;
			//newnode->_next = _head;
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(end()--);
		}
		void pop_front()
		{
			erase(begin());
		}
		//在pos位置插入数据
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			
			prev->_next = newnode;
			newnode->_prev = prev;

			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return newnode;
		}
		//删除pos位置的数据
		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;
			--_size;
			delete cur;

			return next;
		}
		size_t size()const
		{
			//const_iterator it = begin();
			//size_t size = 0;
			//while (it != end())
			//{
			//	size++;
			//	it++;
			//}
			//return size;
			return _size;
		}
	private:
		Node* _head;
		size_t _size;
	};
更多推荐

Chrome扩展开发实战：网页图片抓取，打造专属自己的效率插件

🏆作者简介，黑夜开发者，CSDN领军人物，全栈领域优质创作者✌，CSDN博客专家，阿里云社区专家博主，2023年6月csdn上海赛道top4。🏆数年电商行业从业经验，历任核心研发工程师，项目技术负责人。🏆本文已收录于专栏：100个JavaScript的小应用。🎉欢迎👍点赞✍评论⭐收藏文章目录🚀一、背景🚀二

【C++多线程】Lambda表达式

定义Lambda表达式可以说是c++11引用的最重要的特性之一，虽然跟多线程关系不大，但是它在多线程的场景下使用很频繁，所以在多线程这个主题下介绍它更合适。Lambda来源于函数式编程的概念，也是现代编程语言的一个特点。C++11这次终于把Lambda加进来了，令人非常兴奋，因为Lambda表达式能够大大简化代码复杂度

《DevOps实践指南》- 读书笔记（七）

DevOps实践指南Part5第三步：持续学习与实验的技术实践19.将学习融入日常工作19.1建立公正和学习的文化19.2举行不指责的事后分析会议19.3尽可能广泛地公开事后分析会议结果19.4降低事故容忍度，寻找更弱的故障信号19.5重新定义失败，鼓励评估风险19.6在生产环境注入故障来恢复和学习19.7创建故障演练

利用容器技术优化DevOps流程

利用容器技术优化DevOps流程随着云计算的快速发展，容器技术也日益流行。容器技术可以打包和分发应用程序，并实现快速部署和扩展。在DevOps流程中，容器技术可以大大优化开发、测试、部署和运维各个环节。本文将介绍如何利用容器技术优化DevOps流程。首先，让我们了解一下背景知识。在传统的软件开发过程中，开发人员需要在本

DevOps&Apipost

DevOps旨在通过自动化流程和改善协作，实现软件开发、测试和交付的一体化，从而提高软件交付的质量和速度。为了提高工作效率，加快软件的交付流程，越来越多企业的选择DevOps工作流程。其中API管理的地位非常重要。随着API数量的大幅增长，也带来了新的API管理需求。如何在DevOps工作流中进行API全生命周期管理，

STM32WB55开发(1)----监测STM32WB连接状态

STM32WB55开发----1.监测STM32WB连接状态概述硬件准备视频教学样品申请完整代码下载选择芯片型号配置时钟源配置时钟树RTC时钟配置查看开启STM32_WPAN条件配置HSEM配置IPCC配置RTC启动RF开启蓝牙LED配置设置工程信息工程文件设置参考文档SVCCTL_App_Notification结果

STM32WB55开发(5)----调整射频功率

STM32WB55开发----5.调整射频功率概述硬件准备视频教学样品申请源码下载选择芯片型号配置时钟源配置时钟树RTC时钟配置查看开启STM32_WPAN条件配置HSEM配置IPCC配置RTC启动RF开启蓝牙开启串口调试配置蓝牙参数设置工程信息工程文件设置Keil工程配置代码配置射频功率ACI_HAL_SET_TX_

在Kubernetes上安装和配置Istio：逐步指南，展示如何在Kubernetes集群中安装和配置Istio服务网格

🌷🍁博主猫头虎带您GotoNewWorld.✨🍁🦄博客首页——猫头虎的博客🎐🐳《面试题大全专栏》文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺🌊《IDEA开发秘籍专栏》学会IDEA常用操作，工作效率翻倍~💐🌊《100天精通Golang(基础入门篇）》学会Golang语言，畅玩云原生，走遍大

基于 STM32自研多任务+SpringBoot+Vue 农业大棚智能调光系统

工作以后常常容易感到疲于奔命，即使在周末也没有得到高质量的休息。打工人/学生党如何过周末？你有哪些延长周末和下班时间的好方法吗？-方法就是多积累，多发博客，将感悟全写出来！！，接下来我给大家展示一个课程设计：源码和硬件端代码就不与展示了，在该博客的资源绑定中，大家如果有兴趣可以参考一下。前后端代码保存在我的资源中我的主

STM32 cubemx配置USART DMA传输

文章目录前言一、DMA概念二、STM32DMA数据手册分析3.DMA模式介绍4.cubemx配置总结前言本篇文章来讲解DMA的概念，并使用DMA来进行串口的数据收发。一、DMA概念DMA（DirectMemoryAccess，直接内存访问）是一种计算机系统的技术，允许外部设备（如硬盘驱动器、网络适配器或图形卡）直接与计

大数据与人工智能的未来已来

大数据与人工智能的定义大数据：大数据指的是规模庞大、复杂性高、多样性丰富的数据集合。这些数据通常无法通过传统的数据库管理工具来捕获、存储、管理和处理。大数据的特点包括"3V"：大量（Volume）：大数据集合包含大量的数据，通常是以TB（千兆字节）或PB（百万兆字节）为单位。多样性（Variety）：大数据包括各种类型

热文推荐
  1. 【Java 基础篇】深入理解Java HashMap：使用注意事项和性能优化

    Java是一种广泛使用的编程语言，而集合是Java编程中不可或缺的一部分。在Java的集合框架中，HashMap是一个常用的数据结构，用于存储键值对。本文将深入介绍HashMap集合，从基础到高级用法，帮助您更好地理解和利用它。什么是HashMap？HashMap是Java集合框架中的一个类，它实现了Map接口，用于存

  2. 求生之路2服务器搭建插件安装及详细的游戏参数配置教程windows

    求生之路2服务器搭建插件安装及详细的游戏参数配置教程windows大家好我是艾西，最近研究了下l4d2（求生之路2）这款游戏的搭建以及架设过程。今天就给喜欢l4d2这款游戏的小伙伴们分享下怎么搭建架设一个自己的服务器。毕竟自己当服主是热爱游戏每一个人的梦想，在自己的服务器里为所欲为在游戏里成就自己。（注：因PT原因本文

  3. RocketMQ消息的分类

    一、普通消息1消息发送分类Producer对于消息的发送方式也有多种选择，不同的方式会产生不同的系统效果。同步发送消息同步发送消息是指，Producer发出⼀条消息后，会在收到MQ返回的ACK之后才发下⼀条消息。该方式的消息可靠性最高，但消息发送效率太低。异步发送消息异步发送消息是指，Producer发出消息后无需等待

  4. 【Jetpack】Navigation 导航组件 ④ ( Fragment 跳转中使用 safe args 安全传递参数 )

    文章目录一、页面跳转间的传统的数据传递方式1、传统的数据传递方式-Bundle传递数据1、Navigation组件中的Bundle数据传递2、传统数据传递实现步骤3、FragmentA完整代码示例4、FragmentB完整代码示例5、执行结果2、使用Bundle传递数据安全性差二、页面跳转间的传统的数据传递方式1、导入

  5. C++--哈希表的实现及unorder_set和unorder_map的封装

    1.什么是哈希表哈希表是一种数据结构，用来存放数据的，哈希表存放的数据是无序的，可以实现增删查，当时不能修改数据。可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。该

  6. 知乎万赞的：网络安全系统自学就业路线，建议收藏!

    为什么说网络安全是新风口？近几年，随着移动互联网、大数据、云计算、人工智能等新一代信息技术的快速发展，围绕网络和数据的服务与应用呈现爆发式增长，丰富的应用场景下暴露出越来越多的网络安全风险和问题。但是，我国网络安全整体投入不高。网络安全建设方面，国内网络安全投入占信息化的投入比例大概不到百分之3%，而欧美等发达国家均在

  7. Python 超高频常见字符操作【建议收藏】

    文章目录前言1.字符串截取2.字符串拼接3.字符串搜索4.字符串格式化5.字符串替换6.字符串去除空格7.字符串截取8.字符串反转总结前言为了巩固所学的知识，作者尝试着开始发布一些学习笔记类的博客，方便日后回顾。当然，如果能帮到一些萌新进行新技术的学习那也是极好的。作者菜菜一枚，文章中如果有记录错误，欢迎读者朋友们批评

  8. A Survey of Hallucination in “Large” Foundation Models

    本文是LLM系列文章，针对《ASurveyofHallucinationin“Large”FoundationModels》的翻译。大型基础模型幻觉现象综述摘要1引言2大语言模型中的幻觉3大图像模型中的幻觉4大视频模型中的幻觉5大音频模型中的幻觉6幻觉不总是有害的：不同的视角7结论和未来方向7.1幻觉的自动评估7.2利

  9. 解密堆排序与TopK问题

    📙作者简介：清水加冰，目前大二在读，正在学习C/C++、Python、操作系统、数据库等。📘相关专栏：C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。欢迎点赞👍收藏⭐留言📝如有错误还望各路大佬指正！✨每一次努力都是一种收获，每一次坚持都是一种成长✨目录前言1.堆排序1.1时间