【STL十】关联容器——set容器、multiset容器

set和multiset会根据特定的排序准则，自动将元素排序。两者不同之处在于multiset允许元素重复而set不允许。（如下图）

一、set简介

• 和 map、multimap 容器不同，使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等。
• map、multimap 容器都会自行根据键的大小对存储的键值对进行排序，set 容器也会如此，只不过 set 容器中各键值对的键 key 和值 value 是相等的，根据 key 排序，也就等价为根据 value 排序。
• 使用 set 容器存储的各个元素的值必须各不相同。更重要的是，从语法上讲 set 容器并没有强制对存储元素的类型做 const 修饰，即 set 容器中存储的元素的值是可以修改的。但是，C++ 标准为了防止用户修改容器中元素的值，对所有可能会实现此操作的行为做了限制，使得在正常情况下，用户是无法做到修改 set 容器中元素的值的。

对于初学者来说，切勿尝试直接修改 set 容器中已存储元素的值，这很有可能破坏 set 容器中元素的有序性，最正确的修改 set 容器中元素值的做法是：先删除该元素，然后再添加一个修改后的元素。

二、头文件

#include<set>

三、模板类

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

四、set的内部结构

• set/multiset通常以平衡二叉树完成(balanced binary tree)；（如下图）

• 自动排序的主要优点在于令二叉树于查找元素时拥有良好效能。其查找函数具有对数复杂度。在拥有 1000 个元素的 set 或 multiset 中查找元素，二叉树查找动作（由成员函数执行）的平均时间为线性查找（由STL 算法执行）的 1/50。

• 但是，自动排序造成 set 和 multiset 的一个重要限制：你不能直接改变元素值，因为这样会打乱原本正确的顺序。
  因此，要改变元素值，必须先删除旧元素，再插入新元素。以下接口反映了这种行为:

  • Set 和 multiset 不提供任何操作函数可以直接访问元素。
  • 通过迭代器进行元素间接访问，有一个限制：从迭代器的角度看，元素值是常量。

五、成员函数

1、迭代器

成员函数	功能
begin()	同array容器
end()	同array容器
rbegin()	同array容器
rend()	同array容器
cbegin()	同array容器
cend()	同array容器
crbegin()	同array容器
crend()	同array容器

2、元素访问

成员函数	功能
operator[]	同array容器
at(n)	同array容器
front()	同array容器
back()	同array容器
data()	同array容器

3、容量

成员函数	功能
size()	同array容器
max_size()	同array容器
empty()	同array容器
reserve	同vector容器
capacity	同vector容器
shrink_to_fit	同vector容器

4、修改操作

成员函数	功能
clear()	同vector容器
insert()	同vector容器
insert_or_assign(C++17)	插入元素，或若键已存在则赋值给当前元素
emplace()	同vector容器
emplace_hint()	在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
try_emplace(C++17)	若键不存在则原位插入，若键存在则不做任何事
erase()	同vector容器
push_back()	同vector容器
emplace_back()	同vector容器
pop_back()	同vector容器
push_front()	同vector容器
emplace_front()	同vector容器
pop_front()	同vector容器
resize()	同vector容器
swap()	同vector容器
extract(C++17)	从另一容器释出结点
merge(C++17)	从另一容器接合结点

5、操作

成员函数	功能
merge()	list容器
splice()	list容器
remove(val)	list容器
remove_if()	list容器
reverse()	list容器
unique()	list容器
sort()	list容器

5、查找

成员函数	功能
count(key)	同map容器
find(key)	同map容器
contains (C++20)	同map容器
equal_range(key)	同map容器
lower_bound(key)	同map容器
upper_bound(key)	同map容器

6、查看操作

成员函数	功能
key_comp	同map容器
value_comp	同map容器

六、demo

1、查找find

• 返回值
  指向键等于 key 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

#include <iostream>
#include <string>       // string
#include<set>
using namespace std;
int main() {
    set <string> myset{
        "小b",
        "小c",
        "小a",
        "小d",
    };

    auto ite = myset.find("小d");
    cout << "find = " << *ite << endl;
    
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
        cout << *iter << endl;
    }

    return 0;
}

输出

find = 小d
小a
小b
小c
小d

2、修改操作insert

返回值

• lower_bound：指向首个不小于 key 的元素的迭代器。若找不到这种元素，则返回尾后迭代器
• upper_bound：指向首个大于 key 的元素的迭代器。若找不到这种元素，则返回尾后迭代器

正常场景

#include <iostream>
#include <string>       // string
#include<set>
using namespace std;
int main() {
    set <string> myset{
        "小b",
        "小c",
        "小a",
        "小d",
    };

    auto ite = myset.insert("小e");
    cout << *(ite.first) << " " << ite.second << endl;
    
    set<string> set2;
    set2.insert(myset.begin(), myset.end());

    for (auto iter = set2.begin(); iter != set2.end(); ++iter) {
        cout << *iter << endl;
    }

    return 0;
}

输出

小e 1
小a
小b
小c
小d
小e

3、修改操作erase、clear

• erase

set 类模板中，erase() 方法有 3 种语法格式，分别如下：

//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);

demo

#include <iostream>
#include<set>
using namespace std;
int main() {
    set <int> myset{ 1,2,3,4,5 };

    int num = myset.erase(2);
    cout << "num = " << num << endl;
    cout << "myset.size = " << myset.size() << endl << endl;
    
    set<int>::iterator ite = myset.erase(myset.begin());
    cout << "ite = " << *ite << endl;
    cout << "myset.size = " << myset.size() << endl << endl;


    set<int>::iterator ite2 = myset.erase(myset.begin(),--myset.end());
    cout << "ite = " << *ite2 << endl;
    cout << "myset.size = " << myset.size() << endl;

    return 0;
}

输出

num = 1
myset.size = 4


ite = 3
myset.size = 3


ite = 5
myset.size = 1

• clear
  语法格式如下：

void clear();

显然，该方法不需要传入任何参数，也没有任何返回值。

#include <iostream>
#include<set>
using namespace std;
int main() {
    set <int> myset{ 1,2,3,4,5 };
    cout << "myset.size = " << myset.size() << endl;
 
    myset.clear();

    cout << "myset.size = " << myset.size() << endl;

    return 0;
}

输出

myset.size = 5
myset.size = 0

七、multiset

和set 容器不同的是，multiset 容器可以存储多个值相同的元素。

• 模板类

template < class T,                        // 存储元素的类型
           class Compare = less<T>,        // 指定容器内部的排序规则
           class Alloc = allocator<T> >    // 指定分配器对象的类型
           > class multiset;

• demo

#include <iostream>
#include <set>
using namespace std;
int main() {
    std::multiset<int> mymultiset{ 1,2,2,2,3,4,5 };
    cout << "multiset size = " << mymultiset.size() << endl;
    cout << "multiset count(2) =" << mymultiset.count(2) << endl;

    //删除容器中所有值为 2 的元素
    int num = mymultiset.erase(2);
    cout << "删除了 " << num << " 个元素 2" << endl;
    //输出容器中存储的所有元素
    for (auto iter = mymultiset.begin(); iter != mymultiset.end(); ++iter) {
        cout << *iter << " ";
    }
    return 0;
}

• 输出

multiset size = 7
multiset count(2) =3
删除了 3 个元素 2
1 3 4 5

参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container