【c++丨STL】set/multiset的使用-阿里云开发者社区

前言

之前，我们已经探索了STL中的多个容器及容器适配器，如string、vector、list，以及stack和priority_queue等。今天，我们将进一步拓宽视野，深入学习STL中的容器——set及其变种multiset。

作为STL的重要组成部分，set以其独特的性质——元素自动排序且不重复，在解决许多实际问题时发挥着不可替代的作用。无论是处理需要唯一性的数据集合，还是实现高效的查找操作，set都以其简洁的接口和强大的功能赢得了开发者们的青睐。

一、序列式容器和关联式容器

之前我们学习的string、vector、list等容器都是序列式容器，它们的逻辑结构都是线性序列。对于序列式容器，它们的元素之间通常没有相关性，其元素按照逻辑顺序进行存储和访问。

而set和multiset是关联式容器，它虽然也可以存储数据，但与序列式容器不同的是，其逻辑结构通常是非线性的，元素之间存在紧密联系，元素按照关键字进行存储和访问。如果擅自修改某个元素或者移动元素的逻辑位置，就会破坏它的存储结构。

二、set和multiset简介

set（集合）和multiset（多重集合）是STL中的容器，分别用于处理唯一元素和允许重复元素的场景，它们的底层结构都是红黑树（一种自平衡二叉搜索树）。

set和multiset有以下共同特点：

1. 容器元素自动按照升序排列（也可通过传入第二个模板参数调整排序规则）。

2. 元素插入、删除、查找的时间复杂度均为O(logN)。

set和multiset的核心区别是：set不允许容器内有重复元素，能够达到去重的效果；而multiset支持插入重复元素。

鉴于set和multiset的接口功能几乎没有区别，且set更为常用，所以**接下来的内容将主要聚焦于set常用接口的使用方法**。当然，我们也会在适当的时候提及multiset，以便大家能够对比两者的异同，从而更好地根据实际需求做出选择。

我们在使用 set 或 multiset 时，需要引头文件，并且该容器定义在命名空间std当中。

set和multiset相关接口查阅：

三、set的默认成员函数

set显式实现的默认成员函数有三个：

构造函数(constructor)

c++14下，set有五种，其中较为常用的有以下四个：

函数原型	功能说明
set();	无参构造
set(InputIterator first, InputIterator last);	迭代器区间构造
set(const set& x);	拷贝构造，用一个set对象构造另一个set对象
set(initializer_list il);	初始化器构造

代码示例：

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

template<class T>
void print(const T& con)
{
   
    for (const auto& e : con)
    {
   
        cout << e << ' ';
    }
    cout << endl;
}

int main()
{
   
    set<int> s1;
    set<int> s2({
    6,0,2,8,4 });
    set<int> s3(s2);
    set<int> s4(s2.begin(), s2.end());
    cout << "s1:";
    print(s1);
    cout << "s2:";
    print(s2);
    cout << "s3:";
    print(s3);
    cout << "s4:";
    print(s4);
    return 0;
}

析构函数

析构函数帮助我们自动释放容器动态申请的空间。

赋值重载

将新内容分配给已经存在的容器，替换其当前内容。

代码示例：

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

int main()
{
   
    set<int> s1({
    4,8,2 });
    set<int> s2;
    s2 = s1;
    for (auto& e : s2)
    {
   
        cout << e << ' ';
    }
    cout << endl;
    return 0;
}

四、set的迭代器接口

与vector、list等容器相同，set也支持使用迭代器进行元素访问和遍历。

这里有三点需要注意：

1. set的迭代器是**双向迭代器**。

2. set迭代器进行顺序遍历的结果是**有序的，这归因于它采用了红黑树的中序遍历**算法。

3. 无论是使用普通迭代器还是const迭代器，都**无法修改set元素的值。（set元素的值不支持修改**）

set迭代器的使用方法与其他容器没什么区别，这里就不再赘述。

五、set的容量接口

empty

判断set容器是否为空。若为空，则返回true；否则返回false。

该函数不会以任何方式修改容器。

代码示例：

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

int main()
{
   
    set<int> s1;
    set<int> s2({
    1,2,3 });
    cout << s1.empty() << endl;
    cout << s2.empty() << endl;
    return 0;
}

