std::unordered_set 是 C++11 引入的标准容器，用于存储唯一的元素，并基于哈希表（hash table）实现，具有快速查找、插入、删除的性能（平均 O(1)，最坏 O(n)）。

---

一、std::unordered_map 概述

定义

#include <unordered_map>

std::unordered_map<KeyType, ValueType> my_map;

• 它是一个 key-value 键值对容器。
• 底层采用 **哈希表（Hash Table）**实现，键不能重复。
• 插入、查找、删除操作的平均复杂度为 O(1)。

---

二、基本特性概览

特性	描述
容器类型	关联容器（Associative container）
底层结构	哈希表（Hash Table）
元素是否唯一	是，自动去重
是否有序	无序（不按插入顺序、不按大小排序）
查找效率	平均 O(1)，最坏 O(n)
所需头文件	<unordered_set>
使用命名空间	std

---

三、定义与构造方式

#include <unordered_set>
#include <iostream>
#include <string>

int main() {
    // 默认构造
    std::unordered_set<int> s1;

    // 使用初始化列表
    std::unordered_set<int> s2 = {1, 2, 3, 4};

    // 使用自定义哈希函数（后文介绍）
    // std::unordered_set<std::string, MyHash> s3;

    // 复制构造
    std::unordered_set<int> s4(s2);

    // 移动构造
    std::unordered_set<int> s5(std::move(s2));

    return 0;
}

---

四、常用成员函数

操作	说明	示例
insert()	插入元素（自动去重）	s.insert(5);
erase()	删除指定元素	s.erase(3);
find()	查找元素是否存在	if (s.find(4) != s.end()) {}
count()	返回元素出现次数（要么是 0，要么是 1）	if (s.count(2)) {}
clear()	清空所有元素	s.clear();
size()	返回元素个数	std::cout << s.size();
empty()	判断是否为空	if (s.empty())
begin()/end()	迭代器访问	for (auto e : s) std::cout << e;

---

五、简单示例

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> myset;

    myset.insert(10);
    myset.insert(20);
    myset.insert(30);
    myset.insert(10); // 会被忽略（自动去重）

    std::cout << "Set contains:\n";
    for (int x : myset) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    if (myset.count(20)) {
        std::cout << "20 is in the set\n";
    }

    myset.erase(20);

    if (myset.find(20) == myset.end()) {
        std::cout << "20 is now removed\n";
    }

    return 0;
}

---

六、底层原理简析

std::unordered_set 底层使用 哈希表 + 链表拉链法（开链法） 实现，关键特性如下：

• 每个元素通过哈希函数 Hash() 映射到某个桶（bucket）
• 哈希冲突通过链表处理（多个元素在一个桶里用链表连接）
• 查找效率在负载因子较低时接近 O(1)

内部类型别名（来自 std::unordered_set<T>）：

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

你可以传入：

• 自定义哈希函数
• 自定义判等函数

---

七、自定义类型支持（重载哈希）

你可以往 unordered_set 中插入自定义类，前提是你提供了：

1. 哈希函数（std::hash<YourType> 或自定义结构体）
2. 相等比较函数（默认使用 operator==）

示例：自定义结构体插入 unordered_set

#include <unordered_set>
#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2}); // 重复，自动去重

    for (auto& p : points) {
        std::cout << "(" << p.x << ", " << p.y << ")\n";
    }

    return 0;
}

---

八、构造一个简易哈希表（手写 unordered_map）

我们将实现一个简化版本的哈希表，使用 std::vector + std::list（或 std::forward_list）来处理哈希冲突（链地址法）。

1. 结构定义

#include <iostream>
#include <vector>
#include <list>

template <typename Key, typename Value>
class SimpleHashMap {
private:
    static const size_t BUCKET_SIZE = 16;

    struct Entry {
        Key key;
        Value value;
    };

    std::vector<std::list<Entry>> buckets;

    size_t hash(const Key& key) const {
        return std::hash<Key>()(key) % BUCKET_SIZE;
    }

public:
    SimpleHashMap() : buckets(BUCKET_SIZE) {}

    void insert(const Key& key, const Value& value) {
        size_t idx = hash(key);
        for (auto& entry : buckets[idx]) {
            if (entry.key == key) {
                entry.value = value;  // 覆盖
                return;
            }
        }
        buckets[idx].push_back({key, value});
    }

    bool get(const Key& key, Value& value) const {
        size_t idx = hash(key);
        for (const auto& entry : buckets[idx]) {
            if (entry.key == key) {
                value = entry.value;
                return true;
            }
        }
        return false;
    }

    void erase(const Key& key) {
        size_t idx = hash(key);
        auto& bucket = buckets[idx];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->key == key) {
                bucket.erase(it);
                return;
            }
        }
    }

    void print_all() const {
        for (size_t i = 0; i < BUCKET_SIZE; ++i) {
            for (const auto& entry : buckets[i]) {
                std::cout << entry.key << ": " << entry.value << std::endl;
            }
        }
    }
};

2. 使用示例

int main() {
    SimpleHashMap<std::string, int> mymap;

    mymap.insert("apple", 10);
    mymap.insert("banana", 20);
    mymap.insert("apple", 15); // 会替换

    int val;
    if (mymap.get("apple", val)) {
        std::cout << "apple = " << val << std::endl;
    }

    mymap.erase("banana");

    mymap.print_all();

    return 0;
}

---

九、性能与注意事项

特性	说明
插入/查找时间复杂度	平均 O(1)，最坏 O(n)（当哈希冲突严重时）
空间效率	比 std::set 更快但空间更大
自动去重	插入重复元素不会报错，也不会改变原集合
不保证顺序	元素插入顺序不可预测、不稳定
load_factor & rehash	可通过 load_factor() 和 rehash() 控制哈希表大小和性能

---

适用场景总结

适用于：

• 查找、插入频繁，且不需要排序的场景
• 去重：快速过滤重复元素
• 哈希数据结构应用，如 visited 状态集

---