【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

文章目录

  • 1.模拟实现list
    • 1.1构造函数
    • 1.2迭代器类的实现
    • 1.3运算符重载
    • 1.4增删查改

1.模拟实现list

list使用文章

在这里插入图片描述

1.1构造函数

在这里插入图片描述

析构函数

在这里插入图片描述

  在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node，用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。

namespace my_list
{	//用类模板定义一个list结点template<class T>struct _list_node{//list结点的构造函数，T()作为缺省值，当未转参时调用_list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}//list_node的成员函数，list为带头双向循环链表_list_node* _prev;_list_node* _next;T _val;};//用类模拟实现listtemplate<class T>class list{private:typedef _list_node<T> Node;public://list的构造函数，初始化头节点指针list(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}//析构函数~list(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;delete _head;_head = nullptr;}private://成员函数为list的头节点指针,和链表长度Node* _head;size_t _size;};
}

 

1.2迭代器类的实现

在这里插入图片描述
在这里插入图片描述
 

  因为list的底层实现和之前的vector和string不同，vector和string是数组和顺序表，而list底层是链表。而对于数组和顺序表，我们可以直接使用指针来实现其迭代器，但是对于list类型就无法使用指针来实现它的迭代器，因为迭代器++无法访问到他的下一个节点。所以我们这里建立一个迭代器的结构体，用来封装node指针，来实现list的专属迭代器

  这段代码定义了一个名为__list_iterator的迭代器结构体，用于遍历链表。该结构体模板有三个模板参数：T表示链表中节点的数据类型，Ref表示引用类型T&，Ptr表示指针类型 T* _node：指向链表节点的指针。构造函数__list_iterator(Node* node)：用于初始化迭代器对象，将指针node赋值给_node。通过_node就可以实现各种操作符重载。

  定义了一个迭代器结构体，用于在链表中进行遍历和操作。通过重载运算符，可以使用迭代器对象像指针一样访问链表中的元素。

//使用类进行封装Node*，来实现list的专属迭代器
//list迭代器和一些内置类型迭代器不一样，++无法准确访问到下一个位置
//typedef __list_iterator<T, T&> iterator;
//typedef __list_iterator<T, const T&> 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){__list_iterator<T> 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;}
};

  通过建立一个新的结构体来重载迭代器，我们即可实现list专属迭代器对其链表进行++、- -等操作。

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;//list迭代器实现
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);
}

 

1.3运算符重载

  迭代器的运算符重载在上面的代码中，已经都基本实现了。

在这里插入图片描述

  赋值运算符重载函数operator=首先创建了一个临时的链表对象lt，并将传入的链表对象的副本赋值给lt。然后，调用swap函数，将当前链表对象和临时链表对象进行交换。这样做的原因是为了实现异常安全的赋值操作。通过将传入的链表对象的副本赋值给临时链表对象，可以确保在交换过程中不会影响到传入的链表对象。 最后，返回当前链表对象的引用。

  通过这样的实现逻辑，可以实现链表对象之间的赋值操作，并且保证在异常发生时不会破坏数据的完整性。

//交换
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;
}

 

1.4增删查改

push_back

在这里插入图片描述
  和带头双向循环链表的尾插一样。首先，创建一个新的链表节点newnode，节点的值为传入的参数x。然后，获取到链表的尾指针tail，即头节点的前一个节点。

  接着，将新节点newnode插入到链表的尾部。首先，将新节点的前驱指针指向尾节点tail，将尾节点的后继指针指向新节点。这样就将新节点连接到了链表的尾部。

  然后，将新节点的后继指针指向头节点，将头节点的前驱指针指向新节点。这样就将新节点连接到了链表的头部。

//尾插
void push_back(const T& x)
{//创建一个新的链表结点，且获取到链表的尾指针Node* newnode = new Node(x);Node* tail = _head->_prev;//连接尾结点newnode->_prev = tail;tail->_next = newnode;//连接头节点_head->_prev = newnode;newnode->_next = _head;++_size;
}

 

insert

在这里插入图片描述

  和上面的逻辑类似。

//在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;
}

 

erase

