【C++】STL — List的接口讲解 +详细模拟实现

前言：
本章我们将学习STL中另一个重要的类模板list…

  • list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  • list的底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  • list与forward_list非常相似：主要区别在于forward_list对象是单链接列表，因此它们只能向前迭代，以换取更小、更高效。
  • 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  • 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，需要线性的时间开销。

list是带哨兵位头节点的双向循环链表,
在list中进行插入节点不会导致list的迭代器失效,
只有删除节点时才会出现失效问题，并且失效的只是指向被删除节点的迭代器,会有野指针问题，其他迭代器不受影响

目录

    • 1. list的使用
      • 1.1 list的初始化 + 迭代器的使用
      • 1.2 对list的排序
    • 2. list的模拟实现（list.h）
      • 2.1 链表结点的申请：
      • 2.2 用类封装List 的迭代器
      • 2.3 List链表的实现
      • 2.4 迭代器失效的问题

1. list的使用

我们学习的STL中的list是一种：带头双向循环链表。（带有哨兵位头结点的）

  • 带头双向循环链表 – 链表中的最优设计
  • 可以实现任意位置〇(1)的插入删除，只需要改前后的关系

1.1 list的初始化 + 迭代器的使用

在我们使用list之前我们需要先包一下头文件#include< list >
在这里插入图片描述

#include <iostream>
#include <list>

int main ()
{
  // constructors used in the same order as described above:
  std::list<int> first;                                // empty list of ints
  std::list<int> second (4,100);                       // four ints with value 100
  std::list<int> third (second.begin(),second.end());  // iterating through second
  std::list<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
  return 0;
}

1.2 对list的排序

对于一般的容器而言，我们包一个算法库 #incldue < alogrithm > 可以对普通的容器进行排序。

void test_list2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(4);
	v.push_back(2);
	v.push_back(4);
	v.push_back(3);
	sort(v.begin(), v.end());
	
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}
  • 像vector和string而言，这种连续的容器可以直接用库中的sort
  • 而对于list而言和之前的顺序容器有所区别，因为其链式结构，库中的算法不支持
  • list单独实现了一个自己的排序
  • 但是list的排序效率很低
    在这里插入图片描述

注意：
可见把list的数据拷贝到vector中再，用sort算法对vector中排序，再将vector中的数据拷贝到list中都比直接用list排序要快，所以list的排序效率很低。

2. list的模拟实现（list.h）

在这里插入图片描述

2.1 链表结点的申请：

namespace Joker
{
    //list的节点类
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
	};

注意：

- 默认生成的析构函数够用。

2.2 用类封装List 的迭代器

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

    1. 原生态指针，比如：vector
    1. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
      1. 指针可以解引用，迭代器的类中必须重载operator*()
      2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
      3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
        至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前 移动，所以需要重载，如果是forward_list就不需要重载–
      4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
   template<class T, class Ref, class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr>Self;

     public:
         // 构造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}
      // 具有指针类似行为
		Ref operator*() 
		{ 
			return _node->_data;
		}

		Ptr operator->() 
		{ 
			//return &(operator*()); 
			return &_node->_data;
		}	//
		// 迭代器支持移动
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}
         //--it
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
        //it--
		Self operator--(int)
		{
			Self temp(*this);
			_node = _node->_prev;
			return temp;
		}
//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{ 
			return _node != l._node;
		}

		bool operator==(const Self& l)const
		{ 
			return _node != l._node;
		}
		Node* _node;
	};

注意：

  • 析构函数（不需要写）-- 节点不属于迭代器，不需要迭代器释放

  • 编译器生成的默认析构函数够用，对内置类型不敢处理，只对自定义类型处理

  • 拷贝构造和赋值重载（不需要写）

  • 默认生成的浅拷贝就可以

（2）运算符重载 - > ：

Ptr operator->() 
	{
		//return &(operator*());0
		return &_node->_data;
	}
	返回的是一个指针。

优化如下：

  • it.operator->() – 返回类型是AA*的迭代器
  • it.operator->() ->_data;
  • 编译器为了可读性进行了优化处理
  • 如果不优化应该是it->->_data;
  • 优化以后，省略了一个->

2.3 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;

		// List的构造
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(int n, const T& value = T())
		{
			empty_init();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

      //创造一个哨兵位头结点出来，通用
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}
		
		template <class Iterator（大写I）>
		list(Iterator first, Iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
//拷贝构造现代写法：--需要使用深拷贝
		list(const list<T>& l)
		{
		 //创造一个哨兵位头节点出来，不初始化就是随机值
			empty_init();
		// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}
		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

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

		///
		// List的迭代器
		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());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意：List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val) 
		{ 
		//Node* tail=_head->_prev;
		 //Node* newnode=new node(x);
		 _head     tail  newnode
		 //tail->_next=newnode;
		 //newnode->_prev=tail;
		 //newnode->_next=_head;
		 //_head->prev=newnode;
			insert(end(), val); 
		}

		void pop_back() 
		{ 
			erase(--end()); 
		}

		void push_front(const T& val) 
		{ 
			insert(begin(), val); 
		}

		void pop_front() 
		{ 
			erase(begin()); 
		}

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(bite::list<T>& l)
		{
			std::swap(_head, l._head);
		}
	private:
		Node* _head;
	};
}

