Algorithm-Pattern
  • Introduction
  • C & C++
    • C语言
      • C/C++编译器
      • 宏的使用
      • 编译过程
      • 指针 & 数组
      • 柔性数组
      • 函数指针 & 回调函数
      • C标准库之stdio
      • C标准库之string
      • C标准库之errno
      • C标准库之stdarg
      • C标准库之regex
    • C++基础语法
      • 自增(++) & 自减(--)
      • c语言到c++
      • 可变模板参数
      • 强制类型转换
      • C/C++类型转换的本质
      • 指针 & 引用
      • const的用法
      • static的用法
      • 重要的关键字(一)
      • 重要的关键字(二)
      • 内存申请和释放
      • 内联函数
      • 函数 & 运算符重载
      • 面向对象之封装
      • 构造函数 & 析构函数
      • 面向对象之继承
      • 面向对象之多态
      • 泛型编程
      • 异常
      • 再谈函数指针
    • C++并发编程
      • C++的锁
      • 并发与多线程
    • C++高级特性
      • 函数对象
      • 移动语义 & 完美转发
      • lambda表达式
      • RTTI技术
      • RAII技术
      • 智能指针
      • 模板的特化
      • C++静态库和动态库
      • 内存溢出和内存泄漏
    • STL基础
      • String
      • array/vector/list
      • deque/priority_queue
      • set/map
      • unordered_set/unordered_map
      • algorithm_1
      • functional
      • allocator
    • C++标准库
      • IO
      • Tuple
      • regex
      • bitset
      • numeric
    • STL深入源码
      • vector内部实现
      • deque内部实现
      • sort函数实现
    • 第三方库
      • JsonCpp
      • ProtoBuf
  • 数据结构
    • 线性表
    • 字符串
    • 栈和队列
    • 二叉树
    • 平衡二叉树
    • 平衡多路搜索树
    • 树结构的延申
    • 图
    • 二进制
    • 散列表
  • 算法基础
    • 排序算法
    • 查找算法
    • 数学问题
    • 并查集
    • 递归算法
    • 附加——主定理
    • Catalan数
  • 算法设计思想
    • 滑动窗口思想
    • BFS/DFS
    • 二分法
    • 回溯法
    • 贪心算法
    • 分治法
    • 动态规划
    • 分支限界算法
    • 有限状态机(FSM)
  • LeetCode系列
    • 死磕二叉树
    • 股票买卖问题
    • 打家劫舍问题
    • 跳跃游戏问题
    • 括号匹配问题
    • 石子游戏问题
    • 子序列问题
    • 数组 & 矩阵
    • 排列 & 组合
  • 经典算法问题
    • 几何问题
    • 区间问题
    • 背包问题
    • 石子堆问题
    • 表达式求值
  • 面试题
    • 数据结构和算法基础
    • 程序设计题
      • 实现双线程交替打印
      • C++实现读写锁
      • 实现阻塞队列
      • 实现环形队列
      • 实现线程池
      • 实现智能指针
      • 实现string类
      • 实现高性能local cache
      • 实现内存池
      • 生产者-消费者模型
      • 设计定时器
    • 经典的算法题
    • C++面试题总结
    • 面试算法题总结
由 GitBook 提供支持
在本页
  • unordered_map
  • 1、创建和初始化
  • 2、成员方法
  • unordered_set
  • 自定义类型做key

这有帮助吗?

  1. C & C++
  2. STL基础

unordered_set/unordered_map

上一页set/map下一页algorithm_1

最后更新于4年前

这有帮助吗?

无序容器是 C++ 11 标准才正式引入到 STL 标准库中的,这意味着如果要使用该类容器,则必须选择支持 C++ 11 标准的编译器。

和关联式容器一样,无序容器也使用键值对(pair 类型)的方式存储数据。但它们有本质上的不同:

  • 关联式容器的底层实现采用的树存储结构,更确切的说是红黑树结构;

  • 无序容器的底层实现采用的是哈希表的存储结构。

C++ STL 底层采用哈希表实现无序容器时,会将所有数据存储到一整块连续的内存空间中,并且当数据存储位置发生冲突时,解决方法选用的是“链地址法”(又称“开链法”)。

和关联式容器相比,无序容器具有以下 2 个特点:

  1. 无序容器内部存储的键值对是无序的,各键值对的存储位置取决于该键值对中的键,

  2. 和关联式容器相比,无序容器擅长通过指定键查找对应的值(平均时间复杂度为 O(1));但对于使用迭代器遍历容器中存储的元素,无序容器的执行效率则不如关联式容器。

