目录
基础介绍
unordered_map和unordered_set接口介绍
std::unordered_map 接口
std::unordered_set 接口
unordered系列与红黑树实现的容器对比
性能特点
元素顺序
内存使用
自定义比较函数
常见操作
实用场景
重新哈希
基础介绍
在C++中,unordered
系列容器是C++11标准引入的一种新的容器类型,它们是基于哈希表实现的。与std::map
和std::set
这些基于红黑树实现的有序容器不同,unordered
系列容器不保证元素的顺序,但通常在插入和查找操作上提供了更优的平均时间复杂度,即O(1)。
以下是unordered
系列容器的主要成员:
-
std::unordered_map
:- 它是一个将键映射到值的容器,键是唯一的。
- 允许快速检索所存储的元素。
- 不按顺序存储元素。
-
std::unordered_multimap
:- 类似于
unordered_map
,但是它允许键不是唯一的,即一个键可以映射到多个值。
- 类似于
-
std::unordered_set
:- 它是一个存储唯一元素的集合,元素的值同时也是键。
- 元素通常按照哈希值组织的,因此元素的顺序是未定义的。
-
std::unordered_multiset
:- 类似于
unordered_set
,但它允许存储多个具有相同值的元素。
- 类似于
以下是unordered
系列容器的一些特点:
- 哈希表实现:这些容器内部使用哈希表来存储元素,这意味着它们通常在元素查找、插入和删除操作上非常高效。
- 无序:元素在容器中的顺序是根据它们的哈希值来确定的,因此每次遍历时元素的顺序可能都不同,除非元素被插入或删除。
- 自定义哈希函数:可以提供自定义的哈希函数来优化特定类型键的分布。
- 负载因子:容器可以指定一个负载因子,它决定了何时容器应该重新哈希以维持操作效率。当元素数量与桶数量的比例超过负载因子时,容器会自动增加桶的数量,并进行重新哈希。
- 桶接口:提供了直接访问哈希表“桶”的接口,允许对特定桶的元素进行操作。
使用unordered
系列容器时,需要包含头文件<unordered_map>
或<unordered_set>
。
unordered_map和unordered_set接口介绍
std::unordered_map
和std::unordered_set
都提供了丰富的接口,用于管理容器中的元素。下面是它们的一些主要接口的介绍:
std::unordered_map
接口
-
构造和析构:
unordered_map()
: 默认构造函数。unordered_map(size_type n)
: 构造具有至少n
个桶的容器。unordered_map(const unordered_map& umap)
: 复制构造函数。~unordered_map()
: 析构函数。
-
迭代器:
begin()
: 返回指向容器第一个元素的迭代器。end()
: 返回指向容器最后一个元素之后位置的迭代器。cbegin()
: 返回指向容器第一个元素的常量迭代器。cend()
: 返回指向容器最后一个元素之后位置的常量迭代器。
-
容量:
size()
: 返回容器中元素的数量。max_size()
: 返回容器可以容纳的最大元素数量。empty()
: 检查容器是否为空。reserve(size_type n)
: 为容器分配至少能容纳n
个元素的存储空间。bucket_count()
: 返回容器中桶的数量。max_bucket_count()
: 返回容器可以拥有的最大桶数。
-
元素访问:
operator[]
: 通过键访问或插入元素。at(key)
: 通过键访问元素,如果键不存在则抛出异常。
-
修改器:
insert(const value_type& val)
: 插入元素。emplace(const key_type& k, Args&&... args)
: 构造并插入元素。erase(const_iterator position)
: 删除迭代器指向的元素。erase(const key_type& k)
: 删除键为k
的元素。clear()
: 清空容器。
-
哈希政策:
load_factor()
: 返回当前负载因子。max_load_factor()
: 返回或设置最大负载因子。rehash(size_type n)
: 重新哈希容器,使得桶的数量至少为n
。
-
桶接口:
begin(size_type n)
: 返回第n
个桶的第一个元素的迭代器。end(size_type n)
: 返回第n
个桶的最后一个元素之后位置的迭代器。bucket(const key_type& k)
: 返回键k
所在的桶的索引。bucket_size(size_type n)
: 返回第n
个桶中元素的数量。
std::unordered_set
接口
std::unordered_set
的接口与std::unordered_map
非常相似,不过由于它只存储键而不存储值,因此它的接口不包括那些与值相关的操作。
-
构造和析构:
- 与
unordered_map
类似。
- 与
-
迭代器:
- 与
unordered_map
类似。
- 与
-
容量:
- 与
unordered_map
类似。
- 与
-
元素访问:
- 不提供
operator[]
或at()
,因为unordered_set
只存储键。
- 不提供
-
修改器:
- 与
unordered_map
类似,但不包括插入键值对的操作。
- 与
-
哈希政策:
- 与
unordered_map
类似。
- 与
-
桶接口:
- 与
unordered_map
类似。
- 与
使用这些接口时,通常需要包含头文件<unordered_map>
(对于unordered_map
)或<unordered_set>
(对于unordered_set
)。这些接口提供了灵活的方式来管理哈希表中的元素,允许高效的查找、插入和删除操作。
unordered系列与红黑树实现的容器对比
unordered
系列容器(如std::unordered_map
和std::unordered_set
)与基于红黑树实现的容器(如std::map
和std::set
)在多个方面存在差异。以下是两者之间的对比:
性能特点
-
查找时间复杂度:
unordered
系列容器:平均情况下为O(1),在最坏情况下为O(n)(当所有元素哈希到同一个桶中时)。- 红黑树容器:为O(log n),在最坏情况下也是O(log n),因为红黑树保持平衡。
-
插入和删除时间复杂度:
unordered
系列容器:平均情况下为O(1),但可能需要O(n)进行重新哈希。- 红黑树容器:为O(log n),因为需要维护树的平衡。
元素顺序
unordered
系列容器:不保证元素的顺序,元素根据哈希值分布在桶中。- 红黑树容器:元素按键的顺序排序,即总是有序的。
内存使用
unordered
系列容器:通常需要更多的内存来存储哈希表结构。- 红黑树容器:内存使用通常更为紧凑,因为只需要存储树节点。
自定义比较函数
unordered
系列容器:允许自定义哈希函数和相等比较函数。- 红黑树容器:允许自定义比较函数来定义元素的排序顺序。
常见操作
-
unordered
系列容器:- 适用于快速查找、插入和删除操作。
- 不适合需要有序遍历的场景。
-
红黑树容器:
- 适用于需要元素有序的场景。
- 提供了范围查询操作,如
lower_bound
和upper_bound
。
实用场景
unordered
系列容器:当元素顺序不重要,且需要快速的查找性能时,例如缓存实现。- 红黑树容器:当元素需要保持有序,或者需要频繁进行范围查询时,例如数据库索引。
重新哈希
unordered
系列容器:当负载因子超过一定阈值时,容器会自动进行重新哈希,这可能会是一个相对昂贵的操作。- 红黑树容器:不需要重新哈希,但可能会进行节点重新平衡。
总的来说,选择哪种容器取决于具体的应用场景和性能需求。如果对元素顺序没有要求,并且需要快速的访问速度,unordered
系列容器可能是更好的选择。如果需要元素保持有序,或者频繁进行范围查询,那么基于红黑树的容器会更有优势。