[#unordered_map]
== 类模板 unordered_map

:idprefix: unordered_map_

`boost::unordered_map` — 一个无序关联容器，用于将唯一的键与另一个值关联起来。

=== 概要

[listing,subs="+macros,+quotes"]
-----
// #include xref:reference/header_unordered_map.adoc[<boost/unordered/unordered_map.hpp>]

namespace boost {
namespace unordered {

  template<class Key,
           class T,
           class Hash = boost::hash<Key>,
           class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<std::pair<const Key, T>>>
  class unordered_map {
  public:
    // types
    using key_type             = Key;
    using mapped_type          = T;
    using value_type           = std::pair<const Key, T>;
    using hasher               = Hash;
    using key_equal            = Pred;
    using allocator_type       = Allocator;
    using pointer              = typename std::allocator_traits<Allocator>::pointer;
    using const_pointer        = typename std::allocator_traits<Allocator>::const_pointer;
    using reference            = value_type&;
    using const_reference      = const value_type&;
    using size_type            = std::size_t;
    using difference_type      = std::ptrdiff_t;

    using iterator             = _implementation-defined_;
    using const_iterator       = _implementation-defined_;
    using local_iterator       = _implementation-defined_;
    using const_local_iterator = _implementation-defined_;
    using node_type            = _implementation-defined_;
    using insert_return_type   = _implementation-defined_;

    // construct/copy/destroy
    xref:#unordered_map_default_constructor[unordered_map]();
    explicit xref:#unordered_map_bucket_count_constructor[unordered_map](size_type n,
                           const hasher& hf = hasher(),
                           const key_equal& eql = key_equal(),
                           const allocator_type& a = allocator_type());
    template<class InputIterator>
      xref:#unordered_map_iterator_range_constructor[unordered_map](InputIterator f, InputIterator l,
                    size_type n = _implementation-defined_,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type());
    xref:#unordered_map_copy_constructor[unordered_map](const unordered_map& other);
    xref:#unordered_map_move_constructor[unordered_map](unordered_map&& other);
    template<class InputIterator>
      xref:#unordered_map_iterator_range_constructor_with_allocator[unordered_map](InputIterator f, InputIterator l, const allocator_type& a);
    explicit xref:#unordered_map_allocator_constructor[unordered_map](const Allocator& a);
    xref:#unordered_map_copy_constructor_with_allocator[unordered_map](const unordered_map& other, const Allocator& a);
    xref:#unordered_map_move_constructor_with_allocator[unordered_map](unordered_map&& other, const Allocator& a);
    xref:#unordered_map_initializer_list_constructor[unordered_map](std::initializer_list<value_type> il,
                  size_type n = _implementation-defined_
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& a = allocator_type());
    xref:#unordered_map_bucket_count_constructor_with_allocator[unordered_map](size_type n, const allocator_type& a);
    xref:#unordered_map_bucket_count_constructor_with_hasher_and_allocator[unordered_map](size_type n, const hasher& hf, const allocator_type& a);
    template<class InputIterator>
      xref:#unordered_map_iterator_range_constructor_with_bucket_count_and_allocator[unordered_map](InputIterator f, InputIterator l, size_type n, const allocator_type& a);
    template<class InputIterator>
      xref:#unordered_map_iterator_range_constructor_with_bucket_count_and_hasher[unordered_map](InputIterator f, InputIterator l, size_type n, const hasher& hf,
                    const allocator_type& a);
    xref:#unordered_map_initializer_list_constructor_with_allocator[unordered_map](std::initializer_list<value_type> il, const allocator_type& a);
    xref:#unordered_map_initializer_list_constructor_with_bucket_count_and_allocator[unordered_map](std::initializer_list<value_type> il, size_type n, const allocator_type& a);
    xref:#unordered_map_initializer_list_constructor_with_bucket_count_and_hasher_and_allocator[unordered_map](std::initializer_list<value_type> il, size_type n, const hasher& hf,
                  const allocator_type& a);
    xref:#unordered_map_destructor[~unordered_map]();
    unordered_map& xref:#unordered_map_copy_assignment[operator++=++](const unordered_map& other);
    unordered_map& xref:#unordered_map_move_assignment[operator++=++](unordered_map&& other)
      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
               boost::is_nothrow_move_assignable_v<Hash> &&
               boost::is_nothrow_move_assignable_v<Pred>);
    unordered_map& xref:#unordered_map_initializer_list_assignment[operator++=++](std::initializer_list<value_type>);
    allocator_type xref:#unordered_map_get_allocator[get_allocator]() const noexcept;

    // iterators
    iterator       xref:#unordered_map_begin[begin]() noexcept;
    const_iterator xref:#unordered_map_begin[begin]() const noexcept;
    iterator       xref:#unordered_map_end[end]() noexcept;
    const_iterator xref:#unordered_map_end[end]() const noexcept;
    const_iterator xref:#unordered_map_cbegin[cbegin]() const noexcept;
    const_iterator xref:#unordered_map_cend[cend]() const noexcept;

    // capacity
    ++[[nodiscard]]++ bool xref:#unordered_map_empty[empty]() const noexcept;
    size_type xref:#unordered_map_size[size]() const noexcept;
    size_type xref:#unordered_map_max_size[max_size]() const noexcept;

    // modifiers
    template<class... Args> std::pair<iterator, bool> xref:#unordered_map_emplace[emplace](Args&&... args);
    template<class... Args> iterator xref:#unordered_map_emplace_hint[emplace_hint](const_iterator position, Args&&... args);
    std::pair<iterator, bool> xref:#unordered_map_copy_insert[insert](const value_type& obj);
    std::pair<iterator, bool> xref:#unordered_map_move_insert[insert](value_type&& obj);
    template<class P> std::pair<iterator, bool> xref:#unordered_map_emplace_insert[insert](P&& obj);
    iterator       xref:#unordered_map_copy_insert_with_hint[insert](const_iterator hint, const value_type& obj);
    iterator       xref:#unordered_map_move_insert_with_hint[insert](const_iterator hint, value_type&& obj);
    template<class P> iterator xref:#unordered_map_emplace_insert_with_hint[insert](const_iterator hint, P&& obj);
    template<class InputIterator> void xref:#unordered_map_insert_iterator_range[insert](InputIterator first, InputIterator last);
    void xref:#unordered_map_insert_initializer_list[insert](std::initializer_list<value_type>);

    template<class... Args>
      std::pair<iterator, bool> xref:#unordered_map_try_emplace[try_emplace](const key_type& k, Args&&... args);
    template<class... Args>
      std::pair<iterator, bool> xref:#unordered_map_try_emplace[try_emplace](key_type&& k, Args&&... args);
    template<class K, class... Args>
      std::pair<iterator, bool> xref:#unordered_map_try_emplace[try_emplace](K&& k, Args&&... args);
    template<class... Args>
      iterator xref:#unordered_map_try_emplace_with_hint[try_emplace](const_iterator hint, const key_type& k, Args&&... args);
    template<class... Args>
      iterator xref:#unordered_map_try_emplace_with_hint[try_emplace](const_iterator hint, key_type&& k, Args&&... args);
    template<class K, class... Args>
      iterator xref:#unordered_map_try_emplace_with_hint[try_emplace](const_iterator hint, K&& k, Args&&... args);
    template<class M>
      std::pair<iterator, bool> xref:#unordered_map_insert_or_assign[insert_or_assign](const key_type& k, M&& obj);
    template<class M>
      std::pair<iterator, bool> xref:#unordered_map_insert_or_assign[insert_or_assign](key_type&& k, M&& obj);
    template<class K, class M>
      std::pair<iterator, bool> xref:#unordered_map_insert_or_assign[insert_or_assign](K&& k, M&& obj);
    template<class M>
      iterator xref:#unordered_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, const key_type& k, M&& obj);
    template<class M>
      iterator xref:#unordered_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, key_type&& k, M&& obj);
    template<class K, class M>
      iterator xref:#unordered_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, K&& k, M&& obj);

    node_type xref:#unordered_map_extract_by_iterator[extract](const_iterator position);
    node_type xref:#unordered_map_extract_by_key[extract](const key_type& k);
    template<class K> node_type xref:#unordered_map_extract_by_key[extract](K&& k);
    insert_return_type xref:#unordered_map_insert_with_node_handle[insert](node_type&& nh);
    iterator           xref:#unordered_map_insert_with_hint_and_node_handle[insert](const_iterator hint, node_type&& nh);

    iterator  xref:#unordered_map_erase_by_position[erase](iterator position);
    iterator  xref:#unordered_map_erase_by_position[erase](const_iterator position);
    size_type xref:#unordered_map_erase_by_key[erase](const key_type& k);
    template<class K> size_type xref:#unordered_map_erase_by_key[erase](K&& k);
    iterator  xref:#unordered_map_erase_range[erase](const_iterator first, const_iterator last);
    void      xref:#unordered_map_quick_erase[quick_erase](const_iterator position);
    void      xref:#unordered_map_erase_return_void[erase_return_void](const_iterator position);
    void      xref:#unordered_map_swap[swap](unordered_map& other)
      noexcept(boost::allocator_traits<Allocator>::is_always_equal::value &&
               boost::is_nothrow_swappable_v<Hash> &&
               boost::is_nothrow_swappable_v<Pred>);
    void      xref:#unordered_map_clear[clear]() noexcept;

    template<class H2, class P2>
      void xref:#unordered_map_merge[merge](unordered_map<Key, T, H2, P2, Allocator>& source);
    template<class H2, class P2>
      void xref:#unordered_map_merge[merge](unordered_map<Key, T, H2, P2, Allocator>&& source);
    template<class H2, class P2>
      void xref:#unordered_map_merge[merge](unordered_multimap<Key, T, H2, P2, Allocator>& source);
    template<class H2, class P2>
      void xref:#unordered_map_merge[merge](unordered_multimap<Key, T, H2, P2, Allocator>&& source);

    // observers
    hasher xref:#unordered_map_hash_function[hash_function]() const;
    key_equal xref:#unordered_map_key_eq[key_eq]() const;

    // map operations
    iterator         xref:#unordered_map_find[find](const key_type& k);
    const_iterator   xref:#unordered_map_find[find](const key_type& k) const;
    template<class K>
      iterator       xref:#unordered_map_find[find](const K& k);
    template<class K>
      const_iterator xref:#unordered_map_find[find](const K& k) const;
    template<typename CompatibleKey, typename CompatibleHash, typename CompatiblePredicate>
      iterator       xref:#unordered_map_find[find](CompatibleKey const& k, CompatibleHash const& hash,
                          CompatiblePredicate const& eq);
    template<typename CompatibleKey, typename CompatibleHash, typename CompatiblePredicate>
      const_iterator xref:#unordered_map_find[find](CompatibleKey const& k, CompatibleHash const& hash,
                          CompatiblePredicate const& eq) const;      
    size_type        xref:#unordered_map_count[count](const key_type& k) const;
    template<class K>
      size_type      xref:#unordered_map_count[count](const K& k) const;
    bool             xref:#unordered_map_contains[contains](const key_type& k) const;
    template<class K>
      bool           xref:#unordered_map_contains[contains](const K& k) const;
    std::pair<iterator, iterator>               xref:#unordered_map_equal_range[equal_range](const key_type& k);
    std::pair<const_iterator, const_iterator>   xref:#unordered_map_equal_range[equal_range](const key_type& k) const;
    template<class K>
      std::pair<iterator, iterator>             xref:#unordered_map_equal_range[equal_range](const K& k);
    template<class K>
      std::pair<const_iterator, const_iterator> xref:#unordered_map_equal_range[equal_range](const K& k) const;

    // element access
    mapped_type& xref:#unordered_map_operator[operator[+]+](const key_type& k);
    mapped_type& xref:#unordered_map_operator[operator[+]+](key_type&& k);
    template<class K> mapped_type& xref:#unordered_map_operator[operator[+]+](K&& k);
    mapped_type& xref:#unordered_map_at[at](const key_type& k);
    const mapped_type& xref:#unordered_map_at[at](const key_type& k) const;
    template<class K> mapped_type& xref:#unordered_map_at[at](const K& k);
    template<class K> const mapped_type& xref:#unordered_map_at[at](const K& k) const;

    // bucket interface
    size_type xref:#unordered_map_bucket_count[bucket_count]() const noexcept;
    size_type xref:#unordered_map_max_bucket_count[max_bucket_count]() const noexcept;
    size_type xref:#unordered_map_bucket_size[bucket_size](size_type n) const;
    size_type xref:#unordered_map_bucket[bucket](const key_type& k) const;
    template<class K> size_type xref:#unordered_map_bucket[bucket](const K& k) const;
    local_iterator xref:#unordered_map_begin_2[begin](size_type n);
    const_local_iterator xref:#unordered_map_begin_2[begin](size_type n) const;
    local_iterator xref:#unordered_map_end_2[end](size_type n);
    const_local_iterator xref:#unordered_map_end_2[end](size_type n) const;
    const_local_iterator xref:#unordered_map_cbegin_2[cbegin](size_type n) const;
    const_local_iterator xref:#unordered_map_cend_2[cend](size_type n) const;

    // hash policy
    float xref:#unordered_map_load_factor[load_factor]() const noexcept;
    float xref:#unordered_map_max_load_factor[max_load_factor]() const noexcept;
    void xref:#unordered_map_set_max_load_factor[max_load_factor](float z);
    void xref:#unordered_map_rehash[rehash](size_type n);
    void xref:#unordered_map_reserve[reserve](size_type n);
  };

  // Deduction Guides
  template<class InputIterator,
           class Hash = boost::hash<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>,
           class Pred = std::equal_to<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>,
           class Allocator = std::allocator<xref:#unordered_map_iter_to_alloc_type[__iter-to-alloc-type__]<InputIterator>>>
    unordered_map(InputIterator, InputIterator, typename xref:#unordered_map_deduction_guides[__see below__]::size_type = xref:#unordered_map_deduction_guides[__see below__],
                  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
      -> unordered_map<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#unordered_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>, Hash, Pred,
                       Allocator>;

  template<class Key, class T, class Hash = boost::hash<Key>,
           class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<std::pair<const Key, T>>>
    unordered_map(std::initializer_list<std::pair<Key, T>>,
                  typename xref:#unordered_map_deduction_guides[__see below__]::size_type = xref:#unordered_map_deduction_guides[__see below__], Hash = Hash(),
                  Pred = Pred(), Allocator = Allocator())
      -> unordered_map<Key, T, Hash, Pred, Allocator>;

  template<class InputIterator, class Allocator>
    unordered_map(InputIterator, InputIterator, typename xref:#unordered_map_deduction_guides[__see below__]::size_type, Allocator)
      -> unordered_map<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#unordered_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>,
                       boost::hash<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>,
                       std::equal_to<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class InputIterator, class Allocator>
    unordered_map(InputIterator, InputIterator, Allocator)
      -> unordered_map<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#unordered_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>,
                       boost::hash<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>,
                       std::equal_to<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class InputIterator, class Hash, class Allocator>
    unordered_map(InputIterator, InputIterator, typename xref:#unordered_map_deduction_guides[__see below__]::size_type, Hash, Allocator)
      -> unordered_map<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>, xref:#unordered_map_iter_mapped_type[__iter-mapped-type__]<InputIterator>, Hash,
                       std::equal_to<xref:#unordered_map_iter_key_type[__iter-key-type__]<InputIterator>>, Allocator>;

  template<class Key, class T, class Allocator>
    unordered_map(std::initializer_list<std::pair<Key, T>>, typename xref:#unordered_map_deduction_guides[__see below__]::size_type,
                  Allocator)
      -> unordered_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>;

  template<class Key, class T, class Allocator>
    unordered_map(std::initializer_list<std::pair<Key, T>>, Allocator)
      -> unordered_map<Key, T, boost::hash<Key>, std::equal_to<Key>, Allocator>;

  template<class Key, class T, class Hash, class Allocator>
    unordered_map(std::initializer_list<std::pair<Key, T>>, typename xref:#unordered_map_deduction_guides[__see below__]::size_type, Hash,
                  Allocator)
      -> unordered_map<Key, T, Hash, std::equal_to<Key>, Allocator>;

} // namespace unordered
} // namespace boost
-----

---

=== 描述

*模板参数*

[cols="1,1"]
|===

|_Key_
|`Key` must be https://en.cppreference.com/w/cpp/named_req/Erasable[Erasable^] from the container (i.e. `allocator_traits` can destroy it).

|_T_
|`T` must be https://en.cppreference.com/w/cpp/named_req/Erasable[Erasable^] from the container (i.e. `allocator_traits` can destroy it).

|_Hash_
|A unary function object type that acts a hash function for a `Key`. It takes a single argument of type `Key` and returns a value of type `std::size_t`.

|_Pred_
|A binary function object that implements an equivalence relation on values of type `Key`. A binary function object that induces an equivalence relation on values of type `Key`. It takes two arguments of type `Key` and returns a value of type bool.

|_Allocator_
|An allocator whose value type is the same as the container's value type.
支持使https://en.cppreference.com/w/cpp/named_req/Allocator#Fancy_pointers[异形指针] 的分配器。

|===

元素被组织到桶中。具有相同哈希码的键存储在同一桶中。

桶的数量可以通过调用 insert 自动增加，或者作为调用 rehash 的结果。

=== 配置宏

==== `BOOST_UNORDERED_ENABLE_SERIALIZATION_COMPATIBILITY_V0`

全局定义此宏以支持加载由 Boost 1.84 之前版本的 Boost 保存到 Boost.Serialization 归档中的 `unordered_map`。

=== 类型定义

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ iterator;
----

一个迭代器，其值类型为 `value_type`。

迭代器类别至少为前向迭代器。

可转换为 `const_iterator` 。

---

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ const_iterator;
----

一个常量迭代器，其值类型为 `value_type` 。

迭代器类别至少为前向迭代器。

---

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ local_iterator;
----

一种迭代器，其值类型、差值类型以及指针和引用类型均与 iterator 相同。

`local_iterator` 对象可用于遍历单个桶内的元素。

---

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ const_local_iterator;
----

一种常量迭代器，其值类型、差值类型以及指针和引用类型均与 const_iterator 相同。

`const_local_iterator` 对象可用于遍历单个桶。

---

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ node_type;
----

一个用于存放被提取容器元素的类，符合 https://en.cppreference.com/w/cpp/container/node_handle[NodeHandle] 模型。

---

[source,c++,subs=+quotes]
----
typedef _implementation-defined_ insert_return_type;
----

一个内部类模板的特化：

[source,c++,subs=+quotes]
----
template<class Iterator, class NodeType>
struct _insert_return_type_ // name is exposition only
{
  Iterator position;
  bool     inserted;
  NodeType node;
};
----

其中 `Iterator` = `iterator`，`NodeType` = `node_type`。

---

=== 构造函数

==== 默认构造函数
```c++ unordered_map(); ```

使用 `hasher()` 作为哈希函数，`key_equal()` 作为键相等谓词，`allocator_type()` 作为分配器，以及最大负载因子 `1.0` 构造一个空容器。

[horizontal]
后置条件：`size() == 0`  
要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 桶数构造函数
```c++ explicit unordered_map(size_type n, const hasher&amp; hf = hasher(), const key_equal&amp; eql = key_equal(), const allocator_type&amp; a = allocator_type()); ```

构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`eql` 作为键相等谓词，`a` 作为分配器，以及最大负载因子 `1.0`。

[horizontal]
后置条件：`size() == 0`  
要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 迭代器范围构造函数
[source,c++,subs="+quotes"]
----
template<class InputIterator>
  unordered_map(InputIterator f, InputIterator l,
                size_type n = _implementation-defined_,
                const hasher& hf = hasher(),
                const key_equal& eql = key_equal(),
                const allocator_type& a = allocator_type());
----

构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`eql` 作为键相等谓词，`a` 作为分配器，以及最大负载因子 `1.0`，并将 `[f, l)` 范围内的元素插入其中。

[horizontal]
要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 复制构造函数
```c++ unordered_map(unordered_map const&amp; other); ```

拷贝构造函数。拷贝所包含的元素、哈希函数、谓词、最大负载因子和分配器。

如果 `Allocator::select_on_container_copy_construction` 存在且具有正确的签名，则分配器将根据其结果进行构造。

[horizontal]
要求：`value_type` 可拷贝构造。

---

==== 移动构造函数
```c++ unordered_map(unordered_map&amp;&amp; other); ```

移动构造函数。

[horizontal]
注意：此函数使用 Boost.Move 实现。  
要求：`value_type` 可移动构造。

---

==== 带分配器的迭代器区间构造函数
```c++ template<class inputiterator=""> unordered_map(InputIterator f, InputIterator l, const allocator_type&amp; a); ```</class>

使用 `a` 作为分配器，以默认哈希函数、默认键相等谓词和最大负载因子 `1.0` 构造一个空容器，并将 `[f, l)` 范围内的元素插入其中。

[horizontal]
要求：`hasher`、`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 分配器构造函数
```c++ explicit unordered_map(Allocator const&amp; a); ```

使用分配器 `a` 构造一个空容器。

---

==== 带分配器的复制构造函数
```c++ unordered_map(unordered_map const&amp; other, Allocator const&amp; a); ```

构造一个容器，拷贝 `other` 所包含的元素、哈希函数、谓词和最大负载因子，但使用分配器 `a`。

---

==== 带分配器的移动构造函数
```c++ unordered_map(unordered_map&amp;&amp; other, Allocator const&amp; a); ```

构造一个容器，移动 other 所包含的元素，并使用其哈希函数、谓词和最大负载因子，但使用分配器 a。

[horizontal]
注意：此函数使用 Boost.Move 实现。  要求：`value_type` 可移动插入。

---

==== 初始化列表构造函数
[source,c++,subs="+quotes"]
----
unordered_map(std::initializer_list<value_type> il,
              size_type n = _implementation-defined_
              const hasher& hf = hasher(),
              const key_equal& eql = key_equal(),
              const allocator_type& a = allocator_type());
----

构造一个至少包含 n 个桶的空容器，使用 hf 作为哈希函数，eql 作为键相等谓词，a 作为分配器，以及最大负载因子 1.0，并将 il 中的元素插入其中。

[horizontal]
要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带分配器的桶数构造函数
```c++ unordered_map(size_type n, allocator_type const&amp; a); ```

构造一个至少包含 n 个桶的空容器，使用 hf 作为哈希函数，使用默认的哈希函数和键相等谓词，a 作为分配器，以及最大负载因子 1.0。

[horizontal]
后置条件：`size() == 0`  
要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带哈希函数和分配器的桶数构造函数
```c++ unordered_map(size_type n, hasher const&amp; hf, allocator_type const&amp; a); ```

构造一个至少包含 n 个桶的空容器，使用 hf 作为哈希函数，使用默认的键相等谓词，a 作为分配器，以及最大负载因子 1.0。

[horizontal]
后置条件：`size() == 0`  要求：`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带桶数和分配器的迭代器范围构造函数
[source,c++,subs="+quotes"]
----
template<class InputIterator>
  unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a);
