0. 概述

在 C++11 引入 unordered_set 与 unordered_multiset 前，标准库中已有 set 与 multiset 两种有序关联容器，二者底层基于红黑树实现，虽能保证元素的有序性，却需付出 O (log n) 的时间复杂度代价。而实际开发中，大量场景更关注 “快速操作” 而非 “元素有序”—— 比如判断某个值是否存在、去重存储等，此时哈希表的平均 O (1) 效率优势显著。因此 C++11 新增这两种无序关联容器：它们底层均基于哈希表，继承了无序容器的高效特性，同时延续 “元素唯一 / 元素可重复” 的分化设计（unordered_set 元素唯一适配 “无重复值集合”，unordered_multiset 元素可重复适配 “允许重复值集合”），形成与 set/multiset “有序 vs 无序、效率 vs 排序需求” 的互补。本文将先剖析 “有序集合容器的局限性” 与 “无序集合容器的补充价值”，再系统讲解 unordered_set 的共性特性（构造、哈希实现）、核心特性（元素唯一性）、操作方法（插入 / 查找 / 删除的逻辑），并结合实际场景对比四类集合容器的选型标准，帮助开发者理解 “为何需要两类集合容器”，并根据需求精准选择工具。

1. 为何需要新增：有序容器 set/multiset 的局限性

set 与 multiset 作为 C++98 就存在的有序关联容器，底层依赖红黑树（一种自平衡二叉搜索树）实现，核心特点是 “元素升序排列”，但这一特性也带来了不可忽视的局限，成为 C++11 新增无序集合容器的核心动因：

1.1 时间复杂度瓶颈：O (log n) 难满足高频操作需求

红黑树的结构决定了其插入、查找、删除操作均需通过树的遍历完成，时间复杂度固定为 O (log n)。对于数据量较小的场景，这一开销可忽略，但在高频操作场景（如每秒百万级的元素存在性判断、高频去重存储）中，O (log n) 与 O (1) 的效率差距会被无限放大 —— 例如当数据量为 100 万时，log₂(10⁶)≈20，意味着无序容器的操作效率理论上是有序容器的 20 倍，能显著降低系统响应延迟。

1.2 排序功能的 “冗余性”：多数场景无需有序存储

set/multiset 的 “有序性” 是一把双刃剑：仅当需要元素排序遍历（如 “获取所有数值按升序展示”“统计后按频率排序输出”）时，有序性才有价值；但更多场景下，开发者仅需 “快速判断元素是否存在” 或 “存储无重复元素”，无需关心元素存储顺序。例如：

• 黑名单系统中，判断某个 IP 是否在黑名单内，无需 IP 按顺序存储；

• 缓存系统中，记录已缓存的键值，仅需去重和快速查询，排序无意义。

此时，红黑树为维护有序性付出的性能成本，完全成为不必要的开销。

1.3 内存占用更高：红黑树的结构开销

红黑树的每个节点除了存储元素外，还需维护父节点、左子节点、右子节点指针及颜色标记（共 4 个额外指针 / 标记），内存占用比哈希表更紧凑的 “桶 + 元素” 结构更高。对于内存敏感场景（如嵌入式开发、高并发缓存），这种额外开销会进一步限制容器的使用场景。

2. 无序容器的补充价值：哈希表带来的 “效率革命”

unordered_set 与 unordered_multiset 底层基于哈希表实现，核心目标是 “舍弃有序性，换取极致效率”，恰好弥补了 set/multiset 的上述局限，形成 “有序与无序” 的互补：

2.1 平均 O (1) 时间复杂度：高频操作的 “性能救星”

哈希表通过 “哈希函数将元素映射到桶（bucket）” 的方式存储元素，理想情况下，只需一次哈希计算即可定位到元素所在的桶，进而找到对应元素，插入、查找、删除的平均时间复杂度均为 O (1)。即使存在哈希冲突（多个元素映射到同一桶），通过链表或红黑树优化后，最坏情况也能控制在 O (log k)（k 为桶内元素数），远优于红黑树的 O (log n)。

2.2 无排序开销：按需选择 “有序与否”

