C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍
文章目录
- 前言
- 一、list
- 二、list类的初始化和尾插
- 三、list的迭代器的基本实现
- 四、list的完整实现
- 五、测试
- 六、整个list类
- 总结
前言
C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍
一、list
list本质上是一个双向带头循环链表。
实现list类,需要节点类(clase list_node)、迭代器(class __list_iterator);
节点类(clase list_node): 定义每个节点的结构;
迭代器(class __list_iterator): 使用节点的指针封装出一个类,可以使用运算符重载的形式更好的访问链表;
二、list类的初始化和尾插
namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 链表template<class T> class list{typedef list_node<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* newNode = new Node(x);Node* tail = _head->_prev;newNode->_next = _head;newNode->_prev = tail;tail->_next = newNode;_head->_prev = newNode;}private:Node* _head;};
}
三、list的迭代器的基本实现
- 使用链表节点的指针封装出一个类,是list链表的访问可以向vector一样使用++等操作访问
- vector和list的使用,虽然在形式上一样,但是他们的底层是不一样的
- (*)vector迭代器是对指针的解引用
- (*)list迭代器是调用operator(解引用操作符)函数重载,本质是不一样的
对于const迭代器,是operator(*)和 operator(->)的运算符重载函数的返回值不一样,因此需要增加两个模板参数
- 即: (T& 和 T*)
// 迭代器
template <class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;
public:__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;}Node* _node;
};
- operator->运算符重载编译器会进行优化, 如下:
struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};
void test_list02()
{hhb::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));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}
四、list的完整实现
- list需要有size()的接口,所以需要对链表节点个数进行计数,增加一个成员变量_size.
- 实现insert()和erase()接口后,push_back()和push_front()、pop_back()和pop_front()接口都可以复用接口。
- clear()只清除(不包含哨兵位的头节点)数据,不销毁链表
- 析构函数调用clear()后,释放_head节点(哨兵位的头节点)
- 拷贝构造函数在拷贝之前,一定要先自己初始化(创建哨兵位的头节点)
- 赋值(=)运算符重载使用现代写法,拷贝构造加交换函数加自动调用析构函数。
// 链表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;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();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){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_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;cur = nullptr;--_size;return next;}//size_t size()//{// int sz = 0;// iterator it = begin();// while (it != end())// {// sz++;// ++it;// }// // return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}
五、测试
- 测试push_back, pop_back可以顺便测试insert, erase函数, 所以不单独测试insert和erase函数
void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}
- 测试拷贝构造和赋值运算符重载
void test_list04()
{hhb::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;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}
六、整个list类
// list.h
#pragma once#include <assert.h>
namespace hhb
{// 节点template <class T>struct list_node{list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _val(val){}list_node<T>* _next;list_node<T>* _prev;T _val;};// 迭代器template <class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;public:__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;}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;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void emptyInit(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>& lt){emptyInit();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){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}void push_back(const T& x){//Node* newNode = new Node(x);//Node* tail = _head->_prev;//newNode->_next = _head;//newNode->_prev = tail;//tail->_next = newNode;//_head->_prev = newNode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pos_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;++_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;cur = nullptr;--_size;return next;}//size_t size()//{// int sz = 0;// iterator it = begin();// while (it != end())// {// sz++;// ++it;// }// // return sz;//}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}private:Node* _head;size_t _size;};
}
- 整个测试
#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <list>
using namespace std;
#include "list.h"void print1(const hhb::list<int>& lt)
{hhb::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}void test_list01()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);hhb::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;print1(lt);
}struct A
{
public:A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list02()
{hhb::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));lt.push_back(A(5, 5));hhb::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " " << endl;cout << it->_a1 << " " << it->_a2 << " " << endl;// 此处编译器进行了优化, it->返回的是T* 也就是 A*, 如果要访问A的成员// 按道理来讲,应该是 (it->)->_a1 / (it->)->_a2 来进行访问++it;}cout << endl;}void test_list03()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pos_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);lt.push_back(50);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;}void test_list04()
{hhb::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;hhb::list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;hhb::list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}int main()
{//test_list01();test_list02();//test_list03();//test_list04();return 0;
}
总结
C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍
相关文章:

C++模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍
文章目录 前言一、list二、list类的初始化和尾插三、list的迭代器的基本实现四、list的完整实现五、测试六、整个list类总结 前言 C模拟实现list:list、list类的初始化和尾插、list的迭代器的基本实现、list的完整实现、测试、整个list类等的介绍 一、list list本…...
Offer60:n个骰子的点数
题目:把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。 分析:要解决这个问题,我们需要先统计出每个点数出现的次数,然后把每个点数出现的次数除以,就能求出每个点数出现的概率了。我们…...
几种常见的索引类型扫描
第一种:index unique scan 索引唯一扫描,当可以优化器发现某个查询条件可以利用到主键、唯一键、具有外键约束的列,或者只是访问其中某行索引所在的数据的时候,优化器会选择这种扫描类型。第二种:index range scan 索…...

