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

STL算法之set相关算法

        STL一共提供了四种与set(集合)相关的算法,分别是并集(union)、交集(intersection)、差集(difference)、对称差集(symmetric difference)。

目录

set_union

set_itersection

set_difference

set_symmetric_difference


        所谓set,可细分为数学上定义的和STL的定义两种,数学上的set允许元素重复而未经排序,例如{1,1,4,6,3},STL的定义(也就是set容器)则要求元素不得重复,并且经过排序,例如{1,3,4,6}。本节的四个算法所接受的set,必须是有序区间(sorted range),元素值可重复出现。换句话说,它们可接受STL的set/multiset容器作为输入区间。

        SGI另外提供了hash_set/hash_multiset两种容器,以hashtable为底层机制。其内的元素并未呈现排序状态,所以虽然名称也是set字样,缺不可以应用于本节的四个算法。

        本节四个算法都至少有四个参数,分别表现两个set区间,以下所有说明都以S1代表第一区间[first1, last1),以S2代表第二区间[first2, last2).每一个set算法都提供两个版本,第二个版本允许用户指定"a<b"的意义,因为这些算法判断两个元素是否相等的依据,完全靠“小于”运算。

        a <b && b< a 推导出 a==b

        以下程序测试四个set相关算法。欲使用它们,必须包含<algorithm>

#include <set>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;template <class T>
struct display {void operator() (const T& x) {cout << x << " ";}
};int main() {int ia1[6] = {1, 3, 5, 7, 9, 11};int ia2[7] = {1, 1, 2, 3, 5, 8, 13};multiset<int> S1(ia1, ia1+6);multiset<int> S2(ia2, ia2+7);for_each(S1.begin(), S1.end(), display<int>());// 1 3 5 7 9 11cout << endl;for_each(S2.begin(), S2.end(), display<int>());// 1 1 2 3 5 8 13cout << endl;auto first1 = S1.begin();auto last1 = S1.end();auto first2 = S2.begin();auto last2 = S2.end();cout <<  "Union of S1 and S2:";set_union(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 1 1 2 3 5 7 9 11 13cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "intersection of S1 and S2:";set_intersection(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));// 1 3 5cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "difference of S1 and S2 (S1-S2): " ;set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 7 9 11cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "Symmetric difference of S1 and S2: " ;set_symmetric_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 1 2 7 8 9 11 13cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "difference of S2 and S1 (S2-S1): ";set_difference(first2, last2, first1, last1, ostream_iterator<int>(cout, " ")); // 1 2 8 13cout << endl;return 0;
}

        执行结果如下:

1 3 5 7 9 11 
1 1 2 3 5 8 13 
Union of S1 and S2:1 1 2 3 5 7 8 9 11 13 
intersection of S1 and S2:1 3 5 
difference of S1 and S2 (S1-S2): 7 9 11 
Symmetric difference of S1 and S2: 1 2 7 8 9 11 13 
difference of S2 and S1 (S2-S1): 1 2 8 13 

        请注意,当集合(set)允许重复元素的存在时,并集、交集、差集、对称差集的定义,都与直观定义有些微的不同。例如上述的并集结果,我们会直观以为是{1,2,3,5,7,8,9,11,13},而上述的对称差结果,我们会直观以为是{2,7,8,9,11,13},这都是未考虑重复元素的结果。以下各小节会详细说明。

set_union

        算法set_union可构造S1、S2之并集。也就是说,它能构造出集合S1\cup S2,此集合内含S1或S2内的每一个元素。S1、S2及其并集都是以排序区间表示。返回值为一个迭代器,指向输出区间的尾端。

        由于S1和S2内的每一个元素都不需要唯一,因此,如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间会出现max(n,m)次,其中n个来自S1,其余来自S2,在STL set容器内,m\leq 1n\leq 1

        set_union是一种稳定(stable)操作,意思是输入区间内的每个元素的相对顺序都不会改变。set_union有两个版本,差别在于如何定义某个元素小于另一个元素。第一版本使用operator<进行比较,第二版本采用仿函数comp进行比较。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;} else if (*first2 < *first1) {*result = *first2;++first2;} else {*result = *first1;++first1;++first2;}++result;}// 此时[first1,last1)和[first2,last2)至少有一个空白区间,边界剩下的是都属于union的元素return copy(first2, last2, copy(first1, last1, result));
}

        从以上合并的过程,可以看出主要是利用了set/multi_set经过排序的特性,而后对并集的特例化处理。和数学定义上的union处理略有差异。

