秒懂C++之deque及反向迭代器

fe594ea5bf754ddbb223a54d8fb1e7bc.gif

目录

 

前言

一.deque的常用接口

二.deque的原理

2.1 vector与list的优缺点

2.2 deque的原理

三.反向迭代器

四.全部代码

前言

秒懂C++之List-CSDN博客

秒懂C++之vector（下）-CSDN博客

本文后面关于反向迭代器的操作会涉及到前面的文章~

一.deque的常用接口

deque可以说是结合了容器vector与list的所有特点~

二.deque的原理

2.1 vector与list的优缺点

vector:优~缺~点

  • 支持随机访问
  • 缓存命中（物理空间连续）
  • 浪费空间（扩容多余）
  • 前面部分插入删除效率低

list：优~缺~点

  • 不支持随机访问
  • 缓存命中低（物理空间非连续）
  • 空间按需申请与释放
  • 任意位置插入删除效率高

最后发现，二者可以说是互补的表现

2.2 deque的原理

其实融合两大容器特点的deque并不像我们想象中那样，它本质是通过存储在指针数组的指针来管理数据的~一般buff数组满了不会直接扩容，而是开辟一个新的空间，然后我们在到指针数组中添加一个指针去指向新空间，这也是为什么先在居中位置的原因~（要给前面与后面的指针留空间）

而我们在已满条件头插时也不是从buff数组头部开始，而是在尾部，与下一处空间保持衔接性~

而这种结构的优缺点也很明显~

  • 头插头删，尾插尾删很方便
  • 当我们尝试随机访问时（例如访问第i个的数据），我们以buff容量全为10为例~
  • 若全部buff容量已满，i/10代表访问第i个buff~在第i个buff中 i%10代表求出我们想要访问的数据位置
  • 若第一个buff容量仍不满，i-=第一个buff中的数据个数，后面再重复上一步
  • 当我们尝试中间删除时，若想保持buff容量，则挪动数据。若不想保持，则扩容。

最后我们发现实在是奇怪，两个缺点都有着互相矛盾的地方，很麻烦就是了，而这也是dequeue虽然有两个容器的特点，但终究不是主流的原因。也只有当我们想要多次进行头插头删，尾插尾删这些操作的时候才会想去用它~

不过人家的迭代器很强大，大家可以了解一下~

三.反向迭代器

在学习反向迭代器之前我们先来测试一下原生指针与我们自定义的指针有何区别~

可以发现最开始的指向都是一致的，没有问题。但是二者*解引用以及运算符++后就会有所区别了~

如果我们想要调用反向迭代器，那我们就需要和iterator一样用类去封装反向迭代器，还要再加入const版本~

反向迭代器与正向迭代器不一样的就是把++当成--，把--当成++。其他都一样~

但最后也只是实现了服务于容器List的反向迭代器~有没有一种方法可以让反向迭代器适用所有的容器呢？

我们来写一个关于反向迭代器适配容器的文件~

#pragma once
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref,Ptr> Self;Iterator cur;//创建正向迭代器类对象ReverseIterator(Iterator it)//通过正向迭代器对象构造并初始化对象:cur(it){}Self& operator++(){--cur;//调用正向迭代器的--接口return *this;}Self& operator--(){++cur;//调用正向迭代器的++接口return *this;}Ref operator*(){Iterator tmp = cur;//因为反向迭代器对称的特性，后面需要前置--，而解引用不需要迭代器移动，所有用临时对象来搞--tmp;return *tmp;}Ptr operator->(){return &(operator*());//->实际上是两个，这里只需要返回解引用后的地址即可 例如*返回AA，那么&AA就是AA*了}bool operator!=(const Self& s){return cur != s.cur;}
};