无序容器不维护元素的顺序，插入时无需调整树结构，删除时无需重新平衡红黑树，进一步降低了操作的额外成本。开发者可根据需求灵活选择：需要排序时用 set/multiset，追求效率时用 unordered_set/unordered_multiset，避免 “为不需要的功能买单”。

2.3 延续 “元素唯一 / 可重复” 分化：适配不同集合场景

与 set（元素唯一）和 multiset（元素可重复）的分化逻辑一致，unordered_set 保持元素的唯一性，适合 “无重复值集合”（如黑名单、去重存储）；unordered_multiset 允许元素重复，适合 “允许重复值集合”（如统计元素出现次数、存储重复数据）。这种设计确保无序集合容器能完全覆盖有序集合容器的应用场景，只是用 “效率” 替换了 “有序性”。

3. 四类集合容器对比：精准选型的核心依据

通过对比 set/multiset 与 unordered_set/unordered_multiset 的核心特性，可清晰看到 “为何需要两类集合容器”—— 它们针对不同需求场景设计，无绝对优劣，仅需按需选择：

容器类型	底层实现	元素唯一性	元素顺序	平均操作复杂度（插入 / 查找 / 删除）	核心适用场景
set	红黑树	唯一	元素升序	O(log n)	需要有序遍历、范围查询（如按区间筛选元素）
multiset	红黑树	可重复	元素升序	O(log n)	需要有序遍历且允许重复元素（如按分数排序展示多个学生）
unordered_set	哈希表	唯一	无序（哈希决定）	O(1)	高频元素查询、无需排序（如黑名单判断）
unordered_multiset	哈希表	可重复	无序（哈希决定）	O(1)	高频元素查询且允许重复（如统计词频）

示例选型场景：

• 若需 “按用户年龄（元素）升序展示所有不重复年龄”，选择 set；

• 若需 “按成绩（元素）升序展示所有学生成绩（允许重复）”，选择 multiset；

• 若需 “快速判断某个 ID 是否在已登录用户列表中”，选择 unordered_set；

• 若需 “统计一篇文章中每个单词出现的次数（允许重复存储）”，选择 unordered_multiset。

1. unordered_set

在 C++ 标准库的容器家族里，std::unordered_set 是个 “性能黑马”—— 它以单元素形式存储数据，凭借哈希表的底层实现，在平均情况下能提供常数时间的查找、插入和删除操作，在高频元素访问、快速去重等场景中表现出色（比如黑名单校验、缓存键存储等）。接下来，我们就从 unordered_set 的核心特性入手，逐步解析它的用法、语法特点，以及与 set 的差异，助你轻松掌握这个高效工具。

特点：

• 不允许有重复的元素

• 存储的元素需要支持哈希计算（需提供哈希函数）

• 元素无序排列（不同于 set 的有序性）

• 可以自定义哈希函数和相等性判断（通过仿函数）

1.1 初始化

初始化 std::unordered_set，可直接使用 {} 初始化列表，简洁明了。示例代码如下：

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

// 自定义哈希函数（针对int类型，仅作示例）
struct MyHash {
    size_t operator()(const int& val) const {
        return std::hash<int>()(val) ^ 0x55555555;
    }
};

int main() {
    // 使用初始化列表初始化std::unordered_set
    std::unordered_set<int, MyHash> uset1 = {1, 2, 3, 4};

    for (const auto& val : uset1) {
        std::cout << val << " ";
    }
    // 输出顺序不确定（由哈希决定）

    return 0;
}

上述代码中，通过 {元素 1, 元素 2, ...} 的形式直接初始化 std::unordered_set，相比早期的方式更直观。

在 C++17 中，std::unordered_set 也能享受模板参数自动推导（CTAD）的便利。对于简单的元素类型场景，无需显式指定模板参数：

#include <unordered_set>
#include <string>

int main() {
    // 编译器自动推导元素类型
    std::unordered_set us = {"苹果", "香蕉", "橙子"};
    return 0;
}

但如果需要自定义哈希函数或相等性判断器，仍需显式指定模板参数。