----

构造一个至少包含 `n` 个桶的空容器，使用 `a` 作为分配器，使用默认的哈希函数、默认的键相等谓词以及最大负载因子 `1.0`，并将 `[f, l)` 范围内的元素插入其中。

[horizontal]
要求：`hasher`、`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带桶数和哈希函数的迭代器范围构造函数
[source,c++,subs="+quotes"]
----
    template<class InputIterator>
      unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
                    const allocator_type& a);
----

构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`a` 作为分配器，使用默认的键相等谓词，以及最大负载因子 `1.0`，并将 `[f, l)` 范围内的元素插入其中。

[horizontal]
要求：`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带分配器的初始化列表构造函数

```c++ unordered_map(std::initializer_list<value_type> il, const allocator_type&amp; a); ```</value_type>

使用 a 作为分配器，最大负载因子为 1.0，构造一个空容器，并将 il 中的元素插入其中。

[horizontal]
要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带桶数和分配器的初始化列表构造函数

```c++ unordered_map(std::initializer_list<value_type> il, size_type n, const allocator_type&amp; a); ```</value_type>

构造一个至少包含 `n` 个桶的空容器，使用 `a` 作为分配器，最大负载因子为 `1.0`，并将 `il` 中的元素插入其中。

[horizontal]
要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