在这里会发现，比起直接拷贝复制正向迭代器的代码，不如直接复用它~核心就是通过正向迭代器来构建我们的反向迭代器，而与正向迭代器的不同之处我们也可以在复用它的同时稍微做出一些修改即可。比如运算符++我们就调用正向迭代器的--，运算符--就调用正向迭代器的++。而解引用由于反向迭代器的特殊性，我们再额外做出修改就好了~

这样就相当于我们写了一套反向迭代器的模板，核心在于复用正向迭代器，更精妙的是正向迭代器的所属容器也可以让反向适用。比如我们是写了一个关于容器vector的正向迭代器，那么我们可以通过类模板把正向迭代器传输给反向迭代器，反向迭起器通过复用传输过来的正向迭代器也形成了服务于容器vector的特性~

四.全部代码

//ReverseIterator.h#pragma once
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref,Ptr> Self;Iterator cur;//创建正向迭代器类对象ReverseIterator(Iterator it)//通过正向迭代器对象构造并初始化对象:cur(it){}Self& operator++(){--cur;//调用正向迭代器的--接口return *this;}Self& operator--(){++cur;//调用正向迭代器的++接口return *this;}Ref operator*(){Iterator tmp = cur;//因为反向迭代器对称的特性，后面需要前置--，而解引用不需要迭代器移动，所有用临时对象来搞--tmp;return *tmp;}Ptr operator->(){return &(operator*());//->实际上是两个，这里只需要返回解引用后的地址即可 例如*返回AA，那么&AA就是AA*了}bool operator!=(const Self& s){return cur != s.cur;}
};
//list.h
#pragma once
#include <assert.h>
#include"ReverseIterator.h"
namespace lj
{template <class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _Data;//构造初始化 利用匿名对象调用该类型的构造函数ListNode<T>(const T& x = T()){_next = nullptr;_prev = nullptr;_Data = x;}};template <class T,class Ref,class Ptr>struct _list_iterator{typedef ListNode<T> Node;typedef _list_iterator<T,Ref,Ptr> self;Node* _node;//构造函数_list_iterator(Node* node){_node = node;}//前置++self& operator++(){//不再是单纯的自加1，而是指向下一位置_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;}//指针与指针的对比！=bool operator!=(const self& x){return _node != x._node;}//指针与指针的对比==bool operator==(const self& x){return _node == x._node;}Ptr operator->(){return &_node->_data;}};template <class T>class list{typedef ListNode<T> Node;public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());//把正向迭代器传输过去}reverse_iterator rend(){return reverse_iterator(begin());//把正向迭代器传输过去}//构造函数list(){init();}void init(){_head = new Node;//创建带头节点_head->_next = _head;//构成双向循序_head->_prev = _head;}//尾插void push_back(const T& x){insert(end(), x);先创建新节点//Node* newnode = new Node(x);先找到尾节点//Node* tail = _head->_prev;开始链接//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;}//指向第一个有效节点iterator begin(){	//单参数隐式类型转换//return iterator(_head->_next);return _head->_next;}const_iterator begin()const{	//单参数隐式类型转换//return iterator(_head->_next);return _head->_next;}//指向头节点：哨兵位iterator end(){//return iterator(_head);return _head;}//指向头节点：哨兵位const_iterator end()const{//return iterator(_head);return _head;}//插入iterator insert(iterator pos,const T& x){//创建插入节点Node* newnode = new Node(x);//记录插入位置Node* node = pos._node;Node* nodeprev = node->_prev;nodeprev->_next = newnode;newnode->_prev = nodeprev;newnode->_next = node;node->_prev = newnode;//return iterator(newnode);return newnode;}//头插void push_front(const T& x){insert(begin(), x);}//erase 删除iterator erase(iterator pos){//记录位置Node* node = pos._node;Node* nodenext = node->_next;Node* nodeprev = node->_prev;//开始链接nodeprev->_next = nodenext;nodenext->_prev = nodeprev;delete node;return nodenext;}//pop_back 尾删void pop_back(){erase(--end());}//pop_front 头删void pop_front(){erase(begin());}//clear 清理void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase(it);}}~list(){clear();delete _head;_head = nullptr;}//list l2(l1) 拷贝构造list(list<T>& lt){init();for (const auto& e : lt){push_back(e);}}//赋值拷贝 传统写法/*list<T>& operator=(list<T>& lt){if (*this != lt){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}//赋值拷贝 现代写法list<T>& operator=(list<T> lt){swap(lt);return *this;}private:Node* _head;//带头节点：哨兵位};void test2(){lj::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lj::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;}
}
//vector.h
#pragma once#include <assert.h>
#include"ReverseIterator.h"namespace lj
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;//迭代器构造template <class Inputiterator>vector(Inputiterator first, Inputiterator last){while (first != last){push_back(*first);first++;}}reverse_iterator rbegin(){return reverse_iterator(end());//把正向迭代器传输过去}reverse_iterator rend(){return reverse_iterator(begin());//把正向迭代器传输过去}//构造函数vector(){_start = nullptr;_finish = nullptr;_endofstorage = nullptr;}//拷贝构造 现代写法 v2(v1)vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}T& operator[](size_t pos){assert(pos < size());return _start[pos];}void swap(vector<T>& v){std::swap(_start,v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}//析构函数~vector(){if(_start)delete[] _start;_start = nullptr;_finish = nullptr;_endofstorage = nullptr;}size_t capacity()const{return _endofstorage - _start;}size_t size()const{return _finish - _start;}iterator begin(){return _start;}const_iterator begin()const{return _start;}iterator end(){return _finish;}const_iterator end()const{return _finish;}void reserve(size_t n){if (n>capacity()){size_t old = size();//记录原空间的大小T* tmp = new T[n];//开辟新空间——异地扩容if (_start){for (size_t i = 0; i < old; i++){tmp[i] = _start[i];//赋值拷贝为深拷贝}delete[] _start;//释放原空间}_start = tmp;//指向新空间_finish = _start + old;_endofstorage = _start + n;}}//尾插函数void push_back(const T& x){//检查扩容if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;_finish++;}//插入函数iterator insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);//检查扩容if (_finish == _endofstorage){size_t len = pos - _start;//记录原空间长度reserve(capacity() == 0 ? 4 : capacity() * 2);pos = len + _start;//让pos指向新空间并且同步长度}//开始利用函数插入,往后挪动数据//memmove(pos + 1, pos, (_finish - pos) * sizeof(T));iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;_finish++;return pos;}//resize 扩容初始化   void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);//扩容while (_finish < _start + n){*_finish = val;_finish++;}}else{_finish = _start + n;}}//erase 删除iterator erase(iterator pos){assert(pos <= _finish && pos >= _start);iterator it = pos + 1;while (it<_finish){*(it-1) = *it;it++;}_finish--;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};void test_vector(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);lj::vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;}
}
//test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<vector>
using namespace std;#include"List.h"
#include"vector.h"int main()
{//lj::test2();lj::test_vector();return 0;/*lj::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lj::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;*/
}

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

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

