unordered系列的容器

目录

基础介绍

unordered_map和unordered_set接口介绍

std::unordered_map 接口

std::unordered_set 接口

unordered系列与红黑树实现的容器对比

性能特点

元素顺序

内存使用

自定义比较函数

常见操作

实用场景

重新哈希

---

基础介绍

在C++中，unordered系列容器是C++11标准引入的一种新的容器类型，它们是基于哈希表实现的。与std::map和std::set这些基于红黑树实现的有序容器不同，unordered系列容器不保证元素的顺序，但通常在插入和查找操作上提供了更优的平均时间复杂度，即O(1)。

以下是unordered系列容器的主要成员：

1. std::unordered_map：

   • 它是一个将键映射到值的容器，键是唯一的。
   • 允许快速检索所存储的元素。
   • 不按顺序存储元素。

2. std::unordered_multimap：

   • 类似于unordered_map，但是它允许键不是唯一的，即一个键可以映射到多个值。

3. std::unordered_set：

   • 它是一个存储唯一元素的集合，元素的值同时也是键。
   • 元素通常按照哈希值组织的，因此元素的顺序是未定义的。

4. std::unordered_multiset：

   • 类似于unordered_set，但它允许存储多个具有相同值的元素。

以下是unordered系列容器的一些特点：

• 哈希表实现：这些容器内部使用哈希表来存储元素，这意味着它们通常在元素查找、插入和删除操作上非常高效。
• 无序：元素在容器中的顺序是根据它们的哈希值来确定的，因此每次遍历时元素的顺序可能都不同，除非元素被插入或删除。
• 自定义哈希函数：可以提供自定义的哈希函数来优化特定类型键的分布。
• 负载因子：容器可以指定一个负载因子，它决定了何时容器应该重新哈希以维持操作效率。当元素数量与桶数量的比例超过负载因子时，容器会自动增加桶的数量，并进行重新哈希。
• 桶接口：提供了直接访问哈希表“桶”的接口，允许对特定桶的元素进行操作。

使用unordered系列容器时，需要包含头文件<unordered_map>或<unordered_set>。

unordered_map和unordered_set接口介绍

std::unordered_map和std::unordered_set都提供了丰富的接口，用于管理容器中的元素。下面是它们的一些主要接口的介绍：

std::unordered_map 接口

1. 构造和析构:

   • unordered_map(): 默认构造函数。
   • unordered_map(size_type n): 构造具有至少n个桶的容器。
   • unordered_map(const unordered_map& umap): 复制构造函数。
   • ~unordered_map(): 析构函数。

2. 迭代器:

   • begin(): 返回指向容器第一个元素的迭代器。
   • end(): 返回指向容器最后一个元素之后位置的迭代器。
   • cbegin(): 返回指向容器第一个元素的常量迭代器。
   • cend(): 返回指向容器最后一个元素之后位置的常量迭代器。

3. 容量:

   • size(): 返回容器中元素的数量。
   • max_size(): 返回容器可以容纳的最大元素数量。
   • empty(): 检查容器是否为空。
   • reserve(size_type n): 为容器分配至少能容纳n个元素的存储空间。
   • bucket_count(): 返回容器中桶的数量。
   • max_bucket_count(): 返回容器可以拥有的最大桶数。

4. 元素访问:

   • operator[]: 通过键访问或插入元素。
   • at(key): 通过键访问元素，如果键不存在则抛出异常。

5. 修改器:

   • insert(const value_type& val): 插入元素。
   • emplace(const key_type& k, Args&&... args): 构造并插入元素。
   • erase(const_iterator position): 删除迭代器指向的元素。
   • erase(const key_type& k): 删除键为k的元素。
   • clear(): 清空容器。

6. 哈希政策:

   • load_factor(): 返回当前负载因子。
   • max_load_factor(): 返回或设置最大负载因子。
   • rehash(size_type n): 重新哈希容器，使得桶的数量至少为n。

7. 桶接口:

   • 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非常相似，不过由于它只存储键而不存储值，因此它的接口不包括那些与值相关的操作。

1. 构造和析构:

   • 与unordered_map类似。

2. 迭代器:

   • 与unordered_map类似。

3. 容量:

   • 与unordered_map类似。

4. 元素访问:

   • 不提供operator[]或at()，因为unordered_set只存储键。

5. 修改器:

   • 与unordered_map类似，但不包括插入键值对的操作。

6. 哈希政策:

   • 与unordered_map类似。

7. 桶接口:

   • 与unordered_map类似。

使用这些接口时，通常需要包含头文件<unordered_map>（对于unordered_map）或<unordered_set>（对于unordered_set）。这些接口提供了灵活的方式来管理哈希表中的元素，允许高效的查找、插入和删除操作。

unordered系列与红黑树实现的容器对比

unordered系列容器（如std::unordered_map和std::unordered_set）与基于红黑树实现的容器（如std::map和std::set）在多个方面存在差异。以下是两者之间的对比：

性能特点

1. 查找时间复杂度:

   • unordered系列容器：平均情况下为O(1)，在最坏情况下为O(n)（当所有元素哈希到同一个桶中时）。
   • 红黑树容器：为O(log n)，在最坏情况下也是O(log n)，因为红黑树保持平衡。

2. 插入和删除时间复杂度:

   • unordered系列容器：平均情况下为O(1)，但可能需要O(n)进行重新哈希。
   • 红黑树容器：为O(log n)，因为需要维护树的平衡。

元素顺序

• unordered系列容器：不保证元素的顺序，元素根据哈希值分布在桶中。
• 红黑树容器：元素按键的顺序排序，即总是有序的。

内存使用

• unordered系列容器：通常需要更多的内存来存储哈希表结构。
• 红黑树容器：内存使用通常更为紧凑，因为只需要存储树节点。

自定义比较函数

• unordered系列容器：允许自定义哈希函数和相等比较函数。
• 红黑树容器：允许自定义比较函数来定义元素的排序顺序。

常见操作

• unordered系列容器：

  • 适用于快速查找、插入和删除操作。
  • 不适合需要有序遍历的场景。

• 红黑树容器：

  • 适用于需要元素有序的场景。
  • 提供了范围查询操作，如lower_bound和upper_bound。

实用场景

• unordered系列容器：当元素顺序不重要，且需要快速的查找性能时，例如缓存实现。
• 红黑树容器：当元素需要保持有序，或者需要频繁进行范围查询时，例如数据库索引。

重新哈希

• unordered系列容器：当负载因子超过一定阈值时，容器会自动进行重新哈希，这可能会是一个相对昂贵的操作。
• 红黑树容器：不需要重新哈希，但可能会进行节点重新平衡。

总的来说，选择哪种容器取决于具体的应用场景和性能需求。如果对元素顺序没有要求，并且需要快速的访问速度，unordered系列容器可能是更好的选择。如果需要元素保持有序，或者频繁进行范围查询，那么基于红黑树的容器会更有优势。

原文地址：https://blog.csdn.net/2302_80190394/article/details/142721128

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！