C++ STL 容器详解：unordered_map 与 unordered_set 用法及性能分析

第二章：unordered_map 和 unordered_set 的构造方法

2.1 unordered_map 的常见构造函数

unordered_map 提供了多种构造函数，允许灵活初始化容器。以下是常用的构造方法和功能：

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 的常见构造函数

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)。

5.2 空间复杂度分析

• 空间复杂度：unordered_map 和 unordered_set 的空间复杂度通常为 O(N)，其中 N 为元素个数。哈希表需要为桶（bucket）分配额外空间，并可能因冲突增加内存消耗。
• 负载因子与重新哈希：负载因子是容器中元素数量与桶数量的比值。当负载因子超过默认值（通常为 1.0），unordered_map 或 unordered_set 会触发重新哈希。重新哈希会将容器大小扩展到大约原来的两倍，确保哈希效率，但可能造成性能波动。

5.3 性能优化建议

1. 选择合适的哈希函数：默认哈希函数在大多数情况下足够有效，但若有复杂结构或特殊需求，自定义哈希函数可有效减少冲突，提高查找速度。
2. 避免频繁的重新哈希：频繁插入大量元素时，考虑提前使用 reserve() 分配空间，以减少重新哈希带来的性能开销。
3. 使用合适的数据结构：unordered_map 和 unordered_set 适用于无序数据且追求 O(1) 查找和插入的场景，但若需要有序数据或区间查询，建议选择 map 或 set。

总结

unordered_map 和 unordered_set 的优势在于极高的查找和存储效率，为 C++ 提供了直接、高效的哈希存储解决方案。通过深入理解它们的特性、操作和应用场景，我们可以在算法竞赛、数据处理等场景中将其用于去重、统计与快速查找，从而大幅提升程序性能。unordered_map 通过键值对存储复杂数据关系，而 unordered_set 则简单高效地管理唯一元素。希望通过本篇讲解，能够帮助读者在实际开发中更好地运用这些容器，从而提升代码的质量与效率。