2.4 迭代器失效的问题

  • list insert迭代器不失效，不存在野指针的问题，也不存在意义变了的问题
  • list erase(it)以后，迭代器是会失效的,是野指针问题

解决办法：

  • 之前vector容器迭代器失效时解决办法一样，使用返回值接收。

尾声
看到这里，相信大家对这个C++有了解了。
如果你感觉这篇博客对你有帮助，不要忘了一键三连哦

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

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

相关文章

Conntroller内存马详解（2）

Conntroller内存马详解（2）

流程分析 获取context 第一种&#xff1a;getCurrentWebApplicationContext() // getCurrentWebApplicationContext方法获得的是一个XmlWebApplicationContext实例类型的Root WebApplicationContext。WebApplicationContext context ContextLoader.getCurrentWebApplication…
阅读更多...
docker部署nginx并实现https

docker部署nginx并实现https

文章目录 docker部署nginx并实现https1、服务器环境2、安装docker3、准备证书4、准备nginx配置文件和dockerfile文件5、创建nginx镜像与容器6、验证访问 docker部署nginx并实现https 1、服务器环境 [rootliuyanfen12 ~]#systemctl stop firewalld [rootliuyanfen12 ~]#setenf…
阅读更多...
Flutter笔记：美工设计.导出视频到RIVE

Flutter笔记：美工设计.导出视频到RIVE

Flutter笔记 美工设计.导出视频到RIVE - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28…
阅读更多...
RabbitMQ之顺序消费

RabbitMQ之顺序消费

什么是顺序消费 例如&#xff1a;业务上产生者发送三条消息&#xff0c; 分别是对同一条数据的增加、修改、删除操作&#xff0c; 如果没有保证顺序消费&#xff0c;执行顺序可能变成删除、修改、增加&#xff0c;这就乱了。 如何保证顺序性 一般我们讨论如何保证消息的顺序性&…
阅读更多...
【Linux】进程的隔离和控制：namespace 隔离、cgroup 控制

【Linux】进程的隔离和控制：namespace 隔离、cgroup 控制

文章目录 五、namespace 隔离dd -- 读取、转换并输出数据mkfs -- 格式化文件系统df -- 显示文件系统磁盘使用情况mount -- 加载文件系统到指定的加载点unshare -- 创建子进程&#xff0c;同时与父程序不共享namespace一个 demo 六、cgroup(Control Group) 相关命令pidstat -- 监…
阅读更多...
【LeetCode刷题记录】230. 二叉搜索树中第K小的元素

【LeetCode刷题记录】230. 二叉搜索树中第K小的元素

230 二叉搜索树中第K小的元素 给定一个二叉搜索树的根节点 root &#xff0c;和一个整数 k &#xff0c;请你设计一个算法查找其中第 k 个最小元素&#xff08;从 1 开始计数&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,1,4,null,2], k 1 输出&#xff1…
阅读更多...
2024年深圳杯东三省联赛数模竞赛A题代码改进-更加合理的结果

2024年深圳杯东三省联赛数模竞赛A题代码改进-更加合理的结果

4月下旬深圳杯开赛后第二天就推出了完整版的论文&#xff0c;经过长达半个月大家再售后群的讨论分析&#xff0c;我们又重新对之前思路下写的代码进行了改进。本次改进的结果&#xff0c;我们特地参考了网上一些常见的火箭及其相关的级别分离高度&#xff1a;&#xff08;我们的…
阅读更多...
c语言刷题——输出图案

c语言刷题——输出图案

1.输出用“*”组成的X形图案 题目&#xff1a;请打印用“*”组成的X形图案 描述&#xff1a; 多组输入&#xff0c;一个整数&#xff08;2~20&#xff09;&#xff0c;表示输出的行数&#xff0c;也表示组成“X”的反斜线和正斜线的长度。 输出描述&#xff1a; 针对每行输…
阅读更多...
【C语言】指针篇- 深度解析Sizeof和Strlen：热门面试题探究（5/5)

【C语言】指针篇- 深度解析Sizeof和Strlen：热门面试题探究（5/5)

&#x1f308;个人主页&#xff1a;是店小二呀 &#x1f308;C语言笔记专栏&#xff1a;C语言笔记 &#x1f308;C笔记专栏&#xff1a; C笔记 &#x1f308;喜欢的诗句:无人扶我青云志 我自踏雪至山巅 文章目录 一、简单介绍Sizeof和Strlen1.1 Sizeof1.2 Strlen函数1.3 Sie…
阅读更多...
零基础学习数据库SQL语句之查询表中数据的DQL语句