在这里插入图片描述
  首先，通过断言判断传入的迭代器pos不等于链表的末尾迭代器。如果等于末尾迭代器，表示要删除的节点不存在，会导致错误。然后，根据传入的迭代器pos获取到要删除的节点cur，以及其前驱节点prev和后继节点next。

  接着，将前驱节点的后继指针指向后继节点，将后继节点的前驱指针指向前驱节点。这样就将要删除的节点从链表中断开。然后，释放要删除的节点的内存。还要将链表的大小减1。

  为了避免迭代器失效，返回下一个节点的指针作为新的迭代器。这样可以保证在删除节点后，仍然可以使用返回的迭代器进行遍历和操作。

//删除
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;
}

 
完整实现

#pragma once#include<assert.h>namespace my_list
{	//用类模板定义一个list结点template<class T>struct _list_node{//list结点的构造函数，T()作为缺省值，当未转参时调用_list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}//list_node的成员函数，list为带头双向循环链表_list_node* _prev;_list_node* _next;T _val;};//使用类进行封装Node*，来实现list的专属迭代器//list迭代器和一些内置类型迭代器不一样，++无法准确访问到下一个位置//typedef __list_iterator<T, T&> iterator;//typedef __list_iterator<T, const T&> 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){__list_iterator<T> 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;}};//实现const类型迭代器/*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;}};*///用类模拟实现listtemplate<class T>class list{private:typedef _list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//list迭代器实现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的构造函数，初始化头节点指针list(){empty_init();}//拷贝构造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){//创建一个新的链表结点，且获取到链表的尾指针Node* newnode = new Node(x);Node* tail = _head->_prev;//连接尾结点newnode->_prev = tail;tail->_next = newnode;//连接头节点_head->_prev = newnode;newnode->_next = _head;++_size;//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;}//返回sizesize_t size(){/*size_t sz = 0;iterator it = begin();while (it != end()){++sz;++it;}return sz;*/return _size;}private://成员函数为list的头节点指针,和链表长度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;}
}

 
测试代码

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<list>
using namespace std;#include"list.h"void test_list1()
{//list<int> lt;//lt.push_back(1);//lt.push_back(2);//lt.push_back(3);//lt.push_back(4);//for (auto e : lt)//{//	cout << e << " ";//}//cout << endl;my_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);my_list::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;auto itt = lt.begin();while (itt != lt.end()){++(*itt);++itt;}for (auto e: lt){cout << e << " ";}cout << endl;
}struct A
{A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list2()
{my_list::list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));auto it = lt.begin();while (it != lt.end()){//cout << *(it)._a1 << " " << *(it)._a2 <<endl;cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;
}void test_list3()
{my_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_front(5);lt.push_front(6);print(lt);lt.pop_front();lt.pop_back();print(lt);lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);print(lt);cout << lt.size() << endl;}int main()
{//test_list1();//test_list2();test_list3();return 0;
}

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

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

相关文章

git之reflog分析

git之reflog分析

写在前面 本文一起看下reflog命令。 1&#xff1a;场景描述 在开发的过程中&#xff0c;因为修改错误&#xff0c;想要通过git reset命令恢复到之前的某个版本&#xff0c;但是选择提交ID错误&#xff0c;导致多恢复了一个版本&#xff0c;假定&#xff0c;该版本对应的内容…
阅读更多...
Springboot部署ELK实战

Springboot部署ELK实战

Springboot部署ELK实战 1、部署docker、docker-compose环境安装docker安装docker-compose 2、搭建elk1、构建目录&&配置文件1、docker-compose.yml 文档2、Kibana.yml3、log-config.conf 2、添加es分词器插件3、启动 3、Springboot项目引入es、logStash配置1、引入依赖…
阅读更多...
【新人指南】给新人软件开发工程师的干货建议

【新人指南】给新人软件开发工程师的干货建议

在我是新人时&#xff0c;如果有前辈能够指导方向一下&#xff0c;分享一些踩坑经历&#xff0c;或许会让我少走很多弯路&#xff0c;节省更多的学习的成本。 这篇文章根据我多年的工作经验&#xff0c;给新人总结了一些建议&#xff0c;希望对你会有所帮助。 写好注释 没有注…
阅读更多...
解决Map修改key的问题

