C++之unordered_set和unordered_map基本介绍

引言

在前文对map和set进行自我实现后，也对map和set有了不少的认知。但利用树状结构的效率O（logN）仍然不尽如人意。
而此文提出的哈希容器，效率达到了O（1）,底层是基于哈希表实现的。
哈希表的相关内容，在下篇文章会给到详细说明。

请添加图片描述

unordered_set和unordered_map是两个非常重要的关联容器，它们提供了基于哈希表的快速查找、插入和删除操作。

• unordered_set：存储唯一键的集合，每个元素只出现一次
• unordered_map：存储键值对，每个键唯一对应一个值

一.unordered_set

在这里插入图片描述

1.1概述

unordered_set 是一个不包含重复元素的集合容器。它通过哈希函数将元素映射到存储位置，从而实现快速的查找操作。由于元素的存储顺序是根据哈希值确定的，因此 unordered_set 中的元素顺序是无序的。 由于unordered_set和set增删查以及使用基本一致，在这里就不做过多赘述

1.2与set的差异

对key的要求

unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理unordered_set的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

一、set 对键的要求

• （一）比较操作 set 是基于红黑树实现的有序容器，它需要对键进行比较以维护元素的有序性。因此，set 要求键类型必须支持比较操作，通常通过提供一个比较函数来实现。默认情况下，set 使用 std::less<T> 作为比较函数，它要求键类型必须支持 < 操作符。
• （二）唯一性 set 中的键是唯一的，不允许重复。如果尝试插入一个已经存在的键，插入操作将不会执行。

二、unordered_set 对键的要求

• （一）哈希函数 unordered_set 是基于哈希表实现的无序容器，它需要对键进行哈希操作以确定键的存储位置。因此，unordered_set 要求键类型必须提供一个哈希函数。默认情况下，unordered_set 使用 std::hash<T> 作为哈希函数，但并非所有类型都提供了默认的哈希函数。如果键类型没有默认的哈希函数，需要自定义哈希函数。
• （二）唯一性 unordered_set 中的键也是唯一的，不允许重复。如果尝试插入一个已经存在的键，插入操作将不会执行。

迭代器差异

unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

性能差异

unordered_set的增删查改更快⼀些，因为红⿊树增删查改效率是O（logN） ，⽽哈希表增删查平均效率是O（1）

二、unordered_map

在这里插入图片描述

2.1概述

unordered_map 是一个键值对的集合，其中每个键都是唯一的。它也基于哈希表实现，通过哈希函数将键映射到存储位置。与 unordered_set 类似unordered_map 中的元素顺序是无序的。

2.2与map的差异

对key的要求

一、map 对 key 的要求

map 是基于红黑树实现的有序关联容器，它对键的要求主要体现在以下几个方面：

• （一）必须能够比较大小 由于 map 是有序的，它需要对键进行排序。因此，键的类型必须能够进行比较大小。默认情况下，map 使用 std::less<Key> 来比较键的大小。这意味着键的类型必须支持 < 运算符。

例如，如果键的类型是 int 或 string，它们都支持 < 运算符，因此可以直接用作 map 的键。

map<int, string> intMap; // int 支持 < 运算符
map<string, int> stringMap; // string 支持 < 运算符

如果键的类型是一个自定义类型，那么需要提供一个比较函数。

• （二）键必须是唯一的 map 中的每个键都是唯一的，不允许重复。如果尝试插入一个已经存在的键，插入操作将不会执行，或者会更新该键对应的值。

二、unordered_map 对 key 的要求

unordered_map 是基于哈希表实现的无序关联容器，它对键的要求主要体现在以下几个方面：

• （一）必须能够计算哈希值 由于 unordered_map 是基于哈希表实现的，它需要对键进行哈希运算。因此，键的类型必须能够计算哈希值。默认情况下，unordered_map 使用 std::hash<Key> 来计算键的哈希值。

例如，如果键的类型是 int 或 string，它们都支持 std::hash，因此可以直接用作 unordered_map 的键。

unordered_map<int, string> intMap; // int 支持 std::hash
unordered_map<string, int> stringMap; // string 支持 std::hash

如果键的类型是一个自定义类型，那么需要提供一个哈希函数。

• （二）键必须是唯一的 和 map 一样，unordered_map 中的每个键也必须是唯一的，不允许重复。如果尝试插入一个已经存在的键，插入操作将不会执行，或者会更新该键对应的值。

迭代器的差异

map的iterator是双向迭代器，unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，代器遍历是Key⽆序+去重。

性能的差异

整体⽽⾔⼤多数场景下，unordered_map的增删查改更快⼀些，因为红⿊树增删查改效率是O（logN） ，⽽哈希表增删查平均效率是O（1）

三.unordered_multimap以及unordered_multiset

• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。
• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异，key的要求的差异，iterator及遍历顺序的差异，性能的差异。