一、std::set 与 std::unordered_set 概述

std::set 和 std::unordered_set 都是 C++ STL 中用于存储唯一元素集合的容器。
它们的主要区别在于底层实现和访问特性：

特性	std::set	std::unordered_set
底层实现	红黑树（自动排序）	哈希表（无序存储）
元素顺序	升序排列（默认）	无序
查找复杂度	O(log n)	平均 O(1)，最坏 O(n)
内存占用	较高（树节点指针）	较低（哈希桶）
适用场景	需要排序、范围查找	需要快速查找/插入/删除

---

二、std::set 详解

1. 核心特性

• 唯一性：所有元素自动保持唯一。

• 自动排序：元素会按升序排列（默认使用 < 运算符比较）。

• 双向迭代器：支持从小到大遍历。

• 动态平衡：底层是红黑树，自动保持平衡。

2. 基本使用示例

#include <set>
#include <iostream>

int main() {
    std::set<int> s1;
    std::set<int> s2 = {1, 3, 2};
    std::set<int> s3(s2.begin(), s2.end());

    // 插入与删除
    s1.insert(5);
    s1.insert({6, 7, 8});
    s1.erase(5);
    s1.erase(s1.begin());

    // 查找
    auto it = s1.find(3);
    if (it != s1.end()) {
        std::cout << "Found: " << *it << "\n";
    }

    // 遍历（自动排序）
    for (const auto& val : s1) {
        std::cout << val << " ";
    }

    // 范围查找
    auto lb = s1.lower_bound(4); // >=4 的第一个元素
    auto ub = s1.upper_bound(4); // >4 的第一个元素
}

---

3. 自定义排序规则

如果你希望集合降序排列或使用自定义比较方式，可以定义比较器结构体：

struct CompareDesc {
    bool operator()(int a, int b) const {
        return a > b; // 降序排列
    }
};

int main() {
    std::set<int, CompareDesc> s = {3, 1, 2};
    for (const auto& val : s) {
        std::cout << val << " "; // 输出 3 2 1
    }
}

---

三、std::unordered_set 详解

1. 核心特性

• 唯一性：同样保证元素唯一。

• 无序存储：元素顺序由哈希值决定。

• 查找快速：平均复杂度 O(1)。

• 哈希冲突处理：通过链表或开放寻址法。

2. 基本使用示例

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> us1;
    std::unordered_set<int> us2 = {1, 3, 2};
    std::unordered_set<int> us3(us2.begin(), us2.end());

    // 插入与删除
    us1.insert(5);
    us1.insert({6, 7, 8});
    us1.erase(5);
    us1.erase(us1.begin());

    // 查找
    if (us1.find(3) != us1.end()) {
        std::cout << "Found\n";
    }

    // 遍历（无序）
    for (const auto& val : us1) {
        std::cout << val << " ";
    }

    // 性能优化
    us1.reserve(100);          // 预分配桶空间
    us1.max_load_factor(0.75); // 设置最大负载因子
}

---

3. 自定义哈希与比较函数

当集合元素是自定义类型时，必须同时定义：

• operator==（判断两个键是否相等）

• 哈希函数（生成哈希值）

struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

int main() {
    std::unordered_set<Key, KeyHash> mySet;
    mySet.insert({1, 2});
}

---

四、性能对比与优化建议

操作	std::set	std::unordered_set
查找	O(log n)	平均 O(1)
插入	O(log n)	平均 O(1)
删除	O(log n)	平均 O(1)
遍历	O(n)	O(n)
内存占用	较高	较低

优化建议

• 使用 std::set 时：

  • 适合需要有序集合的场景。

  • 频繁插入删除时注意性能损耗。

  • 善用 lower_bound() 与 upper_bound()。

• 使用 std::unordered_set 时：

  • 适合快速查找/去重的场景。

  • 预先 reserve() 可减少 rehash。

  • 调整 max_load_factor() 控制性能与内存平衡。

  • 为自定义类型提供高效哈希函数。

---

五、常见陷阱与解决方案

1. 修改 std::set 元素

std::set 的元素不能直接修改，否则会破坏有序性。

std::set<int> s = {1, 2, 3};
s.erase(2);
s.insert(4);

---

2. unordered_set rehash 导致迭代器失效

rehash 过程中桶结构会变化，原有迭代器失效。

for (auto it = us.begin(); it != us.end();) {
    if (*it % 2 == 0)
        it = us.erase(it); // 安全删除
    else
        ++it;
}

---

3. 自定义类型哈希冲突问题

必须同时定义 operator== 与哈希函数，否则无法正确区分相同键。

struct Key {
    int a, b;
    bool operator==(const Key& other) const {
        return a == other.a && b == other.b;
    }
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

std::unordered_set<Key, KeyHash> mySet;

---

六、典型应用场景

1. 去重

std::unordered_set<std::string> uniqueWords;
std::string text = "hello world hello";
std::istringstream iss(text);//把字符串当作输入流来解析，可以方便地按空格（或格式）提取单词、数字、数据。
std::string word;
while (iss >> word) { //就是从字符串流中，按空格分隔读取一个单词，然后存入变量 word
    uniqueWords.insert(word);//把单词放进去重的集合里
}
std::cout << "Unique words: " << uniqueWords.size() << "\n";

---

2. 快速查找

std::set<int> blacklist = {1001, 1002, 1003};
if (blacklist.find(1001) != blacklist.end()) {
    std::cout << "Blocked!\n";
}

3. 有序输出

std::set<int> sortedData = {5, 1, 3};
for (int val : sortedData) {
    std::cout << val << " ";  // 输出 1 3 5
}

---

七、总结

容器	优点	缺点	典型用途
std::set	自动排序，稳定迭代器	插入删除较慢	排序集合、范围查询
std::unordered_set	查找插入快，空间效率高	无序，迭代器易失效	快速查找、去重操作