【STL】list

目录

1. list的使用

1.1 list的构造

 1.2 list iterator的使用

1.3 list capacity

1.4 list element access

1.5 list modifiers

1.6 list的迭代器失效

2. list的模拟实现

3. list与vector的对比


1. list的使用

1.1 list的构造

 1.2 list iterator的使用

1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动

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

1.3 list capacity

1.4 list element access

1.5 list modifiers

1.6 list的迭代器失效

        迭代器失效即迭代器所指向的节点的无效,即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代 器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

2. list的模拟实现

#pragma once
#include<assert.h>

namespace erdong
{
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

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

	// typedef __list_iterator<T, T&, T*> iterator;
	// typedef __list_iterator<T, const T&, const T*> const_iterator;
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

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

		Ptr operator->()
		{
			return &_node->_val;
		}

		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) const
		{
			return _node != it._node;
		}

		bool operator==(const self& it) const
		{
			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 tmp;
		}

		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 T* ptr1;
		// T* const ptr2;

		// 如何设计const迭代器?

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

		iterator end()
		{
			return _head;
			//return iterator(_head);
		}

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

		const_iterator end() const
		{
			return _head;
			//return const_iterator(_head);
		}

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

			_size = 0;
		}

		list()
		{
			empty_init();
		}

		// lt2(lt1)
		list(const list<T>& lt)
		//list(const list& 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)
		//list& operator=(list lt)
		{
			swap(lt);

			return *this;
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

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

			_size = 0;
		}

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

		// 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->_next = cur;

			cur->_prev = newnode;
			newnode->_prev = prev;

			++_size;

			return newnode;
		}

		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;

			--_size;

			return next;
		}

		size_t size()
		{
			/*size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}

			return sz;*/

			return _size;
		}

	private:
		Node* _head;
		size_t _size;
	};

	void Print(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			// (*it) += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

3. list与vector的对比

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

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

相关文章

雨污管网开挖深度的计算

一般的管网工程都有纵断面设计图&#xff0c;结合纵断面里的 管内底埋深-管厚度(直径0.6管厚0.06&#xff0c;直径0.8承插管直径0.08厚) - 砂砾石基础一般0.15厚 - 路面结构层厚度就是沟槽开挖深度了&#xff0c;是不是很简单。 管内底埋深其实就是管内流水面到设计路面顶的高…

PyCharm+PyQt5配置方法

一、前言 PyQt5PyQt5是一套Python绑定Digia QT5应用的框架。Qt库是最强大的GUI库之一PyQt5-toolsPyQt5中没有提供常用的Qt工具&#xff0c;比如图形界面开发工具Qt Designer&#xff0c;PyQt5-tools中包含了一系列常用工具Qt Designer可以通过Qt Designer来编写UI界面&#xf…

Docker快速上手及常用命令速查

Docker快速上手 安装 在ubuntu上安装docker: sudo apt-get install docker docker -v #查看版本在centos7上安装docker&#xff1a;(docker在YUM源的Extras仓库中) yum install docker systemctl start dockerdocker常用命令速查 #查看docker信息 docker info #查看本地镜…

网络基础三——其他周边问题

3.1ARP原理 ​ ARP不是一个单纯的数据链路层的协议&#xff0c;而是一个介于数据链路层和网络层之间的协议&#xff1b; ​ 以广播的形式(主机号填成全1)构建Mac帧&#xff0c;发送ARP请求包&#xff0c;告诉所有在局域网的主机我的IP地址和Mac帧&#xff0c;与目的IP相同的主…

[lesson16]类的真正形态

类的真正形态 类的关键字 struct在C语言中以及有了自己的含义&#xff0c;必须继续兼容 在C中提供了新的关键字class用于类的定义 class和struct的用法是完全相同的 在用struct定义类时&#xff0c;所有成员的默认访问级别为public 在用class定义类时&#xff0c;所有成员…

Leetcode算法训练日记 | day22

一、二叉搜索树的最近公共祖先 1.题目 Leetcode&#xff1a;第 235 题 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个结点 p、q&#xff0c;最近公共祖先表示为一个结点 x&#xff0c;满足…

liunx环境变量学习总结

环境变量 在操作系统中&#xff0c;环境变量是一种特殊的变量&#xff0c;它们为运行的进程提供全局配置信息和系统环境设定。本文将介绍如何自定义、删除环境变量&#xff0c;特别是对重要环境变量PATH的管理和定制&#xff0c;以及与环境变量相关的函数使用。 自定义环境变…

【复现】用友NC-Cloud文件上传漏洞_70

目录 一.概述 二 .漏洞影响 三.漏洞复现 1. 漏洞一&#xff1a; 四.修复建议&#xff1a; 五. 搜索语法&#xff1a; 六.免责声明 一.概述 用友NC Cloud大型企业数字化平台&#xff0c;深度应用新一代数字智能技术&#xff0c;完全基于云原生架构&#xff0c;打造开放、…

MySQL进阶之(七)EXPLAIN 详解

七、EXPLAIN 详解 7.1 查询性能那些事7.1.1 查看系统性能参数7.1.2 统计 SQL 的查询成本7.1.3 定位执行慢的 SQL&#xff1a;慢查询日志01、开启慢查询日志参数02、关闭慢查询日志03、删除慢查询日志 7.1.4 查看 SQL 执行成本&#xff1a;SHOW PROFILE 7.2 EXPLAIN 语句输出中各…

pyqt5 QScrollArea组件

本示例中&#xff0c;演示了QScrollArea的使用&#xff0c;以及QScrollBar的样式设定&#xff0c;在代码中使用setStyleSheet设置样式&#xff0c;记得要优先设置scrollArea&#xff0c;再设置窗口的样式&#xff0c;不然QScrollBar的样式会不起作用&#xff0c;使用QSS设置没有…

SGD随机梯度下降

一、补充概念&#xff1a; 目标函数&#xff08;Objective Function&#xff09;&#xff1a;这个术语通常指的是整个优化问题中需要最小化&#xff08;或最大化&#xff09;的函数。在机器学习和优化中&#xff0c;目标函数可以包括损失函数以及正则化项等。目标函数的最优化过…

Python程序设计 列表

教学案例八 列表 1. 计算并显示斐波那契数列 输入n,计算并显示斐波那契数列前n项.一行打印5项&#xff0c;每项显示宽度为6 什么是斐波那契数列 斐波那契数列&#xff08;Fibonacci sequence&#xff09;&#xff0c;又称黄金分割数列、 因数学家莱昂纳多斐波那契&#xff…

基于SSM+Jsp+Mysql的农产品供销服务系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

windows系统安装mysql5.7

1、下载 下载路径&#xff1a;https://downloads.mysql.com/archives/community/ 2、创建配置文件my.ini 下载压缩包解压到安装目录&#xff08;本机解压后在D:\mysql-5.7.44-winx64&#xff09; 在bin的同级目录下创建my.ini文件 my.ini文件 [mysql] # 设置mysql客户端默认字符…

接口自动化测试(python+pytest+requests)

一、选取自动化测试用例 优先级高:先实现业务流程用例、后实现单接口用例功能较稳定的接口优先开展测试用例脚本的实现二、搭建自动化测试环境 核心技术:编程语言:python;测试框架:pytest;接口请求:requests安装/验证requests:命令行终端分别输入 pip install requests / p…

6.1Python之字典的初识

【1】字典的创建与价值 字典&#xff08;Dictionary&#xff09;是一种在Python中用于存储和组织数据的数据结构。元素由键和对应的值组成。其中&#xff0c;键&#xff08;Key&#xff09;必须是唯一的&#xff0c;而值&#xff08;Value&#xff09;则可以是任意类型的数据。…

国内如何实现GPT升级付款

本来想找国外的朋友代付的&#xff0c;但是他告诉我他的信用卡已经被绑定了他也升级了所以只能自己想办法了。就在一位博主下边发现了这个方法真的可以。只是需要与支付宝验证信息。刚开始不敢付款害怕被骗哈哈&#xff0c;我反诈骗意识绝对杠杠的 该方法就是我们办理一张虚拟…

3D可视化技术亮相高铁站,引领智慧出行新潮流

在科技飞速发展的今天&#xff0c;我们的生活正经历着前所未有的变革。高铁站作为现代交通的重要枢纽&#xff0c;也在不断地创新和进步。 3D可视化技术通过三维立体的方式&#xff0c;将高铁站内部和外部的结构、设施、流线等以更加直观、生动的形式呈现出来。乘客们只需通过手…

2、java语法之循环、数组与方法(找工作版)

写在前面&#xff1a;整个系列文章是自己学习慕课相关视频&#xff0c;进行的一个总结。文章只是为了记录学习课程的整个过程&#xff0c;方便以后查漏补缺&#xff0c;找到对应章节。 文章目录 一、Java循环结构1、while循环2、do-while循环3、for循环4、嵌套循环5、break语句…

我认识的建站公司老板都躺平了,每年维护费都大几十万。

这些老板们过的悠哉游哉&#xff0c;大富大贵没有&#xff0c;达到中产&#xff0c;活得舒服&#xff0c;没毛病。 企业官网每年需要交维护费主要是因为以下几个原因&#xff1a; 网站服务器和域名费用&#xff1a;企业官网需要通过服务器进行托管和访问&#xff0c;同时需要…