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

news/2024/11/14 12:43:21/

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.ppmy.cn/news/1505627.html

相关文章

Mysql基础知识总结

Mysql基础知识总结

​⭐️⭐️SQL执行顺序 Sql语句在数据库中的执行流程 &#x1f4e6; 系统&#xff08;客户端&#xff09;访问 MySQL 服务器前&#xff0c;做 的第一件事就是建立 TCP 连接。 Caches & Buffers&#xff1a; 查询缓存组件 SQL Interface: SQL接口 接收用户的SQL命 令&…
阅读更多...
PDF——分割pdf的10个工具

PDF——分割pdf的10个工具

PDF分割器是一种可用于将PDF文档分割成更小的文档甚至单个页面的工具。分割 PDF 文档的主要原因是为了更容易共享。 但该过程的成功取决于您用于拆分 PDF 的工具。较简单的工具仅提供几个选项&#xff0c;可能并不适合所有类型的文档。我们将在本文中列出的 10 个最佳 PDF 分割…
阅读更多...
部署Springboot + Vue 项目到远程服务器Windows10系统的详细配置

部署Springboot + Vue 项目到远程服务器Windows10系统的详细配置

远程服务器操作系统为Windows系统&#xff0c;Java程序环境&#xff0c;Maven环境都安装有&#xff0c;Mysql ,Redis等都有的前提下 1. mysql数据库导入&#xff0c;非常简单很好操作&#xff0c;这里省略。。比如用HeidiSql 或者Navicat 工具导入数据库 2. 后端javaSpringb…
阅读更多...
c#设置触控屏触控自动映射到扩展屏

c#设置触控屏触控自动映射到扩展屏

概要 在大多数系统中，触摸屏和触控笔的使用并不常见，相关的解决方案也较少。在Windows系统中，触摸屏和触控笔通常通过USB连接，并默认映射到主屏幕。如果没有进行额外设置，以下两种场景可能导致问题： 主屏幕为非触控屏幕，扩展屏幕为触控屏幕，导致在扩展屏上的操作实际影…
阅读更多...
在没有硬盘的情况下进行电脑数据迁移

在没有硬盘的情况下进行电脑数据迁移

电脑数据迁移方式 在更换电脑的时候需要进行文件的传输&#xff0c;但是没有硬盘可以选择使用网线直连或者无线文件共享。通用配置 1.将旧电脑的文件夹或者磁盘设置文件共享 找到指定的文件夹右键属》属性&#xff0c;点击共享》点击高级共享 选择共享文件夹以及修改共享用户…
阅读更多...
基于Docker的Redis安装

基于Docker的Redis安装

一、搜索镜像 通过docker 搜索 redis 镜像文件 docker search redis二、下载镜像 通过docker images 查看下载下来的redis镜像&#xff0c;默认下载最新的版本 docker pull redis三、配置挂载文件 创建本地与docker映射的目录&#xff0c;即本地存放的位置 创建本地存放re…
阅读更多...
Flink-DataWorks第二部分：数据集成（第58天）

Flink-DataWorks第二部分：数据集成（第58天）

系列文章目录 数据集成 2.1 概述 2.1.1 离线&#xff08;批量&#xff09;同步简介 2.1.2 实时同步简介 2.1.3 全增量同步任务简介 2.2 支持的数据源及同步方案 2.3 创建和管理数据源 文章目录 系列文章目录前言2. 数据集成2.1 概述2.1.1 离线&#xff08;批量&#xff09;同步…
阅读更多...
C++详解-＞函数模板+类模版

C++详解-＞函数模板+类模版

文章目录 前言1、反泛型编程2、函数模板(1)、函数模板概念(2)、函数模板定义格式(3)、函数模板实例化(4)函数模板参数匹配原则 3、类模版(1)类模板实例化(2)类模板实现Stack&#xff08;压/出栈函数&#xff09; 前言 此篇主要描述函数模板的概念、格式以及实例化等&#xff1b…
阅读更多...
最新文章

Copyright @ 2022~2023