C++ unordered_map 和 unordered_set 容器详解
前言
C++ 标准模板库（STL）中的 unordered_map 和 unordered_set 是哈希表实现的关联容器。与 map 和 set 相比，这两种容器摒弃了元素的有序性，以提升操作效率。unordered_map 和 unordered_set 适合需要频繁插入、删除和查找数据的场景，平均时间复杂度为 O(1)，因此广泛用于高效数据管理和处理。
本文将深入探讨 unordered_map 和 unordered_set 的特性、使用方法，以及与有序容器的性能比较。并通过详细的代码示例，帮助您掌握如何在实际开发中利用这些容器优化性能和内存管理。
第一章：unordered_map 和 unordered_set 的概念
1.1 unordered_map 和 unordered_set 的定义
unordered_map：一种关联容器，用于存储键值对（key-value pairs）。在底层实现上，采用哈希表数据结构，以提供近乎常数时间的查找、插入和删除操作。其特性如下：- 键值对存储：以键值对形式存储数据，每个键唯一。
- 无序存储：键的顺序不固定，存储顺序根据哈希函数决定。
- 高效查找：平均情况下查找时间复杂度为
O(1)。
unordered_set：一种关联容器，仅存储唯一元素，没有键值对结构。同样基于哈希表实现，具有以下特性：- 唯一性：每个元素在容器中唯一，不允许重复。
- 无序存储：元素顺序不固定，由哈希函数决定。
- 高效查找：查找效率极高，平均复杂度为
O(1)。
1.2 与 map、set 的区别
在功能上，unordered_map 和 unordered_set 类似于 map 和 set，但有一些显著区别：
- 底层实现：
unordered_map和unordered_set使用哈希表实现，以提供近乎常数时间的查找效率。map和set使用红黑树实现，确保键的有序性，但查找复杂度为O(log N)。
- 元素顺序：
unordered_map和unordered_set不保证元素顺序，哈希表根据键的哈希值对元素进行散列存储。map和set保持键的有序性，通常按升序排列。
- 迭代器类型：
unordered_map和unordered_set提供的是单向迭代器。map和set提供双向迭代器，支持更灵活的遍历。
- 键的要求：
unordered_map和unordered_set需要键类型支持哈希和相等比较操作。map和set需要键支持小于比较操作，以维持排序关系。
- 性能：
unordered_map和unordered_set在大多数情况下性能优于map和set，尤其是在频繁查找和插入的场景。map和set的性能较为稳定，但在大规模数据处理上可能不及无序容器。
第二章：unordered_map 和 unordered_set 的构造方法
2.1 unordered_map 的常见构造函数
unordered_map 提供了多种构造函数，允许灵活初始化容器。以下是常用的构造方法和功能：
| 构造函数 | 功能 |
|---|---|
unordered_map() | 构造一个空的 unordered_map。 |
unordered_map(InputIterator first, InputIterator last) | 使用 [first, last) 区间的元素初始化容器。 |
unordered_map(const unordered_map& um) | 拷贝构造，生成与 um 相同的容器。 |
unordered_map(std::initializer_list<value_type> il) | 使用初始化列表构造容器。 |
2.1.1 示例：使用不同的构造方法
初始化列表构造：使用初始化列表来初始化 unordered_map。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> myMap = {{"apple", 1}, {"banana", 2}};
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
区间构造函数：使用已有容器的一部分元素构造 unordered_map。
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
vector<pair<string, int>> vec = {{"apple", 1}, {"banana", 2}};
unordered_map<string, int> myMap(vec.begin(), vec.end()); // 从 vector 初始化
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
默认构造函数：创建一个空的 unordered_map。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> myMap; // 空的 unordered_map 容器
cout << "Size of myMap: " << myMap.size() << endl; // 输出：0
return 0;
}
2.2 unordered_set 的常见构造函数
| 构造函数 | 功能 |
|---|---|
unordered_set() | 构造一个空的 unordered_set。 |
unordered_set(InputIterator first, InputIterator last) | 使用 [first, last) 区间的元素初始化容器。 |
unordered_set(const unordered_set& us) | 拷贝构造，生成与 us 相同的容器。 |
unordered_set(std::initializer_list<value_type> il) | 使用初始化列表构造容器。 |
2.2.1 示例：使用不同的构造方法
初始化列表构造：使用初始化列表来初始化 unordered_set。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet = {1, 2, 3, 4, 5};
for (const auto& elem : mySet) {
cout << elem << " "; // 输出顺序可能不固定
}
return 0;
}
区间构造函数：从已有容器的元素构造 unordered_set。
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {1, 2, 3, 4, 5};
unordered_set<int> mySet(vec.begin(), vec.end()); // 从 vector 初始化
for (const auto& elem : mySet) {
cout << elem << " "; // 输出顺序可能不固定
}
return 0;
}
默认构造函数：创建一个空的 unordered_set。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet; // 空的 unordered_set 容器
cout << "Size of mySet: " << mySet.size() << endl; // 输出：0
return 0;
}
第三章：unordered_map 和 unordered_set 的常用操作
3.1 插入操作详解
unordered_map 和 unordered_set 提供了多种插入方法，以满足不同场景的需求。我们将详细探讨常用插入操作，包括 insert()、emplace()、初始化列表插入和区间插入，并对比它们的使用特点和效率。
3.1.1 使用 insert() 插入元素
insert() 是 unordered_map 和 unordered_set 中最常见的插入方法。它不仅可以插入单个元素，还可以插入多个元素、区间或初始化列表中的元素。
unordered_set 中的 insert() 示例：
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet;
mySet.insert(5);
mySet.insert(10);
mySet.insert(15);
for (const auto& elem : mySet) {
cout << elem << " ";
}
return 0;
}
unordered_map 中的 insert() 示例：
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap;
myMap.insert({1, "One"});
myMap.insert({2, "Two"});
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
插入效率：insert() 方法的平均时间复杂度为 O(1)，在极少情况下，哈希冲突增多时，可能退化为 O(N)。
3.1.2 使用 emplace() 插入元素
emplace() 方法直接在 unordered_map 或 unordered_set 中构造元素，避免了复制操作。相较于 insert()，emplace() 更高效，尤其在处理复杂对象时。
unordered_set 中的 emplace() 示例：
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet;
mySet.emplace(5);
mySet.emplace(10);
for (const auto& elem : mySet) {
cout << elem << " ";
}
return 0;
}
unordered_map 中的 emplace() 示例：
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap;
myMap.emplace(1, "One");
myMap.emplace(2, "Two");
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
应用场景：emplace() 非常适合在需要构造复杂对象且避免额外复制的场景下使用。
3.2 查找操作详解
在 unordered_map 和 unordered_set 中，查找操作是最常用的功能之一，尤其在涉及哈希查找的场景下。主要的查找方法有 find()、count() 和 operator[]，我们将一一详细介绍。
3.2.1 使用 find() 查找元素
find() 返回一个迭代器，指向查找到的元素。如果未找到指定元素，则返回 end() 迭代器。对于哈希查找，find() 的平均时间复杂度为 O(1)。
unordered_set 中的 find() 示例：
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet = {1, 2, 3, 4};
auto it = mySet.find(3);
if (it != mySet.end()) {
cout << "Found: " << *it << endl; // 输出：Found: 3
} else {
cout << "Not found" << endl;
}
return 0;
}
unordered_map 中的 find() 示例：
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
auto it = myMap.find(2);
if (it != myMap.end()) {
cout << "Found: " << it->second << endl; // 输出：Found: Two
} else {
cout << "Not found" << endl;
}
return 0;
}
3.2.2 使用 count() 查找元素的出现次数
count() 方法用于统计特定元素在 unordered_set 或 unordered_map 中的出现次数。对于 unordered_set，结果只能为 0 或 1，而在 unordered_map 中，count() 返回键出现的次数（同样只能为 0 或 1）。
unordered_set 中的 count() 示例：
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet = {10, 20, 30};
cout << "Count of 10: " << mySet.count(10) << endl; // 输出：Count of 10: 1
cout << "Count of 15: " << mySet.count(15) << endl; // 输出：Count of 15: 0
return 0;
}
unordered_map 中的 count() 示例：
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}};
cout << "Count of 1: " << myMap.count(1) << endl; // 输出：Count of 1: 1
cout << "Count of 3: " << myMap.count(3) << endl; // 输出：Count of 3: 0
return 0;
}
3.2.3 使用 operator[] 查找或插入元素（仅适用于 unordered_map）
operator[] 是 unordered_map 独有的功能。它不仅可以用于查找元素，还能自动插入不存在的键，且默认值初始化为空。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}};
cout << "Value at key 1: " << myMap[1] << endl; // 输出：One
cout << "Value at key 3 (nonexistent): " << myMap[3] << endl; // 插入新键 3，输出空字符串
return 0;
}
3.3 删除操作详解
删除操作可以从 unordered_map 或 unordered_set 中移除特定的元素或元素范围。主要方法有 erase() 和 clear()。
3.3.1 使用 erase() 删除单个元素
erase() 方法可以通过值或迭代器删除特定元素，或使用区间删除。
unordered_set 中的 erase() 示例：
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet = {1, 2, 3, 4};
mySet.erase(3); // 删除元素 3
for (const auto& elem : mySet) {
cout << elem << " ";
}
return 0;
}
unordered_map 中的 erase() 示例：
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}, {3, "Three"}};
myMap.erase(2); // 删除键为 2 的元素
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
3.3.2 使用 erase() 删除区间
可以指定区间来批量删除元素，erase() 的区间删除适用于需要清空一定范围内的元素。
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> mySet = {1, 2, 3, 4, 5, 6};
auto it1 = mySet.find(2);
auto it2 = mySet.find(5);
mySet.erase(it1, it2); // 删除 [2, 5) 区间的元素
for (const auto& elem : mySet) {
cout << elem << " "; // 输出：1 5 6
}
return 0;
}
3.3.3 使用 clear() 清空容器
clear() 方法可清空 unordered_map 或 unordered_set 中的所有元素，将容器重置为空。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> myMap = {{1, "One"}, {2, "Two"}};
myMap.clear(); // 清空容器
cout << "Size after clear: " << myMap.size() << endl; // 输出：0
return 0;
}
第四章：高级用法
4.1 自定义哈希函数
unordered_map 和 unordered_set 默认使用 std::hash 对元素进行哈希处理，但在某些特殊情况下（例如自定义类型或特定哈希要求），我们需要提供自定义哈希函数。可以通过将自定义哈希结构体作为模板参数传递给容器来实现。
4.1.1 unordered_map 的自定义哈希示例
以下示例演示了如何为一个自定义类型提供哈希函数。假设我们有一个表示二维点的结构体 Point，希望使用 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; // 输出 Point(1, 2), Point(3, 4)
}
return 0;
}
- 解释：
PointHash结构体提供了operator()方法用于计算哈希值。使用异或运算符（^）结合x和y的哈希值，以确保哈希的唯一性。- 将
PointHash作为第三个模板参数传递给unordered_map，实现了对自定义类型Point的存储。
4.2 自定义比较函数
除了自定义哈希函数外，还可以为 unordered_map 和 unordered_set 定义自定义的比较函数。自定义比较函数通常在哈希表需要根据特定规则判断元素相等时使用。
4.2.1 unordered_set 的自定义比较示例
下面的示例展示了如何定义一个 unordered_set，用于存储自定义的 Point 类型，并定义自定义哈希和比较函数。
#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 of pointSet: " << pointSet.size() << endl; // 输出：2
return 0;
}
- 解释：
PointEqual结构体提供了自定义的operator()，用来判断两个Point是否相等。该函数用于元素插入时的相等性判断。- 通过指定
PointHash和PointEqual，可以在unordered_set中存储具有重复点的二维点对象。
第五章：性能分析与优化
5.1 时间复杂度分析
| 操作 | unordered_map 复杂度 | unordered_set 复杂度 |
|---|---|---|
| 插入 | 平均 O(1)，最坏 O(N) | 平均 O(1)，最坏 O(N) |
| 查找 | 平均 O(1)，最坏 O(N) | 平均 O(1)，最坏 O(N) |
| 删除 | 平均 O(1)，最坏 O(N) | 平均 O(1)，最坏 O(N) |
| 遍历 | O(N) | O(N) |
- 说明：由于
unordered_map和unordered_set基于哈希表实现，插入、查找和删除操作在平均情况下均为 O(1) 的时间复杂度。然而，在哈希冲突严重或重新哈希的情况下，复杂度可能降至 O(N)。
5.2 空间复杂度分析
- 空间复杂度：
unordered_map和unordered_set的空间复杂度通常为 O(N)，其中 N 为元素个数。哈希表需要为桶（bucket）分配额外空间，并可能因冲突增加内存消耗。 - 负载因子与重新哈希：负载因子是容器中元素数量与桶数量的比值。当负载因子超过默认值（通常为 1.0），
unordered_map或unordered_set会触发重新哈希。重新哈希会将容器大小扩展到大约原来的两倍，确保哈希效率，但可能造成性能波动。
5.3 性能优化建议
- 选择合适的哈希函数：默认哈希函数在大多数情况下足够有效，但若有复杂结构或特殊需求，自定义哈希函数可有效减少冲突，提高查找速度。
- 避免频繁的重新哈希：频繁插入大量元素时，考虑提前使用
reserve()分配空间，以减少重新哈希带来的性能开销。 - 使用合适的数据结构：
unordered_map和unordered_set适用于无序数据且追求 O(1) 查找和插入的场景，但若需要有序数据或区间查询，建议选择map或set。
总结
unordered_map 和 unordered_set 的优势在于极高的查找和存储效率，为 C++ 提供了直接、高效的哈希存储解决方案。通过深入理解它们的特性、操作和应用场景，我们可以在算法竞赛、数据处理等场景中将其用于去重、统计与快速查找，从而大幅提升程序性能。unordered_map 通过键值对存储复杂数据关系，而 unordered_set 则简单高效地管理唯一元素。希望通过本篇讲解，能够帮助读者在实际开发中更好地运用这些容器，从而提升代码的质量与效率。