苹果CMS插件:优化蜘蛛访问内容,提升百度收录率
确保蜘蛛抓取原始内容 专为苹果CMS设计的广告管理插件,能够智能识别搜索引擎蜘蛛与普通访客,确保蜘蛛访问时展示原始内容,从而提升被百度等搜索引擎收录的几率。 广告显示提升收益 对于普通访客,该插件则优先显示广告内容&#…...
后端开发刷题 | 没有重复项数字的全排列
描述 给出一组数字,返回该组数字的所有排列 例如: [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. (以数字在数组中的位置靠前为优先级,按字典序排列输出。) 数据范围:数字…...
Python中的“打开与关闭文件”:从入门到精通
引言 在日常生活中,我们经常会遇到需要读取或保存信息的情况,比如记录笔记、保存配置信息或者处理大量的数据文件等。对于程序员来说,如何高效、安全地管理这些信息显得尤为重要。Python中的文件操作功能强大且易于使用,可以帮助…...

9.23 My_string.cpp
my_string.h #ifndef MY_STRING_H #define MY_STRING_H#include <iostream> #include <cstring>using namespace std;class My_string { private:char *ptr; //指向字符数组的指针int size; //字符串的最大容量int len; //字符串当前…...

【android10】【binder】【3.向servicemanager注册服务】
系列文章目录 可跳转到下面链接查看下表所有内容https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501文章浏览阅读2次。系列文章大全https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501 目录 …...

Java — LeetCode 面试经典150题(一)
双指针 125.验证回文串 题目 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s,如果它是 回文串 ,返回…...

Python酷玩之旅_mysql-connector
前言 Python作为数据科学、机器学习等领域的必选武器,备受各界人士的喜爱。当你面对不同类型、存储于各类介质的数据时,第一时间是不是要让它亮个相?做个统计,画个图表,搞个报表… 等等。 正如Java中的JdbcDriver一样…...

7.搭建个人金融数据库之快速获取股票列表和基本信息!
前边我们提过,免费的数据一般来自于爬虫,获取难度和维护成本都比较高,其实不太适合小白用户。所以非必要情况下,我们尽量不用这种方式来获取数据。 我自己用的比较多的是tushare,一般来说有它也就够了,大…...

Nginx基础详解1(单体部署与集群部署、负载均衡、正反代理、nginx安装)
本阶段的任务 1.学会集群的操作概念 2.完成对Nginx的入门操作 3.使用Nginx实现集群和负载均衡 4.使用Nginx实现高可用的方案 目录 1.单体部署与集群部署 1.1单体部署的概念 1.2单体部署的优缺点 1.3集群部署的概念 1.4集群部署的优缺点 1.5集群部署需要注意的点 1.…...
等保一体机如何帮你应对网络攻击
等保一体机如何帮你应对网络攻击 在当今信息化时代,网络安全已成为企业和组织面临的重要挑战。随着网络攻击手段的不断升级,传统的安全防护措施已难以应对复杂多变的威胁。等保一体机作为一种集成化的安全防护解决方案,能够有效帮助企业应对…...

CVE-2024-1112 Resource Hacker 缓冲区溢出分析
漏洞简述 CVE-2024-1112 是 Resource Hacker 软件的一个缓冲区溢出漏洞。该漏洞存在于版本 3.6.0.92 中。由于软件在处理命令行中的文件路径时未对文件字符串长度进行限制,过长的字符串参数导致内存被过度写入,从而引发缓冲区溢出。 漏洞复现 构造长度…...
WebGL渲染与创建2D内容
目录 创建画布2D渲染修改顶点着色器光照深度测试混合模式WebGL是一个强大的工具,可以用来在Web浏览器中创建复杂的3D图形。虽然它的设计初衷是为了3D渲染,但也可以用于创建2D内容。通过巧妙地利用几何、投影和纹理,我们可以构建出各种2D图形。 创建画布 首先,我们需要在H…...

ArcGIS Desktop使用入门(三)图层右键工具——拓扑(下篇:地理数据库拓扑)
系列文章目录 ArcGIS Desktop使用入门(一)软件初认识 ArcGIS Desktop使用入门(二)常用工具条——标准工具 ArcGIS Desktop使用入门(二)常用工具条——编辑器 ArcGIS Desktop使用入门(二&#x…...

LeetCode题练习与总结:二叉树的最近公共祖先--236
一、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也…...
uni-app 多环境配置
前后端分离模式下,不同的环境如开发环境(dev)、测试环境(test)、生产环境(prod)等,不同环境后端数据库、api地址等可能都不同 。 uni-app中只有development和production两个环境 以配…...

【d48】【Java】【力扣】LCR 123. 图书整理 I
思路 方法1:放进list,将list倒置,利用stream,将list改为int类型 方法2:递归:递归通用思路;明确每一层做什么确定返回值确定什么地方接收下层的返回值 每一层:调用下层,然后把自己…...
【MySQL】InnoDB 索引为什么使用B+树而不用跳表?
在MySQL中,为了加速查询,使用B树来构建索引,将查询性能从O(n)优化到O(log n)。虽然跳表同样提供O(log n)的查询效率并且实现相对简单,但B树更适合MySQL的索引使用,原因包括: B树和跳表的区别 B树和跳表的…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...