C++ | STL 单集合容器set和多集合容器multiset

2024-03-31 19:18
文章标签 c++ set 容器 集合 stl multiset

本文主要是介绍C++ | STL 单集合容器set和多集合容器multiset,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一.单集合容器set和多集合容器multiset

二.set常用的构造方式

三.set的插入,删除以及查找操作

四.set的访问函数

五.比较 set 和multiset的不同

六.使用set和multiset时的注意事项


一.单集合容器set和多集合容器multiset

set指的是单集合容器,所谓的单集合容器指的是容器里面的数据不能重复,所需要的头文件为#include<set>,其底层为红黑树

multiset指的是多集合容器,所谓的多集合容器指的是容器里面的数据可以重复,所需要的头文件为#include<set>,其底层为红黑树

二.set常用的构造方式

#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{std::set<int> myset; //默认的构造 int arr[] = { 13, 2, 343, 2, 53, 6 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset1(arr, arr + len);Show(myset);Show(myset1);return 0;
}

在构造set容器myset时,调用的是set类中默认的构造函数,(所有的容器中都有默认的构造函数),且构造的同时没有做任何事情。

在构造set容器myset1时,我们传入的参数是一个迭代器区间,即将arr数组的开始和末尾的后一个位置传入,也就是将arr中的数据插入到myset1中。并且我们发现,虽然在向myset1中插入元素时,有重复的元素2,但最终的打印的结果却只有一个2,这是因为单集合容器set里面的数据不能重复。而且打印的结果是从小到大打印的,这是因为单集合容器set的底层为红黑树,默认的排序方式是从小到大的。

三.set的插入,删除以及查找操作

#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{std::set<int> myset; //默认的构造 std::set<int> myset1;int arr[] = { 11,22,33,44 };int len = sizeof(arr) / sizeof(arr[0]);myset1.insert(arr, arr + len);Show(myset1);for (int i = 0; i < 5; i++){myset.insert(i + 1);//按位置插入   set只给出了数据 没有给出位置。}myset.insert(myset.begin(), 10);//位置无效 Show(myset);myset.erase(10);std::set<int>::iterator it = myset.begin();myset.erase(it);Show(myset);return 0;
}

我们知道,set容器的底层是红黑树,而红黑树是在二叉排序树的基础上实现的,这也就意味着在向set容器中插入元素时不需要传入位置,因为红黑树会自动根据插入节点的值的大小来调整该节点的位置,使得最后该二叉树还是一个红黑树,因此也就不存在头插,尾插以及按位置插等方法,例如上述代码中,哪怕你在insert函数中给定了要插入的位置,系统也会将该位置忽略,所以我们在调用insert时只需要给定要插入的值就可以。或者我们也可以给定一个迭代器区间,将这个区间内的所有值都插入。

insert的重载还有很多,在这里就不一一列举。

因为set的底层为红黑树,因此也不存在头删,尾删,因为每个节点的位置随时都可能发生变动

erase的重载还有很多,在这里就不一一列举。

关于在set容器中查找一个值为val的元素是否存在,在std域下有一个泛型算法find可以实现,这个find函数的形参是要查找的范围即一个迭代器区间,以及要查找的值val,但这个find的时间复杂度为O(n),因为这个泛型算法采用的是顺序遍历。另外,在set类中也会提供一个find函数,这个find函数的形参为要查找的值val,而他的时间复杂度为O(log2 n),因为set底层是红黑树,而红黑树中的数据已经经过了排列而变得有序了,那么就可以使用二分法来查找

因此set容器的优点就是“快速查找”

#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 13, 2, 343, 2, 53, 6 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset(arr, arr + len);Show(myset);//find  时间复杂度 O(n)  泛型算法库std::set<int>::iterator fit1 = std::find(myset.begin(),myset.end(), 53);if (fit1 != myset.end()){std::cout << *fit1 << std::endl;}//find	时间复杂度O(log2 n)		set类中提供  优点std::set<int>::iterator fit2 = myset.find(53);if (fit2 != myset.end()){std::cout << *fit2 << std::endl;}return 0;
}

四.set的访问函数

#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 1,9,8,10,7,3,6,2,5,4 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset(arr, arr + len);Show(myset);return 0;
}

我们发现我们在访问某一set容器时,最终的结果是从小到大排序的,因为这是系统默认的,我们也可以通过添加参数,来决定底层的二叉树对数据的排序方法。例如:

#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 1,9,8,10,7,3,6,2,5,4 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int,std::less<int>> myset(arr, arr + len);std::set<int, std::greater<int>> myset1(arr, arr + len);Show(myset);Show(myset1);return 0;
}

五.比较 set 和multiset的不同

所谓的multiset其实就是多集合容器,其底层也是一棵红黑树,之前我们讲过,单集合容器set中不允许有重复的数据存在,而多集合容器multiset恰恰与其相反,因为它允许重复的元素存在。多集合容器multiaet所需要的头文件也为#include<set>。下面,我们来举一个例子,来看一下二者的区别。

#include<iostream>
#include<set>
#include<iterator>
#include<algorithm>int main()
{const int size = 16;int a[size] = { 17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2 };std::multiset<int> intMultiset(a, a + size);	//用a来初始化INTMS容器实例std::ostream_iterator<int> output(std::cout, " ");//整型输出迭代子output,可通过cout输出用空格分隔的整数std::cout << "这里原来有" << intMultiset.count(17)<< "个数值17" << std::endl; intMultiset.insert(17); //插入一个重复的数17std::cout << "输入后这里有" << intMultiset.count(17) << "个数值17" << std::endl;std::multiset<int>::const_iterator result;result = intMultiset.find(18);//找到则返回所在位置,设找到返回与调end()返回的同样值if (result == intMultiset.end()){std::cout << "没找到值18" << std::endl;}else{std::cout << "找到值18" << std::endl;}std::cout << "intMultiset容器中有" << std::endl;copy(intMultiset.begin(), intMultiset.end(), output);//输出容器中全部元素std::cout << std::endl;
}

我们看到一开始多集合容器multiset中只有一个17,但在我们又插入了一个17后,多集合容器multiset中17的个数就变为2个了,所以多集合容器multiset中允许数据重复。因为多集合容器multiset的用法几乎与set相同,所以我们不在这里一一阐述,至于上述代码中出现的泛型算法copy和输出流迭代器在我以前的博客 迭代器 那一篇有讲到过,感兴趣的读者可以自行去学习。

六.使用set和multiset时的注意事项

我们知道set的底层是红黑树,每次我们插入一个新的数据后,红黑树都要按中序遍历的形式从小到大(默认是从小到大)的对数据进行排序,一般我们我们插入的数据的类型都是内置类型,例如 int char double ......,但是如果我们要插入的数据的类型是自定义类型时,红黑树就不知道该怎么对这些自定义类型的数据排序了。所以当我们向set中插入自定义类型的数据时,那么该自定义类型的类中就要提供比较运算符的重载函数,便于set进行排序。multiset的注意事项与set相同。

 

这篇关于C++ | STL 单集合容器set和多集合容器multiset的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/865109

相关文章

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二