【C++】STL - 集合 set

目录

一、什么是 set？

二、set 的定义

三、set 容器内的元素访问

四、set 的常用函数

一、什么是 set？

集合（set）是一个内部自动有序且不含重复元素的容器，它可以在需要删除重复元素的情况下大放异彩，节省时间，减少思维量。

set 就是关键字的简单集合，当只是想知道一个值是否存在时，set 是最有用的。set 内部采用的是一种非常高效的平衡检索二叉树：红黑树（Red-Black Tree），也称为 RB 树，RB 树的统计性能要好于一般平衡二叉树。在 set 中每个元素的值都唯一，而且系统能根据元素的值自动进行排序，set 中元素的值不能直接被改变。

顺序容器包括 vector、deque、list、forward_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力；关联容器包括 set、map。

两者的不同在于：

• 关联容器中的元素是按关键字来保存和访问的；而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的；
• 关联容器不支持顺序容器的位置相关的操作，因为关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
• 关联容器支持高效的关键字查找和访问。两个主要的关联容器（associative container）类型是 map 和 set。map 中的元素是一些关键字 — 值（key--value）对：关键字起到索引的作用，值则表示与索引相关联的数据。而在 set 中每个元素只包含一个关键字：set 支持高效的关键字查询操作 —— 检查一个给定关键字是否在 set 中。

标准库提供 set 关联容器分为：

1. 按关键字有序保存元素：set（关键字即值，即只保存关键字的容器）、multiset（关键字可重复出现的 set）；
2. 无序集合：unordered_set（用哈希函数组织的 set）、unordered_multiset（用哈希函数组织的 set，关键字可以重复出现）。

使用时需包含头文件：

    #include <set>
    using namespace std;

二、set 的定义

    set<类型名> 变量名;

其中，类型名可以是 int、double、char、struct，也可以是 STL 容器：vector、set、queue。 

    // 举例
    set<int> name;
    set<double> name;
    set<char> name;
    set<struct node> name;
    set<set<int>> name;

set 数组的定义和 vector 相同：

    set<int> arr[10];

三、set 容器内的元素访问

set 只能通过迭代器（iterator）访问：

    set<int>::iterator it;
    set<char>::iterator it;

这样，就得到了迭代器 it，并且可以通过 *it 来访问 set 里的元素。

注意：除了 vector 和 string 以外的 STL 容器都不支持 *(it + i) 的访问方式

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

    int main()
    {
        set<int> s;
        s.insert(5);
        s.insert(2);
        s.insert(6);
        for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        {
            cout << *it << " ";
        }
        return 0;
    }

    // 输出结果
    2 5 6 

可以看到，将原本无序的元素插入 set 集合，set 内部的元素自动递增排序，且去除了重复元素。

四、set 的常用函数

• find()：find(value) 返回 set 中 value 所对应的迭代器，即 value 的指针（地址），如果没找到则返回 end()

    #include <iostream>
    #include <set>
    using namespace std;
    int main() 
    {
        set<int> st;
        for (int i = 1; i <= 3; i++)
        {
            st.insert(i);
        }

        set<int>::iterator it = st.find(2); // 在set中查找2，返回其迭代器
        cout << *it << endl;

        // 以上可以直接写成
        cout << *(st.find(2)) << endl;
        return 0;
    }

    // 输出结果
    2
    2

• erase()：可以删除单个元素或删除一个区间内的所有元素

删除单个元素：

1. st.erase(it)，其中 it 为所需要删除元素的迭代器。时间复杂度为 O(1)，可以结合 find() 函数来使用。
2. st.erase(value)，其中 value 为所需要删除元素的值。时间复杂度为 O(logN)，N 为 set 内的元素个数。

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

    int main()
    {
        set<int> st;
        st.insert(100);
        st.insert(200);
        st.insert(100);
        st.insert(300);
        st.insert(500);

        // 删除单个元素
        st.erase(st.find(100)); // 利用find()函数找到100,然后用erase删除它
        st.erase(200);          // 删除值为200的元素
        for (set<int>::iterator it = st.begin(); it != st.end(); it++)
        {
            cout << *it << " ";
        }
        return 0;
    }

    // 输出结果
    300 500

删除一个区间内的所有元素：

1. st.erase(iteratorBegin, iteratorEnd)，其中 iteratorBegin 为所需要删除区间的起始迭代器， iteratorEnd 为所需要删除区间的结束迭代器的下一个地址，即取 [iteratorBegin, iteratorEnd)

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

    int main()
    {
        set<int> st;
        st.insert(100);
        st.insert(200);
        st.insert(100);
        st.insert(300);
        st.insert(500);
        set<int>::iterator it = st.find(300);

        // 删除一个区间内的所有元素
        st.erase(it, st.end());
        for (it = st.begin(); it != st.end(); it++)
        {
            cout << *it << " ";
        }
        return 0;
    }

    // 输出结果
    100 200

• equal_range()：返回一对迭代器，分别表示第一个大于或等于给定关键值的元素和第一个大于给定关键值的元素。这个返回值是一个 pair 类型，第一个是键的 lower_bound，第二个是键的 upper_bound。如果这一对定位器中哪个返回失败，则返回 end() 

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

    int main()
    {
        set<int> s;
        set<int>::iterator it;
        for (int i = 1 ; i <= 5; ++i)
        {
            s.insert(i);
        }
        for (it = s.begin() ; it != s.end() ; ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
        pair<set<int>::const_iterator, set<int>::const_iterator> pr;
        pr = s.equal_range(3);
        cout << "第一个大于等于3的数是："<< *pr.first << endl;
        cout << "第一个大于3的数是："<< *pr.second <<endl;
        return 0;
    }

    // 输出结果
    1 2 3 4 5
    第一个大于等于3的数是：3
    第一个大于3的数是：4

其他方法：

    begin();            // 返回指向第一个元素的迭代器
    end();              // 返回指向最后一个元素的后一个位置的迭代器
    clear();            // 清除所有元素
    count();            // 返回某个值元素的个数，用于判断set中是否有该元素
    size();             // 返回集合中元素的数目
    empty();            // 如果集合为空，返回true，否则返回false
    equal_range();      // 返回集合中与给定值相等的上下限的两个迭代器
    insert();           // 在集合中插入元素 
    erase();            // 删除集合中的元素
    find();             // 返回一个指向被查找到元素的迭代器
    get_allocator();    // 返回集合的分配器
    upper_bound();      // 返回大于某个值元素的迭代器
    lower_bound();      // 返回指向大于（或等于）某值的第一个元素的迭代器
    key_comp();         // 返回一个用于元素键值比较的函数
    value_comp();       // 返回一个用于比较元素间的值的函数
    max_size();         // 返回集合能容纳的元素的最大限值
    rbegin();           // 返回set反转后的开始指针(即原来的end-1)
    rend();             // 返回set反转后的结束指针(即原来的begin-1)
    swap();             // 交换两个集合变量