前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【C++】STL标准模板库容器set

【C++】STL标准模板库容器set

作者头像
修修修也
发布于 2024-09-28 14:52:32
160
发布于 2024-09-28 14:52:32
举报
文章被收录于专栏：修也的进阶日记

在之前对STL的学习中，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，根据"数据在容器中的排列"特性,这些容器统称为序列式(sequence)容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。 还有一种容器是关联式(associative)容器, 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。 下图列出了STL中的各种容器,以及其基层与衍生层的关系:

📌关联式容器set(集合)简介

我们先来看一下cplusplus.com - The C++ Resources Network网站对set的文档介绍:

总结一下:

  1. set是按照一定次序存储元素的容器。
  2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
  3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现的。

注意:

  • 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
  • set中插入元素时，只需要插入value即可，不需要构造键值对。
  • set中的元素不可以重复(因此可以使用set进行去重)。
  • 使用set的迭代器遍历set中的元素，可以得到有序序列。
  • set中的元素默认按照小于来比较。
  • set中查找某个元素，时间复杂度为：
$log_2 n$
$log_2 n$
  • set中的元素不允许修改(因为修改key可能会导致二叉搜索树结构被破坏)。
  • set中的底层使用二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))来实现。

📌set(集合)的使用

🎏set(集合)的模板参数列表

set的模板参数及含义如下:

🎏set(集合)的构造函数

set的构造函数及其功能如下:

使用示例如下:

代码语言：javascript
复制
#include<iostream>
#include<vector>
#include<set>
using namespace std;

int main()
{
	//构造一个没有元素的空容器
	set<int> s1;
	for (auto e : s1)
	{
		cout << e << " ";
	}
	cout << endl;

	vector<int> v;
	v.push_back(2);
	v.push_back(5);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);

	//迭代器区间构造
	set<int> s2(v.begin(), v.end());
	for (auto e : s2)
	{
		cout << e << " ";
	}
	cout << endl;

	//拷贝构造
	set<int> s3(s2);
	for (auto e : s3)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

运行效果如下:

🎏set(集合)的迭代器

set的迭代器相关函数及其功能如下:

使用示例如下:

代码语言：javascript
复制
int main()
{
	vector<int> v;
	v.push_back(2);
	v.push_back(5);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);

	//迭代器区间构造
	set<int> s(v.begin(), v.end());

	//正向迭代器
	set<int>::iterator it_b = s.begin();	//访问正向迭代器开始
	cout << *it_b << endl;

	set<int>::iterator it_e = s.end();		//访问正向迭代器结束
	--it_e;									
	cout << *it_e << endl;
	++it_e;

	while (it_b != it_e)
	{
		cout << *it_b << " ";			//使用正向迭代器遍历set
		++it_b;
	}
	cout << endl;

	//反向迭代器
	set<int>::reverse_iterator rit_b = s.rbegin();		//访问反向迭代器开始
	cout << *rit_b << endl;

	set<int>::reverse_iterator rit_e = s.rend();		//访问反向迭代器结束
	--rit_e;
	cout << *rit_e << endl;
	++rit_e;

	while (rit_b != rit_e)
	{
		cout << *rit_b << " ";			//使用反向迭代器遍历set
		++rit_b;
	}
	cout << endl;

	return 0;
}

运行结果如下:

🎏set(集合)的容量

set的容量相关函数及其功能如下:

使用示例如下:

代码语言：javascript
复制
int main()
{
	//构造一个没有元素的空容器
	set<int> s1;
	cout << s1.empty() << endl;
	cout << s1.size() << endl;
	cout << s1.max_size() << endl;


	vector<int> v;
	v.push_back(2);
	v.push_back(5);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);

	//迭代器区间构造
	set<int> s2(v.begin(), v.end());
	cout << s2.empty() << endl;
	cout << s2.size() << endl;
	cout << s2.max_size() << endl;
	
	return 0;
}

运行结果如下:

🎏set(集合)的修改操作

set的修改相关函数及其功能如下:

函数声明

功能介绍

pair<iterator, bool> insert(const value_type&x)

在set中插入元素x，实际插入的是<x, x>构成的 键值对，如果插入成功，返回<该元素在set中的 位置，true>,如果插入失败，说明x在set中已经 存在，返回<x在set中的位置，false>

void erase ( iterator position )

删除set中position位置上的元素

size_type erase ( const key_type& x )

删除set中值为x的元素，返回删除的元素的个数

void erase ( iterator first, iterator last )

删除set中[first, last)区间中的元素

void swap ( set<Key,Compare,Allocator>& st )

交换两个set中的元素

void clear ( )

将set中的元素清空

iterator find ( const key_type& x ) const

返回set中值为x的元素的位置

size_type count ( const key_type& x ) const

返回set中值为x的元素的个数

insert,erase,clear,find函数使用示例如下:

