【C++ map结构 】std::map 和 std::unordered_map 在使用上的差异

简介: 【C++ map结构 】std::map 和 std::unordered_map 在使用上的差异

原理上的差异

std::unordered_mapstd::map 都是 C++ 标准库中的关联容器,用于存储键值对。但它们之间存在一些关键的差异:

  1. 内部实现:
  • std::map: 基于红黑树实现,是一个平衡二叉搜索树。
  • std::unordered_map: 基于哈希表实现。
  1. 顺序:
  • std::map: 由于是基于红黑树,键值对总是按键的顺序排序。
  • std::unordered_map: 如其名所示,键值对的顺序是无序的。
  1. 性能:
  • std::map: 查找、插入和删除的时间复杂度通常为 O(log n)。
  • std::unordered_map: 在平均情况下,查找、插入和删除的时间复杂度为 O(1)。但在最坏的情况下,这些操作的时间复杂度可能会达到 O(n)。
  1. 哈希函数:
  • std::map: 不使用哈希函数。
  • std::unordered_map: 使用哈希函数来确定元素在哈希表中的位置。
  1. 用途:
  • std::map: 当你需要有序的键值对或需要频繁地进行范围查询时,使用 std::map 是更好的选择。
  • std::unordered_map: 当你不需要有序的键值对,并且主要关心查找、插入和删除的速度时,使用 std::unordered_map 是更好的选择。
  1. 空间使用:
  • std::map: 由于红黑树的结构,它可能会使用更多的内存。
  • std::unordered_map: 通常使用较少的内存,但如果哈希表的负载因子过高,可能会导致重新哈希,这可能会暂时增加内存使用。

选择哪一个容器取决于你的具体需求。如果你需要有序的数据或范围查询,std::map 是更好的选择。如果你关心性能并且不需要有序的数据,std::unordered_map 可能是更好的选择。

确实,std::mapstd::unordered_map 在构造时有一些差异,主要是由于它们的内部实现方式不同。下面我们详细讨论这两者在构造时的差异:

构造之间的差异

1. std::map 的构造:

std::map 的构造相对简单,因为它是基于红黑树实现的。以下是一些常见的构造方法:

  • 默认构造:创建一个空的 std::map
std::map<std::string, int> m1;
  • 范围构造:使用另一个容器的元素范围来构造。
std::pair<std::string, int> arr[] = {{"Alice", 90}, {"Bob", 85}};
std::map<std::string, int> m2(arr, arr + 2);
  • 拷贝构造:使用另一个 std::map 来构造。
std::map<std::string, int> m3(m2);
  • 移动构造:使用另一个 std::map 的内容来构造,并使原 std::map 为空。
std::map<std::string, int> m4(std::move(m3));
  • 初始化列表构造
std::map<std::string, int> m5 = {{"Alice", 90}, {"Bob", 85}};

2. std::unordered_map 的构造:

由于 std::unordered_map 是基于哈希表实现的,它在构造时提供了一些额外的选项,主要与哈希函数和等价关系有关。

  • 默认构造:创建一个空的 std::unordered_map
std::unordered_map<std::string, int> um1;
  • 范围构造
std::pair<std::string, int> arr[] = {{"Alice", 90}, {"Bob", 85}};
std::unordered_map<std::string, int> um2(arr, arr + 2);
  • 拷贝构造
std::unordered_map<std::string, int> um3(um2);
  • 移动构造
std::unordered_map<std::string, int> um4(std::move(um3));
  • 初始化列表构造
std::unordered_map<std::string, int> um5 = {{"Alice", 90}, {"Bob", 85}};
  • 指定桶数量的构造:可以在构造时指定初始桶数量,这有助于优化性能。
std::unordered_map<std::string, int> um6(50); // 50个桶
  • 使用自定义哈希函数和等价关系的构造
