STL库 —— list 的编写

目录

一、成员变量

​编辑

二、push_back 函数

三、迭代器 iterator

3.1 iterator 结构体

3.2 begin() 与 end() 函数

3.3 iterator 运算符重载

3.4 -> 的重载

3.5 const_iterator

四、测试代码

五、修饰符成员

5.1 insert 函数

5.2 erase 函数

5.3 push 函数

5.4 pop 函数

六、容量成员

6.1 size 函数

6.2 empty 函数

七、模板优化iterator

一、成员变量

	template<class T>
	struct ListNode
	{
		T _data;
		ListNode<T>* _prev;
		ListNode<T>* _next;
		ListNode(const T& x = T())
			:_data(x)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	template<class T>
	class my_list
	{
		typedef ListNode<T> Node;
	private:
		Node* _head;//哨兵位头结点
	};

		my_list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

二、push_back 函数

为了测试方便，我们在这里先把 push_back 写出来。

		void push_back(T data)
		{
			Node* NewNode = new Node(data);

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

三、迭代器 iterator

3.1 iterator 结构体

这里的迭代器和之前的迭代器有所不同，诸如 string 、 vector ，他们的内存空间是连续的，迭代器的底层都是基于指针的，而 list 中，由于存储单元的随机性，迭代器不可以再是单纯的指针，而是像上面那样的结构体对象：

    template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
        typedef ListIterator<T> iterator;
		
        Node* _node;
		ListIterator(Node* node)//构造函数
		{
			_node = node;
		}
	};

3.2 begin() 与 end() 函数

然后，需要在 my_list 类中新添 begin 和 end 函数，因为他们都是服务于迭代器，所以他们的返回值类型应该是迭代器，还要注意，根据 STL 通用设计模式， end() 指向的位置不用于存放有效数据元素，而是作为遍历结束的标记。所以 end() 函数可以直接返回通过 _head 构造的迭代器，以此表示链表的末尾。

    template<class T>
	class my_list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T> iterator;

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

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

	private:
		Node* _head;
	};

3.3 iterator 运算符重载

随后，为了使迭代器可以跑起来，需要再对 ++ 、 -- 、 != 等运算符进行重载，
其中，为了保持与内建类型行为一致，内建类型（如int、float等）的前置自增和自减操作返回的是引用。自定义类型（如迭代器）模拟内建类型的行为，包括操作符的使用，有助于保持语言的一致性和直观性。
后置自增和自减不返回其引用的原因与前置自增自减的设计意图及使用方式有关。后置自增操作符的主要特点是先返回对象当前的值（在自增之前的状态），然后再对对象进行自增操作。这一行为决定了其返回类型应该是对象的值而不是引用
顺便，我们可以把 == 和 * 运算符都重载：

		typedef ListIterator<T> iterator;
        iterator& operator++()//前置++
		{
			_node = _node->_next;
			return *this;
		 }
		iterator operator++(int)//后置++
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		iterator& operator--()//前置--
		{
			_node = _node->_prev;
			return *this;
		}
		iterator operator--(int)//后置--
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		T& operator*()
		{
			return _node->_data;
		}
		bool operator!=(const iterator& it)
		{
			return  _node != it._node;
		}
		bool operator==(const iterator& it)
		{
			return _node == it._node;
		}

3.4 -> 的重载

当我们创建一个自定义类型，如 class A(此时在Flash命名空间内)：

	class A
	{
	public:
		int a = 0;
		int b = 0;
	};

