C++ STL 中的 `unordered_map` 和 `unordered_set` 总结

1. unordered_map

unordered_map 是一个基于哈希表实现的容器，存储键值对（key-value），每个键必须唯一，可以快速插入、删除、查找。

基本特性

• 存储结构：键值对 (key-value)。
• 键唯一性：每个键在表中必须是唯一的。
• 无序存储：键值对的存储顺序与插入顺序无关。
• 时间复杂度：
  • 平均情况下，插入、删除、查找的时间复杂度为 ( O(1) )。
  • 最坏情况下（哈希冲突严重时），时间复杂度为 ( O(n) )。

常用函数

示例代码

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

int main() {
    unordered_map<string, int> map;

    // 插入键值对
    map["apple"] = 10;
    map["banana"] = 20;
    map.insert({"cherry", 30});

    // 查找元素
    if (map.find("banana") != map.end()) {
        cout << "banana: " << map["banana"] << endl;
    }

    // 删除元素
    map.erase("apple");

    // 遍历哈希表
    for (auto& [key, value] : map) {
        cout << key << ": " << value << endl;
    }

    return 0;
}

2. unordered_set

unordered_set 是一个基于哈希表实现的容器，用于存储唯一元素（类似于数学中的集合），不存储值。

基本特性

• 存储结构：仅存储唯一的键（没有值）。
• 键唯一性：集合中的每个键必须唯一。
• 无序存储：元素存储的顺序与插入顺序无关。
• 时间复杂度：
  • 平均情况下，插入、删除、查找的时间复杂度为 ( O(1) )。
  • 最坏情况下，时间复杂度为 ( O(n) )。

常用函数

示例代码

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

int main() {
    unordered_set<int> set;

    // 插入元素
    set.insert(10);
    set.insert(20);
    set.insert(30);
    set.insert(10); // 插入失败，10 已存在

    // 查找元素
    if (set.find(20) != set.end()) {
        cout << "20 exists in the set!" << endl;
    }

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

    // 遍历集合
    for (auto& elem : set) {
        cout << elem << " ";
    }

    return 0;
}

3. unordered_map 和 unordered_set 对比

4. 注意事项

1. 无序性：
   • 元素的存储顺序与插入顺序无关，取决于哈希函数的实现。
2. 哈希冲突：
   • 哈希表依赖于哈希函数，若哈希冲突严重，会导致性能下降。
3. 迭代器失效：
   • 插入或删除元素后，迭代器可能会失效。
4. 自定义哈希函数：
   • 如果需要存储用户自定义类型，可以通过提供自定义哈希函数实现。

5. 常见应用场景

5.1 去重

使用 unordered_set 去除重复元素：

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

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 4, 5};
    unordered_set<int> unique(nums.begin(), nums.end());

    for (auto& elem : unique) {
        cout << elem << " ";
    }
    return 0;
}

输出：

1 2 3 4 5

5.2 统计元素出现次数

使用 unordered_map 统计字符出现次数：

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

int main() {
    string text = "hello world";
    unordered_map<char, int> freq;

    for (char c : text) {
        freq[c]++;
    }

    for (auto& [ch, count] : freq) {
        cout << ch << ": " << count << endl;
    }
    return 0;
}

输出：

h: 1
e: 1
l: 3
o: 2
 : 1
w: 1
r: 1
d: 1

总结

• unordered_map：适用于存储键值对，快速查找、统计、映射。
• unordered_set：适用于存储唯一键，快速查找、去重、集合操作。