欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

unordered_map类

程序员文章站 2022-05-12 23:32:59
...

unordered_map

头文件<unordered_map>

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

Unordered Map

Unordered Maps是关联容器,其存储由键值和映射值的组合形成的元素,并且允许基于其键快速检索各个元素。

在unordered_map中,键值通常用于唯一标识元素,而映射值是具有与此键关联的内容的对象。键和映射值的类型可能不同。

在内部,unordered_map中的元素不会根据其键值或映射值按任何特定顺序排序,而是根据其哈希值组织到桶中,以允许通过键值直接快速访问各个元素(使用常量)平均时间复杂度)。

unordered_map容器比映射容器更快,可以通过键访问单个元素,尽管它们通过元素子集进行范围迭代的效率通常较低。

unordered_map实现直接访问运算符(operator []),允许使用其键值作为参数直接访问映射值。

容器中的迭代器至少是前向迭代器。

容器属性

  1. 联想
    关联容器中的元素由其键引用,而不是由它们在容器中的绝对位置引用。
  2. 无序
    无序容器使用哈希表来组织其元素,这些哈希表允许通过键快速访问元素。
  3. 地图
    每个元素将键与映射值相关联:键用于标识主要内容为映射值的元素。
  4. 唯一键约束
    容器中没有两个元素可以具有等效键。
  5. Allocator-aware
    容器使用allocator对象来动态处理其存储需求。

模板参数

  1. key
    键值的类型。 unordered_map中的每个元素由其键值唯一标识。
    别名为成员类型unordered_map :: key_type。
  2. T
    映射值的类型。 unordered_map中的每个元素用于存储一些数据作为其映射值。
    别名为成员类型unordered_map :: mapped_type。请注意,这与unordered_map :: value_type不同(见下文)。
  3. hash
    一种一元函数对象类型,它将类型为key类型的对象作为参数,并根据它返回类型为size_t的唯一值。这可以是实现函数调用操作符的类,也可以是指向函数的指针(请参阅构造函数)。这默认为hash ,它返回一个哈希值,其碰撞概率接近1.0 / std :: numeric_limits <size_t> :: max()。
    unordered_map对象使用此函数返回的哈希值在内部组织其元素,从而加快定位单个元素的过程。
    别名为成员类型unordered_map :: hasher。
  4. pred
    一个二元谓词,它接受键类型的两个参数并返回一个bool。表达式pred(a,b),其中pred是这种类型的对象,a和b是键值,如果a被认为等同于b,则返回true。这可以是实现函数调用操作符的类,也可以是指向函数的指针(请参阅构造函数)。默认为equal_to ,返回与应用等于运算符(a == b)相同的值。
    unordered_map对象使用此表达式来确定两个元素键是否相等。 unordered_map容器中没有两个元素可以使用此谓词生成true的键。
    别名为成员类型unordered_map :: key_equal。
  5. alloc
    用于定义存储分配模型的分配器对象的类型。默认情况下,使用allocator类模板,该模板定义最简单的内存分配模型,并且与值无关。
    别名为成员类型unordered_map :: allocator_type。

在unordered_map成员函数的引用中,假定模板参数具有相同的名称(Key,T,Hash,Pred和Alloc)。

迭代器到unordered_map容器的元素访问键和映射值。 为此,该类定义了所谓的value_type,它是一个对类,其第一个值对应于键类型的const版本(模板参数Key),第二个值对应于映射值(模板参数T):

typedef pair<const Key, T> value_type;

unordered_map容器的迭代器指向此value_type的元素。 因此,对于一个名为it的迭代器,它指向一个map的元素,它的键和映射值可以分别用:

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 

当然,可以使用任何其他直接访问运算符,例如 - >或[],例如:

it->first;               // same as (*it).first   (the key value)
it->second;              // same as (*it).second  (the mapped value)

成员类型

以下别名是unordered_map的成员类型。 它们被成员函数广泛用作参数和返回类型:
【C++11】

成员类型 定义 备注
key_type 第一个模板参数(Key)
mapped_type 第二个模板参数(T)
value_type pair<const key_type,mapped_type>
hasher 第三个模板参数(Huah) defaults to: hash<key_type>
key_equal 第四个模板参数(Pred) defaults to: equal_to<key_type>
allocator_type 第五个模板参数(Alloc) defaults to: allocator<value_type>
reference Alloc::reference
const_reference Alloc::const_reference
pointer Alloc::pointer for the default allocator: value_type*
const_pointer Alloc::const_pointer for the default allocator: const value_type*
iterator value_type的前向迭代器
const_iterator const value_type的前向迭代器
local_iterator value_type的前向迭代器
const_local_iterator const value_type的前向迭代器
size_type 无符号整数类型 usually the same as size_t
difference_type a signed integral type usually the same as ptrdiff_t

成员函数

(constructor) 构造unordered_map(公共成员函数)
(destructor) 破坏unordered_map(公共成员函数)
operator= 分配内容(公共成员函数)

容量

empty 测试容器是否为空(公共成员函数)
size 返回容器大小(公共成员函数)
max_size 返回最大大小(公共成员函数)

迭代器

begin 返回迭代器的开头(公共成员函数)
end 返回迭代器的末尾(公共成员函数)
cbegin 返回const_iterator的开头(公共成员函数)
cend 返回const_iterator的末尾(公共成员函数)

元素访问

operator[] 访问元素(公共成员函数)
at 访问元素(公共成员函数)

元素查找

find 获取元素的迭代器(公共成员函数)
count 使用特定键计数元素(公共成员函数)
equal_range 获取具有特定键的元素范围(公共成员函数)

修饰符

emplace 构造和插入元素(公共成员函数)
emplace_hint 使用提示构造和插入元素(公共成员函数)
insert 插入元素(公共成员函数)
erase 插入元素(公共成员函数)
clear 擦除元素(公共成员函数)
swap 交换元素(公共成员函数)

bucket_count 返回桶的数量(公共成员函数)
max_bucket_count 返回桶的最大数量(公共成员函数)
bucket_size 返回桶的大小(公共成员类型)
bucket 找到元素的存储桶(公共成员函数)

哈希策略

load_factor 返回加载因子(公共成员函数)
max_load_factor 获取或设置最大载荷因子(公共成员函数)
rehash 设置桶的数量(公共成员函数)
reserve 请求更改容量(公共成员函数)

观察

hash_function 获取哈希函数(公共成员类型)
key_eq 获取关键等价谓词(公共成员类型)
get_allocator 获取分配器(公共成员函数)

非成员函数重载

operators (unordered_map) unordered_map的关系运算符(函数模板)
swap (unordered_map) 交换两个unordered_map容器的内容(函数模板)