C++：关于模拟实现vector和list中迭代器模块的理解

文章目录

  • list和vector的迭代器对比
  • list的实现过程
  • 完整代码

本篇是关于vector和list的模拟实现中，关于迭代器模块的更进一步理解，以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等

本篇是写于前面模拟实现的一段时间后，重新回头看迭代器的实现，尤其是在模板角度对list中迭代器封装的部分进行解析，希望可以对迭代器的封装实现有更深层次的理解，同时将与库内的实现做对比进行优化处理

list和vector的迭代器对比

list和vector的迭代器实现是不一样的，在vector中的迭代器就是一个原生指针，因此在实现的时候也就是用的原生指针即可，但是对于list来说不能这样，list的迭代器中例如++和--这样的操作，是不能和vector中的原生指针一样直接去实现的，而是需要用next或者是prior来模拟这个过程，还有例如*和->这样的访问数据的模式，因此在list的迭代器实现中是使用了封装来进行实现的

STL中有六大组件，其中迭代器算其中一个，那么也就意味着迭代器具有通用的功能，例如下面的代码，在使用构造函数时可以使用迭代器进行构造，而这个构造的过程使用的迭代器对于各种容器来说都是通用的：

#include <iostream>
#include <vector>
#include <list>
using namespace std;int main()
{vector<int> v1{ 1,2,3,4,5,3,2,2 };vector<int> v2(v1.begin(), v1.end());list<int> l1(v1.begin(), v1.end());return 0;
}

那么就意味着，在实现迭代器的过程中也是就可以根据迭代器来进行不同容器间的构造

list的实现过程

首先，在list的实现过程中要有下面几个部分组成：list中包含的节点，list的迭代器访问，list的节点之间的关系

那么首先就是list中节点的定义，用到了模板，现在再对该部分进行解析，其实就是在创建的时候可以根据需要的内容开辟出对应的节点类型

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

有了节点信息，就可以对list做一些基础的操作，例如头插头删，尾插尾删等操作，但对于insert和erase这些操作还不能够实现，因此就要实现迭代器模块的内容

不管是对于vector还是list，迭代器的本质就是用一个原生指针去进行访问等等，但是list和vector不同的是，list的存储地址并不是连续的，因此在访问的过程中就需要对迭代器进行一定程度的封装，例如在++或者--的操作符上可以进行一些体现，因此list迭代器的实现是需要进行单独的封装的

// 定义正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> self;__list_iterator(Node* node):_node(node){}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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator !=(const self& s){return _node != s._node;}bool operator ==(const self& s){return _node == s._node;}Node* _node;
};

上面的片段对list进行了一些封装，实现了它的一些基础功能，从代码中也能看出来，迭代器的本质确确实实就是指针，用指针来进行一系列的操作，对下面这几个片段单独进行解析：

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

这是对于迭代器中解引用的运算符重载，这里使用的是&_node->_data的写法，看似很怪，但是实际上这里的函数调用过程应该是这样

在这里插入图片描述
也就是说，这里对于->进行运算符重载后，还需要进行解引用，这个运算符重载函数返回的是一个指针，而这个指针还要继续进行解引用才能得到用户想要得到的值，编译器在这里进行了特殊处理，两个->使得可读性下降，因此将两个->进行了一定程度的合并，只需要一个->就可以实现解引用的目的

其次是对模板的使用部分

template <class T, class Ref, class Ptr>typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> self;

这里在最开始定义的时候，就定义了数据类型，引用和指针三种模板参数，借助这个参数就可以用模板将复杂的内容实现简单化，只需要一份代码，模板就可以直接实例化出用户在调用的时候需要的代码，在进行封装const迭代器的时候，只需要提供的参数改为const版本就可以实现目的，很便捷

这样就实现了正向迭代器的普通版本，而对于const迭代器的版本也只需要进行不同的模板参数就可以实例化出const版本的迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

