1. unordered_map
unordered_map 是一个基于哈希表实现的容器，存储键值对（key-value），每个键必须唯一，可以快速插入、删除、查找。
基本特性
- 存储结构：键值对 (
key-value)。 - 键唯一性：每个键在表中必须是唯一的。
- 无序存储：键值对的存储顺序与插入顺序无关。
- 时间复杂度：
- 平均情况下，插入、删除、查找的时间复杂度为 ( O(1) )。
- 最坏情况下（哈希冲突严重时），时间复杂度为 ( O(n) )。
常用函数
| 函数 | 功能说明 |
|---|---|
insert({key, val}) | 插入键值对，若键已存在，则插入失败。 |
erase(key) | 删除键为 key 的元素，若不存在则不执行操作。 |
find(key) | 返回指向键为 key 的迭代器，若不存在则返回 end()。 |
operator[key] | 通过键访问或插入值，若键不存在则插入默认值。 |
size() | 返回哈希表中元素的数量。 |
empty() | 判断哈希表是否为空。 |
clear() | 清空哈希表中的所有元素。 |
示例代码
#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) )。
常用函数
| 函数 | 功能说明 |
|---|---|
insert(key) | 插入元素 key，若元素已存在，则插入失败。 |
erase(key) | 删除元素 key，若不存在，则不执行操作。 |
find(key) | 查找元素 key，返回指向该元素的迭代器，若不存在则返回 end()。 |
count(key) | 判断元素 key 是否存在，返回 1（存在）或 0（不存在）。 |
size() | 返回集合中元素的数量。 |
empty() | 判断集合是否为空。 |
clear() | 清空集合中的所有元素。 |
示例代码
#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 对比
| 特性 | unordered_map | unordered_set |
|---|---|---|
| 存储内容 | 键值对 (key-value) | 仅存储键 |
| 键的唯一性 | 键必须唯一 | 元素必须唯一 |
| 访问元素 | 通过键访问对应值，map[key] | 查找元素是否存在，find(key) |
| 使用场景 | 用于键值对映射，如字典、计数等 | 用于集合操作，如去重、查找是否存在 |
| 时间复杂度 | 插入、删除、查找的平均复杂度为 ( O(1) ) | 插入、删除、查找的平均复杂度为 ( O(1) ) |
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：适用于存储唯一键，快速查找、去重、集合操作。
