Hoshiᅟᅠ     

Hoshiᅟᅠ     

关注
发信
关注(28)粉丝(399)

【C++篇】无序中的法则：探索 STL之unordered_map 与 unordered_set容器的哈希美学

文章目录

C++ unordered_map 和 unordered_set 容器详解

前言

本文将深入探讨 unordered_map 和 unordered_set 的特性、使用方法，以及与有序容器的性能比较。并通过详细的代码示例，帮助您掌握如何在实际开发中利用这些容器优化性能和内存管理。

第一章：unordered_map 和 unordered_set 的概念

1.1 unordered_map 和 unordered_set 的定义

  • unordered_map 是一种关联容器，用于存储键值对（key-value pairs）。在底层实现上，unordered_map 采用哈希表数据结构，以提供近乎常数时间的查找、插入和删除操作。其特性如下：

    • 键值对存储：以键值对形式存储数据，每个键唯一。
    • 无序存储：键的顺序不固定，存储顺序根据哈希函数决定。
    • 高效查找：平均情况下查找时间复杂度为 O(1)。

  • unordered_set 是一种关联容器，仅存储唯一元素，没有键值对结构。unordered_set 同样基于哈希表实现，具有以下特性：

    • 唯一性：每个元素在容器中唯一，不允许重复。
    • 无序存储：元素顺序不固定，由哈希函数决定。
    • 高效查找：查找效率极高，平均复杂度为 O(1)。

1.2 与 map、set 的区别

在功能上，unordered_map 和 unordered_set 类似于 map 和 set，但有一些显著区别：

  1. 底层实现：

    • unordered_map 和 unordered_set 使用哈希表实现，以提供近乎常数时间的查找效率。
    • map 和 set 使用红黑树实现，确保键的有序性，但查找复杂度为 O(log N)。

  2. 元素顺序：

    • unordered_map 和 unordered_set 不保证元素顺序，哈希表根据键的哈希值对元素进行散列存储。
    • map 和 set 保持键的有序性，通常按升序排列。

  3. 迭代器类型：

    • unordered_map 和 unordered_set 提供的是单向迭代器。
    • map 和 set 提供双向迭代器，支持更灵活的遍历。

  4. 键的要求：

    • unordered_map 和 unordered_set 需要键类型支持哈希和相等比较操作。
    • map 和 set 需要键支持小于比较操作，以维持排序关系。

  5. 性能：

    • unordered_map 和 unordered_set 在大多数情况下性能优于 map 和 set，尤其是在频繁查找和插入的场景。
    • map 和 set 的性能较为稳定，但在大规模数据处理上可能不及无序容器。

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

2.1 unordered_map 的常见构造函数

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

2.1.1 示例：使用不同的构造方法

  1. 默认构造函数：创建一个空的 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. 区间构造函数：使用已有容器的一部分元素构造 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;
}

  3. 初始化列表构造：使用初始化列表来初始化 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;
}

2.2 unordered_set 的常见构造函数

2.2.2 示例：使用不同的构造方法

  1. 默认构造函数：创建一个空的 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;
}

  2. 区间构造函数：从已有容器的元素构造 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;
}

  3. 初始化列表构造：使用初始化列表来初始化 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_map 和 unordered_set 的常用操作

3.1 插入操作详解

unordered_map 和 unordered_set 提供了多种插入方法，以满足不同场景的需求。我们将详细探讨常用插入操作，包括 insert()、emplace()、初始化列表插入和区间插入，并对比它们的使用特点和效率。

3.1.1 使用 insert() 插入元素

insert() 是 unordered_map 和 unordered_set 中最常见的插入方法。它不仅可以插入单个元素，还可以插入多个元素、区间或初始化列表中的元素。

  • 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;
}

  • 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;
}

插入效率：insert() 方法的平均时间复杂度为 O(1)，在极少情况下，哈希冲突增多时，可能退化为 O(N)。

3.1.2 使用 emplace() 插入元素

emplace() 方法直接在 unordered_map 或 unordered_set 中构造元素，避免了复制操作。相较于 insert()，emplace() 更高效，尤其在处理复杂对象时。

  • 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;
}

  • 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;
}

应用场景：emplace() 非常适合在需要构造复杂对象且避免额外复制的场景下使用。

3.2 查找操作详解

在 unordered_map 和 unordered_set 中，查找操作是最常用的功能之一，尤其在涉及哈希查找的场景下。主要的查找方法有 find()、count() 和 operator[]，我们将一一详细介绍。

3.2.1 使用 find() 查找元素

find() 返回一个迭代器，指向查找到的元素。如果未找到指定元素，则返回 end() 迭代器。对于哈希查找，find() 的平均时间复杂度为 O(1)。

  • 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;
}

  • 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;
}
3.2.2 使用 count() 查找元素的出现次数

count() 方法用于统计特定元素在 unordered_set 或 unordered_map 中的出现次数。对于 unordered_set，结果只能为 0 或 1，而在 unordered_map 中，count() 返回键出现的次数（同样只能为 0 或 1）。

  • 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;
}

  • 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;
}
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_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;
}

  • 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;
}
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>
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>
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。

总结

以上就是关于【C++篇】无序中的法则：探索 STL之unordered_map 与 unordered_set容器的哈希美学的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

【C++篇】无序中的法则：探索 STL之unordered_map 与 unordered_set容器的哈希美学-LMLPHP

11-11 17:38
Powered by LMLPHP ©2024 Hoshiᅟᅠ      0.005623