C++ 中 set 和 unordered_set 类型的特性与适用场景

在 C++ 编程里，set 和 unordered_set 都是很实用的容器类型，它们有各自独特的特性和适用场景。接下来，我们就详细探讨一下这两种容器。

特性对比

set 的特性

set 是 C++ 标准库中的一种关联容器，它基于红黑树（一种自平衡的二叉搜索树）实现。这就使得 set 中的元素是有序排列的，默认按照元素的键值升序排列。而且，set 中的元素具有唯一性，相同的元素只会存储一份。当你插入一个已经存在的元素时，插入操作会失败。例如：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(2); // 重复元素，插入无效

    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

上述代码中，虽然尝试插入了两次 2，但最终集合中只有一个 2，并且元素是按升序排列输出的。

unordered_set 的特性

unordered_set 同样用于存储唯一元素，但它基于哈希表实现。这意味着元素在容器中的存储是无序的，插入、查找和删除操作的平均时间复杂度为 O(1)。不过，在最坏情况下，这些操作的时间复杂度会达到 O(n)。例如：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;
    myUnorderedSet.insert(3);
    myUnorderedSet.insert(1);
    myUnorderedSet.insert(2);

    for (auto it = myUnorderedSet.begin(); it != myUnorderedSet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

每次运行这段代码，元素的输出顺序可能都不一样，因为它们在 unordered_set 中是无序存储的。

适用场景分析

set 的适用场景

• 需要有序元素的场景：当你需要对元素进行排序时，set 是一个不错的选择。比如在处理一些需要按顺序输出的数据时，使用 set 可以直接得到有序的结果，无需额外的排序操作。
• 需要频繁查找元素的场景：由于 set 基于红黑树，查找操作的时间复杂度为 O(log n)，在元素数量较多时，查找效率较高。

unordered_set 的适用场景

• 对插入、查找和删除操作性能要求较高的场景：因为 unordered_set 的平均时间复杂度为 O(1)，所以在需要快速插入、查找和删除元素的场景中，它比 set 更具优势。例如，在处理大量数据的去重问题时，使用 unordered_set 可以高效地完成任务。
• 不关心元素顺序的场景：如果你的程序不需要元素保持特定的顺序，那么 unordered_set 可以避免 set 因维护有序性而带来的额外开销。

综上所述，set 和 unordered_set 各有优缺点，在实际编程中，我们需要根据具体的需求来选择合适的容器。如果你需要元素有序且对查找性能有一定要求，那么 set 是个好选择；如果你更注重插入、查找和删除操作的性能，且不关心元素顺序，那么 unordered_set 会更适合你。