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

• 一、set简介
• 二、头文件
• 三、模板类
• • 四、set的内部结构
• 五、成员函数
• • 1、迭代器
  • 2、元素访问
  • 3、容量
  • 4、修改操作
  • ~~5、操作~~
  • 5、查找
  • 6、查看操作
• 六、demo
• • 1、查找find
  • 2、修改操作insert
  • 3、修改操作erase、clear
• 七、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

三、模板类

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、迭代器

2、元素访问

3、容量

4、修改操作

5、操作

5、查找

6、查看操作

六、demo

1、查找find

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

#include #include        // string#includeusing 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 #include        // string#includeusing 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 #includeusing 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 #includeusing 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 #include 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