set_itersection

        算法set_itersection可构造S1,S2之交集。也就是说,它能构造出集合S1\cap S2,此集合内含同时出现在S1和S2的每一个元素。S1、S2及其交集都是以排序区间表示。返回值为一个迭代器,指向输出区间的尾端。

        由于S1和S2内的每个元素都不需要唯一,因此,如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间出现min(n,m)次,并且全部来自S1.在STL set内,m\leq 1n\leq 1

        set_itersection是一种稳定(stable)的操作,意思是输出区间内的每个元素的相对顺序都和S1内的相对顺序相同。它有两个版本,其差异同set_union.其代码定义如下:

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_itersection(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {++first1;} else if (*first2 < *first1) {++first2;} else { // *first1 == *first2*result = *first1;++first1;++first2;}++result;}return result;
}

        对照set_itersection和set_union的算法实现,可发现内部迭代器的前进逻辑是一致的;只是输出时,只讲*first1==*first2的数据输出到result。对于边界情况,因为其中一组迭代器已经为空,所以也就没有了新的元素加入,直接返回了result;

set_difference

        算法set_difference可构造S1、S2只差集。也就是说,它能构造集合S1-S2,此集合内容"出现于S1但不出现于S2"的每一个元素。S1、S2及其交集都是以排序区间表示。返回值为一个迭代器,指向输出区间的尾端。

        由于S1和S2内的每个元素都不需要唯一,因此,如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间出现max(n-m,0)次

        set_difference是一种稳定操作,输出相对顺序保持S1内的相对顺序。代码如下:

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;++result;} else if (*first2 < *first1) {++first2;} else {++first1;++first2;}}return  copy(first1, last1, result);
}

        有了前面set_union及set_itersecion算法的经验,可看出迭代器的逻辑还是保留的相同的步伐。只是输出给result的值,只保留了*first1 < *first2的部分;正好符合S1-S2的特性。

set_symmetric_difference

        算法set_symmetric_difference可构造S1、S2之对称差集。也就是构造出(S1-S2)\cup (S2-S1),此集合内含"出现在S1但不出现于S2"以及“出现在S2不出现在S1”的每一个元素。

        有了前三个算法的基础,很容易得出set_symmetric_difference的结果包含*first1<*first2,以及*first2-*first1的结果,同时需要将边界情况保留。其代码如下:

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;++result;} else if (*first2 < *first1) {*result = *first2++first2;++result;} else {++first1;++first2;}}return  copy(first2, last2, copy(first1, last1, result));
}

 

参考文档《STL源码剖析》---侯捷

相关文章:

STL算法之set相关算法

STL一共提供了四种与set(集合)相关的算法&#xff0c;分别是并集(union)、交集(intersection)、差集(difference)、对称差集(symmetric difference)。 目录 set_union set_itersection set_difference set_symmetric_difference 所谓set&#xff0c;可细分为数学上定义的和…...

vscode中json文件的注释飘红

vscode的json文件 添加注释&#xff0c;提示json中不允许有注释&#xff0c;点编辑器最下面的json&#xff0c;如下图 然后选择如上图的json with comments就好了...

【微服务】SpringBoot 整合Redis Stack 构建本地向量数据库相似性查询

目录 一、前言 二、向量数据库介绍 2.1 什么是向量数据库 2.2 向量数据库特点 2.3 向量数据库使用场景 三、常用的向量数据库解决方案 3.1 Milvus 3.1.1 Milvus是什么 3.1.2 Milvus主要特点 3.2 Faiss 3.2.1 Faiss是什么 3.2.2 Faiss主要特点 3.3 Pinecone 3.3.1 …...

三:安装服务-controller node

一&#xff1a;工具、环境准备-controller node 二&#xff1a;OpenStack环境准备-controller node 三&#xff1a;安装服务-controller node 四&#xff1a;工具、环境准备-compute node 五&#xff1a;OpenStack环境准备-compute node 六&#xff1a;安装服务-compute node 七…...

自定义类型: 结构体、枚举 、联合

目录 结构体 结构体类型的声明 匿名结构体 结构的自引用 结构体变量的定义和初始化 结构体成员变量的访问 结构体内存对齐 结构体传参 位段 位段类型的声明 位段的内存分配 位段的跨平台问题 位段的应用 枚举 枚举类型的定义 枚举的优点 联合体(共用体) 联合…...

Bert+CRF的NER实战

CRF&#xff08;条件随机场-Conditional Random Field&#xff09; 原始本文&#xff1a;我在北京吃炸酱面 标注示例&#xff1a; 我O在O北B-PLA京I-PLA吃O炸B-FOOD酱I-FOOD面I-FOOD CRF&#xff1a; 目的&#xff1a;提出一些不可能出现的预测组合&#xff08;例如I-PLA不能…...

永久停用PostgreSQL 归档功能

