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

相关文章

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

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