注意

请注意，本文尚未完成！您可以通过编辑此文档页面来提供帮助。

概述

简化版 (C++11起)

template< class Key, class Value, /* ... */ >
class unordered_map;

详细

常规版 (C++11起)

template<
    class Key,
    class Value,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, Value>>
>
class unordered_map;

多态版 (C++17 起)

namespace pmr {
    template<
        class Key,
        class Value,
        class Hash = std::hash<Key>,
        class KeyEqual = std::equal_to<Key>,
    >
    using unordered_map = std::unordered_map<Key, Value, Hash, KeyEqual,
                            std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>;
}

std::map 是一个存储具有唯一键的键值对的容器。与 std::map 不同，存储元素的顺序未指定。

技术细节

无序映射的严格定义

无序映射是一个关联容器，包含具有唯一键的键值对。元素的搜索、插入和删除操作的平均时间复杂度为常数。

在内部，元素不按任何特定顺序排序，而是组织到桶中。元素被放入哪个桶完全取决于其键的哈希值。具有相同哈希码的键出现在同一个桶中。这允许快速访问单个元素，因为一旦计算出哈希值，它就指向元素所在的精确桶。

std::unordered_map 满足 Container、AllocatorAwareContainer、UnorderedAssociativeContainer 的要求。

std::unordered_map

定义于	unordered_map

模板参数

公共	键	存储的键的类型。
公共	值	存储的值的类型。
公共	哈希	一个对 Key 类型对象执行哈希处理的函数对象。
公共	KeyEqual	一个接受两个 Key 类型参数并确定键是否相等的函数对象。必须返回 bool。
公共	Allocator	负责分配和释放内存的分配器类型。必须满足 Allocator。

类型名称

公共	key_type	键
公共	mapped_type	值
公共	value_type	std::pair<const Key, Value>
公共	size_type	无符号整型（通常为 std::size_t ).
公共	difference_type	有符号整型（通常为 std::ptrdiff_t ).
公共	hasher	哈希
公共	key_equal	KeyEqual
公共	allocator_type	Allocator
公共	reference	value_type&
公共	const_reference	const value_type&
公共	pointer	Allocator::pointer(C++11 以前) std::allocator_traits<Allocator>::pointer(C++11 起)
公共	const_pointer	Allocator::const_pointer(C++11 以前) std::allocator_traits<Allocator>::const_pointer(C++11 起)
公共	iterator	LegacyBidirectionalIterator 到 value_type
公共	const_iterator	到 const value_type 的 LegacyBidirectionalIterator
公共	local_iterator	像 iterator，但仅用于遍历单个桶。
公共	const_local_iterator	像 const_iterator，但仅用于遍历单个桶。
公共	node_type (C++17 起)	节点句柄的一个特化，表示一个容器节点。
公共	insert_return_type (C++17起)	描述插入 node_type 结果的类型，它是 template < class Iter, class NodeType > struct /* unspecified */ { Iter position; bool inserted; NodeType node; }; 使用模板参数 iterator 和 node_type 实例化的特化。

成员函数

公共	(构造函数)	构造一个新的 unordered_map。
公共	（析构函数）	析构一个 unordered_map。
公共	operator=	将一个 unordered_map 赋值给另一个。
公共	get_allocator	返回关联的分配器。

迭代器

公共	begin cbegin	返回指向开头的迭代器。
公共	end cend	返回指向末尾的迭代器。

容量

公共	empty	如果 unordered_map 为空，则返回 true，否则返回 false。
公共	size	返回 unordered_map 中元素的数量。
公共	max_size	返回最大可能的元素数量。

修饰符

公共	clear	清除 unordered_map 的内容。
公共	insert	插入元素或节点（使用 .extract() 提取的）(C++17 起)。
公共	insert_or_assign (C++17起)	插入新元素，如果已存在则赋值给现有元素。
公共	emplace	就地构造新元素。
公共	emplace_hint	使用提示（迭代器）就地构造元素。
公共	try_emplace (C++17起)	如果键不存在，则就地插入新元素；如果键存在，则不执行任何操作。
公共	erase	擦除元素。
公共	swap	交换两个 unordered_map。
公共	extract (C++17 起)	从 unordered_map 中提取节点（稍后可以插入到其他位置）。
公共	merge (C++17 起)	合并两个 unordered_map。

查找

公共	at	访问指定元素并进行边界检查。
公共	operator[]	访问或插入指定元素。
公共	count	返回匹配特定键的元素数量（对于 unordered_map 始终为 0/1）。
公共	find	搜索元素并返回指向它的迭代器，如果未找到则返回 end 迭代器。
公共	contains (C++20 起)	如果元素在 unordered_map 中，则返回 true，否则返回 false。
公共	equal_range	返回匹配特定键的元素范围。（对于 unordered_map，范围将始终包含一个元素）。

