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

【C++】set和multiset的常用接口详解

news 来源：原创 2025/6/26 12:27:23

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，本篇文章将介绍一下map和multiset的使用。

1. 序列式容器和关联式容器

在介绍set之前我们先简单介绍一下什么是序列式容器和关联式容器。

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是 ⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列unordered_map/unordered_set系列。

set是key搜索场景的结构。

2. set系列的使⽤

2.1 set和multiset参考⽂档

参考文档：<set> - C++ Reference

先来总体看一下set的相关接口。

总的来说还是之前我们在vector，string接触过的那些东西。虽然看起来接口很多，但常用的以及会学习到的就那些。

2.2 set类的介绍

set的声明如下。

参数1：T就是set底层关键字的类型。这个T就是key，名字不同。
参数2：set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。
参数3：set底层存储数据的内存是从空间配置器申请的（空间配置器），如果需要可以⾃⼰实现内存池，传给第三个参数。

⼀般情况下，我们都不需要传后两个模版参数。

set底层是⽤红⿊树（以后会介绍）实现，增删查效率是O（

），迭代器遍历是⾛的搜索树的中序，所以是有序的。

2.3 set的构造和迭代器

先看它的构造函数。

再来看看他的迭代器。

从文档介绍可以看出这是一个双向迭代器，⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序。
⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

2.4 set的增删查（不支持改）

2.4.1 insert

先看insert，增。

增这里首先支持增加一个value_type类型的东西，value_type什么？

从这里可以看到，其实就是我们传的那个关键字Key，并且上面那个key_type也是key。所以就是插入一个key。这里的返回值类型后面会说，暂时不关注。

用set的时候要包含头文件#include <set>

#include <iostream>
#include <set>
using namespace std;
int main()
{set<int> s;s.insert(2);s.insert(1);s.insert(4); //重复s.insert(3);s.insert(4); //重复return 0;
}

第二个参数不传的话，默认排升序。

用迭代器遍历一下。

int main()
{set<int> s;s.insert(2);s.insert(1);s.insert(4);s.insert(3);s.insert(4);auto it = s.begin();while (it != s.end()){cout << *it << ' ';it++;}cout << endl;return 0;
}

如果这里不用auto的话，就是 set<int>::iterator it = s.begin();

可以看到此时的s就是一个去重并且升序的状态。

如果想变成降序，set的参数列表就多传一个参数。

set<int, greater<int>> s;

此时的s就是去重并且排降序。

还支持在某个位置插入，一般不用。

支持插入一段迭代器区间。

还支持插入initializer_list。

就是用大括号括起来插入。

set<int> s;
s.insert(2);
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(4);
s.insert({ 7, 5, 8, 6 }); //插入一段列表值auto it = s.begin();
while (it != s.end())
{cout << *it << ' ';it++;
}
cout << endl;

而且如果这个列表里面有冗余的值，也会去掉。

set除了支持整形，也支持字符串，如下。

set<string> ss({ "hello", "eat", "bad", "cat" });
auto it = ss.begin();
while (it != ss.end())
{cout << *it << ' ';it++;
}
cout << endl;

字符串的话比较顺序是按照ASCII码顺序比的。

这里还有一种写法。

//set<string> ss({ "hello", "eat", "bad", "cat" });set<string> ss = { "hello", "eat", "bad", "cat" }; //另一种写法

第一种写法就是直接调用构造函数，第二种写法就是构造的隐式类型转换，构造+拷贝构造优化成构造。

2.4.2 find和erase

find支持value_type的查找，value_type就是T就是key。

找到了就返回这个迭代器，没找到就返回end，end就是最后一个位置的后一个位置。

删除有三个接口。

传迭代器过去，删除某个位置的值。
传一个值过去，传的这个值可能在容器里，也可能不在，如果在，就直接删除，然后返回删除了几个数，如果删除一个就返回1；如果这个值不在容器里，就会返回0，因为删除了0个数。（set每个数只有一个，但是multiset有多个）
传迭代器区间过去，删除一个区间的值。

我们先给这个容器一些值，并且打印出来。

set<int> s = { 3,1,5,6,4,9,2 };
for (auto e : s)
{cout << e << " ";
}
cout << endl;

比如说我们现在要删除最小值。直接传begin过去就可以。

s.erase(s.begin()); //删除最小值

因为s默认排升序，第一个值就是最小值，迭代器是左闭右开的，就是begin。