总之，C++11 及之后的标准为 std::unordered_set 提供了多种简化的初始化方式，提高了代码的编写效率和可读性。

1.2 插入元素

（1）insert () 函数：安全且支持批量插入

insert () 是 unordered_set 插入的标准接口，支持单个插入和批量插入，遇到重复元素会忽略插入（不覆盖现有元素），适合需要去重的场景：

#include <unordered_set>
#include <string>

std::unordered_set<std::string> fruitSet = {"苹果", "香蕉"};

// 1. 插入单个元素（两种写法）
fruitSet.insert("橙子");                // 直接插入元素
fruitSet.insert(std::string("葡萄"));   // 插入对象

// 2. 批量插入（初始化列表）
fruitSet.insert({"西瓜", "草莓"});

// 3. 检查插入结果（insert返回pair<iterator, bool>，bool表示是否插入成功）
auto result = fruitSet.insert("苹果"); // 元素"苹果"已存在，插入失败
if (!result.second) {
    std::cout << "元素 " << *result.first << " 已存在" << std::endl;
}

（2）emplace ()：C++11+ 高效插入，避免拷贝

emplace () 是 C++11 新增的插入方式，直接在 unordered_set 内部构造元素，避免了 insert () 中可能的临时对象拷贝，效率更高：

#include <unordered_set>
#include <string>

struct Student {
    std::string name;
    int age;
    Student(std::string n, int a) : name(n), age(a) {}
};

// 自定义Student的哈希函数和相等性判断（省略，需配合使用）
struct StudentHash { /* ... */ };
struct StudentEqual { /* ... */ };

std::unordered_set<Student, StudentHash, StudentEqual> studentSet;

// emplace直接传入构造Student的参数，内部构造元素
studentSet.emplace("张三", 18); // 等价于 insert(Student("张三", 18))
studentSet.emplace("李四", 20);

1.3 查找元素

（1）find ()：返回迭代器，快速定位元素

find () 是 unordered_set 查找的首选接口，根据元素查找，返回指向该元素的迭代器；如果不存在，返回 end () 迭代器。由于底层是哈希表，find () 的平均时间复杂度是 O(1)，非常高效：

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

std::unordered_set<std::string> fruitSet = {"苹果", "香蕉", "橙子"};

// 查找元素"香蕉"
auto it = fruitSet.find("香蕉");
if (it != fruitSet.end()) {
    std::cout << "找到元素：" << *it << std::endl;
} else {
    std::cout << "未找到该元素" << std::endl;
}

（2）count ()：返回元素的个数，适合检查存在性

unordered_set 的元素唯一，所以 count () 的返回值只有 0 或 1——0 表示元素不存在，1 表示存在。用法比 find () 更简洁，适合只需判断元素是否存在的场景：

if (fruitSet.count("橙子")) {
    std::cout << "元素\"橙子\"存在" << std::endl;
} else {
    std::cout << "元素\"橙子\"不存在" << std::endl;
}

1.4 遍历

std::unordered_set 的遍历方式与 std::set 类似，但由于其无序性，遍历结果不会按元素排序。

C++11 之前（C++98/03）的遍历方式

没有范围循环和 auto，需显式声明迭代器类型，通过 begin ()/end () 控制循环范围：

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

int main() {
    std::unordered_set<std::string> myUset;
    myUset.insert("苹果");
    myUset.insert("香蕉");
    myUset.insert("橙子");

    // 方式1：普通迭代器遍历
    for (std::unordered_set<std::string>::iterator it = myUset.begin();
         it != myUset.end(); ++it) {
        std::cout << *it << " ";
    }

    // 方式2：常量迭代器（只读）
    for (std::unordered_set<std::string>::const_iterator it = myUset.begin();
         it != myUset.end(); ++it) {
        // 此时不能修改*it，编译会报错
        std::cout << *it << " ";
    }

    return 0;
}

缺点：

• 迭代器类型声明冗长

• 必须手动控制迭代器的起始（begin ()）和终止（end ()）

C++11 的遍历方式

