1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2022 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/unordered_map.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_map}
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
33 namespace std
_GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
38 /// Base types for unordered_map.
40 using __umap_traits
= __detail::_Hashtable_traits
<_Cache
, false, true>;
42 template<typename _Key
,
44 typename _Hash
= hash
<_Key
>,
45 typename _Pred
= std::equal_to
<_Key
>,
46 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
47 typename _Tr
= __umap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
48 using __umap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
49 _Alloc
, __detail::_Select1st
,
51 __detail::_Mod_range_hashing
,
52 __detail::_Default_ranged_hash
,
53 __detail::_Prime_rehash_policy
, _Tr
>;
55 /// Base types for unordered_multimap.
57 using __ummap_traits
= __detail::_Hashtable_traits
<_Cache
, false, false>;
59 template<typename _Key
,
61 typename _Hash
= hash
<_Key
>,
62 typename _Pred
= std::equal_to
<_Key
>,
63 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
64 typename _Tr
= __ummap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
65 using __ummap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
66 _Alloc
, __detail::_Select1st
,
68 __detail::_Mod_range_hashing
,
69 __detail::_Default_ranged_hash
,
70 __detail::_Prime_rehash_policy
, _Tr
>;
72 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
73 class unordered_multimap
;
76 * @brief A standard container composed of unique keys (containing
77 * at most one of each key value) that associates values of another type
80 * @ingroup unordered_associative_containers
82 * @tparam _Key Type of key objects.
83 * @tparam _Tp Type of mapped objects.
84 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
85 * @tparam _Pred Predicate function object type, defaults
86 * to equal_to<_Value>.
87 * @tparam _Alloc Allocator type, defaults to
88 * std::allocator<std::pair<const _Key, _Tp>>.
90 * Meets the requirements of a <a href="tables.html#65">container</a>, and
91 * <a href="tables.html#xx">unordered associative container</a>
93 * The resulting value type of the container is std::pair<const _Key, _Tp>.
95 * Base is _Hashtable, dispatched at compile time via template
96 * alias __umap_hashtable.
98 template<typename _Key
, typename _Tp
,
99 typename _Hash
= hash
<_Key
>,
100 typename _Pred
= equal_to
<_Key
>,
101 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
104 typedef __umap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
111 typedef typename
_Hashtable::key_type key_type
;
112 typedef typename
_Hashtable::value_type value_type
;
113 typedef typename
_Hashtable::mapped_type mapped_type
;
114 typedef typename
_Hashtable::hasher hasher
;
115 typedef typename
_Hashtable::key_equal key_equal
;
116 typedef typename
_Hashtable::allocator_type allocator_type
;
120 /// Iterator-related typedefs.
121 typedef typename
_Hashtable::pointer pointer
;
122 typedef typename
_Hashtable::const_pointer const_pointer
;
123 typedef typename
_Hashtable::reference reference
;
124 typedef typename
_Hashtable::const_reference const_reference
;
125 typedef typename
_Hashtable::iterator iterator
;
126 typedef typename
_Hashtable::const_iterator const_iterator
;
127 typedef typename
_Hashtable::local_iterator local_iterator
;
128 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
129 typedef typename
_Hashtable::size_type size_type
;
130 typedef typename
_Hashtable::difference_type difference_type
;
133 #if __cplusplus > 201402L
134 using node_type
= typename
_Hashtable::node_type
;
135 using insert_return_type
= typename
_Hashtable::insert_return_type
;
138 //construct/destroy/copy
140 /// Default constructor.
141 unordered_map() = default;
144 * @brief Default constructor creates no elements.
145 * @param __n Minimal initial number of buckets.
146 * @param __hf A hash functor.
147 * @param __eql A key equality functor.
148 * @param __a An allocator object.
151 unordered_map(size_type __n
,
152 const hasher
& __hf
= hasher(),
153 const key_equal
& __eql
= key_equal(),
154 const allocator_type
& __a
= allocator_type())
155 : _M_h(__n
, __hf
, __eql
, __a
)
159 * @brief Builds an %unordered_map from a range.
160 * @param __first An input iterator.
161 * @param __last An input iterator.
162 * @param __n Minimal initial number of buckets.
163 * @param __hf A hash functor.
164 * @param __eql A key equality functor.
165 * @param __a An allocator object.
167 * Create an %unordered_map consisting of copies of the elements from
168 * [__first,__last). This is linear in N (where N is
169 * distance(__first,__last)).
171 template<typename _InputIterator
>
172 unordered_map(_InputIterator __first
, _InputIterator __last
,
174 const hasher
& __hf
= hasher(),
175 const key_equal
& __eql
= key_equal(),
176 const allocator_type
& __a
= allocator_type())
177 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
180 /// Copy constructor.
181 unordered_map(const unordered_map
&) = default;
183 /// Move constructor.
184 unordered_map(unordered_map
&&) = default;
187 * @brief Creates an %unordered_map with no elements.
188 * @param __a An allocator object.
191 unordered_map(const allocator_type
& __a
)
196 * @brief Copy constructor with allocator argument.
197 * @param __uset Input %unordered_map to copy.
198 * @param __a An allocator object.
200 unordered_map(const unordered_map
& __umap
,
201 const allocator_type
& __a
)
202 : _M_h(__umap
._M_h
, __a
)
206 * @brief Move constructor with allocator argument.
207 * @param __uset Input %unordered_map to move.
208 * @param __a An allocator object.
210 unordered_map(unordered_map
&& __umap
,
211 const allocator_type
& __a
)
212 noexcept( noexcept(_Hashtable(std::move(__umap
._M_h
), __a
)) )
213 : _M_h(std::move(__umap
._M_h
), __a
)
217 * @brief Builds an %unordered_map from an initializer_list.
218 * @param __l An initializer_list.
219 * @param __n Minimal initial number of buckets.
220 * @param __hf A hash functor.
221 * @param __eql A key equality functor.
222 * @param __a An allocator object.
224 * Create an %unordered_map consisting of copies of the elements in the
225 * list. This is linear in N (where N is @a __l.size()).
227 unordered_map(initializer_list
<value_type
> __l
,
229 const hasher
& __hf
= hasher(),
230 const key_equal
& __eql
= key_equal(),
231 const allocator_type
& __a
= allocator_type())
232 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
235 unordered_map(size_type __n
, const allocator_type
& __a
)
236 : unordered_map(__n
, hasher(), key_equal(), __a
)
239 unordered_map(size_type __n
, const hasher
& __hf
,
240 const allocator_type
& __a
)
241 : unordered_map(__n
, __hf
, key_equal(), __a
)
244 template<typename _InputIterator
>
245 unordered_map(_InputIterator __first
, _InputIterator __last
,
247 const allocator_type
& __a
)
248 : unordered_map(__first
, __last
, __n
, hasher(), key_equal(), __a
)
251 template<typename _InputIterator
>
252 unordered_map(_InputIterator __first
, _InputIterator __last
,
253 size_type __n
, const hasher
& __hf
,
254 const allocator_type
& __a
)
255 : unordered_map(__first
, __last
, __n
, __hf
, key_equal(), __a
)
258 unordered_map(initializer_list
<value_type
> __l
,
260 const allocator_type
& __a
)
261 : unordered_map(__l
, __n
, hasher(), key_equal(), __a
)
264 unordered_map(initializer_list
<value_type
> __l
,
265 size_type __n
, const hasher
& __hf
,
266 const allocator_type
& __a
)
267 : unordered_map(__l
, __n
, __hf
, key_equal(), __a
)
270 /// Copy assignment operator.
272 operator=(const unordered_map
&) = default;
274 /// Move assignment operator.
276 operator=(unordered_map
&&) = default;
279 * @brief %Unordered_map list assignment operator.
280 * @param __l An initializer_list.
282 * This function fills an %unordered_map with copies of the elements in
283 * the initializer list @a __l.
285 * Note that the assignment completely changes the %unordered_map and
286 * that the resulting %unordered_map's size is the same as the number
287 * of elements assigned.
290 operator=(initializer_list
<value_type
> __l
)
296 /// Returns the allocator object used by the %unordered_map.
298 get_allocator() const noexcept
299 { return _M_h
.get_allocator(); }
301 // size and capacity:
303 /// Returns true if the %unordered_map is empty.
304 _GLIBCXX_NODISCARD
bool
305 empty() const noexcept
306 { return _M_h
.empty(); }
308 /// Returns the size of the %unordered_map.
310 size() const noexcept
311 { return _M_h
.size(); }
313 /// Returns the maximum size of the %unordered_map.
315 max_size() const noexcept
316 { return _M_h
.max_size(); }
321 * Returns a read/write iterator that points to the first element in the
326 { return _M_h
.begin(); }
330 * Returns a read-only (constant) iterator that points to the first
331 * element in the %unordered_map.
334 begin() const noexcept
335 { return _M_h
.begin(); }
338 cbegin() const noexcept
339 { return _M_h
.begin(); }
343 * Returns a read/write iterator that points one past the last element in
344 * the %unordered_map.
348 { return _M_h
.end(); }
352 * Returns a read-only (constant) iterator that points one past the last
353 * element in the %unordered_map.
357 { return _M_h
.end(); }
360 cend() const noexcept
361 { return _M_h
.end(); }
367 * @brief Attempts to build and insert a std::pair into the
370 * @param __args Arguments used to generate a new pair instance (see
371 * std::piecewise_contruct for passing arguments to each
372 * part of the pair constructor).
374 * @return A pair, of which the first element is an iterator that points
375 * to the possibly inserted pair, and the second is a bool that
376 * is true if the pair was actually inserted.
378 * This function attempts to build and insert a (key, value) %pair into
379 * the %unordered_map.
380 * An %unordered_map relies on unique keys and thus a %pair is only
381 * inserted if its first element (the key) is not already present in the
384 * Insertion requires amortized constant time.
386 template<typename
... _Args
>
387 std::pair
<iterator
, bool>
388 emplace(_Args
&&... __args
)
389 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
392 * @brief Attempts to build and insert a std::pair into the
395 * @param __pos An iterator that serves as a hint as to where the pair
396 * should be inserted.
397 * @param __args Arguments used to generate a new pair instance (see
398 * std::piecewise_contruct for passing arguments to each
399 * part of the pair constructor).
400 * @return An iterator that points to the element with key of the
401 * std::pair built from @a __args (may or may not be that
404 * This function is not concerned about whether the insertion took place,
405 * and thus does not return a boolean like the single-argument emplace()
407 * Note that the first parameter is only a hint and can potentially
408 * improve the performance of the insertion process. A bad hint would
409 * cause no gains in efficiency.
412 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
413 * for more on @a hinting.
415 * Insertion requires amortized constant time.
417 template<typename
... _Args
>
419 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
420 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
422 #if __cplusplus > 201402L
425 extract(const_iterator __pos
)
427 __glibcxx_assert(__pos
!= end());
428 return _M_h
.extract(__pos
);
433 extract(const key_type
& __key
)
434 { return _M_h
.extract(__key
); }
436 /// Re-insert an extracted node.
438 insert(node_type
&& __nh
)
439 { return _M_h
._M_reinsert_node(std::move(__nh
)); }
441 /// Re-insert an extracted node.
443 insert(const_iterator
, node_type
&& __nh
)
444 { return _M_h
._M_reinsert_node(std::move(__nh
)).position
; }
446 #define __cpp_lib_unordered_map_try_emplace 201411
448 * @brief Attempts to build and insert a std::pair into the
451 * @param __k Key to use for finding a possibly existing pair in
453 * @param __args Arguments used to generate the .second for a
456 * @return A pair, of which the first element is an iterator that points
457 * to the possibly inserted pair, and the second is a bool that
458 * is true if the pair was actually inserted.
460 * This function attempts to build and insert a (key, value) %pair into
461 * the %unordered_map.
462 * An %unordered_map relies on unique keys and thus a %pair is only
463 * inserted if its first element (the key) is not already present in the
465 * If a %pair is not inserted, this function has no effect.
467 * Insertion requires amortized constant time.
469 template <typename
... _Args
>
471 try_emplace(const key_type
& __k
, _Args
&&... __args
)
473 return _M_h
.try_emplace(cend(), __k
, std::forward
<_Args
>(__args
)...);
476 // move-capable overload
477 template <typename
... _Args
>
479 try_emplace(key_type
&& __k
, _Args
&&... __args
)
481 return _M_h
.try_emplace(cend(), std::move(__k
),
482 std::forward
<_Args
>(__args
)...);
486 * @brief Attempts to build and insert a std::pair into the
489 * @param __hint An iterator that serves as a hint as to where the pair
490 * should be inserted.
491 * @param __k Key to use for finding a possibly existing pair in
493 * @param __args Arguments used to generate the .second for a
495 * @return An iterator that points to the element with key of the
496 * std::pair built from @a __args (may or may not be that
499 * This function is not concerned about whether the insertion took place,
500 * and thus does not return a boolean like the single-argument emplace()
501 * does. However, if insertion did not take place,
502 * this function has no effect.
503 * Note that the first parameter is only a hint and can potentially
504 * improve the performance of the insertion process. A bad hint would
505 * cause no gains in efficiency.
508 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
509 * for more on @a hinting.
511 * Insertion requires amortized constant time.
513 template <typename
... _Args
>
515 try_emplace(const_iterator __hint
, const key_type
& __k
,
518 return _M_h
.try_emplace(__hint
, __k
,
519 std::forward
<_Args
>(__args
)...).first
;
522 // move-capable overload
523 template <typename
... _Args
>
525 try_emplace(const_iterator __hint
, key_type
&& __k
, _Args
&&... __args
)
527 return _M_h
.try_emplace(__hint
, std::move(__k
),
528 std::forward
<_Args
>(__args
)...).first
;
534 * @brief Attempts to insert a std::pair into the %unordered_map.
536 * @param __x Pair to be inserted (see std::make_pair for easy
537 * creation of pairs).
539 * @return A pair, of which the first element is an iterator that
540 * points to the possibly inserted pair, and the second is
541 * a bool that is true if the pair was actually inserted.
543 * This function attempts to insert a (key, value) %pair into the
544 * %unordered_map. An %unordered_map relies on unique keys and thus a
545 * %pair is only inserted if its first element (the key) is not already
546 * present in the %unordered_map.
548 * Insertion requires amortized constant time.
550 std::pair
<iterator
, bool>
551 insert(const value_type
& __x
)
552 { return _M_h
.insert(__x
); }
554 // _GLIBCXX_RESOLVE_LIB_DEFECTS
555 // 2354. Unnecessary copying when inserting into maps with braced-init
556 std::pair
<iterator
, bool>
557 insert(value_type
&& __x
)
558 { return _M_h
.insert(std::move(__x
)); }
560 template<typename _Pair
>
561 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
,
562 pair
<iterator
, bool>>
564 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
569 * @brief Attempts to insert a std::pair into the %unordered_map.
570 * @param __hint An iterator that serves as a hint as to where the
571 * pair should be inserted.
572 * @param __x Pair to be inserted (see std::make_pair for easy creation
574 * @return An iterator that points to the element with key of
575 * @a __x (may or may not be the %pair passed in).
577 * This function is not concerned about whether the insertion took place,
578 * and thus does not return a boolean like the single-argument insert()
579 * does. Note that the first parameter is only a hint and can
580 * potentially improve the performance of the insertion process. A bad
581 * hint would cause no gains in efficiency.
584 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
585 * for more on @a hinting.
587 * Insertion requires amortized constant time.
590 insert(const_iterator __hint
, const value_type
& __x
)
591 { return _M_h
.insert(__hint
, __x
); }
593 // _GLIBCXX_RESOLVE_LIB_DEFECTS
594 // 2354. Unnecessary copying when inserting into maps with braced-init
596 insert(const_iterator __hint
, value_type
&& __x
)
597 { return _M_h
.insert(__hint
, std::move(__x
)); }
599 template<typename _Pair
>
600 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
601 insert(const_iterator __hint
, _Pair
&& __x
)
602 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
606 * @brief A template function that attempts to insert a range of
608 * @param __first Iterator pointing to the start of the range to be
610 * @param __last Iterator pointing to the end of the range.
612 * Complexity similar to that of the range constructor.
614 template<typename _InputIterator
>
616 insert(_InputIterator __first
, _InputIterator __last
)
617 { _M_h
.insert(__first
, __last
); }
620 * @brief Attempts to insert a list of elements into the %unordered_map.
621 * @param __l A std::initializer_list<value_type> of elements
624 * Complexity similar to that of the range constructor.
627 insert(initializer_list
<value_type
> __l
)
628 { _M_h
.insert(__l
); }
631 #if __cplusplus > 201402L
633 * @brief Attempts to insert a std::pair into the %unordered_map.
634 * @param __k Key to use for finding a possibly existing pair in
636 * @param __obj Argument used to generate the .second for a pair
639 * @return A pair, of which the first element is an iterator that
640 * points to the possibly inserted pair, and the second is
641 * a bool that is true if the pair was actually inserted.
643 * This function attempts to insert a (key, value) %pair into the
644 * %unordered_map. An %unordered_map relies on unique keys and thus a
645 * %pair is only inserted if its first element (the key) is not already
646 * present in the %unordered_map.
647 * If the %pair was already in the %unordered_map, the .second of
648 * the %pair is assigned from __obj.
650 * Insertion requires amortized constant time.
652 template <typename _Obj
>
654 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
656 auto __ret
= _M_h
.try_emplace(cend(), __k
,
657 std::forward
<_Obj
>(__obj
));
659 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
663 // move-capable overload
664 template <typename _Obj
>
666 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
668 auto __ret
= _M_h
.try_emplace(cend(), std::move(__k
),
669 std::forward
<_Obj
>(__obj
));
671 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
676 * @brief Attempts to insert a std::pair into the %unordered_map.
677 * @param __hint An iterator that serves as a hint as to where the
678 * pair should be inserted.
679 * @param __k Key to use for finding a possibly existing pair in
681 * @param __obj Argument used to generate the .second for a pair
683 * @return An iterator that points to the element with key of
684 * @a __x (may or may not be the %pair passed in).
686 * This function is not concerned about whether the insertion took place,
687 * and thus does not return a boolean like the single-argument insert()
689 * If the %pair was already in the %unordered map, the .second of
690 * the %pair is assigned from __obj.
691 * Note that the first parameter is only a hint and can
692 * potentially improve the performance of the insertion process. A bad
693 * hint would cause no gains in efficiency.
696 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
697 * for more on @a hinting.
699 * Insertion requires amortized constant time.
701 template <typename _Obj
>
703 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
706 auto __ret
= _M_h
.try_emplace(__hint
, __k
, std::forward
<_Obj
>(__obj
));
708 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
712 // move-capable overload
713 template <typename _Obj
>
715 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
717 auto __ret
= _M_h
.try_emplace(__hint
, std::move(__k
),
718 std::forward
<_Obj
>(__obj
));
720 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
727 * @brief Erases an element from an %unordered_map.
728 * @param __position An iterator pointing to the element to be erased.
729 * @return An iterator pointing to the element immediately following
730 * @a __position prior to the element being erased. If no such
731 * element exists, end() is returned.
733 * This function erases an element, pointed to by the given iterator,
734 * from an %unordered_map.
735 * Note that this function only erases the element, and that if the
736 * element is itself a pointer, the pointed-to memory is not touched in
737 * any way. Managing the pointer is the user's responsibility.
740 erase(const_iterator __position
)
741 { return _M_h
.erase(__position
); }
745 erase(iterator __position
)
746 { return _M_h
.erase(__position
); }
750 * @brief Erases elements according to the provided key.
751 * @param __x Key of element to be erased.
752 * @return The number of elements erased.
754 * This function erases all the elements located by the given key from
755 * an %unordered_map. For an %unordered_map the result of this function
756 * can only be 0 (not present) or 1 (present).
757 * Note that this function only erases the element, and that if the
758 * element is itself a pointer, the pointed-to memory is not touched in
759 * any way. Managing the pointer is the user's responsibility.
762 erase(const key_type
& __x
)
763 { return _M_h
.erase(__x
); }
766 * @brief Erases a [__first,__last) range of elements from an
768 * @param __first Iterator pointing to the start of the range to be
770 * @param __last Iterator pointing to the end of the range to
772 * @return The iterator @a __last.
774 * This function erases a sequence of elements from an %unordered_map.
775 * Note that this function only erases the elements, and that if
776 * the element is itself a pointer, the pointed-to memory is not touched
777 * in any way. Managing the pointer is the user's responsibility.
780 erase(const_iterator __first
, const_iterator __last
)
781 { return _M_h
.erase(__first
, __last
); }
784 * Erases all elements in an %unordered_map.
785 * Note that this function only erases the elements, and that if the
786 * elements themselves are pointers, the pointed-to memory is not touched
787 * in any way. Managing the pointer is the user's responsibility.
794 * @brief Swaps data with another %unordered_map.
795 * @param __x An %unordered_map of the same element and allocator
798 * This exchanges the elements between two %unordered_map in constant
800 * Note that the global std::swap() function is specialized such that
801 * std::swap(m1,m2) will feed to this function.
804 swap(unordered_map
& __x
)
805 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
806 { _M_h
.swap(__x
._M_h
); }
808 #if __cplusplus > 201402L
809 template<typename
, typename
, typename
>
810 friend class std::_Hash_merge_helper
;
812 template<typename _H2
, typename _P2
>
814 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
816 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
817 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
820 template<typename _H2
, typename _P2
>
822 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
825 template<typename _H2
, typename _P2
>
827 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
829 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
830 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
833 template<typename _H2
, typename _P2
>
835 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
841 /// Returns the hash functor object with which the %unordered_map was
844 hash_function() const
845 { return _M_h
.hash_function(); }
847 /// Returns the key comparison object with which the %unordered_map was
851 { return _M_h
.key_eq(); }
857 * @brief Tries to locate an element in an %unordered_map.
858 * @param __x Key to be located.
859 * @return Iterator pointing to sought-after element, or end() if not
862 * This function takes a key and tries to locate the element with which
863 * the key matches. If successful the function returns an iterator
864 * pointing to the sought after element. If unsuccessful it returns the
865 * past-the-end ( @c end() ) iterator.
868 find(const key_type
& __x
)
869 { return _M_h
.find(__x
); }
871 #if __cplusplus > 201703L
872 template<typename _Kt
>
874 find(const _Kt
& __x
) -> decltype(_M_h
._M_find_tr(__x
))
875 { return _M_h
._M_find_tr(__x
); }
879 find(const key_type
& __x
) const
880 { return _M_h
.find(__x
); }
882 #if __cplusplus > 201703L
883 template<typename _Kt
>
885 find(const _Kt
& __x
) const -> decltype(_M_h
._M_find_tr(__x
))
886 { return _M_h
._M_find_tr(__x
); }
892 * @brief Finds the number of elements.
893 * @param __x Key to count.
894 * @return Number of elements with specified key.
896 * This function only makes sense for %unordered_multimap; for
897 * %unordered_map the result will either be 0 (not present) or 1
901 count(const key_type
& __x
) const
902 { return _M_h
.count(__x
); }
904 #if __cplusplus > 201703L
905 template<typename _Kt
>
907 count(const _Kt
& __x
) const -> decltype(_M_h
._M_count_tr(__x
))
908 { return _M_h
._M_count_tr(__x
); }
912 #if __cplusplus > 201703L
915 * @brief Finds whether an element with the given key exists.
916 * @param __x Key of elements to be located.
917 * @return True if there is any element with the specified key.
920 contains(const key_type
& __x
) const
921 { return _M_h
.find(__x
) != _M_h
.end(); }
923 template<typename _Kt
>
925 contains(const _Kt
& __x
) const
926 -> decltype(_M_h
._M_find_tr(__x
), void(), true)
927 { return _M_h
._M_find_tr(__x
) != _M_h
.end(); }
933 * @brief Finds a subsequence matching given key.
934 * @param __x Key to be located.
935 * @return Pair of iterators that possibly points to the subsequence
936 * matching given key.
938 * This function probably only makes sense for %unordered_multimap.
940 std::pair
<iterator
, iterator
>
941 equal_range(const key_type
& __x
)
942 { return _M_h
.equal_range(__x
); }
944 #if __cplusplus > 201703L
945 template<typename _Kt
>
947 equal_range(const _Kt
& __x
)
948 -> decltype(_M_h
._M_equal_range_tr(__x
))
949 { return _M_h
._M_equal_range_tr(__x
); }
952 std::pair
<const_iterator
, const_iterator
>
953 equal_range(const key_type
& __x
) const
954 { return _M_h
.equal_range(__x
); }
956 #if __cplusplus > 201703L
957 template<typename _Kt
>
959 equal_range(const _Kt
& __x
) const
960 -> decltype(_M_h
._M_equal_range_tr(__x
))
961 { return _M_h
._M_equal_range_tr(__x
); }
967 * @brief Subscript ( @c [] ) access to %unordered_map data.
968 * @param __k The key for which data should be retrieved.
969 * @return A reference to the data of the (key,data) %pair.
971 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
972 * data associated with the key specified in subscript. If the key does
973 * not exist, a pair with that key is created using default values, which
976 * Lookup requires constant time.
979 operator[](const key_type
& __k
)
980 { return _M_h
[__k
]; }
983 operator[](key_type
&& __k
)
984 { return _M_h
[std::move(__k
)]; }
989 * @brief Access to %unordered_map data.
990 * @param __k The key for which data should be retrieved.
991 * @return A reference to the data whose key is equal to @a __k, if
992 * such a data is present in the %unordered_map.
993 * @throw std::out_of_range If no such data is present.
996 at(const key_type
& __k
)
997 { return _M_h
.at(__k
); }
1000 at(const key_type
& __k
) const
1001 { return _M_h
.at(__k
); }
1004 // bucket interface.
1006 /// Returns the number of buckets of the %unordered_map.
1008 bucket_count() const noexcept
1009 { return _M_h
.bucket_count(); }
1011 /// Returns the maximum number of buckets of the %unordered_map.
1013 max_bucket_count() const noexcept
1014 { return _M_h
.max_bucket_count(); }
1017 * @brief Returns the number of elements in a given bucket.
1018 * @param __n A bucket index.
1019 * @return The number of elements in the bucket.
1022 bucket_size(size_type __n
) const
1023 { return _M_h
.bucket_size(__n
); }
1026 * @brief Returns the bucket index of a given element.
1027 * @param __key A key instance.
1028 * @return The key bucket index.
1031 bucket(const key_type
& __key
) const
1032 { return _M_h
.bucket(__key
); }
1035 * @brief Returns a read/write iterator pointing to the first bucket
1037 * @param __n The bucket index.
1038 * @return A read/write local iterator.
1041 begin(size_type __n
)
1042 { return _M_h
.begin(__n
); }
1046 * @brief Returns a read-only (constant) iterator pointing to the first
1048 * @param __n The bucket index.
1049 * @return A read-only local iterator.
1051 const_local_iterator
1052 begin(size_type __n
) const
1053 { return _M_h
.begin(__n
); }
1055 const_local_iterator
1056 cbegin(size_type __n
) const
1057 { return _M_h
.cbegin(__n
); }
1061 * @brief Returns a read/write iterator pointing to one past the last
1063 * @param __n The bucket index.
1064 * @return A read/write local iterator.
1068 { return _M_h
.end(__n
); }
1072 * @brief Returns a read-only (constant) iterator pointing to one past
1073 * the last bucket elements.
1074 * @param __n The bucket index.
1075 * @return A read-only local iterator.
1077 const_local_iterator
1078 end(size_type __n
) const
1079 { return _M_h
.end(__n
); }
1081 const_local_iterator
1082 cend(size_type __n
) const
1083 { return _M_h
.cend(__n
); }
1088 /// Returns the average number of elements per bucket.
1090 load_factor() const noexcept
1091 { return _M_h
.load_factor(); }
1093 /// Returns a positive number that the %unordered_map tries to keep the
1094 /// load factor less than or equal to.
1096 max_load_factor() const noexcept
1097 { return _M_h
.max_load_factor(); }
1100 * @brief Change the %unordered_map maximum load factor.
1101 * @param __z The new maximum load factor.
1104 max_load_factor(float __z
)
1105 { _M_h
.max_load_factor(__z
); }
1108 * @brief May rehash the %unordered_map.
1109 * @param __n The new number of buckets.
1111 * Rehash will occur only if the new number of buckets respect the
1112 * %unordered_map maximum load factor.
1115 rehash(size_type __n
)
1116 { _M_h
.rehash(__n
); }
1119 * @brief Prepare the %unordered_map for a specified number of
1121 * @param __n Number of elements required.
1123 * Same as rehash(ceil(n / max_load_factor())).
1126 reserve(size_type __n
)
1127 { _M_h
.reserve(__n
); }
1129 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1132 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1133 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1136 #if __cpp_deduction_guides >= 201606
1138 template<typename _InputIterator
,
1139 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1140 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1141 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1142 typename
= _RequireInputIter
<_InputIterator
>,
1143 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1144 typename
= _RequireNotAllocator
<_Pred
>,
1145 typename
= _RequireAllocator
<_Allocator
>>
1146 unordered_map(_InputIterator
, _InputIterator
,
1147 typename unordered_map
<int, int>::size_type
= {},
1148 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1149 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1150 __iter_val_t
<_InputIterator
>,
1151 _Hash
, _Pred
, _Allocator
>;
1153 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
1154 typename _Pred
= equal_to
<_Key
>,
1155 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
1156 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1157 typename
= _RequireNotAllocator
<_Pred
>,
1158 typename
= _RequireAllocator
<_Allocator
>>
1159 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1160 typename unordered_map
<int, int>::size_type
= {},
1161 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1162 -> unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
1164 template<typename _InputIterator
, typename _Allocator
,
1165 typename
= _RequireInputIter
<_InputIterator
>,
1166 typename
= _RequireAllocator
<_Allocator
>>
1167 unordered_map(_InputIterator
, _InputIterator
,
1168 typename unordered_map
<int, int>::size_type
, _Allocator
)
1169 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1170 __iter_val_t
<_InputIterator
>,
1171 hash
<__iter_key_t
<_InputIterator
>>,
1172 equal_to
<__iter_key_t
<_InputIterator
>>,
1175 template<typename _InputIterator
, typename _Allocator
,
1176 typename
= _RequireInputIter
<_InputIterator
>,
1177 typename
= _RequireAllocator
<_Allocator
>>
1178 unordered_map(_InputIterator
, _InputIterator
, _Allocator
)
1179 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1180 __iter_val_t
<_InputIterator
>,
1181 hash
<__iter_key_t
<_InputIterator
>>,
1182 equal_to
<__iter_key_t
<_InputIterator
>>,
1185 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
1186 typename
= _RequireInputIter
<_InputIterator
>,
1187 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1188 typename
= _RequireAllocator
<_Allocator
>>
1189 unordered_map(_InputIterator
, _InputIterator
,
1190 typename unordered_map
<int, int>::size_type
,
1192 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1193 __iter_val_t
<_InputIterator
>, _Hash
,
1194 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
1196 template<typename _Key
, typename _Tp
, typename _Allocator
,
1197 typename
= _RequireAllocator
<_Allocator
>>
1198 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1199 typename unordered_map
<int, int>::size_type
,
1201 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1203 template<typename _Key
, typename _Tp
, typename _Allocator
,
1204 typename
= _RequireAllocator
<_Allocator
>>
1205 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
1206 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1208 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
1209 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1210 typename
= _RequireAllocator
<_Allocator
>>
1211 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1212 typename unordered_map
<int, int>::size_type
,
1214 -> unordered_map
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
1219 * @brief A standard container composed of equivalent keys
1220 * (possibly containing multiple of each key value) that associates
1221 * values of another type with the keys.
1223 * @ingroup unordered_associative_containers
1225 * @tparam _Key Type of key objects.
1226 * @tparam _Tp Type of mapped objects.
1227 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1228 * @tparam _Pred Predicate function object type, defaults
1229 * to equal_to<_Value>.
1230 * @tparam _Alloc Allocator type, defaults to
1231 * std::allocator<std::pair<const _Key, _Tp>>.
1233 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1234 * <a href="tables.html#xx">unordered associative container</a>
1236 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1238 * Base is _Hashtable, dispatched at compile time via template
1239 * alias __ummap_hashtable.
1241 template<typename _Key
, typename _Tp
,
1242 typename _Hash
= hash
<_Key
>,
1243 typename _Pred
= equal_to
<_Key
>,
1244 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
1245 class unordered_multimap
1247 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1253 /// Public typedefs.
1254 typedef typename
_Hashtable::key_type key_type
;
1255 typedef typename
_Hashtable::value_type value_type
;
1256 typedef typename
_Hashtable::mapped_type mapped_type
;
1257 typedef typename
_Hashtable::hasher hasher
;
1258 typedef typename
_Hashtable::key_equal key_equal
;
1259 typedef typename
_Hashtable::allocator_type allocator_type
;
1263 /// Iterator-related typedefs.
1264 typedef typename
_Hashtable::pointer pointer
;
1265 typedef typename
_Hashtable::const_pointer const_pointer
;
1266 typedef typename
_Hashtable::reference reference
;
1267 typedef typename
_Hashtable::const_reference const_reference
;
1268 typedef typename
_Hashtable::iterator iterator
;
1269 typedef typename
_Hashtable::const_iterator const_iterator
;
1270 typedef typename
_Hashtable::local_iterator local_iterator
;
1271 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1272 typedef typename
_Hashtable::size_type size_type
;
1273 typedef typename
_Hashtable::difference_type difference_type
;
1276 #if __cplusplus > 201402L
1277 using node_type
= typename
_Hashtable::node_type
;
1280 //construct/destroy/copy
1282 /// Default constructor.
1283 unordered_multimap() = default;
1286 * @brief Default constructor creates no elements.
1287 * @param __n Mnimal initial number of buckets.
1288 * @param __hf A hash functor.
1289 * @param __eql A key equality functor.
1290 * @param __a An allocator object.
1293 unordered_multimap(size_type __n
,
1294 const hasher
& __hf
= hasher(),
1295 const key_equal
& __eql
= key_equal(),
1296 const allocator_type
& __a
= allocator_type())
1297 : _M_h(__n
, __hf
, __eql
, __a
)
1301 * @brief Builds an %unordered_multimap from a range.
1302 * @param __first An input iterator.
1303 * @param __last An input iterator.
1304 * @param __n Minimal initial number of buckets.
1305 * @param __hf A hash functor.
1306 * @param __eql A key equality functor.
1307 * @param __a An allocator object.
1309 * Create an %unordered_multimap consisting of copies of the elements
1310 * from [__first,__last). This is linear in N (where N is
1311 * distance(__first,__last)).
1313 template<typename _InputIterator
>
1314 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1316 const hasher
& __hf
= hasher(),
1317 const key_equal
& __eql
= key_equal(),
1318 const allocator_type
& __a
= allocator_type())
1319 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1322 /// Copy constructor.
1323 unordered_multimap(const unordered_multimap
&) = default;
1325 /// Move constructor.
1326 unordered_multimap(unordered_multimap
&&) = default;
1329 * @brief Creates an %unordered_multimap with no elements.
1330 * @param __a An allocator object.
1333 unordered_multimap(const allocator_type
& __a
)
1338 * @brief Copy constructor with allocator argument.
1339 * @param __uset Input %unordered_multimap to copy.
1340 * @param __a An allocator object.
1342 unordered_multimap(const unordered_multimap
& __ummap
,
1343 const allocator_type
& __a
)
1344 : _M_h(__ummap
._M_h
, __a
)
1348 * @brief Move constructor with allocator argument.
1349 * @param __uset Input %unordered_multimap to move.
1350 * @param __a An allocator object.
1352 unordered_multimap(unordered_multimap
&& __ummap
,
1353 const allocator_type
& __a
)
1354 noexcept( noexcept(_Hashtable(std::move(__ummap
._M_h
), __a
)) )
1355 : _M_h(std::move(__ummap
._M_h
), __a
)
1359 * @brief Builds an %unordered_multimap from an initializer_list.
1360 * @param __l An initializer_list.
1361 * @param __n Minimal initial number of buckets.
1362 * @param __hf A hash functor.
1363 * @param __eql A key equality functor.
1364 * @param __a An allocator object.
1366 * Create an %unordered_multimap consisting of copies of the elements in
1367 * the list. This is linear in N (where N is @a __l.size()).
1369 unordered_multimap(initializer_list
<value_type
> __l
,
1371 const hasher
& __hf
= hasher(),
1372 const key_equal
& __eql
= key_equal(),
1373 const allocator_type
& __a
= allocator_type())
1374 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1377 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1378 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1381 unordered_multimap(size_type __n
, const hasher
& __hf
,
1382 const allocator_type
& __a
)
1383 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1386 template<typename _InputIterator
>
1387 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1389 const allocator_type
& __a
)
1390 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1393 template<typename _InputIterator
>
1394 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1395 size_type __n
, const hasher
& __hf
,
1396 const allocator_type
& __a
)
1397 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1400 unordered_multimap(initializer_list
<value_type
> __l
,
1402 const allocator_type
& __a
)
1403 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1406 unordered_multimap(initializer_list
<value_type
> __l
,
1407 size_type __n
, const hasher
& __hf
,
1408 const allocator_type
& __a
)
1409 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1412 /// Copy assignment operator.
1414 operator=(const unordered_multimap
&) = default;
1416 /// Move assignment operator.
1418 operator=(unordered_multimap
&&) = default;
1421 * @brief %Unordered_multimap list assignment operator.
1422 * @param __l An initializer_list.
1424 * This function fills an %unordered_multimap with copies of the
1425 * elements in the initializer list @a __l.
1427 * Note that the assignment completely changes the %unordered_multimap
1428 * and that the resulting %unordered_multimap's size is the same as the
1429 * number of elements assigned.
1432 operator=(initializer_list
<value_type
> __l
)
1438 /// Returns the allocator object used by the %unordered_multimap.
1440 get_allocator() const noexcept
1441 { return _M_h
.get_allocator(); }
1443 // size and capacity:
1445 /// Returns true if the %unordered_multimap is empty.
1446 _GLIBCXX_NODISCARD
bool
1447 empty() const noexcept
1448 { return _M_h
.empty(); }
1450 /// Returns the size of the %unordered_multimap.
1452 size() const noexcept
1453 { return _M_h
.size(); }
1455 /// Returns the maximum size of the %unordered_multimap.
1457 max_size() const noexcept
1458 { return _M_h
.max_size(); }
1463 * Returns a read/write iterator that points to the first element in the
1464 * %unordered_multimap.
1468 { return _M_h
.begin(); }
1472 * Returns a read-only (constant) iterator that points to the first
1473 * element in the %unordered_multimap.
1476 begin() const noexcept
1477 { return _M_h
.begin(); }
1480 cbegin() const noexcept
1481 { return _M_h
.begin(); }
1485 * Returns a read/write iterator that points one past the last element in
1486 * the %unordered_multimap.
1490 { return _M_h
.end(); }
1494 * Returns a read-only (constant) iterator that points one past the last
1495 * element in the %unordered_multimap.
1498 end() const noexcept
1499 { return _M_h
.end(); }
1502 cend() const noexcept
1503 { return _M_h
.end(); }
1509 * @brief Attempts to build and insert a std::pair into the
1510 * %unordered_multimap.
1512 * @param __args Arguments used to generate a new pair instance (see
1513 * std::piecewise_contruct for passing arguments to each
1514 * part of the pair constructor).
1516 * @return An iterator that points to the inserted pair.
1518 * This function attempts to build and insert a (key, value) %pair into
1519 * the %unordered_multimap.
1521 * Insertion requires amortized constant time.
1523 template<typename
... _Args
>
1525 emplace(_Args
&&... __args
)
1526 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1529 * @brief Attempts to build and insert a std::pair into the
1530 * %unordered_multimap.
1532 * @param __pos An iterator that serves as a hint as to where the pair
1533 * should be inserted.
1534 * @param __args Arguments used to generate a new pair instance (see
1535 * std::piecewise_contruct for passing arguments to each
1536 * part of the pair constructor).
1537 * @return An iterator that points to the element with key of the
1538 * std::pair built from @a __args.
1540 * Note that the first parameter is only a hint and can potentially
1541 * improve the performance of the insertion process. A bad hint would
1542 * cause no gains in efficiency.
1545 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1546 * for more on @a hinting.
1548 * Insertion requires amortized constant time.
1550 template<typename
... _Args
>
1552 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1553 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1557 * @brief Inserts a std::pair into the %unordered_multimap.
1558 * @param __x Pair to be inserted (see std::make_pair for easy
1559 * creation of pairs).
1561 * @return An iterator that points to the inserted pair.
1563 * Insertion requires amortized constant time.
1566 insert(const value_type
& __x
)
1567 { return _M_h
.insert(__x
); }
1570 insert(value_type
&& __x
)
1571 { return _M_h
.insert(std::move(__x
)); }
1573 template<typename _Pair
>
1574 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1576 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
1581 * @brief Inserts a std::pair into the %unordered_multimap.
1582 * @param __hint An iterator that serves as a hint as to where the
1583 * pair should be inserted.
1584 * @param __x Pair to be inserted (see std::make_pair for easy creation
1586 * @return An iterator that points to the element with key of
1587 * @a __x (may or may not be the %pair passed in).
1589 * Note that the first parameter is only a hint and can potentially
1590 * improve the performance of the insertion process. A bad hint would
1591 * cause no gains in efficiency.
1594 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1595 * for more on @a hinting.
1597 * Insertion requires amortized constant time.
1600 insert(const_iterator __hint
, const value_type
& __x
)
1601 { return _M_h
.insert(__hint
, __x
); }
1603 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1604 // 2354. Unnecessary copying when inserting into maps with braced-init
1606 insert(const_iterator __hint
, value_type
&& __x
)
1607 { return _M_h
.insert(__hint
, std::move(__x
)); }
1609 template<typename _Pair
>
1610 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1611 insert(const_iterator __hint
, _Pair
&& __x
)
1612 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
1616 * @brief A template function that attempts to insert a range of
1618 * @param __first Iterator pointing to the start of the range to be
1620 * @param __last Iterator pointing to the end of the range.
1622 * Complexity similar to that of the range constructor.
1624 template<typename _InputIterator
>
1626 insert(_InputIterator __first
, _InputIterator __last
)
1627 { _M_h
.insert(__first
, __last
); }
1630 * @brief Attempts to insert a list of elements into the
1631 * %unordered_multimap.
1632 * @param __l A std::initializer_list<value_type> of elements
1635 * Complexity similar to that of the range constructor.
1638 insert(initializer_list
<value_type
> __l
)
1639 { _M_h
.insert(__l
); }
1641 #if __cplusplus > 201402L
1644 extract(const_iterator __pos
)
1646 __glibcxx_assert(__pos
!= end());
1647 return _M_h
.extract(__pos
);
1652 extract(const key_type
& __key
)
1653 { return _M_h
.extract(__key
); }
1655 /// Re-insert an extracted node.
1657 insert(node_type
&& __nh
)
1658 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1660 /// Re-insert an extracted node.
1662 insert(const_iterator __hint
, node_type
&& __nh
)
1663 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1668 * @brief Erases an element from an %unordered_multimap.
1669 * @param __position An iterator pointing to the element to be erased.
1670 * @return An iterator pointing to the element immediately following
1671 * @a __position prior to the element being erased. If no such
1672 * element exists, end() is returned.
1674 * This function erases an element, pointed to by the given iterator,
1675 * from an %unordered_multimap.
1676 * Note that this function only erases the element, and that if the
1677 * element is itself a pointer, the pointed-to memory is not touched in
1678 * any way. Managing the pointer is the user's responsibility.
1681 erase(const_iterator __position
)
1682 { return _M_h
.erase(__position
); }
1686 erase(iterator __position
)
1687 { return _M_h
.erase(__position
); }
1691 * @brief Erases elements according to the provided key.
1692 * @param __x Key of elements to be erased.
1693 * @return The number of elements erased.
1695 * This function erases all the elements located by the given key from
1696 * an %unordered_multimap.
1697 * Note that this function only erases the element, and that if the
1698 * element is itself a pointer, the pointed-to memory is not touched in
1699 * any way. Managing the pointer is the user's responsibility.
1702 erase(const key_type
& __x
)
1703 { return _M_h
.erase(__x
); }
1706 * @brief Erases a [__first,__last) range of elements from an
1707 * %unordered_multimap.
1708 * @param __first Iterator pointing to the start of the range to be
1710 * @param __last Iterator pointing to the end of the range to
1712 * @return The iterator @a __last.
1714 * This function erases a sequence of elements from an
1715 * %unordered_multimap.
1716 * Note that this function only erases the elements, and that if
1717 * the element is itself a pointer, the pointed-to memory is not touched
1718 * in any way. Managing the pointer is the user's responsibility.
1721 erase(const_iterator __first
, const_iterator __last
)
1722 { return _M_h
.erase(__first
, __last
); }
1725 * Erases all elements in an %unordered_multimap.
1726 * Note that this function only erases the elements, and that if the
1727 * elements themselves are pointers, the pointed-to memory is not touched
1728 * in any way. Managing the pointer is the user's responsibility.
1735 * @brief Swaps data with another %unordered_multimap.
1736 * @param __x An %unordered_multimap of the same element and allocator
1739 * This exchanges the elements between two %unordered_multimap in
1741 * Note that the global std::swap() function is specialized such that
1742 * std::swap(m1,m2) will feed to this function.
1745 swap(unordered_multimap
& __x
)
1746 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1747 { _M_h
.swap(__x
._M_h
); }
1749 #if __cplusplus > 201402L
1750 template<typename
, typename
, typename
>
1751 friend class std::_Hash_merge_helper
;
1753 template<typename _H2
, typename _P2
>
1755 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1758 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1759 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1762 template<typename _H2
, typename _P2
>
1764 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1765 { merge(__source
); }
1767 template<typename _H2
, typename _P2
>
1769 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1772 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1773 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1776 template<typename _H2
, typename _P2
>
1778 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1779 { merge(__source
); }
1784 /// Returns the hash functor object with which the %unordered_multimap
1785 /// was constructed.
1787 hash_function() const
1788 { return _M_h
.hash_function(); }
1790 /// Returns the key comparison object with which the %unordered_multimap
1791 /// was constructed.
1794 { return _M_h
.key_eq(); }
1800 * @brief Tries to locate an element in an %unordered_multimap.
1801 * @param __x Key to be located.
1802 * @return Iterator pointing to sought-after element, or end() if not
1805 * This function takes a key and tries to locate the element with which
1806 * the key matches. If successful the function returns an iterator
1807 * pointing to the sought after element. If unsuccessful it returns the
1808 * past-the-end ( @c end() ) iterator.
1811 find(const key_type
& __x
)
1812 { return _M_h
.find(__x
); }
1814 #if __cplusplus > 201703L
1815 template<typename _Kt
>
1817 find(const _Kt
& __x
) -> decltype(_M_h
._M_find_tr(__x
))
1818 { return _M_h
._M_find_tr(__x
); }
1822 find(const key_type
& __x
) const
1823 { return _M_h
.find(__x
); }
1825 #if __cplusplus > 201703L
1826 template<typename _Kt
>
1828 find(const _Kt
& __x
) const -> decltype(_M_h
._M_find_tr(__x
))
1829 { return _M_h
._M_find_tr(__x
); }
1835 * @brief Finds the number of elements.
1836 * @param __x Key to count.
1837 * @return Number of elements with specified key.
1840 count(const key_type
& __x
) const
1841 { return _M_h
.count(__x
); }
1843 #if __cplusplus > 201703L
1844 template<typename _Kt
>
1846 count(const _Kt
& __x
) const -> decltype(_M_h
._M_count_tr(__x
))
1847 { return _M_h
._M_count_tr(__x
); }
1851 #if __cplusplus > 201703L
1854 * @brief Finds whether an element with the given key exists.
1855 * @param __x Key of elements to be located.
1856 * @return True if there is any element with the specified key.
1859 contains(const key_type
& __x
) const
1860 { return _M_h
.find(__x
) != _M_h
.end(); }
1862 template<typename _Kt
>
1864 contains(const _Kt
& __x
) const
1865 -> decltype(_M_h
._M_find_tr(__x
), void(), true)
1866 { return _M_h
._M_find_tr(__x
) != _M_h
.end(); }
1872 * @brief Finds a subsequence matching given key.
1873 * @param __x Key to be located.
1874 * @return Pair of iterators that possibly points to the subsequence
1875 * matching given key.
1877 std::pair
<iterator
, iterator
>
1878 equal_range(const key_type
& __x
)
1879 { return _M_h
.equal_range(__x
); }
1881 #if __cplusplus > 201703L
1882 template<typename _Kt
>
1884 equal_range(const _Kt
& __x
)
1885 -> decltype(_M_h
._M_equal_range_tr(__x
))
1886 { return _M_h
._M_equal_range_tr(__x
); }
1889 std::pair
<const_iterator
, const_iterator
>
1890 equal_range(const key_type
& __x
) const
1891 { return _M_h
.equal_range(__x
); }
1893 #if __cplusplus > 201703L
1894 template<typename _Kt
>
1896 equal_range(const _Kt
& __x
) const
1897 -> decltype(_M_h
._M_equal_range_tr(__x
))
1898 { return _M_h
._M_equal_range_tr(__x
); }
1902 // bucket interface.
1904 /// Returns the number of buckets of the %unordered_multimap.
1906 bucket_count() const noexcept
1907 { return _M_h
.bucket_count(); }
1909 /// Returns the maximum number of buckets of the %unordered_multimap.
1911 max_bucket_count() const noexcept
1912 { return _M_h
.max_bucket_count(); }
1915 * @brief Returns the number of elements in a given bucket.
1916 * @param __n A bucket index.
1917 * @return The number of elements in the bucket.
1920 bucket_size(size_type __n
) const
1921 { return _M_h
.bucket_size(__n
); }
1924 * @brief Returns the bucket index of a given element.
1925 * @param __key A key instance.
1926 * @return The key bucket index.
1929 bucket(const key_type
& __key
) const
1930 { return _M_h
.bucket(__key
); }
1933 * @brief Returns a read/write iterator pointing to the first bucket
1935 * @param __n The bucket index.
1936 * @return A read/write local iterator.
1939 begin(size_type __n
)
1940 { return _M_h
.begin(__n
); }
1944 * @brief Returns a read-only (constant) iterator pointing to the first
1946 * @param __n The bucket index.
1947 * @return A read-only local iterator.
1949 const_local_iterator
1950 begin(size_type __n
) const
1951 { return _M_h
.begin(__n
); }
1953 const_local_iterator
1954 cbegin(size_type __n
) const
1955 { return _M_h
.cbegin(__n
); }
1959 * @brief Returns a read/write iterator pointing to one past the last
1961 * @param __n The bucket index.
1962 * @return A read/write local iterator.
1966 { return _M_h
.end(__n
); }
1970 * @brief Returns a read-only (constant) iterator pointing to one past
1971 * the last bucket elements.
1972 * @param __n The bucket index.
1973 * @return A read-only local iterator.
1975 const_local_iterator
1976 end(size_type __n
) const
1977 { return _M_h
.end(__n
); }
1979 const_local_iterator
1980 cend(size_type __n
) const
1981 { return _M_h
.cend(__n
); }
1986 /// Returns the average number of elements per bucket.
1988 load_factor() const noexcept
1989 { return _M_h
.load_factor(); }
1991 /// Returns a positive number that the %unordered_multimap tries to keep
1992 /// the load factor less than or equal to.
1994 max_load_factor() const noexcept
1995 { return _M_h
.max_load_factor(); }
1998 * @brief Change the %unordered_multimap maximum load factor.
1999 * @param __z The new maximum load factor.
2002 max_load_factor(float __z
)
2003 { _M_h
.max_load_factor(__z
); }
2006 * @brief May rehash the %unordered_multimap.
2007 * @param __n The new number of buckets.
2009 * Rehash will occur only if the new number of buckets respect the
2010 * %unordered_multimap maximum load factor.
2013 rehash(size_type __n
)
2014 { _M_h
.rehash(__n
); }
2017 * @brief Prepare the %unordered_multimap for a specified number of
2019 * @param __n Number of elements required.
2021 * Same as rehash(ceil(n / max_load_factor())).
2024 reserve(size_type __n
)
2025 { _M_h
.reserve(__n
); }
2027 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
2030 operator==(const unordered_multimap
<_Key1
, _Tp1
,
2031 _Hash1
, _Pred1
, _Alloc1
>&,
2032 const unordered_multimap
<_Key1
, _Tp1
,
2033 _Hash1
, _Pred1
, _Alloc1
>&);
2036 #if __cpp_deduction_guides >= 201606
2038 template<typename _InputIterator
,
2039 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
2040 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
2041 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
2042 typename
= _RequireInputIter
<_InputIterator
>,
2043 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2044 typename
= _RequireNotAllocator
<_Pred
>,
2045 typename
= _RequireAllocator
<_Allocator
>>
2046 unordered_multimap(_InputIterator
, _InputIterator
,
2047 unordered_multimap
<int, int>::size_type
= {},
2048 _Hash
= _Hash(), _Pred
= _Pred(),
2049 _Allocator
= _Allocator())
2050 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2051 __iter_val_t
<_InputIterator
>, _Hash
, _Pred
,
2054 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
2055 typename _Pred
= equal_to
<_Key
>,
2056 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
2057 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2058 typename
= _RequireNotAllocator
<_Pred
>,
2059 typename
= _RequireAllocator
<_Allocator
>>
2060 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2061 unordered_multimap
<int, int>::size_type
= {},
2062 _Hash
= _Hash(), _Pred
= _Pred(),
2063 _Allocator
= _Allocator())
2064 -> unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
2066 template<typename _InputIterator
, typename _Allocator
,
2067 typename
= _RequireInputIter
<_InputIterator
>,
2068 typename
= _RequireAllocator
<_Allocator
>>
2069 unordered_multimap(_InputIterator
, _InputIterator
,
2070 unordered_multimap
<int, int>::size_type
, _Allocator
)
2071 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2072 __iter_val_t
<_InputIterator
>,
2073 hash
<__iter_key_t
<_InputIterator
>>,
2074 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2076 template<typename _InputIterator
, typename _Allocator
,
2077 typename
= _RequireInputIter
<_InputIterator
>,
2078 typename
= _RequireAllocator
<_Allocator
>>
2079 unordered_multimap(_InputIterator
, _InputIterator
, _Allocator
)
2080 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2081 __iter_val_t
<_InputIterator
>,
2082 hash
<__iter_key_t
<_InputIterator
>>,
2083 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2085 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
2086 typename
= _RequireInputIter
<_InputIterator
>,
2087 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2088 typename
= _RequireAllocator
<_Allocator
>>
2089 unordered_multimap(_InputIterator
, _InputIterator
,
2090 unordered_multimap
<int, int>::size_type
, _Hash
,
2092 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2093 __iter_val_t
<_InputIterator
>, _Hash
,
2094 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2096 template<typename _Key
, typename _Tp
, typename _Allocator
,
2097 typename
= _RequireAllocator
<_Allocator
>>
2098 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2099 unordered_multimap
<int, int>::size_type
,
2101 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2103 template<typename _Key
, typename _Tp
, typename _Allocator
,
2104 typename
= _RequireAllocator
<_Allocator
>>
2105 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
2106 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2108 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
2109 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2110 typename
= _RequireAllocator
<_Allocator
>>
2111 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2112 unordered_multimap
<int, int>::size_type
,
2114 -> unordered_multimap
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
2118 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2120 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2121 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2122 noexcept(noexcept(__x
.swap(__y
)))
2125 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2127 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2128 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2129 noexcept(noexcept(__x
.swap(__y
)))
2132 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2134 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2135 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2136 { return __x
._M_h
._M_equal(__y
._M_h
); }
2138 #if __cpp_impl_three_way_comparison < 201907L
2139 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2141 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2142 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2143 { return !(__x
== __y
); }
2146 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2148 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2149 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2150 { return __x
._M_h
._M_equal(__y
._M_h
); }
2152 #if __cpp_impl_three_way_comparison < 201907L
2153 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2155 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2156 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2157 { return !(__x
== __y
); }
2160 _GLIBCXX_END_NAMESPACE_CONTAINER
2162 #if __cplusplus > 201402L
2163 // Allow std::unordered_map access to internals of compatible maps.
2164 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2165 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2166 struct _Hash_merge_helper
<
2167 _GLIBCXX_STD_C::unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2171 template<typename
... _Tp
>
2172 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2173 template<typename
... _Tp
>
2174 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2176 friend unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2179 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2180 { return __map
._M_h
; }
2183 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2184 { return __map
._M_h
; }
2187 // Allow std::unordered_multimap access to internals of compatible maps.
2188 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2189 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2190 struct _Hash_merge_helper
<
2191 _GLIBCXX_STD_C::unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2195 template<typename
... _Tp
>
2196 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2197 template<typename
... _Tp
>
2198 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2200 friend unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2203 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2204 { return __map
._M_h
; }
2207 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2208 { return __map
._M_h
; }
2212 _GLIBCXX_END_NAMESPACE_VERSION
2215 #endif /* _UNORDERED_MAP_H */