相关文章

uni-app封装组件实现下方滑动弹出模态框

uni-app封装组件实现下方滑动弹出模态框

子组件 <template><div class"bottom-modal" :class"{show: showModal}"><div class"modal-content" :class"{show: showModal}"><!-- 内容区域 --><slot></slot></div></div></…
阅读更多...
【JAVA多线程】AQS，JAVA并发包的核心

【JAVA多线程】AQS，JAVA并发包的核心

目录 1.概述 1.1.什么是AQS 1.2.AQS和BlockQueue的区别 1.3.AQS的结构 2.源码分析 2.1.CLH队列 2.2.模板方法的实现 2.2.1.独占模式 1.获取资源 2.释放资源 2.2.2.共享模式 1.概述 1.1.什么是AQS AQS非常非常重要&#xff0c;可以说是JAVA并发包&#xff08;java.…
阅读更多...
案例开发-日程管理2第一期(超详细教程、配备图文和源代码注释，没学过也能看懂)

案例开发-日程管理2第一期(超详细教程、配备图文和源代码注释，没学过也能看懂)

文章目录 一、 项目前期准备1.数据库准备2.导入依赖3.pojo包处理4.dao包处理5.service包处理6.controller包处理7.加密工具类的使用8.页面文件的导入 总结 一、 项目前期准备 1.数据库准备 创建schedule_system数据库并执行如下语句 SET NAMES utf8mb4; SET FOREIGN_KEY_CHE…
阅读更多...
WPF学习（4）- VirtualizingStackPanel （虚拟化元素）+Canvas控件（绝对布局）

