C++STL【list链表】

list

1. list介绍

  • list文档（非官方）
    官方文档
  • list是双向带头循环链表，它可以在常数范围内的任意位置进行插入和删除操作。
  • list的迭代器是双向迭代器(bidirectional iterator)，它可以前后双向迭代。
    由容器的底层结构决定，STL迭代器有不同的种类：
    在这里插入图片描述
  • list的底层空间如下图所示：
    在这里插入图片描述
  • 正因list的底层空间如此，它相比其他容器：
    优点：在任意位置插入、删除元素的执行效率更高（相比vector、deque等）；
    缺点：不支持位置的随机访问，要访问某个节点，需要迭代器迭代；需要开辟额外的空间来储存下一个节点、上一个节点的地址；缓存命中率低。

2. list的常用接口

  • 与vector一样，list的许多接口中有很多别名：
    在这里插入图片描述

  1. 构造函数(constructor)

    (constructor)功能
    explicit list (const allocator_type& alloc = allocator_type());默认构造函数
    explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());用n个val值初始化
    template <class InputIterator>
    list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());    		用迭代器初始化（可以允许其他类型作为参数初始化）
    list (const list& x);拷贝构造函数
    list<int> lt1;
list<int> lt2(3, 2);
int nums[] = { 1,2,3 };
list<int> lt3(arr, arr + 3);
list<int> lt4(v3);

  2. 容量操作

    函数功能
    size_type size(); const返回有效元素个数
    bool empty(); const判断是否为空
    void resize (size_type n, value_type val = value_type());改变有效元素个数

  3. 迭代器

    函数功能
    iterator begin();
    const_iterator begin() const;    		返回容器开头的位置的迭代器
    iterator end();
    const_iterator end() const;    		返回容器最后一个有效元素的下一个位置的迭代器
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;    		返回容器最后一个有效元素的位置的迭代器
    reverse_iterator rend();
    const_reverse_iterator rend() const;    		返回容器开头的前一个位置的迭代器

    关于list的迭代器：

    1. 迭代器一般是指针，在string和vector中，因为底层空间是连续的，所以它们的迭代器可以直接使用指针；但是list不行，因为它的空间不是连续的，是多块由指针连接的小空间。因此list的迭代器必须做出改变，即重新封装。

    2. list的迭代器如下：
      在这里插入图片描述
      list迭代器被重新封装成为一个类，它的成员变量是一个节点的类型的指针，指向节点；另外在迭代器类中，还实现了一系列运算符重载，如*/->/!=/==/++/--，使得其与别的容器的迭代器功能一致。

    3. 关于迭代器内运算符->的重载：

    重载operator->，编译器进行了特殊处理。

    struct A
{
	A(int a1 = 0, int a2 = 0)
		: _a1(a1)
		, _a2(a2)
	{ }

	int _a1;
	int _a2;
};
void Test()
{
	list<A> la;
	A aa(1, 2);
	la.push_back(aa);
	list<A>::iterator it = la.begin();
	cout << it->_a1 << endl;
}

    operator->返回的是A*，it->_a1就等价于 A * _ a1，这不合语法，正确写法应该是it->->_a1，但是这么写很难看，于是编译器做了优化，自动替我们加上了一个->，于是我们只需写成这样即可：it->_ val

    1. 迭代器提供了一种不暴露容器底层设计的方法来访问容器内容。

  4. 访问元素

    函数功能
    reference front();
    const_reference front() const;    		访问链表开头一个元素
    reference back();
    const_reference back() const;    		访问链表最后一个元素
    int nums[] = { 1,2,3 };
list<int> lt(arr, arr + 3);
cout << lt.front() << endl;
cout << lt.back() << endl;

  5. 修改操作

    函数功能
    void push_back (const value_type& val);尾插一个值
    void pop_back();尾删一个值
    void push_front (const value_type& val);头插一个值
    void pop_front();头删一个值
    insert在某个位置插入元素
    erase删除某个位置的元素
    void swap (list& x);交换两个list对象
    void clear();清空有效元素

  6. 链表操作
    STL还提供了一些链表操作，如sort、reverse等，但是不常使用，这里就不多介绍了，若要查看，请移步官方文档。

3. 模拟实现list（部分接口）

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

namespace Myspace
{
	template <class T>
	struct list_node
	{
		list_node(const T& value = T())
			: _next(nullptr)
			, _pre(nullptr)
			, _val(value)
		{ }

		list_node<T>* _next;
		list_node<T>* _pre;
		T _val;
	};