有了迭代器，在实现链表的各种函数功能就更加方便，例如可以实现erase和insert的操作，实现了这两个函数，在进行头插头删，尾插尾删的时候就更加方便，只需要进行原地的调用即可

	// Modifiersvoid push_front(const T& val){//Node* newnode = new Node;//newnode->_data = val;//newnode->_next = _head->_next;//_head->_next->_prev = newnode;//_head->_next = newnode;//newnode->_prev = _head;//_size++;insert(begin(), val);}void pop_front(){//Node* delnode = _head->_next;//_head->_next = _head->_next->_next;//_head->_next->_prev = _head;//delete delnode;//delnode = nullptr;//_size--;erase(begin());}void push_back(const T& val){//Node* newnode = new Node;//newnode->_data = val;//newnode->_prev = _head->_prev;//_head->_prev->_next = newnode;//newnode->_next = _head;//_head->_prev = newnode;//_size++;insert(end(), val);}void pop_back(){//Node* delnode = _head->_prev;//delnode->_prev->_next = _head;//_head->_prev = delnode->_prev;//delete delnode;//delnode = nullptr;//_size--;erase(--end());}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);_size++;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;cur = nullptr;_size--;prev->_next = next;next->_prev = prev;return iterator(next);}

那么上面是对前面已经有过的内容进行的重新温故，但是上面的代码其实是没有实现反向迭代器的，而在STL的库中，反向迭代器的定义和正向迭代器其实并不相同，它是直接借助正向迭代器对反向迭代器进行适配，有些类似于用vector，list或者deque对栈和队列进行的适配，也体现了封装和代码复用

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}Self& operator++(){--_it;return *this;}Ref operator*(){return *_it;}Ptr operator->(){return _it.operator->();}bool operator!=(const Self& s){return _it != s._it;}
private:Iterator _it;
};

上面的代码就是对于反向迭代器的封装，从中可以看出反向迭代器是使用了正向迭代器的，并且在它的基础上进行的修改，因此这个反向迭代器是可以适配于vector也可以适配于list的

整体来说，对于反向迭代器就是用正向迭代器进行适配出来的，体现了模板的好处

完整代码