解决Map修改key的问题

需求 现在返回json数据带有分页的数据&#xff0c;将返回data属性数据变更为content&#xff0c;数据不变&#xff0c;key发生变化 实现1&#xff0c;源数据比较复杂&#xff0c;组装数据比较麻烦 说明&#xff1a;如果使用这种方式完成需求&#xff0c;需要创建对象&#xff0…
阅读更多...
C++ 多态 虚函数表

C++ 多态 虚函数表

文章目录 简易抽象理解多态多态的具体实现虚函数的定义虚函数的重写重定义&#xff08;隐藏&#xff09;、重载 、重写&#xff08;覆盖&#xff09;区别C11 override 和 final 关键字抽象类的定义接口继承和实现继承多态的原理&#xff1a;虚函数表单继承和多继承关系的虚函数…
阅读更多...
Flask项目打包为exe（附带项目资源，静态文件）

Flask项目打包为exe（附带项目资源，静态文件）

1.在项目根目录创建my_app.spec文件&#xff0c;内容如下&#xff1a; # -*- mode: python ; coding: utf-8 -*-block_cipher Nonea Analysis([server.py], # flask入口pathex[],binaries[], datas[("E:/**/templates","/templates"),("E:/**/s…
阅读更多...
物联网工程开发实施，应该怎么做？

物联网工程开发实施，应该怎么做？

我这里刚好有嵌入式、单片机、plc的资料需要可以私我或在评论区扣个6 物联网工程的概念 物联网工程是研究物联网系统的规划、设计、实施、管理与维护的工程科学&#xff0c;要求物联网工程技术人员根 据既定的目标&#xff0c;依照国家、行业或企业规范&#xff0c;制定物联网…
阅读更多...
Visual ChatGPT：Microsoft ChatGPT 和 VFM 相结合

Visual ChatGPT：Microsoft ChatGPT 和 VFM 相结合

推荐&#xff1a;使用 NSDT场景编辑器助你快速搭建可二次编辑的3D应用场景 什么是Visual ChatGPT&#xff1f; Visual ChatGPT 是一个包含 Visual Foundation 模型 &#xff08;VFM&#xff09; 的系统&#xff0c;可帮助 ChatGPT 更好地理解、生成和编辑视觉信息。VFM 能够指…
阅读更多...
Java抽象类和接口【超详细】

Java抽象类和接口【超详细】

文章目录 一、抽象类1.1 抽象类概念1.2 抽象类语法1.3 抽象类特性1.4 抽象类的作用 二、接口2.1 接口的概念2.2 语法规则2.3 接口使用2.4 接口特性2.5 实现多个接口2.6 接口间的继承2.7 接口使用实例2.8Clonable 接口和深拷贝2.9 抽象类和接口的区别 一、抽象类 1.1 抽象类概念…
阅读更多...
MySQL索引1——索引基本概念与索引结构（B树、R树、Hash等）

MySQL索引1——索引基本概念与索引结构（B树、R树、Hash等）

目录 索引(INDEX)基本概念 索引结构分类 BTree树索引结构 Hash索引结构 Full-Text索引 R-Tree索引 索引(INDEX)基本概念 什么是索引 索引是帮助MySQL高效获取数据的有序数据结构 为数据库表中的某些列创建索引&#xff0c;就是对数据库表中某些列的值通过不同的数据结…
阅读更多...
Flask简介与基础入门

Flask简介与基础入门

一、了解框架 Flask作为Web框架&#xff0c;它的作用主要是为了开发Web应用程序。那么我们首先来了解下Web应用程序。Web应用程序 (World Wide Web)诞生最初的目的&#xff0c;是为了利用互联网交流工作文档。 1、一切从客户端发起请求开始。 所有Flask程序都必须创建一个程序…
阅读更多...
WSL 2 installation is incomplete的解决方案

WSL 2 installation is incomplete的解决方案

问题描述 解决方案 在Windows功能中开启Hyper-v 如果没有Hyper-v选项&#xff0c;新建文本粘贴以下内容后以.cmd为后缀保存后执行即可 pushd "%~dp0" dir /b %SystemRoot%\servicing\Packages\*Hyper-V*.mum >hyper-v.txt for /f %%i in (findstr /i . hyper-v.t…
阅读更多...
Julia 字典和集合

