C++ set自动排序去重特性解析

C++ set容器基于红黑树实现，具备自动排序与去重特性，插入、删除、查找时间复杂度为O(log n)；可通过自定义比较函数对象或函数指针实现排序规则；与unordered_set相比，后者基于哈希表，平均操作时间复杂度O(1)，但无序且最坏情况性能下降；需有序或稳定性能时选set，仅需唯一性且追求平均速度时选unordered_set；批量插入时推荐使用范围insert减少红黑树调整，提升效率。

C++ set容器的核心特性在于其自动排序和去重机制。这意味着当你向set中插入元素时，它们会自动按照一定的规则（默认是升序）进行排序，并且任何重复的元素只会被保留一份。这使得set非常适合需要存储唯一且有序元素的场景。

自动排序与去重机制

set底层通常使用红黑树实现，这保证了插入、删除和查找操作的对数时间复杂度。当我们插入一个元素到set中时，set会首先检查该元素是否已经存在。如果存在，则插入操作会被忽略（去重）；如果不存在，则会将元素插入到红黑树的合适位置，以维持排序。

这种自动排序和去重的特性，让set在某些场景下拥有独特的优势。例如，统计一段文本中不同单词的个数，或者对一组数据进行排序并去重等。

副标题1：set的排序规则如何自定义？

默认情况下，set使用 < 运算符进行排序。但有时我们需要自定义排序规则，比如按照元素的绝对值大小排序，或者按照字符串的长度排序。这时，我们可以通过以下两种方式来实现：

1. 提供比较函数对象（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;
}

2. 提供比较函数指针： 定义一个函数，接受两个参数，返回一个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中插入大量数据时，直接循环插入可能会导致性能瓶颈，因为每次插入都需要重新平衡红黑树。以下是一些提高插入效率的方法：

1. 使用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;
}

2. 避免重复插入： 在插入之前，先检查元素是否已经存在于set中。如果存在，则避免重复插入。虽然set本身会去重，但提前检查可以避免不必要的红黑树调整。可以使用set::count() 方法判断元素是否存在。

3. 使用移动语义： 如果元素是自定义类型，并且拷贝代价较高，可以使用移动语义来避免不必要的拷贝。这需要确保你的自定义类型支持移动构造函数和移动赋值运算符。

4. 预分配内存（仅适用于某些底层实现）： 虽然set本身没有提供预分配内存的接口，但在某些底层实现中，预先分配足够的内存可以减少内存分配和释放的次数，从而提高性能。但这通常需要了解set的具体实现细节。

选择哪种方法取决于数据的特点和具体的应用场景。通常来说，使用insert的范围版本是最简单且有效的方法。