struct MyHash {
    size_t operator()(const std::string& s) const {
        // 自定义哈希函数
        return std::hash<std::string>()(s);
    }
};
struct MyEqual {
    bool operator()(const std::string& a, const std::string& b) const {
        // 自定义等价关系
        return a == b;
    }
};
std::unordered_map<std::string, int, MyHash, MyEqual> um7;

总的来说,std::mapstd::unordered_map 在基本构造方法上都很相似,但 std::unordered_map 提供了一些额外的选项,允许用户更好地控制其哈希表的行为。

需要自定义哈希函数的情况

std::unordered_map 在某些情况下需要自定义哈希函数,而 std::map 不需要。这主要是因为 std::unordered_map 是基于哈希表的,而 std::map 是基于红黑树的。

以下是一些需要为 std::unordered_map 提供自定义哈希函数的情况:

  1. 自定义对象作为键:当你使用自定义类型作为键时,C++ 标准库可能不知道如何为这种类型生成哈希值。在这种情况下,你需要提供自定义哈希函数。
struct Student {
    std::string name;
    int age;
};
struct StudentHash {
    size_t operator()(const Student& s) const {
        return std::hash<std::string>()(s.name) ^ std::hash<int>()(s.age);
    }
};
std::unordered_map<Student, int, StudentHash> scores;
  1. 优化性能:即使对于标准库知道如何哈希的类型,你仍然可能想要提供自定义哈希函数,以优化特定数据集的性能。例如,如果你知道键的某些属性,你可以设计一个更有效的哈希函数。
  2. 避免冲突:如果默认的哈希函数导致太多的冲突,你可能希望提供一个自定义的哈希函数,以减少冲突并提高性能。

对于 std::map,你不需要提供哈希函数,因为它不是基于哈希的。但是,如果你使用自定义类型作为键,你需要确保该类型支持 < 运算符,或者你可以提供自定义的比较函数。这是因为 std::map 需要能够比较键来在红黑树中正确地放置它们。

总之,当使用 std::unordered_map 时,你可能需要提供自定义哈希函数,特别是当使用自定义类型作为键时。而对于 std::map,你只需要确保键类型支持排序即可。

接口使用上的差异

在接口使用方面,std::mapstd::unordered_map 有很多相似之处,这使得在许多情况下可以相对容易地在两者之间切换。但是,由于它们的内部实现和特性不同,还是存在一些差异。以下是一些关键点:

  1. 插入:
  • 对于两者,你都可以使用 insert 方法或 operator[] 来插入键值对。
  1. 查找:
  • std::mapstd::unordered_map 都提供了 find 方法来查找特定的键。
  1. 删除:
  • 两者都使用 erase 方法来删除键值对。
  1. 取值:
  • 使用 operator[]at 方法可以从两种映射中获取值。但要注意,operator[] 在键不存在时会插入该键并默认初始化其值。
  1. 遍历:
  • 由于 std::map 是有序的,你可以期望按键的顺序遍历它。而 std::unordered_map 的遍历顺序是不确定的。
  1. 特定功能:
  • std::map 有一些 std::unordered_map 没有的方法,如 lower_boundupper_bound,这些方法用于范围查询。
  • std::unordered_map 允许你访问和修改其哈希函数和负载因子,这些在 std::map 中不适用。

总的来说,对于基本的插入、查找、删除和取值操作,两者的接口非常相似,可以相对无缝地替换。但是,如果你的代码依赖于 std::map 的排序特性或使用了特定于其中一个容器的功能,那么替换可能会更加复杂。在进行替换之前,最好仔细检查代码以确保没有任何潜在的问题。


代码举例

使用方式相似的场景:存储学生的成绩

