当前位置: 首页 > article >正文

专业视角:set 和 multiset的原理与应用解析

文章目录

  • 前言
    • 关联式容器
    • 键值对
    • 树形结构的关联式容器
  • set
    • 1. `set` 的定义
    • 注意以下八点:
    • 2. `set` 的常用操作
    • 3. `set` 的迭代器
    • 4. `set` 的底层实现
    • 5. 自定义排序(比较器)
    • 6. `set` 与 `multiset` 的区别
    • 7. 示例:`set` 的完整代码
  • multiset

前言

关联式容器

在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身

那什么是关联式容器?它与序列式容器有什么区别?

关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的

键值对,在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代

键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然

有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应

该单词,在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义:

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

树形结构的关联式容器

根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构哈希结构。树型结

构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使

用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一

个容器。

set

1. set 的定义

set 是 C++ 标准库中的一个关联容器,它存储的是唯一的元素,并且自动按一定的顺序排列元素。它通常基于平衡二叉搜索树(如红黑树)实现,提供 <u>O(log n)</u> 的查找、插入和删除时间复杂度。

特别记住两点:不重复,有序!

vectorlist 等容器不同,set 会自动维护元素的顺序,通常是升序排序,但可以通过自定义比较函数来改变排序规则。

  • set的模板参数列表:

T: set中存放元素的类型,实际在底层存储<value, value>的键值对。

Compare:set中元素默认按照小于来比较,也可以自己定义比较方式。

Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理

构造方式:


    // 1. 默认构造函数
    // 创建一个空的 set,元素类型为 int,使用默认的比较函数 less<int>
    set<int> set1;

    // 2. 范围构造函数
    // 使用迭代器指定的范围来初始化 set
    vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    set<int> set2(vec.begin(), vec.end());
    // 由于 set 中元素唯一,重复元素会被自动去除,且会按升序排列


    // 3. 拷贝构造函数
    // 创建一个新的 set,它是另一个 set 的副本
    set<int> set3(set2);

    // 4. 移动构造函数
    // 从另一个 set 中移动元素到新的 set 中,原 set 会变为空
    set<int> set4(move(set3));

    // 5. 初始化列表构造函数
    // 使用初始化列表来初始化 set
    set<int> set5 = {10, 20, 30, 40, 50};
  1. set是按照一定次序存储元素的容器
  2. 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。
    set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行
    排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对
    子集进行直接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现的。

注意以下八点:

1. 与 map/multimap** 的区别:set 中只存 **value

  • 区别
    • mapmultimap 是键值对容器,每个元素是一个 <key, value> 对。
    • set 中存储的仅是 value,但底层实现实际上将 value 视为 <value, value> 的键值对,这样可以复用相同的底层数据结构(如红黑树)。
  • 插入元素
std::set<int> s;
s.insert(5);  // 只插入 value,而不是 <key, value>
- `set` 中插入的只是单个值,而不是键值对。

2. 插入元素时,不需要构造键值对

  • 由于 set 只需要存储 value,插入时直接提供单个值即可。底层数据结构会将其视为键值对 <value, value>,但用户无需关心这些细节。

示例:

std::set<int> s;
s.insert(10);  // 只需要传递单个值
s.insert(20);  // 不需要键值对

这种简化让 set 使用起来更加方便,因为它的重点是值本身,而不是键值关联。


3. set 中的元素不可以重复

  • 特点
    set 保证存储的所有元素是唯一的。
  • 实现方式
    • 当插入一个元素时,set 会根据比较规则(通常是 < 运算符)检查是否已经存在。
    • 如果存在,则插入失败。

示例

std::set<int> s;
s.insert(5);  // 插入成功
s.insert(5);  // 插入失败,值已经存在

应用场景

  • 去重。当需要去除数组或序列中的重复元素时,可以使用 <font style="color:rgba(0, 0, 0, 0.85);">std::set</font><font style="color:rgba(0, 0, 0, 0.85);">std::unordered_set</font>。将一组重复元素转化为唯一集合:
std::vector<int> v = {1, 2, 2, 3, 4, 4};
std::set<int> s(v.begin(), v.end());  // 自动去重

