在C++ STL中的unordered_map
unordered_map是一种关联容器,它存储由键值和映射值组合形成的元素。键值用于唯一识别元素,映射值是与键相关联的内容。键和值都可以是任何类型预定义或用户定义的。简单来说,一个 unordered_map就像一个字典类型的数据结构,它将元素存储在自身中。它包含连续的对 (key, value),这允许基于其唯一键快速检索单个元素。
内部实现 unordered_map 使用哈希表,提供给 map 的键被哈希成哈希表的索引,这就是为什么数据结构的性能很大程度上取决于哈希函数,但平均来说,来自哈希表的搜索、插入和删除的成本是O(1)。
注意: 在最坏情况下,它的时间复杂度可能会从O(1)变成O(n),特别是对于大素数。在这种情况下,强烈建议使用 map 代替,以避免出现超时错误(TLE)。
语法:
unordered_map 语法
以下是演示无序映射的C++程序:
输出:
unordered_map 输出
解释: 这个输出证明的具体事情是,unordered_map 的输出值是以随机键值对为基础产生的,而map则以有序方式显示值和键。
unordered_map vs unordered_set
unordered_map | unordered_set |
---|---|
unordered_map 仅包含 (键-值) 对形式的元素。 | unordered_set 不一定包含以键-值对的形式的元素,主要用于查看集合的存在/不存在。 |
使用运算符 ‘[]’ 提取地图中存在的键的相应值。 | 查找元素是使用 find() 函数进行的,因此不需要运算符”[]” |
注意: 例如,考虑计算单词频率的问题。我们不能使用unordered_set(或set),因为我们不能存储计数,而我们可以使用 unordered_map。
unordered_map vs map
unordered_map | Map |
---|---|
unordered_map键可以以任何方式存储。 | Map是一系列唯一键的有序序列。 |
由于unordered_map实现了不平衡的树结构,因此不可能在元素之间保持顺序。 | Map实现了平衡的树结构,因此可以通过特定的树遍历来保持元素之间的顺序。 |
unordered_map操作的时间复杂度平均为O(1)。 | Map操作的时间复杂度为O(log n)。 |
unordered_map的方法
有很多可用于unordered_map的函数。其中最有用的是:
- operator =
- operator []
- empty
- size for capacity
- begin和end,用于迭代器。
- 查找和计数。
- 插入和删除。
下表显示了unordered_map的所有方法的完整列表:
方法/函数 | 描述 |
---|---|
at() | 此C++ unordered_map函数返回与元素作为键的k相对应的值的引用。 |
begin() | 返回指向unordered_map容器中第一个元素的迭代器。 |
end() | 返回指向unordered_map容器中最后一个元素后面的位置的迭代器。 |
bucket() | 返回元素与键k相对应的存储桶编号。 |
bucket_count | 用于计算unordered_map中桶的总数。不需要传递参数。 |
bucket_size | 返回unordered_map中每个桶中的元素数量。 |
count() | 计算包含给定键的元素数量。 |
equal_range | 返回一个范围,包括序列中所有与键k相等的元素。 |
find() | 返回元素的迭代器。 |
empty() | 检查unordered_map容器是否为空。 |
erase() | 在unordered_map容器中删除元素。 |
C++11库还提供了函数,以查看内部使用的桶计数、桶大小以及使用的哈希函数和各种哈希策略,但在实际应用中它们并不是很有用。我们可以使用迭代器遍历unordered_map的所有元素。
输出
查找单词的词频
给定一串单词,任务是找出单独单词的出现频率:
下面是实现上述方法的C++程序:
输出