【C++】list模拟实现（完结）

ops/2024/11/27 10:14:14/

1.普通迭代器（补充）

1.1 后置++和后置--

我们迭代器里面实现了前置++和前置--，还需要实现后置++和后置--。

 在list.h文件的list_iterator类里面实现。

//后置++/--
Self& operator++(int)
{Self tem(*this);//保存原来的值_node = _node->_next;return tem;
}
Self& operator--(int)
{Self tem(*this);//保存原来的值_node = _node->_prev;return tem;
}

1.2 重载->

因为迭代器模拟的是指针的行为，所以这里我们还要重载一下->。

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

这个->的应用场景如下。

现在有个AA的类或结构体。

struct AA
{int _a = 1;int _b = 2;
};

list里面存这个AA类型的数据。

void test5()
{list<AA> la;}

然后给里面随便存几个数据。

list<AA> la;
la.push_back(AA());
la.push_back(AA());
la.push_back(AA());
la.push_back(AA());

再用迭代器遍历，此时就要用->来引出AA里面的_a或者_b，不能用.引出。

list<AA>::iterator ia = la.begin();
while (ia != la.end())
{cout << ia->_a << " " << ia->_b << endl;++ia;
}

完整地写法如下。

cout << ia.operator->()->_a << " " << ia.operator->()->_b << endl;

第一个箭头是运算符重载的->，第二个_a前面的->就是没有重载的解引用符号。

为了可读性，省略了一个箭头，这里省略的也是第二个->。 

2.const迭代器

2.1 const_iterator

const修饰迭代器，我们不可以对迭代器指向的内容进行修改，但是迭代器可以改变自己的指向。

我们如何实现迭代器可以改变自己指向而不让改变指向内容？

我们修改迭代器指向的内容通过什么修改？通过迭代器类里面的两个运算符重载，operator*和operator->， 如果我们现在把operator*和operator->的返回值用const修饰，就不能通过他们两个修改指向内容了。

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

但是我们不可以直接把list_iterator里面的这两个成员函数给改了，改了的话普通迭代器就不能改了，我们只要const迭代器不能改。所以，我们重新实现一个类，叫list_const_iterator，这个类除了前面两个运算符重载函数变，其他成员函数一律不变。

在list.h文件的namespace里实现。

template<class T>
struct list_const_iterator
{typedef list_node<T> Node; //换个短的名字typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*() {return _node->_data;}const T* operator->(){return &_node->_data;}//前置++/--Self& operator++() //重载++{_node = _node->_next;//加到下一个节点return *this;//返回自己}Self& operator--() //重载--{_node = _node->_prev;//减到前一个节点return *this;//返回自己}//后置++/--Self& operator++(int){Self tem(*this);//保存原来的值_node = _node->_next;return tem;}Self& operator--(int){Self tem(*this);//保存原来的值_node = _node->_prev;return tem;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

同时，我们要在list类里面，public部分加上下面这句话。

typedef list_const_iterator<T> const_iterator;

以及迭代器的begin和end接口。

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

 const迭代器部分的测试我们和接下来要说的打印函数一起测。

2.2 print_container 打印

这个函数就是为了方便我们打印数据。

template<class container>
void print_container(const container& c)
{for (auto e : c){cout << e << " ";}cout << endl;
}

在test.cpp中对const迭代器和print_container一起测试。

void test6()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_container(lt);
}

3.优化两种迭代器的实现

很容易发现，我们前面的实现方式代码过于冗余，list_iterator 和 list_const_iterator两个类重叠部分太多。于是，我们就需要用到类模板，来优化一下。

在list_iterator类的基础上优化。

我们增加两个模板参数，Ref和Ptr。

Ref是引用，或者是const引用；Ptr是地址，或者const地址。

 然后把operator*返回值类型换成Ref，operator->返回值类型换成Ptr。

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

list类里面的如下部分也要改。

就可以了，迭代器的类模板就实现好了。 

我们用前面的测试样例在test.cpp测试一下。

4.迭代器失效问题

list的迭代器失效在insert插入数据是按理来说应该是不会发生的，因为这里没有扩容的的问题。

但是删除数据就有迭代器失效的问题，迭代器失效问题更加详细具体的分析在【C++】vector模拟实现、迭代器失效问题（超详解）

list这里如果删除一个节点，迭代器绝对就是类似野指针了。

解决方案还是对erase进行改造，让erase有返回值，erase返回的是删除结点的下一个节点位置。

iterator erase(iterator pos)
{assert(pos != end());//不可以删哨兵位头节点Node* prev = pos._node->_prev;//存pos前后节点Node* next = pos._node->_next;prev->_next = next;//链接pos前后节点next->_prev = prev;delete pos._node;//释放pos节点--_size;return next;
}

在test.cpp中测试一下。我们删除所有偶数。

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
auto it = lt.begin();
while (it != lt.end())
{if (*it % 2 == 0){it = lt.erase(it);}else{++it;}
}
lt.print_container(lt);

 所以list的迭代器失效问题就简单很多。

但是为了和库里面保持一致，我们还是对insert也改进一下，让他也有返回值。

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);//连接起来newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;++_size;return newnode;//返回插入的节点
}

5.析构函数

5.1 clear

清空所有数据，但是不清除哨兵位头节点。

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

5.2 析构函数

析构函数可以套用clear，clear不清除哨兵位，析构这里另外清除一下就可以了。

~list()
{clear();delete _head;_head = nullptr;
}

