C++ STL set 容器详解：特性、常用操作与 multiset 对比

2.1.1 示例：不同构造方法

初始化列表构造：使用初始化列表来初始化 set 容器。

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

int main() {
    set<int> mySet = {2, 7, 1, 8, 2, 8}; // 自动去重并排序
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：1 2 7 8
    }
    return 0;
}

拷贝构造函数：生成一个与已有 set 容器相同的拷贝。

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

int main() {
    set<int> originalSet = {1, 2, 3};
    set<int> copySet(originalSet); // 拷贝构造
    for (const auto& elem : copySet) {
        cout << elem << " "; // 输出：1 2 3
    }
    return 0;
}

区间构造函数：用 [first, last) 区间内的元素构造 set。适用于将已有容器的一部分元素导入 set。

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

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    set<int> mySet(nums.begin(), nums.end()); // 从 vector 初始化
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：1 3 4 5 9（自动去重并排序）
    }
    return 0;
}

默认构造函数：创建一个空的 set。

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

int main() {
    set<int> mySet; // 空的 set 容器
    cout << "Size of mySet: " << mySet.size() << endl; // 输出：0
    return 0;
}

• 解释：
  • 使用 {} 初始化列表会将相同元素自动去重，且 set 会按照升序排序。
  • 区间构造、拷贝构造和初始化列表构造都非常适合在需要从其他数据结构中导入数据时使用。

2.2 相关文档

• C++ Reference: set constructor

第三章：set 的常用操作

3.1 插入操作详解

插入操作是 set 容器的基础操作之一，set 提供了多种插入元素的方法。由于 set 中不允许重复元素，每次插入操作后，set 会自动去重。

3.1.1 使用 insert() 插入元素

insert() 是 set 中最常用的插入方法。它不仅可以插入单个元素，还可以插入区间元素或初始化列表。

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

int main() {
    set<int> mySet;
    // 插入单个元素
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(8);
    // 插入初始化列表中的所有元素
    mySet.insert({2, 7, 1});
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：1 2 3 5 7 8（自动排序）
    }
    return 0;
}

• 解释：
  • insert() 方法会返回一个 pair，其 first 元素是指向插入位置的迭代器，second 元素是一个布尔值，表示插入是否成功（当元素已存在时为 false）。

3.1.2 使用 emplace() 插入元素

emplace() 允许直接在 set 中构造元素，避免不必要的复制，提高插入效率。与 insert() 相比，emplace() 更高效，尤其在处理复杂对象时。

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

int main() {
    set<int> mySet;
    // 使用 emplace 插入元素
    mySet.emplace(10);
    mySet.emplace(4);
    mySet.emplace(6);
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：4 6 10（自动排序）
    }
    return 0;
}

• 解释：
  • emplace() 方法直接在 set 中构造元素，适用于插入对象的构造比较复杂且不希望进行复制的情况。

3.1.3 插入区间元素

可以使用 insert() 方法从另一个容器中插入一个区间的元素。

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

int main() {
    vector<int> nums = {6, 4, 6, 7, 8}; // 有重复元素
    set<int> mySet;
    mySet.insert(nums.begin(), nums.end()); // 插入 vector 的元素
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：4 6 7 8（自动去重和排序）
    }
    return 0;
}

• 解释：
  • 通过 insert(nums.begin(), nums.end()) 可以从已有容器中导入数据，并在插入时去重和排序。

3.2 查找操作详解

查找操作可以帮助我们在 set 中验证元素是否存在。set 提供了多个方法来实现查找操作。

3.2.1 使用 find() 查找元素

find() 方法返回一个迭代器，指向指定元素的位置，如果元素不在 set 中，则返回 end() 迭代器。

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

int main() {
    set<int> mySet = {3, 6, 9};
    auto it = mySet.find(6);
    if (it != mySet.end()) {
        cout << "Found: " << *it << endl; // 输出：Found: 6
    } else {
        cout << "Not found" << endl;
    }
    return 0;
}

• 解释：
  • find() 方法返回指向查找元素的迭代器，若元素不存在则返回 end()。

3.2.2 使用 count() 统计元素

count() 方法返回指定元素的数量。对于 set，因为元素唯一，结果要么是 0 要么是 1。

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