==== 带桶数、哈希函数和分配器的初始化列表构造函数

```c++ unordered_map(std::initializer_list<value_type> il, size_type n, const hasher&amp; hf, const allocator_type&amp; a); ```</value_type>

构造一个至少包含 n 个桶的空容器，使用 hf 作为哈希函数，a 作为分配器，最大负载因子为 1.0，并将 il 中的元素插入其中。

[horizontal]
要求：`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。

---

=== 析构函数

```c++ ~unordered_map(); ```

[horizontal]
注意：析构函数会应用于每个元素，并且所有内存都会被释放。

---

=== 赋值操作

==== 复制赋值

```c++ unordered_map&amp; operator=(unordered_map const&amp; other); ```

赋值运算符。拷贝所包含的元素、哈希函数、谓词和最大负载因子，但不拷贝分配器。

如果 `Alloc::propagate_on_container_copy_assignment` 存在且 `Alloc::propagate_on_container_copy_assignment::value` 为 `true`，则分配器会被覆盖；否则，拷贝的元素将使用现有的分配器创建。

[horizontal]
要求：`value_type` 可拷贝构造。

---

==== 移动赋值
```c++ unordered_map&amp; operator=(unordered_map&amp;&amp; other) noexcept(boost::allocator_traits<allocator>::is_always_equal::value &amp;&amp; boost::is_nothrow_move_assignable_v<hash> &amp;&amp; boost::is_nothrow_move_assignable_v<pred>); ``` The move assignment operator.</pred></hash></allocator>

如果 `Alloc::propagate_on_container_move_assignment` 存在且 `Alloc::propagate_on_container_move_assignment::value` 为 `true`，则分配器会被覆盖；否则，移动的元素将使用现有的分配器创建。

[horizontal]
要求：`value_type` 可移动构造。

---

==== 初始化列表赋值
```c++ unordered_map&amp; operator=(std::initializer_list<value_type> il); ```</value_type>

从初始化列表中的值进行赋值。所有现有元素要么被新元素覆盖，要么被销毁。

[horizontal]
要求：`value_type` 必须能够从容器中 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^] 并且满足 https://en.cppreference.com/w/cpp/named_req/CopyAssignable[可拷贝赋值^]。

=== 迭代器

==== begin
```c++ iterator begin() noexcept; const_iterator begin() const noexcept; ```

[horizontal]
返回：指向容器第一个元素的迭代器，如果容器为空则返回容器的尾后迭代器。

---

==== end
```c++ iterator end() noexcept; const_iterator end() const noexcept; ```

[horizontal]
返回：指向容器尾后值的迭代器。

---

==== cbegin
```c++ const_iterator cbegin() const noexcept; ```

[horizontal]
返回：指向容器第一个元素的 `const_iterator`，如果容器为空则返回容器的尾后值。

---

==== cend
```c++ const_iterator cend() const noexcept; ```

[horizontal]
返回：指向容器尾后值的 `const_iterator`。

---

=== 大小与容量

==== 空

```c++ [[nodiscard]] bool empty() const noexcept; ```

[horizontal]
返回：`size() == 0`。

---

==== 大小

```c++ size_type size() const noexcept; ```

[horizontal]
返回：`std::distance(begin(), end())`。

---

==== max_size

```c++ size_type max_size() const noexcept; ```

[horizontal]
返回：可能的最大容器的 `size()`。

---

=== 修改器

==== 原地构造
```c++ template<class... args=""> std::pair<iterator, bool=""> emplace(Args&amp;&amp;... args); ```</iterator,></class...>

当且仅当容器中没有具有等价键的元素时，才插入一个使用参数 `args` 构造的对象。

[horizontal]
要求：`value_type` 必须可以从 `args` 出发在 `X` 中进行 https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[可原位构造^]。  返回：如果发生了插入，则返回类型的 bool 分量为 true。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  指向元素的指针和引用永远不会失效。  
如果 `args...` 的形式为 `k,v`，则该函数会延迟构造整个对象，直到确定应该插入元素为止，仅使用 `k` 参数进行检查。当映射的 `key_type` 可移动构造或 `k` 参数本身就是 `key_type` 类型时，此优化生效。

---

==== emplace_hint
```c++ template<class... args=""> iterator emplace_hint(const_iterator position, Args&amp;&amp;... args); ```</class...>

当且仅当容器中没有具有等价键的元素时，才插入一个使用参数 `args` 构造的对象。

`position` 是关于元素插入位置的建议。

[horizontal]
要求：`value_type` 必须可以从 `args` 出发在 `X` 中进行 https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[可原位构造^]。  返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。  
如果 `args...` 的形式为 `k,v`，则该函数会延迟构造整个对象，直到确定应该插入元素为止，仅使用 `k` 参数进行检查。当映射的 `key_type` 可移动构造或 `k` 参数本身就是 `key_type` 类型时，此优化生效。

---

==== 复制插入
```c++ std::pair<iterator, bool=""> insert(const value_type&amp; obj); ```</iterator,>

当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。

[horizontal]
要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。  
返回：返回类型的 bool 分量为 true 表示发生了插入。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 移动插入
```c++ std::pair<iterator, bool=""> insert(value_type&amp;&amp; obj); ```</iterator,>

当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。

[horizontal]
要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/MoveInsertable[可移动插入^]。  
返回：返回类型的 bool 分量为 true 表示发生了插入。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 原地插入
```c++ template<class p=""> std::pair<iterator, bool=""> insert(P&amp;&amp; obj); ```</iterator,></class>

通过执行 `emplace(std::forward<p>(value))` 向容器中插入一个元素。</p>

仅当 std::is_constructible<value_type, p&&="">::value 为 true 时参与重载决议。</value_type,>

[horizontal]
返回：返回类型的 bool 分量为 true 表示发生了插入。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。

---

==== 带提示的复制插入
```c++iterator insert(const_iterator hint, const value_type&amp; obj);```
当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。

`hint` 是关于元素插入位置的建议。

[horizontal]
要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。  
返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 带提示的移动插入
```c++ iterator insert(const_iterator hint, value_type&amp;&amp; obj); ```

当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。

`hint` 是关于元素插入位置的建议。

[horizontal]
要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/MoveInsertable[可移动插入^]。  
返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 带提示的原地插入

```c++ template<class p=""> iterator insert(const_iterator hint, P&amp;&amp; obj); ```</class>

通过执行 `emplace_hint(hint, std::forward<p>(value))` 向容器中插入一个元素。</p>

仅当 std::is_constructible<value_type, p&&="">::value 为 true 时参与重载决议。</value_type,>

`hint` 是关于元素插入位置的建议。

[horizontal]
返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 迭代器范围插入
```c++ template<class inputiterator=""> void insert(InputIterator first, InputIterator last); ```</class>

将一个范围内的元素插入容器中。当且仅当容器中没有具有等价键的元素时，才会插入这些元素。

[horizontal]
要求：`value_type` 必须可以从 `*first` 出发在 `X` 中进行 https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[可原位构造^]。  
抛出：当插入单个元素时，如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== 初始化列表插入
```c++ void insert(std::initializer_list<value_type>); ```</value_type>

将一个范围内的元素插入容器中。当且仅当容器中没有具有等价键的元素时，才会插入这些元素。

[horizontal]
要求：`value_type` 可以在容器中进行 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。  
抛出：当插入单个元素时，如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。

---

==== try_emplace
```c++ template<class... args=""> std::pair<iterator, bool=""> try_emplace(const key_type&amp; k, Args&amp;&amp;... args); template<class... args=""> std::pair<iterator, bool=""> try_emplace(key_type&amp;&amp; k, Args&amp;&amp;... args); template<class k,="" class...="" args=""> std::pair<iterator, bool=""> try_emplace(K&amp;&amp; k, Args&amp;&amp;... args) ```</iterator,></class></iterator,></class...></iterator,></class...>

如果容器中不存在键为 `k` 的元素，则插入一个新元素。

如果已存在键为 `k` 的元素，则该函数不执行任何操作。

[horizontal]
返回：返回类型的 bool 分量为 true 表示发生了插入。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：此函数类似于 xref:#unordered_map_emplace[emplace]，区别在于 `value_type` 的构造方式如下：  ```c++
// first two overloads
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<key>(k)), std::forward_as_tuple(std::forward<args>(args)...))</args></key>