实际场景中如果涉及大量遍历容器的操作,建议首选关联式容器;反之,如果更多的操作是通过键获取对应的值,则应首选无序容器。

unordered_map

unordered_map 容器和 map 容器一样,以键值对(pair类型)的形式存储数据,存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构,该结构本身不具有对数据的排序功能,所以此容器内部不会自行对存储的键值对进行排序。

unordered_map 容器模板的定义如下所示:

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

参数

含义

<key,T>

前 2 个参数分别用于确定键值对中键和值的类型,也就是存储键值对的类型。

Hash = hash<Key>

用于指明容器在存储各个键值对时要使用的哈希函数,默认使用 STL 标准库提供的 hash<key> 哈希函数。注意,默认哈希函数只适用于基本数据类型(包括 string 类型),而不适用于自定义的结构体或者类。

Pred = equal_to<Key>

要知道,unordered_map 容器中存储的各个键值对的键是不能相等的,而判断是否相等的规则,就由此参数指定。默认情况下,使用 STL 标准库中提供的 equal_to<key> 规则,该规则仅支持可直接用 == 运算符做比较的数据类型。

成员方法

功能

begin()

返回指向容器中第一个键值对的正向迭代器。

end()

返回指向容器中最后一个键值对之后位置的正向迭代器。

cbegin()

和 begin() 功能相同,只不过在其基础上增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。

cend()

和 end() 功能相同,只不过在其基础上,增加了 const 属性,即该方法返回的迭代器不能用于修改容器内存储的键值对。

empty()

若容器为空,则返回 true;否则 false。

size()

返回当前容器中存有键值对的个数。

max_size()

返回容器所能容纳键值对的最大个数,不同的操作系统,其返回值亦不相同。

operator[key]

该模板类中重载了 [] 运算符,其功能是可以向访问数组中元素那样,只要给定某个键值对的键 key,就可以获取该键对应的值。注意,如果当前容器中没有以 key 为键的键值对,则其会使用该键向当前容器中插入一个新键值对。

at(key)

返回容器中存储的键 key 对应的值,如果 key 不存在,则会抛出 out_of_range 异常。

find(key)

查找以 key 为键的键值对,如果找到,则返回一个指向该键值对的正向迭代器;反之,则返回一个指向容器中最后一个键值对之后位置的迭代器(如果 end() 方法返回的迭代器)。

count(key)

在容器中查找以 key 键的键值对的个数。

equal_range(key)

返回一个 pair 对象,其包含 2 个迭代器,用于表明当前容器中键为 key 的键值对所在的范围。

emplace()

向容器中添加新键值对,效率比 insert() 方法高。

emplace_hint()

向容器中添加新键值对,效率比 insert() 方法高。

insert()

向容器中添加新键值对。

erase()

删除指定键值对。

clear()

清空容器,即删除容器中存储的所有键值对。

swap()

交换 2 个 unordered_map 容器存储的键值对,前提是必须保证这 2 个容器的类型完全相等。

bucket_count()

返回当前容器底层存储键值对时,使用桶(一个线性链表代表一个桶)的数量。

max_bucket_count()

返回当前系统中,unordered_map 容器底层最多可以使用多少桶。

bucket_size(n)

返回第 n 个桶中存储键值对的数量。

bucket(key)

返回以 key 为键的键值对所在桶的编号。

load_factor()

返回 unordered_map 容器中当前的负载因子。负载因子,指的是的当前容器中存储键值对的数量(size())和使用桶数(bucket_count())的比值,即 load_factor() = size() / bucket_count()。

max_load_factor()

返回或者设置当前 unordered_map 容器的负载因子。

rehash(n)

将当前容器底层使用桶的数量设置为 n。

reserve()

将存储桶的数量(也就是 bucket_count() 方法的返回值)设置为至少容纳count个元(不超过最大负载因子)所需的数量,并重新整理容器。

hash_function()

返回当前容器使用的哈希函数对象。

unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。unordered_set 容器的类模板定义如下:

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;

参数同unordered_map。

当无序容器中存储键值对的键为自定义类型时,默认的哈希函数 hash 以及比较函数 equal_to 将不再适用,只能自己设计适用该类型的哈希函数和比较函数,并显式传递给 Hash 参数和 Pred 参数。

1、创建和初始化

2、成员方法

unordered_set

自定义类型做key

✏️
🖋️
🖋️
✏️
✏️