#pragma oncenamespace mylist
{// 定义节点内容template <class T>struct list_node{list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}T _data;list_node<T>* _next;list_node<T>* _prev;};// 定义正向迭代器template <class T, class Ref, class Ptr>class __list_iterator{public:typedef list_node<T> Node;typedef __list_iterator<T, T&, T*> self;__list_iterator(Node* node):_node(node){}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;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator !=(const self& s){return _node != s._node;}bool operator ==(const self& s){return _node == s._node;}Node* _node;};// 定义反向迭代器template<class Iterator, class Ref, class Ptr>class reverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> self;public:reverse_iterator(Iterator it):_it(it){}self& operator++(){_it--;return *this;}self& operator++(int){self tmp(*this);_it--;return tmp;}self& operator--(){_it++;return *this;}self& operator--(int){self tmp(*this);_it++;return tmp;}Ref operator*(){Iterator cur = _it;return *(--cur);}Ptr operator->(){return &(operator*());}bool operator !=(const self& s){return _it != s._it;}bool operator ==(const self& s){return _it == s._it;}Iterator _it;};// 定义链表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;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;//typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;// Constructorlist(){empty_init();}list(const list<T>& lt){for (auto x : lt){push_back(x);}}list(iterator begin, iterator end){empty_init();while (begin != end){push_back(begin._node->_data);begin++;}}//list(reverse_iterator rbegin, reverse_iterator rend)//{//	empty_init();//	while (rbegin != rend)//	{//		push_back(rbegin._node->_data);//		rbegin++;//	}//}// Destructor~list(){clear();delete _head;_head = nullptr;}// Operator=list<T>& operator=(const list<T>& lt){swap(lt);return *this;}// Iteratorsiterator 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);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}//const_reverse_iterator rbegin() const//{//	return const_reverse_iterator(end());//}//const_reverse_iterator rend() const//{//	return const_reverse_iterator(begin());//}// Capacitybool empty(){return _size == 0;}size_t size(){return _size;}// Element accessT& front(){return begin()._node->_data;}T& back(){return (--end())._node->_data;}// Modifiersvoid push_front(const T& val){//Node* newnode = new Node;//newnode->_data = val;//newnode->_next = _head->_next;//_head->_next->_prev = newnode;//_head->_next = newnode;//newnode->_prev = _head;//_size++;insert(begin(), val);}void pop_front(){//Node* delnode = _head->_next;//_head->_next = _head->_next->_next;//_head->_next->_prev = _head;//delete delnode;//delnode = nullptr;//_size--;erase(begin());}void push_back(const T& val){//Node* newnode = new Node;//newnode->_data = val;//newnode->_prev = _head->_prev;//_head->_prev->_next = newnode;//newnode->_next = _head;//_head->_prev = newnode;//_size++;insert(end(), val);}void pop_back(){//Node* delnode = _head->_prev;//delnode->_prev->_next = _head;//_head->_prev = delnode->_prev;//delete delnode;//delnode = nullptr;//_size--;erase(--end());}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);_size++;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;cur = nullptr;_size--;prev->_next = next;next->_prev = prev;return iterator(next);}void swap(const list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete(cur);cur = next;}_head->_next = _head;_head->_prev = _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_head->_data = T();_size = 0;}void Print(){Node* cur = _head->_next;while (cur != _head){cout << cur->_data << "->";cur = cur->_next;}cout << "null" << endl;}private:Node* _head;size_t _size;};void test_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << "iterator constructor:";list<int> lt1(lt.begin(), lt.end());lt1.Print();cout << "front():" << lt.front() << endl;cout << "back():" << lt.back() << endl;mylist::__list_iterator<int, int&, int*> it = lt.begin();while (it != lt.end()){std::cout << *it << " ";it++;}cout << endl;}void test_clear(){list<int> lt1;cout << "push_back:" << endl;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.Print();lt1.clear();lt1.push_back(5);lt1.push_back(6);lt1.push_back(7);lt1.push_back(8);lt1.Print();}void test_push_pop(){list<int> lt1;cout << "push_back:" << endl;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.Print();cout << "pop_back:" << endl;lt1.pop_back();lt1.Print();list<int> lt2;cout << "push_front:" << endl;lt2.push_front(1);lt2.push_front(2);lt2.push_front(3);lt2.push_front(4);lt2.Print();cout << "pop_front:" << endl;lt2.pop_front();lt2.Print();}void test_reverse_iterator(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << "iterator constructor:";//list<int> lt1(lt.rbegin(), lt.rend());//lt1.Print();cout << "front():" << lt.front() << endl;cout << "back():" << lt.back() << endl;mylist::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){std::cout << *rit << " ";rit++;}cout << endl;}void test(){test_reverse_iterator();//test_push_pop();//test_clear();}
}

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

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

相关文章

【论文笔记】A theory of learning from different domains

【论文笔记】A theory of learning from different domains

防盗 https://www.cnblogs.com/setdong/p/17756127.html domain adaptation 领域理论方向的重要论文. 这篇笔记主要是推导文章中的定理, 还有分析定理的直观解释. 笔记中的章节号与论文中的保持一致. 1. Introduction domain adaptation 的设定介绍: 有两个域, source domain…
阅读更多...
轻量限制流量？阿里云轻量应用服务器月流量包收费说明

轻量限制流量？阿里云轻量应用服务器月流量包收费说明

阿里云轻量应用服务器部分套餐限制月流量&#xff0c;轻量应用服务器按照套餐售卖&#xff0c;有的套餐限制月流量&#xff0c;有的不限制流量。像阿里云轻量2核2G3M带宽轻量服务器一年108元和轻量2核4G4M带宽一年297.98元12个月&#xff0c;这两款是不限制月流量的。阿里云百科…
阅读更多...
中国植被功能型图（1km分辨率）

中国植被功能型图（1km分辨率）

简介&#xff1a; 植被功能型&#xff08;PFT&#xff09;是根据植物种的生态系统功能及其资源利用方式而对宠大的植物种进行的组合&#xff0c;每一种植被功能型共享相似的植物属性&#xff0c;是将植物种的多样性简化为植物功能和结构的多样性,用以预测全球变化情景下生态系…
阅读更多...
优盘中毒了怎么办？资料如何恢复