// third overload
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<k>(k)), std::forward_as_tuple(std::forward<args>(args)...)) ```</args></k>

而不是像 xref:#unordered_map_emplace[emplace] 那样简单地将所有参数转发给 `value_type` 的构造函数。

可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。

指向元素的指针和引用永远不会失效。

`template<class k,="" args="">` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== 带提示位置的 `try_emplace`
```c++ template<class... args=""> iterator try_emplace(const_iterator hint, const key_type&amp; k, Args&amp;&amp;... args); template<class... args=""> iterator try_emplace(const_iterator hint, key_type&amp;&amp; k, Args&amp;&amp;... args); template<class k,="" class...="" args=""> iterator try_emplace(const_iterator hint, K&amp;&amp; k, Args&amp;&amp;... args); ```</class></class...></class...>

如果容器中不存在键为 `k` 的元素，则插入一个新元素。

如果已存在键为 `k` 的元素，则该函数不执行任何操作。

`hint` 是关于元素插入位置的建议。

[horizontal]
返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：此函数类似于 xref:#unordered_map_emplace_hint[emplace_hint]，区别在于 `value_type` 的构造方式如下：  
```c++
// first two overloads
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<key>(k)), std::forward_as_tuple(std::forward<args>(args)...))</args></key>

// third overload
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<k>(k)), std::forward_as_tuple(std::forward<args>(args)...)) ```</args></k>

而不是像 xref:#unordered_map_emplace_hint[emplace_hint] 那样简单地将所有参数转发给 `value_type` 的构造函数。

标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。

可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。

指向元素的指针和引用永远不会失效。

`template<class k,="" args="">` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== insert_or_assign
```c++ template<class m=""> std::pair<iterator, bool=""> insert_or_assign(const key_type&amp; k, M&amp;&amp; obj); template<class m=""> std::pair<iterator, bool=""> insert_or_assign(key_type&amp;&amp; k, M&amp;&amp; obj); template<class k,="" class="" m=""> std::pair<iterator, bool=""> insert_or_assign(K&amp;&amp; k, M&amp;&amp; obj); ```</iterator,></class></iterator,></class></iterator,></class>

向容器中插入一个新元素，或通过赋值更新现有元素的值。

如果存在键为 `k` 的元素，则通过赋值 `std::forward<m>(obj)` 来更新它。</m>

如果不存在这样的元素，则将其添加到容器中，形式为：  
```c++
// first two overloads
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<key>(k)), std::forward_as_tuple(std::forward<m>(obj)))</m></key>

