138fd1498Szrj // unordered_map implementation -*- C++ -*-
238fd1498Szrj
338fd1498Szrj // Copyright (C) 2010-2018 Free Software Foundation, Inc.
438fd1498Szrj //
538fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free
638fd1498Szrj // software; you can redistribute it and/or modify it under the
738fd1498Szrj // terms of the GNU General Public License as published by the
838fd1498Szrj // Free Software Foundation; either version 3, or (at your option)
938fd1498Szrj // any later version.
1038fd1498Szrj
1138fd1498Szrj // This library is distributed in the hope that it will be useful,
1238fd1498Szrj // but WITHOUT ANY WARRANTY; without even the implied warranty of
1338fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1438fd1498Szrj // GNU General Public License for more details.
1538fd1498Szrj
1638fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional
1738fd1498Szrj // permissions described in the GCC Runtime Library Exception, version
1838fd1498Szrj // 3.1, as published by the Free Software Foundation.
1938fd1498Szrj
2038fd1498Szrj // You should have received a copy of the GNU General Public License and
2138fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program;
2238fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
2338fd1498Szrj // <http://www.gnu.org/licenses/>.
2438fd1498Szrj
2538fd1498Szrj /** @file bits/unordered_map.h
2638fd1498Szrj * This is an internal header file, included by other library headers.
2738fd1498Szrj * Do not attempt to use it directly. @headername{unordered_map}
2838fd1498Szrj */
2938fd1498Szrj
3038fd1498Szrj #ifndef _UNORDERED_MAP_H
3138fd1498Szrj #define _UNORDERED_MAP_H
3238fd1498Szrj
_GLIBCXX_VISIBILITY(default)3338fd1498Szrj namespace std _GLIBCXX_VISIBILITY(default)
3438fd1498Szrj {
3538fd1498Szrj _GLIBCXX_BEGIN_NAMESPACE_VERSION
3638fd1498Szrj _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
3738fd1498Szrj
3838fd1498Szrj /// Base types for unordered_map.
3938fd1498Szrj template<bool _Cache>
4038fd1498Szrj using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
4138fd1498Szrj
4238fd1498Szrj template<typename _Key,
4338fd1498Szrj typename _Tp,
4438fd1498Szrj typename _Hash = hash<_Key>,
4538fd1498Szrj typename _Pred = std::equal_to<_Key>,
4638fd1498Szrj typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
4738fd1498Szrj typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
4838fd1498Szrj using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
4938fd1498Szrj _Alloc, __detail::_Select1st,
5038fd1498Szrj _Pred, _Hash,
5138fd1498Szrj __detail::_Mod_range_hashing,
5238fd1498Szrj __detail::_Default_ranged_hash,
5338fd1498Szrj __detail::_Prime_rehash_policy, _Tr>;
5438fd1498Szrj
5538fd1498Szrj /// Base types for unordered_multimap.
5638fd1498Szrj template<bool _Cache>
5738fd1498Szrj using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
5838fd1498Szrj
5938fd1498Szrj template<typename _Key,
6038fd1498Szrj typename _Tp,
6138fd1498Szrj typename _Hash = hash<_Key>,
6238fd1498Szrj typename _Pred = std::equal_to<_Key>,
6338fd1498Szrj typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
6438fd1498Szrj typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
6538fd1498Szrj using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
6638fd1498Szrj _Alloc, __detail::_Select1st,
6738fd1498Szrj _Pred, _Hash,
6838fd1498Szrj __detail::_Mod_range_hashing,
6938fd1498Szrj __detail::_Default_ranged_hash,
7038fd1498Szrj __detail::_Prime_rehash_policy, _Tr>;
7138fd1498Szrj
7238fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
7338fd1498Szrj class unordered_multimap;
7438fd1498Szrj
7538fd1498Szrj /**
7638fd1498Szrj * @brief A standard container composed of unique keys (containing
7738fd1498Szrj * at most one of each key value) that associates values of another type
7838fd1498Szrj * with the keys.
7938fd1498Szrj *
8038fd1498Szrj * @ingroup unordered_associative_containers
8138fd1498Szrj *
8238fd1498Szrj * @tparam _Key Type of key objects.
8338fd1498Szrj * @tparam _Tp Type of mapped objects.
8438fd1498Szrj * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
8538fd1498Szrj * @tparam _Pred Predicate function object type, defaults
8638fd1498Szrj * to equal_to<_Value>.
8738fd1498Szrj * @tparam _Alloc Allocator type, defaults to
8838fd1498Szrj * std::allocator<std::pair<const _Key, _Tp>>.
8938fd1498Szrj *
9038fd1498Szrj * Meets the requirements of a <a href="tables.html#65">container</a>, and
9138fd1498Szrj * <a href="tables.html#xx">unordered associative container</a>
9238fd1498Szrj *
9338fd1498Szrj * The resulting value type of the container is std::pair<const _Key, _Tp>.
9438fd1498Szrj *
9538fd1498Szrj * Base is _Hashtable, dispatched at compile time via template
9638fd1498Szrj * alias __umap_hashtable.
9738fd1498Szrj */
9838fd1498Szrj template<typename _Key, typename _Tp,
9938fd1498Szrj typename _Hash = hash<_Key>,
10038fd1498Szrj typename _Pred = equal_to<_Key>,
10138fd1498Szrj typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
10238fd1498Szrj class unordered_map
10338fd1498Szrj {
10438fd1498Szrj typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
10538fd1498Szrj _Hashtable _M_h;
10638fd1498Szrj
10738fd1498Szrj public:
10838fd1498Szrj // typedefs:
10938fd1498Szrj //@{
11038fd1498Szrj /// Public typedefs.
11138fd1498Szrj typedef typename _Hashtable::key_type key_type;
11238fd1498Szrj typedef typename _Hashtable::value_type value_type;
11338fd1498Szrj typedef typename _Hashtable::mapped_type mapped_type;
11438fd1498Szrj typedef typename _Hashtable::hasher hasher;
11538fd1498Szrj typedef typename _Hashtable::key_equal key_equal;
11638fd1498Szrj typedef typename _Hashtable::allocator_type allocator_type;
11738fd1498Szrj //@}
11838fd1498Szrj
11938fd1498Szrj //@{
12038fd1498Szrj /// Iterator-related typedefs.
12138fd1498Szrj typedef typename _Hashtable::pointer pointer;
12238fd1498Szrj typedef typename _Hashtable::const_pointer const_pointer;
12338fd1498Szrj typedef typename _Hashtable::reference reference;
12438fd1498Szrj typedef typename _Hashtable::const_reference const_reference;
12538fd1498Szrj typedef typename _Hashtable::iterator iterator;
12638fd1498Szrj typedef typename _Hashtable::const_iterator const_iterator;
12738fd1498Szrj typedef typename _Hashtable::local_iterator local_iterator;
12838fd1498Szrj typedef typename _Hashtable::const_local_iterator const_local_iterator;
12938fd1498Szrj typedef typename _Hashtable::size_type size_type;
13038fd1498Szrj typedef typename _Hashtable::difference_type difference_type;
13138fd1498Szrj //@}
13238fd1498Szrj
13338fd1498Szrj #if __cplusplus > 201402L
13438fd1498Szrj using node_type = typename _Hashtable::node_type;
13538fd1498Szrj using insert_return_type = typename _Hashtable::insert_return_type;
13638fd1498Szrj #endif
13738fd1498Szrj
13838fd1498Szrj //construct/destroy/copy
13938fd1498Szrj
14038fd1498Szrj /// Default constructor.
14138fd1498Szrj unordered_map() = default;
14238fd1498Szrj
14338fd1498Szrj /**
14438fd1498Szrj * @brief Default constructor creates no elements.
14538fd1498Szrj * @param __n Minimal initial number of buckets.
14638fd1498Szrj * @param __hf A hash functor.
14738fd1498Szrj * @param __eql A key equality functor.
14838fd1498Szrj * @param __a An allocator object.
14938fd1498Szrj */
15038fd1498Szrj explicit
15138fd1498Szrj unordered_map(size_type __n,
15238fd1498Szrj const hasher& __hf = hasher(),
15338fd1498Szrj const key_equal& __eql = key_equal(),
15438fd1498Szrj const allocator_type& __a = allocator_type())
15538fd1498Szrj : _M_h(__n, __hf, __eql, __a)
15638fd1498Szrj { }
15738fd1498Szrj
15838fd1498Szrj /**
15938fd1498Szrj * @brief Builds an %unordered_map from a range.
16038fd1498Szrj * @param __first An input iterator.
16138fd1498Szrj * @param __last An input iterator.
16238fd1498Szrj * @param __n Minimal initial number of buckets.
16338fd1498Szrj * @param __hf A hash functor.
16438fd1498Szrj * @param __eql A key equality functor.
16538fd1498Szrj * @param __a An allocator object.
16638fd1498Szrj *
16738fd1498Szrj * Create an %unordered_map consisting of copies of the elements from
16838fd1498Szrj * [__first,__last). This is linear in N (where N is
16938fd1498Szrj * distance(__first,__last)).
17038fd1498Szrj */
17138fd1498Szrj template<typename _InputIterator>
17238fd1498Szrj unordered_map(_InputIterator __first, _InputIterator __last,
17338fd1498Szrj size_type __n = 0,
17438fd1498Szrj const hasher& __hf = hasher(),
17538fd1498Szrj const key_equal& __eql = key_equal(),
17638fd1498Szrj const allocator_type& __a = allocator_type())
17738fd1498Szrj : _M_h(__first, __last, __n, __hf, __eql, __a)
17838fd1498Szrj { }
17938fd1498Szrj
18038fd1498Szrj /// Copy constructor.
18138fd1498Szrj unordered_map(const unordered_map&) = default;
18238fd1498Szrj
18338fd1498Szrj /// Move constructor.
18438fd1498Szrj unordered_map(unordered_map&&) = default;
18538fd1498Szrj
18638fd1498Szrj /**
18738fd1498Szrj * @brief Creates an %unordered_map with no elements.
18838fd1498Szrj * @param __a An allocator object.
18938fd1498Szrj */
19038fd1498Szrj explicit
19138fd1498Szrj unordered_map(const allocator_type& __a)
19238fd1498Szrj : _M_h(__a)
19338fd1498Szrj { }
19438fd1498Szrj
19538fd1498Szrj /*
19638fd1498Szrj * @brief Copy constructor with allocator argument.
19738fd1498Szrj * @param __uset Input %unordered_map to copy.
19838fd1498Szrj * @param __a An allocator object.
19938fd1498Szrj */
20038fd1498Szrj unordered_map(const unordered_map& __umap,
20138fd1498Szrj const allocator_type& __a)
20238fd1498Szrj : _M_h(__umap._M_h, __a)
20338fd1498Szrj { }
20438fd1498Szrj
20538fd1498Szrj /*
20638fd1498Szrj * @brief Move constructor with allocator argument.
20738fd1498Szrj * @param __uset Input %unordered_map to move.
20838fd1498Szrj * @param __a An allocator object.
20938fd1498Szrj */
21038fd1498Szrj unordered_map(unordered_map&& __umap,
21138fd1498Szrj const allocator_type& __a)
21238fd1498Szrj : _M_h(std::move(__umap._M_h), __a)
21338fd1498Szrj { }
21438fd1498Szrj
21538fd1498Szrj /**
21638fd1498Szrj * @brief Builds an %unordered_map from an initializer_list.
21738fd1498Szrj * @param __l An initializer_list.
21838fd1498Szrj * @param __n Minimal initial number of buckets.
21938fd1498Szrj * @param __hf A hash functor.
22038fd1498Szrj * @param __eql A key equality functor.
22138fd1498Szrj * @param __a An allocator object.
22238fd1498Szrj *
22338fd1498Szrj * Create an %unordered_map consisting of copies of the elements in the
22438fd1498Szrj * list. This is linear in N (where N is @a __l.size()).
22538fd1498Szrj */
22638fd1498Szrj unordered_map(initializer_list<value_type> __l,
22738fd1498Szrj size_type __n = 0,
22838fd1498Szrj const hasher& __hf = hasher(),
22938fd1498Szrj const key_equal& __eql = key_equal(),
23038fd1498Szrj const allocator_type& __a = allocator_type())
23138fd1498Szrj : _M_h(__l, __n, __hf, __eql, __a)
23238fd1498Szrj { }
23338fd1498Szrj
23438fd1498Szrj unordered_map(size_type __n, const allocator_type& __a)
23538fd1498Szrj : unordered_map(__n, hasher(), key_equal(), __a)
23638fd1498Szrj { }
23738fd1498Szrj
23838fd1498Szrj unordered_map(size_type __n, const hasher& __hf,
23938fd1498Szrj const allocator_type& __a)
24038fd1498Szrj : unordered_map(__n, __hf, key_equal(), __a)
24138fd1498Szrj { }
24238fd1498Szrj
24338fd1498Szrj template<typename _InputIterator>
24438fd1498Szrj unordered_map(_InputIterator __first, _InputIterator __last,
24538fd1498Szrj size_type __n,
24638fd1498Szrj const allocator_type& __a)
24738fd1498Szrj : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
24838fd1498Szrj { }
24938fd1498Szrj
25038fd1498Szrj template<typename _InputIterator>
25138fd1498Szrj unordered_map(_InputIterator __first, _InputIterator __last,
25238fd1498Szrj size_type __n, const hasher& __hf,
25338fd1498Szrj const allocator_type& __a)
25438fd1498Szrj : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
25538fd1498Szrj { }
25638fd1498Szrj
25738fd1498Szrj unordered_map(initializer_list<value_type> __l,
25838fd1498Szrj size_type __n,
25938fd1498Szrj const allocator_type& __a)
26038fd1498Szrj : unordered_map(__l, __n, hasher(), key_equal(), __a)
26138fd1498Szrj { }
26238fd1498Szrj
26338fd1498Szrj unordered_map(initializer_list<value_type> __l,
26438fd1498Szrj size_type __n, const hasher& __hf,
26538fd1498Szrj const allocator_type& __a)
26638fd1498Szrj : unordered_map(__l, __n, __hf, key_equal(), __a)
26738fd1498Szrj { }
26838fd1498Szrj
26938fd1498Szrj /// Copy assignment operator.
27038fd1498Szrj unordered_map&
27138fd1498Szrj operator=(const unordered_map&) = default;
27238fd1498Szrj
27338fd1498Szrj /// Move assignment operator.
27438fd1498Szrj unordered_map&
27538fd1498Szrj operator=(unordered_map&&) = default;
27638fd1498Szrj
27738fd1498Szrj /**
27838fd1498Szrj * @brief %Unordered_map list assignment operator.
27938fd1498Szrj * @param __l An initializer_list.
28038fd1498Szrj *
28138fd1498Szrj * This function fills an %unordered_map with copies of the elements in
28238fd1498Szrj * the initializer list @a __l.
28338fd1498Szrj *
28438fd1498Szrj * Note that the assignment completely changes the %unordered_map and
28538fd1498Szrj * that the resulting %unordered_map's size is the same as the number
28638fd1498Szrj * of elements assigned.
28738fd1498Szrj */
28838fd1498Szrj unordered_map&
28938fd1498Szrj operator=(initializer_list<value_type> __l)
29038fd1498Szrj {
29138fd1498Szrj _M_h = __l;
29238fd1498Szrj return *this;
29338fd1498Szrj }
29438fd1498Szrj
29538fd1498Szrj /// Returns the allocator object used by the %unordered_map.
29638fd1498Szrj allocator_type
29738fd1498Szrj get_allocator() const noexcept
29838fd1498Szrj { return _M_h.get_allocator(); }
29938fd1498Szrj
30038fd1498Szrj // size and capacity:
30138fd1498Szrj
30238fd1498Szrj /// Returns true if the %unordered_map is empty.
30338fd1498Szrj bool
30438fd1498Szrj empty() const noexcept
30538fd1498Szrj { return _M_h.empty(); }
30638fd1498Szrj
30738fd1498Szrj /// Returns the size of the %unordered_map.
30838fd1498Szrj size_type
30938fd1498Szrj size() const noexcept
31038fd1498Szrj { return _M_h.size(); }
31138fd1498Szrj
31238fd1498Szrj /// Returns the maximum size of the %unordered_map.
31338fd1498Szrj size_type
31438fd1498Szrj max_size() const noexcept
31538fd1498Szrj { return _M_h.max_size(); }
31638fd1498Szrj
31738fd1498Szrj // iterators.
31838fd1498Szrj
31938fd1498Szrj /**
32038fd1498Szrj * Returns a read/write iterator that points to the first element in the
32138fd1498Szrj * %unordered_map.
32238fd1498Szrj */
32338fd1498Szrj iterator
32438fd1498Szrj begin() noexcept
32538fd1498Szrj { return _M_h.begin(); }
32638fd1498Szrj
32738fd1498Szrj //@{
32838fd1498Szrj /**
32938fd1498Szrj * Returns a read-only (constant) iterator that points to the first
33038fd1498Szrj * element in the %unordered_map.
33138fd1498Szrj */
33238fd1498Szrj const_iterator
33338fd1498Szrj begin() const noexcept
33438fd1498Szrj { return _M_h.begin(); }
33538fd1498Szrj
33638fd1498Szrj const_iterator
33738fd1498Szrj cbegin() const noexcept
33838fd1498Szrj { return _M_h.begin(); }
33938fd1498Szrj //@}
34038fd1498Szrj
34138fd1498Szrj /**
34238fd1498Szrj * Returns a read/write iterator that points one past the last element in
34338fd1498Szrj * the %unordered_map.
34438fd1498Szrj */
34538fd1498Szrj iterator
34638fd1498Szrj end() noexcept
34738fd1498Szrj { return _M_h.end(); }
34838fd1498Szrj
34938fd1498Szrj //@{
35038fd1498Szrj /**
35138fd1498Szrj * Returns a read-only (constant) iterator that points one past the last
35238fd1498Szrj * element in the %unordered_map.
35338fd1498Szrj */
35438fd1498Szrj const_iterator
35538fd1498Szrj end() const noexcept
35638fd1498Szrj { return _M_h.end(); }
35738fd1498Szrj
35838fd1498Szrj const_iterator
35938fd1498Szrj cend() const noexcept
36038fd1498Szrj { return _M_h.end(); }
36138fd1498Szrj //@}
36238fd1498Szrj
36338fd1498Szrj // modifiers.
36438fd1498Szrj
36538fd1498Szrj /**
36638fd1498Szrj * @brief Attempts to build and insert a std::pair into the
36738fd1498Szrj * %unordered_map.
36838fd1498Szrj *
36938fd1498Szrj * @param __args Arguments used to generate a new pair instance (see
37038fd1498Szrj * std::piecewise_contruct for passing arguments to each
37138fd1498Szrj * part of the pair constructor).
37238fd1498Szrj *
37338fd1498Szrj * @return A pair, of which the first element is an iterator that points
37438fd1498Szrj * to the possibly inserted pair, and the second is a bool that
37538fd1498Szrj * is true if the pair was actually inserted.
37638fd1498Szrj *
37738fd1498Szrj * This function attempts to build and insert a (key, value) %pair into
37838fd1498Szrj * the %unordered_map.
37938fd1498Szrj * An %unordered_map relies on unique keys and thus a %pair is only
38038fd1498Szrj * inserted if its first element (the key) is not already present in the
38138fd1498Szrj * %unordered_map.
38238fd1498Szrj *
38338fd1498Szrj * Insertion requires amortized constant time.
38438fd1498Szrj */
38538fd1498Szrj template<typename... _Args>
38638fd1498Szrj std::pair<iterator, bool>
38738fd1498Szrj emplace(_Args&&... __args)
38838fd1498Szrj { return _M_h.emplace(std::forward<_Args>(__args)...); }
38938fd1498Szrj
39038fd1498Szrj /**
39138fd1498Szrj * @brief Attempts to build and insert a std::pair into the
39238fd1498Szrj * %unordered_map.
39338fd1498Szrj *
39438fd1498Szrj * @param __pos An iterator that serves as a hint as to where the pair
39538fd1498Szrj * should be inserted.
39638fd1498Szrj * @param __args Arguments used to generate a new pair instance (see
39738fd1498Szrj * std::piecewise_contruct for passing arguments to each
39838fd1498Szrj * part of the pair constructor).
39938fd1498Szrj * @return An iterator that points to the element with key of the
40038fd1498Szrj * std::pair built from @a __args (may or may not be that
40138fd1498Szrj * std::pair).
40238fd1498Szrj *
40338fd1498Szrj * This function is not concerned about whether the insertion took place,
40438fd1498Szrj * and thus does not return a boolean like the single-argument emplace()
40538fd1498Szrj * does.
40638fd1498Szrj * Note that the first parameter is only a hint and can potentially
40738fd1498Szrj * improve the performance of the insertion process. A bad hint would
40838fd1498Szrj * cause no gains in efficiency.
40938fd1498Szrj *
41038fd1498Szrj * See
41138fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
41238fd1498Szrj * for more on @a hinting.
41338fd1498Szrj *
41438fd1498Szrj * Insertion requires amortized constant time.
41538fd1498Szrj */
41638fd1498Szrj template<typename... _Args>
41738fd1498Szrj iterator
41838fd1498Szrj emplace_hint(const_iterator __pos, _Args&&... __args)
41938fd1498Szrj { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
42038fd1498Szrj
42138fd1498Szrj #if __cplusplus > 201402L
42238fd1498Szrj /// Extract a node.
42338fd1498Szrj node_type
42438fd1498Szrj extract(const_iterator __pos)
42538fd1498Szrj {
42638fd1498Szrj __glibcxx_assert(__pos != end());
42738fd1498Szrj return _M_h.extract(__pos);
42838fd1498Szrj }
42938fd1498Szrj
43038fd1498Szrj /// Extract a node.
43138fd1498Szrj node_type
43238fd1498Szrj extract(const key_type& __key)
43338fd1498Szrj { return _M_h.extract(__key); }
43438fd1498Szrj
43538fd1498Szrj /// Re-insert an extracted node.
43638fd1498Szrj insert_return_type
43738fd1498Szrj insert(node_type&& __nh)
43838fd1498Szrj { return _M_h._M_reinsert_node(std::move(__nh)); }
43938fd1498Szrj
44038fd1498Szrj /// Re-insert an extracted node.
44138fd1498Szrj iterator
44238fd1498Szrj insert(const_iterator, node_type&& __nh)
44338fd1498Szrj { return _M_h._M_reinsert_node(std::move(__nh)).position; }
44438fd1498Szrj
44538fd1498Szrj #define __cpp_lib_unordered_map_try_emplace 201411
44638fd1498Szrj /**
44738fd1498Szrj * @brief Attempts to build and insert a std::pair into the
44838fd1498Szrj * %unordered_map.
44938fd1498Szrj *
45038fd1498Szrj * @param __k Key to use for finding a possibly existing pair in
45138fd1498Szrj * the unordered_map.
45238fd1498Szrj * @param __args Arguments used to generate the .second for a
45338fd1498Szrj * new pair instance.
45438fd1498Szrj *
45538fd1498Szrj * @return A pair, of which the first element is an iterator that points
45638fd1498Szrj * to the possibly inserted pair, and the second is a bool that
45738fd1498Szrj * is true if the pair was actually inserted.
45838fd1498Szrj *
45938fd1498Szrj * This function attempts to build and insert a (key, value) %pair into
46038fd1498Szrj * the %unordered_map.
46138fd1498Szrj * An %unordered_map relies on unique keys and thus a %pair is only
46238fd1498Szrj * inserted if its first element (the key) is not already present in the
46338fd1498Szrj * %unordered_map.
46438fd1498Szrj * If a %pair is not inserted, this function has no effect.
46538fd1498Szrj *
46638fd1498Szrj * Insertion requires amortized constant time.
46738fd1498Szrj */
46838fd1498Szrj template <typename... _Args>
46938fd1498Szrj pair<iterator, bool>
47038fd1498Szrj try_emplace(const key_type& __k, _Args&&... __args)
47138fd1498Szrj {
47238fd1498Szrj iterator __i = find(__k);
47338fd1498Szrj if (__i == end())
47438fd1498Szrj {
47538fd1498Szrj __i = emplace(std::piecewise_construct,
47638fd1498Szrj std::forward_as_tuple(__k),
47738fd1498Szrj std::forward_as_tuple(
47838fd1498Szrj std::forward<_Args>(__args)...))
47938fd1498Szrj .first;
48038fd1498Szrj return {__i, true};
48138fd1498Szrj }
48238fd1498Szrj return {__i, false};
48338fd1498Szrj }
48438fd1498Szrj
48538fd1498Szrj // move-capable overload
48638fd1498Szrj template <typename... _Args>
48738fd1498Szrj pair<iterator, bool>
48838fd1498Szrj try_emplace(key_type&& __k, _Args&&... __args)
48938fd1498Szrj {
49038fd1498Szrj iterator __i = find(__k);
49138fd1498Szrj if (__i == end())
49238fd1498Szrj {
49338fd1498Szrj __i = emplace(std::piecewise_construct,
49438fd1498Szrj std::forward_as_tuple(std::move(__k)),
49538fd1498Szrj std::forward_as_tuple(
49638fd1498Szrj std::forward<_Args>(__args)...))
49738fd1498Szrj .first;
49838fd1498Szrj return {__i, true};
49938fd1498Szrj }
50038fd1498Szrj return {__i, false};
50138fd1498Szrj }
50238fd1498Szrj
50338fd1498Szrj /**
50438fd1498Szrj * @brief Attempts to build and insert a std::pair into the
50538fd1498Szrj * %unordered_map.
50638fd1498Szrj *
50738fd1498Szrj * @param __hint An iterator that serves as a hint as to where the pair
50838fd1498Szrj * should be inserted.
50938fd1498Szrj * @param __k Key to use for finding a possibly existing pair in
51038fd1498Szrj * the unordered_map.
51138fd1498Szrj * @param __args Arguments used to generate the .second for a
51238fd1498Szrj * new pair instance.
51338fd1498Szrj * @return An iterator that points to the element with key of the
51438fd1498Szrj * std::pair built from @a __args (may or may not be that
51538fd1498Szrj * std::pair).
51638fd1498Szrj *
51738fd1498Szrj * This function is not concerned about whether the insertion took place,
51838fd1498Szrj * and thus does not return a boolean like the single-argument emplace()
51938fd1498Szrj * does. However, if insertion did not take place,
52038fd1498Szrj * this function has no effect.
52138fd1498Szrj * Note that the first parameter is only a hint and can potentially
52238fd1498Szrj * improve the performance of the insertion process. A bad hint would
52338fd1498Szrj * cause no gains in efficiency.
52438fd1498Szrj *
52538fd1498Szrj * See
52638fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
52738fd1498Szrj * for more on @a hinting.
52838fd1498Szrj *
52938fd1498Szrj * Insertion requires amortized constant time.
53038fd1498Szrj */
53138fd1498Szrj template <typename... _Args>
53238fd1498Szrj iterator
53338fd1498Szrj try_emplace(const_iterator __hint, const key_type& __k,
53438fd1498Szrj _Args&&... __args)
53538fd1498Szrj {
53638fd1498Szrj iterator __i = find(__k);
53738fd1498Szrj if (__i == end())
53838fd1498Szrj __i = emplace_hint(__hint, std::piecewise_construct,
53938fd1498Szrj std::forward_as_tuple(__k),
54038fd1498Szrj std::forward_as_tuple(
54138fd1498Szrj std::forward<_Args>(__args)...));
54238fd1498Szrj return __i;
54338fd1498Szrj }
54438fd1498Szrj
54538fd1498Szrj // move-capable overload
54638fd1498Szrj template <typename... _Args>
54738fd1498Szrj iterator
54838fd1498Szrj try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
54938fd1498Szrj {
55038fd1498Szrj iterator __i = find(__k);
55138fd1498Szrj if (__i == end())
55238fd1498Szrj __i = emplace_hint(__hint, std::piecewise_construct,
55338fd1498Szrj std::forward_as_tuple(std::move(__k)),
55438fd1498Szrj std::forward_as_tuple(
55538fd1498Szrj std::forward<_Args>(__args)...));
55638fd1498Szrj return __i;
55738fd1498Szrj }
55838fd1498Szrj #endif // C++17
55938fd1498Szrj
56038fd1498Szrj //@{
56138fd1498Szrj /**
56238fd1498Szrj * @brief Attempts to insert a std::pair into the %unordered_map.
56338fd1498Szrj
56438fd1498Szrj * @param __x Pair to be inserted (see std::make_pair for easy
56538fd1498Szrj * creation of pairs).
56638fd1498Szrj *
56738fd1498Szrj * @return A pair, of which the first element is an iterator that
56838fd1498Szrj * points to the possibly inserted pair, and the second is
56938fd1498Szrj * a bool that is true if the pair was actually inserted.
57038fd1498Szrj *
57138fd1498Szrj * This function attempts to insert a (key, value) %pair into the
57238fd1498Szrj * %unordered_map. An %unordered_map relies on unique keys and thus a
57338fd1498Szrj * %pair is only inserted if its first element (the key) is not already
57438fd1498Szrj * present in the %unordered_map.
57538fd1498Szrj *
57638fd1498Szrj * Insertion requires amortized constant time.
57738fd1498Szrj */
57838fd1498Szrj std::pair<iterator, bool>
57938fd1498Szrj insert(const value_type& __x)
58038fd1498Szrj { return _M_h.insert(__x); }
58138fd1498Szrj
58238fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
58338fd1498Szrj // 2354. Unnecessary copying when inserting into maps with braced-init
58438fd1498Szrj std::pair<iterator, bool>
58538fd1498Szrj insert(value_type&& __x)
58638fd1498Szrj { return _M_h.insert(std::move(__x)); }
58738fd1498Szrj
588*58e805e6Szrj template<typename _Pair>
589*58e805e6Szrj __enable_if_t<is_constructible<value_type, _Pair&&>::value,
590*58e805e6Szrj pair<iterator, bool>>
59138fd1498Szrj insert(_Pair&& __x)
592*58e805e6Szrj { return _M_h.emplace(std::forward<_Pair>(__x)); }
59338fd1498Szrj //@}
59438fd1498Szrj
59538fd1498Szrj //@{
59638fd1498Szrj /**
59738fd1498Szrj * @brief Attempts to insert a std::pair into the %unordered_map.
59838fd1498Szrj * @param __hint An iterator that serves as a hint as to where the
59938fd1498Szrj * pair should be inserted.
60038fd1498Szrj * @param __x Pair to be inserted (see std::make_pair for easy creation
60138fd1498Szrj * of pairs).
60238fd1498Szrj * @return An iterator that points to the element with key of
60338fd1498Szrj * @a __x (may or may not be the %pair passed in).
60438fd1498Szrj *
60538fd1498Szrj * This function is not concerned about whether the insertion took place,
60638fd1498Szrj * and thus does not return a boolean like the single-argument insert()
60738fd1498Szrj * does. Note that the first parameter is only a hint and can
60838fd1498Szrj * potentially improve the performance of the insertion process. A bad
60938fd1498Szrj * hint would cause no gains in efficiency.
61038fd1498Szrj *
61138fd1498Szrj * See
61238fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
61338fd1498Szrj * for more on @a hinting.
61438fd1498Szrj *
61538fd1498Szrj * Insertion requires amortized constant time.
61638fd1498Szrj */
61738fd1498Szrj iterator
61838fd1498Szrj insert(const_iterator __hint, const value_type& __x)
61938fd1498Szrj { return _M_h.insert(__hint, __x); }
62038fd1498Szrj
62138fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
62238fd1498Szrj // 2354. Unnecessary copying when inserting into maps with braced-init
62338fd1498Szrj iterator
62438fd1498Szrj insert(const_iterator __hint, value_type&& __x)
62538fd1498Szrj { return _M_h.insert(__hint, std::move(__x)); }
62638fd1498Szrj
627*58e805e6Szrj template<typename _Pair>
628*58e805e6Szrj __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
62938fd1498Szrj insert(const_iterator __hint, _Pair&& __x)
630*58e805e6Szrj { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
63138fd1498Szrj //@}
63238fd1498Szrj
63338fd1498Szrj /**
63438fd1498Szrj * @brief A template function that attempts to insert a range of
63538fd1498Szrj * elements.
63638fd1498Szrj * @param __first Iterator pointing to the start of the range to be
63738fd1498Szrj * inserted.
63838fd1498Szrj * @param __last Iterator pointing to the end of the range.
63938fd1498Szrj *
64038fd1498Szrj * Complexity similar to that of the range constructor.
64138fd1498Szrj */
64238fd1498Szrj template<typename _InputIterator>
64338fd1498Szrj void
64438fd1498Szrj insert(_InputIterator __first, _InputIterator __last)
64538fd1498Szrj { _M_h.insert(__first, __last); }
64638fd1498Szrj
64738fd1498Szrj /**
64838fd1498Szrj * @brief Attempts to insert a list of elements into the %unordered_map.
64938fd1498Szrj * @param __l A std::initializer_list<value_type> of elements
65038fd1498Szrj * to be inserted.
65138fd1498Szrj *
65238fd1498Szrj * Complexity similar to that of the range constructor.
65338fd1498Szrj */
65438fd1498Szrj void
65538fd1498Szrj insert(initializer_list<value_type> __l)
65638fd1498Szrj { _M_h.insert(__l); }
65738fd1498Szrj
65838fd1498Szrj
65938fd1498Szrj #if __cplusplus > 201402L
66038fd1498Szrj #define __cpp_lib_unordered_map_insertion 201411
66138fd1498Szrj /**
66238fd1498Szrj * @brief Attempts to insert a std::pair into the %unordered_map.
66338fd1498Szrj * @param __k Key to use for finding a possibly existing pair in
66438fd1498Szrj * the map.
66538fd1498Szrj * @param __obj Argument used to generate the .second for a pair
66638fd1498Szrj * instance.
66738fd1498Szrj *
66838fd1498Szrj * @return A pair, of which the first element is an iterator that
66938fd1498Szrj * points to the possibly inserted pair, and the second is
67038fd1498Szrj * a bool that is true if the pair was actually inserted.
67138fd1498Szrj *
67238fd1498Szrj * This function attempts to insert a (key, value) %pair into the
67338fd1498Szrj * %unordered_map. An %unordered_map relies on unique keys and thus a
67438fd1498Szrj * %pair is only inserted if its first element (the key) is not already
67538fd1498Szrj * present in the %unordered_map.
67638fd1498Szrj * If the %pair was already in the %unordered_map, the .second of
67738fd1498Szrj * the %pair is assigned from __obj.
67838fd1498Szrj *
67938fd1498Szrj * Insertion requires amortized constant time.
68038fd1498Szrj */
68138fd1498Szrj template <typename _Obj>
68238fd1498Szrj pair<iterator, bool>
68338fd1498Szrj insert_or_assign(const key_type& __k, _Obj&& __obj)
68438fd1498Szrj {
68538fd1498Szrj iterator __i = find(__k);
68638fd1498Szrj if (__i == end())
68738fd1498Szrj {
68838fd1498Szrj __i = emplace(std::piecewise_construct,
68938fd1498Szrj std::forward_as_tuple(__k),
69038fd1498Szrj std::forward_as_tuple(std::forward<_Obj>(__obj)))
69138fd1498Szrj .first;
69238fd1498Szrj return {__i, true};
69338fd1498Szrj }
69438fd1498Szrj (*__i).second = std::forward<_Obj>(__obj);
69538fd1498Szrj return {__i, false};
69638fd1498Szrj }
69738fd1498Szrj
69838fd1498Szrj // move-capable overload
69938fd1498Szrj template <typename _Obj>
70038fd1498Szrj pair<iterator, bool>
70138fd1498Szrj insert_or_assign(key_type&& __k, _Obj&& __obj)
70238fd1498Szrj {
70338fd1498Szrj iterator __i = find(__k);
70438fd1498Szrj if (__i == end())
70538fd1498Szrj {
70638fd1498Szrj __i = emplace(std::piecewise_construct,
70738fd1498Szrj std::forward_as_tuple(std::move(__k)),
70838fd1498Szrj std::forward_as_tuple(std::forward<_Obj>(__obj)))
70938fd1498Szrj .first;
71038fd1498Szrj return {__i, true};
71138fd1498Szrj }
71238fd1498Szrj (*__i).second = std::forward<_Obj>(__obj);
71338fd1498Szrj return {__i, false};
71438fd1498Szrj }
71538fd1498Szrj
71638fd1498Szrj /**
71738fd1498Szrj * @brief Attempts to insert a std::pair into the %unordered_map.
71838fd1498Szrj * @param __hint An iterator that serves as a hint as to where the
71938fd1498Szrj * pair should be inserted.
72038fd1498Szrj * @param __k Key to use for finding a possibly existing pair in
72138fd1498Szrj * the unordered_map.
72238fd1498Szrj * @param __obj Argument used to generate the .second for a pair
72338fd1498Szrj * instance.
72438fd1498Szrj * @return An iterator that points to the element with key of
72538fd1498Szrj * @a __x (may or may not be the %pair passed in).
72638fd1498Szrj *
72738fd1498Szrj * This function is not concerned about whether the insertion took place,
72838fd1498Szrj * and thus does not return a boolean like the single-argument insert()
72938fd1498Szrj * does.
73038fd1498Szrj * If the %pair was already in the %unordered map, the .second of
73138fd1498Szrj * the %pair is assigned from __obj.
73238fd1498Szrj * Note that the first parameter is only a hint and can
73338fd1498Szrj * potentially improve the performance of the insertion process. A bad
73438fd1498Szrj * hint would cause no gains in efficiency.
73538fd1498Szrj *
73638fd1498Szrj * See
73738fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
73838fd1498Szrj * for more on @a hinting.
73938fd1498Szrj *
74038fd1498Szrj * Insertion requires amortized constant time.
74138fd1498Szrj */
74238fd1498Szrj template <typename _Obj>
74338fd1498Szrj iterator
74438fd1498Szrj insert_or_assign(const_iterator __hint, const key_type& __k,
74538fd1498Szrj _Obj&& __obj)
74638fd1498Szrj {
74738fd1498Szrj iterator __i = find(__k);
74838fd1498Szrj if (__i == end())
74938fd1498Szrj {
75038fd1498Szrj return emplace_hint(__hint, std::piecewise_construct,
75138fd1498Szrj std::forward_as_tuple(__k),
75238fd1498Szrj std::forward_as_tuple(
75338fd1498Szrj std::forward<_Obj>(__obj)));
75438fd1498Szrj }
75538fd1498Szrj (*__i).second = std::forward<_Obj>(__obj);
75638fd1498Szrj return __i;
75738fd1498Szrj }
75838fd1498Szrj
75938fd1498Szrj // move-capable overload
76038fd1498Szrj template <typename _Obj>
76138fd1498Szrj iterator
76238fd1498Szrj insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
76338fd1498Szrj {
76438fd1498Szrj iterator __i = find(__k);
76538fd1498Szrj if (__i == end())
76638fd1498Szrj {
76738fd1498Szrj return emplace_hint(__hint, std::piecewise_construct,
76838fd1498Szrj std::forward_as_tuple(std::move(__k)),
76938fd1498Szrj std::forward_as_tuple(
77038fd1498Szrj std::forward<_Obj>(__obj)));
77138fd1498Szrj }
77238fd1498Szrj (*__i).second = std::forward<_Obj>(__obj);
77338fd1498Szrj return __i;
77438fd1498Szrj }
77538fd1498Szrj #endif
77638fd1498Szrj
77738fd1498Szrj //@{
77838fd1498Szrj /**
77938fd1498Szrj * @brief Erases an element from an %unordered_map.
78038fd1498Szrj * @param __position An iterator pointing to the element to be erased.
78138fd1498Szrj * @return An iterator pointing to the element immediately following
78238fd1498Szrj * @a __position prior to the element being erased. If no such
78338fd1498Szrj * element exists, end() is returned.
78438fd1498Szrj *
78538fd1498Szrj * This function erases an element, pointed to by the given iterator,
78638fd1498Szrj * from an %unordered_map.
78738fd1498Szrj * Note that this function only erases the element, and that if the
78838fd1498Szrj * element is itself a pointer, the pointed-to memory is not touched in
78938fd1498Szrj * any way. Managing the pointer is the user's responsibility.
79038fd1498Szrj */
79138fd1498Szrj iterator
79238fd1498Szrj erase(const_iterator __position)
79338fd1498Szrj { return _M_h.erase(__position); }
79438fd1498Szrj
79538fd1498Szrj // LWG 2059.
79638fd1498Szrj iterator
79738fd1498Szrj erase(iterator __position)
79838fd1498Szrj { return _M_h.erase(__position); }
79938fd1498Szrj //@}
80038fd1498Szrj
80138fd1498Szrj /**
80238fd1498Szrj * @brief Erases elements according to the provided key.
80338fd1498Szrj * @param __x Key of element to be erased.
80438fd1498Szrj * @return The number of elements erased.
80538fd1498Szrj *
80638fd1498Szrj * This function erases all the elements located by the given key from
80738fd1498Szrj * an %unordered_map. For an %unordered_map the result of this function
80838fd1498Szrj * can only be 0 (not present) or 1 (present).
80938fd1498Szrj * Note that this function only erases the element, and that if the
81038fd1498Szrj * element is itself a pointer, the pointed-to memory is not touched in
81138fd1498Szrj * any way. Managing the pointer is the user's responsibility.
81238fd1498Szrj */
81338fd1498Szrj size_type
81438fd1498Szrj erase(const key_type& __x)
81538fd1498Szrj { return _M_h.erase(__x); }
81638fd1498Szrj
81738fd1498Szrj /**
81838fd1498Szrj * @brief Erases a [__first,__last) range of elements from an
81938fd1498Szrj * %unordered_map.
82038fd1498Szrj * @param __first Iterator pointing to the start of the range to be
82138fd1498Szrj * erased.
82238fd1498Szrj * @param __last Iterator pointing to the end of the range to
82338fd1498Szrj * be erased.
82438fd1498Szrj * @return The iterator @a __last.
82538fd1498Szrj *
82638fd1498Szrj * This function erases a sequence of elements from an %unordered_map.
82738fd1498Szrj * Note that this function only erases the elements, and that if
82838fd1498Szrj * the element is itself a pointer, the pointed-to memory is not touched
82938fd1498Szrj * in any way. Managing the pointer is the user's responsibility.
83038fd1498Szrj */
83138fd1498Szrj iterator
83238fd1498Szrj erase(const_iterator __first, const_iterator __last)
83338fd1498Szrj { return _M_h.erase(__first, __last); }
83438fd1498Szrj
83538fd1498Szrj /**
83638fd1498Szrj * Erases all elements in an %unordered_map.
83738fd1498Szrj * Note that this function only erases the elements, and that if the
83838fd1498Szrj * elements themselves are pointers, the pointed-to memory is not touched
83938fd1498Szrj * in any way. Managing the pointer is the user's responsibility.
84038fd1498Szrj */
84138fd1498Szrj void
84238fd1498Szrj clear() noexcept
84338fd1498Szrj { _M_h.clear(); }
84438fd1498Szrj
84538fd1498Szrj /**
84638fd1498Szrj * @brief Swaps data with another %unordered_map.
84738fd1498Szrj * @param __x An %unordered_map of the same element and allocator
84838fd1498Szrj * types.
84938fd1498Szrj *
85038fd1498Szrj * This exchanges the elements between two %unordered_map in constant
85138fd1498Szrj * time.
85238fd1498Szrj * Note that the global std::swap() function is specialized such that
85338fd1498Szrj * std::swap(m1,m2) will feed to this function.
85438fd1498Szrj */
85538fd1498Szrj void
85638fd1498Szrj swap(unordered_map& __x)
85738fd1498Szrj noexcept( noexcept(_M_h.swap(__x._M_h)) )
85838fd1498Szrj { _M_h.swap(__x._M_h); }
85938fd1498Szrj
86038fd1498Szrj #if __cplusplus > 201402L
86138fd1498Szrj template<typename, typename, typename>
86238fd1498Szrj friend class std::_Hash_merge_helper;
86338fd1498Szrj
86438fd1498Szrj template<typename _H2, typename _P2>
86538fd1498Szrj void
86638fd1498Szrj merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
86738fd1498Szrj {
86838fd1498Szrj using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
86938fd1498Szrj _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
87038fd1498Szrj }
87138fd1498Szrj
87238fd1498Szrj template<typename _H2, typename _P2>
87338fd1498Szrj void
87438fd1498Szrj merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
87538fd1498Szrj { merge(__source); }
87638fd1498Szrj
87738fd1498Szrj template<typename _H2, typename _P2>
87838fd1498Szrj void
87938fd1498Szrj merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
88038fd1498Szrj {
88138fd1498Szrj using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
88238fd1498Szrj _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
88338fd1498Szrj }
88438fd1498Szrj
88538fd1498Szrj template<typename _H2, typename _P2>
88638fd1498Szrj void
88738fd1498Szrj merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
88838fd1498Szrj { merge(__source); }
88938fd1498Szrj #endif // C++17
89038fd1498Szrj
89138fd1498Szrj // observers.
89238fd1498Szrj
89338fd1498Szrj /// Returns the hash functor object with which the %unordered_map was
89438fd1498Szrj /// constructed.
89538fd1498Szrj hasher
89638fd1498Szrj hash_function() const
89738fd1498Szrj { return _M_h.hash_function(); }
89838fd1498Szrj
89938fd1498Szrj /// Returns the key comparison object with which the %unordered_map was
90038fd1498Szrj /// constructed.
90138fd1498Szrj key_equal
90238fd1498Szrj key_eq() const
90338fd1498Szrj { return _M_h.key_eq(); }
90438fd1498Szrj
90538fd1498Szrj // lookup.
90638fd1498Szrj
90738fd1498Szrj //@{
90838fd1498Szrj /**
90938fd1498Szrj * @brief Tries to locate an element in an %unordered_map.
91038fd1498Szrj * @param __x Key to be located.
91138fd1498Szrj * @return Iterator pointing to sought-after element, or end() if not
91238fd1498Szrj * found.
91338fd1498Szrj *
91438fd1498Szrj * This function takes a key and tries to locate the element with which
91538fd1498Szrj * the key matches. If successful the function returns an iterator
91638fd1498Szrj * pointing to the sought after element. If unsuccessful it returns the
91738fd1498Szrj * past-the-end ( @c end() ) iterator.
91838fd1498Szrj */
91938fd1498Szrj iterator
92038fd1498Szrj find(const key_type& __x)
92138fd1498Szrj { return _M_h.find(__x); }
92238fd1498Szrj
92338fd1498Szrj const_iterator
92438fd1498Szrj find(const key_type& __x) const
92538fd1498Szrj { return _M_h.find(__x); }
92638fd1498Szrj //@}
92738fd1498Szrj
92838fd1498Szrj /**
92938fd1498Szrj * @brief Finds the number of elements.
93038fd1498Szrj * @param __x Key to count.
93138fd1498Szrj * @return Number of elements with specified key.
93238fd1498Szrj *
93338fd1498Szrj * This function only makes sense for %unordered_multimap; for
93438fd1498Szrj * %unordered_map the result will either be 0 (not present) or 1
93538fd1498Szrj * (present).
93638fd1498Szrj */
93738fd1498Szrj size_type
93838fd1498Szrj count(const key_type& __x) const
93938fd1498Szrj { return _M_h.count(__x); }
94038fd1498Szrj
94138fd1498Szrj //@{
94238fd1498Szrj /**
94338fd1498Szrj * @brief Finds a subsequence matching given key.
94438fd1498Szrj * @param __x Key to be located.
94538fd1498Szrj * @return Pair of iterators that possibly points to the subsequence
94638fd1498Szrj * matching given key.
94738fd1498Szrj *
94838fd1498Szrj * This function probably only makes sense for %unordered_multimap.
94938fd1498Szrj */
95038fd1498Szrj std::pair<iterator, iterator>
95138fd1498Szrj equal_range(const key_type& __x)
95238fd1498Szrj { return _M_h.equal_range(__x); }
95338fd1498Szrj
95438fd1498Szrj std::pair<const_iterator, const_iterator>
95538fd1498Szrj equal_range(const key_type& __x) const
95638fd1498Szrj { return _M_h.equal_range(__x); }
95738fd1498Szrj //@}
95838fd1498Szrj
95938fd1498Szrj //@{
96038fd1498Szrj /**
96138fd1498Szrj * @brief Subscript ( @c [] ) access to %unordered_map data.
96238fd1498Szrj * @param __k The key for which data should be retrieved.
96338fd1498Szrj * @return A reference to the data of the (key,data) %pair.
96438fd1498Szrj *
96538fd1498Szrj * Allows for easy lookup with the subscript ( @c [] )operator. Returns
96638fd1498Szrj * data associated with the key specified in subscript. If the key does
96738fd1498Szrj * not exist, a pair with that key is created using default values, which
96838fd1498Szrj * is then returned.
96938fd1498Szrj *
97038fd1498Szrj * Lookup requires constant time.
97138fd1498Szrj */
97238fd1498Szrj mapped_type&
97338fd1498Szrj operator[](const key_type& __k)
97438fd1498Szrj { return _M_h[__k]; }
97538fd1498Szrj
97638fd1498Szrj mapped_type&
97738fd1498Szrj operator[](key_type&& __k)
97838fd1498Szrj { return _M_h[std::move(__k)]; }
97938fd1498Szrj //@}
98038fd1498Szrj
98138fd1498Szrj //@{
98238fd1498Szrj /**
98338fd1498Szrj * @brief Access to %unordered_map data.
98438fd1498Szrj * @param __k The key for which data should be retrieved.
98538fd1498Szrj * @return A reference to the data whose key is equal to @a __k, if
98638fd1498Szrj * such a data is present in the %unordered_map.
98738fd1498Szrj * @throw std::out_of_range If no such data is present.
98838fd1498Szrj */
98938fd1498Szrj mapped_type&
99038fd1498Szrj at(const key_type& __k)
99138fd1498Szrj { return _M_h.at(__k); }
99238fd1498Szrj
99338fd1498Szrj const mapped_type&
99438fd1498Szrj at(const key_type& __k) const
99538fd1498Szrj { return _M_h.at(__k); }
99638fd1498Szrj //@}
99738fd1498Szrj
99838fd1498Szrj // bucket interface.
99938fd1498Szrj
100038fd1498Szrj /// Returns the number of buckets of the %unordered_map.
100138fd1498Szrj size_type
100238fd1498Szrj bucket_count() const noexcept
100338fd1498Szrj { return _M_h.bucket_count(); }
100438fd1498Szrj
100538fd1498Szrj /// Returns the maximum number of buckets of the %unordered_map.
100638fd1498Szrj size_type
100738fd1498Szrj max_bucket_count() const noexcept
100838fd1498Szrj { return _M_h.max_bucket_count(); }
100938fd1498Szrj
101038fd1498Szrj /*
101138fd1498Szrj * @brief Returns the number of elements in a given bucket.
101238fd1498Szrj * @param __n A bucket index.
101338fd1498Szrj * @return The number of elements in the bucket.
101438fd1498Szrj */
101538fd1498Szrj size_type
101638fd1498Szrj bucket_size(size_type __n) const
101738fd1498Szrj { return _M_h.bucket_size(__n); }
101838fd1498Szrj
101938fd1498Szrj /*
102038fd1498Szrj * @brief Returns the bucket index of a given element.
102138fd1498Szrj * @param __key A key instance.
102238fd1498Szrj * @return The key bucket index.
102338fd1498Szrj */
102438fd1498Szrj size_type
102538fd1498Szrj bucket(const key_type& __key) const
102638fd1498Szrj { return _M_h.bucket(__key); }
102738fd1498Szrj
102838fd1498Szrj /**
102938fd1498Szrj * @brief Returns a read/write iterator pointing to the first bucket
103038fd1498Szrj * element.
103138fd1498Szrj * @param __n The bucket index.
103238fd1498Szrj * @return A read/write local iterator.
103338fd1498Szrj */
103438fd1498Szrj local_iterator
103538fd1498Szrj begin(size_type __n)
103638fd1498Szrj { return _M_h.begin(__n); }
103738fd1498Szrj
103838fd1498Szrj //@{
103938fd1498Szrj /**
104038fd1498Szrj * @brief Returns a read-only (constant) iterator pointing to the first
104138fd1498Szrj * bucket element.
104238fd1498Szrj * @param __n The bucket index.
104338fd1498Szrj * @return A read-only local iterator.
104438fd1498Szrj */
104538fd1498Szrj const_local_iterator
104638fd1498Szrj begin(size_type __n) const
104738fd1498Szrj { return _M_h.begin(__n); }
104838fd1498Szrj
104938fd1498Szrj const_local_iterator
105038fd1498Szrj cbegin(size_type __n) const
105138fd1498Szrj { return _M_h.cbegin(__n); }
105238fd1498Szrj //@}
105338fd1498Szrj
105438fd1498Szrj /**
105538fd1498Szrj * @brief Returns a read/write iterator pointing to one past the last
105638fd1498Szrj * bucket elements.
105738fd1498Szrj * @param __n The bucket index.
105838fd1498Szrj * @return A read/write local iterator.
105938fd1498Szrj */
106038fd1498Szrj local_iterator
106138fd1498Szrj end(size_type __n)
106238fd1498Szrj { return _M_h.end(__n); }
106338fd1498Szrj
106438fd1498Szrj //@{
106538fd1498Szrj /**
106638fd1498Szrj * @brief Returns a read-only (constant) iterator pointing to one past
106738fd1498Szrj * the last bucket elements.
106838fd1498Szrj * @param __n The bucket index.
106938fd1498Szrj * @return A read-only local iterator.
107038fd1498Szrj */
107138fd1498Szrj const_local_iterator
107238fd1498Szrj end(size_type __n) const
107338fd1498Szrj { return _M_h.end(__n); }
107438fd1498Szrj
107538fd1498Szrj const_local_iterator
107638fd1498Szrj cend(size_type __n) const
107738fd1498Szrj { return _M_h.cend(__n); }
107838fd1498Szrj //@}
107938fd1498Szrj
108038fd1498Szrj // hash policy.
108138fd1498Szrj
108238fd1498Szrj /// Returns the average number of elements per bucket.
108338fd1498Szrj float
108438fd1498Szrj load_factor() const noexcept
108538fd1498Szrj { return _M_h.load_factor(); }
108638fd1498Szrj
108738fd1498Szrj /// Returns a positive number that the %unordered_map tries to keep the
108838fd1498Szrj /// load factor less than or equal to.
108938fd1498Szrj float
109038fd1498Szrj max_load_factor() const noexcept
109138fd1498Szrj { return _M_h.max_load_factor(); }
109238fd1498Szrj
109338fd1498Szrj /**
109438fd1498Szrj * @brief Change the %unordered_map maximum load factor.
109538fd1498Szrj * @param __z The new maximum load factor.
109638fd1498Szrj */
109738fd1498Szrj void
109838fd1498Szrj max_load_factor(float __z)
109938fd1498Szrj { _M_h.max_load_factor(__z); }
110038fd1498Szrj
110138fd1498Szrj /**
110238fd1498Szrj * @brief May rehash the %unordered_map.
110338fd1498Szrj * @param __n The new number of buckets.
110438fd1498Szrj *
110538fd1498Szrj * Rehash will occur only if the new number of buckets respect the
110638fd1498Szrj * %unordered_map maximum load factor.
110738fd1498Szrj */
110838fd1498Szrj void
110938fd1498Szrj rehash(size_type __n)
111038fd1498Szrj { _M_h.rehash(__n); }
111138fd1498Szrj
111238fd1498Szrj /**
111338fd1498Szrj * @brief Prepare the %unordered_map for a specified number of
111438fd1498Szrj * elements.
111538fd1498Szrj * @param __n Number of elements required.
111638fd1498Szrj *
111738fd1498Szrj * Same as rehash(ceil(n / max_load_factor())).
111838fd1498Szrj */
111938fd1498Szrj void
112038fd1498Szrj reserve(size_type __n)
112138fd1498Szrj { _M_h.reserve(__n); }
112238fd1498Szrj
112338fd1498Szrj template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
112438fd1498Szrj typename _Alloc1>
112538fd1498Szrj friend bool
112638fd1498Szrj operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
112738fd1498Szrj const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
112838fd1498Szrj };
112938fd1498Szrj
113038fd1498Szrj #if __cpp_deduction_guides >= 201606
113138fd1498Szrj
113238fd1498Szrj template<typename _InputIterator,
113338fd1498Szrj typename _Hash = hash<__iter_key_t<_InputIterator>>,
113438fd1498Szrj typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
113538fd1498Szrj typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
113638fd1498Szrj typename = _RequireInputIter<_InputIterator>,
113738fd1498Szrj typename = _RequireAllocator<_Allocator>>
113838fd1498Szrj unordered_map(_InputIterator, _InputIterator,
113938fd1498Szrj typename unordered_map<int, int>::size_type = {},
114038fd1498Szrj _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
114138fd1498Szrj -> unordered_map<__iter_key_t<_InputIterator>,
114238fd1498Szrj __iter_val_t<_InputIterator>,
114338fd1498Szrj _Hash, _Pred, _Allocator>;
114438fd1498Szrj
114538fd1498Szrj template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
114638fd1498Szrj typename _Pred = equal_to<_Key>,
114738fd1498Szrj typename _Allocator = allocator<pair<const _Key, _Tp>>,
114838fd1498Szrj typename = _RequireAllocator<_Allocator>>
114938fd1498Szrj unordered_map(initializer_list<pair<_Key, _Tp>>,
115038fd1498Szrj typename unordered_map<int, int>::size_type = {},
115138fd1498Szrj _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
115238fd1498Szrj -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
115338fd1498Szrj
115438fd1498Szrj template<typename _InputIterator, typename _Allocator,
115538fd1498Szrj typename = _RequireInputIter<_InputIterator>,
115638fd1498Szrj typename = _RequireAllocator<_Allocator>>
115738fd1498Szrj unordered_map(_InputIterator, _InputIterator,
115838fd1498Szrj typename unordered_map<int, int>::size_type, _Allocator)
115938fd1498Szrj -> unordered_map<__iter_key_t<_InputIterator>,
116038fd1498Szrj __iter_val_t<_InputIterator>,
116138fd1498Szrj hash<__iter_key_t<_InputIterator>>,
116238fd1498Szrj equal_to<__iter_key_t<_InputIterator>>,
116338fd1498Szrj _Allocator>;
116438fd1498Szrj
116538fd1498Szrj template<typename _InputIterator, typename _Allocator,
116638fd1498Szrj typename = _RequireInputIter<_InputIterator>,
116738fd1498Szrj typename = _RequireAllocator<_Allocator>>
116838fd1498Szrj unordered_map(_InputIterator, _InputIterator, _Allocator)
116938fd1498Szrj -> unordered_map<__iter_key_t<_InputIterator>,
117038fd1498Szrj __iter_val_t<_InputIterator>,
117138fd1498Szrj hash<__iter_key_t<_InputIterator>>,
117238fd1498Szrj equal_to<__iter_key_t<_InputIterator>>,
117338fd1498Szrj _Allocator>;
117438fd1498Szrj
117538fd1498Szrj template<typename _InputIterator, typename _Hash, typename _Allocator,
117638fd1498Szrj typename = _RequireInputIter<_InputIterator>,
117738fd1498Szrj typename = _RequireAllocator<_Allocator>>
117838fd1498Szrj unordered_map(_InputIterator, _InputIterator,
117938fd1498Szrj typename unordered_map<int, int>::size_type,
118038fd1498Szrj _Hash, _Allocator)
118138fd1498Szrj -> unordered_map<__iter_key_t<_InputIterator>,
118238fd1498Szrj __iter_val_t<_InputIterator>, _Hash,
118338fd1498Szrj equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
118438fd1498Szrj
118538fd1498Szrj template<typename _Key, typename _Tp, typename _Allocator,
118638fd1498Szrj typename = _RequireAllocator<_Allocator>>
118738fd1498Szrj unordered_map(initializer_list<pair<_Key, _Tp>>,
118838fd1498Szrj typename unordered_map<int, int>::size_type,
118938fd1498Szrj _Allocator)
119038fd1498Szrj -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
119138fd1498Szrj
119238fd1498Szrj template<typename _Key, typename _Tp, typename _Allocator,
119338fd1498Szrj typename = _RequireAllocator<_Allocator>>
119438fd1498Szrj unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
119538fd1498Szrj -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
119638fd1498Szrj
119738fd1498Szrj template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
119838fd1498Szrj typename = _RequireAllocator<_Allocator>>
119938fd1498Szrj unordered_map(initializer_list<pair<_Key, _Tp>>,
120038fd1498Szrj typename unordered_map<int, int>::size_type,
120138fd1498Szrj _Hash, _Allocator)
120238fd1498Szrj -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
120338fd1498Szrj
120438fd1498Szrj #endif
120538fd1498Szrj
120638fd1498Szrj /**
120738fd1498Szrj * @brief A standard container composed of equivalent keys
120838fd1498Szrj * (possibly containing multiple of each key value) that associates
120938fd1498Szrj * values of another type with the keys.
121038fd1498Szrj *
121138fd1498Szrj * @ingroup unordered_associative_containers
121238fd1498Szrj *
121338fd1498Szrj * @tparam _Key Type of key objects.
121438fd1498Szrj * @tparam _Tp Type of mapped objects.
121538fd1498Szrj * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
121638fd1498Szrj * @tparam _Pred Predicate function object type, defaults
121738fd1498Szrj * to equal_to<_Value>.
121838fd1498Szrj * @tparam _Alloc Allocator type, defaults to
121938fd1498Szrj * std::allocator<std::pair<const _Key, _Tp>>.
122038fd1498Szrj *
122138fd1498Szrj * Meets the requirements of a <a href="tables.html#65">container</a>, and
122238fd1498Szrj * <a href="tables.html#xx">unordered associative container</a>
122338fd1498Szrj *
122438fd1498Szrj * The resulting value type of the container is std::pair<const _Key, _Tp>.
122538fd1498Szrj *
122638fd1498Szrj * Base is _Hashtable, dispatched at compile time via template
122738fd1498Szrj * alias __ummap_hashtable.
122838fd1498Szrj */
122938fd1498Szrj template<typename _Key, typename _Tp,
123038fd1498Szrj typename _Hash = hash<_Key>,
123138fd1498Szrj typename _Pred = equal_to<_Key>,
123238fd1498Szrj typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
123338fd1498Szrj class unordered_multimap
123438fd1498Szrj {
123538fd1498Szrj typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
123638fd1498Szrj _Hashtable _M_h;
123738fd1498Szrj
123838fd1498Szrj public:
123938fd1498Szrj // typedefs:
124038fd1498Szrj //@{
124138fd1498Szrj /// Public typedefs.
124238fd1498Szrj typedef typename _Hashtable::key_type key_type;
124338fd1498Szrj typedef typename _Hashtable::value_type value_type;
124438fd1498Szrj typedef typename _Hashtable::mapped_type mapped_type;
124538fd1498Szrj typedef typename _Hashtable::hasher hasher;
124638fd1498Szrj typedef typename _Hashtable::key_equal key_equal;
124738fd1498Szrj typedef typename _Hashtable::allocator_type allocator_type;
124838fd1498Szrj //@}
124938fd1498Szrj
125038fd1498Szrj //@{
125138fd1498Szrj /// Iterator-related typedefs.
125238fd1498Szrj typedef typename _Hashtable::pointer pointer;
125338fd1498Szrj typedef typename _Hashtable::const_pointer const_pointer;
125438fd1498Szrj typedef typename _Hashtable::reference reference;
125538fd1498Szrj typedef typename _Hashtable::const_reference const_reference;
125638fd1498Szrj typedef typename _Hashtable::iterator iterator;
125738fd1498Szrj typedef typename _Hashtable::const_iterator const_iterator;
125838fd1498Szrj typedef typename _Hashtable::local_iterator local_iterator;
125938fd1498Szrj typedef typename _Hashtable::const_local_iterator const_local_iterator;
126038fd1498Szrj typedef typename _Hashtable::size_type size_type;
126138fd1498Szrj typedef typename _Hashtable::difference_type difference_type;
126238fd1498Szrj //@}
126338fd1498Szrj
126438fd1498Szrj #if __cplusplus > 201402L
126538fd1498Szrj using node_type = typename _Hashtable::node_type;
126638fd1498Szrj #endif
126738fd1498Szrj
126838fd1498Szrj //construct/destroy/copy
126938fd1498Szrj
127038fd1498Szrj /// Default constructor.
127138fd1498Szrj unordered_multimap() = default;
127238fd1498Szrj
127338fd1498Szrj /**
127438fd1498Szrj * @brief Default constructor creates no elements.
127538fd1498Szrj * @param __n Mnimal initial number of buckets.
127638fd1498Szrj * @param __hf A hash functor.
127738fd1498Szrj * @param __eql A key equality functor.
127838fd1498Szrj * @param __a An allocator object.
127938fd1498Szrj */
128038fd1498Szrj explicit
128138fd1498Szrj unordered_multimap(size_type __n,
128238fd1498Szrj const hasher& __hf = hasher(),
128338fd1498Szrj const key_equal& __eql = key_equal(),
128438fd1498Szrj const allocator_type& __a = allocator_type())
128538fd1498Szrj : _M_h(__n, __hf, __eql, __a)
128638fd1498Szrj { }
128738fd1498Szrj
128838fd1498Szrj /**
128938fd1498Szrj * @brief Builds an %unordered_multimap from a range.
129038fd1498Szrj * @param __first An input iterator.
129138fd1498Szrj * @param __last An input iterator.
129238fd1498Szrj * @param __n Minimal initial number of buckets.
129338fd1498Szrj * @param __hf A hash functor.
129438fd1498Szrj * @param __eql A key equality functor.
129538fd1498Szrj * @param __a An allocator object.
129638fd1498Szrj *
129738fd1498Szrj * Create an %unordered_multimap consisting of copies of the elements
129838fd1498Szrj * from [__first,__last). This is linear in N (where N is
129938fd1498Szrj * distance(__first,__last)).
130038fd1498Szrj */
130138fd1498Szrj template<typename _InputIterator>
130238fd1498Szrj unordered_multimap(_InputIterator __first, _InputIterator __last,
130338fd1498Szrj size_type __n = 0,
130438fd1498Szrj const hasher& __hf = hasher(),
130538fd1498Szrj const key_equal& __eql = key_equal(),
130638fd1498Szrj const allocator_type& __a = allocator_type())
130738fd1498Szrj : _M_h(__first, __last, __n, __hf, __eql, __a)
130838fd1498Szrj { }
130938fd1498Szrj
131038fd1498Szrj /// Copy constructor.
131138fd1498Szrj unordered_multimap(const unordered_multimap&) = default;
131238fd1498Szrj
131338fd1498Szrj /// Move constructor.
131438fd1498Szrj unordered_multimap(unordered_multimap&&) = default;
131538fd1498Szrj
131638fd1498Szrj /**
131738fd1498Szrj * @brief Creates an %unordered_multimap with no elements.
131838fd1498Szrj * @param __a An allocator object.
131938fd1498Szrj */
132038fd1498Szrj explicit
132138fd1498Szrj unordered_multimap(const allocator_type& __a)
132238fd1498Szrj : _M_h(__a)
132338fd1498Szrj { }
132438fd1498Szrj
132538fd1498Szrj /*
132638fd1498Szrj * @brief Copy constructor with allocator argument.
132738fd1498Szrj * @param __uset Input %unordered_multimap to copy.
132838fd1498Szrj * @param __a An allocator object.
132938fd1498Szrj */
133038fd1498Szrj unordered_multimap(const unordered_multimap& __ummap,
133138fd1498Szrj const allocator_type& __a)
133238fd1498Szrj : _M_h(__ummap._M_h, __a)
133338fd1498Szrj { }
133438fd1498Szrj
133538fd1498Szrj /*
133638fd1498Szrj * @brief Move constructor with allocator argument.
133738fd1498Szrj * @param __uset Input %unordered_multimap to move.
133838fd1498Szrj * @param __a An allocator object.
133938fd1498Szrj */
134038fd1498Szrj unordered_multimap(unordered_multimap&& __ummap,
134138fd1498Szrj const allocator_type& __a)
134238fd1498Szrj : _M_h(std::move(__ummap._M_h), __a)
134338fd1498Szrj { }
134438fd1498Szrj
134538fd1498Szrj /**
134638fd1498Szrj * @brief Builds an %unordered_multimap from an initializer_list.
134738fd1498Szrj * @param __l An initializer_list.
134838fd1498Szrj * @param __n Minimal initial number of buckets.
134938fd1498Szrj * @param __hf A hash functor.
135038fd1498Szrj * @param __eql A key equality functor.
135138fd1498Szrj * @param __a An allocator object.
135238fd1498Szrj *
135338fd1498Szrj * Create an %unordered_multimap consisting of copies of the elements in
135438fd1498Szrj * the list. This is linear in N (where N is @a __l.size()).
135538fd1498Szrj */
135638fd1498Szrj unordered_multimap(initializer_list<value_type> __l,
135738fd1498Szrj size_type __n = 0,
135838fd1498Szrj const hasher& __hf = hasher(),
135938fd1498Szrj const key_equal& __eql = key_equal(),
136038fd1498Szrj const allocator_type& __a = allocator_type())
136138fd1498Szrj : _M_h(__l, __n, __hf, __eql, __a)
136238fd1498Szrj { }
136338fd1498Szrj
136438fd1498Szrj unordered_multimap(size_type __n, const allocator_type& __a)
136538fd1498Szrj : unordered_multimap(__n, hasher(), key_equal(), __a)
136638fd1498Szrj { }
136738fd1498Szrj
136838fd1498Szrj unordered_multimap(size_type __n, const hasher& __hf,
136938fd1498Szrj const allocator_type& __a)
137038fd1498Szrj : unordered_multimap(__n, __hf, key_equal(), __a)
137138fd1498Szrj { }
137238fd1498Szrj
137338fd1498Szrj template<typename _InputIterator>
137438fd1498Szrj unordered_multimap(_InputIterator __first, _InputIterator __last,
137538fd1498Szrj size_type __n,
137638fd1498Szrj const allocator_type& __a)
137738fd1498Szrj : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
137838fd1498Szrj { }
137938fd1498Szrj
138038fd1498Szrj template<typename _InputIterator>
138138fd1498Szrj unordered_multimap(_InputIterator __first, _InputIterator __last,
138238fd1498Szrj size_type __n, const hasher& __hf,
138338fd1498Szrj const allocator_type& __a)
138438fd1498Szrj : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
138538fd1498Szrj { }
138638fd1498Szrj
138738fd1498Szrj unordered_multimap(initializer_list<value_type> __l,
138838fd1498Szrj size_type __n,
138938fd1498Szrj const allocator_type& __a)
139038fd1498Szrj : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
139138fd1498Szrj { }
139238fd1498Szrj
139338fd1498Szrj unordered_multimap(initializer_list<value_type> __l,
139438fd1498Szrj size_type __n, const hasher& __hf,
139538fd1498Szrj const allocator_type& __a)
139638fd1498Szrj : unordered_multimap(__l, __n, __hf, key_equal(), __a)
139738fd1498Szrj { }
139838fd1498Szrj
139938fd1498Szrj /// Copy assignment operator.
140038fd1498Szrj unordered_multimap&
140138fd1498Szrj operator=(const unordered_multimap&) = default;
140238fd1498Szrj
140338fd1498Szrj /// Move assignment operator.
140438fd1498Szrj unordered_multimap&
140538fd1498Szrj operator=(unordered_multimap&&) = default;
140638fd1498Szrj
140738fd1498Szrj /**
140838fd1498Szrj * @brief %Unordered_multimap list assignment operator.
140938fd1498Szrj * @param __l An initializer_list.
141038fd1498Szrj *
141138fd1498Szrj * This function fills an %unordered_multimap with copies of the
141238fd1498Szrj * elements in the initializer list @a __l.
141338fd1498Szrj *
141438fd1498Szrj * Note that the assignment completely changes the %unordered_multimap
141538fd1498Szrj * and that the resulting %unordered_multimap's size is the same as the
141638fd1498Szrj * number of elements assigned.
141738fd1498Szrj */
141838fd1498Szrj unordered_multimap&
141938fd1498Szrj operator=(initializer_list<value_type> __l)
142038fd1498Szrj {
142138fd1498Szrj _M_h = __l;
142238fd1498Szrj return *this;
142338fd1498Szrj }
142438fd1498Szrj
142538fd1498Szrj /// Returns the allocator object used by the %unordered_multimap.
142638fd1498Szrj allocator_type
142738fd1498Szrj get_allocator() const noexcept
142838fd1498Szrj { return _M_h.get_allocator(); }
142938fd1498Szrj
143038fd1498Szrj // size and capacity:
143138fd1498Szrj
143238fd1498Szrj /// Returns true if the %unordered_multimap is empty.
143338fd1498Szrj bool
143438fd1498Szrj empty() const noexcept
143538fd1498Szrj { return _M_h.empty(); }
143638fd1498Szrj
143738fd1498Szrj /// Returns the size of the %unordered_multimap.
143838fd1498Szrj size_type
143938fd1498Szrj size() const noexcept
144038fd1498Szrj { return _M_h.size(); }
144138fd1498Szrj
144238fd1498Szrj /// Returns the maximum size of the %unordered_multimap.
144338fd1498Szrj size_type
144438fd1498Szrj max_size() const noexcept
144538fd1498Szrj { return _M_h.max_size(); }
144638fd1498Szrj
144738fd1498Szrj // iterators.
144838fd1498Szrj
144938fd1498Szrj /**
145038fd1498Szrj * Returns a read/write iterator that points to the first element in the
145138fd1498Szrj * %unordered_multimap.
145238fd1498Szrj */
145338fd1498Szrj iterator
145438fd1498Szrj begin() noexcept
145538fd1498Szrj { return _M_h.begin(); }
145638fd1498Szrj
145738fd1498Szrj //@{
145838fd1498Szrj /**
145938fd1498Szrj * Returns a read-only (constant) iterator that points to the first
146038fd1498Szrj * element in the %unordered_multimap.
146138fd1498Szrj */
146238fd1498Szrj const_iterator
146338fd1498Szrj begin() const noexcept
146438fd1498Szrj { return _M_h.begin(); }
146538fd1498Szrj
146638fd1498Szrj const_iterator
146738fd1498Szrj cbegin() const noexcept
146838fd1498Szrj { return _M_h.begin(); }
146938fd1498Szrj //@}
147038fd1498Szrj
147138fd1498Szrj /**
147238fd1498Szrj * Returns a read/write iterator that points one past the last element in
147338fd1498Szrj * the %unordered_multimap.
147438fd1498Szrj */
147538fd1498Szrj iterator
147638fd1498Szrj end() noexcept
147738fd1498Szrj { return _M_h.end(); }
147838fd1498Szrj
147938fd1498Szrj //@{
148038fd1498Szrj /**
148138fd1498Szrj * Returns a read-only (constant) iterator that points one past the last
148238fd1498Szrj * element in the %unordered_multimap.
148338fd1498Szrj */
148438fd1498Szrj const_iterator
148538fd1498Szrj end() const noexcept
148638fd1498Szrj { return _M_h.end(); }
148738fd1498Szrj
148838fd1498Szrj const_iterator
148938fd1498Szrj cend() const noexcept
149038fd1498Szrj { return _M_h.end(); }
149138fd1498Szrj //@}
149238fd1498Szrj
149338fd1498Szrj // modifiers.
149438fd1498Szrj
149538fd1498Szrj /**
149638fd1498Szrj * @brief Attempts to build and insert a std::pair into the
149738fd1498Szrj * %unordered_multimap.
149838fd1498Szrj *
149938fd1498Szrj * @param __args Arguments used to generate a new pair instance (see
150038fd1498Szrj * std::piecewise_contruct for passing arguments to each
150138fd1498Szrj * part of the pair constructor).
150238fd1498Szrj *
150338fd1498Szrj * @return An iterator that points to the inserted pair.
150438fd1498Szrj *
150538fd1498Szrj * This function attempts to build and insert a (key, value) %pair into
150638fd1498Szrj * the %unordered_multimap.
150738fd1498Szrj *
150838fd1498Szrj * Insertion requires amortized constant time.
150938fd1498Szrj */
151038fd1498Szrj template<typename... _Args>
151138fd1498Szrj iterator
151238fd1498Szrj emplace(_Args&&... __args)
151338fd1498Szrj { return _M_h.emplace(std::forward<_Args>(__args)...); }
151438fd1498Szrj
151538fd1498Szrj /**
151638fd1498Szrj * @brief Attempts to build and insert a std::pair into the
151738fd1498Szrj * %unordered_multimap.
151838fd1498Szrj *
151938fd1498Szrj * @param __pos An iterator that serves as a hint as to where the pair
152038fd1498Szrj * should be inserted.
152138fd1498Szrj * @param __args Arguments used to generate a new pair instance (see
152238fd1498Szrj * std::piecewise_contruct for passing arguments to each
152338fd1498Szrj * part of the pair constructor).
152438fd1498Szrj * @return An iterator that points to the element with key of the
152538fd1498Szrj * std::pair built from @a __args.
152638fd1498Szrj *
152738fd1498Szrj * Note that the first parameter is only a hint and can potentially
152838fd1498Szrj * improve the performance of the insertion process. A bad hint would
152938fd1498Szrj * cause no gains in efficiency.
153038fd1498Szrj *
153138fd1498Szrj * See
153238fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
153338fd1498Szrj * for more on @a hinting.
153438fd1498Szrj *
153538fd1498Szrj * Insertion requires amortized constant time.
153638fd1498Szrj */
153738fd1498Szrj template<typename... _Args>
153838fd1498Szrj iterator
153938fd1498Szrj emplace_hint(const_iterator __pos, _Args&&... __args)
154038fd1498Szrj { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
154138fd1498Szrj
154238fd1498Szrj //@{
154338fd1498Szrj /**
154438fd1498Szrj * @brief Inserts a std::pair into the %unordered_multimap.
154538fd1498Szrj * @param __x Pair to be inserted (see std::make_pair for easy
154638fd1498Szrj * creation of pairs).
154738fd1498Szrj *
154838fd1498Szrj * @return An iterator that points to the inserted pair.
154938fd1498Szrj *
155038fd1498Szrj * Insertion requires amortized constant time.
155138fd1498Szrj */
155238fd1498Szrj iterator
155338fd1498Szrj insert(const value_type& __x)
155438fd1498Szrj { return _M_h.insert(__x); }
155538fd1498Szrj
155638fd1498Szrj iterator
155738fd1498Szrj insert(value_type&& __x)
155838fd1498Szrj { return _M_h.insert(std::move(__x)); }
155938fd1498Szrj
1560*58e805e6Szrj template<typename _Pair>
1561*58e805e6Szrj __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
156238fd1498Szrj insert(_Pair&& __x)
1563*58e805e6Szrj { return _M_h.emplace(std::forward<_Pair>(__x)); }
156438fd1498Szrj //@}
156538fd1498Szrj
156638fd1498Szrj //@{
156738fd1498Szrj /**
156838fd1498Szrj * @brief Inserts a std::pair into the %unordered_multimap.
156938fd1498Szrj * @param __hint An iterator that serves as a hint as to where the
157038fd1498Szrj * pair should be inserted.
157138fd1498Szrj * @param __x Pair to be inserted (see std::make_pair for easy creation
157238fd1498Szrj * of pairs).
157338fd1498Szrj * @return An iterator that points to the element with key of
157438fd1498Szrj * @a __x (may or may not be the %pair passed in).
157538fd1498Szrj *
157638fd1498Szrj * Note that the first parameter is only a hint and can potentially
157738fd1498Szrj * improve the performance of the insertion process. A bad hint would
157838fd1498Szrj * cause no gains in efficiency.
157938fd1498Szrj *
158038fd1498Szrj * See
158138fd1498Szrj * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
158238fd1498Szrj * for more on @a hinting.
158338fd1498Szrj *
158438fd1498Szrj * Insertion requires amortized constant time.
158538fd1498Szrj */
158638fd1498Szrj iterator
158738fd1498Szrj insert(const_iterator __hint, const value_type& __x)
158838fd1498Szrj { return _M_h.insert(__hint, __x); }
158938fd1498Szrj
159038fd1498Szrj // _GLIBCXX_RESOLVE_LIB_DEFECTS
159138fd1498Szrj // 2354. Unnecessary copying when inserting into maps with braced-init
159238fd1498Szrj iterator
159338fd1498Szrj insert(const_iterator __hint, value_type&& __x)
159438fd1498Szrj { return _M_h.insert(__hint, std::move(__x)); }
159538fd1498Szrj
1596*58e805e6Szrj template<typename _Pair>
1597*58e805e6Szrj __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
159838fd1498Szrj insert(const_iterator __hint, _Pair&& __x)
1599*58e805e6Szrj { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
160038fd1498Szrj //@}
160138fd1498Szrj
160238fd1498Szrj /**
160338fd1498Szrj * @brief A template function that attempts to insert a range of
160438fd1498Szrj * elements.
160538fd1498Szrj * @param __first Iterator pointing to the start of the range to be
160638fd1498Szrj * inserted.
160738fd1498Szrj * @param __last Iterator pointing to the end of the range.
160838fd1498Szrj *
160938fd1498Szrj * Complexity similar to that of the range constructor.
161038fd1498Szrj */
161138fd1498Szrj template<typename _InputIterator>
161238fd1498Szrj void
161338fd1498Szrj insert(_InputIterator __first, _InputIterator __last)
161438fd1498Szrj { _M_h.insert(__first, __last); }
161538fd1498Szrj
161638fd1498Szrj /**
161738fd1498Szrj * @brief Attempts to insert a list of elements into the
161838fd1498Szrj * %unordered_multimap.
161938fd1498Szrj * @param __l A std::initializer_list<value_type> of elements
162038fd1498Szrj * to be inserted.
162138fd1498Szrj *
162238fd1498Szrj * Complexity similar to that of the range constructor.
162338fd1498Szrj */
162438fd1498Szrj void
162538fd1498Szrj insert(initializer_list<value_type> __l)
162638fd1498Szrj { _M_h.insert(__l); }
162738fd1498Szrj
162838fd1498Szrj #if __cplusplus > 201402L
162938fd1498Szrj /// Extract a node.
163038fd1498Szrj node_type
163138fd1498Szrj extract(const_iterator __pos)
163238fd1498Szrj {
163338fd1498Szrj __glibcxx_assert(__pos != end());
163438fd1498Szrj return _M_h.extract(__pos);
163538fd1498Szrj }
163638fd1498Szrj
163738fd1498Szrj /// Extract a node.
163838fd1498Szrj node_type
163938fd1498Szrj extract(const key_type& __key)
164038fd1498Szrj { return _M_h.extract(__key); }
164138fd1498Szrj
164238fd1498Szrj /// Re-insert an extracted node.
164338fd1498Szrj iterator
164438fd1498Szrj insert(node_type&& __nh)
164538fd1498Szrj { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
164638fd1498Szrj
164738fd1498Szrj /// Re-insert an extracted node.
164838fd1498Szrj iterator
164938fd1498Szrj insert(const_iterator __hint, node_type&& __nh)
165038fd1498Szrj { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
165138fd1498Szrj #endif // C++17
165238fd1498Szrj
165338fd1498Szrj //@{
165438fd1498Szrj /**
165538fd1498Szrj * @brief Erases an element from an %unordered_multimap.
165638fd1498Szrj * @param __position An iterator pointing to the element to be erased.
165738fd1498Szrj * @return An iterator pointing to the element immediately following
165838fd1498Szrj * @a __position prior to the element being erased. If no such
165938fd1498Szrj * element exists, end() is returned.
166038fd1498Szrj *
166138fd1498Szrj * This function erases an element, pointed to by the given iterator,
166238fd1498Szrj * from an %unordered_multimap.
166338fd1498Szrj * Note that this function only erases the element, and that if the
166438fd1498Szrj * element is itself a pointer, the pointed-to memory is not touched in
166538fd1498Szrj * any way. Managing the pointer is the user's responsibility.
166638fd1498Szrj */
166738fd1498Szrj iterator
166838fd1498Szrj erase(const_iterator __position)
166938fd1498Szrj { return _M_h.erase(__position); }
167038fd1498Szrj
167138fd1498Szrj // LWG 2059.
167238fd1498Szrj iterator
167338fd1498Szrj erase(iterator __position)
167438fd1498Szrj { return _M_h.erase(__position); }
167538fd1498Szrj //@}
167638fd1498Szrj
167738fd1498Szrj /**
167838fd1498Szrj * @brief Erases elements according to the provided key.
167938fd1498Szrj * @param __x Key of elements to be erased.
168038fd1498Szrj * @return The number of elements erased.
168138fd1498Szrj *
168238fd1498Szrj * This function erases all the elements located by the given key from
168338fd1498Szrj * an %unordered_multimap.
168438fd1498Szrj * Note that this function only erases the element, and that if the
168538fd1498Szrj * element is itself a pointer, the pointed-to memory is not touched in
168638fd1498Szrj * any way. Managing the pointer is the user's responsibility.
168738fd1498Szrj */
168838fd1498Szrj size_type
168938fd1498Szrj erase(const key_type& __x)
169038fd1498Szrj { return _M_h.erase(__x); }
169138fd1498Szrj
169238fd1498Szrj /**
169338fd1498Szrj * @brief Erases a [__first,__last) range of elements from an
169438fd1498Szrj * %unordered_multimap.
169538fd1498Szrj * @param __first Iterator pointing to the start of the range to be
169638fd1498Szrj * erased.
169738fd1498Szrj * @param __last Iterator pointing to the end of the range to
169838fd1498Szrj * be erased.
169938fd1498Szrj * @return The iterator @a __last.
170038fd1498Szrj *
170138fd1498Szrj * This function erases a sequence of elements from an
170238fd1498Szrj * %unordered_multimap.
170338fd1498Szrj * Note that this function only erases the elements, and that if
170438fd1498Szrj * the element is itself a pointer, the pointed-to memory is not touched
170538fd1498Szrj * in any way. Managing the pointer is the user's responsibility.
170638fd1498Szrj */
170738fd1498Szrj iterator
170838fd1498Szrj erase(const_iterator __first, const_iterator __last)
170938fd1498Szrj { return _M_h.erase(__first, __last); }
171038fd1498Szrj
171138fd1498Szrj /**
171238fd1498Szrj * Erases all elements in an %unordered_multimap.
171338fd1498Szrj * Note that this function only erases the elements, and that if the
171438fd1498Szrj * elements themselves are pointers, the pointed-to memory is not touched
171538fd1498Szrj * in any way. Managing the pointer is the user's responsibility.
171638fd1498Szrj */
171738fd1498Szrj void
171838fd1498Szrj clear() noexcept
171938fd1498Szrj { _M_h.clear(); }
172038fd1498Szrj
172138fd1498Szrj /**
172238fd1498Szrj * @brief Swaps data with another %unordered_multimap.
172338fd1498Szrj * @param __x An %unordered_multimap of the same element and allocator
172438fd1498Szrj * types.
172538fd1498Szrj *
172638fd1498Szrj * This exchanges the elements between two %unordered_multimap in
172738fd1498Szrj * constant time.
172838fd1498Szrj * Note that the global std::swap() function is specialized such that
172938fd1498Szrj * std::swap(m1,m2) will feed to this function.
173038fd1498Szrj */
173138fd1498Szrj void
173238fd1498Szrj swap(unordered_multimap& __x)
173338fd1498Szrj noexcept( noexcept(_M_h.swap(__x._M_h)) )
173438fd1498Szrj { _M_h.swap(__x._M_h); }
173538fd1498Szrj
173638fd1498Szrj #if __cplusplus > 201402L
173738fd1498Szrj template<typename, typename, typename>
173838fd1498Szrj friend class std::_Hash_merge_helper;
173938fd1498Szrj
174038fd1498Szrj template<typename _H2, typename _P2>
174138fd1498Szrj void
174238fd1498Szrj merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
174338fd1498Szrj {
174438fd1498Szrj using _Merge_helper
174538fd1498Szrj = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
174638fd1498Szrj _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
174738fd1498Szrj }
174838fd1498Szrj
174938fd1498Szrj template<typename _H2, typename _P2>
175038fd1498Szrj void
175138fd1498Szrj merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
175238fd1498Szrj { merge(__source); }
175338fd1498Szrj
175438fd1498Szrj template<typename _H2, typename _P2>
175538fd1498Szrj void
175638fd1498Szrj merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
175738fd1498Szrj {
175838fd1498Szrj using _Merge_helper
175938fd1498Szrj = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
176038fd1498Szrj _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
176138fd1498Szrj }
176238fd1498Szrj
176338fd1498Szrj template<typename _H2, typename _P2>
176438fd1498Szrj void
176538fd1498Szrj merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
176638fd1498Szrj { merge(__source); }
176738fd1498Szrj #endif // C++17
176838fd1498Szrj
176938fd1498Szrj // observers.
177038fd1498Szrj
177138fd1498Szrj /// Returns the hash functor object with which the %unordered_multimap
177238fd1498Szrj /// was constructed.
177338fd1498Szrj hasher
177438fd1498Szrj hash_function() const
177538fd1498Szrj { return _M_h.hash_function(); }
177638fd1498Szrj
177738fd1498Szrj /// Returns the key comparison object with which the %unordered_multimap
177838fd1498Szrj /// was constructed.
177938fd1498Szrj key_equal
178038fd1498Szrj key_eq() const
178138fd1498Szrj { return _M_h.key_eq(); }
178238fd1498Szrj
178338fd1498Szrj // lookup.
178438fd1498Szrj
178538fd1498Szrj //@{
178638fd1498Szrj /**
178738fd1498Szrj * @brief Tries to locate an element in an %unordered_multimap.
178838fd1498Szrj * @param __x Key to be located.
178938fd1498Szrj * @return Iterator pointing to sought-after element, or end() if not
179038fd1498Szrj * found.
179138fd1498Szrj *
179238fd1498Szrj * This function takes a key and tries to locate the element with which
179338fd1498Szrj * the key matches. If successful the function returns an iterator
179438fd1498Szrj * pointing to the sought after element. If unsuccessful it returns the
179538fd1498Szrj * past-the-end ( @c end() ) iterator.
179638fd1498Szrj */
179738fd1498Szrj iterator
179838fd1498Szrj find(const key_type& __x)
179938fd1498Szrj { return _M_h.find(__x); }
180038fd1498Szrj
180138fd1498Szrj const_iterator
180238fd1498Szrj find(const key_type& __x) const
180338fd1498Szrj { return _M_h.find(__x); }
180438fd1498Szrj //@}
180538fd1498Szrj
180638fd1498Szrj /**
180738fd1498Szrj * @brief Finds the number of elements.
180838fd1498Szrj * @param __x Key to count.
180938fd1498Szrj * @return Number of elements with specified key.
181038fd1498Szrj */
181138fd1498Szrj size_type
181238fd1498Szrj count(const key_type& __x) const
181338fd1498Szrj { return _M_h.count(__x); }
181438fd1498Szrj
181538fd1498Szrj //@{
181638fd1498Szrj /**
181738fd1498Szrj * @brief Finds a subsequence matching given key.
181838fd1498Szrj * @param __x Key to be located.
181938fd1498Szrj * @return Pair of iterators that possibly points to the subsequence
182038fd1498Szrj * matching given key.
182138fd1498Szrj */
182238fd1498Szrj std::pair<iterator, iterator>
182338fd1498Szrj equal_range(const key_type& __x)
182438fd1498Szrj { return _M_h.equal_range(__x); }
182538fd1498Szrj
182638fd1498Szrj std::pair<const_iterator, const_iterator>
182738fd1498Szrj equal_range(const key_type& __x) const
182838fd1498Szrj { return _M_h.equal_range(__x); }
182938fd1498Szrj //@}
183038fd1498Szrj
183138fd1498Szrj // bucket interface.
183238fd1498Szrj
183338fd1498Szrj /// Returns the number of buckets of the %unordered_multimap.
183438fd1498Szrj size_type
183538fd1498Szrj bucket_count() const noexcept
183638fd1498Szrj { return _M_h.bucket_count(); }
183738fd1498Szrj
183838fd1498Szrj /// Returns the maximum number of buckets of the %unordered_multimap.
183938fd1498Szrj size_type
184038fd1498Szrj max_bucket_count() const noexcept
184138fd1498Szrj { return _M_h.max_bucket_count(); }
184238fd1498Szrj
184338fd1498Szrj /*
184438fd1498Szrj * @brief Returns the number of elements in a given bucket.
184538fd1498Szrj * @param __n A bucket index.
184638fd1498Szrj * @return The number of elements in the bucket.
184738fd1498Szrj */
184838fd1498Szrj size_type
184938fd1498Szrj bucket_size(size_type __n) const
185038fd1498Szrj { return _M_h.bucket_size(__n); }
185138fd1498Szrj
185238fd1498Szrj /*
185338fd1498Szrj * @brief Returns the bucket index of a given element.
185438fd1498Szrj * @param __key A key instance.
185538fd1498Szrj * @return The key bucket index.
185638fd1498Szrj */
185738fd1498Szrj size_type
185838fd1498Szrj bucket(const key_type& __key) const
185938fd1498Szrj { return _M_h.bucket(__key); }
186038fd1498Szrj
186138fd1498Szrj /**
186238fd1498Szrj * @brief Returns a read/write iterator pointing to the first bucket
186338fd1498Szrj * element.
186438fd1498Szrj * @param __n The bucket index.
186538fd1498Szrj * @return A read/write local iterator.
186638fd1498Szrj */
186738fd1498Szrj local_iterator
186838fd1498Szrj begin(size_type __n)
186938fd1498Szrj { return _M_h.begin(__n); }
187038fd1498Szrj
187138fd1498Szrj //@{
187238fd1498Szrj /**
187338fd1498Szrj * @brief Returns a read-only (constant) iterator pointing to the first
187438fd1498Szrj * bucket element.
187538fd1498Szrj * @param __n The bucket index.
187638fd1498Szrj * @return A read-only local iterator.
187738fd1498Szrj */
187838fd1498Szrj const_local_iterator
187938fd1498Szrj begin(size_type __n) const
188038fd1498Szrj { return _M_h.begin(__n); }
188138fd1498Szrj
188238fd1498Szrj const_local_iterator
188338fd1498Szrj cbegin(size_type __n) const
188438fd1498Szrj { return _M_h.cbegin(__n); }
188538fd1498Szrj //@}
188638fd1498Szrj
188738fd1498Szrj /**
188838fd1498Szrj * @brief Returns a read/write iterator pointing to one past the last
188938fd1498Szrj * bucket elements.
189038fd1498Szrj * @param __n The bucket index.
189138fd1498Szrj * @return A read/write local iterator.
189238fd1498Szrj */
189338fd1498Szrj local_iterator
189438fd1498Szrj end(size_type __n)
189538fd1498Szrj { return _M_h.end(__n); }
189638fd1498Szrj
189738fd1498Szrj //@{
189838fd1498Szrj /**
189938fd1498Szrj * @brief Returns a read-only (constant) iterator pointing to one past
190038fd1498Szrj * the last bucket elements.
190138fd1498Szrj * @param __n The bucket index.
190238fd1498Szrj * @return A read-only local iterator.
190338fd1498Szrj */
190438fd1498Szrj const_local_iterator
190538fd1498Szrj end(size_type __n) const
190638fd1498Szrj { return _M_h.end(__n); }
190738fd1498Szrj
190838fd1498Szrj const_local_iterator
190938fd1498Szrj cend(size_type __n) const
191038fd1498Szrj { return _M_h.cend(__n); }
191138fd1498Szrj //@}
191238fd1498Szrj
191338fd1498Szrj // hash policy.
191438fd1498Szrj
191538fd1498Szrj /// Returns the average number of elements per bucket.
191638fd1498Szrj float
191738fd1498Szrj load_factor() const noexcept
191838fd1498Szrj { return _M_h.load_factor(); }
191938fd1498Szrj
192038fd1498Szrj /// Returns a positive number that the %unordered_multimap tries to keep
192138fd1498Szrj /// the load factor less than or equal to.
192238fd1498Szrj float
192338fd1498Szrj max_load_factor() const noexcept
192438fd1498Szrj { return _M_h.max_load_factor(); }
192538fd1498Szrj
192638fd1498Szrj /**
192738fd1498Szrj * @brief Change the %unordered_multimap maximum load factor.
192838fd1498Szrj * @param __z The new maximum load factor.
192938fd1498Szrj */
193038fd1498Szrj void
193138fd1498Szrj max_load_factor(float __z)
193238fd1498Szrj { _M_h.max_load_factor(__z); }
193338fd1498Szrj
193438fd1498Szrj /**
193538fd1498Szrj * @brief May rehash the %unordered_multimap.
193638fd1498Szrj * @param __n The new number of buckets.
193738fd1498Szrj *
193838fd1498Szrj * Rehash will occur only if the new number of buckets respect the
193938fd1498Szrj * %unordered_multimap maximum load factor.
194038fd1498Szrj */
194138fd1498Szrj void
194238fd1498Szrj rehash(size_type __n)
194338fd1498Szrj { _M_h.rehash(__n); }
194438fd1498Szrj
194538fd1498Szrj /**
194638fd1498Szrj * @brief Prepare the %unordered_multimap for a specified number of
194738fd1498Szrj * elements.
194838fd1498Szrj * @param __n Number of elements required.
194938fd1498Szrj *
195038fd1498Szrj * Same as rehash(ceil(n / max_load_factor())).
195138fd1498Szrj */
195238fd1498Szrj void
195338fd1498Szrj reserve(size_type __n)
195438fd1498Szrj { _M_h.reserve(__n); }
195538fd1498Szrj
195638fd1498Szrj template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
195738fd1498Szrj typename _Alloc1>
195838fd1498Szrj friend bool
195938fd1498Szrj operator==(const unordered_multimap<_Key1, _Tp1,
196038fd1498Szrj _Hash1, _Pred1, _Alloc1>&,
196138fd1498Szrj const unordered_multimap<_Key1, _Tp1,
196238fd1498Szrj _Hash1, _Pred1, _Alloc1>&);
196338fd1498Szrj };
196438fd1498Szrj
196538fd1498Szrj #if __cpp_deduction_guides >= 201606
196638fd1498Szrj
196738fd1498Szrj template<typename _InputIterator,
196838fd1498Szrj typename _Hash = hash<__iter_key_t<_InputIterator>>,
196938fd1498Szrj typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
197038fd1498Szrj typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
197138fd1498Szrj typename = _RequireInputIter<_InputIterator>,
197238fd1498Szrj typename = _RequireAllocator<_Allocator>>
197338fd1498Szrj unordered_multimap(_InputIterator, _InputIterator,
197438fd1498Szrj unordered_multimap<int, int>::size_type = {},
197538fd1498Szrj _Hash = _Hash(), _Pred = _Pred(),
197638fd1498Szrj _Allocator = _Allocator())
197738fd1498Szrj -> unordered_multimap<__iter_key_t<_InputIterator>,
197838fd1498Szrj __iter_val_t<_InputIterator>, _Hash, _Pred,
197938fd1498Szrj _Allocator>;
198038fd1498Szrj
198138fd1498Szrj template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
198238fd1498Szrj typename _Pred = equal_to<_Key>,
198338fd1498Szrj typename _Allocator = allocator<pair<const _Key, _Tp>>,
198438fd1498Szrj typename = _RequireAllocator<_Allocator>>
198538fd1498Szrj unordered_multimap(initializer_list<pair<_Key, _Tp>>,
198638fd1498Szrj unordered_multimap<int, int>::size_type = {},
198738fd1498Szrj _Hash = _Hash(), _Pred = _Pred(),
198838fd1498Szrj _Allocator = _Allocator())
198938fd1498Szrj -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
199038fd1498Szrj
199138fd1498Szrj template<typename _InputIterator, typename _Allocator,
199238fd1498Szrj typename = _RequireInputIter<_InputIterator>,
199338fd1498Szrj typename = _RequireAllocator<_Allocator>>
199438fd1498Szrj unordered_multimap(_InputIterator, _InputIterator,
199538fd1498Szrj unordered_multimap<int, int>::size_type, _Allocator)
199638fd1498Szrj -> unordered_multimap<__iter_key_t<_InputIterator>,
199738fd1498Szrj __iter_val_t<_InputIterator>,
199838fd1498Szrj hash<__iter_key_t<_InputIterator>>,
199938fd1498Szrj equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
200038fd1498Szrj
200138fd1498Szrj template<typename _InputIterator, typename _Allocator,
200238fd1498Szrj typename = _RequireInputIter<_InputIterator>,
200338fd1498Szrj typename = _RequireAllocator<_Allocator>>
200438fd1498Szrj unordered_multimap(_InputIterator, _InputIterator, _Allocator)
200538fd1498Szrj -> unordered_multimap<__iter_key_t<_InputIterator>,
200638fd1498Szrj __iter_val_t<_InputIterator>,
200738fd1498Szrj hash<__iter_key_t<_InputIterator>>,
200838fd1498Szrj equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
200938fd1498Szrj
201038fd1498Szrj template<typename _InputIterator, typename _Hash, typename _Allocator,
201138fd1498Szrj typename = _RequireInputIter<_InputIterator>,
201238fd1498Szrj typename = _RequireAllocator<_Allocator>>
201338fd1498Szrj unordered_multimap(_InputIterator, _InputIterator,
201438fd1498Szrj unordered_multimap<int, int>::size_type, _Hash,
201538fd1498Szrj _Allocator)
201638fd1498Szrj -> unordered_multimap<__iter_key_t<_InputIterator>,
201738fd1498Szrj __iter_val_t<_InputIterator>, _Hash,
201838fd1498Szrj equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
201938fd1498Szrj
202038fd1498Szrj template<typename _Key, typename _Tp, typename _Allocator,
202138fd1498Szrj typename = _RequireAllocator<_Allocator>>
202238fd1498Szrj unordered_multimap(initializer_list<pair<_Key, _Tp>>,
202338fd1498Szrj unordered_multimap<int, int>::size_type,
202438fd1498Szrj _Allocator)
202538fd1498Szrj -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
202638fd1498Szrj
202738fd1498Szrj template<typename _Key, typename _Tp, typename _Allocator,
202838fd1498Szrj typename = _RequireAllocator<_Allocator>>
202938fd1498Szrj unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
203038fd1498Szrj -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
203138fd1498Szrj
203238fd1498Szrj template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
203338fd1498Szrj typename = _RequireAllocator<_Allocator>>
203438fd1498Szrj unordered_multimap(initializer_list<pair<_Key, _Tp>>,
203538fd1498Szrj unordered_multimap<int, int>::size_type,
203638fd1498Szrj _Hash, _Allocator)
203738fd1498Szrj -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
203838fd1498Szrj
203938fd1498Szrj #endif
204038fd1498Szrj
204138fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
204238fd1498Szrj inline void
204338fd1498Szrj swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
204438fd1498Szrj unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
204538fd1498Szrj noexcept(noexcept(__x.swap(__y)))
204638fd1498Szrj { __x.swap(__y); }
204738fd1498Szrj
204838fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
204938fd1498Szrj inline void
205038fd1498Szrj swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
205138fd1498Szrj unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
205238fd1498Szrj noexcept(noexcept(__x.swap(__y)))
205338fd1498Szrj { __x.swap(__y); }
205438fd1498Szrj
205538fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
205638fd1498Szrj inline bool
205738fd1498Szrj operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
205838fd1498Szrj const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
205938fd1498Szrj { return __x._M_h._M_equal(__y._M_h); }
206038fd1498Szrj
206138fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
206238fd1498Szrj inline bool
206338fd1498Szrj operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
206438fd1498Szrj const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
206538fd1498Szrj { return !(__x == __y); }
206638fd1498Szrj
206738fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
206838fd1498Szrj inline bool
206938fd1498Szrj operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
207038fd1498Szrj const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
207138fd1498Szrj { return __x._M_h._M_equal(__y._M_h); }
207238fd1498Szrj
207338fd1498Szrj template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
207438fd1498Szrj inline bool
207538fd1498Szrj operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
207638fd1498Szrj const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
207738fd1498Szrj { return !(__x == __y); }
207838fd1498Szrj
207938fd1498Szrj _GLIBCXX_END_NAMESPACE_CONTAINER
208038fd1498Szrj
208138fd1498Szrj #if __cplusplus > 201402L
208238fd1498Szrj // Allow std::unordered_map access to internals of compatible maps.
208338fd1498Szrj template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
208438fd1498Szrj typename _Alloc, typename _Hash2, typename _Eq2>
208538fd1498Szrj struct _Hash_merge_helper<
208638fd1498Szrj _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
208738fd1498Szrj _Hash2, _Eq2>
208838fd1498Szrj {
208938fd1498Szrj private:
209038fd1498Szrj template<typename... _Tp>
209138fd1498Szrj using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
209238fd1498Szrj template<typename... _Tp>
209338fd1498Szrj using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
209438fd1498Szrj
209538fd1498Szrj friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
209638fd1498Szrj
209738fd1498Szrj static auto&
209838fd1498Szrj _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
209938fd1498Szrj { return __map._M_h; }
210038fd1498Szrj
210138fd1498Szrj static auto&
210238fd1498Szrj _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
210338fd1498Szrj { return __map._M_h; }
210438fd1498Szrj };
210538fd1498Szrj
210638fd1498Szrj // Allow std::unordered_multimap access to internals of compatible maps.
210738fd1498Szrj template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
210838fd1498Szrj typename _Alloc, typename _Hash2, typename _Eq2>
210938fd1498Szrj struct _Hash_merge_helper<
211038fd1498Szrj _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
211138fd1498Szrj _Hash2, _Eq2>
211238fd1498Szrj {
211338fd1498Szrj private:
211438fd1498Szrj template<typename... _Tp>
211538fd1498Szrj using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
211638fd1498Szrj template<typename... _Tp>
211738fd1498Szrj using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
211838fd1498Szrj
211938fd1498Szrj friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
212038fd1498Szrj
212138fd1498Szrj static auto&
212238fd1498Szrj _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
212338fd1498Szrj { return __map._M_h; }
212438fd1498Szrj
212538fd1498Szrj static auto&
212638fd1498Szrj _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
212738fd1498Szrj { return __map._M_h; }
212838fd1498Szrj };
212938fd1498Szrj #endif // C++17
213038fd1498Szrj
213138fd1498Szrj _GLIBCXX_END_NAMESPACE_VERSION
213238fd1498Szrj } // namespace std
213338fd1498Szrj
213438fd1498Szrj #endif /* _UNORDERED_MAP_H */
2135