#include <iostream>
#include <map>
#include <unordered_map>
int main() {
    // 使用 std::map
    std::map<std::string, int> studentScoresMap;
    studentScoresMap["Alice"] = 90;
    studentScoresMap["Bob"] = 85;
    studentScoresMap["Charlie"] = 88;
    // 查找学生的成绩
    if (studentScoresMap.find("Alice") != studentScoresMap.end()) {
        std::cout << "Alice's score: " << studentScoresMap["Alice"] << std::endl;
    }
    // 使用 std::unordered_map
    std::unordered_map<std::string, int> studentScoresUnorderedMap;
    studentScoresUnorderedMap["Alice"] = 90;
    studentScoresUnorderedMap["Bob"] = 85;
    studentScoresUnorderedMap["Charlie"] = 88;
    // 查找学生的成绩
    if (studentScoresUnorderedMap.find("Alice") != studentScoresUnorderedMap.end()) {
        std::cout << "Alice's score: " << studentScoresUnorderedMap["Alice"] << std::endl;
    }
    return 0;
}

在上述代码中,我们使用 std::mapstd::unordered_map 的方式几乎完全相同。

使用方式不同的场景:存储并按顺序遍历学生的成绩

#include <iostream>
#include <map>
#include <unordered_map>
int main() {
    // 使用 std::map
    std::map<std::string, int> studentScoresMap;
    studentScoresMap["Charlie"] = 88;
    studentScoresMap["Alice"] = 90;
    studentScoresMap["Bob"] = 85;
    // 按学生姓名的字母顺序遍历成绩
    std::cout << "Using std::map:" << std::endl;
    for (const auto& pair : studentScoresMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 使用 std::unordered_map
    std::unordered_map<std::string, int> studentScoresUnorderedMap;
    studentScoresUnorderedMap["Charlie"] = 88;
    studentScoresUnorderedMap["Alice"] = 90;
    studentScoresUnorderedMap["Bob"] = 85;
    // 遍历成绩(顺序不确定)
    std::cout << "Using std::unordered_map:" << std::endl;
    for (const auto& pair : studentScoresUnorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

在这个例子中,使用 std::map 可以确保按学生姓名的字母顺序遍历成绩,而使用 std::unordered_map 则不能保证遍历的顺序。这是两者在使用上的一个主要区别。

结语

在我们的编程学习之旅中,理解是我们迈向更高层次的重要一步。然而,掌握新技能、新理念,始终需要时间和坚持。从心理学的角度看,学习往往伴随着不断的试错和调整,这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误,我们应该将其视为学习和进步的机会,而不仅仅是困扰。通过理解和解决这些问题,我们不仅可以修复当前的代码,更可以提升我们的编程能力,防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来,不断提升自己的编程技术。无论你是初学者还是有经验的开发者,我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用,不妨点击收藏,或者留下你的评论分享你的见解和经验,也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持,也是对我持续分享和创作的动力。

目录
相关文章
|
4天前
|
C语言 C++
C/C++ 自定义头文件,及头文件结构详解
还是从"stdio.h"说起,这是C语言中内置的标准库,也就是说,头文件很多时候其实就是一个“库”,类似于代码的仓库,也就是说将某些具有特定功能的常量、宏、函数等归为一个大类,然后放进这个“仓库”,就像stdio.h就是一个标准输入/输出的头文件
34 1
|
4天前
|
存储 编译器 C++
C++:map&set 对红黑树的封装
C++:map&set 对红黑树的封装
11 1
|
4天前
|
存储 C++ 容器
C++:STL - set & map
C++:STL - set & map
16 4
|
4天前
|
存储 算法 数据安全/隐私保护
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
7 0
|
4天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
10 1
|
4天前
|
存储 搜索推荐 C++
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构
【C++高阶(二)】熟悉STL中的map和set --了解KV模型和pair结构
|
4天前
|
C++
【C++】std::string 转换成非const类型 char* 的三种方法记录
【C++】std::string 转换成非const类型 char* 的三种方法记录
8 0
|
4天前
|
存储 自然语言处理 C++
c++的学习之路:25、map与set
c++的学习之路:25、map与set
15 0
|
4天前
|
存储 C++ 容器
【C++初阶】STL详解(十)set、map、multiset、multimap的介绍及使用
【C++初阶】STL详解(十)set、map、multiset、multimap的介绍及使用
35 0
|
4天前
|
容器
C++map/multimap容器
C++map/multimap容器