	// 正向迭代器
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_iterator<T, Ref, Ptr> Self; // Self表示自己
		typedef list_node<T> Node;

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

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp = *this;
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp = *this;
			_node = _node->_pre;
			return tmp;
		}

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

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

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

		Node* _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;


		///
		// <构造>
		void CreatHead()
		{
			_head = new Node;
			_head->_next = _head->_pre = _head;
		}

		list()
		{
			CreatHead();
		}

		list(int n, const T& _value = T())
		{
			CreatHead();
			while (n--)
			{
				push_back(_value);
			}
		}

		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			CreatHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& lt)
		{
			CreatHead();
			//for (auto e : lt)
			//{
			//	push_back(e);
			//}
			list<T> temp(lt.begin(), lt.end());
			this->swap(temp);
		}

		list<T> operator=(list<T> lt)
		{
			if (lt._head != _head)
			{
				swap(lt);
			}
			return *this;
		}


		///
		// <迭代器>
		iterator begin()
		{
			return _head->_next; // 单参数的构造函数，可以进行整型提升，Node* 提升为iterator
		}

		iterator end()
		{
			return _head;
		}

		const_iterator begin() const
		{
			return _head->_next; // 单参数的构造函数，可以进行整型提升，Node* 提升为iterator
		}

		const_iterator end() const
		{
			return _head;
		}

		///
		// <容量>
		size_t size()
		{
			size_t sz = 0;
			Node* cur = _head->_next;
			while (cur != _head)
			{
				sz++;
				++cur;
			}
			return sz;
		}

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

		void resize(size_t n, const T& value = T())
		{
			size_t sz = size();
			if (n < sz)
			{
				while (n < sz)
				{
					pop_back();
					sz--;
				}
			}
			else
			{
				while (sz < n)
				{
					push_back(value);
					sz++;
				}
			}
		}

		///
		// <访问>
		T& front()
		{
			return _head->_next->_val;
		}

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

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

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

		///
		// <删除、插入>
		void push_back(const T& value)
		{
			insert(end(), value);
		}

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

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

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

		iterator insert(iterator pos, const T& value = T())
		{
			Node* newnode = new Node(value); // 待插入的新节点
			Node* cur = pos._node; // 取出pos迭代器的节点
			newnode->_pre = cur->_pre;
			newnode->_next = cur;
			cur->_pre->_next = newnode;
			cur->_pre = newnode;

			return newnode;
		}

		iterator erase(iterator pos)
		{
			assert(pos._node != _head);
			Node* cur = pos._node;
			Node* ret = cur->_next; // 保留一下返回值
			cur->_pre->_next = cur->_next;
			cur->_next->_pre = cur->_pre;
			delete cur;
			return ret;
		}

		void clear()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}
			_head->_next = _head->_pre = _head;
		}

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

	private:
		Node* _head;
	};
}

注意：

  1. 构造函数vector(int n, const T& value = T())接口需要重载多个（int/size_t/long），以防止创建对象时（vector<int> v(2,3);）编译器自动匹配到vector(InputIterator first, InputIterator last)这个接口。
    原因：编译器总会选择最匹配的接口。
  2. 在扩容时拷贝数据的时候，不要使用memcpy（上述代码的第151行），原因如下：
    如果模板实例化为string，那么此时就相当于memcpy(string1, string2, size)，将两个string类memcpy，一定是浅拷贝，因为string类本身有个char*的指针，需要动态开辟空间，memcpy仅仅是将两个指针指向了同一块空间，并没有开辟新的空间。
    直接赋值即可，赋值会调用string自己的赋值运算符重载，它自己会实现深拷贝。
    不止是string，其他任何动态管理空间的类都是如此。

4. 迭代器失效

list的结构是链状表，正因为它不是一块连续的空间，它的迭代器失效问题没有string和vector多。

只有在删除数据的时候，才可能引起迭代器失效。

  • 链表的insert没有迭代器失效的问题！
    因为没有扩容，不需要挪动数据，位置没有改变，迭代器还是指向那个节点。

  • 但是earse有迭代器失效的问题！
    因为节点释放了，迭代器却依旧指向那个位置。
    STL为erase增添了返回值，我们用完erase后要接收它的返回值，它返回的是删除的节点的下一个节点。

