【C++】list类：模拟实现（适合新手的手撕list）

2024-09-07 03:20
文章标签 c++ 实现 模拟 新手 list 适合

本文主要是介绍【C++】list类：模拟实现（适合新手的手撕list），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：在开始模拟实现list前，最好先熟悉下list相关接口：

【C++】容器list常用接口详解-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/2301_80555259/article/details/141756824?spm=1001.2014.3001.5501

目录

一.基本结构

 二.构造函数

三.析构函数

四.迭代器的实现

 五.const迭代器

六.修改操作

七.list和vector对比

一.基本结构

list类是一个带头双向循环链表，因此在定义list类前，先要定义节点类
节点类中的成员都是要面向外部访问的，因此都应该设置为public类，所以干脆这里直接定义为struct（成员都是public的class类）

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

在list类中，由于链表都是些链接关系，所以list类中只需要定义一个头结点head即可，当然此处为了方便后续操作，加入了size

list类的基本框架 

template<class T>
class list
{//简化下list_nodetypedef list_node node;
public://各种函数private:node* _head;//头结点size_t _size;//有效数据个数
};

 二.构造函数

如何初始化head?头结点一开始prev和next都是指向本身的

 因此，无参构造能很轻易地写出来

//无参构造
list()
{_head = new node;_head->_prev = _head;_head->_next = _head;_size = 0;
}//当然更这样写更好
//创建并初始化哨兵卫头结点，方便给构造和拷贝复用
void emptyinit()
{head = new node;_head->_prev = _head;_head->_next = _head;_size = 0;
}//无参构造
list()
{emptyinit();
}

无参的构造写好以后，接下来就可以仿照STL库中的带参构造，写一个用迭代器区间初始化的构造函数：

//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{emptyinit();while (first != last){push_back(*first);++first;}
}

 拷贝构造有很多写法，这里给出两种写法：

