C++ unordered_set 与 unordered_map 核心解析

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)，是处理此类统计问题的经典方案。