C++初阶：反向迭代器模板，dequeue与模板进阶

目录

  • 1. 反向迭代器的实现
  • 2. 容器deque的数据结构（双端队列）
  • 3. 模板的进阶知识与使用
    • 3.1 非类型模板参数
    • 3.2 模板特化
      • 3.2.1 全特化
      • 3.2.2 偏特化（半特化）
    • 3.3 模板的分离编译

1. 反向迭代器的实现

  1. 反向迭代器与正向迭代器的行为与定义方式存在很大程度上的雷同，只是细节上略有不同。我可以通过适配器的方式，对容器的正向迭代器进行封装调用来实现反向迭代器的功能。
  2. 使用适配器的方式创建反向迭代器，是在所有容器迭代器对外接口都相同，即行为相同的前提条件下才能够实现的。
  3. 以适配器的方式实现反向迭代器，只要传递对应容器的迭代器类型就会适配出相应的反向迭代器。

1. 反向迭代器的结构与定义
在这里插入图片描述

template<class iterator, class Ref, class Ptr>
struct reverse_iterator
{
	typedef reverse_iterator<iterator, Ref, Ptr> self;

	iterator cur;
	
	//正向迭代器没有默认构造，需要传值对其进行构造
	//构造
	reverse_iterator(const iterator& it)
		:cur(it)
	{}
}
  1. 模板参数作用：
    <1> iterator：各种容器的迭代器
    <2> Ref：区分普通迭代器与const迭代器的解引用运算符重载返回值不同
    <3> Ptr：区分operator->返回的地址能否被修改
  2. 将类定义为struct，默认为其内部资源的访问权限都为public

2. 反向迭代器的++与–

//前置++
self& operator++()
{
	//反向迭代器与正向迭代器的行为相反
	--cur;
	
	//返回调整后
	return *this;
}

//后置++
self operator++(int)
{
	//构造一个中间变量
	self tmp(cur);
	--cur;
	
	return tmp;
}

//前置--
self& operator--()
{
	++cur;
	
	return *this;
}

self operator--()
{
	self tmp(cur);

	return tmp;
}

2. 逻辑比较，解引用运算符重载与operator->

//两个反向迭代器进行判断，实则调用其内部正向迭代器逻辑比较方法
bool operator!=(const reverse_iterator& rit)
{
	return cur != rit.cur;
}

bool operator==(const reverse_iterator& rit)
{
	return cur == rit.cur;
}

//operator*运算符重载，返回迭代器指向的数据
Ref operator*()
{
	//赋值运算重载为默认成员函数，所以不必担心传递的容器有没有支持
	//又因为迭代器的底层都是指针，不会有深拷贝的情况存在，所以可以直接使用默认的赋值
	iterator tmp = cur;

	return *--tmp;
}

//返回迭代器指向元素数据的地址
Ptr operator->()
{
	//iterator tmp = cur;
	//return &(*--tmp);

	//复用反向迭代器的解引用操作符重载，得到迭代器指向的元素
	return &(operator());
}

2. 容器deque的数据结构（双端队列）

  1. 在STL库中实现的容器stack，queue这两个数据结构，其模板参数中的容器类型参数，默认缺省为一种我们还未学习过的数据结构deque。
  2. 为什么库中实现的栈与队列要默认调用这种数据结构容器而不是原有的list，vector，接下来就让我们来进行逐步的分析与学习。

1. stack与queue数据结构的特性

  1. 栈：后进先出，频繁尾插尾删
  2. 队列：先进先出，频繁尾插头删
  3. 综上所属，因为这两种数据结构的特性，所以在容器选择上我们无疑要选择头部插入删除，与尾部插入删除效率最优的数据结构。

2. vector与list的优缺点

  1. 容器vector，底层数据结构为顺序表，其底层物理结构是连续的。
    优点：
    <1> 下标随机访问的效率极高
    <2> 缓存命中率高
    <3> 尾插尾删效率高
    缺点：
    <1> 扩容消耗大
    <2> 随机插入删除效率低
  2. 容器list，底层数据结构为带头双向循环链表，其底层物理结构为碎片化的空间。
    优点：
    <1> 任意位置的插入删除操作效率高
    <2> 不存在扩容消耗
    缺点：
    <1> 不支持下标访问
    <2> 访问，缓存命中率低

3. deque的底层数据结构

  1. 顺序表与链表这两种数据结构它们的优缺点互补，其中顺序表可以适配栈频繁尾插尾删的需要，而链表可以满足频繁队列频繁尾插头删的需要。
  2. 虽然以上两个基础的数据结构可以分别适配于栈于队列的功能需要，但不可否的是，这两种基础数据结构在拥有一方面性能极值的同时，另一面也导致它们的缺陷十分明显。
  3. 那么，有没有一种数据可以继承它们两者优点的同时一定程度的规避它们二者的缺点呢，接下来，我们就来对deque这种汲两者之长，避二者之短数据结构的了解性学习。