4. 使用 set 的迭代器遍历,可以得到有序序列

  • 特点
    set 自动维护元素的顺序(通常是升序)。
  • 遍历方式
    使用迭代器(begin()end())可以顺序访问元素。

示例

std::set<int> s = {3, 1, 2};
for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";  // 输出:1 2 3
}

5. 默认按照“小于”比较排序

  • 排序规则
    默认情况下,set 按照 < 运算符来比较元素。
  • 自定义规则
    可以通过传入自定义比较器来改变排序方式。

示例:默认升序排序

std::set<int> s = {3, 1, 2};
for (int x : s) {
    std::cout << x << " ";  // 输出:1 2 3
}

自定义降序排序

std::set<int, std::greater<int>> s = {3, 1, 2};
for (int x : s) {
    std::cout << x << " ";  // 输出:3 2 1
}

6. 查找某个元素的时间复杂度为 O(log₂ n)

  • 原因
    • set 底层实现基于红黑树(自平衡二叉搜索树),其深度为 O(log₂ n)
    • 插入、删除和查找的时间复杂度都与树的高度成正比,因此为 O(log₂ n)

示例

std::set<int> s = {3, 1, 2};
auto it = s.find(2);  // 查找值为 2 的元素
if (it != s.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Not found!" << std::endl;
}

7. set 中的元素不允许修改

  • 原因
    • set 的底层实现依赖元素的排序规则。如果允许修改元素的值,可能破坏集合的有序性。
    • 一旦元素被插入,红黑树会根据该值的位置平衡树的结构。如果值被修改,这种平衡可能失效。

示例

std::set<int> s = {1, 2, 3};
auto it = s.find(2);
// *it = 5;  // 错误,不能直接修改元素

如果需要修改 set 中的元素,必须先删除该元素,再插入修改后的值:

s.erase(it);  // 删除元素
s.insert(5);  // 插入新值

8. 底层实现使用红黑树

  • 红黑树简介
    红黑树是一种自平衡二叉搜索树,具有以下特点:

这些规则确保树的高度在 O(log₂ n) 范围内,从而保证插入、删除、查找操作的高效性。

- 每个节点要么是红色,要么是黑色。
- 树根是黑色。
- 红节点的子节点必须是黑色(即红节点不能连续)。
- 从根节点到任何叶子节点的路径中,黑节点数量相同。

红黑树在 set 中的作用

  • 确保 set 的元素总是有序。
  • 保证查找、插入、删除的时间复杂度为 O(log₂ n)

2. set 的常用操作

  • 插入元素insert() 方法插入一个元素。如果元素已经存在,则插入会失败,set 保证元素唯一性。
std::set<int> s;
s.insert(1);  // 插入元素 1
s.insert(2);  // 插入元素 2
s.insert(1);  // 插入失败,因为 1 已经存在
  • 删除元素erase() 方法用于删除指定的元素或通过迭代器删除元素。
s.erase(1);  // 删除元素 1
  • 查找元素:使用 find() 查找元素,如果找到返回指向该元素的迭代器,若找不到返回 end() 迭代器。
auto it = s.find(2);  // 查找元素 2
if (it != s.end()) {
    std::cout << "Found: " << *it << std::endl;
}
  • 访问元素set 中的元素不能通过下标访问,必须使用迭代器。
for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";  // 输出 set 中的元素
}
  • 大小和空检查size() 方法返回容器中元素的个数,empty() 判断容器是否为空。
std::cout << "Size: " << s.size() << std::endl;
if (s.empty()) {
    std::cout << "Set is empty." << std::endl;
}

lower_bound(value)

功能:返回指向第一个**不小于 **value 的元素的迭代器。如果容器中不存在这样的元素,则返回指向 end() 的迭代器。

用法:常用于查找某个值或**第一个****大于等于**该值的元素。

示例代码


    set<int> s = {10, 20, 30, 40, 50};
    int value = 25;
    auto it = s.lower_bound(value);  // 查找第一个不小于25的元素

    if (it != s.end()) {
        cout << "Lower bound of " << value << ": " << *it << endl;  // 输出 30
    } else {
        cout << "No element found." << endl;
    }

upper_bound(value)

  • 功能:返回指向**第一个大于**** ****value** 的元素的迭代器。如果容器中不存在这样的元素,则返回指向 end() 的迭代器。
  • 用法:常用于查找某个值的下一个元素,或第一个大于该值的元素。