引入了范围循环（range-based for loop） 和 auto 关键字，简化了迭代器声明和循环控制：

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

int main() {
    std::unordered_set<std::string> myUset = {
        "苹果",    // C++11初始化列表，比insert更简洁
        "香蕉",
        "橙子"
    };

    // 方式1：通过auto简化迭代器类型，配合范围循环
    for (auto it = myUset.begin(); it != myUset.end(); ++it) {
        std::cout << *it << " ";
    }

    // 方式2：范围循环直接遍历元素（最常用）
    for (const auto& val : myUset) {  // val类型是const std::string
        std::cout << val << " ";
    }

    return 0;
}

改进点：

• auto 自动推导迭代器 / 元素类型，避免冗长声明

• 范围循环 for (const auto& val : myUset) 无需手动控制 begin ()/end ()，更简洁

• 初始化列表 {"苹果", ...} 比 insert 更直观

1.5 删除元素

erase () 是 unordered_set 删除的核心函数，支持按 “迭代器”“元素”“范围” 删除，灵活度高：

std::unordered_set<int> numSet = {1, 2, 3, 4};

// 1. 按迭代器删除（删除第一个元素）
auto it = numSet.begin();
numSet.erase(it); // 删除迭代器指向的元素（如1）

// 2. 按元素删除（删除元素3）
size_t deletedCount = numSet.erase(3); // 返回删除的元素个数（unordered_set中0或1）
std::cout << "删除了 " << deletedCount << " 个元素" << std::endl; // 输出1

// 3. 按范围删除（删除从迭代器it到末尾的元素）
auto startIt = numSet.find(2); // 找到元素2的迭代器
numSet.erase(startIt, numSet.end()); // 删除2和4

注意：删除迭代器后，该迭代器会失效，不能再使用（比如 ++it），需重新获取。

1.5.1 遍历删除元素

一、遍历删除 unordered_set 特定元素

std::unordered_set 是无序关联容器，底层为哈希表。删除元素时，被删除的迭代器会失效，但其他迭代器通常不受影响（桶数量变化时可能有例外）。正确的做法是利用 erase 方法的返回值（下一个有效的迭代器）更新当前迭代器。

方法 1：使用 erase 的返回值（C++11 及以上推荐）

unordered_set::erase (iterator) 会返回被删除元素的下一个迭代器，可直接用于更新当前迭代器：

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> myUset = {1, 2, 3, 4, 5};

    // 目标：删除偶数元素
    auto it = myUset.begin();
    while (it != myUset.end()) {
        if (*it % 2 == 0) { // 满足删除条件（偶数）
            // erase返回下一个有效迭代器，直接赋值给it
            it = myUset.erase(it);
        } else {
            // 不删除则正常递增迭代器
            ++it;
        }
    }

    // 打印结果：1 3 5（顺序可能不同，因无序性）
    for (const auto& val : myUset) {
        cout << val << " ";
    }

    return 0;
}

方法 2：先保存下一个迭代器（兼容 C++11 之前版本）

C++11 之前，unordered_set::erase 不返回迭代器，需先通过 it++ 保存下一个迭代器，再删除当前元素：

auto it = myUset.begin();
while (it != myUset.end()) {
    if (*it % 2 == 0) {
        // 先通过it++获取下一个迭代器，再删除当前元素
        myUset.erase(it++);
    } else {
        ++it;
    }
}

原理：it++ 会先返回当前迭代器的副本，再递增迭代器，因此删除的是 “旧” 迭代器，而 it 已指向下一步。

1.5.2 遍历删除错误做法及原因

1. 直接删除后递增迭代器：

// 错误示例！可能导致崩溃或未定义行为
auto it = myUset.begin();
while (it != myUset.end()) {
    if (*it % 2 == 0) {
        myUset.erase(it); // 删除当前迭代器指向的元素
    }
    ++it; // 危险！被删除的迭代器已失效，递增操作未定义
}

错误原因：

erase (it) 会使迭代器 it 失效（指向已释放的内存），此时执行 ++it 属于未定义行为（可能崩溃、跳过元素或陷入死循环）。