6.构造函数（优化）

6.1 空链表初始化

我们重新写一个函数，用来初始化空的list。空的list就是只有哨兵位头节点。

void empty_init()
{_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;
}

这个代码和list默认构造代码一模一样。这样实现主要是为了方便后面的拷贝构造。

6.2 默认构造

我们现在默认构造的代码就直接复用前面写的empty_init。

list()
{empty_init();
}

6.3 拷贝构造

这里的拷贝构造依然是复用push_back实现。

list(const list<T>& lt)
{for (auto& e : lt){push_back(e);}
}

比如说我们用lt1拷贝构造lt2 

但是此时的lt2连哨兵位都没有，这样写肯定有问题。所以我们要加上前面写的empty_init。

//lt2(lt1)
list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}

 

 在test.cpp里对前面的三个一起测试。

void test8()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2(lt1);//拷贝构造lt1.print_container(lt1);lt2.print_container(lt2);
}

 

7.operator= 赋值运算符重载

这里的赋值运算符重载，也是要深拷贝，所以我们还是采用现代写法，现代写法详解在【C++拓展】深拷贝现代写法 

首先自己写一个swap。

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

在test.cpp中测试一下。

list<int> lt1, lt2;
lt1.push_back(1);
lt1.push_back(2);
lt2.push_back(3);
lt2.push_back(4);
lt1.print_container(lt1);
lt2.print_container(lt2);
lt2 = lt1; //赋值
lt1.print_container(lt1);
lt2.print_container(lt2);

 

list的内容就结束了，感谢观看，下篇再见~


http://www.ppmy.cn/ops/137049.html

相关文章

111.有效数字

111.有效数字

class Solution {public boolean isValid(String word) {if(word.length()<3){return false;}int countV0,countC0;//分别统计原音和辅音for(int i0;i<word.length();i){if(Character.isLetterOrDigit(word.charAt(i))){if(word.charAt(i)a||word.charAt(i)e||word.charA…
阅读更多...
Xcode15（iOS17.4）打包的项目在 iOS12 系统上启动崩溃

Xcode15（iOS17.4）打包的项目在 iOS12 系统上启动崩溃

0x00 启动崩溃 崩溃日志&#xff0c;只有 2 行&#xff0c;看不出啥来。 0x01 默认配置 由于我开发时&#xff0c;使用的 Xcode 14.1&#xff0c;打包在另外一台电脑 Xcode 15.3 Xcode 14.1 Build Settings -> Asset Catalog Compliter - Options Xcode 15.3 Build S…
阅读更多...
Flutter实现tts语音播报

Flutter实现tts语音播报

目录 引言 添加flutter_tts依赖 设置语言和发音人 macOS Android iOS 说话、停止、获取语言、设置语言、设置语音速率、获取声音、设置声音、设置音量、设置音高、是否语言可用、设置共享实例 监听平台 封装代码 使用案例 引言 随着移动应用的不断发展&#xff0c;…
阅读更多...
godot游戏引擎_瓦片集和瓦片地图介绍

godot游戏引擎_瓦片集和瓦片地图介绍

在 Godot 中&#xff0c;TileSet 和 TileMap 是用于处理瓦片地图的两个关键概念&#xff0c;它们的作用和用途有明显的区别。以下是两者的详细对比&#xff1a; 1. TileSet&#xff08;瓦片集&#xff09; TileSet 是资源&#xff0c;定义瓦片的内容和属性。 特点&#xff1a…
阅读更多...
【Electron学习笔记（二）】基于Electron开发应用程序

【Electron学习笔记（二）】基于Electron开发应用程序

基于Electron开发本地应用程序 基于Electron开发本地应用程序前言正文1、创建 pages 目录2、创建 index.html 文件3 、创建 html.css 文件4 、main.js里引入页面5 、运行 start 命令6 、启用开发者模式7 、解决内容安全策略8、完善窗口行为9、配置自动重启&#xff0c;保存后自…
阅读更多...
vue3+ts 我写了一个跟swagger.yml生成请求和响应实体（接口）

vue3+ts 我写了一个跟swagger.yml生成请求和响应实体（接口）

一、下载地址 swagger-to-ts: 使用python编写的一个根据swagger.yml生成vue3或ts的接口&#xff08;interface&#xff09;和类&#xff08;class&#xff09; - Gitee.com 进入下面页面&#xff0c;将这两个文件一起下载 二、配置 打开 config.toml 文件&#xff0c;修改ip为…
阅读更多...
网络层协议IP

网络层协议IP

对于网络层我们直接通过IP协议来了解其内容 一.IP协议 首先我们先来了解几个概念&#xff1a; 主机&#xff1a;配有IP地址&#xff0c;但是不进行路由控制的设备 路由器&#xff1a;配有IP地址&#xff0c;同时进行路由控制的设备 节点&#xff1a;主机和路由器的统称 所以现在…
阅读更多...
uni-app运行 安卓模拟器 MuMu模拟器

uni-app运行 安卓模拟器 MuMu模拟器

最近公司开发移动端系统&#xff0c;使用真机时每次调试的时候换来换去的麻烦&#xff0c;所以使用模拟器来调试方便。记录一下安装和连接的过程 一、安装MuMu模拟器 百度搜索MuMu模拟器并打开官网或者点这里MuMu模拟器官网 点击下载模拟器 安装模拟器&#xff0c;如果系统…
阅读更多...
最新文章

Copyright @ 2022~2023