size

返回set容器当中的元素个数。

代码示例：

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

int main()
{
   
    set<int> s1;
    set<int> s2({
    1,2,3 });
    cout << s1.size() << endl;
    cout << s2.size() << endl;
    return 0;
}

六、set的增删相关接口

insert

insert的功能是插入元素，支持单个值插入、指定位置插入（实际未必插入在指定位置，因为要保持有序性）、迭代器区间插入和初始化器插入。

注意：单个值插入函数的返回值是一个pair（二元组，之前的文章已经提到过），其具体内容如下：

当容器中没有相同值元素，则插入成功，返回值pair的第一个元素是指向新插入元素的迭代器，第二个元素是布尔类型，值为true；反之，当容器中已有相同值的元素，则意味着插入失败，返回值pair的第一个元素是指向已有元素的迭代器，第二个元素的值为false。

对于multiset而言，由于其允许相同元素存在，所以单个值插入接口的返回值是一个指向新插入元素的迭代器。

代码示例：

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

template<class T>
void print(const T& con)
{
   
    for (const auto& e : con)
    {
   
        cout << e << ' ';
    }
    cout << endl;
}

int main()
{
   
    set<int> s1({
    1,2,3 });
    multiset<int> s2({
    1,2,3 });
    auto a = s1.insert(1);
    auto b = s2.insert(1);
    cout << "s1.insert(1):" << a.second << endl;
    cout << "s2.insert(1):" << *b << endl;
    cout << endl;
    cout << "s1:";
    print(s1);
    cout << "s2:";
    print(s2);
    return 0;
}

erase

erase的功能是删除set容器内的元素，它支持按值删除，迭代器删除和迭代器区间删除。对于按值删除，函数的返回值是成功删除的元素个数，其他两个函数的返回值是指向被删除元素（或区间）下一个元素的迭代器。

对于multiset，如果有多个val值，则该函数会删除所有的val，并返回下一个元素的迭代器。

代码示例：

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

template<class T>
void print(const T& con)
{
   
    for (const auto& e : con)
    {
   
        cout << e << ' ';
    }
    cout << endl;
}

int main()
{
   
    set<int> s = {
    1,2,3,4,5,6,7,8,9,10 };
    cout << "s: ";
    print(s);
    cout << endl;
    cout << "迭代器删除" << endl;
    s.erase(s.begin());
    cout << "s: ";
    print(s);
    cout << endl;
    cout << "按值删除" << endl;
    cout << "被删除的元素个数：" << s.erase(1) << endl;
    cout << "s: ";
    print(s);
    cout << endl;
    cout << "被删除的元素个数：" << s.erase(2) << endl;
    cout << "s: ";
    print(s);
    cout << endl;
    cout << "迭代器区间删除" << endl;
    s.erase(s.begin(), s.end());
    cout << "s: ";
    print(s);
    return 0;
}

swap

交换两个set容器的内容。两个容器大小可能不同。

在调用成员函数之后，所有迭代器、引用和指针对交换后的对象仍然有效。

请注意，存在一个名称相同的非成员函数swap，它用与该成员函数类似的优化重载了该算法。

代码示例：

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

template<class T>
void print(const T& con)
{
   
    for (const auto& e : con)
    {
   
        cout << e << ' ';
    }
    cout << endl;
}

int main()
{
   
    set<int> s1 = {
    1,2,3 };
    set<int> s2 = {
    4,5,6 };
    cout << "s1: ";
    print(s1);
    cout << "s2: ";
    print(s2);
    s1.swap(s2);
    cout << endl << "交换后：" << endl;
    cout << "s1: ";
    print(s1);
    cout << "s2: ";
    print(s2);
    return 0;
}

clear

从set容器中删除所有元素，容器的大小变为0。

七、set的其他操作接口

find

find的功能是查找（按值查找）。在容器中搜索与val等效的元素，如果找到则返回指向查找到的元素迭代器，否则返回尾迭代器。

对于multiset，如果找到的元素在容器中有重复值，则函数返回中序遍历序列的第一个找到的元素的迭代器。

