注意

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

概述

简化版 (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_multimap = std::unordered_multimap<Key, Value, Hash, KeyEqual,
                                std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>;
}

std::unordered_multimap 是一个存储键值对的容器。它的工作方式几乎与 std::unordered_map 相同，唯一的区别是键可以重复。如果两个元素的键相同，则比较它们的值以确定是否应将它们添加到多重映射中。

与 std::multimap 不同，存储元素的顺序未指定。

技术细节

无序多重映射的技术定义

无序多重映射是一种无序关联容器，它支持等效键（unordered_multimap 可能包含每个键值的多个副本），并将另一种类型的值与键关联起来。

unordered_multimap 类支持正向迭代器。搜索、插入和删除的平均时间复杂度为常数。

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

此容器的迭代顺序不需要稳定（例如，不能使用 std::equal 比较两个 std::unordered_multimap），除非每个键比较等效的元素组（使用 key_eq() 作为比较器比较相等）在迭代顺序中形成一个连续子范围，也可以通过 equal_range() 访问。

std::unordered_multimap 符合 Container、AllocatorAwareContainer、UnorderedAssociativeContainer 的要求。

std::unordered_multimap

定义于	unordered_multimap

模板参数

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

类型名称

公共	key_type	键
公共	mapped_type	值
公共	value_type	std::pair<const Key, Value>
公共	size_type	无符号整型（通常为 std::size_t ).
公共	difference_type	有符号整型（通常为 std::ptrdiff_t ).
公共	哈希器	哈希
公共	key_equal	键相等
公共	allocator_type	分配器
公共	引用	value_type&
公共	const_reference	const value_type&
公共	指针	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 起)
公共	迭代器	LegacyBidirectionalIterator 到 value_type
公共	const_iterator	指向 const value_type 的LegacyBidirectionalIterator
公共	local_iterator	像 iterator，但仅用于遍历单个桶。
公共	const_local_iterator	像 const_iterator，但仅用于遍历单个桶。
公共	node_type (C++17 起)	节点句柄的一个特化，表示一个容器节点。

成员函数

公共	（构造函数）	构造一个新的无序多重映射。
公共	（析构函数）	析构一个无序多重映射。
公共	operator=	将一个无序多重映射赋值给另一个。
公共	get_allocator	返回关联的分配器。

迭代器

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

容量

公共	empty	如果无序多重映射为空，则返回 true，否则返回 false。
公共	size	返回无序多重映射中的元素数量。
公共	max_size	返回最大可能的元素数量。

修饰符

公共	clear	清除无序多重映射的内容。
公共	insert	插入元素或节点（使用 .extract() 提取的）(C++17 起)。
公共	emplace	就地构造新元素。
公共	emplace_hint	使用提示（迭代器）就地构造元素。
公共	erase	擦除元素。
公共	swap	交换两个无序多重映射。
公共	extract (C++17 起)	从无序多重映射中提取节点（以后可以在其他地方插入）。
公共	merge (C++17 起)	将两个无序多重映射合并在一起。

查找

公共	count	返回与特定键匹配的元素数量。
公共	find	搜索元素并返回指向它的迭代器，如果未找到则返回 end 迭代器。
公共	contains (C++20 起)	如果元素在无序多重映射中，则返回 true，否则返回 false。
公共	equal_range	返回与特定键匹配的元素范围。

桶接口

公共	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 中移除)	比较无序多重映射中的值。
公共	std::swap (std::unordered_multimap)	std::swap 算法的重载。
公共	std::erase_if (std::unordered_multimap) (自 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{}) 必须是格式良好的。

更多示例

基本操作

创建、插入和打印

#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;
}

结果

player3 has got Shield
player2 has got Health potion
player2 has got Sword