[#unordered_node_map] == 类模板 unordered_node_map :idprefix: unordered_node_map_ `boost::unordered_node_map` — 一个基于节点的、开放寻址的无序关联容器，将唯一键与对应值相关联。 `boost::unordered_node_map` 使用与 `boost::unordered_flat_map` 类似的开放寻址布局，但由于其基于节点的特性，它提供了指针稳定性和节点处理功能。其性能介于 `boost::unordered_map` 和 `boost::unordered_flat_map` 之间。 由于使用开放寻址，`boost::unordered_node_map` 的接口在多个方面与 `boost::unordered_map`/`std::unordered_map` 有所不同： - `begin()` 不是常数时间复杂度操作。 - 未提供用于桶管理的 API（除 `bucket_count` 外）。 - 容器的最大负载因子由内部管理，用户无法进行设置。 除此之外，`boost::unordered_node_map` 基本上可以作为标准无序关联容器的即时代替品。 === 概要 [listing,subs="+macros,+quotes"] ----- // #include xref:reference/header_unordered_node_map.adoc[``] namespace boost { namespace unordered { template, class Pred = std::equal_to, class Allocator = std::allocator>> class unordered_node_map { public: // types using key_type = Key; using mapped_type = T; using value_type = std::pair; using init_type = std::pair< typename std::remove_const::type, typename std::remove_const::type >; using hasher = Hash; using key_equal = Pred; using allocator_type = Allocator; using pointer = typename std::allocator_traits::pointer; using const_pointer = typename std::allocator_traits::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 node_type = _implementation-defined_; using insert_return_type = _implementation-defined_; using stats = xref:reference/stats.adoc#stats_stats_type[__stats-type__]; // if statistics are xref:unordered_node_map_boost_unordered_enable_stats[enabled] // construct/copy/destroy xref:#unordered_node_map_default_constructor[unordered_node_map](); explicit xref:#unordered_node_map_bucket_count_constructor[unordered_node_map](size_type n, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); template xref:#unordered_node_map_iterator_range_constructor[unordered_node_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_node_map_copy_constructor[unordered_node_map](const unordered_node_map& other); xref:#unordered_node_map_move_constructor[unordered_node_map](unordered_node_map&& other); template xref:#unordered_node_map_iterator_range_constructor_with_allocator[unordered_node_map](InputIterator f, InputIterator l, const allocator_type& a); explicit xref:#unordered_node_map_allocator_constructor[unordered_node_map](const Allocator& a); xref:#unordered_node_map_copy_constructor_with_allocator[unordered_node_map](const unordered_node_map& other, const Allocator& a); xref:#unordered_node_map_move_constructor_with_allocator[unordered_node_map](unordered_node_map&& other, const Allocator& a); xref:#unordered_node_map_move_constructor_from_concurrent_node_map[unordered_node_map](concurrent_node_map&& other); xref:#unordered_node_map_initializer_list_constructor[unordered_node_map](std::initializer_list il, size_type n = _implementation-defined_ const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); xref:#unordered_node_map_bucket_count_constructor_with_allocator[unordered_node_map](size_type n, const allocator_type& a); xref:#unordered_node_map_bucket_count_constructor_with_hasher_and_allocator[unordered_node_map](size_type n, const hasher& hf, const allocator_type& a); template xref:#unordered_node_map_iterator_range_constructor_with_bucket_count_and_allocator[unordered_node_map](InputIterator f, InputIterator l, size_type n, const allocator_type& a); template xref:#unordered_node_map_iterator_range_constructor_with_bucket_count_and_hasher[unordered_node_map](InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); xref:#unordered_node_map_initializer_list_constructor_with_allocator[unordered_node_map](std::initializer_list il, const allocator_type& a); xref:#unordered_node_map_initializer_list_constructor_with_bucket_count_and_allocator[unordered_node_map](std::initializer_list il, size_type n, const allocator_type& a); xref:#unordered_node_map_initializer_list_constructor_with_bucket_count_and_hasher_and_allocator[unordered_node_map](std::initializer_list il, size_type n, const hasher& hf, const allocator_type& a); xref:#unordered_node_map_destructor[~unordered_node_map](); unordered_node_map& xref:#unordered_node_map_copy_assignment[operator++=++](const unordered_node_map& other); unordered_node_map& xref:#unordered_node_map_move_assignment[operator++=++](unordered_node_map&& other) ++noexcept( (boost::allocator_traits::is_always_equal::value || boost::allocator_traits::propagate_on_container_move_assignment::value) && std::is_same::value);++ unordered_node_map& xref:#unordered_node_map_initializer_list_assignment[operator++=++](std::initializer_list); allocator_type xref:#unordered_node_map_get_allocator[get_allocator]() const noexcept; // iterators iterator xref:#unordered_node_map_begin[begin]() noexcept; const_iterator xref:#unordered_node_map_begin[begin]() const noexcept; iterator xref:#unordered_node_map_end[end]() noexcept; const_iterator xref:#unordered_node_map_end[end]() const noexcept; const_iterator xref:#unordered_node_map_cbegin[cbegin]() const noexcept; const_iterator xref:#unordered_node_map_cend[cend]() const noexcept; // capacity ++[[nodiscard]]++ bool xref:#unordered_node_map_empty[empty]() const noexcept; size_type xref:#unordered_node_map_size[size]() const noexcept; size_type xref:#unordered_node_map_max_size[max_size]() const noexcept; // modifiers template std::pair xref:#unordered_node_map_emplace[emplace](Args&&... args); template iterator xref:#unordered_node_map_emplace_hint[emplace_hint](const_iterator position, Args&&... args); std::pair xref:#unordered_node_map_copy_insert[insert](const value_type& obj); std::pair xref:#unordered_node_map_copy_insert[insert](const init_type& obj); std::pair xref:#unordered_node_map_move_insert[insert](value_type&& obj); std::pair xref:#unordered_node_map_move_insert[insert](init_type&& obj); iterator xref:#unordered_node_map_copy_insert_with_hint[insert](const_iterator hint, const value_type& obj); iterator xref:#unordered_node_map_copy_insert_with_hint[insert](const_iterator hint, const init_type& obj); iterator xref:#unordered_node_map_move_insert_with_hint[insert](const_iterator hint, value_type&& obj); iterator xref:#unordered_node_map_copy_insert_with_hint[insert](const_iterator hint, init_type&& obj); template void xref:#unordered_node_map_insert_iterator_range[insert](InputIterator first, InputIterator last); void xref:#unordered_node_map_insert_initializer_list[insert](std::initializer_list); insert_return_type xref:#unordered_node_map_insert_node[insert](node_type&& nh); iterator xref:#unordered_node_map_insert_node_with_hint[insert](const_iterator hint, node_type&& nh); template std::pair xref:#unordered_node_map_try_emplace[try_emplace](const key_type& k, Args&&... args); template std::pair xref:#unordered_node_map_try_emplace[try_emplace](key_type&& k, Args&&... args); template std::pair xref:#unordered_node_map_try_emplace[try_emplace](K&& k, Args&&... args); template iterator xref:#unordered_node_map_try_emplace_with_hint[try_emplace](const_iterator hint, const key_type& k, Args&&... args); template iterator xref:#unordered_node_map_try_emplace_with_hint[try_emplace](const_iterator hint, key_type&& k, Args&&... args); template iterator xref:#unordered_node_map_try_emplace_with_hint[try_emplace](const_iterator hint, K&& k, Args&&... args); template std::pair xref:#unordered_node_map_insert_or_assign[insert_or_assign](const key_type& k, M&& obj); template std::pair xref:#unordered_node_map_insert_or_assign[insert_or_assign](key_type&& k, M&& obj); template std::pair xref:#unordered_node_map_insert_or_assign[insert_or_assign](K&& k, M&& obj); template iterator xref:#unordered_node_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, const key_type& k, M&& obj); template iterator xref:#unordered_node_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, key_type&& k, M&& obj); template iterator xref:#unordered_node_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, K&& k, M&& obj); _convertible-to-iterator_ xref:#unordered_node_map_erase_by_position[erase](iterator position); _convertible-to-iterator_ xref:#unordered_node_map_erase_by_position[erase](const_iterator position); size_type xref:#unordered_node_map_erase_by_key[erase](const key_type& k); template size_type xref:#unordered_node_map_erase_by_key[erase](K&& k); iterator xref:#unordered_node_map_erase_range[erase](const_iterator first, const_iterator last); void xref:#unordered_node_map_swap[swap](unordered_node_map& other) noexcept(boost::allocator_traits::is_always_equal::value || boost::allocator_traits::propagate_on_container_swap::value); node_type xref:#unordered_node_map_extract_by_position[extract](const_iterator position); node_type xref:#unordered_node_map_extract_by_key[extract](const key_type& key); template node_type xref:#unordered_node_map_extract_by_key[extract](K&& key); init_type xref:#unordered_node_map_pull[pull](const_iterator position); void xref:#unordered_node_map_clear[clear]() noexcept; template void xref:#unordered_node_map_merge[merge](unordered_node_map& source); template void xref:#unordered_node_map_merge[merge](unordered_node_map&& source); // observers hasher xref:#unordered_node_map_hash_function[hash_function]() const; key_equal xref:#unordered_node_map_key_eq[key_eq]() const; // map operations iterator xref:#unordered_node_map_find[find](const key_type& k); const_iterator xref:#unordered_node_map_find[find](const key_type& k) const; template iterator xref:#unordered_node_map_find[find](const K& k); template const_iterator xref:#unordered_node_map_find[find](const K& k) const; size_type xref:#unordered_node_map_count[count](const key_type& k) const; template size_type xref:#unordered_node_map_count[count](const K& k) const; bool xref:#unordered_node_map_contains[contains](const key_type& k) const; template bool xref:#unordered_node_map_contains[contains](const K& k) const; std::pair xref:#unordered_node_map_equal_range[equal_range](const key_type& k); std::pair xref:#unordered_node_map_equal_range[equal_range](const key_type& k) const; template std::pair xref:#unordered_node_map_equal_range[equal_range](const K& k); template std::pair xref:#unordered_node_map_equal_range[equal_range](const K& k) const; // element access mapped_type& xref:#unordered_node_map_operator[operator[+]+](const key_type& k); mapped_type& xref:#unordered_node_map_operator[operator[+]+](key_type&& k); template mapped_type& xref:#unordered_node_map_operator[operator[+]+](K&& k); mapped_type& xref:#unordered_node_map_at[at](const key_type& k); const mapped_type& xref:#unordered_node_map_at[at](const key_type& k) const; template mapped_type& xref:#unordered_node_map_at[at](const K& k); template const mapped_type& xref:#unordered_node_map_at[at](const K& k) const; // bucket interface size_type xref:#unordered_node_map_bucket_count[bucket_count]() const noexcept; // hash policy float xref:#unordered_node_map_load_factor[load_factor]() const noexcept; float xref:#unordered_node_map_max_load_factor[max_load_factor]() const noexcept; void xref:#unordered_node_map_set_max_load_factor[max_load_factor](float z); size_type xref:#unordered_node_map_max_load[max_load]() const noexcept; void xref:#unordered_node_map_rehash[rehash](size_type n); void xref:#unordered_node_map_reserve[reserve](size_type n); // statistics (if xref:unordered_node_map_boost_unordered_enable_stats[enabled]) stats xref:#unordered_node_map_get_stats[get_stats]() const; void xref:#unordered_node_map_reset_stats[reset_stats]() noexcept; }; // Deduction Guides template>, class Pred = std::equal_to>, class Allocator = std::allocator>> unordered_node_map(InputIterator, InputIterator, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type = xref:#unordered_node_map_deduction_guides[__see below__], Hash = Hash(), Pred = Pred(), Allocator = Allocator()) -> unordered_node_map, xref:#unordered_node_map_iter_mapped_type[__iter-mapped-type__], Hash, Pred, Allocator>; template, class Pred = std::equal_to, class Allocator = std::allocator>> unordered_node_map(std::initializer_list>, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type = xref:#unordered_node_map_deduction_guides[__see below__], Hash = Hash(), Pred = Pred(), Allocator = Allocator()) -> unordered_node_map; template unordered_node_map(InputIterator, InputIterator, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type, Allocator) -> unordered_node_map, xref:#unordered_node_map_iter_mapped_type[__iter-mapped-type__], boost::hash>, std::equal_to>, Allocator>; template unordered_node_map(InputIterator, InputIterator, Allocator) -> unordered_node_map, xref:#unordered_node_map_iter_mapped_type[__iter-mapped-type__], boost::hash>, std::equal_to>, Allocator>; template unordered_node_map(InputIterator, InputIterator, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type, Hash, Allocator) -> unordered_node_map, xref:#unordered_node_map_iter_mapped_type[__iter-mapped-type__], Hash, std::equal_to>, Allocator>; template unordered_node_map(std::initializer_list>, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type, Allocator) -> unordered_node_map, std::equal_to, Allocator>; template unordered_node_map(std::initializer_list>, Allocator) -> unordered_node_map, std::equal_to, Allocator>; template unordered_node_map(std::initializer_list>, typename xref:#unordered_node_map_deduction_guides[__see below__]::size_type, Hash, Allocator) -> unordered_node_map, Allocator>; } // namespace unordered } // namespace boost ----- --- === 描述 *模板参数* [cols="1,1"] |=== |_Key_ .2+|`std::pair` must be https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[EmplaceConstructible^] 从任何可转换为 `std::pair` 的对象构造并插入容器，并且还必须可以从容器中 https://en.cppreference.com/w/cpp/named_req/Erasable[可擦除^]。 |_T_ |_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 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`/`emplace` 自动增加，或者作为调用 `rehash`/`reserve` 的结果。容器的 _负载因子_（元素数量除以桶数量）永远不会大于 `max_load_factor()`，但在容器规模较小时，实现可能会允许更高的负载。 如果 `link:../../../../../container_hash/doc/html/hash.html#ref_hash_is_avalanching[hash_is_avalanching]::value` 为 `true`，则哈希函数将按原样使用；否则，会增加一个位混合后处理阶段，以牺牲额外的计算成本为代价来提高哈希质量。 --- === 配置宏 ==== `BOOST_UNORDERED_ENABLE_STATS` 全局定义此宏可为容器启用 xref:reference/stats.adoc#stats[统计计算]。请注意，此选项会降低许多操作的整体性能。 --- === 类型定义 [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_ 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 struct _insert_return_type_ // name is exposition only { Iterator position; bool inserted; NodeType node; }; ---- 其中 `Iterator` = `iterator`，`NodeType` = `node_type`。 --- === 构造函数 ==== 默认构造函数 ```c++ unordered_node_map(); ``` 使用 `hasher()` 作为哈希函数，`key_equal()` 作为键相等谓词，`allocator_type()` 作为分配器，构造一个空容器。 [horizontal] 后置条件：`size() == 0` 要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 桶数构造函数 ```c++ explicit unordered_node_map(size_type n, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); ``` 构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`eql` 作为键相等谓词，`a` 作为分配器。 [horizontal] 后置条件：`size() == 0` 要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 迭代器范围构造函数 [source,c++,subs="+quotes"] ---- template unordered_node_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` 作为分配器，并将 `[f, l)` 范围内的元素插入其中。 [horizontal] 要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 复制构造函数 ```c++ unordered_node_map(unordered_node_map const& other); ``` 拷贝构造函数。拷贝所包含的元素、哈希函数、谓词和分配器。 如果 `Allocator::select_on_container_copy_construction` 存在且具有正确的签名，则分配器将根据其结果进行构造。 --- ==== 移动构造函数 ```c++ unordered_node_map(unordered_node_map&& other); ``` 移动构造函数。`other` 的内部桶数组会被直接转移给新容器。哈希函数、谓词和分配器通过移动构造从 `other` 获得。如果启用了统计信息（详见 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`]），则会从 `other` 转移内部的统计信息，并调用 `other.reset_stats()`。 --- ==== 带分配器的迭代器范围构造函数 ```c++ template unordered_node_map(InputIterator f, InputIterator l, const allocator_type& a); ``` 使用 `a` 作为分配器，以默认哈希函数和键相等谓词构造一个空容器，并将 `[f, l)` 范围内的元素插入其中。 [horizontal] 要求：`hasher`、`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 分配器构造函数 ```c++ explicit unordered_node_map(Allocator const& a); ``` 使用分配器 `a` 构造一个空容器。 --- ==== 带分配器的拷贝构造函数 ```c++ unordered_node_map(unordered_node_map const& other, Allocator const& a); ``` 构造一个容器，拷贝 `other` 所包含的元素、哈希函数和谓词，但使用分配器 `a`。 --- ==== 带分配器的移动构造函数 ```c++ unordered_node_map(unordered_node_map&& other, Allocator const& a); ``` 如果 `a == other.get_allocator()`，则 `other` 的元素节点会直接转移给新容器；否则，元素将从 `other` 中的元素通过移动构造获得。哈希函数和谓词通过移动构造从 `other` 获得，而分配器则通过拷贝构造从 `a` 获得。如果启用了统计信息（详见 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`]），则当 `a == other.get_allocator()` 时，会从 `other` 转移内部的统计信息，并且始终会调用 `other.reset_stats()`。 --- ==== 从 `concurrent_node_map` 的移动构造函数 ```c++ unordered_node_map(concurrent_node_map&& other); ``` 从 xref:#concurrent_node_map[`concurrent_node_map`] 进行移动构造。`other` 的内部桶数组直接转移给新容器。哈希函数、谓词和分配器通过移动构造从 `other` 获得。如果启用了统计信息（详见 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`]），则从 `other` 转移内部的统计信息，并调用 `other.reset_stats()`。 [horizontal] 复杂度：常数时间。 并发性：在 `other` 上阻塞。 --- ==== 初始化列表构造函数 [source,c++,subs="+quotes"] ---- unordered_node_map(std::initializer_list 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`，并将 `il` 中的元素插入其中。 [horizontal] 要求：如果使用默认值，则 `hasher`、`key_equal` 和 `allocator_type` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 带分配器的桶数构造函数 ```c++ unordered_node_map(size_type n, allocator_type const& a); ``` 构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，使用默认的哈希函数和键相等谓词，并以 `a` 作为分配器。 [horizontal] 后置条件：`size() == 0` 要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 带哈希函数和分配器的桶数构造函数 ```c++ unordered_node_map(size_type n, hasher const& hf, allocator_type const& a); ``` 构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，使用默认的键相等谓词，并以 `a` 作为分配器。 [horizontal] 后置条件：`size() == 0` 要求：`key_equal` 需满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^] 要求。 --- ==== 带桶数和分配器的迭代器范围构造函数 [source,c++,subs="+quotes"] ---- template unordered_node_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a); ---- 构造一个至少包含 `n` 个桶的空容器，使用 `a` 作为分配器以及默认的哈希函数和键相等谓词，并将 `[f, l)` 范围内的元素插入其中。 [horizontal] 要求：`hasher`、`key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 带桶数和哈希函数的迭代器范围构造函数 [source,c++,subs="+quotes"] ---- template unordered_node_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); ---- 构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`a` 作为分配器，使用默认的键相等谓词，并将 `[f, l)` 范围内的元素插入其中。 [horizontal] 要求;; `key_equal` 需满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造] 要求。 --- ==== 带分配器的初始化列表构造函数 ```c++ unordered_node_map(std::initializer_list il, const allocator_type& a); ``` 使用 `a` 以及默认的哈希函数和键相等谓词构造一个空容器，并将 `il` 中的元素插入其中。 [horizontal] 要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 带桶数和分配器的初始化列表构造函数 ```c++ unordered_node_map(std::initializer_list il, size_type n, const allocator_type& a); ``` 使用 `a` 以及默认的哈希函数和键相等谓词，构造一个至少包含 `n` 个桶的空容器，并将 `il` 中的元素插入其中。 [horizontal] 要求：`hasher` 和 `key_equal` 需要满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^]。 --- ==== 带桶数、哈希函数和分配器的初始化列表构造函数 ```c++ unordered_node_map(std::initializer_list il, size_type n, const hasher& hf, const allocator_type& a); ``` 构造一个至少包含 `n` 个桶的空容器，使用 `hf` 作为哈希函数，`a` 作为分配器，使用默认的键相等谓词，并将 `il` 中的元素插入其中。 [horizontal] 要求;; `key_equal` 需满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造] 要求。 --- === 析构函数 ```c++ ~unordered_node_map(); ``` [horizontal] 注意：析构函数会应用于每个元素，并且所有内存都会被释放。 --- === 赋值操作 ==== 拷贝赋值 ```c++ unordered_node_map& operator=(unordered_node_map const& other); ``` 赋值运算符。销毁之前存在的元素，从 `other` 拷贝赋值哈希函数和谓词，如果 `Alloc::propagate_on_container_copy_assignment` 存在且 `Alloc::propagate_on_container_copy_assignment::value` 为 `true`，则从 `other` 拷贝赋值分配器，最后插入 `other` 中元素的副本。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。 --- ==== 移动赋值 ```c++ unordered_node_map& operator=(unordered_node_map&& other) noexcept((boost::allocator_traits::is_always_equal::value || boost::allocator_traits::propagate_on_container_move_assignment::value) && std::is_same::value); ``` 移动赋值运算符。销毁之前存在的元素，交换来自 `other` 的哈希函数和谓词，并且如果 `Alloc::propagate_on_container_move_assignment` 存在且 `Alloc::propagate_on_container_move_assignment::value` 为 `true`，则从 `other` 移动赋值分配器。如果此时分配器与 `other.get_allocator()` 相等，则 `other` 的内部桶数组直接转移给当前容器；否则，插入从 `other` 元素移动构造而来的副本。如果启用了统计信息（详见 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`]），则当最终分配器与 `other.get_allocator()` 相等时，从 `other` 转移内部的统计信息，并且始终会调用 `other.reset_stats()`。 --- ==== 初始化列表赋值 ```c++ unordered_node_map& operator=(std::initializer_list il); ``` 从初始化列表中的值进行赋值。所有之前存在的元素都会被销毁。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。 === 迭代器 ==== begin ```c++ iterator begin() noexcept; const_iterator begin() const noexcept; ``` [horizontal] 返回：指向容器第一个元素的迭代器，如果容器为空则返回容器的尾后迭代器。 复杂度：O(`bucket_count()`) --- ==== end ```c++ iterator end() noexcept; const_iterator end() const noexcept; ``` [horizontal] 返回：指向容器尾后值的迭代器。 --- ==== cbegin ```c++ const_iterator cbegin() const noexcept; ``` [horizontal] 返回：指向容器第一个元素的 `const_iterator`，如果容器为空则返回容器的尾后值。 复杂度：O(`bucket_count()`) --- ==== cend ```c++ const_iterator cend() const noexcept; ``` [horizontal] 返回：指向容器尾后值的 `const_iterator`。 --- === 大小与容量 ==== 空 ```c++ [[nodiscard]] bool empty() const noexcept; ``` [horizontal] Returns:;; `size() == 0` --- ==== 大小 ```c++ size_type size() const noexcept; ``` [horizontal] Returns:;; `std::distance(begin(), end())` --- ==== max_size ```c++ size_type max_size() const noexcept; ``` [horizontal] 返回：可能的最大容器的 `size()`。 --- === 修改器 ==== 原地构造 ```c++ template std::pair emplace(Args&&... args); ``` 当且仅当容器中没有具有等价键的元素时，才插入一个使用参数 `args` 构造的对象。 [horizontal] 要求：`value_type` 可从 `args` 构造。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 如果 `args...` 的形式为 `k,v`，则该函数会延迟构造整个对象，直到确定应该插入元素为止，仅使用 `k` 参数进行检查。当 `key_type` 可移动构造或 `k` 参数本身就是 `key_type` 类型时，此优化生效。 --- ==== emplace_hint ```c++ template iterator emplace_hint(const_iterator position, Args&&... args); ``` 当且仅当容器中没有具有等价键的元素时，才插入一个使用参数 `args` 构造的对象。 `position` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 要求：`value_type` 可从 `args` 构造。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 如果 `args...` 的形式为 `k,v`，则该函数会延迟构造整个对象，直到确定应该插入元素为止，仅使用 `k` 参数进行检查。当 `key_type` 可移动构造或 `k` 参数本身就是 `key_type` 类型时，此优化生效。 --- ==== 复制插入 ```c++ std::pair insert(const value_type& obj); std::pair insert(const init_type& obj); ``` 当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 形式为 `insert(x)` 的调用，如果 `x` 可以同等转换为 `const value_type&` 和 `const init_type&`，则不会产生歧义，并且会选择 `init_type` 重载。 --- ==== 移动插入 ```c++ std::pair insert(value_type&& obj); std::pair insert(init_type&& obj); ``` 当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/MoveInsertable[可移动插入^]。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 形式为 `insert(x)` 的调用，如果 `x` 可以同等转换为 `value_type&&` 和 `init_type&&`，则不会产生歧义，并且会选择 `init_type` 重载。 --- ==== 带提示的复制插入 ```c++ iterator insert(const_iterator hint, const value_type& obj); iterator insert(const_iterator hint, const init_type& obj); ``` 当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。 `hint` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 形式为 `insert(hint, x)` 的调用，如果 `x` 可以同等转换为 `const value_type&` 和 `const init_type&`，则不会产生歧义，并且会选择 `init_type` 重载。 --- ==== 带提示的移动插入 ```c++ iterator insert(const_iterator hint, value_type&& obj); iterator insert(const_iterator hint, init_type&& obj); ``` 当且仅当容器中没有具有等价键的元素时，才将 `obj` 插入容器。 `hint` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 要求：`value_type` 满足 https://en.cppreference.com/w/cpp/named_req/MoveInsertable[可移动插入^]。 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 形式为 `insert(hint, x)` 的调用，如果 `x` 可以同等转换为 `value_type&&` 和 `init_type&&`，则不会产生歧义，并且会选择 `init_type` 重载。 --- ==== 迭代器范围插入 ```c++ template void insert(InputIterator first, InputIterator last); ``` 将一个范围内的元素插入容器中。当且仅当容器中没有具有等价键的元素时，才会插入这些元素。 [horizontal] 要求：`value_type` 可以从 `*first` 出发在容器中进行 https://en.cppreference.com/w/cpp/named_req/EmplaceConstructible[可原位构造^]。 抛出：当插入单个元素时，如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 --- ==== 初始化列表插入 ```c++ void insert(std::initializer_list); ``` 将一个范围内的元素插入容器中。当且仅当容器中没有具有等价键的元素时，才会插入这些元素。 [horizontal] 要求：`value_type` 可以在容器中进行 https://en.cppreference.com/w/cpp/named_req/CopyInsertable[可拷贝插入^]。 抛出：当插入单个元素时，如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 --- ==== 节点插入 ```c++ insert_return_type insert(node_type&& nh); ``` 如果 `nh` 非空，则当且仅当容器中没有键与 `nh.key()` 等价的元素时，才将关联的元素插入容器。函数返回时 `nh` 变为空。 [horizontal] 返回：一个 `insert_return_type` 对象，由 `position`、`inserted` 和 `node` 构造而成。 * 若 `nh` 为空，则 `inserted` 为 `false` ， `position` 为 `end()` ，且 `node` 为空。 * 否则，若插入操作发生，则 `inserted` 为 `true` ， `position` 指向被插入的元素，且 `node` 为空。 * 若插入操作失败，则 `inserted` 为 `false` ， `node` 保留 `nh` 的原始值，且 `position` 指向与 `nh.key()` 等效的元素。 若 `nh` 非空，则当且仅当容器中不存在键等价于 `nh.key()` 的元素时，插入其关联元素。函数返回时 `nh` 为空。 --- ==== 带提示的节点插入 ```c++ iterator insert(const_iterator hint, node_type&& nh); ``` 如果 `nh` 非空，则当且仅当容器中没有键与 `nh.key()` 等价的元素时，才将关联的元素插入容器。如果插入发生，则 `nh` 变为空；否则 `nh` 不变。 `hint` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 返回：如果 `nh` 为空，则返回的迭代器为 `end()`。如果插入发生，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：如果 `nh` 非空且 `nh` 与容器的分配器不相等，则行为未定义。 --- ==== try_emplace ```c++ template std::pair try_emplace(const key_type& k, Args&&... args); template std::pair try_emplace(key_type&& k, Args&&... args); template std::pair try_emplace(K&& k, Args&&... args); ``` 如果容器中不存在键为 `k` 的元素，则插入一个新元素。 如果已存在键为 `k` 的元素，则该函数不执行任何操作。 [horizontal] 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：此函数类似于 xref:#unordered_node_map_emplace[emplace]，区别在于如果存在具有等价键的元素，则不构造 `value_type`；否则，构造形式为： ```c++ // first two overloads ```c++ value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(args)...)) ``` // third overload value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(args)...)) ``` 与 xref:#unordered_node_map_emplace[emplace] 不同，后者只是将所有参数直接转发给 `value_type` 的构造函数。 可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 `template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 -- --- ==== 带提示的 try_emplace ```c++ template iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); template iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); template iterator try_emplace(const_iterator hint, K&& k, Args&&... args); ``` 如果容器中不存在键为 `k` 的元素，则插入一个新元素。 如果已存在键为 `k` 的元素，则该函数不执行任何操作。 `hint` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：此函数类似于 xref:#unordered_node_map_emplace_hint[emplace_hint]，区别在于如果存在具有等价键的元素，则不构造 `value_type`；否则，构造形式为： ```c++ // first two overloads ```c++ value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(args)...)) ``` // third overload value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(args)...)) ``` 与 xref:#unordered_node_map_emplace_hint[emplace_hint] 不同，后者只是将所有参数直接转发给 `value_type` 的构造函数。 可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 `template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 -- --- ==== insert_or_assign ```c++ template std::pair insert_or_assign(const key_type& k, M&& obj); template std::pair insert_or_assign(key_type&& k, M&& obj); template std::pair insert_or_assign(K&& k, M&& obj); ``` 向容器中插入一个新元素，或通过赋值更新现有元素的值。 如果存在键为 `k` 的元素，则通过赋值 `std::forward(obj)` 来更新它。 如果不存在这样的元素，则将其添加到容器中，形式为： ```c++ // first two overloads value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(obj))) // third overload value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(obj))) ``` [horizontal] 返回：返回类型的 `bool` 分量为 `true` 表示发生了插入。 如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 `template` 仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== 带提示位置的 insert_or_assign ```c++ template iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); template iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); template iterator insert_or_assign(const_iterator hint, K&& k, M&& obj); ``` 向容器中插入一个新元素，或通过赋值更新现有元素的值。 如果存在键为 `k` 的元素，则通过赋值 `std::forward(obj)` 来更新它。 如果不存在这样的元素，则将其添加到容器中，形式为： ```c++ // first two overloads value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(obj))) // third overload value_type(std::piecewise_construct, std::forward_as_tuple(std::forward(k)), std::forward_as_tuple(std::forward(obj))) ``` `hint` 是关于元素插入位置的建议。此实现会忽略该建议。 [horizontal] 返回：如果发生了插入，则迭代器指向新插入的元素；否则，指向具有等价键的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 `template` 仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== 按位置擦除 [source,c++,subs=+quotes] ---- _convertible-to-iterator_ erase(iterator position); _convertible-to-iterator_ erase(const_iterator position); ---- 擦除由 `position` 指向的元素。 [horizontal] 返回：一个不透明对象，可隐式转换为 `position` 在被擦除之前紧后位置的 `iterator` 或 `const_iterator`。 抛出：不抛出任何异常。 注意：返回的不透明对象只能被丢弃或立即转换为 `iterator` 或 `const_iterator`。 --- ==== 通过键擦除 ```c++ size_type erase(const key_type& k); template size_type erase(K&& k); ``` 擦除所有键与 `k` 等价的元素。 [horizontal] 返回：被擦除的元素数量。 抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef，且 `iterator` 和 `const_iterator` 都不能从 `K` 隐式转换时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== 范围擦除 ```c++ iterator erase(const_iterator first, const_iterator last); ``` Erases the elements in the range from `first` to `last`. [horizontal] 返回：被擦除元素之后的迭代器——即 `last`。 抛出：在此实现中不抛出任何异常（既不调用 `hasher` 也不调用 `key_equal` 对象）。 --- ==== 交换 ```c++ void swap(unordered_node_map& other) noexcept(boost::allocator_traits::is_always_equal::value || boost::allocator_traits::propagate_on_container_swap::value); ``` 交换容器的内容与参数的内容。 如果 `Allocator::propagate_on_container_swap` 被声明且 `Allocator::propagate_on_container_swap::value` 为 `true`，则交换容器的分配器。否则，使用不相等的分配器进行交换将导致未定义行为。 [horizontal] 抛出：除非 `key_equal` 或 `hasher` 在交换时抛出异常，否则不抛出任何异常。 --- ==== 通过位置提取 ```c++ node_type extract(const_iterator position); ``` 提取 `position` 所指向的元素。 [horizontal] 返回：一个持有被提取元素的 `node_type` 对象。 抛出：不抛出任何异常。 --- ==== 通过键提取 ```c++ node_type extract(const key_type& k); template node_type extract(K&& k); ``` 提取键与 `k` 等价的元素（如果存在）。 [horizontal] 返回：一个持有被提取元素的 `node_type` 对象；如果未提取到任何元素，则返回空。 抛出：仅当 `hasher` 或 `key_equal` 抛出异常时才会抛出。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== pull ```c++ init_type pull(const_iterator position); ``` 从 `position` 指向的元素移动构造一个 `init_value` 对象 `x`，擦除该元素并返回 `x`。 --- ==== 清空 ```c++ void clear() noexcept; ``` 擦除容器中的所有元素。 [horizontal] 后置条件：`size() == 0`，`max_load() >= max_load_factor() * bucket_count()` --- ==== 合并 ```c++ template void merge(unordered_node_map& source); template void merge(unordered_node_map&& source); ``` 从 `source` 转移所有键在 `*this` 中尚未存在的元素节点。 [horizontal] 要求：`this->get_allocator() == source.get_allocator()`。 注意：会使被转移元素的迭代器失效。如果 `*this` 的结果大小大于其原始最大负载，则会使与 `*this` 关联的所有迭代器失效。 --- === 观察器 ==== get_allocator ``` allocator_type get_allocator() const noexcept; ``` [horizontal] 返回：容器的分配器。 --- ==== 哈希函数 ``` hasher hash_function() const; ``` [horizontal] 返回：容器的哈希函数。 --- ==== key_eq ``` key_equal key_eq() const; ``` [horizontal] 返回：容器的键相等谓词。 --- === 查找 ==== find ```c++ iterator find(const key_type& k); const_iterator find(const key_type& k) const; template iterator find(const K& k); ``` [horizontal] 返回：指向键与 `k` 等价的元素的迭代器；如果不存在这样的元素，则返回 `end()`。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== count ```c++ size_type count(const key_type& k) const; template size_type count(const K& k) const; ``` [horizontal] 返回：键与 `k` 等价的元素数量。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== 包含 ```c++ bool contains(const key_type& k) const; template bool contains(const K& k) const; ``` [horizontal] 返回：一个布尔值，指示容器中是否存在键等于 `key` 的元素。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== equal_range ```c++ std::pair equal_range(const key_type& k); std::pair equal_range(const key_type& k) const; template std::pair equal_range(const K& k); template std::pair equal_range(const K& k) const; ``` [horizontal] 返回：包含所有键与 `k` 等价的元素的范围。如果容器不包含任何此类元素，则返回 `std::make_pair(b.end(), b.end())`。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== operator++[++++]++ ```c++ mapped_type& operator[](const key_type& k); mapped_type& operator[](key_type&& k); template mapped_type& operator[](K&& k); ``` [horizontal] 效果：如果容器中不存在键与 `k` 等价的元素，则插入值 `std::pair(k, mapped_type())`。 返回：对 `x.second` 的引用，其中 `x` 是容器中已存在的元素，或是新插入的键与 `k` 等价的元素。 抛出：如果除调用 `hasher` 之外的操作抛出异常，则该函数无效果。 注意：可能使迭代器失效，但仅当插入导致负载大于最大负载时才会发生。 `template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- ==== at ```c++ mapped_type& at(const key_type& k); const mapped_type& at(const key_type& k) const; template mapped_type& at(const K& k); template const mapped_type& at(const K& k) const; ``` [horizontal] 返回：对 `x.second` 的引用，其中 `x` 是键与 `k` 等价的（唯一）元素。 抛出：如果不存在这样的元素，则抛出 `std::out_of_range` 类型的异常对象。 注意：`template` 重载仅在 `Hash::is_transparent` 和 `Pred::is_transparent` 是有效的成员 typedef 时参与重载决议。库假定 `Hash` 可同时使用 `K` 和 `Key` 调用，且 `Pred` 是透明的。这支持了异构查找，从而避免了实例化 `Key` 类型对象的开销。 --- === 桶接口 ==== bucket_count ```c++ size_type bucket_count() const noexcept; ``` [horizontal] 返回：桶数组的大小。 --- === 哈希策略 ==== 负载因子 ```c++ float load_factor() const noexcept; ``` [horizontal] 返回：`static_cast(size())/static_cast(bucket_count())`，如果 `bucket_count() == 0` 则返回 `0`。 --- ==== max_load_factor ```c++ float max_load_factor() const noexcept; ``` [horizontal] 返回：容器的最大负载因子。 --- ==== 设置最大负载因子 ```c++ void max_load_factor(float z); ``` [horizontal] 效果：不执行任何操作，因为用户不允许更改此参数。保留此函数是为了与 `boost::unordered_map` 保持兼容。 --- ==== max_load ```c++ size_type max_load() const noexcept; ``` [horizontal] 返回：容器在不触发重哈希的情况下能够容纳的最大元素数量（假设不再有元素被擦除）。 注意：在构造、重哈希或清空操作之后，容器的最大负载至少为 `max_load_factor() * bucket_count()`。在高负载条件下，该数值可能会因元素擦除而减小。 --- ==== 重哈希 ```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()))`。 与 `rehash` 类似，此函数可用于增大或缩小容器中的桶数量。 使迭代器失效并改变元素的顺序。 [horizontal] 抛出：如果抛出异常（除非是由容器的哈希函数或比较函数抛出的），则该函数无效果。 --- === 统计信息 ==== get_stats ```c++ stats get_stats() const; ``` [horizontal] 返回：容器迄今为止所执行插入和查找操作的统计描述。 注意：仅在 xref:reference/stats.adoc#stats[统计计算] 通过 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`] 启用时才可用。 --- ==== reset_stats ```c++ void reset_stats() noexcept; ``` [horizontal] 效果：将容器内部维护的统计信息归零。 注意：仅在 xref:reference/stats.adoc#stats[统计计算] 通过 xref:unordered_node_map_boost_unordered_enable_stats[`BOOST_UNORDERED_ENABLE_STATS`] 启用时才可用。 --- === 推导指引 如果以下任何一条件为真，则推导指引将不参与重载决议： - 它具有一个 `InputIterator` 模板参数，并且为该参数推导出的类型不符合输入迭代器的要求。 - 它具有一个 `Allocator` 模板参数，并且为该参数推导出的类型不符合分配器的要求。 - 它具有一个 `Hash` 模板参数，并且为该参数推导出的类型是整数类型或符合分配器的要求。 - 它具有一个 `Pred` 模板参数，并且为该参数推导出的类型符合分配器的要求。 推导指引中的 `size_type` 参数类型指的是由该推导指引所推导出的容器类型的 `size_type` 成员类型。其默认值与所选构造函数的默认值一致。 ==== _iter-value-type_ [listings,subs="+macros,+quotes"] ----- template using __iter-value-type__ = typename std::iterator_traits::value_type; // exposition only ----- ==== __iter-key-type__ [listings,subs="+macros,+quotes"] ----- template using __iter-key-type__ = std::remove_const_t< std::tuple_element_t<0, xref:#unordered_node_map_iter_value_type[__iter-value-type__]>>; // exposition only ----- ==== __iter-mapped-type__ [listings,subs="+macros,+quotes"] ----- template using __iter-mapped-type__ = std::tuple_element_t<1, xref:#unordered_node_map_iter_value_type[__iter-value-type__]>; // exposition only ----- ==== __iter-to-alloc-type__ [listings,subs="+macros,+quotes"] ----- template using __iter-to-alloc-type__ = std::pair< std::add_const_t>>, std::tuple_element_t<1, xref:#unordered_node_map_iter_value_type[__iter-value-type__]>>; // exposition only ----- === 相等性比较 ==== operator ```c++ template bool operator==(const unordered_node_map& x, const unordered_node_map& y); ``` 若 `x.size() == y.size()` 且对于 `x` 中的每个元素，在 `y` 中均存在一个具有相同键且值相等（使用 `operator==` 比较值类型）的元素，则返回 `true`。 [horizontal] 注意：如果两个容器不具有等价的相等谓词，则行为未定义。 --- ==== operator! ```c++ template bool operator!=(const unordered_node_map& x, const unordered_node_map& y); ``` 若 `x.size() == y.size()` 且对于 `x` 中的每个元素，在 `y` 中均存在一个具有相同键且值相等（使用 `operator==` 比较值类型）的元素，则返回 `false`。 [horizontal] 注意：如果两个容器不具有等价的相等谓词，则行为未定义。 === 交换 ```c++ template void swap(unordered_node_map& x, unordered_node_map& y) noexcept(noexcept(x.swap(y))); ``` 交换 `x` 和 `y` 的内容。 如果 `Allocator::propagate_on_container_swap` 被声明且 `Allocator::propagate_on_container_swap::value` 为 `true`，则交换容器的分配器。否则，使用不相等的分配器进行交换将导致未定义行为。 [horizontal] 效果：`x.swap(y)` 抛出：除非 `key_equal` 或 `hasher` 在交换时抛出异常，否则不抛出任何异常。 --- === erase_if ```c++ template typename unordered_node_map::size_type erase_if(unordered_node_map& c, Predicate pred); ``` 遍历容器 `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_node_map` 可以通过本库提供的 API，借助 link:../../../../../serialization/index.html[Boost.Serialization^] 进行归档/恢复。支持常规归档和 XML 归档。 ==== 将 unordered_node_map 保存到归档中 将 `unordered_node_map` `x` 的所有元素保存到归档（XML 归档） `ar` 。 [horizontal] 要求：`std::remove_const::type` 和 `std::remove_const::type` 必须是可序列化的（对于 XML 归档需支持 XML 序列化），并且它们必须支持 Boost.Serialization 的 `save_construct_data`/`load_construct_data` 协议（该协议由满足 https://en.cppreference.com/w/cpp/named_req/DefaultConstructible[可默认构造^] 的类型自动支持）。 --- ==== 从归档中加载 unordered_node_map 删除 `unordered_node_map` 容器 `x` 中所有已存在的元素，并从归档（XML 归档）`ar` 中插入从原始 `unordered_node_map` 容器 `other` 保存到 `ar` 所读取存储中的元素恢复出的副本。 [horizontal] 要求：`key_type` 和 `mapped_type` 必须分别能够从 `std::remove_const::type&&` 和 `std::remove_const::type&&` 构造。`x.key_equal()` 在功能上必须等价于 `other.key_equal()`。 --- ==== 将迭代器/常量迭代器保存到归档 将迭代器（或常量迭代器）`it` 的位置信息保存到归档（XML 归档）`ar` 中。`it` 可以是一个 `end()` 迭代器。 [horizontal] 要求：`it` 所指向的 `unordered_node_map` 容器 `x` 必须先被保存到 `ar` 中，并且在保存 `x` 和保存 `it` 之间，不能对 `x` 执行任何修改操作。 --- ==== 从归档加载迭代器/常量迭代器 使迭代器（或常量迭代器）`it` 指向原始迭代器（或常量迭代器）被保存到归档（XML 归档）`ar` 所读取存储中的位置恢复后的位置。 [horizontal] 要求：如果 `x` 是 `it` 所指向的 `unordered_node_map` 容器，则在加载 `x` 和加载 `it` 之间，不能对 `x` 执行任何修改操作。