// third overload
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<k>(k)), std::forward_as_tuple(std::forward<m>(obj))) ```</m></k>

[horizontal]
返回：返回类型的 bool 分量为 true 表示发生了插入。  
如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。  

`template<class k,="" class="" m="">` 仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== 带提示位置的 `insert_or_assign`
```c++ template<class m=""> iterator insert_or_assign(const_iterator hint, const key_type&amp; k, M&amp;&amp; obj); template<class m=""> iterator insert_or_assign(const_iterator hint, key_type&amp;&amp; k, M&amp;&amp; obj); template<class k,="" class="" m=""> iterator insert_or_assign(const_iterator hint, K&amp;&amp; k, M&amp;&amp; obj); ```</class></class></class>

向容器中插入一个新元素，或通过赋值更新现有元素的值。

如果存在键为 `k` 的元素，则通过赋值 `std::forward<m>(obj)` 来更新它。</m>

如果不存在这样的元素，则将其添加到容器中，形式为：  
```c++
// first two overloads
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<key>(k)), std::forward_as_tuple(std::forward<m>(obj)))</m></key>

// third overload
value_type(std::piecewise_construct, std::forward_as_tuple(std::forward<k>(k)), std::forward_as_tuple(std::forward<m>(obj))) ```</m></k>

`hint` 是关于元素插入位置的建议。

[horizontal]
返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  指向元素的指针和引用永远不会失效。  
`template<class k,="" class="" m="">` 仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== 通过迭代器提取
```c++ node_type extract(const_iterator position); ```

移除 `position` 所指向的元素。

[horizontal]
返回：一个拥有该元素的 `node_type`。  
注意：通过此方法提取的节点可以插入到兼容的 `unordered_multimap` 中。

---

==== 通过键提取
```c++ node_type extract(const key_type&amp; k); template<class k=""> node_type extract(K&amp;&amp; k); ```</class>

移除一个键与 `k` 等价的元素。

[horizontal]
返回：如果找到该元素，则返回一个拥有该元素的 `node_type`；否则返回一个空的 `node_type`。  
抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。  
注意：通过此方法提取的节点可以插入到兼容的 `unordered_multimap` 中。  
`template<class k="">` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== 通过 `node_handle` 插入
```c++ insert_return_type insert(node_type&amp;&amp; nh); ```

如果 `nh` 为空，则无效果。

否则，当且仅当容器中没有具有等价键的元素时，才插入 `nh` 所拥有的元素。

[horizontal]
要求：`nh` 为空或 `nh.get_allocator()` 等于容器的分配器。  
返回：如果 `nh` 为空，则返回一个 `insert_return_type`，其中 `inserted` 为 `false`，`position` 等于 `end()`，`node` 为空。  
否则如果已存在具有等价键的元素，则返回一个 `insert_return_type`，其中 `inserted` 为 `false`，`position` 指向匹配的元素，`node` 包含 `nh` 中的节点。  
否则如果插入成功，则返回一个 `insert_return_type`，其中 `inserted` 为 `true`，`position` 指向新插入的元素，`node` 为空。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。  
此函数可用于插入从兼容的 `unordered_multimap` 中提取的节点。

---

==== 带提示和 `node_handle` 的插入
```c++ iterator insert(const_iterator hint, node_type&amp;&amp; nh); ```

如果 `nh` 为空，则无效果。

否则，当且仅当容器中没有具有等价键的元素时，才插入 `nh` 所拥有的元素。

如果容器中已存在具有等价键的元素，则对 `nh` 无影响（即 `nh` 仍然包含该节点）。

`hint` 是关于元素插入位置的建议。

[horizontal]
要求：`nh` 为空或 `nh.get_allocator()` 等于容器的分配器。  
返回：如果 `nh` 为空，则返回 `end()`。  
如果容器中已存在具有等价键的元素，则返回指向该元素的迭代器。  
否则返回指向新插入元素的迭代器。  
抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。  
注意：标准关于 `hint` 的含义表述相当模糊。但唯一实际的使用方式，也是 Boost.Unordered 支持的唯一方式，是将其指向一个具有相同键的已存在元素。  
可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。  
指向元素的指针和引用永远不会失效。  
此函数可用于插入从兼容的 `unordered_multimap` 中提取的节点。

---

==== 通过位置擦除

```c++ iterator erase(iterator position); iterator erase(const_iterator position); ```

擦除 `position` 所指向的元素。

[horizontal]
返回：`position` 在被擦除之前的后一个迭代器。  
抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。  
注意：在旧版本中，此操作可能效率较低，因为它需要搜索多个桶以找到返回迭代器的位置。数据结构已经更改，不再是这种情况，并且备用的擦除方法已被弃用。

---

==== 通过键擦除
```c++ size_type erase(const key_type&amp; k); template<class k=""> size_type erase(K&amp;&amp; k); ```</class>

擦除所有键与 `k` 等价的元素。

[horizontal]
返回：被擦除的元素数量。  
抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。  
注意：`template<class k="">` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。</class>

---

==== 范围擦除

```c++ iterator erase(const_iterator first, const_iterator last); ```

擦除从 `first` 到 `last` 范围内的元素。

[horizontal]
返回：被擦除元素之后的迭代器——即 `last`。  
抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。  
在此实现中，此重载不会调用任何函数对象的方法，因此不会抛出异常，但这在其他实现中可能并不成立。

---

==== quick_erase
```c++ void quick_erase(const_iterator position); ```

擦除 `position` 所指向的元素。

[horizontal]
抛出：;; 仅当由 `hasher` 或 `key_equal` 抛出异常时才会抛出异常。

在此实现中，此重载不会调用任一函数对象的方法，因此不会抛出异常，但在其他实现中可能并非如此。

备注：;; 之所以实现此方法，是因为从 `erase` 返回下一个元素的迭代器开销较大，但容器已经过重新设计，情况不再如此。因此，此方法现已废弃。

---

==== erase_return_void
```c++ void erase_return_void(const_iterator position); ```

擦除 `position` 所指向的元素。

[horizontal]
抛出：;; 仅当由 `hasher` 或 `key_equal` 抛出异常时才会抛出异常。

在此实现中，此重载不会调用任一函数对象的方法，因此不会抛出异常，但在其他实现中可能并非如此。

备注：;; 之所以实现此方法，是因为从 `erase` 返回下一个元素的迭代器开销较大，但容器已经过重新设计，情况不再如此。因此，此方法现已废弃。

---

==== 交换
```c++ void swap(unordered_map&amp; other) noexcept(boost::allocator_traits<allocator>::is_always_equal::value &amp;&amp; boost::is_nothrow_swappable_v<hash> &amp;&amp; boost::is_nothrow_swappable_v<pred>); ```</pred></hash></allocator>

将容器的内容与参数进行交换。

如果 `Allocator::propagate_on_container_swap` 已声明且 `Allocator::propagate_on_container_swap::value` 为 `true`，则交换两个容器的分配器。否则，使用不相等的分配器进行交换将导致未定义行为。

[horizontal]
抛出：;; 除非由 `key_equal` 或 `hasher` 的复制构造函数或复制赋值运算符抛出异常，否则不会抛出异常。
备注：;; 异常规范与 C++11 标准不完全相同，因为相等谓词和哈希函数是通过它们的复制构造函数进行交换的。

---

==== 清空
```c++ void clear(); ```

清除容器中的所有元素。

[horizontal]
后置条件：;; `size() == 0`抛出：;; 永不抛出异常。

---

==== 合并
```c++ template<class h2,="" class="" p2=""> void merge(unordered_map<key, t,="" h2,="" p2,="" allocator="">&amp; source); template<class h2,="" class="" p2=""> void merge(unordered_map<key, t,="" h2,="" p2,="" allocator="">&amp;&amp; source); template<class h2,="" class="" p2=""> void merge(unordered_multimap<key, t,="" h2,="" p2,="" allocator="">&amp; source); template<class h2,="" class="" p2=""> void merge(unordered_multimap<key, t,="" h2,="" p2,="" allocator="">&amp;&amp; source); ```</key,></class></key,></class></key,></class></key,></class>

尝试通过迭代 `source` 并提取 `source` 中不包含在 `*this` 内的任何节点，然后将其插入到 `*this` 中，从而实现两个容器的“合并”。

由于 `source` 可能具有不同的哈希函数和键相等谓词，因此 `source` 中每个节点的键都将使用 `this-&gt;hash_function()` 重新计算哈希值，然后根据需要再使用 `this-&gt;key_eq()` 进行比较。

如果 `this-&gt;get_allocator() != source.get_allocator()`，则此函数的行为未定义。

此函数不会复制或移动任何元素，而只是将节点从 `source` 重新定位到 `*this` 中。

[horizontal]
注意:;; + --
* 指向被转移元素的指针和引用保持有效。
* 使指向被转移元素的迭代器失效。
* 使属于 `*this` 的迭代器失效。
* `source` 中未被转移的元素的迭代器保持有效。
--

---

=== 观察器

==== get_allocator
``` allocator_type get_allocator() const; ```

---

==== 哈希函数
``` hasher hash_function() const; ```

[horizontal]
返回：;; 容器的哈希函数。

---

==== key_eq
``` key_equal key_eq() const; ```

[horizontal]
返回：;; 容器的键相等谓词。

---

=== 查找

==== find
```c++ iterator         find(const key_type&amp; k); const_iterator   find(const key_type&amp; k) const; template<class k=""> iterator       find(const K&amp; k); template<class k=""> const_iterator find(const K&amp; k) const; template<typename compatiblekey,="" typename="" compatiblehash,="" compatiblepredicate=""> iterator       find(CompatibleKey const&amp; k, CompatibleHash const&amp; hash, CompatiblePredicate const&amp; eq); template<typename compatiblekey,="" typename="" compatiblehash,="" compatiblepredicate=""> const_iterator find(CompatibleKey const&amp; k, CompatibleHash const&amp; hash, CompatiblePredicate const&amp; eq) const;</typename></typename></class></class>