//直接拷贝构造
list(const list& x)
{empty_init();for (auto e : x){push_back(e);}
}
//利用临时对象拷贝构造
list(const list& x)
{emptyinit();//利用迭代器区间构造出一个临时对象tmplist tmp(x.begin(), x.end());std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}

利用临时对象来进行拷贝构造实际上是一种精妙的方法，它先定义了一个临时变量tmp，利用迭代器区间构造深拷贝了x的所有值，随后将新创建节点的_head以及_size跟tmp交换即可，同时，出了作用域以后tmp作为临时对象就会销毁，调用析构函数，由于此时已经交换了，那么此时实际实在销毁原先新节点的内存。

三.析构函数

在实现析构函数前，可以先实现下clear函数，析构函数实际可以复用clear

//清空出了头节点外的数据
void clear()
{iterator it = begin();while (it != end()){it = erase(it);//erase会返回下一个节点的迭代器}_size = 0;
}
//清理头节点
~list()
{clear();delete _head;_head = nullptr;
}

四.迭代器的实现

之前模拟vector和string的时候，两者底层都是连续的，想要得到下一个数据直接++即可，想要得到数据直接*解引用即可


然而这对于list是不行的，因为它底层不连续，此时就需要我们重载各种运算符了，但由于其底层仍然是一个指针（内置类型，不能重载），因此我们就将其封装进一个类来重载

template<class T>
struct list_iterator
{//这里要加<T>typedef list_node<T> node;typedef list_iterator iterator;//成员变量node* _node;//成员函数
};

1.构造函数

//构造函数
list_iterator(node* node):_node(node)
{}

2. 前置++/--和后置++/--

//前置++
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;
}

3.等于和不等于

//等于
bool operator==(const iterator& it)const
{return _node == it._node;
}
//不等于
bool operator!=(const iterator& it)const
{return _node != it._node;
}

4.解引用和箭头操作

迭代器的使用都是相同的，与指针相同，所以解引用迭代器得到的应该是节点数据。此外，当list存储的类型是结构体时，还应该支持->箭头操作。

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

指的注意的是，本来使用该迭代器需要用第一个->来找到data(当储存结构体类型时），然后再使用一个->才能查找到结构体内部的数据，但编译器为了代码的可读性，帮助我们省略了一个箭头，只需要一个箭头就可以访问数据了

做完这些后就可以将迭代器映射到list类当中了，在list类中复用迭代器类

typedef list_iterator iterator;
iterator begin()
{//使用匿名对象return iterator(_head->next);
}
iterator end()
{return iterator(_head);
}

 五.const迭代器

const迭代器和普通迭代器的区别是什么？const迭代器是为const对象准备的，const对象进行了限制，不能修改对象里的数据，那么，什么操作会因此数据的改变呢？很明显是解引用操作和箭头->，它们一个返回值的引用（T&），一个返回的指针(T*)，都具备修改的可能,当然，begin()和end()也可能修改

大家第一时间想到的可能是再重写一个const迭代器的类，里面的实现和普通迭代器都一样，唯一不同的点在于赋值重载*和->时，返回的const修饰的值 

然而这样做就会显得很臃肿，代码重复度很高，仔细观察不同点，仅仅在于T*和T&,那么不妨在原先的迭代器模板中再加入两个模板参数，只有在编写这两个函数时用到这两个参数

template<class T, class Ref, class Ptr>
struct list_iterator
{//...Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
}

此时就能在list类中将普通迭代器和const迭代器区分开了，当使用const对象时 ，直接返回const迭代器，使用普通对象，就返回普通迭代器

template<class T>
class list
{//这里要加<T>typedef list_node<T> node;
public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//...private:node* _head;size_t _size;
};
iterator begin()
{//使用匿名对象return iterator(_head->next);
}
iterator end()
{return iterator(_head);
}
const_iterator begin()const
{return const_iterator(_head->next);
}
const_iterator end()const
{return const_iterator(_head);
}

六.修改操作

void push_back(const T& x)
{node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;_head->_prev = newnode;newnode->_prev = tail;newnode->_next = _head;++_size;
}iterator insert(iterator pos, const T& x)
{//pos是公开类，内部的_node可以用.访问node* prev = pos._node->_prev;node* next = pos._node;node* newnode = new node(x);newnode->_prev = prev;newnode->_next = next;prev->_next = newnode;next->_prev = newnode;++_size;return iterator(newnode);
}iterator erase(iterator pos)
{assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return iterator(next);
}//直接复用erase
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}

七.list和vector对比

至此，list我们已经模拟完成，有没有加深一下对list的理解呢？在这里我们再对比一下list和vector的区别：

目录vectorlist
底层结构顺序表，物理空间连续带头双向循环链表，物理空间不连续
随机访问支持，效率为O(1)不支持，访问效率为O(N)
插入和删除任一位置插入删除效率低任一位置插入删除效率高
空间利用率连续空间，缓存利用率高不连续空间，容易造成内存碎片
迭代器原生的指针对原生指针的封装
迭代器失效插入和删除都会失效只有删除会失效
使用场景高效储存，支持随机访问有大量插入和删除操作，不关心随机访问

这篇关于【C++】list类：模拟实现（适合新手的手撕list）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1143912。

相关文章

Go语言使用Buffer实现高性能处理字节和字符

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ
阅读更多...
基于WinForm+Halcon实现图像缩放与交互功能

基于WinForm+Halcon实现图像缩放与交互功能

《基于WinForm+Halcon实现图像缩放与交互功能》本文主要讲述在WinForm中结合Halcon实现图像缩放、平移及实时显示灰度值等交互功能,包括初始化窗口的不同方式,以及通过特定事件添加相应... 目录前言初始化窗口添加图像缩放功能添加图像平移功能添加实时显示灰度值功能示例代码总结最后前言本文将
阅读更多...
Redis延迟队列的实现示例

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi
阅读更多...
C#实现WinForm控件焦点的获取与失去

C#实现WinForm控件焦点的获取与失去

《C#实现WinForm控件焦点的获取与失去》在一个数据输入表单中,当用户从一个文本框切换到另一个文本框时,需要准确地判断焦点的转移,以便进行数据验证、提示信息显示等操作,本文将探讨Winform控件... 目录前言获取焦点改变TabIndex属性值调用Focus方法失去焦点总结最后前言在一个数据输入表单
阅读更多...
基于C#实现PDF文件合并工具

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col
阅读更多...
C++中实现调试日志输出

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
Python实现将实体类列表数据导出到Excel文件

Python实现将实体类列表数据导出到Excel文件

《Python实现将实体类列表数据导出到Excel文件》在数据处理和报告生成中,将实体类的列表数据导出到Excel文件是一项常见任务,Python提供了多种库来实现这一目标,下面就来跟随小编一起学习一... 目录一、环境准备二、定义实体类三、创建实体类列表四、将实体类列表转换为DataFrame五、导出Da
阅读更多...
Java操作PDF文件实现签订电子合同详细教程

Java操作PDF文件实现签订电子合同详细教程

《Java操作PDF文件实现签订电子合同详细教程》：本文主要介绍如何在PDF中加入电子签章与电子签名的过程,包括编写Word文件、生成PDF、为PDF格式做表单、为表单赋值、生成文档以及上传到OB... 目录前言：先看效果：1.编写word文件1.2然后生成PDF格式进行保存1.3我这里是将文件保存到本地后
阅读更多...
Python实现数据清洗的18种方法

Python实现数据清洗的18种方法

《Python实现数据清洗的18种方法》本文主要介绍了Python实现数据清洗的18种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录1. 去除字符串两边空格2. 转换数据类型3. 大小写转换4. 移除列表中的重复元素5. 快速统
阅读更多...
用Java打造简易计算器的实现步骤

用Java打造简易计算器的实现步骤

《用Java打造简易计算器的实现步骤》：本文主要介绍如何设计和实现一个简单的Java命令行计算器程序,该程序能够执行基本的数学运算（加、减、乘、除）,文中通过代码介绍的非常详细,需要的朋友可以参考... 目录目标：一、项目概述与功能规划二、代码实现步骤三、测试与优化四、总结与收获总结目标：简单计算器，设计
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2