C++ unordered_set 与 unordered_map 核心解析

C++ unordered 系列关联式容器详解

在 C++98 标准中，STL 提供的关联式容器底层多基于红黑树，查询效率为 O(log N)。当数据量极大时，这种对数级比较开销可能成为瓶颈。C++11 引入了 unordered 系列容器，底层采用哈希表结构，将平均查找时间复杂度优化至 O(1)，非常适合需要频繁快速检索的场景。

unordered_map：键值对的高效存储

unordered_map 存储 <key, value> 键值对，允许通过 key 快速索引到对应的 value。它的核心特点如下：

• 无序性：内部元素不排序，完全依赖哈希值分布。
• 快速访问：相同哈希值的键值对会被放入同一个桶（Bucket）中，实现常数级查找。
• 迭代器：至少支持前向迭代器。
• 操作符重载：实现了 operator[]，可直接用 key 访问或插入 value。

这里有个细节需要注意：operator[] 在 key 不存在时会构造默认值并插入，存在则直接返回引用。因此，如果 key 已存在，count 函数的返回值最大为 1，因为 key 不可重复。

使用示例

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

void test_unordered_map() {
    unordered_map<string, string> dict;
    
    // 插入方式一：make_pair
    dict.insert(make_pair("insert", "插入"));
    dict.insert(make_pair("love", "爱"));
    
    // 插入方式二：operator[] (若 key 不存在则创建)
    dict["sort"] = "排序";
    dict["miss"] = "想念、错过";
    
    // 遍历输出
    for (auto it = dict.begin(); it != dict.end(); ++it) {
        cout << it->first << ":" << it->second << endl;
    }
}

int main() {
    test_unordered_map();
    return 0;
}

unordered_set：唯一元素的集合

unordered_set 以任意顺序存储唯一元素，元素的值即为其键。它主要用于去重和快速查找。

• 唯一性：一旦存入，元素不可修改（但可移除后重新插入）。
• 哈希组织：根据哈希值分桶，无需维护顺序。
• 性能：单元素访问快于有序集合，但在范围迭代上通常不如有序容器高效。

使用示例

#include <iostream>
#include <unordered_set>

using namespace std;

void test_unordered_set() {
    unordered_set<int> us;
    
    // 插入元素，重复的会被自动忽略
    us.insert(2);
    us.insert(3);
    us.insert(2); // 重复，不会插入
    us.insert(1);
    us.insert(0);
    
    // 遍历输出
    for (auto it = us.begin(); it != us.end(); ++it) {
        cout << *it << endl;
    }
}

int main() {
    test_unordered_set();
    return 0;
}

注意：unordered_set 只能去重，无法保证从左到右的顺序，如果需要有序且去重，应使用 set。

性能对比测试

为了直观感受差异，我们对比一下 map/set 与 unordered_map/unordered_set 在大量数据下的表现。主要关注插入、查找和删除三个操作。

#include <vector>
#include <set>
#include <unordered_set>
#include <ctime>
#include <cstdlib>

using namespace std;

void test_performance() {
    const size_t N = 1000000;
    unordered_set<int> us;
    set<int> s;
    vector<int> v;
    
    v.reserve(N);
    srand((size_t)time(0));
    
    // 准备随机数据
    for (size_t i = 0; i < N; ++i) {
        v.push_back(rand() + 1);
    }
    
    // 测试 set 插入
    size_t begin1 = clock();
    for (auto e : v) { s.insert(e); }
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;
    
    // 测试 unordered_set 插入
    size_t begin2 = clock();
    for (auto e : v) { us.insert(e); }
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;
    
    // 测试 set 查找
    size_t begin3 = clock();
    for (auto e : v) { s.find(e); }
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << endl;
    
    // 测试 unordered_set 查找
    size_t begin4 = clock();
    for (auto e : v) { us.find(e); }
    size_t end4 = clock();
    cout << "unordered_set find:" << end4 - begin4 << endl;
    
    cout << "插入数据个数：" << s.size() << endl;
    cout << "插入数据个数：" << us.size() << endl;
}

从测试结果来看，在处理大量重复数据时，unordered_set 和 unordered_map 凭借哈希表的特性，在插入和查找速度上更具优势。但如果业务逻辑强依赖数据的有序性，map 和 set 则是更好的选择。

实战应用：找出重复 N 次的元素

在 LeetCode 等算法题中，unordered_map 常被用来统计频率。例如：在长度为 2N 的数组里找出重复 N 次的元素。

思路：利用 unordered_map 统计每个元素出现的次数，目标元素的出现次数应为数组长度的一半。

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_map<int, int> countmap;
        
        // 统计频次
        for (auto element : nums) {
            countmap[element]++;
        }
        
        int targetCount = nums.size() / 2;
        
        // 找到出现次数为目标值的元素
        for (auto& pair : countmap) {
            if (pair.second == targetCount) {
                return pair.first;
            }
        }
        
        return -1; // 理论上不会到达此处
    }
};

这个解法利用了哈希表 O(1) 的查找特性，整体时间复杂度降为 O(N)，空间复杂度为 O(N)，是处理此类统计问题的经典方案。