C++ set容器的核心优势是自动排序与元素唯一性，基于红黑树实现，插入、删除、查找时间复杂度为O(log n)；通过指定比较器可自定义排序规则；与unordered_set相比，set有序但速度较慢，后者基于哈希表，平均O(1)操作但无序；适用于去重、唯一ID管理、查找表、索引构建及集合运算等场景。
C++
set
容器的核心优势在于它能自动对元素进行排序，并且保证容器内元素的唯一性，也就是去重。这在很多场景下都非常有用，省去了手动排序和去重的麻烦。
解决方案
set
容器基于红黑树实现，这使得它在插入、删除和查找操作上都能保持较高的效率，通常是 O(log n) 的时间复杂度。
使用
set
非常简单。首先，你需要包含头文件
<set>
。然后，你可以创建一个
set
std::set<int> mySet;
创建了一个存储整数的
set
。
立即学习“C++免费学习笔记（深入）”；
插入元素使用
insert()
方法。例如，
mySet.insert(10);
会将整数 10 插入到
mySet
中。如果
set
中已经存在相同的元素，
insert()
方法不会执行任何操作，保证了元素的唯一性。
遍历
set
可以使用迭代器。例如：
#include <iostream> #include <set> int main() { std::set<int> mySet; mySet.insert(30); mySet.insert(10); mySet.insert(20); mySet.insert(10); // 重复插入，不会生效 for (auto it = mySet.begin(); it != mySet.end(); ++it) { std::cout << *it << " "; // 输出：10 20 30 } std::cout << std::endl; return 0; }
可以看到，
set
自动将元素排序并去重了。
set
的排序机制是怎样的？如何自定义排序规则？
默认情况下，
set
使用
<
运算符进行排序。但如果你需要自定义排序规则，比如按照元素的绝对值大小排序，或者对自定义类型进行排序，你可以使用函数对象（functor）或 Lambda 表达式。
例如，使用函数对象：
#include <iostream> #include <set> #include <cmath> struct AbsCompare { bool operator()(int a, int b) const { return std::abs(a) < std::abs(b); } }; int main() { std::set<int, AbsCompare> mySet; mySet.insert(-10); mySet.insert(5); mySet.insert(-5); mySet.insert(10); for (auto it = mySet.begin(); it != mySet.end(); ++it) { std::cout << *it << " "; // 输出：5 -5 -10 10 } std::cout << std::endl; return 0; }
或者使用 lambda 表达式：
#include <iostream> #include <set> #include <cmath> int main() { auto absCompare = [](int a, int b) { return std::abs(a) < std::abs(b); }; std::set<int, decltype(absCompare)> mySet(absCompare); // 需要传入比较器实例 mySet.insert(-10); mySet.insert(5); mySet.insert(-5); mySet.insert(10); for (auto it = mySet.begin(); it != mySet.end(); ++it) { std::cout << *it << " "; // 输出：5 -5 -10 10 } std::cout << std::endl; return 0; }
注意，使用 lambda 表达式时，需要使用
decltype
来推导 lambda 表达式的类型，并且在创建
set
对象时，需要传入一个 lambda 表达式的实例。这稍微麻烦一些，但 lambda 表达式在很多情况下更加简洁方便。
set
和
unordered_set
的区别是什么？应该如何选择？
set
和
unordered_set
都是 C++ 标准库中的容器，用于存储唯一元素。它们的主要区别在于底层实现和性能特点。
set
基于红黑树实现，元素是有序的。
unordered_set
基于哈希表实现，元素是无序的。
由于红黑树的特性，
set
在插入、删除和查找操作上具有 O(log n) 的时间复杂度，并且元素是有序的，可以方便地进行范围查找。但哈希表的平均时间复杂度为 O(1)，因此
unordered_set
在插入、删除和查找操作上通常比
set
更快。
选择哪个容器取决于你的具体需求。如果需要保持元素的有序性，或者需要进行范围查找，那么
set
是一个更好的选择。如果不需要保持元素的有序性，并且对性能要求较高，那么
unordered_set
可能更适合。
另外，
unordered_set
对存储的元素类型有额外的要求，需要提供一个哈希函数和一个相等比较函数。对于内置类型，这些函数通常已经定义好了。但对于自定义类型，你需要自己实现这些函数。
set
在实际开发中有哪些应用场景？
set
在实际开发中有很多应用场景，例如：
- 数据去重： 当你需要从一个数据集中去除重复元素时，可以使用
set
。
- 维护唯一 ID 集合： 例如，在游戏中，可以使用
set
来维护所有在线玩家的 ID 集合，确保每个玩家只有一个 ID。
- 实现高效的查找表： 当你需要快速查找某个元素是否存在于一个集合中时，可以使用
set
。
- 构建索引： 可以使用
set
来构建索引，加速数据的查找过程。
- 集合运算：
set
可以方便地进行集合运算，例如求并集、交集和差集。
总的来说，
set
是一个非常实用的容器，在很多场景下都能发挥重要作用。理解
set
的特点和使用方法，可以帮助你编写更高效、更简洁的代码。
评论（已关闭）
评论已关闭