在这里插入图片描述

  1. deque（双端队列），这一数据结构的物理逻辑结构大致如上图，其由数据结点与中控指针数组组成。
    <1> 数据结点：deque的数据结点并不像链表一样只能够存储一个数据结点，其的每一个数据结点都是具有一定长度的连续物理空间。
    <2> 中控指针数组：此数组中记录着每一个数据结点的首元素地址，从前至后。

2. deque的数据存储，插入，删除与扩容

  1. deque的常用支持接口：
    <1> push_back
    <2> pop_back
    <3> push_front
    <4> pop_front
    <5> insert
    <6> operator[]
  2. 从上述deque支持的常用接口可以看出，这种数据结构在支持随机的插入删除的同时，又支持[]的访问方式，下面就让我们了解一下这几个接口的内部实现原理与效率。
  3. 头插：deque的头插方式在不同的情境下会有不同的策略
    <1> 当前数据结点已满时，其会新开辟一块空间，而后在这块新开辟空间的尾部插入数据，中控数组向前增加一个指针，此指针指向新空间
    <2> 当前数据结点在前方空间有空余则直接在前方插入
    <3> 补充：中控数组中存储的指针不是从数组首部开始的，其会在数组中部开始存储，当中控数组被装满后，也会进行扩容

在这里插入图片描述

  1. operator[]运算符重载：deque支持下标访问的方式根据不同平台实现这一数据结构的细节的不同而不同，当其每一个数据结点的大小一致时，deque下标就可以通过计算公式直接得出。
  2. 示例：当deque的数据结点长度为10，设要访问的下标为n
    <1> n / 10，直至n的值等于0，此时计算n进行除运算的次数i，n下标表示的元素就在第i各数据结点中，控制指针从从第一个元素向后挪移（i - 1）步。
    <2> n % 10，得到n于所在数据结点中的相对下标，通过这一数据结点的首地址与相对下标即可拿到对应下标的元素。
    上述计算过程的效率并不算低，堪称高效，略逊与vector
  1. 随机删除：当需要随机删除时，这一数据结构就显不够优秀。
    <1> 当确定每个数据结点的空间大小相同，删除时就要挪动数据，效率相对很低
    <2> 当可以调整每个数据结点的空间大小时，进行删除的操作就可以通过对数据结点缩容来解决，相对挪动数据的消耗大大降低
    <3> 可以如果每个数据结点空间大小不同，那么下标访问的操作上就会更加复杂，拉低效率，需要中控数组的每个元素除开记录数据结点的地址外，还要记录每个数据结点的长度
    <4> 总的来说，deque的结构设计上下标访问与随机删除的效率无法同时兼顾

deque的迭代器与遍历方式

  1. deque的迭代器是一个自定类型，其由四个指针组成：
    <1> first：指向一个数据结点的开始
    <2> last：指向一个数据结点的结束
    <3> cur：指向遍历到的数据
    <4> node：指向数据结点对应中控数据的指针

在这里插入图片描述

  1. deque迭代器的遍历方式：
    <1> first指向要遍历的数据结点的开始，last执行要遍历数据结点的结束，cur从first的位置开始，遍历至last结束。
    <2> node指针++，调整first，last与cur，重复上述步骤，直至遍历完成所有数据结点。

3. 模板的进阶知识与使用

3.1 非类型模板参数

  1. 当想要定义一个容量不同的静态栈容器模板时，会发现根据现有的知识我们无法做到，这里引入一些模板相关进阶知识的补充。
  2. 函数的参数是变量，而模板的参数就是类型，正是模板可以将类型作为参数的特性，才使得我们可以通过传递不同类型给模板而得到对应数据结构的容器，那么模板参数除开数据类型外，还可以传递其他参数吗
  3. 非类型模板参数：模板中还存在着一种非类型模板参数，其参数类型为整形类型且仅能是整形，具体定义与使用方式，如下：
//定义方式：类型名 + 变量名
//可以给缺省
template<class T, size_t N = 10>
class Stack
{
public:
	void Print()
	{
		cout << sizeof(arr) / sizeof(arr[0]) << endl;
	}

private:
//在类中可以直接调用，当作整形常量来使用，宏常量
	int arr[N];
};

