17370845950

set基于红黑树实现，元素有序，操作复杂度O(log n)；unordered_set基于哈希表，无序但平均O(1)，需根据是否需要排序选择。

在C++中，set 和 unordered_set 都是标准模板库（STL）提供的关联容器，用于存储唯一的元素。它们的核心功能相似，但在底层实现、性能特征和使用场景上有明显区别。

set 与 unordered_set 的主要区别

set 基于红黑树（一种自平衡二叉搜索树）实现，元素自动按升序排列。插入、删除和查找的时间复杂度为 O(log n)。

unordered_set 基于哈希表实现，元素无固定顺序。理想情况下插入、删除和查找操作接近 O(1)，最坏情况可能退化到 O(n)。

选择依据：

• 需要有序遍历 → 使用 set
• 追求最快平均查找速度且不需要排序 → 使用 unordered_set
• 自定义类型需提供比较函数（set）或哈希函数（unordered_set）

set 使用示例

set 会自动对元素进行排序，并保证唯一性。

#include iostream>
#include
using namespace std;

int main() {
    set s;
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(5); // 重复元素不会被插入

    cout     for (int x : s) {
        cout     }
    cout
    if (s.find(3) != s.end()) {
        cout     }

    s.erase(1);
    cout     for (int x : s) cout     cout
    return 0;
}

unordered_set 使用示例

unordered_set 不保证顺序，但通常具有更快的访问速度。

#include stream>
#include
using namespace std;

int main() {
    unordered_set us;
    us.insert(5);
    us.insert(1);
    us.insert(3);
    us.insert(5); // 重复，不插入

    cout     for (int x : us) {
        cout     }
    cout
    if (us.count(3)) {
        cout     }

    us.erase(1);
    cout
    return 0;
}

自定义类型的支持

若要在 set 中使用自定义类型，需提供比较函数；对于 unordered_set，需提供哈希函数。

例如定义一个结构体 Person：

struct Person {
    string name;
    int age;
    bool operator==(const Person& p) const {
        return name == p.name && age == p.age;
    }
};

// set 需要小于比较
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) const {
        if (a.name != b.name) return a.name         return a.age     }
};

// unordered_set 需要哈希特化
struct HashPerson {
    size_t operator()(const Person& p) const {
        return hash{}(p.name) ^ (hash{}(p.age)     }
};

// 使用方式：
set people_set;
unordered_set people_unordered; 基本上就这些。根据是否需要有序和性能要求来选择合适的容器。