Julia 字典和集合

数组是一种集合&#xff0c;此外 Julia 也有其他类型的集合&#xff0c;比如字典和 set&#xff08;无序集合列表&#xff09;。 字典 字典是一种可变容器模型&#xff0c;且可存储任意类型对象。 字典的每个键值 key>value 对用 > 分割&#xff0c;每个键值对之间用逗…
阅读更多...
OSLog与NSLog对比

OSLog与NSLog对比

NSLog: NSLog的文档&#xff0c;第一句话就说&#xff1a;Logs an error message to the Apple System Log facility.&#xff0c;所以首先&#xff0c;NSLog就不是设计作为普通的debug log的&#xff0c;而是error log&#xff1b;其次&#xff0c;NSLog也并非是printf的简单…
阅读更多...
前端学习---vue2--选项/数据--data-computed-watch-methods-props

前端学习---vue2--选项/数据--data-computed-watch-methods-props

写在前面&#xff1a; vue提供了很多数据相关的。 文章目录 data 动态绑定介绍使用使用数据 computed 计算属性介绍基础使用计算属性缓存 vs 方法完整使用 watch 监听属性介绍使用 methodspropspropsData data 动态绑定 介绍 简单的说就是进行双向绑定的区域。 vue实例的数…
阅读更多...
Java课题笔记~ IoC 控制反转

Java课题笔记~ IoC 控制反转

二、IoC 控制反转 控制反转&#xff08;IoC&#xff0c;Inversion of Control&#xff09;&#xff0c;是一个概念&#xff0c;是一种思想。指将传统上由程序代码直接操控的对象调用权交给容器&#xff0c;通过容器来实现对象的 装配和管理。控制反转就是对对象控制权的转移&a…
阅读更多...
为react项目添加开发/提交规范（前端工程化、eslint、prettier、husky、commitlint、stylelint）

为react项目添加开发/提交规范（前端工程化、eslint、prettier、husky、commitlint、stylelint）

因历史遗留原因&#xff0c;接手的项目没有代码提醒/格式化&#xff0c;包括 eslint、pretttier&#xff0c;也没有 commit 提交校验&#xff0c;如 husky、commitlint、stylelint&#xff0c;与其期待自己或者同事的代码写得完美无缺&#xff0c;不如通过一些工具来进行规范和…
阅读更多...
FFmpeg中硬解码后深度学习模型的图像处理dnn_processing(一)

FFmpeg中硬解码后深度学习模型的图像处理dnn_processing(一)

ffmpeg 硬件解码 ffmpeg硬件解码可以使用最新的vulkan来做&#xff0c;基本上来说&#xff0c;不挑操作系统是比较重要的&#xff0c;如果直接使用cuda也是非常好的选择。 AVPixelFormat sourcepf AV_PIX_FMT_NV12;// AV_PIX_FMT_NV12;// AV_PIX_FMT_YUV420P;AVPixelFormat d…
阅读更多...
SpringBoot+SSM实战＜一＞：打造高效便捷的企业级Java外卖订购系统

SpringBoot+SSM实战＜一＞：打造高效便捷的企业级Java外卖订购系统

文章目录 项目简介项目架构功能模块管理端用户端 技术选型用户层网关层应用层数据层工具 项目优缺点结语 黑马程序员最新Java项目实战《苍穹外卖》&#xff1a;让你轻松掌握SpringBootSSM的企业级开发技巧项目简介 《苍穹外卖》是一款为餐饮企业&#xff08;餐厅、饭店&#x…
阅读更多...
zookeeper --- 基础篇

zookeeper --- 基础篇

一、zookeeper简介 1.1、什么是zookeeper zookeeper官网&#xff1a;https://zookeeper.apache.org/ 大数据生态系统里的很多组件的命名都是某种动物或者昆虫&#xff0c;他是用来管 Hadoop&#xff08;大象&#xff09;、Hive(蜜蜂)、Pig(小 猪)的管理员。顾名思义就是管理…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023