std : : unordered_map 、 std : : unordered_set

一.简介

std::unordered_map 是C++标准库中的一种关联容器，它提供了一种用于存储键-值对的数据结构，其中键是唯一的，且不会按特定顺序排序。与 std::map 不同，std::unordered_map 使用哈希表作为其底层数据结构，因此它具有 O(1) 平均时间复杂度的查找操作。

注意：

• std::unordered_map 使用哈希表作为其底层数据结构。哈希表是一种将键映射到存储位置的数据结构，而不是按顺序存储键值对的容器。哈希表使用哈希函数来计算键的哈希值，然后将键值对存储在哈希表的相应存储桶中。因为哈希表的工作原理不涉及元素之间的比较，而是基于哈希值的，所以它没有元素之间的自然排序。
• std::unordered_map 的设计目标是提供高效的查找操作，平均情况下具有 O(1) 复杂度的插入、删除和查找操作。为了实现这一目标，它牺牲了元素的有序性。因此，std::unordered_map 不提供自定义比较器的功能，因为元素的排序在哈希表中没有意义。

std::unordered_set 是C++标准库中的一种关联容器，它用于存储不重复的元素集合，不会按特定顺序排序。与 std::set 不同，std::unordered_set 使用哈希表作为其底层数据结构，因此具有 O(1) 平均时间复杂度的插入、删除和查找操作。

注意：

• std::unordered_set 是一个无序的容器，元素是不重复的，它不支持自定义排序或提供比较器。因为它使用哈希表来组织元素，元素的存储和检索不是基于比较操作的，而是通过哈希值来实现的。所以，std::unordered_set 不允许定义元素之间的比较器。

二.STL中map、set、unordered_set、unordered_map的区别和应用场景

map

        map支持键值的自动排序，底层机制是红黑树，红黑树的查询和维护时间复杂度均为 O(logn) ，但是占用空间比较大，因为每个节点都要保持父节点、孩子节点及颜色信息。

set

        set与map类似，set的底层实现通常也是红黑树。set是一种特殊的Map，只有键没有值。

unordered_map 

        unordered_map是C++ 11 新添加的容器，底层机制是哈希表，通过hash函数计算元素位置，其查询时间复杂度为 O(1) ，维护时间与 buclet 桶所维护的 list 长度有固安，但是建立 hash 表耗时较大。

unordered_set

        unordered_set与unordered_map 类似，unordered_set的底层实现通常也是哈希表。unordered_set 是一种特殊的unordered_map，只有键没有值。

从底层机制和特点可以看出：map适用于有序数据的应用场景，unordered_map适用于高效查询的应用场景。