有序之美：C++ Set的哲学与诗意

前言

有序之美：C++ Set的哲学与诗意

在C++的繁华语言世界中，有一个数据结构宛如一位端庄优雅的隐士，它不事张扬，却蕴藏着深邃的智慧与独特的魅力。这便是标准模板库（STL）中的set容器。若将C++比作一幅绚丽的画卷，set则如点缀画卷的灵动笔触，简单而不失精妙。

一.C++ set 的概念

1.1 set 的定义

set 是 C++ STL 中的一种关联式容器，专为存储唯一元素而设计。它提供了自动排序和高效的查找操作，元素总是根据特定顺序（默认是升序）排列。

• 唯一性：每个元素在 set 中是唯一的，插入重复元素时，新元素不会覆盖旧元素，且插入会被忽略。
• 自动排序：set 容器根据元素的顺序关系自动排序。默认情况下使用 < 运算符进行比较。（升序）
• 底层实现：set 使用红黑树实现，确保数据结构在插入、查找和删除操作上的平衡性和高效性。

set 容器的这些特性使其成为去重和自动排序操作的理想选择，并在 O(log N) 的时间复杂度下提供快速的查找、插入和删除操作。

1.2 set 的特点

• 有序性:与 unordered_set 不同，set 会根据元素值自动排序，通常使用升序排列。排序操作由内部的红黑树维护。
• 高效查找：set 适用于频繁查找的场景，查找时间复杂度为 O(log N)。
• 动态数据支持：支持动态的插入和删除，能够适应需要频繁更新的数据集。
• 不允许重复元素：在 set 中，元素的值即为键，不存在重复值。若需要存储重复值，请使用 multiset。

二. set 的构造方法

2.1 常见构造函数

set 提供了多种构造函数，以便用户根据需求灵活初始化容器。以下是 set 常用的构造方法和功能：

2.1.1 示例：不同构造方法

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

#include <iostream>
#include <set>
using namespace std;int main() {set<int> mySet;  // 空的 set 容器cout << "Size of mySet: " << mySet.size() << endl; // 输出: 0return 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> originalSet = {1, 2, 3};set<int> copySet(originalSet); // 拷贝构造for (const auto& elem : copySet) {cout << elem << " "; // 输出: 1 2 3}return 0;
}

初始化列表构造：使用初始化列表来初始化 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 会按照升序排序。
• 区间构造、拷贝构造和初始化列表构造都非常适合在需要从其他数据结构中导入数据时使用。

2.2 相关文档

https://cplusplus.com/reference/set/set/set/

三.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: 1cout << "Count of 7: " << mySet.count(7) << endl; // 输出: Count of 7: 0return 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) 区间内的元素，不包含 4for (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(); // 清空 setcout << "Size after clear: " << mySet.size() << endl; // 输出: Size after clear: 0return 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: 3cout << "Is mySet empty? " << (mySet.empty() ? "Yes" : "No") << endl; // 输出: NomySet.clear(); // 清空 mySetcout << "Size after clear: " << mySet.size() << endl; // 输出: 0cout << "Is mySet empty? " << (mySet.empty() ? "Yes" : "No") << endl; // 输出: Yesreturn 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 示例：自定义比较器

可以通过自定义比较器来实现降序排列。自定义比较器可以是一个函数对象或函数

#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; // 输出: 2cout << "Count of 3: " << myMultiSet.count(3) << endl; // 输出: 3return 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)); // 删除第一个 3for (const auto& elem : myMultiSet) {cout << elem << " "; // 输出: 2 3 4}return 0;
}

解释：

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

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

7.4 使用场景

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

小结

在程序世界中，set像是一位哲人，它教会我们如何在规则中追求秩序，又如何在有序中寻求高效。在处理数据的过程中，set常常成为开发者的得力助手，为复杂的逻辑注入优雅的简洁。

如果你愿意走近set，你会发现它并不只是一个简单的数据结构，而是C++语言中一颗璀璨的明珠。在这片有序的天地里，set以它独特的规则与高效的实现，让我们感受到编程的艺术之美。每一行代码的编写，都是对这位隐士的一次致敬。

本篇关于STL容器中set的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！