示例代码

    set<int> s = {10, 20, 30, 40, 50};

    int value = 25;
    auto it = s.upper_bound(value);  // 查找第一个大于25的元素

    if (it != s.end()) {
        cout << "Upper bound of " << value << ": " << *it << endl;  // 输出 30
    } else {
        cout << "No element found." << endl;
    }

3. set 的迭代器

set 提供了双向迭代器,允许遍历容器中的元素。

  • begin():返回指向容器第一个元素的迭代器。
  • end():返回指向容器尾后位置的迭代器,即指向容器中最后一个元素的下一个位置。
  • rbegin():返回指向容器最后一个元素的反向迭代器。
  • rend():返回指向容器第一个元素前一个位置的反向迭代器。

示例:

std::set<int> s = {3, 1, 2};

for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";  // 输出:1 2 3
}

std::cout << std::endl;

for (auto it = s.rbegin(); it != s.rend(); ++it) {
    std::cout << *it << " ";  // 输出:3 2 1
}

4. set 的底层实现

  • set 是基于平衡二叉搜索树(如红黑树或 AVL 树)实现的,这使得 set 能够提供 O(log n) 的查找、插入和删除操作。
  • 每个节点包含一个元素和指向左右子节点的指针。树是自平衡的,即插入或删除操作后,树会通过旋转操作保持平衡,保证操作的时间复杂度为 O(log n)

5. 自定义排序(比较器)

默认情况下,set 会按升序排列元素。如果想要按降序排列,或者按自定义规则排列,可以传入自定义的比较器。

例如,按降序排列:

#include <set>

std::set<int, std::greater<int>> s;  // 使用 greater<int> 进行降序排列
s.insert(3);
s.insert(1);
s.insert(2);

for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";  // 输出:3 2 1
}

6. setmultiset 的区别

1. 元素唯一性

  • set:不允许重复的元素。
  • multiset:允许存储重复的元素。

2. 插入规则

  • set:插入时会检查是否已有相同的元素,如果存在,则插入失败。
  • multiset:可以插入相同的元素,multiset 会记录每个重复值。

3. 元素计数

  • set:每个值在集合中最多出现一次,count() 的返回值是 01
  • multiset:可以存储相同的元素,count() 返回指定值的出现次数。

4. 查找和删除

  • set
    • find():返回指定元素的迭代器(如果存在)。
    • erase():删除指定值的唯一实例。
  • multiset
    • find():返回指向第一个匹配值的迭代器。
    • erase():删除某个值的所有实例,或者通过迭代器删除指定的单个实例。

5. 其他特性

  • 两者底层都使用红黑树,时间复杂度为 O(log n)
  • 都是有序容器,默认按升序排列元素。
#include <iostream>
#include <set>

