C++ STL 容器详解：unordered_map 与 unordered_set 实战指南

unordered_set 构造

用法类似，仅存储单一值。

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

int main() {
    unordered_set<int> mySet = {1, 2, 3, 4, 5};
    vector<int> vec = {1, 2, 3, 4, 5};
    unordered_set<int> mySet2(vec.begin(), vec.end());
    
    for (const auto& elem : mySet) {
        cout << elem << " ";
    }
    return 0;
}

常用操作

插入操作

insert() 是最通用的方法，而 emplace() 在构造复杂对象时更高效，因为它直接在容器内构建元素，避免了临时对象的复制开销。

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

int main() {
    unordered_map<int, string> myMap;
    
    // insert: 先构造再插入
    myMap.insert({1, "One"});
    
    // emplace: 直接构造，避免复制
    myMap.emplace(2, "Two");
    
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
}

查找操作

• find()：返回迭代器，若未找到返回 end()。
• count()：返回元素出现次数（对于 set/map 通常为 0 或 1）。
• operator[]：仅适用于 map，查找失败时会自动插入默认值。

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

int main() {
    unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}};
    
    // find
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        cout << "Found: " << it->second << endl;
    }
    
    // count
    cout << "Count of 1: " << myMap.count(1) << endl;
    
    // operator[] 注意：会修改容器
    cout << "Value at key 3: " << myMap[3] << endl; // 自动插入 3 -> ""
    return 0;
}

删除操作

使用 erase() 删除指定元素或区间，clear() 清空所有数据。

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

int main() {
    unordered_set<int> mySet = {1, 2, 3, 4, 5, 6};
    
    // 删除单个元素
    mySet.erase(3);
    
    // 删除区间 [it1, it2)
    auto it1 = mySet.find(2);
    auto it2 = mySet.find(5);
    mySet.erase(it1, it2);
    
    // 清空
    mySet.clear();
    return 0;
}

高级用法：自定义哈希

当处理自定义类型（如结构体）时，默认哈希函数不可用，需显式提供。

unordered_map 自定义哈希

#include <iostream>
#include <unordered_map>
#include <functional>
using namespace std;

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

// 自定义哈希结构体
struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ hash<int>()(p.y);
    }
};

int main() {
    unordered_map<Point, string, PointHash> pointMap;
    pointMap[{1, 2}] = "Point(1, 2)";
    pointMap[{3, 4}] = "Point(3, 4)";
    
    for (const auto& pair : pointMap) {
        cout << pair.second << endl;
    }
    return 0;
}

unordered_set 自定义比较

除了哈希，有时还需自定义相等判断逻辑。

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

struct Point {
    int x, y;
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ hash<int>()(p.y);
    }
};

struct PointEqual {
    bool operator()(const Point& p1, const Point& p2) const {
        return p1.x == p2.x && p1.y == p2.y;
    }
};

int main() {
    unordered_set<Point, PointHash, PointEqual> pointSet;
    pointSet.insert({1, 2});
    pointSet.insert({3, 4});
    pointSet.insert({1, 2}); // 重复点不会插入
    
    cout << "Size: " << pointSet.size() << endl; // 输出 2
    return 0;
}

性能分析与优化

时间复杂度

最坏情况通常由严重的哈希冲突引起。虽然概率极低，但在极端输入下仍需警惕。

空间与负载因子

容器内部维护桶（bucket）数组。负载因子（元素数/桶数）超过阈值（默认约 1.0）时会触发重新哈希（rehash），导致性能波动。

优化建议

1. 预留空间：若已知元素数量，使用 reserve() 提前分配桶，减少 rehash 次数。
2. 定制哈希：针对特定数据结构设计分布均匀的哈希函数，降低冲突率。
3. 场景匹配：无需排序时用 unordered，需排序或范围查询时用 map/set。

总结

unordered_map 和 unordered_set 是 C++ 中处理高频查找与去重任务的首选工具。理解其哈希原理、掌握自定义哈希方法，并合理预估性能开销，能显著提升代码效率。在实际工程中，根据数据特性在有序性与速度之间做出权衡，才是关键所在。