STL --- 2、容器 set 和multiset

std::set 和 std::multiset 都是 STL 中的关联容器，用于存储一组有序的元素。

1、std::set 和 std::multiset 特点

（1）std::set 中每个元素的键值都唯一，而 std::multiset 中可以有多个相同的键值。
（2）std::set 中的元素按照键值大小顺序是按照元素的值从小到大排列的。如果需要按照其他方式排序，可以使用自定义比较函数来实现。

（3）std::set 和 std::multiset 都提供了基本的插入、查找、删除等操作，以及迭代器遍历等功能。它们底层实现使用红黑树，因此插入、查找、删除等操作的时间复杂度都是 O(log n)。

（4）std::set 和 std::multiset 的使用方式类似，可以通过迭代器遍历来访问容器中的元素。

因此，std::set 适合用于需要快速查找、去重的场景，而 std::multiset 适合用于需要保存多个相同键值的场景。

2、std::set 和 std::multiset 常用的api

1. insert(value)：将一个值插入到set或multiset中。
2. erase(position)：删除set或multiset中指定位置的元素。
3. erase(value)：删除set或multiset中所有等于指定值的元素。
4. find(value)：查找set或multiset中是否存在等于指定值的元素，如果存在返回该元素的迭代器，否则返回end()。
5. count(value)：返回set或multiset中等于指定值的元素个数。
6. size()：返回set或multiset中元素的个数。
7. empty()：判断set或multiset是否为空。
8. clear()：清空set或multiset中的所有元素。
9. lower_bound(value)：返回set或multiset中第一个大于等于指定值的元素的迭代器。
10. upper_bound(value)：返回set或multiset中第一个大于指定值的元素的迭代器。
11. equal_range(value)：返回set或multiset中等于指定值的元素的区间，返回一个pair类型的迭代器，第一个元素是lower_bound返回的迭代器，第二个元素是upper_bound返回的迭代器。

3、std::set 和 std::multiset 的示例

#include <iostream>
#include <set>int main() {// std::set 示例std::set<int> mySet;// 插入元素mySet.insert(3);mySet.insert(1);mySet.insert(4);mySet.insert(1); // 重复元素不会被插入// 遍历元素for (int x : mySet) {std::cout << x << " ";}std::cout << std::endl;// 查找元素auto it = mySet.find(4);if (it != mySet.end()) {std::cout << "Found " << *it << std::endl;} else {std::cout << "Not found" << std::endl;}// std::multiset 示例std::multiset<int> myMultiSet;// 插入元素myMultiSet.insert(3);myMultiSet.insert(1);myMultiSet.insert(4);myMultiSet.insert(1); // 可以插入重复元素// 遍历元素for (int x : myMultiSet) {std::cout << x << " ";}std::cout << std::endl;// 查找元素auto it2 = myMultiSet.find(4);if (it2 != myMultiSet.end()) {std::cout << "Found " << *it2 << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

输出：

1 3 4
Found 4
1 1 3 4
Found 4

在上面的示例中，我们首先创建了两个空的 std::set 和 std::multiset。然后，我们使用 insert() 函数插入一些元素。对于 std::set，重复的元素不会被插入，而对于 std::multiset，可以插入重复的元素。最后，我们使用 find() 函数查找特定元素并输出结果。

需要注意的是，std::set 和 std::multiset 中元素的顺序是按照元素的值从小到大排列的。如果需要按照其他方式排序，可以使用自定义比较函数来实现。

4、std::map和set区别

std::map和std::set都是STL中的关联容器，但它们的主要区别在于：

（1）元素的类型：std::map存储的是键值对，即每个元素都包含一个键和一个值；而std::set只存储键值，即每个元素只包含一个键。

（2）元素的排序：std::map中的元素按照键进行排序，而std::set中的元素按照键进行排序，并且每个键都必须是唯一的。

（3）查找效率：由于std::map中的元素是按照键进行排序的，因此可以通过二分查找等高效算法进行查找；而std::set中的元素也是按照键进行排序的，但由于每个键都必须是唯一的，因此查找效率可能会受到影响。

（4）插入效率：由于std::map和std::set都是基于红黑树实现的，因此插入元素的效率都是O(logn)级别的。

总的来说，std::map适用于需要存储键值对，并且需要按照键进行排序的情况；而std::set适用于只需要存储键，并且需要按照键进行排序，并且每个键都必须是唯一的情况。