int main()
{
//使用时，同样需要给定值
	Stack<char> st1;
	Stack<char, 20> st2;
	
	st1.Print();
	st2.Print();

	return 0;
}
  1. 补充：
    <1> 容器array，对标普通数组，除有比普通数组更严格的越界检查无有不同
    <2> 容器forward_list，单链表

3.2 模板特化

3.2.1 全特化

  1. 特化，正如其名，是对特殊化情况的特殊化处理。
  2. 模板的全特化就是将会出现特殊情况提前列出，并给出对应的特殊化处理方式，具体情况如下：
//正常情况下的模板
template <class T>
struct Less
{
	bool operator()(T left, T right)
	{
		return left < right;
	}
};
//特殊情况下的模板
//语法如下：声明处的模板参数为空，具体定义处给出确定的参数类型，与具体的处理方法
template <>
struct Less<Date*>
{
	bool operator()(Date* left, Date* right)
	{
		return *left < *right;
	}
};
  1. 模板特化的处理方式，使得Date指针类型的数据进行比较会返回Date类型数据比较的结果。

3.2.2 偏特化（半特化）

  1. 偏特化与全特化没有本质上的区别：
    <1> 只是全特化对于指定的特殊模板参数很明确很具体
    <2> 而偏特化只是做出了部分限制，与大致上的区分

应用场景1：（不常用）

template<class T1, class T2>
class Demo
{
public:
	void Print()
	{
		cout << "class Demo(T1, T2)" << endl;
	}
};

template<class T2>
class Demo<int, T2>
{
public:
	void Print()
	{
		cout << "class Demo(T1, int)" << endl;
	}
};

int main()
{
	Demo<char, char> d1;
	Demo<int, char> d2;
	Demo<int, int> d3;
	
	//正常模板
	d1.Print();
	//特化模板
	d2.Print();
	//特化模板
	d3.Print();

	return 0;
}

应用场景2：（常用）

template<class T1, class T2>
class Demo
{
public:
	void Print()
	{
		cout << "class Demo(T1, T2)" << endl;
	}
};

template<class T1, class T2>
class Demo<T1*, T2*>
{
public:
	void Print()
	{
		cout << "class Demo(T1*, T2*)" << endl;
	}
};

int main()
{
	Demo<int, int> d1;
	Demo<int*, int> d2;
	Demo<int*, int*> d3;
	
	//正常模板
	d1.Print();
	//正常模板
	d2.Print();
	//特化模板
	d3.Print();

	return 0;
}
  1. 只做一类限制，限制所有的原生指针类型的参数使用偏特化。
  2. 模板的调用次序：全特化 -> 偏特化 -> 原模板

3.3 模板的分离编译

  1. 多文件项目的编译方式：

在这里插入图片描述

  1. 从上图多文件的编译方式可以看出，各个文件在最后一步链接之前是独立编译的，而模板并不是函数，不是已完成的代码，需要根据所给出的指定类型进行实例化。
  2. 当我们将模板的声明与定义分离后，预处理时的头文件展开中就不会包含模板的实现方法，而在编译的过程中，调用模板示例化的步骤就会因为缺失必要的类型信息无法进行。
  3. func.cpp文件包含有模板的实现方法缺少类型信息，test.cpp文件包含有类型信息却缺少实现方法。
  4. 在编译过程中，如果本文件所需要的资源在其他文件，编译时各个文件进行对其他文件进行扫描寻找资源，这样的编译方式是效率极其低下的。

补充1：编译器编译优化，文件生成动态库与模板声明定义分离的方式

  1. 经过上面的了解后，难道模板真的没有任何办法可以做到声明与定义分离吗，事实并非如此，我可以通过在模板定义的文件中提前加入对应的显示调用，即提前给出模板参数的类型。具体使用与定义方法，如下：
//Add.h
//声明
template<class T>
T Add(const T& left, const T& right);

//Add.cpp
//显示实例化
template
int Add<int>(const int& left, const int& right);
//定义
template<class T>
T Add(const T& left, const T& right)
{
	return left + right;
}
  1. 显示实例化的方式虽然可以达到模板定义与分离的效果，可是此种方法并不推荐使用，需要对每种可能出现的类型都进行显示实例化。
  1. 编译器在编译项目时，往往第一次编译的速度较慢，而后续再次编译同一文件时，速度就会非常快速几乎不会耗费时间，这是为什么呢。
  2. 当每个项目初次被编译后，得到的可执行程序并不会立即销毁，而是会被编译器存放到一个文件动态库中，当下次再此编译调度项目时，若是文件没有更新就会直接调用库中已有的可执行程序，这种方法使得编译的编译效率大大得到了优化。
  3. 检测一个二次编译项目是否需要编译，编译器会对照可执行程序的生成时间与文件的修改时间，若修改时间先于前者则会直接调用，若后于前者最会编译调整对应的修改部分更新动态库，而后再调用。
  4. 补充：头文件中同时拥有声明与定义时，文件后缀可以声明为.hpp，C++文件的后缀也可以时.cc

