专业视角：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> 的查找、插入和删除时间复杂度。

特别记住两点：不重复，有序！

与 vector 或 list 等容器不同，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

• 区别：
  • map 和 multimap 是键值对容器，每个元素是一个 <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. set 与 multiset 的区别

1. 元素唯一性

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

2. 插入规则

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

3. 元素计数

• set：每个值在集合中最多出现一次，count() 的返回值是 0 或 1。
• 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) 的值是 0 或 1，而 multiset.count(x) 可以大于 1。

选择 set 或 multiset，取决于是否需要支持重复的元素存储。

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(lo{g}_{2}N)$
7. multiset的作用：可以对元素进行有重复的排序

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