```

[horizontal]
返回：;; 指向键与 `k` 等价之元素的迭代器；若无此元素，则返回 `b.end()`。
备注：;; 包含 `CompatibleKey`、`CompatibleHash` 和 `CompatiblePredicate` 的模板重载属于非标准扩展，允许使用兼容的哈希函数和相等谓词来处理不同类型的键，从而避免昂贵的类型转换。通常不建议使用它们，而应使用 `K` 成员函数模板。
此外，仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

==== count
```c++ size_type        count(const key_type&amp; k) const; template<class k=""> size_type      count(const K&amp; k) const; ```</class>

[horizontal]
返回：;; 键与 `k` 等价的元素个数。
备注：;; 仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

==== 包含
```c++ bool             contains(const key_type&amp; k) const; template<class k=""> bool           contains(const K&amp; k) const; ```</class>

[horizontal]
返回：;; 一个布尔值，指示容器中是否存在键等于 `key` 的元素。
备注：;; 仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

==== equal_range
```c++ std::pair<iterator, iterator="">               equal_range(const key_type&amp; k); std::pair<const_iterator, const_iterator="">   equal_range(const key_type&amp; k) const; template<class k=""> std::pair<iterator, iterator="">             equal_range(const K&amp; k); template<class k=""> std::pair<const_iterator, const_iterator=""> equal_range(const K&amp; k) const; ```</const_iterator,></class></iterator,></class></const_iterator,></iterator,>

[horizontal]
返回：;; 一个范围，包含所有键与 `k` 等价的元素。若容器中不包含任何此类元素，则返回 `std::make_pair(b.end(), b.end())`。
备注：;; 仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

==== operator++[++++]++
```c++ mapped_type&amp; operator[](const key_type&amp; k); mapped_type&amp; operator[](key_type&amp;&amp; k); template<class k=""> mapped_type&amp; operator[](K&amp;&amp; k); ```</class>

[horizontal]
效果：;; 如果容器中尚不存在键与 `k` 等价的元素，则插入值 `std::pair<key_type const,="" mapped_type="">(k, mapped_type())`。
返回：;; 指向 `x.second` 的引用，其中 `x` 是容器中已存在的元素，或者是键与 `k` 等价的新插入元素。
抛出：;; 如果除调用 `hasher` 之外的操作抛出异常，则该函数无效。
备注：;; 可能使迭代器失效，但仅当插入导致负载因子大于或等于最大负载因子时才会发生。
此外，指向元素的指针和引用永远不会失效。
另外，仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class></key_type>

---

==== at
```c++ mapped_type&amp; at(const key_type&amp; k); const mapped_type&amp; at(const key_type&amp; k) const; template<class k=""> mapped_type&amp; at(const K&amp; k); template<class k=""> const mapped_type&amp; at(const K&amp; k) const; ```</class></class>

[horizontal]
返回：;; 指向 `x.second` 的引用，其中 `x` 是键与 `k` 等价的（唯一）元素。
抛出：;; 如果不存在这样的元素，则抛出 `std::out_of_range` 类型的异常对象。
备注：;; 仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

=== 桶接口

==== bucket_count
```c++ size_type bucket_count() const noexcept; ```

[horizontal]
返回：;; 桶的数量。

---

==== max_bucket_count
```c++ size_type max_bucket_count() const noexcept; ```

[horizontal]
返回：;; 桶数量的上限。

---

==== 桶大小
```c++ size_type bucket_size(size_type n) const; ```

[horizontal]
要求：;; `n &lt; bucket_count()`返回：;; 桶 `n` 中的元素个数。

---

==== 桶
```c++ size_type bucket(const key_type&amp; k) const; template<class k=""> size_type bucket(const K&amp; k) const; ```</class>

[horizontal]
返回：;; 包含键 `k` 的元素的桶索引。
后置条件：;; 返回值小于 `bucket_count()`。
备注：;; 仅当 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时，`template<class k="">` 重载才会参与重载决议。库假定 `Hash` 可同时以 `K` 和 `Key` 类型调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型的开销。</class>

---

==== begin

```c++ local_iterator begin(size_type n); const_local_iterator begin(size_type n) const; ```

[horizontal]
要求：;; `n` 应在 `[0, bucket_count())` 范围内。
返回：;; 指向索引为 `n` 的桶中第一个元素的局部迭代器。

---

==== end
```c++ local_iterator end(size_type n); const_local_iterator end(size_type n) const; ```

[horizontal]
要求：;; `n` 应在 `[0, bucket_count())` 范围内。
返回：;; 指向索引为 `n` 的桶中“尾后”元素的局部迭代器。

---

==== cbegin
```c++ const_local_iterator cbegin(size_type n) const; ```

[horizontal]
要求：;; `n` 应在 `[0, bucket_count())` 范围内。
返回：;; 指向索引为 `n` 的桶中第一个元素的常量局部迭代器。

---

==== cend
```c++ const_local_iterator cend(size_type n) const; ```

[horizontal]
要求：;; `n` 应在 `[0, bucket_count())` 范围内。
返回：;; 指向索引为 `n` 的桶中“尾后”元素的常量局部迭代器。

---

=== 哈希策略

==== 负载因子
```c++ float load_factor() const noexcept; ```

[horizontal]
返回：;; 每个桶的平均元素个数。

---

==== max_load_factor

```c++ float max_load_factor() const noexcept; ```

[horizontal]
返回：;; 返回当前的最大负载因子。

---

==== 设置最大负载因子
```c++ void max_load_factor(float z); ```

[horizontal]
效果：;; 改变容器的最大负载因子，以 `z` 作为提示。

---


==== 重哈希
```c++ void rehash(size_type n); ```

改变桶的数量，使得至少包含 `n` 个桶，并且使得负载因子小于或等于最大负载因子。在适用的情况下，这将增大或缩小与容器相关联的 `bucket_count()`。

当 `size() == 0` 时，`rehash(0)` 将释放底层桶数组的内存。

使迭代器失效，并改变元素的顺序。指向元素的指针和引用不会失效。

[horizontal]
抛出：;; 如果抛出异常（除非是由容器的哈希函数或比较函数抛出），则该函数无效。

---

==== 保留
```c++ void reserve(size_type n); ```

等价于 `a.rehash(ceil(n / a.max_load_factor()))`；如果 `n &gt; 0` 且 `a.max_load_factor() == std::numeric_limits<float>::infinity()`，则等价于 `a.rehash(1)`。</float>

与 `rehash` 类似，此函数可用于增加或减少容器中桶的数量。

使迭代器失效，并改变元素的顺序。指向元素的指针和引用不会失效。

[horizontal]
抛出：;; 如果抛出异常（除非是由容器的哈希函数或比较函数抛出），则该函数无效。

=== 推导指引
在以下任一条件成立时，推导指引将不参与重载决议：

- 它具有 `InputIterator` 模板参数，并且为该参数推导出的类型不符合输入迭代器的要求。
- 它具有 `Allocator` 模板参数，并且为该参数推导出的类型不符合分配器的要求。
- 它具有 `Hash` 模板参数，并且为该参数推导出的是整数类型或符合分配器要求的类型。
- 它具有 `Pred` 模板参数，并且为该参数推导出的是符合分配器要求的类型。

推导指引中的 `size_type` 参数类型指向由该推导指引所推导出的容器类型的 `size_type` 成员类型。其默认值与所选构造函数的默认值一致。

==== _iter-value-type_
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-value-type__ =
    typename std::iterator_traits<InputIterator>::value_type; // exposition only
-----

==== __iter-key-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-key-type__ = std::remove_const_t<
    std::tuple_element_t<0, xref:#unordered_map_iter_value_type[__iter-value-type__]<InputIterator>>>; // exposition only
-----

==== __iter-mapped-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-mapped-type__ =
    std::tuple_element_t<1, xref:#unordered_map_iter_value_type[__iter-value-type__]<InputIterator>>;  // exposition only
-----

==== __iter-to-alloc-type__
[listings,subs="+macros,+quotes"]
-----
template<class InputIterator>
  using __iter-to-alloc-type__ = std::pair<
    std::add_const_t<std::tuple_element_t<0, xref:#unordered_map_iter_value_type[__iter-value-type__]<InputIterator>>>,
    std::tuple_element_t<1, xref:#unordered_map_iter_value_type[__iter-value-type__]<InputIterator>>>; // exposition only
-----

=== 相等性比较

==== operator
```c++ template<class key,="" class="" t,="" hash,="" pred,="" alloc=""> bool operator==(const unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; x, const unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; y); ```</key,></key,></class>

如果 `x.size() == y.size()` 并且对于 `x` 中的每个元素，在 `y` 中都有一个具有相同键且值相等的元素（使用 `operator==` 比较值类型），则返回 `true`。

[horizontal]
备注：;; 如果两个容器不具有等价的相等谓词，则行为未定义。

---

==== operator!
```c++ template<class key,="" class="" t,="" hash,="" pred,="" alloc=""> bool operator!=(const unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; x, const unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; y); ```</key,></key,></class>

如果 `x.size() == y.size()` 并且对于 `x` 中的每个元素，在 `y` 中都有一个具有相同键且值相等的元素（使用 `operator==` 比较值类型），则返回 `false`。

[horizontal]
备注：;; 如果两个容器不具有等价的相等谓词，则行为未定义。

=== 交换
```c++ template<class key,="" class="" t,="" hash,="" pred,="" alloc=""> void swap(unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; x, unordered_map<key, t,="" hash,="" pred,="" alloc="">&amp; y) noexcept(noexcept(x.swap(y))); ```</key,></key,></class>

交换 `x` 和 `y` 的内容。

如果 `Allocator::propagate_on_container_swap` 已声明且 `Allocator::propagate_on_container_swap::value` 为 `true`，则交换两个容器的分配器。否则，使用不相等的分配器进行交换将导致未定义行为。

[horizontal]
效果：;; `x.swap(y)`
抛出：;; 除非由 `key_equal` 或 `hasher` 的复制构造函数或复制赋值运算符抛出异常，否则不会抛出异常。
备注：;; 异常规范与 C++11 标准不完全相同，因为相等谓词和哈希函数是通过它们的复制构造函数进行交换的。

---

=== erase_if
```c++ template<class k,="" class="" t,="" h,="" p,="" a,="" predicate=""> typename unordered_map<k, t,="" h,="" p,="" a="">::size_type erase_if(unordered_map<k, t,="" h,="" p,="" a="">&amp; c, Predicate pred); ```</k,></k,></class>

遍历容器 `c` 并移除所有使给定谓词返回 `true` 的元素。

[horizontal]
返回：;; 被移除的元素数量。备注：;; 等价于：```c++auto original_size = c.size();for (auto i = c.begin(), last = c.end(); i != last; ) {    if (pred(*i)) {        i = c.erase(i);    } else {       ++i;    }}return original_size - c.size();```注意，传递给 `pred` 的引用是非常量的。

=== 序列化

`unordered_map` 可以通过本库提供的 API，使用 link:../../../../../serialization/index.html[Boost.Serialization^] 进行归档/恢复。支持常规归档和 XML 归档。

==== 将 unordered_map 保存到归档

将 `unordered_map` `x` 的所有元素保存到归档（XML 归档）`ar` 中。

[horizontal]
要求：;; `std::remove_const<key_type>::type` 和 `std::remove_const<mapped_type>::type` 必须是可序列化的（支持 XML 序列化），并且它们支持 Boost.Serialization 的 `save_construct_data`/`load_construct_data` 协议（该协议由 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[DefaultConstructible^] 类型的自动支持）。</mapped_type></key_type>

---

==== 从归档中加载 unordered_map

删除 `unordered_map` `x` 中所有已存在的元素，并从归档（XML 归档）`ar` 中插入由 `ar` 所读取存储中保存的原始 `unordered_map` `other` 元素的恢复副本。

[horizontal]
要求：;; `value_type` 可以从 `(std::remove_const<key_type>::type&amp;&amp;, std::remove_const<mapped_type>::type&amp;&amp;)` 进行 https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^]。`x.key_equal()` 在功能上等价于 `other.key_equal()`。
注意：;; 如果归档是使用 Boost 1.84 之前的 Boost 版本保存的，则必须全局定义配置宏 `BOOST_UNORDERED_ENABLE_SERIALIZATION_COMPATIBILITY_V0` 才能使此操作成功；否则将抛出异常。</mapped_type></key_type>

---

==== 将迭代器/常量迭代器保存到归档中

将 `iterator`（`const_iterator`）`it` 的位置信息保存到归档（XML 归档）`ar` 中。`it` 可以是 `end()` 迭代器。

[horizontal]
要求：;; `it` 所指向的 `unordered_map` `x` 此前已保存至 `ar`，并且在保存 `x` 和保存 `it` 之间未对 `x` 执行任何修改操作。

---

==== 从归档中加载迭代器/常量迭代器

使 `iterator`（`const_iterator`）`it` 指向保存到由归档（XML 归档）`ar` 读取的存储中的原始 `iterator`（`const_iterator`）的被恢复位置。

[horizontal]
要求：;; 如果 `x` 是 `it` 所指向的 `unordered_map`，则在加载 `x` 和加载 `it` 之间未对 `x` 执行任何修改操作。
