⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口

这篇具有很好参考价值的文章主要介绍了⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类 C++ 表情包趣味教程 👉 《C++要笑着学》

💭 写在前面：好久没更新了，C++ 系列教程的更新速度真的是快赶得上 "年更" 了，最近这个专栏订阅量破 1200 了，也有不少小伙伴要接着往下看，所以我得好好更新！不能烂尾啊是吧。上一章我们讲解了二叉搜索树，本章我们将继续讲解 STL，介绍 set 类和 multiset，对一些常用的接口进行讲解，为后续讲解红黑树数据结构做必要的铺垫。

Ⅰ. Set 类

0x00 引入：Set 介绍

0x01 元素的插入（insert 接口）

0x02 Set 同样支持范围 for

0x03 元素的查找（find 接口）

0x04 判断元素是否在集合中（count 接口）

0x05 元素的删除（erase 接口）

0x06 区间查找：lower_bound 和 upper_bound 接口

Ⅱ. multiset 类

0x00 引入：不去重的 set

0x01 multiset 的用法

0x02 multiset 的删除（erase 接口）

0x03 multiset 的查找（find 接口）

Ⅰ. Set 类

0x00 引入：Set 介绍

template < class T,                     // set::key_type/value_type
           class Compare = less<T>,     // set::key_compare/value_compare
           class Alloc = allocator<T>   // set::allocator_type
           > class set;

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类通过插入新的元素来扩展容器，有效地通过插入的元素数量增加容器的大小。

因为集合中的元素是唯一的，插入操作检查每个插入的元素是否等同于已经在容器中的元素。

如果是，则不插入该元素，返回一个到这个现有元素的迭代器（如果该函数返回一个值）。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类在内部，集合容器保持其所有元素按照其比较对象指定的标准进行排序。

这些元素总是按照这个排序插入到它各自的位置，是 "排序 + 去重" 的。

🔍 官方文档：https://cplusplus.com/reference/set/set/
📜 头文件：#include <set>

的底层是二叉搜索树再平衡的，是基于红黑树实现的，可归类到二叉搜索树中：

"Sets are typically implemented as binary search trees (官方文档) "

0x01 元素的插入（insert 接口）

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类下面我们来简单来一下的插入，调用的 insert 接口：

pair<iterator,bool> insert (const value_type& val);
iterator insert (iterator position, const value_type& val);

template <class InputIterator>  
    void insert (InputIterator first, InputIterator last);

💬 代码演示：insert()

我们通过 insert 接口将数据插入到中，然后使用迭代器将数据打印出来。

void test_set1() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    // 排序 + 去重
    set<int>::iterator it = s.begin();
    while (it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

int main(void)
{
    test_set1();

    return 0;
}

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类

我们发现确实有去重的效果，这和数学中的集合 (set) 是一样的，集合元素具有 "惟一性" 。

所以，如果插入的元素已经存在于里了，就不插入了。

不仅如此，我们是按照 4,5,2,1,3,3 的顺序依次插入的，它还会自动帮你排好序：

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类因此，是 "排序 + 去重" 的！

0x02 Set 同样支持范围 for

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类很好！既然支持迭代器，那自然也是支持范围 for 的！

从底层的角度 "范围 for" 其实就是迭代器，编译器处理完之后都是一样的，所以自然也是支持的。

💬 代码演示：使用范围 for

void test_set1() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);


    // 支持范围 for
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
}

0x03 元素的查找（find 接口）

下面再介绍一下 find 接口，如果这个元素被找到就会返回 val 的迭代器，否则返回 end。

iterator find (const value_type& val) const;

💬 代码演示：find 的使用

void test_set2() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    set<int>::iterator pos = s.find(2);
    if (pos != s.end()) {
        cout << "找到了" << endl;
    }
}

我们现在用下算法中的 find 接口，看看和中的 find 的写法有什么区别？哪个更好：

pos = find(s.begin(), s.end(), 2);
if (pos != s.end()) {
    cout << "找到了" << endl;
}

