《21天学通C++》（第十九章）STL集合类（set和multiset）

为什么需要set和multiset:
1.自动排序： set和multiset会自动按照元素的值进行排序。
2.快速查找： 由于元素是有序的，set和multiset可以提供对元素的快速查找，通常是基于二叉搜索树实现的，查找操作的时间复杂度为O(log n)。
3.set的唯一性保证： set保证了容器中元素的唯一性，即不会有重复的元素。这在需要确保数据集中没有重复项时非常有用。

1.实例化std::set和std::multiset

需要添加头文件<set>

//默认类型实例化
std::set<int> mySet;
std::multiset<int> myMultiSet;//自定义类实例化（假设有MyClass类）
std::set<MyClass> mySet;
std::multiset<MyClass> myMultiSet;

2.在set或multiset中插入元素

可以使用insert()

下面以set为例子展示，multiset操作与其一致，但允许插入重复元素

#include<iostream>
#include <set>
int main(){std::set<int> mySet;// 插入单个元素mySet.insert(10);for(int num:mySet){std::cout<<num<<" ";}//输出结果为10std::cout<<std::endl;// 插入多个元素mySet.insert({30, 20, 40});for(int num:mySet){std::cout<<num<<" ";}//输出结果10 20 30 40，因为会插入元素后会自动排序std::cout<<std::endl;// 插入迭代器范围内的元素int arr[] = {50, 60, 70};mySet.insert(std::begin(arr), std::end(arr));for(int num:mySet){std::cout<<num<<" ";}//输出结果为10 20 30 40 50 60 70system("pause");return 0;
}

3.在set或multiset中查找元素

使用find()成员函数，用于查找容器中是否存在某个元素。它返回一个迭代器，如果元素存在，则指向找到的元素；如果元素不存在，则返回end()。

下面以set为例子展示，multiset操作与其一致，但若含有多个相同的符合条件的值，则只指向第一个

#include<iostream>
#include <set>
int main(){std::set<int> mySet = {1, 2, 3, 4, 5};auto it1 = mySet.find(3); // 查找元素 3if (it1 != mySet.end()) {// 找到元素std::cout << "Found: " << *it1 << std::endl;} else {// 元素不存在std::cout << "Not found" << std::endl;}//输出结果为“Found：3”auto it2 = mySet.find(6); // 查找元素 3if (it2 != mySet.end()) {// 找到元素std::cout << "Found: " << *it2 << std::endl;} else {// 元素不存在std::cout << "Not found" << std::endl;}//输出结果为“Not found”system("pause");return 0;
}

4.删除set或multiset中的元素

使用erase()成员函数，有以下几个重载版本
删除特定元素

mySet.erase(someValue); // 删除一个特定值

删除迭代器指向的元素

auto it = mySet.find(someValue);
if (it != mySet.end()) {mySet.erase(it); // 删除迭代器指向的元素
}

删除一定范围内的元素

mySet.erase(mySet.begin(), mySet.end()); // 使用迭代器指定边界

下面以multiset为例子，set操作类似

#include <iostream>
#include <set>int main() {// 实例化一个 std::multisetstd::multiset<int> myMultiSet = {1, 2, 3, 4, 4, 5};// 创建一个副本，删除指定值4auto count1 = myMultiSet;count1.erase(4);for(auto num:count1){std::cout<<num<<" ";}//输出结果为1 2 3 5，会把所有符合条件的都删除std::cout<<std::endl;// 创建一个副本，删除迭代器指向的元素3auto count2 = myMultiSet;auto it = count2.find(3);if (it != count2.end()) {count2.erase(it);}for(auto num:count2){std::cout<<num<<" ";}//输出结果为1 2 4 4 5std::cout<<std::endl;// 创建一个副本，删除一定范围的元素auto count3 = myMultiSet;count3.erase(count3.begin(), count3.find(3));//把开头到元素3(不包括3)都删除for(auto num:count3){std::cout<<num<<" ";}//输出结果为3 4 4 5system("pause");return 0;
}

5.std::unordered_set和std::unordered_multiset

从C++11起引入了这两种容器，它们是基于散列表（哈希表）实现的，相较于set和multiset，他们有以下优缺点：

优点

1. 平均时间复杂度： 由于哈希表的特性，在理想情况下，插入、删除和查找操作平均时间复杂度为O(1)，比set和multiset的O(log n)更快
2. 更快的访问速度： 在元素较多且冲突较少的情况下，访问速度更快

缺点

1. 最坏情况时间复杂度： 在最坏情况下，时间复杂度为O(n)，比set和multiset更慢
2. 不适合有序遍历： 这两种容器不保证元素的有序性