int main() {
    set<int> mySet = {1, 4, 9};
    cout << "Count of 4: " << mySet.count(4) << endl; // 输出：Count of 4: 1
    cout << "Count of 7: " << mySet.count(7) << endl; // 输出：Count of 7: 0
    return 0;
}

• 解释：
  • 因为 set 不允许重复元素，所以 count() 只能返回 0 或 1。

3.3 删除操作详解

删除操作允许我们从 set 中移除特定元素或区间。

3.3.1 使用 erase() 删除单个元素

erase() 方法可以通过值或迭代器来删除元素。

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

int main() {
    set<int> mySet = {2, 4, 6, 8};
    mySet.erase(4); // 删除值为 4 的元素
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：2 6 8
    }
    return 0;
}

• 解释：
  • erase() 方法可以根据值删除元素，若元素不存在则不会进行任何操作。

3.3.2 使用迭代器区间删除元素

erase() 还支持根据迭代器区间来删除一组元素。

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

int main() {
    set<int> mySet = {1, 2, 3, 4, 5};
    auto it1 = mySet.find(2);
    auto it2 = mySet.find(4);
    mySet.erase(it1, it2); // 删除 [2, 4) 区间内的元素，不包含 4
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：1 4 5
    }
    return 0;
}

• 解释：
  • erase(it1, it2) 删除的是从迭代器 it1 到 it2（不包含 it2）的元素。

3.3.3 清空 set

使用 clear() 方法可以清空整个 set。

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

int main() {
    set<int> mySet = {3, 5, 7};
    mySet.clear(); // 清空 set
    cout << "Size after clear: " << mySet.size() << endl; // 输出：Size after clear: 0
    return 0;
}

• 解释：
  • clear() 方法会删除 set 中的所有元素，将 set 大小变为 0。

第四章：set 的常用成员函数

set 容器提供了一系列成员函数，使用户能够方便地进行数据操作和信息查询。在本节中，将详细介绍这些常用的成员函数及其用法。

4.1 常用成员函数概述

4.2 成员函数示例

4.2.1 begin() 和 end()

begin() 返回指向 set 第一个元素的迭代器，end() 返回指向 set 尾后位置的迭代器。

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

int main() {
    set<int> mySet = {5, 10, 15};
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        cout << *it << " "; // 输出：5 10 15
    }
    return 0;
}

4.2.2 rbegin() 和 rend()

rbegin() 返回指向 set 最后一个元素的反向迭代器，rend() 返回指向 set 第一个元素之前位置的反向迭代器。

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

int main() {
    set<int> mySet = {3, 6, 9};
    for (auto it = mySet.rbegin(); it != mySet.rend(); ++it) {
        cout << *it << " "; // 输出：9 6 3
    }
    return 0;
}

4.2.3 size() 和 empty()

size() 返回 set 中的元素个数，empty() 用于检查 set 是否为空。

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

int main() {
    set<int> mySet = {1, 2, 3};
    cout << "Size of mySet: " << mySet.size() << endl; // 输出：Size of mySet: 3
    cout << "Is mySet empty? " << (mySet.empty() ? "Yes" : "No") << endl; // 输出：No
    mySet.clear(); // 清空 mySet
    cout << "Size after clear: " << mySet.size() << endl; // 输出：0
    cout << "Is mySet empty? " << (mySet.empty() ? "Yes" : "No") << endl; // 输出：Yes
    return 0;
}

4.2.4 max_size()

max_size() 返回 set 可以容纳的最大元素数量。

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

int main() {
    set<int> mySet;
    cout << "Max size of mySet: " << mySet.max_size() << endl; // 输出一个很大的数，表示最大可能容量
    return 0;
}

4.2.5 swap()

swap() 用于交换两个 set 容器的内容。

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

int main() {
    set<int> set1 = {1, 3, 5};
    set<int> set2 = {2, 4, 6};
    set1.swap(set2); // 交换 set1 和 set2 的内容
    cout << "Elements in set1: ";
    for (const auto& elem : set1) {
        cout << elem << " "; // 输出：2 4 6
    }
    cout << "\nElements in set2: ";
    for (const auto& elem : set2) {
        cout << elem << " "; // 输出：1 3 5
    }
    return 0;
}

• 解释：
  • swap() 函数交换两个 set 的内容，但不会影响各自的容量或分配。

第五章：性能分析

5.1 时间复杂度

C++ 的 set 容器基于红黑树实现，因此在大部分操作中具备较高的效率。以下是 set 常用操作的时间复杂度分析：

• 插入 (insert)：时间复杂度为 O(log N)。由于 set 使用平衡二叉树维护元素的有序性，每次插入操作需要找到合适的插入位置，因此为 O(log N)。
• 查找 (find)：时间复杂度为 O(log N)。在 set 中查找特定元素时，借助红黑树的性质可以在 O(log N) 时间内完成查找。
• 删除 (erase)：时间复杂度为 O(log N)。删除操作需要定位待删除元素的位置，并调整树的平衡结构，因此复杂度为 O(log N)。
• 遍历：遍历整个 set 的时间复杂度为 O(N)。由于 set 是有序的，遍历操作是顺序的，因此与元素数量成线性关系。

5.2 空间复杂度

• 空间复杂度：set 的空间复杂度通常为 O(N)，其中 N 表示 set 中存储的元素个数。由于 set 基于红黑树实现，每个节点包含元素值及指向子节点的指针，因此在存储元素之外需要额外的指针空间。
• 内存管理：set 使用了动态内存分配，在插入和删除元素时，内存会动态调整，以确保红黑树的平衡。虽然 set 内部使用红黑树存储元素，但 STL 已优化了 set 的内存分配，使其尽可能地降低内存浪费。

5.3 性能优化建议

• 避免频繁的插入和删除操作：虽然 set 在插入和删除操作上表现良好，但大量的插入或删除操作仍会影响性能。如果数据量很大且操作频繁，建议考虑 unordered_set，其基于哈希表实现，在插入和删除操作上的平均时间复杂度为 O(1)。
• 适用场景：set 适用于需要有序存储且不允许重复元素的场景，例如需要自动排序的场景，或在大数据量中频繁查找特定元素时。
• 空间与时间的平衡：set 需要较多内存来维护树的平衡，因此在嵌入式系统或内存受限的环境下使用时需谨慎。

第六章：高级用法

6.1 自定义排序和比较器

默认情况下，set 使用 < 运算符按升序排序元素。不过，在某些情况下，我们可能需要使用自定义的排序规则。C++ set 容器允许使用自定义比较器，以实现自定义的排序方式。

6.1.1 示例：自定义比较器

可以通过自定义比较器来实现降序排列。自定义比较器可以是一个函数对象或函数指针，在 set 声明时作为模板参数传入。

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

// 定义一个比较器，使 set 按降序排列
struct DescendingOrder {
    bool operator()(const int& a, const int& b) const {
        return a > b;
    }
};

int main() {
    set<int, DescendingOrder> mySet; // 使用自定义比较器
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(4);
    mySet.insert(2);
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：4 3 2 1
    }
    return 0;
}

• 解释：
  • DescendingOrder 是一个结构体，实现了降序排列的 operator() 函数。在定义 set 时将该比较器传入，实现了 set 的降序排列。
• 应用场景：自定义比较器适用于需要特殊排序逻辑的情况，比如按字符串长度排序或按特定规则排列数据。

6.2 使用迭代器进行复杂操作

set 容器的迭代器支持多种操作，适合在遍历、条件删除等场景中使用。以下介绍迭代器在复杂操作中的应用。

6.2.1 示例：使用迭代器删除特定条件下的元素

可以使用迭代器遍历 set，并根据条件删除符合要求的元素。例如，删除所有偶数元素。

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

int main() {
    set<int> mySet = {1, 2, 3, 4, 5, 6};
    for (auto it = mySet.begin(); it != mySet.end();) {
        if (*it % 2 == 0) {
            it = mySet.erase(it); // 删除偶数元素并更新迭代器
        } else {
            ++it;
        }
    }
    for (const auto& elem : mySet) {
        cout << elem << " "; // 输出：1 3 5
    }
    return 0;
}

• 解释：
  • 使用 erase() 删除元素时会返回一个新的迭代器，指向被删除元素的下一个位置。删除时务必更新迭代器以避免迭代器失效。

6.2.2 示例：逆向遍历 set

