【C++进阶】五、STL---unordered_set unordered_set的介绍及使用

创始人

2025-05-28 12:00:34

0次

一、unordered系列关联式容器

二、unordered_set的介绍及使用

2.1 介绍

2.2 使用

三、unordered_map的介绍及使用

3.1 介绍

3.2 使用

一、unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想

最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文只对 unordered_map 和 unordered_set 进行介绍

unordered系列容器的底层结构是是哈希桶

二、unordered_set的介绍及使用

2.1 介绍

unordered_set 的文档介绍：

unordered_set - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set

翻译如下：

unordered_set 是不按特定顺序存储唯一元素的容器，允许基于它们的 key 快速检索单个元素
在 unordered_set 中，元素的值与唯一标识它的 key 同时存在，key 是不可变的，因此，unordered_set 中的元素在容器中不能被修改，但是它可以进行插入和删除
在内部，unordered_set 中的元素不按任何特定顺序排序，而是根据它们的哈希值插入到相应的桶中，允许直接根据它们的值快速访问单个元素(平均时间复杂度恒定，即常数O(1) )
Unordered_set 容器在通过键访问单个元素时比 set 容器更快，尽管它们在通过元素子集进行范围迭代时通常效率较低
容器中的迭代器至少是前向迭代器（只支持单向迭代器 ++）

unordered_set 的模板参数有四个：

第四个模板参数 class Alloc = allocator 是空间配置器，暂时不用理会
第三个模板参数 class Hash = hash 是用于指定哈希函数类型，用于将 Key 类型的对象映射为一个无符号整数，这个整数就是哈希表中元素的索引
第二个模板参数 class Pred = equal_to 是仿函数，用于判断两个 Key 类型的对象是否相等，因为哈希表中可能存在哈希冲突，所以在同一个索引位置上可能会存储多个元素，Pred 就是用来判断这些元素是否相等的
第一个模板参数 class Key 是指定哈希表中元素的键类型，是键值对中 key 的类型

使用 unordered_set 要包含头文件：

#include

2.2 使用

先介绍一下 unordered_set 的前四个成员类型

key_type 是第一个模板参数，即（Key），value_type 也是第一个模板参数（Key），即键值对 pair --> pair
hasher 是第二个模板参数，即（Hash）
key_equal 是第三个模板参数，即（Pred）

unordered_set 的使用与 set 非常类似（参考 set 使用即可），但是由于 unordered_set 使用哈希表实现，所以它的效率更高，适用于需要快速查找、插入和删除元素的场景，注意 unordered_set 的迭代器是单向迭代器，只能++

unordered_set 会对插入重复的元素进行去重，即不允许插入相同的值

例如：

#include 
#include 
using namespace std;int main() 
{unordered_set myset = { 1, 2, 3, 2, 4, 3, 5 }; // 插入重复的元素for (auto it = myset.begin(); it != myset.end(); ++it){cout << *it << " ";}return 0;
}

运行结果

三、unordered_map的介绍及使用

3.1 介绍

unordered_map 的文档介绍：

unordered_map - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map

翻译如下：

unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的 value
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同
在 unordered_map 内部没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map 将相同哈希值的键值对放在相同的桶中
unordered_map 容器通过 key 访问单个元素要比 map 快，但它通常在遍历元素子集的范围迭代方面效率较低
unordered_maps实现了直接访问操作符( operator[] )，它允许使用 key作为参数直接访问 value
它的迭代器至少是前向迭代器（只支持单向迭代器 ++）

unordered_map 的模板参数有五个：

第五个模板参数 class Alloc = allocator 是空间配置器，暂时不用理会
第四个模板参数 class Hash = hash 是用于指定哈希函数类型，用于将 Key 类型的对象映射为一个无符号整数，这个整数就是哈希表中元素的索引
第三个模板参数 class Pred = equal_to 是仿函数，用于判断两个 Key 类型的对象是否相等，因为哈希表中可能存在哈希冲突，所以在同一个索引位置上可能会存储多个元素，Pred 就是用来判断这些元素是否相等的
第二个模板参数 class T 是键值对中 value 的类型
第一个模板参数 class Key 是键值对中 key 的类型

使用 unordered_map 要包含头文件：

#include

3.2 使用

先介绍一下 unordered_map 的前四个成员类型：

key_type 是第一个模板参数，即（Key）
mapped_type 是第二个模板参数，即（T）
value_type 是键值对 pair>
hasher 是第三个模板参数，即（Hash）
key_equal 是第四个模板参数，即（Pred）

unordered_map 的使用与 map 非常类似（参考map即可），但是由于 unordered_map 使用哈希表实现，所以它的效率更高，适用于需要快速查找、插入和删除键值对的场景，注意 unordered_map 的迭代器是单向迭代器，只能++

还有一点，unordered_map 支持随机访问，即通过 Key 进行访问

这里解释跟 set 的 [] 一致，就不解释了

测试代码

void Test()
{unordered_map count;string str[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };for (auto& e : str){count[e]++;}for (auto& kv : count){cout << kv.first << ":" << kv.second << endl;}
}

运行结果

unordered_map 对插入的元素进行去重的方式是根据键（key）是否已存在进行去重的。在 unordered_map 中，每个 key 只能对应一个值，因此如果插入了一个已存在的 key ，那不会进行插入。如果插入的 key 在 unordered_map 中不存在，那么该键值对将被插入到 unordered_map 中

例如：

#include 
#include 
#include 
using namespace std;int main() 
{unordered_map um;um.insert(make_pair(1, "apple"));um.insert(make_pair(2, "banana"));um.insert(make_pair(3, "cherry"));for (auto& it : um){cout << it.first << ": " << it.second << endl;}cout << endl;um.insert(make_pair(2, "orange")); // 插入已存在的键key，插入失败um.insert(make_pair(4, "orange"));// 插入不存在的键key，会插入新键值对  for (auto& e : um){cout << e.first << ": " << e.second << endl;}return 0;
}

运行结果