2. 在 C++11 前使用 erase 后直接复用迭代器：

C++11 之前的 unordered_set::erase 不返回下一个迭代器，若删除后直接使用原迭代器，会导致同样的失效问题：

// C++11 前的错误示例
auto it = myUset.begin();
while (it != myUset.end()) {
    if (*it % 2 == 0) {
        myUset.erase(it); // 迭代器 it 已失效
    } else {
        ++it;
    }
    // 若执行了 erase，此处 it 已失效，循环条件判断可能出错
}

1.6 清空容器

clear () 方法可一键清空 unordered_set 中的所有元素，释放内存（但可能保留部分底层哈希表的容量）：

std::unordered_set<std::string> fruitSet = {"苹果", "香蕉"};
fruitSet.clear(); // 清空所有元素，size() 变为 0
std::cout << "清空后元素数量：" << fruitSet.size() << std::endl; // 输出 0

若需彻底释放内存，可结合 “swap 技巧”（C++11 前常用，C++11 后可使用 shrink_to_fit ()）：

// 彻底释放内存（C++11 前）
std::unordered_set<std::string>().swap(fruitSet);

// C++11 及以上：请求容器收缩至匹配实际元素数量
fruitSet.shrink_to_fit();

1.7 unordered_set 与 set 的核心差异

特性	std::unordered_set	std::set
底层实现	哈希表（Hash Table）	红黑树（Red-Black Tree，一种平衡二叉树）
元素顺序	无序（按哈希值存储）	元素升序排列（可自定义比较器）
查找 / 插入 / 删除效率	平均 O (1)，最坏 O (n)（哈希冲突严重时）	稳定 O (log n)
内存占用	较高（哈希表需要额外空间解决冲突）	较低（红黑树结构紧凑）
元素的要求	需支持哈希函数（std::hash）和相等性判断（std::equal_to）	需支持比较运算符（如 <，或自定义比较器）
迭代器稳定性	插入时可能失效（哈希表扩容时），删除时仅被删迭代器失效	插入 / 删除时其他迭代器通常有效

适用场景选择：

• 若需快速查找且不关心顺序 → 选 unordered_set（如黑名单校验、去重缓存）。

• 若需元素有序或对最坏情况性能有要求 → 选 set（如有序遍历、范围查询）。

1.8 自定义哈希函数与相等性判断

unordered_set 默认使用 std::hash 计算哈希值，用 std::equal_to 判断元素是否相等。对于自定义类型（如结构体），需手动提供哈希函数和相等性判断器。

1.8.1 为自定义类型实现哈希与相等性

#include <unordered_set>
#include <string>

// 自定义类型：表示学生信息
struct Student {
    int id;
    std::string name;

    Student(int id, const std::string& name) : id(id), name(name) {}
};

// 1. 自定义哈希函数（需满足：若 a == b，则 hash(a) == hash(b)）
struct StudentHash {
    size_t operator()(const Student& s) const {
        // 组合 id 和 name 的哈希值（简单示例，实际可优化）
        return std::hash<int>()(s.id) ^ std::hash<std::string>()(s.name);
    }
};

// 2. 自定义相等性判断器
struct StudentEqual {
    bool operator()(const Student& a, const Student& b) const {
        // 定义两个 Student 相等的条件：id 和 name 都相同
        return a.id == b.id && a.name == b.name;
    }
};

// 3. 使用自定义类型作为元素
int main() {
    std::unordered_set<Student, StudentHash, StudentEqual> studentSet;

    // 插入元素
    studentSet.emplace(1, "张三");
    studentSet.emplace(2, "李四");

    // 查找
    auto it = studentSet.find(Student(1, "张三"));
    if (it != studentSet.end()) {
        std::cout << "找到学生：" << it->id << " " << it->name << std::endl; // 输出 1 张三
    }

    return 0;
}

1.8.2 为标准类型扩展哈希（谨慎使用）

可通过特化 std::hash 为标准类型（如 std::pair）添加哈希支持（需注意：C++ 标准不允许在 std 命名空间中添加非标准库类型的特化，但部分编译器支持对标准类型的扩展）：