文章目录 引言永久停用归档功能归档的优势归档的劣势开启归档的情况关闭归档的情况see also引言 PostgreSQL 是一个开源的关系型数据库系统,支持数据归档(WAL),可以实现数据备份、恢复和灾难恢复等功能。在使用 PostgreSQL 的过程中,如果 PostgreSQL 数据库开启了归档(a…...

《数字图像处理基础》学习07-图像几何变换之最近邻插值法放大图像

目录 一&#xff0c;概念 二&#xff0c;题目及matlab实现 1&#xff0c;解题思路 2&#xff0c;matlab实现 1&#xff09;matlab思路 2&#xff09;完整代码 三&#xff0c;放大图像及matlab实现 一&#xff0c;概念 通过上一篇&#xff0c;我已经学习了使用最邻近插…...

pip安装库时报错(请求超时)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

XPath表达式详解及其在Web开发中的应用

XPath&#xff08;XML Path Language&#xff09;是一种强大的查询语言&#xff0c;用于在XML文档中选择节点。由于HTML可以被视为一种特殊的XML&#xff0c;因此XPath同样适用于HTML文档。XPath允许开发者通过元素的层级结构和属性来选择节点或节点集合&#xff0c;这使得它成…...

Qt中Socket网络编程

文章目录 Qt中Socket网络编程服务器端客户端 Qt中Socket网络编程 这里就拿b站上爱编程的小丙的demo来做总结吧&#xff0c;首先要感谢成功带我入门的人&#xff1a;爱编程的小丙和程序员长风&#xff0c;这两个人是讲Socket编程我听懂的课555&#xff0c;接下来就总结一下Qt中…...

【05】Selenium+Python 两种文件上传方式(AutoIt)

上传文件的两种方式 一、input标签上传文件 可以用send_keys方法直接上传文件 示例代码 input标签上传文件import time from selenium import webdriver from chromedriver_py import binary_path # this will get you the path variable from selenium.webdriver.common.by i…...

Python网络编程

网络编程 Socket(套接字) socket 位于 网络协议中的 数据传输层、 该层 主要 可以通过 UDP 或者 TCP协议 实现 数据的传输 TCP 协议 VS UDP协议 tcp : 是一个 可靠的 &#xff0c;面向 连接的协议。 数据在网络传输中 是安全的&#xff0c;不易丢失的。 TCP连接 在建立的时候&…...

openssl生成ca证书

常见CA文件夹 1、生成CA钥匙 openssl genrsa -out ./private/cakey.pem 2、生成CA自签名 openssl req -new -x509 -key ./private/cakey.pem -out ./cacert.crt -days 3650 3、生成http服务器私钥 openssl genrsa -out ./data/frontt.project.com.key 2048 4、CA给http服务器…...

Oracle RAC 环境下数据文件误建在本地目录的处理过程

问题描述 在 Oracle RAC 环境中&#xff0c;有时会误将数据文件创建在本地目录&#xff0c;导致其他节点无法访问该数据文件&#xff0c;从而报出 ORA-01157 和 ORA-01110 错误。 问题分析 错误日志 Mon Nov 16 19:02:38 2021 Errors in file /u01/app/oracle/diag/rdbms/orc…...

新质驱动·科东软件受邀出席2024智能网联+低空经济暨第二届湾区汽车T9+N闭门会议

为推进广东省加快发展新质生产力&#xff0c;贯彻落实“百县千镇万村高质量发展工程”&#xff0c;推动韶关市新丰县智能网联新能源汽车、低空经济与数字技术的创新与发展&#xff0c;充分发挥湾区汽车产业链头部企业的带动作用。韶关市指导、珠三角湾区智能网联新能源汽车产业…...

windows11 使用体验记录

好的地方&#xff1a; UI上字体风格貌似更好看了&#xff0c;文件夹增加了多个标签&#xff0c;类似于浏览器既可以打开多个窗口&#xff0c;也可以在同一个窗口中打开多个标签页 不好的地方&#xff1a; 桌面右下角点击日期时间&#xff0c;显示日期&#xff0c;时间呢&…...

202页MES项目需求方案深入解读,学习MES系统设计规划

202页MES项目需求方案深入解读&#xff0c;学习MES系统设计规划 MES项目需求方案旨在实现制造执行、效率提升、精细化管理等多个方面的功能。整体结构分为七大部分&#xff0c;包括制造执行、效率、精细化、品质在线、设备、用户思想和数据互联。制造执行部分关注订单、品质数据…...

前端css实例

前端css实例 一、带条纹的表格 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>条纹样式的表格<…...

YOLO的框架及版本迭代

YOLO&#xff08;You Only Look Once&#xff09;是一种非常流行的实时目标检测算法&#xff0c;其特点是将目标检测任务转换为一个回归问题&#xff0c;通过一次前向传播就可以同时完成目标的分类和定位。以下是YOLO框架的整体架构和工作原理&#xff1a; 一、YOLO的基本框架…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...