去测试 A 类型的 list 时，虽然 push_back 可以用，但是我们想遍历链表时，迭代器却不能用了：

	void test()
	{
		my_list<A> la;
		la.push_back({ 6, 12 });
		la.push_back({ 7, 18 });
		la.push_back({ 3, 22 });
		my_list<A>::iterator it = la.begin();
		while (it != la.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}


错误的原因在于，系统不支持自定义类型的流插入，这里有两种解放方案：
1.重新重载一个 << 运算符
2.改变输出的格式 cout << (*it).a << (*it).b << " ";

		while (it != la.end())
		{
			cout << (*it).a << (*it).b << " ";
			it++;
		}

 但是究其本源，迭代器模拟的还是指针，如果是指针的话，就可以通过 -> 读取指针指向空间的数据，所以这里可以重载 -> 来达到模拟指针目的。

		T* operator->()
		{
			return &_node->_data;//->的优先级更高
		}

3.5 const_iterator

为了保证迭代器的内容不被修改，我们还要为迭代器添加 const ，但是根据所学知识，仅在函数返回值前加 const 是不能满足需求的，这只能保证迭代器本身不能被修改，此时就不可能自增和自减了，所以要新建一个 const_iterator 类，来模拟实现 const T* 指针的行为。

其中只有 operator* 与 operator-> 返回值不同。

template<class T>
	struct ListConstIterator
	{
		typedef ListNode<T> Node;
		typedef ListConstIterator<T> const_iterator;

		Node* _node;

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

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

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

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

		const_iterator operator++(int)
		{
			const_iterator tmp(*this);
			_node = _node->_next;

			return tmp;
		}

		const_iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		const_iterator operator--(int)
		{
			const_iterator 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;
		}
	};

此时在 my_list 类中在添加 cbegin 和 cend 函数：

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

四、测试代码

有了之前的代码，我们就可以进行统一的测试：

    void test_push_back()
	{
		my_list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
		l1.push_back(5);
		my_list<int>::iterator it = l1.begin();
		while (it != l1.end())
		{
			cout << *it << endl;
			it++;
		}
	}

五、修饰符成员

上面的代码就可以让我们基本理清 list 的行为，有助于写下面的函数。

5.1 insert 函数

库中的 insert 支持的是迭代器访问，此时 pos 是上面的迭代器结构体， pos._node 才是此时要访问的节点。pos 位置前的节点的下一个节点是新插入的节点，pos位置是新插入节点后面的节点。

		void insert(iterator pos, T data)
		{
			Node* NewNode = new Node(data);
			Node* prev = pos._node->_prev;
			Node* cur = pos._node;
			//节点位置： prev Newnode cur
			prev->_next = NewNode;
			NewNode->_prev = prev;
			NewNode->_next = cur;
			cur->_prev = NewNode;
		}

5.2 erase 函数

erase 函数更加简单，其不需要创建新节点，仅需控制指针的指向即可。

		void erase(iterator pos)
		{
			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;
			//prev pos next
			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
		}

5.3 push 函数

有了 insert 函数， push_back 函数就可以直接复用，因为是尾插，且传入的 pos 位置是插入位置的下一个节点， end 函数指向的是哨兵位节点，所以 pos 直接取到 end 即可。

		void push_back2(T data)
		{
			insert(end(), data);
		}

同 push_back 使用 end 作为 pos 一样， begin 返回的是哨兵位的下一个节点，所以传入位置直接取到 begin 即可。

		void push_front(T data)
		{
			insert(begin(), data);
		}

5.4 pop 函数

因为没有重载运算符 - ，所以 pop_back 传值时只能使用自减操作， end 指向的是哨兵位，所以需要使用 end 前面的位置，标准库中并没有实现减操作的重载，且效率很低，所以没有必要手搓。

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

六、容量成员

6.1 size 函数

`std::list`的`size()`成员函数返回容器中元素的数目。在C++11及之后的标准中，`std::list::size()`的时间复杂度为常数时间O(1)。这是通过内部维护一个表示元素数量的计数器来实现的。
每当添加或删除元素时，这个计数器就会相应地更新。
因此，`size()`函数的实现通常看起来像这样：

        size_t size() const 
        {
            return _size;  // _size是一个成员变量，用来追踪当前链表中元素的数量
        }

这里的`_size`是容器的一个私有成员变量，其在构造函数中初始化，在向容器添加元素或从容器中移除元素时被更新。

但是要注意，在使用复用函数时，如上的 "push_front" "pop_back" 时， _size 不需要进行自增或自减操作，这样可能会自增自减两次，导致错误。

6.2 empty 函数

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

七、模板优化iterator

上面的 iterator 与 const_iterator 重复度太高，此时，就可以使用模板进行优化，让编译器根据传入的参数进行实例化：

template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> iterator;
		Node* _node;
	};

 与之前学的模板不同的是，传入的参数增加了，传入的参数变成了引用和指针：

    template<class T>
	class my_list
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
	}

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

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

相关文章

【Ubuntu】update-alternatives 命令详解

【Ubuntu】update-alternatives 命令详解

1、查看所有候选项 ​​​​​​​sudo update-alternatives --list java 2、​​​​​​​更换候选项 sudo update-alternatives --config java 3、自动选择优先级最高的作为默认项 sudo update-alternatives --auto java 4、删除候选项 sudo update-alternatives --rem…
阅读更多...
Netty 入门应用之Http服务WebSocket