桶接口

公共	begin cbegin	返回指向指定桶开头的迭代器。
公共	end cend	返回指向指定桶末尾的迭代器。
公共	bucket_count	返回桶的数量。
公共	max_bucket_count	返回最大桶数量。
公共	bucket_size	返回特定桶中元素的数量。
公共	bucket	返回特定键的桶。

哈希策略

公共	load_factor	返回每个桶的平均元素数量。
公共	max_load_factor	管理每个桶的最大平均元素数量。
公共	rehash	至少保留指定数量的桶并重新生成哈希表。
公共	reserve	为至少指定数量的元素保留空间并重新生成哈希表。

观察器

公共	hash_function	返回哈希键的内部函数对象。
公共	key_eq	返回一个比较键的内部函数对象。

非成员函数

公共	operator== operator!= (C++20 中移除)	比较 unordered_map 中的值。
公共	std::swap (std::unordered_map)	std::swap 算法的重载。
公共	std::erase_if (std::unordered_map) (C++20起)	std::erase_if 算法的重载。

推导指南 (C++17 起)

点击展开

推导指南

// (1)
template< class InputIt, class Alloc >
unordered_map( InputIt, InputIt, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>,
            std::hash<iter_key_t<InputIt>>,
            std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (2)
template< class InputIt, class Hash, class Alloc >
unordered_map( InputIt, InputIt, typename /*see below*/::size_type, Hash, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash,
              std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (3)
template< class InputIt, class Alloc >
unordered_map( InputIt, InputIt, typename /*see below*/::size_type, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>,
           std::hash<iter_key_t<InputIt>>,
           std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (4)
template< class InputIt,
          class Hash = std::hash<iter_key_t<InputIt>>,
          class Pred = std::equal_to<iter_key_t<InputIt>>,
          class Alloc = std::allocator<iter_to_alloc_t<InputIt>> >
unordered_map( InputIt, InputIt,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash, Pred, Alloc>;

(1 - 4) 允许从迭代器范围推导

// (5)
template< class Key, class T, typename Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>, Alloc )
  -> unordered_map<Key, T, std::hash<Key>, std::equal_to<Key>, Alloc>;

// (6)
template< class Key, class T, class Hash, class Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>,
       typename /*see below*/::size_type, Hash, Alloc )
  -> unordered_map<Key, T, Hash, std::equal_to<Key>, Alloc>;

// (7)
template< class Key, class T, typename Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>,
     typename /*see below*/::size_type, Alloc )
  -> unordered_map<Key, T, std::hash<Key>, std::equal_to<Key>, Alloc>;

// (8)
template< class Key, class T, class Hash = std::hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T>> >
unordered_map( std::initializer_list<std::pair<Key, T>>,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
-> unordered_map<Key, T, Hash, Pred, Alloc>;

(5 - 8) 允许从 std::initializer_list 推导

别名 iter_key_t、iter_val_t 和 iter_to_alloc_t 定义如下

template< class InputIt >
using iter_key_t = std::remove_const_t<
                     typename std::iterator_traits<InputIt>::value_type::first_type>;

template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type::second_type;

template< class InputIt >
using iter_to_alloc_t = std::pair<
  std::add_const_t<typename std::iterator_traits<InputIt>::value_type::first_type>,
  typename std::iterator_traits<InputIt>::value_type::second_type
>

注意

请注意，这些别名不保证在标准库的任何地方都能找到。它们仅为这些推导指南的展示目的而定义，并且在本文档撰写时尚未出现在标准库中。

重载决议

为了使任何推导指南参与重载解析，必须满足以下要求：如果以下任何一项为真，则无序关联容器的推导指南不得参与重载解析

• InputIt 满足 LegacyInputIterator
• Alloc 满足 Allocator
• Hash 不推导为整数类型或不满足 Allocator
• Pred 不满足 Allocator

注意

库确定类型不满足 LegacyInputIterator 的程度是未指定的，但至少

• 整型不符合输入迭代器的条件。

同样，它确定类型不满足 Allocator 的程度是未指定的，但至少

• 成员类型 Alloc::value_type 必须存在。
• 当作为未求值操作数处理时，表达式 std::declval<Alloc&>().allocate(std::size_t{}) 必须是格式良好的。

更多示例

基本操作

创建 unordered_map，插入键值对并打印

创建、插入和打印

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
  std::unordered_map<std::string, std::string> player_locations {
    {"player2", "Capital City"},
    {"player3", "The Harbor"}
  };

  player_locations["player1"] = "Mine";

  for (const auto& [key, value] : player_locations)
    std::cout << key << " is in " << value << '\n';

  return 0;
}

结果

player2 is in Capital City
player3 is in The Harbor
player1 is in Mine