注意

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

概述

简化版 (C++98 起)

template< class Key, /* ... */ >
class unorderd_multiset;

详细

常规版 (C++98 起)

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> 
class unordered_multiset;

多态版 (C++17 起)

namespace pmr {
    template <class Key,
              class Hash = std::hash<Key>,
              class Pred = std::equal_to<Key>>
    using unordered_multiset = std::unordered_multiset<Key, Hash, Pred,
                                   std::pmr::polymorphic_allocator<Key>>
}

std::unordered_multiset 是一个无序关联容器，用于存储唯一对象。

技术细节

unordered_multiset 的技术定义

std::unordered_multiset 是一个关联容器，包含一组类型为 Key 的唯一对象。

搜索、插入和删除的平均时间复杂度是常数。

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

容器元素不能被修改（即使是非 const 迭代器），因为修改可能会改变元素的哈希值并破坏容器。

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

std::unordered_multiset

定义于	unordered_set

模板参数

公共	键	存储的键的类型。
公共	哈希	一个对 Key 类型对象执行哈希处理的函数对象。
公共	比较	满足 Compare 的比较器类型。
公共	分配器	负责分配和释放内存的分配器类型。必须满足 Allocator。

类型名称

公共	key_type	键
公共	value_type	键
公共	size_type	无符号整型（通常是 std::size_t）。
公共	difference_type	有符号整型（通常是 std::ptrdiff_t）。
公共	哈希器	哈希
公共	key_equal	KeyEqual
公共	allocator_type	分配器
公共	引用	value_type&
公共	const_reference	const value_type&
公共	指针	std::allocator_traits<Allocator>::pointer
公共	const_pointer	std::allocator_traits<Allocator>::const_pointer
公共	迭代器 ❗	指向 value_type 的常量 LegacyBidirectionalIterator
公共	const_iterator ❗	指向 const value_type 的 LegacyBidirectionalIterator
公共	local_iterator	像 iterator，但仅用于遍历单个桶。
公共	const_local_iterator	像 const_iterator，但仅用于遍历单个桶。
公共	node_type (C++17 起)	表示容器节点的 节点句柄 特化。

无序多重集的迭代器

iterator 被称为常量，因为它不可能修改其指向的值。这是因为修改迭代器指向的值可能会使无序多重集的内部结构失效，从而导致各种不正确和意外的行为。

成员类型别名 iterator 和 const_iterator 可能相同。这完全取决于实现。这意味着任何仅在迭代器类型上有所不同重载函数/特化可能是不正确的，并可能导致 ODR 违反。

成员函数

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

迭代器

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

容量

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

修饰符

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

查找

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

桶接口

公共	begin (size_type) cbegin (size_type)	返回指向指定桶开头的迭代器。
公共	end (size_type) cend (size_type)	返回指向指定桶末尾的迭代器。
公共	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_multiset)	std::swap 算法的重载。
公共	std::erase_if (std::unordered_multiset) (自 C++20 起)	std::erase_if 算法的重载。

推导指南 (C++17 起)

点击展开

推导指南

// (1)
template< class InputIt, class Alloc >
unordered_multiset( InputIt, InputIt, Alloc )
  -> unordered_multiset<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_multiset( InputIt, InputIt, typename /*see below*/::size_type, Hash, Alloc )
  -> unordered_multiset<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash,
              std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (3)
template< class InputIt, class Alloc >
unordered_multiset( InputIt, InputIt, typename /*see below*/::size_type, Alloc )
  -> unordered_multiset<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_multiset( InputIt, InputIt,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
  -> unordered_multiset<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash, Pred, Alloc>;

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

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

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

// (7)
template< class Key, class T, typename Alloc >
unordered_multiset( std::initializer_list<std::pair<Key, T>>,
     typename /*see below*/::size_type, Alloc )
  -> unordered_multiset<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_multiset( std::initializer_list<std::pair<Key, T>>,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
-> unordered_multiset<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{}) 必须是格式良好的。