这里用到的就是第1个接口。这个接口的返回值是删除位置的后一个位置的迭代器。

我们也可以输入一个值让他删除。

int x;
cin >> x; //输入一个值
int ret = s.erase(x); //ret接收erase的返回值
if (ret == 0)cout << "此值不存在" << endl;
for (auto e : s)
{cout << e << " ";
}
cout << endl;

先输入一个存在的值。

再输入一个不存在的值试试。

不存在的话什么都不删。这里用到的就是第2个接口。

第二个接口其实可以理解为是用find+第一个接口来实现的，如下。

int x;
cin >> x; //输入一个值
auto pos = s.find(x);//先找值
if (pos != s.end()) //找到了就删
{s.erase(pos);cout << "删除成功" << endl;
}
elsecout << "此值不存在" << endl;

迭代器区间删除在2.4.4里会说。

删除后迭代器失效问题

这里删除数据绝对会导致迭代器失效。失效有两种情况，一是导致野指针问题，二是删除后迭代器意义改变。具体分析需要结合底层。比如说我们删除一个数之后再访问这个迭代器，vs平台下是一定会报错的。

2.4.3 count

count就是传一个value_type，然后返回这个值在容器里的个数。虽然set里的值有就是1，没有就是0，是要和multiset保持一致，因为multiset里不仅是有没有这个值，他还可能有多个。

count确定某个值在不在会比find更方便。

set<int> s = { 3,1,5,6,4,9,2 };
for (auto e : s)
{cout << e << " ";
}
cout << endl;int x;
cin >> x; //输入一个值
if (s.count(x)) //非0就存在
{cout << x << "存在" << endl;
}
else
{cout << x << "不存在" << endl;
}

2.4.4 lower_bound 和 upper_bound

lower_bound 是返回⼤于等于val位置的迭代器；upper_bound 是返回⼤于val位置的迭代器。
这样设计是为了方便我们找一段迭代器区间，因为只要是迭代器区间，就必须是左闭右开的。

比如说现在有一堆值，如下。

set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };

现在要求 : 1. 删除[30, 50]区间的值 2. 删除[25, 65]之间的值。

先看第一个。删30到50之间的值，但是迭代器区间只能是左闭右开，左闭能删除，右开怎么办？

set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
//删除[30,50]
auto left = s.lower_bound(30); //左闭

给upper_bound传50过去，upper_bound返回比50大的第一个迭代器。

set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
//删除[30,50]
auto left = s.lower_bound(30); //左闭 返回 >=30
auto right = s.upper_bound(50);//右开 返回 >50

这里正好有30，就返回30；返回比50大的第一个迭代器，60，60是开区间。

然后我们删掉这个区间。这里就用到了前面没说的删除的第三个接口，传迭代器区间。

s.erase(left, right); //删除
for (auto e : s)
{cout << e << " ";
}
cout << endl;

再看第二个，删除25到65之间的值。25和65都不在这个容器里，怎么办？还是一样的，lower_bound传25过去，没有25就返回比25大的第一个迭代器，给upper_bound传65过去，upper_bound返回比65大的第一个迭代器。

set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
//删除[25,65]
auto left = s.lower_bound(25); //左闭 返回 >=25
auto right = s.upper_bound(65);//右开 返回 >65
s.erase(left, right); //删除
for (auto e : s)
{cout << e << " ";
}
cout << endl;

3.set和multiset的差别

multiset的使用不需要再包含别的头文件，就是#include <set>。

multiset和set的使⽤基本完全类似，主要区别点在于 multiset⽀持值冗余。

那么insert / find / count / erase都围绕着⽀持值冗余有所差异。

insert相⽐set的不同的是，multiset的支持插入已经存在的值。

count相⽐set的不同的是，multiset的会返回x的实际个数。

multiset<int> ms = { 2,5,4,7,6,8,2,1,5,2 };
for (auto e : ms)
{cout << e << ' ';
}
cout << endl;
cout << ms.count(2) << endl;
cout << ms.count(9) << endl;

2在容器里有3个，count就返回3，9不在容器里，就返回0。

find不同的是，multiset里的x可能会存在多个，如果有多个，find查找的是中序的第⼀个。

比如说下面这颗树，我们找3，但是有两个3。（这棵树不平衡，只是举例说明什么叫中序第一个）

可以自己可以走一遍中序遍历，会发现框起来的3是中序遍历的第一个3，就返回它。

