异常教程

C++ 容器类 <unordered_set>（建议收藏）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在现代 C++ 开发中，容器类（Container Classes）是处理数据结构的核心工具。其中，<unordered_set> 作为标准库中的一员，以其高效的无序集合特性，成为解决许多编程问题的首选。无论是快速查找元素、去重数据流，还是实现高效的键值存储，<unordered_set> 都能提供简洁而强大的支持。本文将从基础概念到高级技巧，结合实例深入解析这一容器的使用场景与实现原理，帮助读者掌握其核心功能并避免常见误区。

基本概念与特性

什么是 <unordered_set>？

<unordered_set> 是 C++ 标准库中实现 无序集合（Hash Set） 的容器类，其底层基于 哈希表（Hash Table） 结构。与有序容器如 <set> 不同，<unordered_set> 不保证元素的存储顺序，但提供了 平均 O(1) 时间复杂度 的插入、删除和查找操作。

类比理解：
可以将 <unordered_set> 想象为一个 图书馆的索引系统。当读者需要快速定位一本书时，只需通过书名或作者的索引表直接找到书籍的位置，无需逐层翻阅。这种“直接定位”的特性，正是 <unordered_set> 高效性的核心。

核心特性总结

特性描述
无序性元素的存储顺序不可预测，仅支持通过哈希值快速访问。
唯一性元素值唯一，不允许重复插入。
哈希函数通过哈希函数将键值映射到存储位置，实现快速查找。
动态调整容量随着元素数量变化，容器会自动扩容或缩容以维持性能。

核心功能与代码实践

基础用法：创建与插入元素

使用 <unordered_set> 需要包含头文件 <unordered_set>，并通过模板指定元素类型。以下是一个简单示例：

#include <iostream>
#include <unordered_set>

int main() {
    // 创建一个存储整数的 unordered_set
    std::unordered_set<int> my_set;

    // 插入元素
    my_set.insert(10);
    my_set.insert(20);
    my_set.insert(30);

    // 输出元素（注意：顺序可能与插入顺序不同）
    for (const auto& num : my_set) {
        std::cout << num << " ";
    }
    // 可能的输出：30 10 20
    return 0;
}

关键点：

  • 插入重复元素会被自动忽略，例如 my_set.insert(10); 第二次执行时不会改变集合。
  • 迭代遍历时的输出顺序与插入顺序无关，因为 <unordered_set> 不维护元素顺序。

查找与存在性判断

通过 find() 方法或 count() 函数可快速判断元素是否存在：

// 查找元素 20
auto it = my_set.find(20);
if (it != my_set.end()) {
    std::cout << "元素 20 存在！";
}

// 使用 count() 判断存在性
if (my_set.count(20) > 0) {
    std::cout << "元素 20 存在！";
}

性能对比：

  • find() 的时间复杂度为 O(1)（平均情况），而 count() 在底层同样调用 find()，因此两者效率相同。
  • 若仅需判断存在性，推荐使用 find()，因其返回迭代器可进一步操作元素。

遍历与删除元素

遍历方式

<unordered_set> 支持 范围 for 循环或 迭代器遍历：

// 范围 for 循环
for (const auto& num : my_set) {
    std::cout << num << " ";
}

// 迭代器遍历
for (auto it = my_set.begin(); it != my_set.end(); ++it) {
    std::cout << *it << " ";
}

删除元素

可通过 erase() 方法删除单个元素或区间：

// 删除元素 20
my_set.erase(20);

// 删除所有元素
my_set.clear();

进阶技巧与原理剖析

哈希函数与冲突解决

哈希函数的作用

哈希函数将元素的值转换为一个整数（称为哈希值），并将其映射到哈希表的存储位置（桶）。例如，对整数 10，哈希函数可能直接返回其值，而对字符串则需更复杂的计算。

冲突（Collision）的处理

当两个不同元素的哈希值相同（即 哈希冲突）时，<unordered_set> 使用 开放寻址法（Open Addressing） 或 链地址法（Chaining） 来解决。C++ 标准库通常采用 链地址法，即同一哈希值的元素存储在链表中。

类比说明：
想象一个图书馆的索引卡系统，当两个书名的哈希值相同，它们会被放在同一张索引卡下，形成链表结构。查找时，需遍历该链表直至找到目标元素。

