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){}// *itconst T& operator*(){return _node->_data;}// it->const T* operator->(){return &_node->_data;}// ++itconst_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 curprev->_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 nextprev->_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;}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

机器学习和深度学习-- 李宏毅（笔记与个人理解）Day10

机器学习和深度学习-- 李宏毅（笔记与个人理解）Day10

Day 10 Genaral GUidance training Loss 不够的case Loss on Testing data over fitting 为什么over fitting 留到下下周哦~~ 期待 solve CNN卷积神经网络 Bias-Conplexiy Trade off cross Validation how to split? N-fold Cross Validation mismatch 这节课总体听下来比较…
阅读更多...
lovesql 手工sql注入

lovesql 手工sql注入

1.页面 2.万能密码登录成功 我还傻乎乎的以为密码就是flag 但不是 3. 继续注入 判断列数 确定了只有三列 开始尝试联合注入 4.使用联合注入之前先判断显示位 5.之后一步一步的构造&#xff0c;先得到当前数据库名 利用database&#xff08;&#xff09; 再得到库里有哪些表 …
阅读更多...
Vue+el-table 修改表格 单元格横线边框颜色及表格空数据时边框颜色

Vue+el-table 修改表格 单元格横线边框颜色及表格空数据时边框颜色

需求 目前 找到对应的css样式进行修改 修改后 css样式 >>>.el-table th.el-table__cell.is-leaf {border-bottom: 1px solid #444B5F !important;}>>>.el-table td.el-table__cell,.el-table th.el-table__cell.is-leaf {border-bottom: 1px solid #444B5F …
阅读更多...
目标检测——3D车道数据集

目标检测——3D车道数据集

一、重要性及意义 3D车道检测在自动驾驶和智能交通领域具有极其重要的地位&#xff0c;其重要性和意义主要体现在以下几个方面&#xff1a; 首先&#xff0c;3D车道检测可以精确判断车辆在道路上的位置、方向和速度&#xff0c;从而预测潜在的危险情况并及时采取措施。这种能…
阅读更多...
如何在极狐GitLab 启用依赖代理功能

如何在极狐GitLab 启用依赖代理功能

本文作者&#xff1a;徐晓伟 GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署极狐GitLab。 本文主要讲述了如何在[极狐GitLab…
阅读更多...
UDP实现Mini版在线聊天室

UDP实现Mini版在线聊天室

实现原理 只有当客户端先对服务器发送online消息的时候&#xff0c;服务器才会把客户端加入到在线列表。当在线列表的用户发消息的时候&#xff0c;服务器会把消息广播给在线列表中的所有用户。而当用户输入offline时&#xff0c;表明自己要下线了&#xff0c;此时服务器把该用…
阅读更多...
【软件测试】个人博客系统测试

【软件测试】个人博客系统测试

个人博客系统测试 一、项目背景1.1 技术背景1.2 功能背景 二、自动化测试2.1 什么是自动化测试2.2 通过使用selenium进行自动化测试的编写&#xff08;Java实现&#xff09;2.3 编写测试用例&#xff0c;执行自动化测试2.3.1 输入用户名:test,密码:123&#xff0c;登录成功2.3.…
阅读更多...
云服务器上Docker启动的MySQL会自动删除数据库的问题

云服务器上Docker启动的MySQL会自动删除数据库的问题

一、问题说明 除了常见的情况&#xff0c;例如没有实现数据挂载&#xff0c;导致数据丢失外&#xff0c;还需要考虑数据库是否被攻击&#xff0c;下图 REVOVER_YOUR_DATA 就代表被勒索了&#xff0c;这种情况通常是数据库端口使用了默认端口&#xff08;3306&#xff09;且密码…
阅读更多...
jmeter实验 模拟:从CSV数据到加密请求到解密返回数据再到跨越线程组访问解密后的数据

jmeter实验 模拟:从CSV数据到加密请求到解密返回数据再到跨越线程组访问解密后的数据

注意,本实验所说的加密只是模拟加密解密,您需要届时写自己的加解密算法或者引用含有加密算法的相关jar包才行. 思路: 线程组1: 1.从CSV文件读取原始数据 2.将读取到的数据用BeanShell预习处理器进行加密 3.HTTP提取器使用加密后的数据发起请求 4.使用BeanShell后置处理器…
阅读更多...
vite+react+ts+scss 创建项目

vite+react+ts+scss 创建项目

npm create vitelatest输入项目名称选择react选择typescript swc WC 通过利用 Rust 编写的编译器&#xff0c;使用了更先进的优化技术&#xff0c;使得它在处理 TypeScript 代码时能够更快地进行转换和编译。特别是在大型项目中&#xff0c;SWC 相对于传统的 TypeScript 编译器…
阅读更多...
使用QT 开发不规则窗体

使用QT 开发不规则窗体

使用QT 开发不规则窗体 不规则窗体贴图法的不规则窗体创建UI模板创建一个父类创建业务窗体main函数直接调用user_dialog创建QSS文件 完整的QT工程 不规则窗体 QT中开发不规则窗体有两种方法&#xff1a;&#xff08;1&#xff09;第一种方法&#xff0c;使用QWidget::setMask函…
阅读更多...
跨域问题一文解决

跨域问题一文解决

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Vue ⛺️稳中求进&#xff0c;晒太阳 一、为什么会出现跨域的问题&#xff1f; 是浏览器的同源策略&#xff0c;跨域也是因为浏览器这个机制引起的&#xff0c;这个机制的存在还是在于安全…
阅读更多...
FFmpeg: 简易ijkplayer播放器实现--01项目简介

FFmpeg: 简易ijkplayer播放器实现--01项目简介

文章目录 项目介绍流程图播放器实现过程界面展示 项目介绍 此项目基于FFmeg中 ffplay.c进行二次开发&#xff0c;实现基本的功能&#xff0c;开发软件为Qt 项目优势&#xff1a; 参考ijkplayer播放器&#xff0c;实现UI界面和播放器核心进行解耦&#xff0c;容易添加其他功能…
阅读更多...
机器学习和深度学习 -- 李宏毅（笔记与个人理解1-6）

机器学习和深度学习 -- 李宏毅（笔记与个人理解1-6）

机器学习和深度学习教程 – 李宏毅&#xff08;笔记与个人理解&#xff09; day1 课程内容 什么是机器学习 找函数关键技术&#xff08;深度学习&#xff09; 函数 – 类神经网络来表示 &#xff1b;输入输出可以是 向量或者矩阵等如何找到函数&#xff1a; supervised Lear…
阅读更多...
SSRF靶场

SSRF靶场

SSRF概述 ​ 强制服务器发送一个攻击者的请求 ​ 互联网上的很多web应用提供了从其他服务器&#xff08;也可以是本地)获取数据的功能。使用用户指定的URL&#xff0c;web应用可以获取图片&#xff08;载入图片&#xff09;、文件资源&#xff08;下载或读取)。如下图所示&…
阅读更多...
C语言面试题之返回倒数第 k 个节点

C语言面试题之返回倒数第 k 个节点

返回倒数第 k 个节点 实例要求 1、实现一种算法&#xff0c;找出单向链表中倒数第 k 个节点&#xff1b;2、返回该节点的值&#xff1b; 示例&#xff1a;输入&#xff1a; 1->2->3->4->5 和 k 2 输出&#xff1a; 4 说明&#xff1a;给定的 k 保证是有效的。实…
阅读更多...
uniapp开发h5端使用video播放mp4格式视频黑屏，但有音频播放解决方案

uniapp开发h5端使用video播放mp4格式视频黑屏，但有音频播放解决方案

mp4格式视频有一些谷歌播放视频黑屏&#xff0c;搜狗浏览器可以正常播放 可能和视频的编码格式有关&#xff0c;谷歌只支持h.264编码格式的视频播放 将mp4编码格式修改为h.264即可 转换方法&#xff1a; 如果是自己手动上传文件可以手动转换 如果是后端接口调取的地址就需…
阅读更多...
效果炸裂！文生图再升级，支持多对象个性化图片生成！开源！

效果炸裂！文生图再升级，支持多对象个性化图片生成！开源！

大家好&#xff0c;今天和大家分享一篇最新的文生图工作&#xff0c;代码已开源 标题&#xff1a;Identity Decoupling for Multi-Subject Personalization of Text-to-Image Models 单位&#xff1a;KAIST 论文&#xff1a;https://arxiv.org/pdf/2404.04243.pdf 代码&#xf…
阅读更多...
【linux】yum 和 vim

【linux】yum 和 vim

yum 和 vim 1. Linux 软件包管理器 yum1.1 什么是软件包1.2 查看软件包1.3 如何安装软件1.4 如何卸载软件1.5 关于 rzsz 2. Linux编辑器-vim使用2.1 vim的基本概念2.2 vim的基本操作2.3 vim命令模式命令集2.4 vim底行模式命令集2.5 vim操作总结补充&#xff1a;vim下批量化注释…
阅读更多...
贪心算法简介

贪心算法简介

目录 一、什么是贪心算法&#xff1f; 二、贪心算法的特点 三、贪心算法解决找零问题、最短路径问题、背包问题 1.找零问题 2.最短路径问题 3.背包问题 一、什么是贪心算法&#xff1f; 贪心算法就是希望通过局部最优来解决全局最优 基本步骤&#xff1a;1.将问题分为若…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023