补充2：模板的优缺点

  1. 优点：因为模板复用的方式，大大调高了代码的灵活性与编写效率
  2. 缺点：编译报错时，报错信息凌乱不易定位

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C++中的STL(未完成)】

【C++中的STL(未完成)】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#xff1a;…
阅读更多...
java 8 stream api将List＜T＞转换成树形结构

java 8 stream api将List＜T＞转换成树形结构

1、新建实体类 package com.example.springboot3.entity;import lombok.Builder; import lombok.Data;import java.util.List;Data Builder public class Menu {/*** id*/public Integer id;/*** 名称*/public String name;/*** 父id &#xff0c;根节点为0*/public Integer p…
阅读更多...
vue3+threejs新手从零开发卡牌游戏（十七）：模拟对方手牌上场

vue3+threejs新手从零开发卡牌游戏（十七）：模拟对方手牌上场

写一个模拟对方手牌上场的事件&#xff0c;其中注意上场后卡牌需要翻转下&#xff0c;同时调整攻击力文字位置&#xff0c;主要代码如下&#xff1a; utils/common.ts&#xff1a; import { nextTick } from vue; import * as THREE from three; import * as TWEEN from tween…
阅读更多...
【Java程序设计】【C00377】基于（JavaWeb）Springboot的社区医疗服务系统（有论文）

【Java程序设计】【C00377】基于（JavaWeb）Springboot的社区医疗服务系统（有论文）

【C00377】基于&#xff08;JavaWeb&#xff09;Springboot的社区医疗服务系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#x…
阅读更多...
javaSSM公司招聘管理系统IDEA开发mysql数据库web结构计算机java编程maven项目

javaSSM公司招聘管理系统IDEA开发mysql数据库web结构计算机java编程maven项目

一、源码特点 IDEA开发SSM公司招聘管理系统是一套完善的完整企业内部系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;MAVEN方式加 载&#xff0c;系统具有完整的源代码和…
阅读更多...
极端道路天气数据集 雨天 雾天 道路晴朗

极端道路天气数据集 雨天 雾天 道路晴朗

极端道路天气数据集 是一系列专为自动驾驶、智能交通系统研发以及计算机视觉算法测试而设计的真实世界或模拟的道路环境图像和视频集合。这些数据集包含了在各类极端天气条件下捕捉到的道路场景&#xff0c;例如大雾、暴雨、暴雪、冰雹、雾霾、道路结冰等&#xff0c;这些都是…
阅读更多...
Vue3 + Vite + TS + Element-Plus + Pinia创建新项目(1)

Vue3 + Vite + TS + Element-Plus + Pinia创建新项目(1)

1、cmd进入命令行后&#xff0c;输入npm create vite 2、使用vs code打开文件夹 3、在VS Code的终端里面输入命令&#xff1a;npm i 安装依赖 4、安装依赖库 npm i vue-router 路由安装 npm i pinia 全局状态管理 npm i axios 请求库 npm i element-p…
阅读更多...
30---SDRAM电路设计

30---SDRAM电路设计

视频链接 SDRAM电路设计01_哔哩哔哩_bilibili SDRAM电路设计 1、SDRAM简介 SDRAM&#xff1a;Synchronous Dynamic Random Access Memory&#xff0c;同步动态随机存储器。 同步是指其时钟频率和CPU前端总线的系统时钟相同&#xff0c;并且内部命令的发送与数据的传输都以…
阅读更多...
国内ip切换app，让切换ip变得简单

国内ip切换app，让切换ip变得简单

在数字化快速发展的今天&#xff0c;互联网已经成为我们生活中不可或缺的一部分。然而&#xff0c;随着网络应用的深入&#xff0c;用户对于网络环境的需求也日益多样化。其中&#xff0c;IP地址作为网络中的关键标识&#xff0c;其切换与管理显得尤为重要。为了满足用户对于IP…
阅读更多...
推荐5款测试数据生成工具！

推荐5款测试数据生成工具！

一个成功、有效的测试策略由下面几个基本部分组成&#xff1a;完整的测试覆盖率、最小化的环境影响和健壮的测试数据。 其中测试数据尤其重要&#xff0c;其质量直接关系到测试的有效性。可以把测试数据看作是保持测试引擎运行的燃料——高质量的测试数据有助于确保测试执行的…
阅读更多...
气体放电的基本物理过程

气体放电的基本物理过程

本篇为本科课程《高电压工程基础》的笔记。 和固体液体介质相比&#xff0c;气体绝缘有不老化的有点&#xff0c;而且击穿后具有完全的绝缘自恢复特性&#xff0c;是绝缘部分的重点。 带电质点的产生与消失 中性气体不到点&#xff0c;但是由于宇宙射线和地壳中的放射性物质…
阅读更多...
【鸿蒙HarmonyOS开发笔记】使用@Preview装饰器预览组件

【鸿蒙HarmonyOS开发笔记】使用@Preview装饰器预览组件

概述 ArkTS应用/服务支持组件预览&#xff0c;要求compileSdkVersion为8或以上。组件预览支持实时预览&#xff0c;不支持动态图和动态预览。组件预览通过在组件前添加注解Preview实现&#xff0c;在单个源文件中&#xff0c;最多可以使用10个Preview装饰自定义组件。 Preview…
阅读更多...
NIO与AIO

NIO与AIO

NIO与AIO NIO模型 在 LInux 环境中&#xff0c;java.nio.channels.Selector 的子类叫做 sun.nio.ch.EPollSelectorImpl &#xff0c;其底 层是基于 Epoll 模型去实现的 IO 多路复用器。 对于 Epoll 模型 我们需要了解到它底层的三个函数 在 JDK 实现的底层中&#xff0c;EPol…
阅读更多...
由浅到深认识Java语言（27）：异常

由浅到深认识Java语言（27）：异常

该文章Github地址&#xff1a;https://github.com/AntonyCheng/java-notes 在此介绍一下作者开源的SpringBoot项目初始化模板&#xff08;Github仓库地址&#xff1a;https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址&#xff1a;https://blog.c…
阅读更多...
mysql如何存Emoji表情

mysql如何存Emoji表情

如何存Emoji表情 背景解决方案一&#xff1a; 如果是自己搭建的数据库&#xff0c;参考如下。 1&#xff1a;先创建数据库&#xff0c;utf8编码2&#xff1a; 修改mysql 的配置文件 /etc/my.cnf 文件3&#xff1a;然后把你的表和字段也要支持utf8md4编码4&#xff1a;修改你连…
阅读更多...
分页功能制作

分页功能制作

使用HTML&#xff0c;css&#xff0c;js和json假数据制作分页功能。 以下为分页功能结构&#xff0c;下面可以点击上一页&#xff0c;下一页及数字&#xff0c;还可以自己输入想要跳转的页面点击跳转。下面每页显示的内容也会跟着改变。还可以选择不同的每页显示数据的条数。默…
阅读更多...
备考ICA----Istio实验11---为多个主机配置TLS Istio Ingress Gateway实验

备考ICA----Istio实验11---为多个主机配置TLS Istio Ingress Gateway实验

备考ICA----Istio实验11—为多个主机配置TLS Istio Ingress Gateway实验 1. 部署应用 kubectl apply -f istio/samples/helloworld/helloworld.yaml -l servicehelloworld kubectl apply -f istio/samples/helloworld/helloworld.yaml -l versionv12. 证书准备 接上一个实验…
阅读更多...
【孙子级介绍语言模型的原理，实战和评估】

【孙子级介绍语言模型的原理，实战和评估】

&#x1f525;博主&#xff1a;程序员不想YY啊&#x1f525; &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家&#x1f4ab; &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 &#x1f308;希望本文对您有所裨益&#xff0c;如有…
阅读更多...
超级爆火项目 壁纸取图小程序源码系统 带完整的安装代码包以及安装部署教程

超级爆火项目 壁纸取图小程序源码系统 带完整的安装代码包以及安装部署教程

在当今数字化时代&#xff0c;手机壁纸已经成为人们展示个性和品味的重要载体。为了满足广大用户对精美壁纸的需求&#xff0c;小编给大家分享一款超级爆火的“壁纸取图小程序源码系统”。该系统不仅提供了完整的安装代码包&#xff0c;还附带了详尽的安装部署教程&#xff0c;…
阅读更多...
2024大广赛设计趋势揭秘：助你称霸比赛！

2024大广赛设计趋势揭秘：助你称霸比赛！

2024大广赛火热进行中&#xff0c;今天就与大家分享几个当下最流行的设计趋势&#xff0c;希望这些流行的设计趋势助你一举夺魁&#xff0c;他们是适老化设计、电商类设计、车机主题设计与游戏类主题设计&#xff0c;大赛当前&#xff0c;不看说不过去哦~ 适老化设计 适老化设…
阅读更多...
最新文章

Copyright @ 2022~2023