int main() {
    // 创建 set 和 multiset
    std::set<int> mySet;
    std::multiset<int> myMultiset;

    // 插入元素
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(5);  // 重复插入失败
    myMultiset.insert(5);
    myMultiset.insert(3);
    myMultiset.insert(5);  // 重复插入成功

    // 遍历元素
    std::cout << "set elements: ";
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    std::cout << "multiset elements: ";
    for (const auto& elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    // 查找元素
    auto itSet = mySet.find(5);
    if (itSet != mySet.end()) {
        std::cout << "Found 5 in set.\n";
    }

    auto itMultiset = myMultiset.find(5);
    if (itMultiset != myMultiset.end()) {
        std::cout << "Found 5 in multiset.\n";
    }

    // 统计元素数量
    std::cout << "Count of 5 in set: " << mySet.count(5) << "\n";
    std::cout << "Count of 5 in multiset: " << myMultiset.count(5) << "\n";

    // 删除元素
    mySet.erase(5);  // 删除唯一的 5
    myMultiset.erase(5);  // 删除所有 5

    // 遍历删除后的容器
    std::cout << "set after erase: ";
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    std::cout << "multiset after erase: ";
    for (const auto& elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << "\n";

    return 0;
}

输出示例

set elements: 3 5 
multiset elements: 3 5 5 
Found 5 in set.
Found 5 in multiset.
Count of 5 in set: 1
Count of 5 in multiset: 2
set after erase: 3 
multiset after erase: 3 

总结

  • 相同点
    • 都是有序容器,支持高效的插入、查找和删除操作(O(log n))。
    • 使用迭代器遍历时,元素按照排序规则输出。
  • 不同点
    • set 不允许重复元素,multiset 允许。
    • set.count(x) 的值是 01,而 multiset.count(x) 可以大于 1。

选择 setmultiset,取决于是否需要支持重复的元素存储。


7. 示例:set 的完整代码

#include <iostream>
#include <set>

int main() {
    // 用数组array中的元素构造set
    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
    set<int> s(array, array+sizeof(array)/sizeof(array));
    cout << s.size() << endl;
    // 正向打印set中的元素,从打印结果中可以看出:set可去重
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    
    // 使用迭代器逆向打印set中的元素
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << " ";
    cout << endl;
    // set中值为3的元素出现了几次
    cout << s.count(3) << endl;


    // 创建一个空的 set 容器
    std::set<int> s;
    
    // 插入元素
    s.insert(3);
    s.insert(1);
    s.insert(2);
    
    // 遍历 set 并输出元素
    for (auto it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";  // 输出:1 2 3
    }
    std::cout << std::endl;
    
    // 查找元素
    auto it = s.find(2);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    }

    // 删除元素
    s.erase(2);

    // 输出删除后的元素
    for (auto it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";  // 输出:1 3
    }
    
    std::cout << "\nSize: " << s.size() << std::endl;
    std::cout << "Is empty: " << s.empty() << std::endl;
    
    return 0;
}

输出:

1 2 3 
Found: 2
1 3 
Size: 2
Is empty: 0

multiset

  1. multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。
  2. 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成
    的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值**不能在容器
    **中进行修改(因为元素总是const的),但可以从容器中插入或删除。
  3. 在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则
    进行排序
  4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭
    代器遍历时会得到一个有序序列。
  5. multiset底层结构为二叉搜索树(红黑树)。

注意:

  1. multiset中再底层中存储的是<value, value>的键值对
  2. mtltiset的插入接口中只需要插入即可
  3. 与set的区别是,multiset中的元素可以重复,set是中value是唯一的
  4. 使用迭代器对multiset中的元素进行遍历,可以得到有序的序列
  5. multiset中的元素不能修改
  6. 在multiset中找某个元素,时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
  7. multiset的作用:可以对元素进行有重复的排序

  1. 📜 [ 声明 ] 由于作者水平有限,本文有错误和不准确之处在所难免,
  2. 本人也很想知道这些错误,恳望读者批评指正!
  3. 我是:勇敢滴勇~感谢大家的支持!

http://www.kler.cn/a/584422.html

相关文章:

  • (2025|ICLR|厦大华为,LoSA,基于表示互信息的动态层级稀疏率,基于重构误差的秩分配)LLM 的动态低秩稀疏自适应
  • SQL Server数据库基于SQL性能优化
  • 迪威 3D 模型发布系统:制造业产品展示革新利器
  • 批量给 Excel 添加或删除密码保护|Excel 批量设置打开密码和只读密码
  • 【3dmax笔记】008:选择工具
  • 数字隔离器,如何提升储能系统的安全与效能?
  • k8s集群中部署dcgm-exporter收集GPU指标
  • 5-27 临摹大师-IP-Adapter
  • 【Docker项目实战】使用Docker与Caddy部署BanBan任务管理工具
  • 如何搭建一个适配微信小程序,h5,app的uni-app项目
  • C# NX二次开发:获取模型中所有的草图并获取草图中的对象
  • 基于SpringBoot + Vue 的校园论坛系统
  • K8S学习之基础二十六:k8s的StatefulSet控制器
  • 在 Ubuntu 上安装和配置 Docker 的完整指南
  • 网络爬虫-1:发送请求+维持会话+代理设置/超时设置
  • 高德爬取瓦片和vue2使用
  • Sglang部署大模型常用参数详解
  • 【Oracle】19c数据库控制文件多路径配置
  • 使用阿里云操作系统控制台巧解调度抖动
  • Python----数据可视化(pyecharts二:绘图一:条形图,直方图,折线图,散点图,箱图,饼图,热力图)