文章目录
一、STL 集合类
1.1 简介
在学习STL 集合类之前，我们先回顾一下数学中集合的概念。集合中的元素具有互异性和无序性。互异性是指集合中的元素各不相同，无序性是指元素与所在位置无关。
在C++中，为了方便各种数据操作和处理。在传统集合的概念上进行类一定的改造，将其封装为了STL 集合类。STL 集合类包含set、multiset、unordered_set 和 unordered_multiset。下面来分别介绍一下这4种集合类的区别：
- set。存于集合里的元素经过排序，且每个元素是唯一的。
- multiset。存于集合里的元素经过排序，且每个元素可以不唯一。
- unordered_set。存于集合里的元素未经排序，且每个元素是唯一的。
- unordered_multiset。存于集合里的元素未经排序，且每个元素可以不唯一。
总的来说， set 和 multiset 用于存储一组经过排序的元素，其查找元素的复杂度为O(log n)，而 unordered_set 和 unordered_multiset 中的元素是未经排序的，所以集合中元素的插入和查找时间是固定的。
set 和 multiset的区别在于，set 只能存储唯一的值，而 multiset 可以存储重复的值。
1.2 集合类的优缺点
对于需要频繁查找的应用程序来说，STL set 和 multiset 很有优势，因为其元素是经过排序的，因此查找的速度会更快。
这种优势的实现方式是，在向集合中插入元素时通过find()，找到合适的位置进行排序。因此，在新增（插入）元素时，无疑会增加额外的开销。好在是find()内部实现使用的是二叉树结构。该结构用于查找的时间复杂度往往在O(log n)左右。
缺点在于，set 和 multiset 不能像顺序容器（比如 vector）一样，可以使用其他元素替换给定位置的元素。这是因为 set 和 multiset 将把新元素同二叉树中的其他元素进行比较，进而将其放在其他位置。
总的来说，与顺序容器(比如 vector)相比：
- 优点是：set 和 multiset 内部由类似二叉树的结构实现，所以查找速度快。
- 缺点是：在新增元素时，会增加一点额外的开销；同时，不能使用其他元素直接替换给定位置的元素。
1.3 集合类的基本操作
STL set 和 multiset 都是模板类，要使用其成员函数，必须先实例化。
实例化 set 和 multiset 通常有以下三种方法：
（1）实例化一个特定类型的 set 或 multiset ，比如实例化一个 int 类型的集合。
set <int> setNums;
multiset <int> msetNUms;
（2）要声明一个包含Tuna对象的 set 和 multiset 。
set <Tuna> setNums;
multiset <Tuna> msetNUms;
（3）通过复制，实例化一个 set 或 multiset 。
set<int>setNums1(setNums); //把setNums赋给setNums1
multiset <int> msetNUms2(msetNUms);
以上三种方式，都没有指定排序标准。因此使用的都是默认谓词less，即升序排序。如果想指定排序的规则，需要提前声明：
# 升序排序
set<int, less<int>>setNums;
# 降序排序
set<int, greater<int>>setNums;
二、集合类常用的成员函数
常用的集合类成员函数包括：插入、查找、删除 等。使用这些成员函数，能够轻松的解决很多集合类数据操作问题，并且使你的代码变得更加简洁可读。下面就来分别来讲一讲这些常用的成员函数！
2.1 插入元素insert()
要在 set 和 multiset 中插入元素，可以使用成员函数 insert()，这个函数接受要插入的值。
#include<iostream>
#include<set>
using namespace std;
template <typename T>
void DisplayContents(const T& Input)
{
for(auto iElement = Input.cbegin();iElement != Input.cend(); ++iElement)
cout<<*iElement<<" ";
cout<<endl;
}
int main()
{
set <int> setIntegers;
multiset <int> msetIntegers;
setIntegers.insert(60);
setIntegers.insert(-1);
setIntegers.insert(300);
cout<<"显示内容到屏幕："<<endl;
DisplayContents(setIntegers);
msetIntegers.insert(setIntegers.begin(), setIntegers.end());
msetIntegers.insert(300);
cout<<"再插入一个元素后，显示内容到屏幕："<<endl;
DisplayContents(msetIntegers);
cout<<"300的数量是："<<msetIntegers.count(300)<<endl;
return 0;
}
运行结果：
2.2 查找元素find()
在 set 和 multiset 中，可以使用成员函数find()来查找相应的元素。multiset 可能包含多个相同的元素，因此对于 multiset，这个函数查找第一个与给定值匹配的元素。
#include<set>
#include<iostream>
using namespace std;
int main()
{
set<int> setNums;
//插入元素
setNums.insert(50);
setNums.insert(-48);
setNums.insert(6);
setNums.insert(160);
//显示集合元素
for (auto iElement=setNums.cbegin(); iElement != setNums.cend(); ++iElement)
cout<<*iElement<<endl;
//查找集合元素-1
auto iElementFound = setNums.find(-1);
if(iElementFound != setNums.end())
cout<<"Element "<<*iElementFound<<" found!"<<endl;
else
cout<<"Element -1 not found in setNums!"<<endl;
//查找集合元素6
auto anotherFind = setNums.find(6);
if(anotherFind != setNums.end())
cout<<"Element "<<*anotherFind<<" found!"<<endl;
else
cout<<"Element 6 not found in setNums!"<<endl;
return 0;
}
运行结果：
2.3 删除元素erase()
和大多数关联容器一样，当你想删除 set 和 multiset 中的元素时，可以使用成员函数erase()。
#include<iostream>
#include<set>
using namespace std;
template <typename T>
void DisplayContents(const T& Input)
{
for(auto iElement = Input.cbegin();iElement != Input.cend(); ++iElement)
cout<<*iElement<<" ";
cout<<endl;
}
int main()
{
multiset <int, greater<int>> msetNums;
msetNums.insert(46);
msetNums.insert(78);
msetNums.insert(-100);
msetNums.insert(-100);
msetNums.insert(8);
cout<<"msetNums 包含 "<<msetNums.size()<<" 个元素"<<endl;
cout<<"降序显示mseNums全部元素："<<endl;
DisplayContents(msetNums);
msetNums.erase(-100);
cout<<"删除-100后，显示mseNums全部元素："<<endl;
DisplayContents(msetNums);
return 0;
}
运行结果：
三、总结与归纳
3.1 牢记知识点
- STL set 和 multiset 容器针对频繁查找的情形进行了优化。
- multiset可存储多个值相同的元素，而set只能存储不同的值。
- 使用count()可获得元素包含特点值的个数。
- 使用size()可获得集合包含的元素个数。
- 在需要频繁插入而很少查找的情形下，不要使用set 和 multiset；在这种情况下，使用 vector 和 list 更合适。
3.2 问与答
问：如何声明一个其元素按降序排序的整型 set?
答：默认情况下使用升序，要声明一个其元素按降序排序的整型 set，需提前声明：
set<int, greater<int>>;
问：如果在一个字符串 set 中插入字符串 AI jun 两次，将会发生神码情况？
答：set 不能存储多个相同的值，因此 set 类的实现不允许插入第二个 AI Jun。如果一定要插入两次，可以使用multiset。
问：我使用函数 find 在 set 中找到了一个元素，并有一个指向该元素的迭代器。能否使用这个迭代器来修改它指向的元素的值。
答：不能，这是因为 set 会根据元素的值大小进行排序，因此不能将迭代器指向任一元素的值。应将指向 set 中的元素的迭代器视为 const 迭代器。