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或S2内的每一个元素。S1、S2及其并集都是以排序区间表示。返回值为一个迭代器,指向输出区间的尾端。
由于S1和S2内的每一个元素都不需要唯一,因此,如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间会出现max(n,m)次,其中n个来自S1,其余来自S2,在STL set容器内,且
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和S2的每一个元素。S1、S2及其交集都是以排序区间表示。返回值为一个迭代器,指向输出区间的尾端。
由于S1和S2内的每个元素都不需要唯一,因此,如果某个值在S1出现n次,在S2出现m次,那么该值在输出区间出现min(n,m)次,并且全部来自S1.在STL set内,且
。
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"以及“出现在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算法之set相关算法
STL一共提供了四种与set(集合)相关的算法,分别是并集(union)、交集(intersection)、差集(difference)、对称差集(symmetric difference)。 目录 set_union set_itersection set_difference set_symmetric_difference 所谓set,可细分为数学上定义的和…...

vscode中json文件的注释飘红
vscode的json文件 添加注释,提示json中不允许有注释,点编辑器最下面的json,如下图 然后选择如上图的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
一:工具、环境准备-controller node 二:OpenStack环境准备-controller node 三:安装服务-controller node 四:工具、环境准备-compute node 五:OpenStack环境准备-compute node 六:安装服务-compute node 七…...

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

Bert+CRF的NER实战
CRF(条件随机场-Conditional Random Field) 原始本文:我在北京吃炸酱面 标注示例: 我O在O北B-PLA京I-PLA吃O炸B-FOOD酱I-FOOD面I-FOOD CRF: 目的:提出一些不可能出现的预测组合(例如I-PLA不能…...
永久停用PostgreSQL 归档功能
文章目录 引言永久停用归档功能归档的优势归档的劣势开启归档的情况关闭归档的情况see also引言 PostgreSQL 是一个开源的关系型数据库系统,支持数据归档(WAL),可以实现数据备份、恢复和灾难恢复等功能。在使用 PostgreSQL 的过程中,如果 PostgreSQL 数据库开启了归档(a…...

《数字图像处理基础》学习07-图像几何变换之最近邻插值法放大图像
目录 一,概念 二,题目及matlab实现 1,解题思路 2,matlab实现 1)matlab思路 2)完整代码 三,放大图像及matlab实现 一,概念 通过上一篇,我已经学习了使用最邻近插…...

pip安装库时报错(请求超时)
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...
XPath表达式详解及其在Web开发中的应用
XPath(XML Path Language)是一种强大的查询语言,用于在XML文档中选择节点。由于HTML可以被视为一种特殊的XML,因此XPath同样适用于HTML文档。XPath允许开发者通过元素的层级结构和属性来选择节点或节点集合,这使得它成…...
Qt中Socket网络编程
文章目录 Qt中Socket网络编程服务器端客户端 Qt中Socket网络编程 这里就拿b站上爱编程的小丙的demo来做总结吧,首先要感谢成功带我入门的人:爱编程的小丙和程序员长风,这两个人是讲Socket编程我听懂的课555,接下来就总结一下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 : 是一个 可靠的 ,面向 连接的协议。 数据在网络传输中 是安全的,不易丢失的。 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 环境中,有时会误将数据文件创建在本地目录,导致其他节点无法访问该数据文件,从而报出 ORA-01157 和 ORA-01110 错误。 问题分析 错误日志 Mon Nov 16 19:02:38 2021 Errors in file /u01/app/oracle/diag/rdbms/orc…...

新质驱动·科东软件受邀出席2024智能网联+低空经济暨第二届湾区汽车T9+N闭门会议
为推进广东省加快发展新质生产力,贯彻落实“百县千镇万村高质量发展工程”,推动韶关市新丰县智能网联新能源汽车、低空经济与数字技术的创新与发展,充分发挥湾区汽车产业链头部企业的带动作用。韶关市指导、珠三角湾区智能网联新能源汽车产业…...
windows11 使用体验记录
好的地方: UI上字体风格貌似更好看了,文件夹增加了多个标签,类似于浏览器既可以打开多个窗口,也可以在同一个窗口中打开多个标签页 不好的地方: 桌面右下角点击日期时间,显示日期,时间呢&…...

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

前端css实例
前端css实例 一、带条纹的表格 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>条纹样式的表格<…...
YOLO的框架及版本迭代
YOLO(You Only Look Once)是一种非常流行的实时目标检测算法,其特点是将目标检测任务转换为一个回归问题,通过一次前向传播就可以同时完成目标的分类和定位。以下是YOLO框架的整体架构和工作原理: 一、YOLO的基本框架…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...