优盘中毒了怎么办？资料如何恢复

在现代社会中&#xff0c;优盘成为我们日常生活与工作中必备的便携式存储设备。然而&#xff0c;正是由于其便携性&#xff0c;优盘也成为病毒感染的主要目标之一。本篇文章将帮助读者了解如何应对优盘中毒的情况&#xff0c;以及如何恢复因病毒感染丢失的资料。 ▶优盘为什么…
阅读更多...
简单好用的CHM文件阅读器 CHM Viewer Star最新 for mac

简单好用的CHM文件阅读器 CHM Viewer Star最新 for mac

CHM Viewer Star 是一款适用于 Mac 平台的 CHM 文件阅读器软件&#xff0c;支持本地和远程 CHM 文件的打开和查看。它提供了直观易用的界面设计&#xff0c;支持多种浏览模式&#xff0c;如书籍模式、缩略图模式和文本模式等&#xff0c;并提供了丰富的功能和工具&#xff0c;如…
阅读更多...
温度在线检测技术在电力电缆线路的应用

温度在线检测技术在电力电缆线路的应用

在电力电缆的日常运行检测中&#xff0c;针对电缆温度的状况&#xff0c;所采用的电力温度在线检测技术也得到了大范围的普及。电网系统中&#xff0c;其单位时间内可输送的电力能源受到其温度的变化影响。因此&#xff0c;采用更有效的方式实时检测电缆系统运行温度&#xff0…
阅读更多...
Linux|qtcreator编译可执行程序双击运行

Linux|qtcreator编译可执行程序双击运行

qt GUI window移植到linux参见&#xff1a;VS|vs2017跨平台编译linux&&CConsole&&QtGUI 参考&#xff1a;QtCreator修改项目的生成目录 文章目录 双击.pro文件&#xff0c;点击configureproject构建项目切换到release模式下双击打开pro文件&#xff0c;修改依赖…
阅读更多...
WPF向Avalonia迁移（四、其他事项）

WPF向Avalonia迁移（四、其他事项）

开发必备 1. Avalonia项目源代码&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;没有源代码&#xff0c;你连控件的背景色怎么改都找不着&#xff01;&#xff01; 2.下载你所使用的版本&#x…
阅读更多...
【手写数字识别】数据挖掘实验二

【手写数字识别】数据挖掘实验二

文章目录 Ⅰ、项目任务要求任务描述&#xff1a;主要任务要求(必须完成以下内容但不限于这些内容)&#xff1a; II、实现过程数据集描述实验运行环境描述KNN模型决策树模型朴素贝叶斯模型SVM模型不同方法对MNIST数据集分类识别结果分析(不同方法识别对比率表及结果分析) 完整代…
阅读更多...
李宏毅 2022机器学习 HW3 boss baseline 上分记录

李宏毅 2022机器学习 HW3 boss baseline 上分记录

作业数据是所有数据都有标签的版本。 李宏毅 2022机器学习 HW3 boss baseline 上分记录 1. 训练数据增强, private 0.760562. cross validation&ensemble, private 0.816473. test dataset augmentation, private 0.824584. resnet, private 0.865555. Image Normalizatio…
阅读更多...
DP4054H完全兼容替代TP4054 36V 耐压 500mA 线性锂电充电芯片

DP4054H完全兼容替代TP4054 36V 耐压 500mA 线性锂电充电芯片

产品概述&#xff1a; DP4054H是一款完整的采用恒定电流/恒定电压单节锂离子电池充电管理芯片。其SOT小封装和较少的外部元件数目使其成为便携式应用的理想器件&#xff0c;DP4054H可以适合USB 电源和适配器电源工作。由于采用了内部PMOSFET架构&#xff0c;加上防倒充电 路&am…
阅读更多...
【微服务】RedisSearch 使用详解

【微服务】RedisSearch 使用详解

