【unordered_set和unordered_map】—— 我与C++的不解之缘（二十七）

1. unordered_set 和 unordered_map 简介

在 C++ 标准库中，unordered_set 和 unordered_map 都属于 无序关联容器。它们与 set 和 map 的主要区别在于，它们使用 哈希表 作为底层数据结构，因此它们的元素并不是按照某种顺序存储的，而是根据元素的哈希值存储。哈希表的查找效率通常是常数时间复杂度 O(1)，但最坏情况下是 O(n)。

• unordered_set：是一个无序的集合容器，只存储唯一的元素，类似于 set，但是内部没有元素的顺序。
• unordered_map：是一个无序的映射容器，存储键值对，每个键唯一，类似于 map，但是不保证按键的顺序排列。

更多详细内容可以参考文档：unordered_set 和 unordered_map

2. unordered_set 的基本用法

unordered_set 是一个存储唯一元素的集合，其中元素按哈希值进行存储。常用操作包括插入元素、删除元素、查找元素等。

• unordered_set声明如下，Key就是unordered_set底层关键字的类型
• unordered_set默认要求Key可以转化为整形，如果不支持或者有自己的需求的需要自己实现仿函数(将Key转化为整形)传给第二个模版参数。
• unordered_set底层存储数据的内存都是从空间适配器中申请的，如果自己有需求实现内存池，要传给第四个模版参数
• 一般我们在使用的时候不需要传后三个模版参数。
• unordered_set底层是使用哈希桶实现的，查找的效率为O(1)；但是数据不再有序，所以取名为unordered_set。

2.1 基本操作

#include <iostream>
#include <unordered_set>

using namespace std;
void test_unordered_set()
{
    // 创建一个 unordered_set
    unordered_set<int> uset;
    // 插入元素
    uset.insert(10);
    uset.insert(20);
    uset.insert(30);
    uset.insert(40);
    // 输出所有元素
    cout << "unordered_set contains: ";
    for (const auto& e : uset) {
        cout << e << " ";
    }
    cout << endl;

    // 查找
    if (uset.find(20) != uset.end())
        cout << "Found 20 in the unordered_set!" << endl;
    else
        cout << "20 not found in the unordered_set!" << endl;
    // 删除元素
    uset.erase(30);
    cout << "After erasing 30, unordered_set contains: ";
    for (const auto& e : uset)
        cout << e << " ";
    cout << endl;

    // 判断是否为空
    if (uset.empty())
        cout << "The unordered_set is empty." << endl;
    else
        cout << "The unordered_set is not empty." << endl;

}
int main() {
    test_unordered_set();
    return 0;
}

运行结果：

unordered_set contains: 10 20 30 40
Found 20 in the unordered_set!
After erasing 30, unordered_set contains: 10 20 40
The unordered_set is not empty.

2.2 解释

• insert()：向 unordered_set 中插入元素。插入的元素是唯一的，如果尝试插入重复元素，unordered_set 会忽略它。
• find()：用于查找元素。如果找到，返回指向该元素的迭代器；否则返回 end()。
• erase()：用于删除指定元素。
• empty()：检查集合是否为空。

这里对于其他的函数，就需要去了解它底层的哈希桶结构了，在实现哈希结构时再去深入探究。

2.3 unordered_set和set的区别

通过查看文档已经使用unoedered_set，我们可以发现unordered_set和set支持的增删查改是一模一样的，我们现在就来看一下它们有什么不同：

• 首先set的底层是红黑树，而unordered_set底层是哈希表。
• 其次它们对于key的要求不同，set要求key支持比较；而unoedered_set要求key支持转化成整型且要支持比较。
• 然后就是迭代器的不同，set的iterator是双向迭代器，而unordered_set的iterator是单向迭代器；set底层是红黑树，set的迭代器是有序+去重的；而unoedered_set底层是哈希桶，unoedered_set是无序+去重的。
• 最后就是性能上的差异，对于大多数场景下unoedered_set增删查改的效率要高于set的；（红黑树的效率是O(log N)，哈希表的效率是O(1)。