返回中序的第一个，我们就可以把所有相同的值全打印出来。

auto tar = ms.find(2);
while (tar != ms.end() && *tar == 2) 
{cout << *tar << " ";tar++;
}
cout << endl;

erase不同的是，multiset的erase给值时会删除所有的x。

ms.erase(2);
for (auto e : ms)
{cout << e << ' ';
}
cout << endl;

4.相关练习

4.1 两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

这个题的思路：先用set去重+排序，然后用两个指针比较两个数组的值，相同的就放到一起。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{set<int> s1, s2;vector<int> ret;for (auto e : nums1) s1.insert(e);for (auto e : nums2) s2.insert(e);
}

vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{set<int> s1, s2;vector<int> ret;for (auto e : nums1) s1.insert(e);for (auto e : nums2) s2.insert(e);auto it1 = s1.begin();auto it2 = s2.begin();
}

相同就放到ret里，然后同时往后移动，不同的话，谁小谁就后移。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{set<int> s1, s2;vector<int> ret;for (auto e : nums1) s1.insert(e);for (auto e : nums2) s2.insert(e);auto it1 = s1.begin();auto it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 == *it2){ret.push_back(*it1); //相同就放到retit1++; it2++;}else if (*it1 > *it2) it2++;else it1++;}return ret;
}

最后返回ret就行。

4.2 环形链表

142. 环形链表 II - 力扣（LeetCode）

这道题用set写就会特别简单，思路：遍历这个链表，把节点的地址存到set里，如果出现相同的结点地址，就是带环，否则不带环。（存的是地址不是值！因为不同的节点可能存在值相同）

当我们遍历到-4时，前面这4个节点地址都没出现重复，继续遍历。

-4节点的下一个是2。

因为2的地址出现了两次，所以直接就可以判断为带环。代码实现如下。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *cur = head;set<ListNode*> s;while(cur){if(s.count(cur)) return cur;else s.insert(cur);cur = cur->next;}return nullptr;}
};

本次分享就到这里了，我们下篇见~

【C++】set和multiset的常用接口详解

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，本篇文章将介绍一下map和multiset的使用。 1. 序列式容器和关联式容器在介绍set之前我们先简单介绍一下什么是序列式容器和关联式容器。前⾯我们已经接触过S…...

编程日记 2025/6/26 12:27:23

PostgreSQL 联合索引生效条件