零基础学习数据库SQL语句之查询表中数据的DQL语句

是用来查询数据库表的记录的语句 在SQL语句中占有90%以上 也是最为复杂的操作 最为繁琐的操作 DQL语句很重要很重要 初始化数据库和表 USE dduo;create table tb_emp(id int unsigned primary key auto_increment comment ID,username varchar(20) not null unique comment…
阅读更多...
大语言模型中的第一性原理：Scaling laws

大语言模型中的第一性原理：Scaling laws

大语言模型的尺度定律在大语言模型的训练过程中起到了非常重要的作用。即使读者不参与大语言模型的训练过程&#xff0c;但了解大语言模型的尺度定律仍然是很重要的&#xff0c;因为它能帮助我们更好的理解未来大语言模型的发展路径。 1. 什么是尺度定律 尺度定律&#xff08…
阅读更多...
stamps做sbas-insar，时序沉降图怎么画？

stamps做sbas-insar，时序沉降图怎么画？

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…
阅读更多...
【跟我学RISC-V】（二）RISC-V的基础知识学习与汇编练习

【跟我学RISC-V】（二）RISC-V的基础知识学习与汇编练习

写在前面&#xff1a; 这篇文章是跟我学RISC-V的第二期&#xff0c;是第一期的延续&#xff0c;第一期主要是带大家了解一下什么是RISC-V,是比较大体、宽泛的概念。这一期主要是讲一些基础知识&#xff0c;然后进行RISC-V汇编语言与c语言的编程。在第一期里我们搭建了好几个环…
阅读更多...
WPF之绑定验证（错误模板使用）

WPF之绑定验证（错误模板使用）

1&#xff0c;前言&#xff1a; 默认情况下&#xff0c;WPF XAML 中使用的绑定并未开启绑定验证&#xff0c;这样导致用户在UI上对绑定的属性进行赋值时即使因不符合规范内部已抛出异常&#xff08;此情况仅限WPF中的数据绑定操作&#xff09;&#xff0c;也被程序默认忽略&…
阅读更多...
4.【Orangepi Zero2】Linux定时器(signal、setitimer)，软件PWM驱动舵机（SG90）

4.【Orangepi Zero2】Linux定时器(signal、setitimer)，软件PWM驱动舵机（SG90）

Linux定时器&#xff08;signal、setitimer&#xff09;&#xff0c;软件PWM驱动舵机&#xff08;SG90&#xff09; signalsetitimer示例 软件PWM驱动舵机&#xff08;SG90&#xff09; signal 详情请看Linux 3.进程间通信&#xff08;shmget shmat shmdt shmctl 共享内存、si…
阅读更多...
【计算机网络】循环冗余校验：Cyclic Redundancy Check

【计算机网络】循环冗余校验：Cyclic Redundancy Check

1. 任务目标 利用循环冗余校验&#xff08;CRC&#xff09;检测错误。 循环冗余校验&#xff08;英语&#xff1a;Cyclic redundancy check&#xff0c;通称 CRC&#xff09;是一种根据网上数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数&#xff0c;主要用来…
阅读更多...
智慧文旅展现文化新风貌，科技助力旅行品质升级：借助智慧技术，文旅产业焕发新生机，为旅行者带来更高品质的文化体验之旅

智慧文旅展现文化新风貌，科技助力旅行品质升级：借助智慧技术，文旅产业焕发新生机，为旅行者带来更高品质的文化体验之旅

一、引言 在数字化、智能化的浪潮下&#xff0c;文旅产业正迎来前所未有的发展机遇。智慧文旅作为文旅产业与信息技术深度融合的产物&#xff0c;不仅为旅行者带来了全新的文化体验&#xff0c;也为文旅产业注入了新的活力。本文旨在探讨智慧文旅如何借助智慧技术展现文化新风…
阅读更多...
C++：二叉搜索树的底层模拟实现

C++：二叉搜索树的底层模拟实现

概念&#xff1a; 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树&#xff1a; 搜索二叉树的操作&#xff1a; int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};二叉搜索树需要满足左子树比根小&#xff0c;右子树比根大&#xff0c;…
阅读更多...
Leetcode—1235. 规划兼职工作【困难】（upper_bound、自定义排序规则）

Leetcode—1235. 规划兼职工作【困难】（upper_bound、自定义排序规则）

2024每日刷题&#xff08;125&#xff09; Leetcode—1235. 规划兼职工作 算法思想 实现代码 class Solution { public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {int n startTime.size();vec…
阅读更多...
循环神经网络完整实现（Pytorch 13）

循环神经网络完整实现（Pytorch 13）

一 循环神经网络的从零开始实现 从头开始基于循环神经网络实现字符级语言模型。 %matplotlib inline import math import torch from torch import nn from torch.nn import functional as F from d2l import torch as d2lbatch_size, num_steps 32, 35 train_iter, vocab …
阅读更多...
最新文章

Copyright @ 2022~2023