WPF学习（4）- VirtualizingStackPanel （虚拟化元素）+Canvas控件（绝对布局）

VirtualizingStackPanel虚拟化元素 VirtualizingStackPanel 类&#xff08;虚拟化元素&#xff09;和StackPanel 类在用法上几乎差不多。其作用是在水平或垂直的一行中排列并显示内容。它继承于一个叫VirtualizingPanel的抽象类&#xff0c;而这个VirtualizingPanel抽象类继承…
阅读更多...
大数据-68 Kafka 高级特性 物理存储 日志存储概述

大数据-68 Kafka 高级特性 物理存储 日志存储概述

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…
阅读更多...
Java之SpringBoot入门(含Spring Mvc)

Java之SpringBoot入门(含Spring Mvc)

1.Spring Boot Helper的安装 首先我们要装好Spring Boot Helper 但是由于直接在IDEA中下的是收费版&#xff0c;在学习阶段我们可以去官网下载一些免费版使用 Spring Boot Helper - IntelliJ IDEs Plugin | Marketplace&#xff08;点击即可进入官网&#xff09; 然后在IDEA…
阅读更多...
【practise】删除有序数组中的重复项

【practise】删除有序数组中的重复项

关于博主&#xff1a; 今天分享一道简单的关于“双指针”算法的题目。算是双指针中非常基础的题目&#xff0c;有兴趣可以借鉴一波~ 目录 1.题目介绍2.题解思路&#xff1a;双指针法3.代码示例 1.题目介绍 题目链接&#xff1a;LINK 本题要求是&#xff1a;对给定的有序数组…
阅读更多...
回溯分割+子集篇--代码随想录算法训练营第二十二天| 131.分割回文串，93.复原IP地址，78.子集，90.子集II

回溯分割+子集篇--代码随想录算法训练营第二十二天| 131.分割回文串，93.复原IP地址，78.子集，90.子集II

131.分割回文串 题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 讲解视频&#xff1a;131.分割回文串 题目描述&#xff1a; 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是回文串 。返回 s 所有可能的分割方案。 示例 …
阅读更多...
sql二次注入实战--2018年网顶杯

sql二次注入实战--2018年网顶杯

网址&#xff1a;BUUCTF在线评测 (buuoj.cn) 当我们进入后显示这个页面&#xff1a; 当我们第一次点击发帖的时候就会跳转到登陆页面&#xff0c;上面有提示&#xff0c;告诉我们账号为zhangwei,密码为zhangwei***&#xff1a; 这里我们可以使用bp抓包工具来进行暴力破解密码&…
阅读更多...
makefile举例说明

makefile举例说明

文章目录 makefile文件config.mk配置文件common.mk文件 目录结构 makefile文件 include config.mk导入config.mk的文件&#xff0c;通常包含项目的配置变量。 all:for dir in $(BUILD_DIR); \do \make -C $$dir; \doneall是项目主目标&#xff0c;遍历BUILD_DIR变量每个子目录…
阅读更多...
基于springboot+vue+uniapp的“口腔助手”小程序

基于springboot+vue+uniapp的“口腔助手”小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…
阅读更多...
Python开发： 飞机大战 小游戏

Python开发： 飞机大战 小游戏