利用 rbegin() 和 rend()，可以对 set 进行逆向遍历。

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

int main() {
    set<int> mySet = {10, 20, 30, 40};
    for (auto it = mySet.rbegin(); it != mySet.rend(); ++it) {
        cout << *it << " "; // 输出：40 30 20 10
    }
    return 0;
}

• 解释：
  • rbegin() 和 rend() 分别返回指向 set 容器最后一个元素和第一个元素之前位置的反向迭代器，实现逆序遍历。

第七章：multiset 的使用

multiset 是 C++ STL 中的另一种关联容器，与 set 类似，但允许重复元素。multiset 的主要特点是能存储多个相同的键值，并按照键值顺序自动排序。它适用于需要频繁计数或存储重复数据的场景。

7.1 multiset 与 set 的区别

7.2 使用 multiset 存储重复键

multiset 容器可以有效地存储和管理重复的键值。以下示例展示了如何在 multiset 中插入重复的键值。

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

int main() {
    multiset<int> myMultiSet;
    myMultiSet.insert(5);
    myMultiSet.insert(5);
    myMultiSet.insert(3);
    myMultiSet.insert(3);
    for (const auto& elem : myMultiSet) {
        cout << elem << " "; // 输出：3 3 5 5
    }
    return 0;
}

• 解释：
  • 在 multiset 中，即使是相同的键（如 3 和 5），每次插入操作都会保留重复值。

7.3 multiset 的常用操作

multiset 支持的操作与 set 类似，但针对重复元素的操作略有不同，以下列出几个常用操作。

7.3.1 使用 count() 统计元素

count() 方法可以统计特定元素的出现次数。

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

int main() {
    multiset<int> myMultiSet = {1, 1, 2, 3, 3, 3};
    cout << "Count of 1: " << myMultiSet.count(1) << endl; // 输出：2
    cout << "Count of 3: " << myMultiSet.count(3) << endl; // 输出：3
    return 0;
}

• 解释：
  • count() 方法返回特定元素在 multiset 中的出现次数。

7.3.2 使用 equal_range() 查找范围

equal_range() 方法返回一个范围，表示特定元素的所有匹配项。

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

int main() {
    multiset<int> myMultiSet = {2, 2, 3, 3, 3, 4};
    auto range = myMultiSet.equal_range(3); // 获取键为 3 的范围
    for (auto it = range.first; it != range.second; ++it) {
        cout << *it << " "; // 输出：3 3 3
    }
    return 0;
}

• 解释：
  • equal_range() 返回一个 pair，其中 first 为指定元素的第一个位置，second 为指定元素的最后一个位置（不含 second）。

7.3.3 删除特定的重复元素

erase() 方法可以删除指定元素的一个或所有出现次数。

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

int main() {
    multiset<int> myMultiSet = {2, 3, 3, 4};
    myMultiSet.erase(myMultiSet.find(3)); // 删除第一个 3
    for (const auto& elem : myMultiSet) {
        cout << elem << " "; // 输出：2 3 4
    }
    return 0;
}

• 解释：
  • erase() 删除迭代器指定位置的元素，仅删除一次。若要删除所有相同元素，可直接传入键值。

myMultiSet.erase(3); // 删除所有键为 3 的元素

7.4 使用场景

• 重复记录：在存储包含重复项的数据时（如多个学生的成绩或产品订单），multiset 能提供灵活的管理方式。
• 频率统计：当需要对某些值进行频率统计时，multiset 可以用来存储和快速统计每个元素的出现次数。
• 分类存储：适合在需要分类存储数据并保留重复记录的场景中使用，比如管理多个分数段的学生记录。

总结

C++ 的 set 和 multiset 容器提供了在数据管理中追求秩序与高效的完美解决方案。通过唯一键存储的特性，set 自然适合去重和自动排序，维护集合的唯一性；而 multiset 则应对那些需要保留重复项的场景，使得数据的多样性和丰富性得以保留。凭借 STL 的精妙实现和红黑树的底层结构，set 和 multiset 在高效性与灵活性上找到平衡，在大数据场景中亦不失光彩。这两者不仅仅是容器，更是一种数据哲学——在无序与有序、唯一与多重之间，为开发者提供了灵活的空间，助力高效的数据管理和算法设计。