代码语言：javascript
复制
int main()
{
	//构造一个没有元素的空容器
	set<int> s1;
	//插入元素
	s1.insert(3);
	s1.insert(1);
	s1.insert(7);
	s1.insert(4);
	s1.insert(0);
	s1.insert(8);
	s1.insert(2);
	s1.insert(6);
	s1.insert(9);
	s1.insert(5);

	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	set<int>::iterator pos = s1.find(1);
	//迭代器删除元素
	s1.erase(pos);
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	//key值删除元素
	s1.erase(3);
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	//迭代区间删除元素
	s1.erase(s1.begin(), s1.find(5));
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	//清空set中的元素
	s1.clear();
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	return 0;
}

运行结果如下:

swap函数使用示例如下:

代码语言：javascript
复制
int main()
{
	//构造两个没有元素的空容器
	set<int> s1;
	set<int> s2;
	//s1中插入元素
	s1.insert(3);
	s1.insert(1);
	s1.insert(4);
	s1.insert(0);
	s1.insert(2);

	cout << "s1 : ";
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	cout << "s2 : ";
	for (auto k : s2)
	{
		cout << k << " ";
	}
	cout << endl;

	//交换s1和s2的值
	s1.swap(s2);
	cout << "s1 : ";
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	cout << "s2 : ";
	for (auto k : s2)
	{
		cout << k << " ";
	}
	cout << endl;

	return 0;
}

运行结果如下:

count()函数的定义如下图:

count函数使用示例如下:

代码语言：javascript
复制
int main()
{
	//构造一个没有元素的空容器
	set<int> s1;
	//s1中插入元素
	s1.insert(3);
	s1.insert(1);
	s1.insert(4);
	s1.insert(0);
	s1.insert(2);

	cout << "s1 : ";
	for (auto k : s1)
	{
		cout << k << " ";
	}
	cout << endl;

	cout << s1.count(2) << endl;
	cout << s1.count(4) << endl;
	cout << s1.count(6) << endl;
	cout << s1.count(8) << endl;

	return 0;
}

运行结果如下:

📌关联式容器multiset简介

我们先来看一下cplusplus.com - The C++ Resources Network网站对set的文档介绍:

总结一下:

  1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
  2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
  3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
  4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
  5. multiset底层结构为二叉搜索树(红黑树)

注意:

  1. multiset中再底层中存储的是<value, value>的键值对
  2. mtltiset的插入接口中只需要插入即可
  3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
  4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
  5. multiset中的元素不能修改
  6. 在multiset中找某个元素，时间复杂度为O(log_2 N)
  7. multiset的作用：可以对元素进行排序

📌关联式容器multiset使用

multiset的接口是和set一模一样的,区别在于具体的使用上:

首先,multiset支持插入重复的键值key, 这就意味着multiset没有set的去重作用 :

代码语言：javascript
复制
int main()
{
	//构造一个没有元素的空容器set
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(5);
	s.insert(5);	//插入多个重复键值key
	s.insert(5);
	s.insert(4);
	s.insert(5);
	s.insert(2);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	//构造一个没有元素的空容器multiset
	multiset<int> ms;
	ms.insert(3);
	ms.insert(1);
	ms.insert(5);
	ms.insert(5);	//插入多个重复键值key
	ms.insert(5);
	ms.insert(4);
	ms.insert(5);
	ms.insert(2);

	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

运行结果如下:

同时,对于set模板里几乎没有什么意义的几个函数接口在multiset这里就可以得到很好的应用了,如:count,equal_range等函数:

如下代码,我们利用count函数计算multiset中5出现的次数,并利用equal_range函数将其全部删除:

代码语言：javascript
复制
int main()
{
	//构造一个没有元素的空容器multiset
	multiset<int> ms;
	ms.insert(3);
	ms.insert(1);
	ms.insert(5);
	ms.insert(5);	//插入多个重复键值key
	ms.insert(5);
	ms.insert(4);
	ms.insert(5);
	ms.insert(2);

	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl;

	//计算5出现的次数
	cout << "5出现的次数: " << ms.count(5) << endl;

	//删掉所有的5
	pair<multiset<int>::iterator, multiset<int>::iterator> ret = ms.equal_range(5);	//这里ret的类型直接用auto也行
	multiset<int>::iterator left = ret.first;
	multiset<int>::iterator right = ret.second;
	ms.erase(left, right);

	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

运行结果如下:

结语

希望这篇关于 STL标准模板库容器set 的博客能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-09-27，如有侵权请联系 cloudcommunity@tencent.com 删除
c++
容器
set
stl
函数

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

c++
容器
set
stl
函数
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 📌关联式容器set(集合)简介
  • 📌set(集合)的使用
    • 🎏set(集合)的模板参数列表
      • 🎏set(集合)的构造函数
        • 🎏set(集合)的迭代器
          • 🎏set(集合)的容量
            • 🎏set(集合)的修改操作
            • 📌关联式容器multiset简介
            • 📌关联式容器multiset使用
            • 结语
            相关产品与服务
            容器服务
            腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
            产品介绍产品文档
            精选特惠 用云无忧
            领券

            腾讯云开发者

            扫码关注腾讯云开发者

            扫码关注腾讯云开发者

            领取腾讯云代金券

            热门产品

            热门推荐

            更多推荐

            Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

            深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

            腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

            Copyright © 2013 - 2024 Tencent Cloud.

            All Rights Reserved. 腾讯云 版权所有

            登录 后参与评论