代码示例：

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

int main()
{
   
    set<int> s = {
    1,2,3,4,5 };
    int num = 0;
    while (cin >> num)
    {
   
        if (s.find(num) != s.end())
        {
   
            cout << "找到了！\n" << endl;
        }
        else
        {
   
            cout << "没找到\n" << endl;
        }
    }
    return 0;
}

count

count返回容器中值为val的元素个数。
因为set容器中的所有元素都是唯一的，所以该函数只能返回1或0，因此可以判断一个元素是否在set容器中。但对于允许出现重复元素的multiset，它还可以用于统计某元素的个数。

代码示例：

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

int main()
{
   
    set<int> s = {
    1,2,3 };
    multiset<int> ms = {
    1,2,2,2,3 };
    cout << s.count(2) << endl;
    cout << ms.count(2) << endl;
    return 0;
}

接下来要介绍的 lower_bound**、 upper_bound 和 equal_range 是multiset常用接口。**

lower_bound和upper_bound

返回一个迭代器，指向容器中第一个不在val值之前的元素（查找区间左端点）。

也就是说当容器内部有形如{val, val, val,...}的子序列时，返回第一个val的迭代器。

如果val应位于所有元素之前，则函数返回当前第一个元素的迭代器。

反之，若val应位于所有元素之后，则函数返回尾迭代器。

upper_bount函数返回一个迭代器，指向容器中被认为是val之后的第一个元素（查找区间右端点）。至于为什么不返回第一个不在val值之后的元素，是因为STL的区间都遵循“左闭右开”。

也就是说当容器内部有形如{val, val, val,...}的子序列时，返回最后一个val的下个元素的迭代器。

如果val应位于所有元素之前，则函数返回当前第一个元素的迭代器。

反之，如果val应位于所有元素之后，则函数返回尾迭代器。

代码示例：

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

int main()
{
   
    multiset<int> ms = {
    1,2,2,2,3 };
    auto begin = ms.lower_bound(2);
    auto end = ms.upper_bound(2);
    for (auto it = begin; it != end; it++)
    {
   
        cout << *it << ' ';
    }
    cout << endl;
    return 0;
}

equal_range

返回一个pair（两个迭代器），表示范围的边界（**注意左闭右开**），该范围包含容器中与val相等的所有元素。

如果val应位于所有元素之前，则返回的两个迭代器都指向第一个元素。

反之，如果val应位于所有元素之后，则返回的两个迭代器都是尾迭代器。

代码示例：

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

int main()
{
   
    multiset<int> ms = {
    1,2,2,2,3 };
    auto range = ms.equal_range(2);
    for (auto it = range.first; it != range.second; it++)
    {
   
        cout << *it << ' ';
    }
    cout << endl;
}

总结

通过本文的学习，我们深入了解了STL中的set容器及其变种multiset。set以其元素自动排序且不重复的特性，在需要唯一性数据集合和高效查找操作的场景中发挥着重要作用。

在了解set容器的基础上，之后我们会进一步引出STL中的另一个重要容器——map。与set类似，map也是关联式容器，其底层结构同样可以采用红黑树。不同的是，map存储的是键值对（key_value），且键（key）是唯一的，而值（value）可以是任意的。map容器以键为基准进行自动排序，并支持高效的查找、插入和删除操作。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

【c++丨STL】set/multiset的使用

前言

一、序列式容器和关联式容器

二、set和multiset简介

三、set的默认成员函数

构造函数(constructor)

析构函数

赋值重载

四、set的迭代器接口

五、set的容量接口

empty

size

六、set的增删相关接口

insert

erase

swap

clear

七、set的其他操作接口

find

count

lower_bound和upper_bound

equal_range

总结

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【c++丨STL】set/multiset的使用

前言

一、序列式容器和关联式容器

二、set和multiset简介

三、set的默认成员函数

构造函数(constructor)

析构函数

赋值重载

四、set的迭代器接口

五、set的容量接口

empty

size

六、set的增删相关接口

insert

erase

swap

clear

七、set的其他操作接口

find

count

lower_bound和upper_bound

equal_range

总结

热门文章

最新文章

相关课程

相关电子书