#include <unordered_set>
#include <utility> // for std::pair

// 为 std::pair<int, int> 特化 std::hash
namespace std {
    template<> struct hash<std::pair<int, int>> {
        size_t operator()(const std::pair<int, int>& p) const {
            return hash<int>()(p.first) ^ hash<int>()(p.second);
        }
    };
}

// 使用 pair 作为元素
std::unordered_set<std::pair<int, int>> coordSet;
coordSet.insert({0, 0}); // 插入坐标(0,0)

1.9 性能优化技巧

1. 预分配容量：

若已知元素数量，使用 reserve (n) 提前分配足够容量，避免哈希表多次扩容（扩容会触发重新哈希，耗时较高）：

std::unordered_set<int> uset;
uset.reserve(1000); // 预留至少存储 1000 个元素的空间

2. 合理设置负载因子：

负载因子 = 元素数量 / 桶数量，默认值通常为 1.0。负载因子越小，哈希冲突概率越低，但内存占用越高。可通过 max_load_factor (f) 调整：

uset.max_load_factor(0.7); // 降低负载因子，减少冲突

3. 避免哈希函数质量差：

哈希函数若容易产生碰撞（如对不同元素返回相同哈希值），会导致 unordered_set 退化为链表，性能骤降。设计时需保证哈希值分布均匀。

1.10 总结

std::unordered_set 凭借哈希表的特性，在平均情况下提供 O (1) 的查找、插入和删除效率，是高频元素访问和去重场景的理想选择。其核心特点包括：

• 元素无序，元素唯一，支持自定义哈希和相等性判断。

• 提供 insert ()、emplace () 等插入方式，find ()、count () 等查找接口，erase () 多种删除形式。

• 与 set 相比，更适合追求查找速度且不关心顺序的场景。

掌握 unordered_set 的用法和特性，能帮助你在 C++ 开发中更灵活地处理集合数据，平衡性能与需求。

3. 文章总结

本文系统介绍了 C++11 引入的无序关联容器 unordered_set，核心围绕其设计价值、特性及使用场景展开，可概括为以下要点：

1. 设计背景与价值

针对传统有序集合容器（set/multiset）基于红黑树实现带来的 O (log n) 时间复杂度、排序冗余及内存开销问题，无序集合容器以哈希表为底层，通过牺牲有序性换取平均 O (1) 的操作效率，填补了 “高频操作且无需排序” 场景的需求空白。

2. 核心特性

• 元素唯一性：unordered_set 元素唯一，适用于 “无重复值集合” 场景（如黑名单、去重存储）。

• 无序性：元素存储顺序由哈希函数决定，与插入顺序无关，区别于有序容器的元素升序特性。

• 性能：插入、查找、删除平均复杂度为 O (1)（哈希冲突严重时最坏为 O (n)），优于红黑树的稳定 O (log n)，但内存占用更高。

3. 关键操作与用法

• 初始化：支持初始化列表、CTAD 自动推导（C++17）及自定义哈希 / 相等性判断器。

• 插入：insert ()（去重）、emplace ()（高效构造）为主要方式，不支持 operator []（无键值对结构）。

• 查找：find () 定位单个元素，count () 检查存在性（返回 0 或 1）。

• 删除：支持按迭代器、元素或范围删除，需注意迭代器失效规则（仅被删迭代器失效）。

4. 与有序容器的选型标准

• 需快速元素查询、无需排序 → 选 unordered_set/unordered_multiset。

• 需有序遍历或范围查询 → 选 set/multiset。

• 元素唯一用 unordered_set/set，元素可重用 unordered_multiset/multiset。

5. 最佳实践

• 预分配容量（reserve ()）、调整负载因子减少哈希冲突。

• 自定义类型作为元素时，需确保哈希函数均匀性和相等性判断逻辑正确。

• 遍历删除元素时，利用 erase () 返回值更新迭代器避免失效。

综上，unordered_set 为 C++ 开发者提供了 “效率优先” 的集合存储方案，与有序集合容器形成互补，掌握其特性可根据场景精准选型，平衡性能与功能需求。