Netty 入门应用之Http服务WebSocket

Netty实现Http服务 主要的变化是在初始化器中引入了新的编解码器 一些创建的类作用和Netty HelloWorld的小demo一样我这里就不再次重复了 1、Http服务端代码 public class HttpServer {public static void main(String[] args) {// 创建Reactor// 用来管理channel 监听事件 …
阅读更多...
FME学习之旅---day22

FME学习之旅---day22

我们付出一些成本&#xff0c;时间的或者其他&#xff0c;最终总能收获一些什么。 教程&#xff1a;栅格入门 FME 支持读取和写入 70 多种栅格格式。本教程将介绍几个基本示例&#xff0c;展示如何使用 FME 读取、转换和写入栅格数据。 FME 数据检查器不应用任何对比度增强。因…
阅读更多...
实战项目——智慧社区（一）

实战项目——智慧社区（一）

1、项目介绍 系统功能 登录、修改密码、登出 &#xff08;1&#xff09;首页 &#xff08;1.1&#xff09;数据统计&#xff1a;小区人员统计对比图&#xff0c;占比图 &#xff08;2&#xff09;物业管理 &#xff08;2.1&#xff09;小区管理&#xff1a;小区数据的增删改…
阅读更多...
centos 7.9 nginx本地化安装，把镜像改成阿里云

centos 7.9 nginx本地化安装，把镜像改成阿里云

1.把centos7.9系统切换到阿里云的镜像源 1.1.先备份 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup1.2.下载新的CentOS-Base.repo配置文件 wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo特别…
阅读更多...
Redux和Redux Toolkit

Redux和Redux Toolkit

Redux 概念&#xff1a;redux是react最常用的集中状态管理工具&#xff0c;类似于Vue中的Pinia(vuex)&#xff0c;可以独立于框架运行作用&#xff1a;通过集中管理的方式管理应用的状态 Redux快速体验 不和任何框架绑定&#xff0c;不使用任何构建工具&#xff0c;使用纯Re…
阅读更多...
uniapp小程序编译报错

uniapp小程序编译报错

说明 微信小程序编译每次都出现[ project.config.json 文件内容错误] project.config.json: libVersion 字段需为 string, 解决 找到manifest.json文件 添加&#xff1a;"libVersion": "latest"&#xff0c;重新编译即可。
阅读更多...
MySQL limit N offset M 速度慢？来实际体验下

MySQL limit N offset M 速度慢？来实际体验下

直接开始 有一张表&#xff1a;trade_user&#xff0c;表结构如下&#xff1a; mysql> desc trade_user; ------------------------------------------------------------------ | Field | Type | Null | Key | Default | Extra | -------------…
阅读更多...
记一次IP访问MySQL失败多次被自动锁定导致无法连接问题，解决方法只需一条SQL。

记一次IP访问MySQL失败多次被自动锁定导致无法连接问题，解决方法只需一条SQL。

&#x1f469;&#x1f3fd;‍&#x1f4bb;个人主页&#xff1a;阿木木AEcru &#x1f525; 系列专栏&#xff1a;《Docker容器化部署系列》 《Java每日面筋》 &#x1f4b9;每一次技术突破&#xff0c;都是对自我能力的挑战和超越。 前言 今天下午还在带着耳机摸鱼&#xff…
阅读更多...
Linux CentOS 安装 MySQL 服务教程

Linux CentOS 安装 MySQL 服务教程

Linux CentOS 安装 MySQL 服务教程 1. 查看系统和GNU C库(glibc)版本信息 1.1 查询机器 glibc 版本信息 glibc&#xff0c;全名GNU C Library&#xff0c;是大多数Linux发行版中使用的C库&#xff0c;为系统和应用程序提供核心的API接口。在Linux系统中&#xff0c;特别是在…
阅读更多...
动态规划-入门理解

动态规划-入门理解

一、什么情况可以使用动态规划 动态规划 最优子结构 重叠子问题 转移方程 最优子结构&#xff1a;保证能从局部解推出全局解&#xff0c;也就是保证能够写出转移方程 重叠子问题&#xff1a;说明暴力解法太耗时&#xff0c;我们可以使用动态规划进行优化 转移方程&#xff…
阅读更多...
自用---

自用---

零、环境配置 keil代码补全 keil pack包 cubemx配置安装包 一、LED cubemx配置PD2引脚为输出模式 uint16_t led_value 0x00; void led_set(uint8_t led_dis) {HAL_GPIO_WritePin(GPIOC,GPIO_PIN_All,GPIO_PIN_SET);HAL_GPIO_WritePin(GPIOC,led_dis<<8,GPIO_PIN_R…
阅读更多...
03-JAVA设计模式-桥接模式

03-JAVA设计模式-桥接模式

桥接模式 什么是桥接模式 桥接模式&#xff08;Bridge Pattern&#xff09;是一种将抽象与实现解耦的设计模式&#xff0c;使得二者可以独立变化。在桥接模式中&#xff0c;抽象部分与实现部分通过一个桥接接口进行连接&#xff0c;从而允许抽象部分和实现部分独立演化。 场…
阅读更多...
服务器docker应用一览

服务器docker应用一览

文章目录 一、简单需求二、业务流程三、运行效果四、实现过程1. 前提2. 源码3.核心代码4. 项目打包5、部署 一、简单需求 现有某云主机服务器&#xff0c;用来做项目演示用&#xff0c;上面运行了docker应用&#xff0c;现希望有一总览页面&#xff0c;用来展示部署的应用。 …
阅读更多...
微信小程序实现输入appid跳转其他小程序

微信小程序实现输入appid跳转其他小程序

前言 本文记录wx.navigateToMiniProgram打开另一个小程序API使用方法&#xff0c;并封装为组件。 wxml 部分 输入框用来记录appid&#xff0c;按钮用来查询并跳转。 <view class"container"><input class"input" placeholder"请输入要查…
阅读更多...
Linux: softirq 简介

Linux: softirq 简介

文章目录 1. 前言2. softirq 实现2.1 softirq 初始化2.1.1 注册各类 softirq 处理接口2.1.2 创建 softirq 处理线程 2.2 softirq 的 触发 和 处理2.1.1 softirq 触发2.1.2 softirq 处理2.1.2.1 在 中断上下文 处理 softirq2.1.2.2 在 ksoftirqd 内核线程上下文 处理 softirq 3.…
阅读更多...
Facial Micro-Expression Recognition Based on DeepLocal-Holistic Network 阅读笔记

Facial Micro-Expression Recognition Based on DeepLocal-Holistic Network 阅读笔记

中科院王老师团队的工作&#xff0c;用于做微表情识别。 摘要&#xff1a; Toimprove the efficiency of micro-expression feature extraction,inspired by the psychological studyof attentional resource allocation for micro-expression cognition,we propose a deep loc…
阅读更多...
HTTP与HTTPS：深度解析两种网络协议的工作原理、安全机制、性能影响与现代Web应用中的重要角色

HTTP与HTTPS：深度解析两种网络协议的工作原理、安全机制、性能影响与现代Web应用中的重要角色

HTTP (HyperText Transfer Protocol) 和 HTTPS (Hypertext Transfer Protocol Secure) 是互联网通信中不可或缺的两种协议&#xff0c;它们共同支撑了全球范围内的Web内容传输与交互。本文将深度解析HTTP与HTTPS的工作原理、安全机制、性能影响&#xff0c;并探讨它们在现代Web…
阅读更多...
[leetcode]remove-duplicates-from-sorted-list-ii

[leetcode]remove-duplicates-from-sorted-list-ii

. - 力扣&#xff08;LeetCode&#xff09; 给定一个已排序的链表的头 head &#xff0c; 删除原始链表中所有重复数字的节点&#xff0c;只留下不同的数字 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,3,4,4,5] 输出&#xff1a;[1,2,5]示例 2&…
阅读更多...
百度OCR身份证识别C++离线SDKV3.0 C#对接

百度OCR身份证识别C++离线SDKV3.0 C#对接

百度OCR身份证识别C离线SDKV3.0 C#对接 目录 说明 效果 问题 项目 代码 下载 说明 自己根据SDK封装了动态库&#xff0c;然后C#调用。 SDK 简介 本 SDK 适应于于 Windows 平台下的⾝份证识别系统,⽀持 C接⼜开发的 SDK,开发者可在VS2015 下⾯进⾏开发&#xff08;推荐…
阅读更多...
最新文章

Copyright @ 2022~2023