C++ set容器基于红黑树实现，具备自动排序与去重特性，插入、删除、查找时间复杂度为O(log n)；可通过自定义比较函数对象或函数指针实现排序规则；与unordered_set相比，后者基于哈希表，平均操作时间复杂度O(1)，但无序且最坏情况性能下降；需有序或稳定性能时选set，仅需唯一性且追求平均速度时选unordered_set；批量插入时推荐使用范围insert减少红黑树调整，提升效率。
C++ set容器的核心特性在于其自动排序和去重机制。这意味着当你向set中插入元素时，它们会自动按照一定的规则（默认是升序）进行排序，并且任何重复的元素只会被保留一份。这使得set非常适合需要存储唯一且有序元素的场景。
自动排序与去重机制
set底层通常使用红黑树实现，这保证了插入、删除和查找操作的对数时间复杂度。当我们插入一个元素到set中时，set会首先检查该元素是否已经存在。如果存在，则插入操作会被忽略（去重）；如果不存在，则会将元素插入到红黑树的合适位置，以维持排序。
这种自动排序和去重的特性，让set在某些场景下拥有独特的优势。例如，统计一段文本中不同单词的个数，或者对一组数据进行排序并去重等。
立即学习“C++免费学习笔记（深入）”；
副标题1：set的排序规则如何自定义？
默认情况下，set使用
<
运算符进行排序。但有时我们需要自定义排序规则，比如按照元素的绝对值大小排序，或者按照字符串的长度排序。这时，我们可以通过以下两种方式来实现：
- 提供比较函数对象（functor）： 创建一个类，重载
()
运算符，定义自己的比较逻辑。然后，在创建set对象时，将该类的实例作为模板参数传递给set。
#include #include #include struct AbsCompare { bool operator()(int a, int b) const { return std::abs(a) < std::abs(b); }};int main() { std::set mySet = {-3, 1, -4, 2, -1}; for (int x : mySet) { std::cout << x << " "; // Output: -1 1 2 -3 -4 } std::cout << std::endl; return 0;}- 提供比较函数指针： 定义一个函数，接受两个参数，返回一个bool值，表示它们的排序关系。然后，在创建set对象时，将该函数的指针作为模板参数传递给set。
#include #include #include bool compareStringLength(const std::string& a, const std::string& b) { return a.length() < b.length();}int main() { std::set mySet(compareStringLength); mySet.insert("apple"); mySet.insert("banana"); mySet.insert("kiwi"); for (const std::string& s : mySet) { std::cout << s << " "; // Output: kiwi apple banana } std::cout << std::endl; return 0;}副标题2：set与unordered_set的区别是什么？何时使用set，何时使用unordered_set？
set和unordered_set都是C++ STL中的关联容器，用于存储唯一元素。它们的主要区别在于底层实现和性能特点：
- set: 基于红黑树实现，元素有序存储，插入、删除和查找操作的时间复杂度为O(log n)。
- unordered_set: 基于哈希表实现，元素无序存储，插入、删除和查找操作的平均时间复杂度为O(1)，最坏情况下为O(n)。
何时使用set:
- 需要存储有序元素。
- 对元素的顺序有要求。
- 插入、删除和查找操作的性能要求稳定。
何时使用unordered_set:
- 不需要存储有序元素。
- 对元素的顺序没有要求。
- 追求更高的平均查找速度。
选择哪个容器取决于具体的应用场景和性能需求。如果对元素的顺序有要求，或者需要稳定的性能，那么set是更好的选择。如果对元素的顺序没有要求，并且追求更高的平均查找速度，那么unordered_set是更好的选择。 但需要注意，unordered_set 在处理哈希冲突时，性能可能会下降。
副标题3：如何高效地向set中插入大量数据？
向set中插入大量数据时，直接循环插入可能会导致性能瓶颈，因为每次插入都需要重新平衡红黑树。以下是一些提高插入效率的方法：
- 使用insert的范围版本： 如果数据已经存储在另一个容器（例如vector）中，可以使用insert的范围版本，一次性将所有元素插入到set中。这可以减少红黑树的调整次数。
#include #include #include int main() { std::vector data = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0}; std::set mySet; mySet.insert(data.begin(), data.end()); for (int x : mySet) { std::cout << x << " "; // Output: 0 1 2 3 4 5 6 7 8 9 } std::cout << std::endl; return 0;}
-
避免重复插入： 在插入之前，先检查元素是否已经存在于set中。如果存在，则避免重复插入。虽然set本身会去重，但提前检查可以避免不必要的红黑树调整。可以使用
set::count()
方法判断元素是否存在。
-
使用移动语义： 如果元素是自定义类型，并且拷贝代价较高，可以使用移动语义来避免不必要的拷贝。这需要确保你的自定义类型支持移动构造函数和移动赋值运算符。
-
预分配内存（仅适用于某些底层实现）： 虽然set本身没有提供预分配内存的接口，但在某些底层实现中，预先分配足够的内存可以减少内存分配和释放的次数，从而提高性能。但这通常需要了解set的具体实现细节。
选择哪种方法取决于数据的特点和具体的应用场景。通常来说，使用insert的范围版本是最简单且有效的方法。
以上就是C++ set容器特性 自动排序与去重机制的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1472022.html
微信扫一扫 
支付宝扫一扫 