algorithm 中的 find 是暴力查找的方式实现的，从 begin 查到 end，其时间复杂度为。

而中的 find 的时间复杂度是，查找效率的差别可谓是天壤之别！

"谅尔等腐草之荧光，如何比得上天空之皓月？"

0x04 判断元素是否在集合中（count 接口）

介绍一下 count 接口，有时我们需要判断元素在不在集合中，使用 count 往往比使用 find 方便。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类 count 非常的简单粗暴，如果在集合中则返回1，不在则返回 0。

size_type count (const value_type& val) const;

💬 代码演示：查看 3 在不在集合中

void test_set3() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    if (s.count(3)) {
        cout << "3在" << endl;
    }
}

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类这里如果用 find 就没这么方便了，你还需要做一个判断：

if (s.find(3) != s.end()) {
    cout << "3在" << endl;
}

0x05 元素的删除（erase 接口）

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类 erase 支持三种，分别是在某个位置删除，删除一个值和删除一个区间：

void erase (iterator position);
size_type erase (const value_type& val);
void erase (iterator first, iterator last);

我们下面先讲第三种，删除一个区间，实际上这一种用的是比较少的，因为比较麻烦……

💬 代码演示：通过 find 查找 pos 位置，然后删除（迭代器）

void test_set2() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    cout << "当前集合元素: ";
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    int x = 0;
    while (1) {
        cout << "请输入要删除的元素:";
        cin >> x;

        // 查看要删除的元素在不在集合中
        set<int>::iterator pos = s.find(x);
        if (pos != s.end()) {
            // 在集合中，删除
            s.erase(pos);
            cout << "成功删除: " << x << endl;

            // 打印删除后的结果
            cout << "删除后: ";
            for (auto e : s) {
                cout << e << " ";
            }
            cout << endl;
        }
        else {
            // 不在集合中，提示删除失败
            cout << "删除失败！" << x << "不在集合中。" << endl;
        }
    }
}

当然了，还可以直接给 erase 一个值进行删除，这个用法相较于迭代器就简单许多！

"在就删，不在就不动。"

💬 代码演示：erase 直接删除给定元素

void test_set3() {
    set<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    cout << "当前集合元素: ";
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    s.erase(3);   // 直接删除3
    cout << "删除后: ";
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
}

❓ 思考：那迭代器的方式删除和直接删除有什么区别呢？

💡 解答：迭代器 find + erase(pos) 的是找到了再删，我们一般和 find 搭配使用，因为如果这个元素不存在我们还强硬调用 erase 删除就会引发报错。而 erase(x) 就比较好了，直接删，就算这个值不存在也不会报错。

0x06 区间查找：lower_bound 和 upper_bound 接口

"适合确定范围"

iterator lower_bound(const key_type& key);

lower_bound() 用于在指定区域内查找不小于 (大于等于) 目标值的第一个元素。

返回一个指向集合中第一个大于等于给定值的元素的迭代器，如果找不到，则返回 end。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类即获取集合中任意元素的下界：

$⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类$

💬 代码演示：用 lower_bound 查找第一个不小于 25 的元素

#include <iostream>
#include <set>
using namespace std;

int main(void) 
{
    set<int> s = { 10, 20, 30, 40, 50 };

    // 使用 lower_bound 查找第一个不小于 25 的元素
    auto it = s.lower_bound(25);

    // 输出结果
    if (it != s.end()) {
        cout << "第一个不小于 25 的元素是: " << *it << endl;
    }
    else {
        cout << "未找到不小于 25 的元素" << endl;
    }

    return 0;
}

🔑 解读：lower_bound(25) 会返回一个指向集合中第一个不小于 25 的元素的迭代器。在集合{10, 20, 30, 40, 50} 中，第一个不小于 25 的元素是 30，所以输出结果是30。

可以用来干什么呢？如果我们需要删除大于等于 x 的所有元素，我们就可以用到这个接口了。

💬 代码演示：删除大于等于 x 的所有元素： $⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类$