自定义哈希函数与比较器

默认情况下，<unordered_set> 使用 std::hash 作为哈希函数，但若存储自定义类型（如结构体或类），需手动指定哈希逻辑。

示例：自定义结构体的哈希函数

#include <unordered_set>
#include <string>

struct Person {
    std::string name;
    int age;
};

// 为 Person 类型定义哈希函数
namespace std {
    template <>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // 结合 name 和 age 的哈希值
            return std::hash<std::string>()(p.name) ^ 
                   (std::hash<int>()(p.age) << 1);
        }
    };
}

int main() {
    std::unordered_set<Person> people;
    // 插入自定义对象
    people.insert({ "Alice", 30 });
    return 0;
}

性能优化与负载因子

负载因子（Load Factor）

负载因子定义为 容器中元素数量与桶数量的比值。当负载因子过高时，哈希冲突概率增加，性能下降。可通过 max_load_factor() 设置最大负载因子，并调用 rehash() 或 reserve() 预分配空间：

// 设置最大负载因子为 1.0
my_set.max_load_factor(1.0);

// 预分配可容纳 100 个元素的空间
my_set.reserve(100);

时间复杂度分析

操作平均时间复杂度最坏时间复杂度
插入（insert）O(1)O(n)
查找（find）O(1)O(n)
删除（erase）O(1)O(n)

注意：最坏情况通常因哈希冲突导致，合理设计哈希函数可显著降低此类风险。

使用场景与案例分析

场景 1：快速去重

当需要从大量数据中去除重复项时，<unordered_set> 是理想选择。例如，统计一段文本中出现的唯一单词：

#include <fstream>
#include <string>
#include <unordered_set>

int main() {
    std::ifstream file("input.txt");
    std::unordered_set<std::string> unique_words;

    std::string word;
    while (file >> word) {
        unique_words.insert(word);
    }

    std::cout << "Unique words: " << unique_words.size() << std::endl;
    return 0;
}

场景 2：高效存在性判断

在游戏开发中，判断玩家是否已收集特定道具：

std::unordered_set<std::string> collected_items = { "sword", "shield" };

if (collected_items.find("potion") != collected_items.end()) {
    std::cout << "已拥有药水！";
}

场景 3：交集与并集操作

通过集合运算快速实现复杂逻辑：

std::unordered_set<int> set1 = {1, 2, 3};
std::unordered_set<int> set2 = {3, 4, 5};
std::unordered_set<int> intersection;

// 找出交集
for (const auto& num : set1) {
    if (set2.count(num)) {
        intersection.insert(num);
    }
}

常见问题与注意事项

问题 1：元素不可修改

<unordered_set> 中的元素值不可直接修改，因为修改值会破坏哈希值与存储位置的映射关系。若需修改元素，需先删除旧值，再插入新值：

auto it = my_set.find(20);
if (it != my_set.end()) {
    my_set.erase(it);
    my_set.insert(25); // 修改为 25
}

问题 2：线程安全性

<unordered_set> 并非线程安全，多线程环境下需自行加锁或使用线程安全容器（如 std::shared_mutex）。

问题 3：迭代器失效

在以下情况下，迭代器可能失效：

  • 插入或删除元素时（可能导致扩容或缩容）
  • 调用 rehash() 或 reserve()

结论

<unordered_set> 是 C++ 标准库中一个强大而灵活的容器类，其基于哈希表的高效特性使其在需要快速查找、去重和存在性判断的场景中大放异彩。通过掌握其核心功能、哈希原理及优化技巧，开发者能够显著提升代码的性能与可读性。无论是处理大数据集、游戏逻辑还是算法优化，<unordered_set> 都是值得信赖的工具。

在实际开发中，建议根据具体需求权衡 <unordered_set> 与其他容器（如 <set>、<vector>）的优劣，例如：

  • 需要有序性时，选择 <set>；
  • 需要频繁随机访问时，选择 <vector>；
  • 需要高效无序集合时，优先选择 <unordered_set>。

通过合理使用这一容器，开发者能够更高效地应对复杂的数据结构挑战。

最新发布

查看更多文章