`，将两个string类memcpy，一定是浅拷贝，因为string类本身有个char*的指针，需要动态开辟空间，memcpy仅仅是将两个指针指向了同一块空间，并没有开辟新的空间。
直接赋值即可，赋值会调用string自己的赋值运算符重载，它自己会实现深拷贝。
不止是string，其他任何动态管理空间的类都是如此。

4. 迭代器失效

list的结构是链状表，正因为它不是一块连续的空间，它的迭代器失效问题没有string和vector多。

只有在删除数据的时候，才可能引起迭代器失效。

  • 链表的insert没有迭代器失效的问题！
    因为没有扩容，不需要挪动数据，位置没有改变，迭代器还是指向那个节点。

  • 但是earse有迭代器失效的问题！
    因为节点释放了，迭代器却依旧指向那个位置。
    STL为erase增添了返回值，我们用完erase后要接收它的返回值，它返回的是删除的节点的下一个节点。

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

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

相关文章

SQOOP安装与使用

SQOOP安装与使用

SQOOP安装及使用 文章目录 SQOOP安装及使用SQOOP安装1、上传并解压2、修改配置文件3、修改环境变量4、添加MySQL连接驱动5、测试 准备MySQL数据登录MySQL数据库创建student数据库切换数据库并导入数据另外一种导入数据的方式使用Navicat运行SQL文件导出MySQL数据库 importMySQL…
阅读更多...
HarmonyOS应用开发-环境搭建（windows环境）

HarmonyOS应用开发-环境搭建（windows环境）

官网地址&#xff1a;链接 DevEco Studio 3.1.1 Release&#xff1a;下载地址 1、安装DevEco Studio 直接安装即可 2、配置开发环境 1.运行已安装的DevEco Studio&#xff0c;首次使用&#xff0c;请选择Do not import settings&#xff0c;单击OK。 2.安装Node.js与ohpm。注…
阅读更多...
【MySQL】索引优化与关联查询优化

【MySQL】索引优化与关联查询优化

数据库调优的几个维度&#xff1a; 索引失效&#xff0c;没有充分用到索引——索引建立关联查询太多JOIN——SQL优化服务器调优以及各个参数设置——调整my.cnf数据过多——分库分表 SQL查询优化的几种方式&#xff1a; 物理查询优化&#xff1a;通过索引以及表连接方式进行…
阅读更多...
微服务分布式中为什么要分库分表呢？

微服务分布式中为什么要分库分表呢？

什么是分库分表&#xff1f; 概念&#xff1a; 分库分表是一种数据库水平扩展的方法&#xff0c;通过将数据分散存储在多个数据库实例或多张表中&#xff0c;以提高系统的性能和扩展性。在Java应用中&#xff0c;可以使用一些数据库中间件或框架来实现分库分表。 为什么要分…
阅读更多...
2024-3-6-数据库作业

2024-3-6-数据库作业

作业&#xff1a;数据库操作的增、删、改完成 源代码&#xff1a; #include <myhead.h> void do_add(sqlite3 *ppDb) {char *errmsg NULL;char sql[128] "insert into Worker values(1001,小张,15000);";// "insert into Worker values(1002,小刘,900…
阅读更多...
实验一 将调试集成到vscode

实验一 将调试集成到vscode

先唤起终端&#xff0c;按照上一篇文章的步骤分别启动调试服务器和调试客户端&#xff0c;然后挂在后台 PS&#xff1a;同时挂两个终端可以开两个窗口&#xff0c;也可以使用多窗口分屏式终端terminator 注意是要图二的光标一直闪&#xff0c;如果熄灭了说明连接超时了&#xf…
阅读更多...
Linux中systemv共享内存

Linux中systemv共享内存

目录 1.原理 2.接口 1.shmget(share_memory_get获得共享内存) 2.ftok 3.shmat(share_memory_attaintion挂接到物理内存上) 4.key和shmid的区别 5.ipc 指令 6.shmdt函数&#xff08;share_memory_detach取消挂接&#xff09; 7.shmctl函数&#xff08;share_memory_cont…
阅读更多...
【你也能从零基础学会网站开发】Web建站之HTML+CSS入门篇 网站开发的基本概念与站点文件的管理

【你也能从零基础学会网站开发】Web建站之HTML+CSS入门篇 网站开发的基本概念与站点文件的管理

&#x1f680; 个人主页 极客小俊 ✍&#x1f3fb; 作者简介&#xff1a;web开发者、设计师、技术分享 &#x1f40b; 希望大家多多支持, 我们一起学习和进步&#xff01;&#x1f604; &#x1f3c5; 如果对你有帮助的话&#xff0c;欢迎评论 &#x1f4ac;点赞&#x1f44d;&…
阅读更多...
笔记本上使用usb蓝牙适配器

笔记本上使用usb蓝牙适配器

注意 必须先禁用笔记本上原来的蓝牙功能 禁用笔记本原来的蓝牙功能 使用usb蓝牙适配器
阅读更多...
matlab读取hdf5格式的全球火灾排放数据库Global Fire Emissions Database（GFED）数据

matlab读取hdf5格式的全球火灾排放数据库Global Fire Emissions Database（GFED）数据

1.引言 火灾是大气中痕量气体和气溶胶的重要来源&#xff0c;并且是全球尺度上最重要的干扰因素。此外&#xff0c;森林砍伐和热带泥炭地火灾以及火灾频率增加的地区&#xff0c;都会增加大气中二氧化碳的积累。烧毁面积提供了生物质燃烧事件期间受火灾影响土地的估算&#xff…
阅读更多...
实时智能应答数字人搭建

实时智能应答数字人搭建

语音驱动口型的算法 先看效果&#xff1a; 你很快就可以帮得上我了 FACEGOOD 决定将语音驱动口型的算法技术正式开源&#xff0c;这是 AI 虚拟数字人的核心算法&#xff0c;技术开源后将大程度降低 AI 数字人的开发门槛。FACEGOOD是一家国际领先的3D基础软件开发商&#xff0c;…
阅读更多...
分类算法(Classification algorithms)

分类算法(Classification algorithms)

逻辑回归(logical regression&#xff09;&#xff1a; 逻辑回归这个名字听上去好像应该是回归算法的&#xff0c;但其实这个名字只是在历史上取名有点区别&#xff0c;但实际上它是一个完全属于是分类算法的。 我们为什么要学习它呢&#xff1f;在用我们的线性回归时会遇到一…
阅读更多...
Xss-labs-master 1-16关

Xss-labs-master 1-16关

第一关 <?php ini_set("display_errors", 0); $str $_GET["name"]; echo "<h2 aligncenter>欢迎用户".$str."</h2>"; ?> <center><img srclevel1.png></center> <?php echo "&l…
阅读更多...
OpenAI-Sora学习手册

OpenAI-Sora学习手册

通过Sora看2024红利&#xff1a;文生视频&#xff0c;虽然AI不一定是风口&#xff0c;但一定是未来深入到生活工作&#xff0c;乃至思考的必备工具。 目录 Sora介绍 Sora基础介绍 Sora官方网址 Sora的价值 1.物理世界的交互 2.创意世界的绽放 3.多角色、更精准、更细节…
阅读更多...
两天学会微服务网关Gateway-Gateway网关限流

两天学会微服务网关Gateway-Gateway网关限流

锋哥原创的微服务网关Gateway视频教程&#xff1a; Gateway微服务网关视频教程&#xff08;无废话版&#xff09;_哔哩哔哩_bilibiliGateway微服务网关视频教程&#xff08;无废话版&#xff09;共计17条视频&#xff0c;包括&#xff1a;1_Gateway简介、2_Gateway工作原理、3…
阅读更多...
shell脚本一键部署docker

shell脚本一键部署docker

Docker介绍 Docker 是一个开源的平台&#xff0c;用于开发、交付和运行应用程序。它利用容器化技术&#xff0c;可以帮助开发人员更轻松地打包应用程序及其依赖项&#xff0c;并将其部署到任何环境中&#xff0c;无论是开发工作站、数据中心还是云中。以下是 Docker 的一些关键…
阅读更多...
ChatGPT提问技巧——控制温度和TOP-P样本

ChatGPT提问技巧——控制温度和TOP-P样本

ChatGPT提问技巧——控制温度和TOP-P样本 “控制温度和Top-P抽样”在自然语言处理中&#xff0c;控制温度是指通过调整生成文本的随机性和多样性&#xff0c;而Top-P抽样是一种生成文本的策略&#xff0c;它选择概率最高的前P个词作为候选词汇。这两个技术常用于生成文本的质量…
阅读更多...
ChatGPT在地学、GIS、气象、农业、生态、环境等领域中的应用

ChatGPT在地学、GIS、气象、农业、生态、环境等领域中的应用

以ChatGPT、LLaMA、Gemini、DALLE、Midjourney、Stable Diffusion、星火大模型、文心一言、千问为代表AI大语言模型带来了新一波人工智能浪潮&#xff0c;可以面向科研选题、思维导图、数据清洗、统计分析、高级编程、代码调试、算法学习、论文检索、写作、翻译、润色、文献辅助…
阅读更多...
DataFunSummit 2023：洞察现代数据栈技术的创新与发展（附大会核心PPT下载）

DataFunSummit 2023：洞察现代数据栈技术的创新与发展（附大会核心PPT下载）

随着数字化浪潮的推进&#xff0c;数据已成为企业竞争的核心要素。为了应对日益增长的数据挑战&#xff0c;现代数据栈技术日益受到业界的关注。DataFunSummit 2023年现代数据栈技术峰会正是在这样的背景下应运而生&#xff0c;汇聚了全球数据领域的精英&#xff0c;共同探讨现…
阅读更多...
Android应用开发data android:schemes标签的作用

Android应用开发data android:schemes标签的作用

文章目录 data android:schemesAndroidManifest.xml 中 <data> 元素的属性详解 data android:schemes 在 AndroidManifest.xml 文件中&#xff0c; 标签的作用是指定该应用可以处理的 URI 方案。 URI 是统一资源标识符&#xff0c;它是一种用于标识资源的标准方法。URI…
阅读更多...
最新文章

Copyright @ 2022~2023