至于其中细节上的不同，要了解了unordered_set的底层哈希表，才能真正理解。

3. unordered_map 的基本用法

unordered_map 是一个哈希表实现的键值对容器，类似于 map，但是它的元素不按键排序。

unordered_map和unordered_set都是用哈希表进行封装实现的，这里就不过多描述了，和unordered_set十分相似。

3.1 基本操作

#include <iostream>
#include <unordered_map>
using namespace std;
void test_unordered_map()
{
    //创建一个 unordered_map
    unordered_map<string, int> umap;
    //和map的operator[]一样，可以用来插入数据
    umap["apple"] = 2;
    umap["banana"] = 5;
    umap["orange"] = 3;
    //输出
    cout << "unordered_map contains:" << endl;
    for (const auto& pair : umap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    //查找
    auto it = umap.find("banana");
    if (it != umap.end())
        cout << "Found 'banana' with value " << it->second << endl;
    else
        cout << "'banana' not found in the unordered_map!" << endl;
    //删除
    umap.erase("orange");
    cout << "After erasing 'orange', unordered_map contains:" << endl;
    for (const auto& pair : umap)
        cout << pair.first << ": " << pair.second << endl;
    // 检查是否存在某个key
    if (umap.count("apple") > 0)
        std::cout << "'apple' exists in the unordered_map." << std::endl;
}
int main() {
    test_unordered_map();
    return 0;
}

运行结果：

unordered_map contains:
apple: 2
banana: 5
orange: 3
Found 'banana' with value 5
After erasing 'orange', unordered_map contains:
apple: 2
banana: 5
"apple" exists in the unordered_map.

3.2 解释

• 插入元素：unordered_map 支持通过下标（[]）或者 insert() 插入元素。若键已存在，通过下标访问时会更新其对应的值。
• find()：查找给定键是否存在，返回指向该元素的迭代器，如果元素不存在，返回 end()。
• erase()：删除指定键值对。
• count()：检查容器中是否存在指定的键。

3.3 unordered_map和map的区别

这里set和map都是使用红黑树封装实现的，而unordered_set和unordered_map都是使用哈希表封装实现的。

unordered_map和map的区别与unordered_set和set的区别是大差不差的。

• 首先map的底层是红黑树，而unordered_map底层是哈希表。
• 其次它们对于key的要求不同，map要求key支持比较；而unoedered_map要求key支持转化成整型且要支持比较。
• 然后就是迭代器的不同，map的iterator是双向迭代器，而unordered_map的iterator是单向迭代器；map底层是红黑树，map的迭代器是有序+去重的；而unoedered_map底层是哈希桶，unoedered_map是无序+去重的。
• 最后就是性能上的差异，对于大多数场景下unoedered_map增删查改的效率要高于map的；（红黑树的效率是O(log N)，哈希表的效率是O(1)。

4. 性能分析

这一部分，我们要学习底层哈希表以后才会深入理解；这里简单说一下

底层的哈希表使用的是哈希桶结构（就是顺序表中存储链表，这样可以避免冲突的问题）。

unordered_set 和 unordered_map 的查找、插入和删除操作平均时间复杂度为 O(1)。不过，由于哈希冲突的存在，最坏情况下时间复杂度会退化为 O(n)，即所有元素都映射到同一个哈希桶中。

• 哈希冲突：为了减少哈希冲突，C++ 中的 unordered_set 和 unordered_map 使用了哈希表和动态扩展机制，使得哈希表的负载因子保持在合理范围内，避免性能急剧下降。
• 负载因子：容器的负载因子是元素数量与桶数量的比值，当负载因子达到某个阈值时，容器会自动增加桶的数量，从而保持查找效率。

6. unordered_multimap和unordered_multiset

• unordered_multimap/unordered_multiset和multimap/multiset功能完全类似，支持key冗余

这里就不过多描述了，有需要了解的可以参考一下之前的文章讲解：

【map与set】—— 我与C++的不解之缘（二十二）

到这里本篇文章内容就结束了，感谢各位的支持！！！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws