set / unordered_set

set 基于红黑树，有序去重；unordered_set 基于哈希表，无序去重但更快。两者都保证元素唯一性。

std::set

#include <set>

std::set<int> s = {5, 3, 1, 4, 2, 3};  // 自动去重排序
// s = {1, 2, 3, 4, 5}

// 插入
s.insert(6);
s.emplace(7);
auto [it, ok] = s.insert(3);  // ok=false，已存在

// 查找
bool found = s.count(3);       // 0 或 1
auto it2 = s.find(3);          // 迭代器，未找到返回 end()
bool has = s.contains(3);      // C++20

// 删除
s.erase(3);                    // 按值删除
s.erase(s.find(4));            // 按迭代器删除

// 范围查找
auto lo = s.lower_bound(3);    // 第一个 >= 3
auto hi = s.upper_bound(5);    // 第一个 > 5
for (auto it = lo; it != hi; ++it) {
    std::cout << *it << " ";   // 3 4 5
}

// 有序遍历
for (int x : s) std::cout << x << " ";  // 1 2 4 5 6 7

// multiset：允许重复
std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
std::cout << ms.count(3) << "\n";  // 3
ms.erase(ms.find(3));              // 只删除一个 3

std::unordered_set

#include <unordered_set>

std::unordered_set<std::string> us = {"apple", "banana", "cherry"};

us.insert("date");
us.emplace("elderberry");

bool found = us.count("apple");   // 1
bool has = us.contains("apple");  // C++20

us.erase("banana");

// 遍历（无序）
for (const auto& s : us) std::cout << s << " ";

// 性能调优
us.reserve(1000);
us.max_load_factor(0.5);

自定义比较器

// set 自定义排序
struct CaseInsensitive {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) { return tolower(c1) < tolower(c2); });
    }
};

std::set<std::string, CaseInsensitive> ci_set;
ci_set.insert("Apple");
ci_set.insert("apple");  // 被视为重复，不插入

// unordered_set 自定义哈希
struct Point { int x, y; };

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<long long>{}((long long)p.x << 32 | p.y);
    }
};

struct PointEqual {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_set<Point, PointHash, PointEqual> point_set;
point_set.insert({1, 2});

集合运算

std::set<int> a = {1, 2, 3, 4, 5};
std::set<int> b = {3, 4, 5, 6, 7};
std::set<int> result;

// 交集
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::inserter(result, result.begin()));
// result = {3, 4, 5}

// 并集
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::inserter(result, result.begin()));

// 差集
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::inserter(result, result.begin()));
// result = {1, 2}

关键认知

set 适合需要有序遍历或范围查询的场景；unordered_set 适合只需要快速查找/插入/删除的场景（快 3-5x）。集合运算（交并差）需要有序容器，用 std::set_* 算法。