最近面试的时候，总会遇到一个问题在 PostgreSQL 中，联合索引在什么条件下会生效？ 特此记录~ 前置信息数据库版本 PostgreSQL 14.13, compiled by Visual C build 1941, 64-bit 建表语句 CREATE TABLE people (id SERIAL PRIMARY KEY,c…...

编程日记 2025/6/27 1:22:44

聊聊redisson的lockWatchdogTimeout

序本文主要研究一下redisson的lockWatchdogTimeout lockWatchdogTimeout redisson/src/main/java/org/redisson/config/Config.java private long lockWatchdogTimeout 30 * 1000;/*** This parameter is only used if lock has been acquired without leaseTimeout param…...

编程日记 2025/6/25 10:18:24

数据结构第七章（三）-树形查找：红黑树

树形查找（二） 红黑树一、红黑树1.定义2.黑高3.性质二、插入1.插入步骤2.举例总结红黑树红黑树来喽~ 我们在上一篇说了二叉排序树（BST）和平衡二叉树（AVL），那么既然都有这两个了，…...

编程日记 2025/6/27 1:01:43

C++篇——多态

目录引言 1，什么是多态 2. 多态的定义及实现 2_1，多态的构成条件 2_2，虚函数 2_3，虚函数的重写 2_4，虚函数重写的两个例外 2_4_1，协变(基类与派生类虚函数返回值类型不同) 2_4_2. 析构函数的重写(基类…...

编程日记 2025/6/26 6:45:42

AI实时对话的通信基础，WebRTC技术综合指南

在通过您的网络浏览器进行音频和视频通话、屏幕共享或实时数据传输时，您可能并不常思考其背后的技术。推动这些功能的核心力量之一就是WebRTC。2011年由谷歌发布的这个开源项目，如今已发展成为一个高度全面且不断扩展的生态系统。尤其是在AI技术大幅突破…...

编程日记 2025/6/26 23:55:19

【寻找Linux的奥秘】第五章：认识进程

请君浏览前言1. 冯诺依曼体系结构数据流动 2. 操作系统（Operating System）2.1 概念2.2 设计OS的目的2.3 如何理解“管理”2.4 系统调用和库函数概念 3. 进程3.1 基本概念3.1.1 查看进程3.1.2 创建进程 3.2 进程状态3.2.1 简单介绍3.2.2 运行&&阻…...

编程日记 2025/6/27 1:03:00

uniapp微信小程序-长按按钮百度语音识别回显文字

流程图： 话不多说，上代码： <template><view class"content"><view class"speech-chat" longpress"startSpeech" touchend"endSpeech"><view class"animate-block" …...

编程日记 2025/6/27 1:06:10

支付宝创建商家订单收款码（统一收单线下交易预创建）.net开发的软件附带大型XML文件可以删除吗？AlipaySDKNet.OpenAPI.xml

支付宝创建商家订单收款码（统一收单线下交易预创建）一个程序55MB，XML就带了35MB AlipaySDKNet.OpenAPI.xml，BouncyCastle.Crypto.xml 支付宝店铺收款码创建的程序，这些文件可以不用吗在支付宝店铺收款码创建的程序中…...

编程日记 2025/6/27 1:22:45

Profinet转Ethernet/IP网关模块通信协议适配配置

案例背景在某自动化生产车间中，现有控制系统采用了西门子 S7 - 1500 PLC 作为主要控制器，负责生产流程的核心控制。同时，由于部分设备的历史原因，存在使用 AB 的 PLC 进行特定环节控制的情况。为了实现整个生产系统的信息交互与…...

编程日记 2025/6/26 19:31:48

4.6/Q1，GBD数据库最新文章解读

文章题目：Global burden, subtype, risk factors and etiological analysis of enteric infections from 1990-2021: population based study DOI：10.3389/fcimb.2025.1527765 中文标题：1990-2021 年肠道感染的全球负担、亚型、危险因素和病因…...

编程日记 2025/6/27 0:26:22

数字孪生技术：开启未来的“镜像”技术

想象一下，你拥有一个与现实世界一模一样的 “数字分身”，它不仅长得像你，行为举止、思维方式也和你毫无二致，甚至能提前预知你的下一步行动。这听起来像是科幻电影里的情节，但数字孪生技术却让它在现实中成为了可能。数…...

编程日记 2025/6/26 22:22:40

Java 序列化（Serialization）

一、理论说明 1. 序列化的定义 Java 序列化是指将对象转换为字节流的过程，以便将其存储到文件、数据库或通过网络传输。反序列化则是将字节流重新转换为对象的过程。通过实现java.io.Serializable接口，类可以被标记为可序列化的，该接口是一…...

编程日记 2025/6/26 3:39:46

Python解析Excel入库如何做到行的拆分

我们读取解析Excel入库经常会遇到这种场景，那就是行的拆分，如图： 比如我们入库，要以name为主键，可是表格name的值全是以逗号分割的多个，这怎么办呢？这就必须拆成多行了啊。代码如下&#xff…...

编程日记 2025/6/24 8:35:45

信创国产化监控 | 达梦数据库监控全解析

达梦数据库（DM Database）是国产数据库的代表产品之一，在政府、金融、电信、能源等多个关键行业应用广泛，它具有高兼容性、高安全性、高可用性、高性能、自主可控等特点。随着国产化替代进程加速，达梦数据库在关键信息基…...

编程日记 2025/6/21 5:23:07

Parsec解决PnP连接失败的问题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言一、准备环境二、DMZ三、端口映射1.Parsec设置固定端口2.路由器设置端口转发3.重启被控端Parsec四、多少一句1.有光猫管理员账号2.没有光猫管理员账号总结前言…...

编程日记 2025/6/25 8:44:48

LLM笔记（二）LLM数据基础

核心目标: 构建 LLM 的数据基础，将原始文本转化为模型可处理的、包含丰富语义和结构信息的数值形式。一、环境与库准备 (Environment & Libraries): 必要库确认: 在开始之前，确保 torch (PyTorch深度学习框架) 和 tiktoken (OpenAI的高效BPE分词…...

编程日记 2025/6/25 15:49:01

让三个线程（t1、t2、t3）按顺序依次打印 A、B、C

public class ThreadWait {private static final Object lock = new Object();private static boolean t1Output=true;private static boolean t2Output=false;private static boolean t3Output=false;public static void main(String[] args) {//线程1new Thread(new Runnable…...

编程日记 2025/6/24 10:25:34