void test_set4() {
    set<int> s = { 10, 20, 30, 40, 50 };
    cout << "删除前: ";
    for (auto e : s) {
        cout << e << " ";
    } cout << endl;


    int x = 0;
    cout << "请输入x: ";
    cin >> x;

    auto it = s.lower_bound(x);  // 找到第一个不小于x的元素
    s.erase(it, s.end());        // 迭代器区间删除

    cout << "删除后: ";
    for (auto e : s) {
        cout << e << " ";
    } cout << endl;
}

🔑 解读：接收 x 的值为 30 之后，就从 lower_bound 的位置开始作为迭代器的起始位置，end 作为结束位置，调用迭代器版本的 erase 就可以做到 30, 40, 50 都删除的效果，最后保留 10, 20。

还有一个 upper_bound 接口，在指定范围内查找大于目标值的第一个元素，不包含等于。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类这两个接口就是为了迎合迭代器的 "左闭右开" 而配备的，可以结合使用。

💬 代码演示：删除区间

void test_set5() {
    set<int> s = { 10, 20, 30, 40, 50 };
    cout << "删除前: ";
    for (auto e : s) {
        cout << e << " ";
    } cout << endl;
        

    int x = 0, y = 0;
    cin >> x >> y;
    auto left_it = s.lower_bound(x);
    auto right_it = s.upper_bound(y);
    s.erase(left_it, right_it);

    cout << "删除后: ";
    for (auto e : s) {
        cout << e << " ";
    } cout << endl;
}

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类感兴趣的朋友可以看下 lower_bound 的底层实现：

template <class ForwardIterator, class T>
ForwardIterator lower_bound (
    ForwardIterator first, 
    ForwardIterator last, 
    const T& val
    )
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = distance(first,last);
    while (count>0)
    {
        it = first; step=count/2; advance (it,step);
        if (*it<val) {
            first=++it;
            count-=step+1;
        }
        else count=step;
    }
    return first;
}

emmm，是个很经典的二分查找算法！使用了 advance 函数来跳过部分区间~

Ⅱ. multiset 类

0x00 引入：不去重的 set

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类如果我们想让不去重，我们就可以使用，使用方法和 Set 大差不差。

Set 是 "排序 + 去重"，但 multiset 是 "排序 + 不去重"，也就是说 multiset 允许元素重复！

0x01 multiset 的用法

multiset 就在 Set 类中，所以头文件就是 #include <set>

💬 代码演示：multiset 的插入

#include <iostream>
#include <set>
using namespace std;

void test() {
    multiset<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);


    // 支持范围 for
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
}

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类可以看到，是不去重的，就给你排个序，已经有的元素也会继续插入。

0x02 multiset 的删除（erase 接口）

因为 Set 不重复，所以 erase 就删除指定元素，但 multiset 是允许冗余的。

⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类,C++要笑着学,c++,开发语言,C++要笑着学,set类,multiset类所以 multiset 的 erase 接口会把所有指定元素删掉：

void test() {
    multiset<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);

    cout << "删除前: ";
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    s.erase(3);    // 会把所有的3都杀了

    cout << "删除后: ";
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
}

0x03 multiset 的查找（find 接口）

multiset 的 find 如果要查找的元素在集合中有多个，会返回中序的第一个，假设我们要 find(3)：

💬 代码演示：find 接口

void test() {
    multiset<int> s;
    s.insert(4);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(3);
    s.insert(3);
    s.insert(3);   // 一共有3个3

    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 返回的是中序的第一个
    auto pos = s.find(3);
    while (pos != s.end()) {
        cout << *pos << " ";
    }
}

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2023.12.12
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！

📜 参考资料

C++reference[EB/OL]. []. http://www.cplusplus.com/reference/.

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

比特科技. C++[EB/OL]. 2021[2021.8.31]. 文章来源地址https://www.toymoban.com/news/detail-767774.html

到了这里，关于⚡【C++要笑着学】(30) 集合类：set 类 | 元素的插入和删除 | lower_bound 接口 | upper_bound 接口 | multiset 类的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！