玩法 你可以控制飞机左右移动&#xff0c;躲避敌机子弹&#xff0c;同时发射自己的炮弹&#xff0c;将敌人击落&#xff01; 部署方案&#xff1a; 1、代码如下图&#xff1b; 2、将代码保存到一个python中&#xff0c;比如planeFight.py&#xff1b; 3、在你的电脑中安装p…
阅读更多...
为什么需要云仓？

为什么需要云仓？

云仓&#xff0c;即云端仓储管理&#xff0c;是指通过互联网技术整合和管理仓储资源&#xff0c;实现高效、低成本的库存管理和物流服务。随着电子商务的发展和企业供应链全球化的加剧&#xff0c;云仓成为现代企业管理的一种重要手段。 1、云仓可以显著提高仓储管理效率&#…
阅读更多...
算法测试.

算法测试.

一.CodeForces 1829A 题意&#xff1a; 题目意思就是给你t个字符串&#xff0c;让你找出每个串与codeforces这个串有多少不同的字母&#xff1b; 题解&#xff1a; 定义一个变量循环比较字符串&#xff0c;不相同计数即可&#xff1b; 代码&#xff1a; #include <iost…
阅读更多...
SQL二次注入

SQL二次注入

目录 1.什么是二次注入&#xff1f; 2.二次注入过程 2.1寻找注入点 2.2注册admin#用户 2.3修改密码 1.什么是二次注入&#xff1f; 当用户提交的恶意数据被存入数据库后&#xff0c;因为被过滤函数过滤掉了&#xff0c;所以无法生效&#xff0c;但应用程序在从数据库中拿…
阅读更多...
TCP Analysis Flags 之 TCP Window Full

TCP Analysis Flags 之 TCP Window Full

前言 默认情况下&#xff0c;Wireshark 的 TCP 解析器会跟踪每个 TCP 会话的状态&#xff0c;并在检测到问题或潜在问题时提供额外的信息。在第一次打开捕获文件时&#xff0c;会对每个 TCP 数据包进行一次分析&#xff0c;数据包按照它们在数据包列表中出现的顺序进行处理。可…
阅读更多...
supermap制作发布二三维地图服务

supermap制作发布二三维地图服务

一、下载安装 软件版本&#xff1a; SuperMap iDesktopX 11i(2023) SP1 for Windows SuperMap iServer 11i(2023) SP1 for Windows 下载地址&#xff1a; http://support.supermap.com.cn/DownloadCenter/ProductPlatform.aspx 二、运行 服务端&#xff1a;双击iserver的…
阅读更多...
C# Unity 面向对象补全计划 设计者模式 之 单例模式

C# Unity 面向对象补全计划 设计者模式 之 单例模式

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列作为七大原则和设计模式的进阶知识&#xff0c;看不懂没关系 了解我的专栏C#面向对象与进阶:http://t.csdnimg.cn/mIitr&#xff0c;尤其是关于类的那篇文章即…
阅读更多...
Python（模块---pandas+matplotlib+pyecharts）

Python（模块---pandas+matplotlib+pyecharts）

import pandas as pd import matplotlib.pyplot as plt dfpd.read_excel(简易数据.xlsx) # print(df) plt.rcParams[font.sans-serif][SimHei] #设置画布的大小 plt.figure(figsize(10,6)) labelsdf[电影中文名] ydf[国籍] # print(labels) # print(y)# import pandas as pd im…
阅读更多...
在Stable Diffusion中驱动Tesla P40

在Stable Diffusion中驱动Tesla P40

一、安装P40显卡 在前面我的“在win10电脑上搭建python环境下的本地AI绘画工具Stable Diffusion”博文中&#xff0c;Stable Diffusion的运行完全依赖CPU和内存&#xff0c;因此每生成一次图片&#xff0c;需几小时之多&#xff0c;我常是在临下班时开始生成&#xff0c;到第二…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023