目录 一、RedisJson介绍 1.1 RedisJson是什么 1.2 RedisJson特点 1.3 RedisJson使用场景 1.3.1 数据结构化存储 1.3.2 实时数据分析 1.3.3 事件存储和分析 1.3.4 文档存储和检索 二、当前使用中的问题 2.1 刚性数据库模式限制了敏捷性 2.2 基于磁盘的文档存储导致瓶…
阅读更多...
【20】c++设计模式——＞组合模式

【20】c++设计模式——＞组合模式

组合模式定义 C组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;他允许将对象组合成树形结构来表示“部分-整体”的层次结构&#xff1b;在组合模式中有两种基本类型的对象&#xff1a;叶子对象和组合对象&#xff0c;叶子对象时没有子对象…
阅读更多...
Websocket获取B站直播间弹幕教程——第二篇、解包/拆包

Websocket获取B站直播间弹幕教程——第二篇、解包/拆包

教程一、Websocket获取B站直播间弹幕教程 — 哔哩哔哩直播开放平台 1、封包 我们连接上B站Websocket成功后&#xff0c;要做两件事情&#xff1a; 第一、发送鉴权包。第二、发送心跳包&#xff0c;每30秒一次&#xff0c;维持websocket连接。 这两个包不是直接发送过去&…
阅读更多...
无为WiFi的一批服务器

无为WiFi的一批服务器

我们在多个地区拥有高速服务器&#xff0c;保证网速给力&#xff0c;刷片无压力 嘿嘿 <?phpinclude("./includes/common.php"); $actisset($_GET[act])?daddslashes($_GET[act]):null; $urldaddslashes($_GET[url]); $authcodedaddslashes($_GET[authcode]);he…
阅读更多...
RxJava介绍及基本原理

RxJava介绍及基本原理

随着互联网的迅猛发展&#xff0c;Java已成为最广泛应用于后端开发的语言之一。而在处理异步操作和事件驱动编程方面&#xff0c;传统的Java多线程并不总是最佳选择。这时候&#xff0c;RxJava作为一个基于观察者模式、函数式编程和响应式编程理念的库&#xff0c;为我们提供了…
阅读更多...
30WSIP网络有源号角 50W SIP网络有源号角

30WSIP网络有源号角 50W SIP网络有源号角

30WSIP网络有源号角 50W SIP网络有源号角 SIP-7044是我司的一款SIP网络有源号角&#xff0c;具有10/100M以太网接口&#xff0c;内置有一个高品质扬声器&#xff0c;将网络音源通过自带的功放和喇叭输出播放&#xff0c;可达到功率30W。SIP-7044作为SIP系统的播放终端&#xf…
阅读更多...
【photoshop学习】用 Photoshop 做的 15 件创意事

【photoshop学习】用 Photoshop 做的 15 件创意事

用 Photoshop 做的 15 件创意事 每个人总是谈论 Photoshop 的无限可能。您可以使用该程序做很多事情&#xff0c;列表几乎是无穷无尽的。 嘿&#xff0c;我是卡拉&#xff01;如果您花过一些时间使用 在线ps&#xff0c;您可能见过我&#xff08;并且注意到我提到了这一点&am…
阅读更多...
一个完整的初学者指南Django-part1

一个完整的初学者指南Django-part1

源自&#xff1a;https://simpleisbetterthancomplex.com/series/2017/09/04/a-complete-beginners-guide-to-django-part-1.html 一个完整的初学者指南Django - 第1部分 介绍 今天我将开始一个关于 Django 基础知识的新系列教程。这是一个完整的 Django 初学者指南。材料分为七…
阅读更多...
iPhone 15分辨率,屏幕尺寸,PPI 详细数据对比 iPhone 15 Plus、iPhone 15 Pro、iPhone 15 Pro Max

iPhone 15分辨率,屏幕尺寸,PPI 详细数据对比 iPhone 15 Plus、iPhone 15 Pro、iPhone 15 Pro Max

史上最全iPhone 机型分辨率&#xff0c;屏幕尺寸&#xff0c;PPI详细数据&#xff01;已更新到iPhone 15系列&#xff01; 点击放大查看高清图 &#xff01;
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023