1.set容器+(multiset)介绍

1.1 介绍

 集合是按照特定顺序存储唯一元素的容器。
 在集合中，元素的值也标识它(值本身就是键，类型为T)，并且每个值必须是唯一的。集合中元素的值在容器中一次就不能修改(元素总是const)，但可以从容器中插入或删除它们。
 在内部，集合中的元素总是按照由其内部比较对象(Compare类型)指示的特定严格弱排序标准排序。
 在按键访问单个元素时，Set容器通常比unordered_set容器慢，但它们允许基于顺序对子集进行直接迭代。
 集合通常实现为二叉搜索树。

1.2 简单解析

 A. 头文件: set
 B. 关键区分：
 集合容器set : 存储唯一元素(值本身就是键，重复添加进入无效) + 内部集合有序(内部元素对象是有序储存的)
 集合容器multiset : 可以存储多个重复元素(可以重复添加进入集合当中) + 内部集合有序(内部元素对象是有序储存的)
 两者核心区别点就只在于multiset可以重复存储多个相同元素，而对于set来说其内部容器当中的元素都是唯一不可重复的。
 C. 常用情景
 常用于数字问题的计数，去重，搜索等相关操作。

2.迭代器操作(Iterator)

 set.begin() —— 返回容器头部元素迭代器
 set.end() —— 返回容器尾部元素下一位置的迭代器

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> s; // 内部有序
    s.insert(1);s.insert(3);s.insert(2);
    cout << * s.begin() << endl;
    // 输出结果 : 1
    for(auto it = s.begin(); it != s.end(); it ++ ){
        cout << * it << ' ';
    }
    // 输出结果 : 1 2 3
}

 细节: set的begin()和end()两种迭代器操作都不支持进行+/-操作进行迭代器的访问位置转移(区别与vector)，都会直接报错

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> s;
    s.insert(1);s.insert(3);s.insert(2);
    set<int> :: iterator it;
    // no match for 'operator+' (operand types are 'std::set<int>::iterator' {aka 'std::_Rb_tree_const_iterator<int>'} and 'int')|
    for(it = s.begin() + 1; it != s.end(); it ++ ){
        cout << *it << endl;
    }
}

3.容量操作(Capacity)

 set.empty() —— 返回容器是否为空，为空返回True，否则为 false
 set.size() —— 返回容器内部元素个数
 set.max_size() —— 返回容器最大存储容量

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> s;
    s.insert(1);s.insert(3);s.insert(2);s.insert(1); // 插入元素
    cout << s.empty() << endl;
    // 输出: 0(false),不为空
    cout << s.size() << endl;
    // 输出: 3 , 因为set容器重复添加相同元素是无效的
    cout << s.max_size() << endl;
    // 输出: 461168601842738790

    multiset<int> ms;
    ms.insert(1);ms.insert(3);ms.insert(2);ms.insert(1);
    cout << ms.size() << endl;
    // 输出: 4 , multiset可以重复添加相同元素
}

4.修改操作(Modifiers)

 set.insert() —— 向容器当中插入元素
 set.erase() —— 删除容器当中所有值为 x 的元素
 set.clear() —— 删除容器当中所有元素
 set.swap() —— 交换两个容器当中的元素

#include<iostream>
#include<set>
using namespace std;
int main(){
    multiset<int> ms, t; // 内部有序
    ms.insert(1);ms.insert(3);ms.insert(2);ms.insert(1);
    for(auto it = ms.begin(); it != ms.end(); it ++ )
        cout << * it << ' ';
    // 输出 : 1 1 2 3
    cout << '\n';

    ms.erase(1); // 删除所有元素 1
    for(auto it = ms.begin(); it != ms.end(); it ++ )
        cout << * it << ' ';
    // 输出 : 2 3
    cout << '\n';

    swap(ms, t);// 元素内部元素被交换
    cout << ms.size() << ' ' << t.size() << endl;
    // 输出 : 0 2

    t.clear();
    cout << t.size() << endl;
    // 输出 : 0 ,被清空
}

5.其余操作(Operation)

 set.find() —— 得到指定元素的迭代器,若不存在返回 end 迭代器
 set.count() —— 查找指定元素的个数
 set.lower_bound() —— 查找第一个大于等于元素x的迭代器位置，若不存在返回 end 迭代器
 set.upper_bound() —— 查找第一个大于元素x的迭代器位置，若不存在返回 end 迭代器

#include<iostream>
#include<set>
using namespace std;
int main(){
    multiset<int> ms, t;
    set<int> s;
    ms.insert(1);ms.insert(3);ms.insert(2);ms.insert(1);
    cout << * ms.find(1) << endl;
    // 输出 1
    if(ms.find(5) == ms.end()) puts("不存在这个元素");
    // 输出 不存在这个元素

    cout << ms.count(1) << endl;
    // 输出 2, 有两个元素1

    cout <<  * ms.lower_bound(2) <<endl;
    // 输出 2
    if(ms.lower_bound(5) == ms.end()) puts("无法找到");
    // 输出 无法找到
}