当前位置：首页 > news >正文

C++ Primer 泛型算法结构

news 来源：原创 2025/9/14 4:42:51

欢迎阅读我的【C++Primer】专栏

专栏简介：本专栏主要面向C++初学者，解释C++的一些基本概念和基础语言特性，涉及C++标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级程序设计技术。希望对读者有帮助！

在这里插入图片描述

10.5 泛型算法结构

任何算法的最基本的特性是它要求其迭代器提供哪些操作。某些算法,如find,只要求通过迭代器访问元素、递增迭代器以及比较两个迭代器是否相等这些能力。其他一些算法,如sort,还要求读、写和随机访问元素的能力。算法所要求的迭代器操作可以分为5个迭代器类别(iterator category),如表10.5所示。每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。

表10.5:迭代器类别


输入迭代器	只读,不写;单遍扫描,只能递增
输出迭代器	只写,不读;单遍扫描,只能递增
前向迭代器	读写;多道扫描,只能递增
双向迭代器	多遍扫描,可递增递减
随机访问迭代器	可读写,多遍扫描,支持全部迭代器运算

第二种算法分类的方式(如我们在本章开始所做的是按照是否读、写或是重排序列中的元素来分类。附录A按这种分类方法列出了所有算法。

算法还共享一组参数传递规范和一组命名规范,我们在介绍迭代器类别之后将介绍这些内容。

5类迭代器

类似容器,迭代器也定义了一组公共操作。一些操作所有迭代器都支持,另外一些只有特定类别的迭代器才支持。例如,ostream_iterator只支持递增、解引用和赋值。vector、string和deque的迭代器除了这些操作外,还支持递减、关系和算术运算。

迭代器是按它们所提供的操作来分类的,而这种分类形成了一种层次。除了输出迭代器之外,一个高层类别的迭代器支持低层类别迭代器的所有操作。

C++标准指明了泛型和数值算法的每个迭代器参数的最小类别。例如,find算法在-个序列上进行一遍扫描,对元素进行只读操作,因此至少需要输入迭代器。replace函数需要一对迭代器,至少是前向迭代器。类似的,replace_copy的前两个迭代器参数也要求至少是前向迭代器。其第三个迭代器表示目的位置,必须至少是输出迭代器。其他的例子类似。对每个迭代器参数来说,其能力必须与规定的最小类别至少相当。向算法传递一个能力更差的迭代器会产生错误。

对于向一个算法传错误类别的选代器的问题,很多编译器不会给出任何警告或提示

迭代器类别

输入迭代器(input iterator):可以读取序列中的元素。一个输入迭代器必须支持

用于比较两个迭代器的相等和不相等运算符(==、！=)
用于推进迭代器的前置和后置递增运算(++)
用于读取元素的解引用运算符(*);解引用只会出现在赋值运算符的右侧
箭头运算符(->),等价于*it).member,即,解引用迭代器,并提取对象的成员

输入迭代器只用于顺序访问。对于一个输入迭代器,*it++保证是有效的,但递增它可能导致所有其他指向流的选代器失效。其结果就是,不能保证输入迭代器的状态可以保存下来并用来访问元素因此,输入迭代器只能用于单道扫描算法.算法find和accumulate要求输入迭代器;而istream_itterator是一种输入迭代器。

输出迭代器(output iterator):可以看作输入迭代器功能上的补集一一只写而不读元素。输出迭代器必须支持

用于推进迭代器的前置和后置递增运算(++)
解引用运算符(*),只出现在赋值运算符的左侧(向一个已经解引用的输出迭代器赋值,就是将值写入它所指向的元素

我们只能向一个输出迭代器赋值一次。类似输入迭代器,输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。例如,copy函数的第三个参数就是输出迭代器。ostream_iterator类型也是输出迭代器。

前向迭代器(forward iterator):可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出选代器的操作,而且可以多次读写同一个元素。因此,我们可以保存前向迭代器的状态,使用前向迭代器的算法可以对序列进行多遍扫描。算法rep1ace要求前向选代器,forward_list上的迭代器是前向迭代器。

双向迭代器(bidirectional iterator):可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外,双向迭代器还支持前置和后置递减运算符(一)。算法reverse要求双向迭代器,除了forward_list之外,其他标准库都提供符合双向迭代器要求的迭代器。

随机访问迭代器(random-access iterator):提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能,此外还支持表3.7〔第99页)中的操作:

用于比较两个迭代器相对位置的关系运算符(C<、<=、>和>=)
迭代器和一个整数值的加减运算(+、+=、-和一),计算结果是迭代器在序列中前进(或后退)给定整数个元素后的位置
用于两个迭代器上的减法运算符(C-),得到两个迭代器的距离
下标运算符(iter[n1],与*(iter[n])等价

算法sort要求随机访问迭代器。array、deque、string和vector的迭代器都是随机访问迭代器,用于访问内置数组元素的指针也是。

算法形参模式

在任何其他算法分类之上,还有一组参数规范。理解这些参数规范对学习新算法很有帮助一一通过理解参数的含义,你可以将注意力集中在算法所做的操作上。大多数算法具有如下4种形式之一:

alg(beg,end,other args);
al8(beg,end,dest,other args);
alg(beg,end,beg2,orher args);
alg(beg,end,beg2,end2,other args);

其中alg是算法的名字,beg和end表示算法所操作的输入范围。几乎所有算法都接受一个输入范围,是否有其他参数依赖于要执行的操作。这里列出了常见的一种–dest、beg2和end2,都是迭代器参数。顾名思义,如果用到了这些迭代器参数,它们分别承担指定目的位置和第二个范围的角色。除了这些迭代器参数,一些算法还接受额外的、非迭代器的特定参数。

接受单个目标迭代器的算法

dest参数是一个表示算法可以写入的目的位置的迭代器。算法假定(assume):按其需要写入数据,不管写入多少个元素都是安全的。

如果dest是一个直接指向容器的迭代器,那么算法将输出数据写到容器中已存在的元素内。更常见的情况是,aest被绑定到一个插入迭代器或是一个ostream_iterator。插入迭代器会将新元素添加到容器中,因而保证空间是足够的。ostream_iterator会将数据写入到一个输出流,同样不管要写入多少个元素都没有问题。

接受第二个输入序列的算法

接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

如果一个算法接受beg2和end2,这两个迭代器表示第二个范围。这类算法接受两个完整指定的范围:[beg,end)表示的范围和[peg2end2)表示的第二个范围。

只接受单独的beg2(不接受end2)的算法将beg2作为第二个输入范围中的首元素。此范围的结束位置未指定,这些算法假定从beg2开始的范围与beg和end所表示的范围至少一样大。

接受单独beg2的算法假定从beg2开始的序列与beg和end所表示的范图少一样大。

算法命名规范

除了参数规范,算法还遮循一套命名和重载规范。这些规范处理诸如:如何提供一个操作代替默认的<或一运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。

一些算法使用重载形式传递一个谓词

接受谓词参数来代曼<或一运算符的算法,以及那些不接受额外参数的算法,通常都是重载的函数。函数的一个版本用元素类型的运算符来比较元素;另一个版本接受一个额外谓词参数,来代替<或一:

unique(pbeg,end);//使用==运算符比较元素
unique(peg,end,comp);//使用comp比较元素

两个调用都重新整理给定序列,将相邻的重复元素删除。第一个调用使用元素类型的一运算符来检查重复元素;第二个则调用comp来确定两个元素是否相等。由于两个版本的函数在参数个数上不相等,因此具体应该调用哪个版本不会产生歧义。

_if版本的算法
接受一个元素值的算法通常有另一个不同名的(不是重载的)版本,该版本接受一个谓词代替元素值。接受诸词参数的算法都有附加的_if前缀:

find(beg,end,val);//查找输入范图中val第一次出现的位置
find_if(beg,end,pred);//查找第一个令pred为真的元素

这两个算法都在输入范园中查找特定元素第一次出现的位置.算法find查找一个指定值:

算法find_if查找使得pred返回非零值的元素。

这两个算法提供了命名上差异的版本,而非重载版本,因为两个版本的算法都接受相同数目的参数。因此可能产生重载歧义,虽然很罕见,但为了避免任何可能的歧义,标准库选择提供不同名字的版本而不是重载。

区分拷贝元素的版本和不拷贝的版本

默认情况下,重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本,将元素写到一个指定的输出目的位置。如我们所见,写到额外目的守间的算法都在名字后面附加一个_copy:

reverse(pbeg,end);//反转输入范围中元素的顺序
reverse_copy(pegend,dest);//将元素按送序指贝到dest

-些算法同时提供_copy和_if版本。这些版本接受一个目的位置迭代器和一个谓词:

//从v1中删除奇数元素
remove_if(v1.begin(),v1.end(),
[](int i){return i%2});
//将偶数元交从v1拷贝到v2;v1不变
remove_copy_if(v1.begin(),v1.end(),back_inserter(v2),
[](int i){return i%2});

两个算法都调用了lambda来确定元素是否为奇数。在第一个调用中,我们从输入序列中将奇数元素删除。在第二个调用中,我们将非奇数(亦即偶数)元素从输入范围拷贝到v2中。

C++ Primer 泛型算法结构

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/9/14 4:42:51

java给钉钉邮箱发送邮件

1.开通POP和IMAP 2.引入pom <dependency><groupId>javax.mail</groupId><artifactId>mail</artifactId><version>1.4.7</version> </dependency>3.逻辑 String host "smtp.qiye.aliyun.com"; String port "…...

编程日记 2025/9/14 4:40:38

交安ABC-公路水运工程企业安全员ABC如何报名？报名要哪些条件？

交安ABC的报名方式及报名条件如下： 报名方式 1. 企业注册：企业要进入交通运输部公路水运工程施工主要负责人和安全生产管理人员信息管理系统，注册企业账户，提交企业相关信息，填写企业资料。 2. 发送审核&#xff…...

编程日记 2025/9/7 8:05:55

软件测试丨Docker与虚拟机架构对比分析

Docker 与虚拟机（VM）在架构上有显著区别，主要体现在资源利用、性能、隔离性和启动时间等方面。以下是两者的主要架构区别： 1. 架构层次 Docker: 主机操作系统：Docker 直接运行在宿主机的操作系统上。Docker 引擎&…...

编程日记 2025/9/14 4:16:53

Gatling介绍

Gatling：基于Scala的高性能负载测试工具一、Gatling 简介 Gatling 是一个开源的 HTTP 压力测试工具，专为高并发场景设计，支持 HTTP/HTTPS、WebSocket、Kafka 等协议。其基于 Scala 的脚本语法简洁高效，支持实时报告生成和分布式…...

编程日记 2025/9/14 4:26:17

Shot Studio for macOS 发布 1.0.2

Shot Studio 是一个 macOS 的 app，专门为开发者设计，主要用于各大 app 应用商店的预览图设计。提供了非常多的模板，也预设了很多尺寸。可以直接一键使用在 1.0.2 这个版本中新增了： 文本渐变图层：边框、颜色、圆…...

编程日记 2025/9/2 21:29:05

基于Spring Boot的乡村养老服务管理系统设计与实现（LW+源码+讲解）

专注于大学生项目实战开发,讲解,毕业答疑辅导，欢迎高校老师/同行前辈交流合作✌。技术范围：SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：…...

编程日记 2025/9/8 16:35:28

Harbor服务需要crt证书，而下载是nginx的证书pem，应该怎么处理

1. 明确文件用途 shgbitai.com.key：SSL 私钥文件（与 Apache/Nginx 通用）。shgbitai.com.pem：已合并的证书文件（通常包含域名证书中间证书链）。 Nginx 的证书通常以 .pem 或 .crt 为后缀，而 …...

编程日记 2025/9/11 21:09:07

Hadoop第一课（配置linux系统）

1、让hadoop用户，有root权限，如果可以不输密码更好： (1)先登入root用户 (2)visudo命令进入配置文件 (3)找到 root ALL(ALL) ALL这一行，在该行下面增加:hadoop ALL(ALL) ALL （：set nu可以显示行号&#xff…...

编程日记 2025/9/13 1:35:12

Java+Vue+uniapp微信小程序校园自助打印系统（程序+论文+讲解+安装+调试+售后）

感兴趣的可以先收藏起来，还有大家在毕设选题，项目以及论文编写等相关问题都可以给我留言咨询，我会一一回复，希望帮助更多的人。系统介绍在当今时代，网络与科学技术正以前所未有的速度迅猛发展，这股强大…...

编程日记 2025/9/13 18:59:25

QT 中的元对象系统(二)：元对象实现原理QMetaObject

目录 1.元对象系统的构成 2.QObject和QMetaObject的关系 3.Qt 元对象模型QMetaObject 3.1.基本信息 3.2.类信息classinfo 3.3.类构造函数constructor 3.4.枚举信息 enumerator 3.5.类方法method 3.6.类属性peoproty 4.MOS(Meta Object System)示例 5.总结 1.元对象系…...

编程日记 2025/9/11 14:57:02

C++:指针函数与函数指针

文章目录概述什么是指针函数（Pointer Function）什么是函数指针（Function Pointer）总结： 概述什么是指针函数（Pointer Function） 指针函数是指返回类型为指针的函数。即，函数返回…...

编程日记 2025/9/13 4:12:34

用HTML5+CSS+JavaScript实现新奇挂钟动画

用HTML5+CSS+JavaScript实现新奇挂钟动画引言在技术博客中，如何吸引粉丝并保持他们的关注？除了干货内容，独特的视觉效果也是关键。今天，我们将通过HTML5、CSS和JavaScript实现一个新奇挂钟动画，并将其嵌入到你的网站中。这个动画不仅能让你的网站脱颖而出，还能展示你的…...

编程日记 2025/8/28 1:49:50

【MySQL篇】表的操作

1，创建表语法： create table ( field1 datatype, field2 datatype, field3 datatype )charset 字符集 collate 校验规则 engine 存储引擎; 说明： field表示列名datatype表示列的类型charset字符集，如果没有指明，则…...

编程日记 2025/9/9 1:49:50

CCF-CSP历年真题大全附题解python

2023012的真题 202312-1 仓库规划 5415. 仓库规划 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/5418/ 解题思路： 其实就是对比（x.y,z.....）需要找到一个每个元素都大于这个坐标得坐标，本题可以直接…...

编程日记 2025/9/13 10:20:08

Mysql——约束与多表查询

一、约束 1.1定义约束是对表中的数据进行限制的一套规则，用于防止用户向数据库中输入无效数据。它可以保证表中的数据满足特定业务规则和逻辑，从而维护数据的准确性和可靠性。 1.2作用数据完整性 ：约束可以确保数据在插入、更新或删除时符…...

编程日记 2025/9/13 20:38:09

如何看待 Kaiming He 最新提出的 Fractal Generative Models ？

何恺明团队提出的分形生成模型（Fractal Generative Models）引发了广泛关注，其核心思想是通过递归调用生成模型模块构建自相似结构，类似数学中的分形概念（如雪花结构），从而高效生成高分辨率数据（如图像）。 Fractal Generative Models即分形生成模型，是一种新型的生成…...

编程日记 2025/9/11 21:48:32

【大模型系列篇】如何解决DeepSeek-R1结构化输出问题，使用PydanticAl和DeepSeek构建结构化Agent

今日号外：🔥🔥🔥 DeepSeek开源周：炸场！DeepSeek开源FlashMLA，提升GPU效率下面我们开始今天的主题，deepseek官方明确表示deepseek-r1目前不支持json输出/function call，可…...

编程日记 2025/9/9 10:49:13

Metal 学习笔记五：3D变换

在上一章中，您通过在 vertex 函数中计算position，来平移顶点和在屏幕上移动对象。但是，在 3D 空间中，您还想执行更多操作，例如旋转和缩放对象。您还需要一个场景内摄像机，以便您可以在场景中移动。要移动…...

编程日记 2025/9/13 9:59:33

Android-创建mipmap-anydpi-v26的Logo

利用 Android Studio 自动创建创建新项目：打开 Android Studio，点击 “Start a new Android Studio project” 创建新项目。在创建项目的过程中，当设置Target SDK Version为 26 或更高版本时，Android Studio 会在项目的res目录下…...

编程日记 2025/9/12 15:22:48

DOM 事件 HTML 标签属性速查手册

以下是一份 DOM 事件 & HTML 标签属性速查手册，涵盖常用场景和示例，助你快速查阅和使用： 一、DOM 事件速查表 1. 鼠标事件事件名触发时机适用元素示例代码click元素被点击任意可见元素button.addEventListener(click, () > { ... …...

编程日记 2025/9/8 15:07:22

差旅费控平台作用、功能、11款主流产品优劣势对比

本文将对比以下11款主流费控系统：合思、喜报销、泛微费控报销系统、经贝管家、每刻报销、SAP Concur、Expensify、Zoho Expense等。随着全球化和企业跨地区运营的不断发展，企业差旅管理已逐渐成为许多公司面临的管理挑战之一。从差旅申请到费用报销的全…...

编程日记 2025/9/12 7:28:33

常用的配置文件格式对比（ini，toml，yaml，json，env，settings.py）及应用程序修改自身配置并保留注释

代码与环境配置解耦 git分支的代码应做到“环境无关”：代码本身不硬编码任何环境特定的配置（如数据库连接、密钥、API地址），而是通过外部机制动态注入。配置与代码分离：将配置信息存储在代码库之外（如环…...

编程日记 2025/9/11 12:01:07

MySQL 存储过程详解

文章目录 1. 存储过程定义1.1 基本概念1.2 核心特点1.3 存储过程 vs 函数 2. 工作原理与示意图2.1 执行流程2.2 示意图 3. 使用场景3.1 复杂业务逻辑3.2 批量数据处理3.3 权限控制3.4 性能优化 4. 示例与说明4.1 基础示例：创建存储过程4.2 带输出参数的存储过程4.3 …...

编程日记 2025/9/10 22:24:26

使用DeepSeek/chatgpt等AI工具辅助网络协议流量数据包分析

随着deepseek,chatgpt等大模型的能力越来越强大，本文将介绍一下deepseek等LLM在分数流量数据包这方面的能力。为需要借助LLM等大模型辅助分析流量数据包的同学提供参考，也了解一下目前是否有必要继续学习wireshark工具以及复杂的协议知识。 pcap格式目…...

编程日记 2025/9/12 16:11:51

源码压缩包泄露

##解题思路因为网站的文件都放在www下面，所以直接访问/www.zip就可以得到网页的源码压缩包在fl000g.txt这个文件中看到一个flag{flag_here}不像是真的flag，尝试提交ctfshow{flag_here}，果然提交失败打开文件属性之类的，也没有…...

编程日记 2025/9/10 15:15:39

TCP/IP 5层协议簇：数据链路层（交换机工作原理）

目录 1. 数据链路层 2. 帧 3. 工作在数据链路层的设备 4. 交换机工作原理 1. 数据链路层数据链路层（2层Data Link Layer）：传输单元是帧、这层工作的主要设备二层交换机、网卡 2. 帧帧的结构如下：帧最大1518字节如下&…...

编程日记 2025/9/13 0:48:01

TCP/IP的分层结构、各层的典型协议，以及与ISO七层模型的差别

1. TCP/IP的分层结构 TCP/IP模型是一个四层模型，主要用于网络通信的设计和实现。它的分层结构如下： (1) 应用层（Application Layer） 功能：提供应用程序之间的通信服务，处理特定的应用细节。典型协议&am…...

编程日记 2025/9/11 12:24:18

【分布式理论11】分布式协同之分布式事务（一个应用操作多个资源）：从刚性事务到柔性事务的演进

文章目录一. 什么是分布式事务？二. 分布式事务的挑战三. 事务的ACID特性四. CAP理论与BASE理论1. CAP理论1.1. 三大特性1.2. 三者不能兼得 2. BASE理论五. 分布式事务解决方案1. 两阶段提交（2PC）2. TCC（Try-Confirm-Cancel&…...

编程日记 2025/9/11 1:00:23

Linux: 已占用接口

Linux: 已占用接口 1. netstat（适用于旧系统）1.1 书中对该命令的介绍 2. ss（适用于新系统，替代 netstat）3. lsof（查看详细进程信息）4. fuser（快速查找占用端口的进程）5. …...

编程日记 2025/9/10 19:34:35

HWUI 和 Skia

📌 HWUI 和 Skia 的关系 Skia 是 Android 的底层 2D 图形库，提供 CPU 和 GPU 渲染能力，支持 OpenGL、Vulkan、Metal 等后端。HWUI 是 Android UI 组件的 GPU 渲染引擎，主要用于加速 View、动画、阴影等 UI 元素的绘制。HWUI 依赖…...

编程日记 2025/9/11 14:09:56

Pytorch使用手册--将 PyTorch 模型导出为 ONNX（专题二十六）

注意截至 PyTorch 2.1，ONNX 导出器有两个版本。 torch.onnx.dynamo_export 是最新的（仍处于测试阶段）导出器，基于 PyTorch 2.0 发布的 TorchDynamo 技术。 torch.onnx.export 基于 TorchScript 后端，自 PyTorch 1.2.0 起可用。一、torch.onnx.dynamo_export使用在 60 …...

编程日记 2025/9/11 13:30:24

GitHub SSH连接问题解决指南

🔍 GitHub SSH连接问题解决指南问题描述遇到错误：ssh: connect to host github.com port 22: Connection refused 说明您的网络环境无法访问GitHub的SSH端口22，常见原因： 防火墙/网络运营商限制（国内常见&#xf…...

编程日记 2025/9/13 22:59:11

【Linux】vim 设置

【Linux】vim 设置零、起因刚学Linux，有时候会重装Linux系统，然后默认的vi不太好用，需要进行一些设置，本文简述如何配置一个好用的vim。壹、软件安装 sudo apt-get install vim贰、配置路径对所有用户生效： …...

编程日记 2025/9/10 15:24:48

2025届开发岗秋招经验教训总结

实习实习的作用： 学习知识，充实简历了解特定部门的氛围转正比秋招提前占坑提前展现工作能力，争取更高起薪其中，除非有梦中情组，我认为占坑是最不重要的一个，因为现在的校招就业形势并未严峻到转正占满…...

编程日记 2025/9/6 18:37:51

Java 之集成 DataX 数据同步工具

1、官网下载 DataX https://github.com/alibaba/DataX 2、将依赖添加到本地（DataX没有maven坐标，需要自己安装） mvn install:install-file -Dfile"datax-common-0.0.1.jar" "-DgroupIdcom.datax" "-DartifactIdda…...

编程日记 2025/9/10 16:30:04

JMH 详细使用

JMH 基本使用官方地址 JMH 是一个用于 Java 代码微基准测试的工具，允许开发者对特定部分进行精确的性能测试； 安装 JMH 环境： Maven 项目；JDK 8； Maven 方式安装引入如下依赖： <dependencies>…...

编程日记 2025/9/13 11:39:41

2025 PHP授权系统网站源码

2025 PHP授权系统网站源码安装教程： PHP7.0以上先上传源码到服务器，然后再配置伪静态， 访问域名根据操作完成安装， 然后配置伪静态规则。 Ngix伪静态规则： location / { if (!-e $request_filename) { rewrite …...

编程日记 2025/9/13 18:31:15

【对话推荐系统】Towards Topic-Guided Conversational Recommender System 论文阅读

Towards Topic-Guided Conversational Recommender System 论文阅读 Abstract1 Introduction2 Related Work2.1 Conversation System2.2 Conversational Recommender System2.3 Dataset for Conversational Recommendation 3 Dataset Construction3.1 Collecting Movies for Re…...

编程日记 2025/9/10 10:00:32

目录