1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2024 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 #include <bits/hashtable.h>
34 #include <bits/allocator.h>
35 #include <bits/functional_hash.h> // hash
36 #include <bits/stl_function.h> // equal_to
38 namespace std
_GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
43 /// Base types for unordered_map.
45 using __umap_traits
= __detail::_Hashtable_traits
<_Cache
, false, true>;
47 template<typename _Key
,
49 typename _Hash
= hash
<_Key
>,
50 typename _Pred
= std::equal_to
<_Key
>,
51 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
52 typename _Tr
= __umap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
53 using __umap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
54 _Alloc
, __detail::_Select1st
,
56 __detail::_Mod_range_hashing
,
57 __detail::_Default_ranged_hash
,
58 __detail::_Prime_rehash_policy
, _Tr
>;
60 /// Base types for unordered_multimap.
62 using __ummap_traits
= __detail::_Hashtable_traits
<_Cache
, false, false>;
64 template<typename _Key
,
66 typename _Hash
= hash
<_Key
>,
67 typename _Pred
= std::equal_to
<_Key
>,
68 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
69 typename _Tr
= __ummap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
70 using __ummap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
71 _Alloc
, __detail::_Select1st
,
73 __detail::_Mod_range_hashing
,
74 __detail::_Default_ranged_hash
,
75 __detail::_Prime_rehash_policy
, _Tr
>;
77 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
78 class unordered_multimap
;
81 * @brief A standard container composed of unique keys (containing
82 * at most one of each key value) that associates values of another type
85 * @ingroup unordered_associative_containers
86 * @headerfile unordered_map
89 * @tparam _Key Type of key objects.
90 * @tparam _Tp Type of mapped objects.
91 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
92 * @tparam _Pred Predicate function object type, defaults
93 * to equal_to<_Value>.
94 * @tparam _Alloc Allocator type, defaults to
95 * std::allocator<std::pair<const _Key, _Tp>>.
97 * Meets the requirements of a <a href="tables.html#65">container</a>, and
98 * <a href="tables.html#xx">unordered associative container</a>
100 * The resulting value type of the container is std::pair<const _Key, _Tp>.
102 * Base is _Hashtable, dispatched at compile time via template
103 * alias __umap_hashtable.
105 template<typename _Key
, typename _Tp
,
106 typename _Hash
= hash
<_Key
>,
107 typename _Pred
= equal_to
<_Key
>,
108 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
111 typedef __umap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
118 typedef typename
_Hashtable::key_type key_type
;
119 typedef typename
_Hashtable::value_type value_type
;
120 typedef typename
_Hashtable::mapped_type mapped_type
;
121 typedef typename
_Hashtable::hasher hasher
;
122 typedef typename
_Hashtable::key_equal key_equal
;
123 typedef typename
_Hashtable::allocator_type allocator_type
;
127 /// Iterator-related typedefs.
128 typedef typename
_Hashtable::pointer pointer
;
129 typedef typename
_Hashtable::const_pointer const_pointer
;
130 typedef typename
_Hashtable::reference reference
;
131 typedef typename
_Hashtable::const_reference const_reference
;
132 typedef typename
_Hashtable::iterator iterator
;
133 typedef typename
_Hashtable::const_iterator const_iterator
;
134 typedef typename
_Hashtable::local_iterator local_iterator
;
135 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
136 typedef typename
_Hashtable::size_type size_type
;
137 typedef typename
_Hashtable::difference_type difference_type
;
140 #if __cplusplus > 201402L
141 using node_type
= typename
_Hashtable::node_type
;
142 using insert_return_type
= typename
_Hashtable::insert_return_type
;
145 //construct/destroy/copy
147 /// Default constructor.
148 unordered_map() = default;
151 * @brief Default constructor creates no elements.
152 * @param __n Minimal initial number of buckets.
153 * @param __hf A hash functor.
154 * @param __eql A key equality functor.
155 * @param __a An allocator object.
158 unordered_map(size_type __n
,
159 const hasher
& __hf
= hasher(),
160 const key_equal
& __eql
= key_equal(),
161 const allocator_type
& __a
= allocator_type())
162 : _M_h(__n
, __hf
, __eql
, __a
)
166 * @brief Builds an %unordered_map from a range.
167 * @param __first An input iterator.
168 * @param __last An input iterator.
169 * @param __n Minimal initial number of buckets.
170 * @param __hf A hash functor.
171 * @param __eql A key equality functor.
172 * @param __a An allocator object.
174 * Create an %unordered_map consisting of copies of the elements from
175 * [__first,__last). This is linear in N (where N is
176 * distance(__first,__last)).
178 template<typename _InputIterator
>
179 unordered_map(_InputIterator __first
, _InputIterator __last
,
181 const hasher
& __hf
= hasher(),
182 const key_equal
& __eql
= key_equal(),
183 const allocator_type
& __a
= allocator_type())
184 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
187 /// Copy constructor.
188 unordered_map(const unordered_map
&) = default;
190 /// Move constructor.
191 unordered_map(unordered_map
&&) = default;
194 * @brief Creates an %unordered_map with no elements.
195 * @param __a An allocator object.
198 unordered_map(const allocator_type
& __a
)
203 * @brief Copy constructor with allocator argument.
204 * @param __uset Input %unordered_map to copy.
205 * @param __a An allocator object.
207 unordered_map(const unordered_map
& __umap
,
208 const allocator_type
& __a
)
209 : _M_h(__umap
._M_h
, __a
)
213 * @brief Move constructor with allocator argument.
214 * @param __uset Input %unordered_map to move.
215 * @param __a An allocator object.
217 unordered_map(unordered_map
&& __umap
,
218 const allocator_type
& __a
)
219 noexcept( noexcept(_Hashtable(std::move(__umap
._M_h
), __a
)) )
220 : _M_h(std::move(__umap
._M_h
), __a
)
224 * @brief Builds an %unordered_map from an initializer_list.
225 * @param __l An initializer_list.
226 * @param __n Minimal initial number of buckets.
227 * @param __hf A hash functor.
228 * @param __eql A key equality functor.
229 * @param __a An allocator object.
231 * Create an %unordered_map consisting of copies of the elements in the
232 * list. This is linear in N (where N is @a __l.size()).
234 unordered_map(initializer_list
<value_type
> __l
,
236 const hasher
& __hf
= hasher(),
237 const key_equal
& __eql
= key_equal(),
238 const allocator_type
& __a
= allocator_type())
239 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
242 unordered_map(size_type __n
, const allocator_type
& __a
)
243 : unordered_map(__n
, hasher(), key_equal(), __a
)
246 unordered_map(size_type __n
, const hasher
& __hf
,
247 const allocator_type
& __a
)
248 : unordered_map(__n
, __hf
, key_equal(), __a
)
251 template<typename _InputIterator
>
252 unordered_map(_InputIterator __first
, _InputIterator __last
,
254 const allocator_type
& __a
)
255 : unordered_map(__first
, __last
, __n
, hasher(), key_equal(), __a
)
258 template<typename _InputIterator
>
259 unordered_map(_InputIterator __first
, _InputIterator __last
,
260 size_type __n
, const hasher
& __hf
,
261 const allocator_type
& __a
)
262 : unordered_map(__first
, __last
, __n
, __hf
, key_equal(), __a
)
265 unordered_map(initializer_list
<value_type
> __l
,
267 const allocator_type
& __a
)
268 : unordered_map(__l
, __n
, hasher(), key_equal(), __a
)
271 unordered_map(initializer_list
<value_type
> __l
,
272 size_type __n
, const hasher
& __hf
,
273 const allocator_type
& __a
)
274 : unordered_map(__l
, __n
, __hf
, key_equal(), __a
)
277 /// Copy assignment operator.
279 operator=(const unordered_map
&) = default;
281 /// Move assignment operator.
283 operator=(unordered_map
&&) = default;
286 * @brief %Unordered_map list assignment operator.
287 * @param __l An initializer_list.
289 * This function fills an %unordered_map with copies of the elements in
290 * the initializer list @a __l.
292 * Note that the assignment completely changes the %unordered_map and
293 * that the resulting %unordered_map's size is the same as the number
294 * of elements assigned.
297 operator=(initializer_list
<value_type
> __l
)
303 /// Returns the allocator object used by the %unordered_map.
305 get_allocator() const noexcept
306 { return _M_h
.get_allocator(); }
308 // size and capacity:
310 /// Returns true if the %unordered_map is empty.
311 _GLIBCXX_NODISCARD
bool
312 empty() const noexcept
313 { return _M_h
.empty(); }
315 /// Returns the size of the %unordered_map.
317 size() const noexcept
318 { return _M_h
.size(); }
320 /// Returns the maximum size of the %unordered_map.
322 max_size() const noexcept
323 { return _M_h
.max_size(); }
328 * Returns a read/write iterator that points to the first element in the
333 { return _M_h
.begin(); }
337 * Returns a read-only (constant) iterator that points to the first
338 * element in the %unordered_map.
341 begin() const noexcept
342 { return _M_h
.begin(); }
345 cbegin() const noexcept
346 { return _M_h
.begin(); }
350 * Returns a read/write iterator that points one past the last element in
351 * the %unordered_map.
355 { return _M_h
.end(); }
359 * Returns a read-only (constant) iterator that points one past the last
360 * element in the %unordered_map.
364 { return _M_h
.end(); }
367 cend() const noexcept
368 { return _M_h
.end(); }
374 * @brief Attempts to build and insert a std::pair into the
377 * @param __args Arguments used to generate a new pair instance (see
378 * std::piecewise_contruct for passing arguments to each
379 * part of the pair constructor).
381 * @return A pair, of which the first element is an iterator that points
382 * to the possibly inserted pair, and the second is a bool that
383 * is true if the pair was actually inserted.
385 * This function attempts to build and insert a (key, value) %pair into
386 * the %unordered_map.
387 * An %unordered_map relies on unique keys and thus a %pair is only
388 * inserted if its first element (the key) is not already present in the
391 * Insertion requires amortized constant time.
393 template<typename
... _Args
>
394 std::pair
<iterator
, bool>
395 emplace(_Args
&&... __args
)
396 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
399 * @brief Attempts to build and insert a std::pair into the
402 * @param __pos An iterator that serves as a hint as to where the pair
403 * should be inserted.
404 * @param __args Arguments used to generate a new pair instance (see
405 * std::piecewise_contruct for passing arguments to each
406 * part of the pair constructor).
407 * @return An iterator that points to the element with key of the
408 * std::pair built from @a __args (may or may not be that
411 * This function is not concerned about whether the insertion took place,
412 * and thus does not return a boolean like the single-argument emplace()
414 * Note that the first parameter is only a hint and can potentially
415 * improve the performance of the insertion process. A bad hint would
416 * cause no gains in efficiency.
419 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
420 * for more on @a hinting.
422 * Insertion requires amortized constant time.
424 template<typename
... _Args
>
426 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
427 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
429 #if __cplusplus > 201402L
432 extract(const_iterator __pos
)
434 __glibcxx_assert(__pos
!= end());
435 return _M_h
.extract(__pos
);
440 extract(const key_type
& __key
)
441 { return _M_h
.extract(__key
); }
443 /// Re-insert an extracted node.
445 insert(node_type
&& __nh
)
446 { return _M_h
._M_reinsert_node(std::move(__nh
)); }
448 /// Re-insert an extracted node.
450 insert(const_iterator
, node_type
&& __nh
)
451 { return _M_h
._M_reinsert_node(std::move(__nh
)).position
; }
454 #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
456 * @brief Attempts to build and insert a std::pair into the
459 * @param __k Key to use for finding a possibly existing pair in
461 * @param __args Arguments used to generate the .second for a
464 * @return A pair, of which the first element is an iterator that points
465 * to the possibly inserted pair, and the second is a bool that
466 * is true if the pair was actually inserted.
468 * This function attempts to build and insert a (key, value) %pair into
469 * the %unordered_map.
470 * An %unordered_map relies on unique keys and thus a %pair is only
471 * inserted if its first element (the key) is not already present in the
473 * If a %pair is not inserted, this function has no effect.
475 * Insertion requires amortized constant time.
477 template <typename
... _Args
>
479 try_emplace(const key_type
& __k
, _Args
&&... __args
)
481 return _M_h
.try_emplace(cend(), __k
, std::forward
<_Args
>(__args
)...);
484 // move-capable overload
485 template <typename
... _Args
>
487 try_emplace(key_type
&& __k
, _Args
&&... __args
)
489 return _M_h
.try_emplace(cend(), std::move(__k
),
490 std::forward
<_Args
>(__args
)...);
494 * @brief Attempts to build and insert a std::pair into the
497 * @param __hint An iterator that serves as a hint as to where the pair
498 * should be inserted.
499 * @param __k Key to use for finding a possibly existing pair in
501 * @param __args Arguments used to generate the .second for a
503 * @return An iterator that points to the element with key of the
504 * std::pair built from @a __args (may or may not be that
507 * This function is not concerned about whether the insertion took place,
508 * and thus does not return a boolean like the single-argument emplace()
509 * does. However, if insertion did not take place,
510 * this function has no effect.
511 * Note that the first parameter is only a hint and can potentially
512 * improve the performance of the insertion process. A bad hint would
513 * cause no gains in efficiency.
516 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
517 * for more on @a hinting.
519 * Insertion requires amortized constant time.
521 template <typename
... _Args
>
523 try_emplace(const_iterator __hint
, const key_type
& __k
,
526 return _M_h
.try_emplace(__hint
, __k
,
527 std::forward
<_Args
>(__args
)...).first
;
530 // move-capable overload
531 template <typename
... _Args
>
533 try_emplace(const_iterator __hint
, key_type
&& __k
, _Args
&&... __args
)
535 return _M_h
.try_emplace(__hint
, std::move(__k
),
536 std::forward
<_Args
>(__args
)...).first
;
538 #endif // __glibcxx_unordered_map_try_emplace
542 * @brief Attempts to insert a std::pair into the %unordered_map.
544 * @param __x Pair to be inserted (see std::make_pair for easy
545 * creation of pairs).
547 * @return A pair, of which the first element is an iterator that
548 * points to the possibly inserted pair, and the second is
549 * a bool that is true if the pair was actually inserted.
551 * This function attempts to insert a (key, value) %pair into the
552 * %unordered_map. An %unordered_map relies on unique keys and thus a
553 * %pair is only inserted if its first element (the key) is not already
554 * present in the %unordered_map.
556 * Insertion requires amortized constant time.
558 std::pair
<iterator
, bool>
559 insert(const value_type
& __x
)
560 { return _M_h
.insert(__x
); }
562 // _GLIBCXX_RESOLVE_LIB_DEFECTS
563 // 2354. Unnecessary copying when inserting into maps with braced-init
564 std::pair
<iterator
, bool>
565 insert(value_type
&& __x
)
566 { return _M_h
.insert(std::move(__x
)); }
568 template<typename _Pair
>
569 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
,
570 pair
<iterator
, bool>>
572 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
577 * @brief Attempts to insert a std::pair into the %unordered_map.
578 * @param __hint An iterator that serves as a hint as to where the
579 * pair should be inserted.
580 * @param __x Pair to be inserted (see std::make_pair for easy creation
582 * @return An iterator that points to the element with key of
583 * @a __x (may or may not be the %pair passed in).
585 * This function is not concerned about whether the insertion took place,
586 * and thus does not return a boolean like the single-argument insert()
587 * does. Note that the first parameter is only a hint and can
588 * potentially improve the performance of the insertion process. A bad
589 * hint would cause no gains in efficiency.
592 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
593 * for more on @a hinting.
595 * Insertion requires amortized constant time.
598 insert(const_iterator __hint
, const value_type
& __x
)
599 { return _M_h
.insert(__hint
, __x
); }
601 // _GLIBCXX_RESOLVE_LIB_DEFECTS
602 // 2354. Unnecessary copying when inserting into maps with braced-init
604 insert(const_iterator __hint
, value_type
&& __x
)
605 { return _M_h
.insert(__hint
, std::move(__x
)); }
607 template<typename _Pair
>
608 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
609 insert(const_iterator __hint
, _Pair
&& __x
)
610 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
614 * @brief A template function that attempts to insert a range of
616 * @param __first Iterator pointing to the start of the range to be
618 * @param __last Iterator pointing to the end of the range.
620 * Complexity similar to that of the range constructor.
622 template<typename _InputIterator
>
624 insert(_InputIterator __first
, _InputIterator __last
)
625 { _M_h
.insert(__first
, __last
); }
628 * @brief Attempts to insert a list of elements into the %unordered_map.
629 * @param __l A std::initializer_list<value_type> of elements
632 * Complexity similar to that of the range constructor.
635 insert(initializer_list
<value_type
> __l
)
636 { _M_h
.insert(__l
); }
639 #if __cplusplus > 201402L
641 * @brief Attempts to insert a std::pair into the %unordered_map.
642 * @param __k Key to use for finding a possibly existing pair in
644 * @param __obj Argument used to generate the .second for a pair
647 * @return A pair, of which the first element is an iterator that
648 * points to the possibly inserted pair, and the second is
649 * a bool that is true if the pair was actually inserted.
651 * This function attempts to insert a (key, value) %pair into the
652 * %unordered_map. An %unordered_map relies on unique keys and thus a
653 * %pair is only inserted if its first element (the key) is not already
654 * present in the %unordered_map.
655 * If the %pair was already in the %unordered_map, the .second of
656 * the %pair is assigned from __obj.
658 * Insertion requires amortized constant time.
660 template <typename _Obj
>
662 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
664 auto __ret
= _M_h
.try_emplace(cend(), __k
,
665 std::forward
<_Obj
>(__obj
));
667 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
671 // move-capable overload
672 template <typename _Obj
>
674 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
676 auto __ret
= _M_h
.try_emplace(cend(), std::move(__k
),
677 std::forward
<_Obj
>(__obj
));
679 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
684 * @brief Attempts to insert a std::pair into the %unordered_map.
685 * @param __hint An iterator that serves as a hint as to where the
686 * pair should be inserted.
687 * @param __k Key to use for finding a possibly existing pair in
689 * @param __obj Argument used to generate the .second for a pair
691 * @return An iterator that points to the element with key of
692 * @a __x (may or may not be the %pair passed in).
694 * This function is not concerned about whether the insertion took place,
695 * and thus does not return a boolean like the single-argument insert()
697 * If the %pair was already in the %unordered map, the .second of
698 * the %pair is assigned from __obj.
699 * Note that the first parameter is only a hint and can
700 * potentially improve the performance of the insertion process. A bad
701 * hint would cause no gains in efficiency.
704 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
705 * for more on @a hinting.
707 * Insertion requires amortized constant time.
709 template <typename _Obj
>
711 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
714 auto __ret
= _M_h
.try_emplace(__hint
, __k
, std::forward
<_Obj
>(__obj
));
716 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
720 // move-capable overload
721 template <typename _Obj
>
723 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
725 auto __ret
= _M_h
.try_emplace(__hint
, std::move(__k
),
726 std::forward
<_Obj
>(__obj
));
728 __ret
.first
->second
= std::forward
<_Obj
>(__obj
);
735 * @brief Erases an element from an %unordered_map.
736 * @param __position An iterator pointing to the element to be erased.
737 * @return An iterator pointing to the element immediately following
738 * @a __position prior to the element being erased. If no such
739 * element exists, end() is returned.
741 * This function erases an element, pointed to by the given iterator,
742 * from an %unordered_map.
743 * Note that this function only erases the element, and that if the
744 * element is itself a pointer, the pointed-to memory is not touched in
745 * any way. Managing the pointer is the user's responsibility.
748 erase(const_iterator __position
)
749 { return _M_h
.erase(__position
); }
753 erase(iterator __position
)
754 { return _M_h
.erase(__position
); }
758 * @brief Erases elements according to the provided key.
759 * @param __x Key of element to be erased.
760 * @return The number of elements erased.
762 * This function erases all the elements located by the given key from
763 * an %unordered_map. For an %unordered_map the result of this function
764 * can only be 0 (not present) or 1 (present).
765 * Note that this function only erases the element, and that if the
766 * element is itself a pointer, the pointed-to memory is not touched in
767 * any way. Managing the pointer is the user's responsibility.
770 erase(const key_type
& __x
)
771 { return _M_h
.erase(__x
); }
774 * @brief Erases a [__first,__last) range of elements from an
776 * @param __first Iterator pointing to the start of the range to be
778 * @param __last Iterator pointing to the end of the range to
780 * @return The iterator @a __last.
782 * This function erases a sequence of elements from an %unordered_map.
783 * Note that this function only erases the elements, and that if
784 * the element is itself a pointer, the pointed-to memory is not touched
785 * in any way. Managing the pointer is the user's responsibility.
788 erase(const_iterator __first
, const_iterator __last
)
789 { return _M_h
.erase(__first
, __last
); }
792 * Erases all elements in an %unordered_map.
793 * Note that this function only erases the elements, and that if the
794 * elements themselves are pointers, the pointed-to memory is not touched
795 * in any way. Managing the pointer is the user's responsibility.
802 * @brief Swaps data with another %unordered_map.
803 * @param __x An %unordered_map of the same element and allocator
806 * This exchanges the elements between two %unordered_map in constant
808 * Note that the global std::swap() function is specialized such that
809 * std::swap(m1,m2) will feed to this function.
812 swap(unordered_map
& __x
)
813 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
814 { _M_h
.swap(__x
._M_h
); }
816 #if __cplusplus > 201402L
817 template<typename
, typename
, typename
>
818 friend class std::_Hash_merge_helper
;
820 template<typename _H2
, typename _P2
>
822 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
824 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
825 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
828 template<typename _H2
, typename _P2
>
830 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
833 template<typename _H2
, typename _P2
>
835 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
837 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
838 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
841 template<typename _H2
, typename _P2
>
843 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
849 /// Returns the hash functor object with which the %unordered_map was
852 hash_function() const
853 { return _M_h
.hash_function(); }
855 /// Returns the key comparison object with which the %unordered_map was
859 { return _M_h
.key_eq(); }
865 * @brief Tries to locate an element in an %unordered_map.
866 * @param __x Key to be located.
867 * @return Iterator pointing to sought-after element, or end() if not
870 * This function takes a key and tries to locate the element with which
871 * the key matches. If successful the function returns an iterator
872 * pointing to the sought after element. If unsuccessful it returns the
873 * past-the-end ( @c end() ) iterator.
876 find(const key_type
& __x
)
877 { return _M_h
.find(__x
); }
879 #if __cplusplus > 201703L
880 template<typename _Kt
>
882 find(const _Kt
& __x
) -> decltype(_M_h
._M_find_tr(__x
))
883 { return _M_h
._M_find_tr(__x
); }
887 find(const key_type
& __x
) const
888 { return _M_h
.find(__x
); }
890 #if __cplusplus > 201703L
891 template<typename _Kt
>
893 find(const _Kt
& __x
) const -> decltype(_M_h
._M_find_tr(__x
))
894 { return _M_h
._M_find_tr(__x
); }
900 * @brief Finds the number of elements.
901 * @param __x Key to count.
902 * @return Number of elements with specified key.
904 * This function only makes sense for %unordered_multimap; for
905 * %unordered_map the result will either be 0 (not present) or 1
909 count(const key_type
& __x
) const
910 { return _M_h
.count(__x
); }
912 #if __cplusplus > 201703L
913 template<typename _Kt
>
915 count(const _Kt
& __x
) const -> decltype(_M_h
._M_count_tr(__x
))
916 { return _M_h
._M_count_tr(__x
); }
920 #if __cplusplus > 201703L
923 * @brief Finds whether an element with the given key exists.
924 * @param __x Key of elements to be located.
925 * @return True if there is any element with the specified key.
928 contains(const key_type
& __x
) const
929 { return _M_h
.find(__x
) != _M_h
.end(); }
931 template<typename _Kt
>
933 contains(const _Kt
& __x
) const
934 -> decltype(_M_h
._M_find_tr(__x
), void(), true)
935 { return _M_h
._M_find_tr(__x
) != _M_h
.end(); }
941 * @brief Finds a subsequence matching given key.
942 * @param __x Key to be located.
943 * @return Pair of iterators that possibly points to the subsequence
944 * matching given key.
946 * This function probably only makes sense for %unordered_multimap.
948 std::pair
<iterator
, iterator
>
949 equal_range(const key_type
& __x
)
950 { return _M_h
.equal_range(__x
); }
952 #if __cplusplus > 201703L
953 template<typename _Kt
>
955 equal_range(const _Kt
& __x
)
956 -> decltype(_M_h
._M_equal_range_tr(__x
))
957 { return _M_h
._M_equal_range_tr(__x
); }
960 std::pair
<const_iterator
, const_iterator
>
961 equal_range(const key_type
& __x
) const
962 { return _M_h
.equal_range(__x
); }
964 #if __cplusplus > 201703L
965 template<typename _Kt
>
967 equal_range(const _Kt
& __x
) const
968 -> decltype(_M_h
._M_equal_range_tr(__x
))
969 { return _M_h
._M_equal_range_tr(__x
); }
975 * @brief Subscript ( @c [] ) access to %unordered_map data.
976 * @param __k The key for which data should be retrieved.
977 * @return A reference to the data of the (key,data) %pair.
979 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
980 * data associated with the key specified in subscript. If the key does
981 * not exist, a pair with that key is created using default values, which
984 * Lookup requires constant time.
987 operator[](const key_type
& __k
)
988 { return _M_h
[__k
]; }
991 operator[](key_type
&& __k
)
992 { return _M_h
[std::move(__k
)]; }
997 * @brief Access to %unordered_map data.
998 * @param __k The key for which data should be retrieved.
999 * @return A reference to the data whose key is equal to @a __k, if
1000 * such a data is present in the %unordered_map.
1001 * @throw std::out_of_range If no such data is present.
1004 at(const key_type
& __k
)
1005 { return _M_h
.at(__k
); }
1008 at(const key_type
& __k
) const
1009 { return _M_h
.at(__k
); }
1012 // bucket interface.
1014 /// Returns the number of buckets of the %unordered_map.
1016 bucket_count() const noexcept
1017 { return _M_h
.bucket_count(); }
1019 /// Returns the maximum number of buckets of the %unordered_map.
1021 max_bucket_count() const noexcept
1022 { return _M_h
.max_bucket_count(); }
1025 * @brief Returns the number of elements in a given bucket.
1026 * @param __n A bucket index.
1027 * @return The number of elements in the bucket.
1030 bucket_size(size_type __n
) const
1031 { return _M_h
.bucket_size(__n
); }
1034 * @brief Returns the bucket index of a given element.
1035 * @param __key A key instance.
1036 * @return The key bucket index.
1039 bucket(const key_type
& __key
) const
1040 { return _M_h
.bucket(__key
); }
1043 * @brief Returns a read/write iterator pointing to the first bucket
1045 * @param __n The bucket index.
1046 * @return A read/write local iterator.
1049 begin(size_type __n
)
1050 { return _M_h
.begin(__n
); }
1054 * @brief Returns a read-only (constant) iterator pointing to the first
1056 * @param __n The bucket index.
1057 * @return A read-only local iterator.
1059 const_local_iterator
1060 begin(size_type __n
) const
1061 { return _M_h
.begin(__n
); }
1063 const_local_iterator
1064 cbegin(size_type __n
) const
1065 { return _M_h
.cbegin(__n
); }
1069 * @brief Returns a read/write iterator pointing to one past the last
1071 * @param __n The bucket index.
1072 * @return A read/write local iterator.
1076 { return _M_h
.end(__n
); }
1080 * @brief Returns a read-only (constant) iterator pointing to one past
1081 * the last bucket elements.
1082 * @param __n The bucket index.
1083 * @return A read-only local iterator.
1085 const_local_iterator
1086 end(size_type __n
) const
1087 { return _M_h
.end(__n
); }
1089 const_local_iterator
1090 cend(size_type __n
) const
1091 { return _M_h
.cend(__n
); }
1096 /// Returns the average number of elements per bucket.
1098 load_factor() const noexcept
1099 { return _M_h
.load_factor(); }
1101 /// Returns a positive number that the %unordered_map tries to keep the
1102 /// load factor less than or equal to.
1104 max_load_factor() const noexcept
1105 { return _M_h
.max_load_factor(); }
1108 * @brief Change the %unordered_map maximum load factor.
1109 * @param __z The new maximum load factor.
1112 max_load_factor(float __z
)
1113 { _M_h
.max_load_factor(__z
); }
1116 * @brief May rehash the %unordered_map.
1117 * @param __n The new number of buckets.
1119 * Rehash will occur only if the new number of buckets respect the
1120 * %unordered_map maximum load factor.
1123 rehash(size_type __n
)
1124 { _M_h
.rehash(__n
); }
1127 * @brief Prepare the %unordered_map for a specified number of
1129 * @param __n Number of elements required.
1131 * Same as rehash(ceil(n / max_load_factor())).
1134 reserve(size_type __n
)
1135 { _M_h
.reserve(__n
); }
1137 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1140 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1141 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1144 #if __cpp_deduction_guides >= 201606
1146 template<typename _InputIterator
,
1147 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1148 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1149 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1150 typename
= _RequireInputIter
<_InputIterator
>,
1151 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1152 typename
= _RequireNotAllocator
<_Pred
>,
1153 typename
= _RequireAllocator
<_Allocator
>>
1154 unordered_map(_InputIterator
, _InputIterator
,
1155 typename unordered_map
<int, int>::size_type
= {},
1156 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1157 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1158 __iter_val_t
<_InputIterator
>,
1159 _Hash
, _Pred
, _Allocator
>;
1161 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
1162 typename _Pred
= equal_to
<_Key
>,
1163 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
1164 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1165 typename
= _RequireNotAllocator
<_Pred
>,
1166 typename
= _RequireAllocator
<_Allocator
>>
1167 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1168 typename unordered_map
<int, int>::size_type
= {},
1169 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1170 -> unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
1172 template<typename _InputIterator
, typename _Allocator
,
1173 typename
= _RequireInputIter
<_InputIterator
>,
1174 typename
= _RequireAllocator
<_Allocator
>>
1175 unordered_map(_InputIterator
, _InputIterator
,
1176 typename unordered_map
<int, int>::size_type
, _Allocator
)
1177 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1178 __iter_val_t
<_InputIterator
>,
1179 hash
<__iter_key_t
<_InputIterator
>>,
1180 equal_to
<__iter_key_t
<_InputIterator
>>,
1183 template<typename _InputIterator
, typename _Allocator
,
1184 typename
= _RequireInputIter
<_InputIterator
>,
1185 typename
= _RequireAllocator
<_Allocator
>>
1186 unordered_map(_InputIterator
, _InputIterator
, _Allocator
)
1187 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1188 __iter_val_t
<_InputIterator
>,
1189 hash
<__iter_key_t
<_InputIterator
>>,
1190 equal_to
<__iter_key_t
<_InputIterator
>>,
1193 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
1194 typename
= _RequireInputIter
<_InputIterator
>,
1195 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1196 typename
= _RequireAllocator
<_Allocator
>>
1197 unordered_map(_InputIterator
, _InputIterator
,
1198 typename unordered_map
<int, int>::size_type
,
1200 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1201 __iter_val_t
<_InputIterator
>, _Hash
,
1202 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
1204 template<typename _Key
, typename _Tp
, typename _Allocator
,
1205 typename
= _RequireAllocator
<_Allocator
>>
1206 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1207 typename unordered_map
<int, int>::size_type
,
1209 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1211 template<typename _Key
, typename _Tp
, typename _Allocator
,
1212 typename
= _RequireAllocator
<_Allocator
>>
1213 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
1214 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1216 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
1217 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
1218 typename
= _RequireAllocator
<_Allocator
>>
1219 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1220 typename unordered_map
<int, int>::size_type
,
1222 -> unordered_map
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
1227 * @brief A standard container composed of equivalent keys
1228 * (possibly containing multiple of each key value) that associates
1229 * values of another type with the keys.
1231 * @ingroup unordered_associative_containers
1232 * @headerfile unordered_map
1235 * @tparam _Key Type of key objects.
1236 * @tparam _Tp Type of mapped objects.
1237 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1238 * @tparam _Pred Predicate function object type, defaults
1239 * to equal_to<_Value>.
1240 * @tparam _Alloc Allocator type, defaults to
1241 * std::allocator<std::pair<const _Key, _Tp>>.
1243 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1244 * <a href="tables.html#xx">unordered associative container</a>
1246 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1248 * Base is _Hashtable, dispatched at compile time via template
1249 * alias __ummap_hashtable.
1251 template<typename _Key
, typename _Tp
,
1252 typename _Hash
= hash
<_Key
>,
1253 typename _Pred
= equal_to
<_Key
>,
1254 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
1255 class unordered_multimap
1257 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1263 /// Public typedefs.
1264 typedef typename
_Hashtable::key_type key_type
;
1265 typedef typename
_Hashtable::value_type value_type
;
1266 typedef typename
_Hashtable::mapped_type mapped_type
;
1267 typedef typename
_Hashtable::hasher hasher
;
1268 typedef typename
_Hashtable::key_equal key_equal
;
1269 typedef typename
_Hashtable::allocator_type allocator_type
;
1273 /// Iterator-related typedefs.
1274 typedef typename
_Hashtable::pointer pointer
;
1275 typedef typename
_Hashtable::const_pointer const_pointer
;
1276 typedef typename
_Hashtable::reference reference
;
1277 typedef typename
_Hashtable::const_reference const_reference
;
1278 typedef typename
_Hashtable::iterator iterator
;
1279 typedef typename
_Hashtable::const_iterator const_iterator
;
1280 typedef typename
_Hashtable::local_iterator local_iterator
;
1281 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1282 typedef typename
_Hashtable::size_type size_type
;
1283 typedef typename
_Hashtable::difference_type difference_type
;
1286 #if __cplusplus > 201402L
1287 using node_type
= typename
_Hashtable::node_type
;
1290 //construct/destroy/copy
1292 /// Default constructor.
1293 unordered_multimap() = default;
1296 * @brief Default constructor creates no elements.
1297 * @param __n Mnimal initial number of buckets.
1298 * @param __hf A hash functor.
1299 * @param __eql A key equality functor.
1300 * @param __a An allocator object.
1303 unordered_multimap(size_type __n
,
1304 const hasher
& __hf
= hasher(),
1305 const key_equal
& __eql
= key_equal(),
1306 const allocator_type
& __a
= allocator_type())
1307 : _M_h(__n
, __hf
, __eql
, __a
)
1311 * @brief Builds an %unordered_multimap from a range.
1312 * @param __first An input iterator.
1313 * @param __last An input iterator.
1314 * @param __n Minimal initial number of buckets.
1315 * @param __hf A hash functor.
1316 * @param __eql A key equality functor.
1317 * @param __a An allocator object.
1319 * Create an %unordered_multimap consisting of copies of the elements
1320 * from [__first,__last). This is linear in N (where N is
1321 * distance(__first,__last)).
1323 template<typename _InputIterator
>
1324 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1326 const hasher
& __hf
= hasher(),
1327 const key_equal
& __eql
= key_equal(),
1328 const allocator_type
& __a
= allocator_type())
1329 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1332 /// Copy constructor.
1333 unordered_multimap(const unordered_multimap
&) = default;
1335 /// Move constructor.
1336 unordered_multimap(unordered_multimap
&&) = default;
1339 * @brief Creates an %unordered_multimap with no elements.
1340 * @param __a An allocator object.
1343 unordered_multimap(const allocator_type
& __a
)
1348 * @brief Copy constructor with allocator argument.
1349 * @param __uset Input %unordered_multimap to copy.
1350 * @param __a An allocator object.
1352 unordered_multimap(const unordered_multimap
& __ummap
,
1353 const allocator_type
& __a
)
1354 : _M_h(__ummap
._M_h
, __a
)
1358 * @brief Move constructor with allocator argument.
1359 * @param __uset Input %unordered_multimap to move.
1360 * @param __a An allocator object.
1362 unordered_multimap(unordered_multimap
&& __ummap
,
1363 const allocator_type
& __a
)
1364 noexcept( noexcept(_Hashtable(std::move(__ummap
._M_h
), __a
)) )
1365 : _M_h(std::move(__ummap
._M_h
), __a
)
1369 * @brief Builds an %unordered_multimap from an initializer_list.
1370 * @param __l An initializer_list.
1371 * @param __n Minimal initial number of buckets.
1372 * @param __hf A hash functor.
1373 * @param __eql A key equality functor.
1374 * @param __a An allocator object.
1376 * Create an %unordered_multimap consisting of copies of the elements in
1377 * the list. This is linear in N (where N is @a __l.size()).
1379 unordered_multimap(initializer_list
<value_type
> __l
,
1381 const hasher
& __hf
= hasher(),
1382 const key_equal
& __eql
= key_equal(),
1383 const allocator_type
& __a
= allocator_type())
1384 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1387 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1388 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1391 unordered_multimap(size_type __n
, const hasher
& __hf
,
1392 const allocator_type
& __a
)
1393 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1396 template<typename _InputIterator
>
1397 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1399 const allocator_type
& __a
)
1400 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1403 template<typename _InputIterator
>
1404 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1405 size_type __n
, const hasher
& __hf
,
1406 const allocator_type
& __a
)
1407 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1410 unordered_multimap(initializer_list
<value_type
> __l
,
1412 const allocator_type
& __a
)
1413 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1416 unordered_multimap(initializer_list
<value_type
> __l
,
1417 size_type __n
, const hasher
& __hf
,
1418 const allocator_type
& __a
)
1419 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1422 /// Copy assignment operator.
1424 operator=(const unordered_multimap
&) = default;
1426 /// Move assignment operator.
1428 operator=(unordered_multimap
&&) = default;
1431 * @brief %Unordered_multimap list assignment operator.
1432 * @param __l An initializer_list.
1434 * This function fills an %unordered_multimap with copies of the
1435 * elements in the initializer list @a __l.
1437 * Note that the assignment completely changes the %unordered_multimap
1438 * and that the resulting %unordered_multimap's size is the same as the
1439 * number of elements assigned.
1442 operator=(initializer_list
<value_type
> __l
)
1448 /// Returns the allocator object used by the %unordered_multimap.
1450 get_allocator() const noexcept
1451 { return _M_h
.get_allocator(); }
1453 // size and capacity:
1455 /// Returns true if the %unordered_multimap is empty.
1456 _GLIBCXX_NODISCARD
bool
1457 empty() const noexcept
1458 { return _M_h
.empty(); }
1460 /// Returns the size of the %unordered_multimap.
1462 size() const noexcept
1463 { return _M_h
.size(); }
1465 /// Returns the maximum size of the %unordered_multimap.
1467 max_size() const noexcept
1468 { return _M_h
.max_size(); }
1473 * Returns a read/write iterator that points to the first element in the
1474 * %unordered_multimap.
1478 { return _M_h
.begin(); }
1482 * Returns a read-only (constant) iterator that points to the first
1483 * element in the %unordered_multimap.
1486 begin() const noexcept
1487 { return _M_h
.begin(); }
1490 cbegin() const noexcept
1491 { return _M_h
.begin(); }
1495 * Returns a read/write iterator that points one past the last element in
1496 * the %unordered_multimap.
1500 { return _M_h
.end(); }
1504 * Returns a read-only (constant) iterator that points one past the last
1505 * element in the %unordered_multimap.
1508 end() const noexcept
1509 { return _M_h
.end(); }
1512 cend() const noexcept
1513 { return _M_h
.end(); }
1519 * @brief Attempts to build and insert a std::pair into the
1520 * %unordered_multimap.
1522 * @param __args Arguments used to generate a new pair instance (see
1523 * std::piecewise_contruct for passing arguments to each
1524 * part of the pair constructor).
1526 * @return An iterator that points to the inserted pair.
1528 * This function attempts to build and insert a (key, value) %pair into
1529 * the %unordered_multimap.
1531 * Insertion requires amortized constant time.
1533 template<typename
... _Args
>
1535 emplace(_Args
&&... __args
)
1536 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1539 * @brief Attempts to build and insert a std::pair into the
1540 * %unordered_multimap.
1542 * @param __pos An iterator that serves as a hint as to where the pair
1543 * should be inserted.
1544 * @param __args Arguments used to generate a new pair instance (see
1545 * std::piecewise_contruct for passing arguments to each
1546 * part of the pair constructor).
1547 * @return An iterator that points to the element with key of the
1548 * std::pair built from @a __args.
1550 * Note that the first parameter is only a hint and can potentially
1551 * improve the performance of the insertion process. A bad hint would
1552 * cause no gains in efficiency.
1555 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1556 * for more on @a hinting.
1558 * Insertion requires amortized constant time.
1560 template<typename
... _Args
>
1562 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1563 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1567 * @brief Inserts a std::pair into the %unordered_multimap.
1568 * @param __x Pair to be inserted (see std::make_pair for easy
1569 * creation of pairs).
1571 * @return An iterator that points to the inserted pair.
1573 * Insertion requires amortized constant time.
1576 insert(const value_type
& __x
)
1577 { return _M_h
.insert(__x
); }
1580 insert(value_type
&& __x
)
1581 { return _M_h
.insert(std::move(__x
)); }
1583 template<typename _Pair
>
1584 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1586 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
1591 * @brief Inserts a std::pair into the %unordered_multimap.
1592 * @param __hint An iterator that serves as a hint as to where the
1593 * pair should be inserted.
1594 * @param __x Pair to be inserted (see std::make_pair for easy creation
1596 * @return An iterator that points to the element with key of
1597 * @a __x (may or may not be the %pair passed in).
1599 * Note that the first parameter is only a hint and can potentially
1600 * improve the performance of the insertion process. A bad hint would
1601 * cause no gains in efficiency.
1604 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1605 * for more on @a hinting.
1607 * Insertion requires amortized constant time.
1610 insert(const_iterator __hint
, const value_type
& __x
)
1611 { return _M_h
.insert(__hint
, __x
); }
1613 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1614 // 2354. Unnecessary copying when inserting into maps with braced-init
1616 insert(const_iterator __hint
, value_type
&& __x
)
1617 { return _M_h
.insert(__hint
, std::move(__x
)); }
1619 template<typename _Pair
>
1620 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1621 insert(const_iterator __hint
, _Pair
&& __x
)
1622 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
1626 * @brief A template function that attempts to insert a range of
1628 * @param __first Iterator pointing to the start of the range to be
1630 * @param __last Iterator pointing to the end of the range.
1632 * Complexity similar to that of the range constructor.
1634 template<typename _InputIterator
>
1636 insert(_InputIterator __first
, _InputIterator __last
)
1637 { _M_h
.insert(__first
, __last
); }
1640 * @brief Attempts to insert a list of elements into the
1641 * %unordered_multimap.
1642 * @param __l A std::initializer_list<value_type> of elements
1645 * Complexity similar to that of the range constructor.
1648 insert(initializer_list
<value_type
> __l
)
1649 { _M_h
.insert(__l
); }
1651 #if __cplusplus > 201402L
1654 extract(const_iterator __pos
)
1656 __glibcxx_assert(__pos
!= end());
1657 return _M_h
.extract(__pos
);
1662 extract(const key_type
& __key
)
1663 { return _M_h
.extract(__key
); }
1665 /// Re-insert an extracted node.
1667 insert(node_type
&& __nh
)
1668 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1670 /// Re-insert an extracted node.
1672 insert(const_iterator __hint
, node_type
&& __nh
)
1673 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1678 * @brief Erases an element from an %unordered_multimap.
1679 * @param __position An iterator pointing to the element to be erased.
1680 * @return An iterator pointing to the element immediately following
1681 * @a __position prior to the element being erased. If no such
1682 * element exists, end() is returned.
1684 * This function erases an element, pointed to by the given iterator,
1685 * from an %unordered_multimap.
1686 * Note that this function only erases the element, and that if the
1687 * element is itself a pointer, the pointed-to memory is not touched in
1688 * any way. Managing the pointer is the user's responsibility.
1691 erase(const_iterator __position
)
1692 { return _M_h
.erase(__position
); }
1696 erase(iterator __position
)
1697 { return _M_h
.erase(__position
); }
1701 * @brief Erases elements according to the provided key.
1702 * @param __x Key of elements to be erased.
1703 * @return The number of elements erased.
1705 * This function erases all the elements located by the given key from
1706 * an %unordered_multimap.
1707 * Note that this function only erases the element, and that if the
1708 * element is itself a pointer, the pointed-to memory is not touched in
1709 * any way. Managing the pointer is the user's responsibility.
1712 erase(const key_type
& __x
)
1713 { return _M_h
.erase(__x
); }
1716 * @brief Erases a [__first,__last) range of elements from an
1717 * %unordered_multimap.
1718 * @param __first Iterator pointing to the start of the range to be
1720 * @param __last Iterator pointing to the end of the range to
1722 * @return The iterator @a __last.
1724 * This function erases a sequence of elements from an
1725 * %unordered_multimap.
1726 * Note that this function only erases the elements, and that if
1727 * the element is itself a pointer, the pointed-to memory is not touched
1728 * in any way. Managing the pointer is the user's responsibility.
1731 erase(const_iterator __first
, const_iterator __last
)
1732 { return _M_h
.erase(__first
, __last
); }
1735 * Erases all elements in an %unordered_multimap.
1736 * Note that this function only erases the elements, and that if the
1737 * elements themselves are pointers, the pointed-to memory is not touched
1738 * in any way. Managing the pointer is the user's responsibility.
1745 * @brief Swaps data with another %unordered_multimap.
1746 * @param __x An %unordered_multimap of the same element and allocator
1749 * This exchanges the elements between two %unordered_multimap in
1751 * Note that the global std::swap() function is specialized such that
1752 * std::swap(m1,m2) will feed to this function.
1755 swap(unordered_multimap
& __x
)
1756 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1757 { _M_h
.swap(__x
._M_h
); }
1759 #if __cplusplus > 201402L
1760 template<typename
, typename
, typename
>
1761 friend class std::_Hash_merge_helper
;
1763 template<typename _H2
, typename _P2
>
1765 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1768 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1769 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1772 template<typename _H2
, typename _P2
>
1774 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1775 { merge(__source
); }
1777 template<typename _H2
, typename _P2
>
1779 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1782 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1783 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1786 template<typename _H2
, typename _P2
>
1788 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1789 { merge(__source
); }
1794 /// Returns the hash functor object with which the %unordered_multimap
1795 /// was constructed.
1797 hash_function() const
1798 { return _M_h
.hash_function(); }
1800 /// Returns the key comparison object with which the %unordered_multimap
1801 /// was constructed.
1804 { return _M_h
.key_eq(); }
1810 * @brief Tries to locate an element in an %unordered_multimap.
1811 * @param __x Key to be located.
1812 * @return Iterator pointing to sought-after element, or end() if not
1815 * This function takes a key and tries to locate the element with which
1816 * the key matches. If successful the function returns an iterator
1817 * pointing to the sought after element. If unsuccessful it returns the
1818 * past-the-end ( @c end() ) iterator.
1821 find(const key_type
& __x
)
1822 { return _M_h
.find(__x
); }
1824 #if __cplusplus > 201703L
1825 template<typename _Kt
>
1827 find(const _Kt
& __x
) -> decltype(_M_h
._M_find_tr(__x
))
1828 { return _M_h
._M_find_tr(__x
); }
1832 find(const key_type
& __x
) const
1833 { return _M_h
.find(__x
); }
1835 #if __cplusplus > 201703L
1836 template<typename _Kt
>
1838 find(const _Kt
& __x
) const -> decltype(_M_h
._M_find_tr(__x
))
1839 { return _M_h
._M_find_tr(__x
); }
1845 * @brief Finds the number of elements.
1846 * @param __x Key to count.
1847 * @return Number of elements with specified key.
1850 count(const key_type
& __x
) const
1851 { return _M_h
.count(__x
); }
1853 #if __cplusplus > 201703L
1854 template<typename _Kt
>
1856 count(const _Kt
& __x
) const -> decltype(_M_h
._M_count_tr(__x
))
1857 { return _M_h
._M_count_tr(__x
); }
1861 #if __cplusplus > 201703L
1864 * @brief Finds whether an element with the given key exists.
1865 * @param __x Key of elements to be located.
1866 * @return True if there is any element with the specified key.
1869 contains(const key_type
& __x
) const
1870 { return _M_h
.find(__x
) != _M_h
.end(); }
1872 template<typename _Kt
>
1874 contains(const _Kt
& __x
) const
1875 -> decltype(_M_h
._M_find_tr(__x
), void(), true)
1876 { return _M_h
._M_find_tr(__x
) != _M_h
.end(); }
1882 * @brief Finds a subsequence matching given key.
1883 * @param __x Key to be located.
1884 * @return Pair of iterators that possibly points to the subsequence
1885 * matching given key.
1887 std::pair
<iterator
, iterator
>
1888 equal_range(const key_type
& __x
)
1889 { return _M_h
.equal_range(__x
); }
1891 #if __cplusplus > 201703L
1892 template<typename _Kt
>
1894 equal_range(const _Kt
& __x
)
1895 -> decltype(_M_h
._M_equal_range_tr(__x
))
1896 { return _M_h
._M_equal_range_tr(__x
); }
1899 std::pair
<const_iterator
, const_iterator
>
1900 equal_range(const key_type
& __x
) const
1901 { return _M_h
.equal_range(__x
); }
1903 #if __cplusplus > 201703L
1904 template<typename _Kt
>
1906 equal_range(const _Kt
& __x
) const
1907 -> decltype(_M_h
._M_equal_range_tr(__x
))
1908 { return _M_h
._M_equal_range_tr(__x
); }
1912 // bucket interface.
1914 /// Returns the number of buckets of the %unordered_multimap.
1916 bucket_count() const noexcept
1917 { return _M_h
.bucket_count(); }
1919 /// Returns the maximum number of buckets of the %unordered_multimap.
1921 max_bucket_count() const noexcept
1922 { return _M_h
.max_bucket_count(); }
1925 * @brief Returns the number of elements in a given bucket.
1926 * @param __n A bucket index.
1927 * @return The number of elements in the bucket.
1930 bucket_size(size_type __n
) const
1931 { return _M_h
.bucket_size(__n
); }
1934 * @brief Returns the bucket index of a given element.
1935 * @param __key A key instance.
1936 * @return The key bucket index.
1939 bucket(const key_type
& __key
) const
1940 { return _M_h
.bucket(__key
); }
1943 * @brief Returns a read/write iterator pointing to the first bucket
1945 * @param __n The bucket index.
1946 * @return A read/write local iterator.
1949 begin(size_type __n
)
1950 { return _M_h
.begin(__n
); }
1954 * @brief Returns a read-only (constant) iterator pointing to the first
1956 * @param __n The bucket index.
1957 * @return A read-only local iterator.
1959 const_local_iterator
1960 begin(size_type __n
) const
1961 { return _M_h
.begin(__n
); }
1963 const_local_iterator
1964 cbegin(size_type __n
) const
1965 { return _M_h
.cbegin(__n
); }
1969 * @brief Returns a read/write iterator pointing to one past the last
1971 * @param __n The bucket index.
1972 * @return A read/write local iterator.
1976 { return _M_h
.end(__n
); }
1980 * @brief Returns a read-only (constant) iterator pointing to one past
1981 * the last bucket elements.
1982 * @param __n The bucket index.
1983 * @return A read-only local iterator.
1985 const_local_iterator
1986 end(size_type __n
) const
1987 { return _M_h
.end(__n
); }
1989 const_local_iterator
1990 cend(size_type __n
) const
1991 { return _M_h
.cend(__n
); }
1996 /// Returns the average number of elements per bucket.
1998 load_factor() const noexcept
1999 { return _M_h
.load_factor(); }
2001 /// Returns a positive number that the %unordered_multimap tries to keep
2002 /// the load factor less than or equal to.
2004 max_load_factor() const noexcept
2005 { return _M_h
.max_load_factor(); }
2008 * @brief Change the %unordered_multimap maximum load factor.
2009 * @param __z The new maximum load factor.
2012 max_load_factor(float __z
)
2013 { _M_h
.max_load_factor(__z
); }
2016 * @brief May rehash the %unordered_multimap.
2017 * @param __n The new number of buckets.
2019 * Rehash will occur only if the new number of buckets respect the
2020 * %unordered_multimap maximum load factor.
2023 rehash(size_type __n
)
2024 { _M_h
.rehash(__n
); }
2027 * @brief Prepare the %unordered_multimap for a specified number of
2029 * @param __n Number of elements required.
2031 * Same as rehash(ceil(n / max_load_factor())).
2034 reserve(size_type __n
)
2035 { _M_h
.reserve(__n
); }
2037 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
2040 operator==(const unordered_multimap
<_Key1
, _Tp1
,
2041 _Hash1
, _Pred1
, _Alloc1
>&,
2042 const unordered_multimap
<_Key1
, _Tp1
,
2043 _Hash1
, _Pred1
, _Alloc1
>&);
2046 #if __cpp_deduction_guides >= 201606
2048 template<typename _InputIterator
,
2049 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
2050 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
2051 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
2052 typename
= _RequireInputIter
<_InputIterator
>,
2053 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2054 typename
= _RequireNotAllocator
<_Pred
>,
2055 typename
= _RequireAllocator
<_Allocator
>>
2056 unordered_multimap(_InputIterator
, _InputIterator
,
2057 unordered_multimap
<int, int>::size_type
= {},
2058 _Hash
= _Hash(), _Pred
= _Pred(),
2059 _Allocator
= _Allocator())
2060 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2061 __iter_val_t
<_InputIterator
>, _Hash
, _Pred
,
2064 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
2065 typename _Pred
= equal_to
<_Key
>,
2066 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
2067 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2068 typename
= _RequireNotAllocator
<_Pred
>,
2069 typename
= _RequireAllocator
<_Allocator
>>
2070 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2071 unordered_multimap
<int, int>::size_type
= {},
2072 _Hash
= _Hash(), _Pred
= _Pred(),
2073 _Allocator
= _Allocator())
2074 -> unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
2076 template<typename _InputIterator
, typename _Allocator
,
2077 typename
= _RequireInputIter
<_InputIterator
>,
2078 typename
= _RequireAllocator
<_Allocator
>>
2079 unordered_multimap(_InputIterator
, _InputIterator
,
2080 unordered_multimap
<int, int>::size_type
, _Allocator
)
2081 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2082 __iter_val_t
<_InputIterator
>,
2083 hash
<__iter_key_t
<_InputIterator
>>,
2084 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2086 template<typename _InputIterator
, typename _Allocator
,
2087 typename
= _RequireInputIter
<_InputIterator
>,
2088 typename
= _RequireAllocator
<_Allocator
>>
2089 unordered_multimap(_InputIterator
, _InputIterator
, _Allocator
)
2090 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2091 __iter_val_t
<_InputIterator
>,
2092 hash
<__iter_key_t
<_InputIterator
>>,
2093 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2095 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
2096 typename
= _RequireInputIter
<_InputIterator
>,
2097 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2098 typename
= _RequireAllocator
<_Allocator
>>
2099 unordered_multimap(_InputIterator
, _InputIterator
,
2100 unordered_multimap
<int, int>::size_type
, _Hash
,
2102 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2103 __iter_val_t
<_InputIterator
>, _Hash
,
2104 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2106 template<typename _Key
, typename _Tp
, typename _Allocator
,
2107 typename
= _RequireAllocator
<_Allocator
>>
2108 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2109 unordered_multimap
<int, int>::size_type
,
2111 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2113 template<typename _Key
, typename _Tp
, typename _Allocator
,
2114 typename
= _RequireAllocator
<_Allocator
>>
2115 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
2116 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2118 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
2119 typename
= _RequireNotAllocatorOrIntegral
<_Hash
>,
2120 typename
= _RequireAllocator
<_Allocator
>>
2121 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2122 unordered_multimap
<int, int>::size_type
,
2124 -> unordered_multimap
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
2128 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2130 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2131 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2132 noexcept(noexcept(__x
.swap(__y
)))
2135 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2137 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2138 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2139 noexcept(noexcept(__x
.swap(__y
)))
2142 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2144 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2145 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2146 { return __x
._M_h
._M_equal(__y
._M_h
); }
2148 #if __cpp_impl_three_way_comparison < 201907L
2149 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2151 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2152 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2153 { return !(__x
== __y
); }
2156 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2158 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2159 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2160 { return __x
._M_h
._M_equal(__y
._M_h
); }
2162 #if __cpp_impl_three_way_comparison < 201907L
2163 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2165 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2166 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2167 { return !(__x
== __y
); }
2170 _GLIBCXX_END_NAMESPACE_CONTAINER
2172 #if __cplusplus > 201402L
2173 // Allow std::unordered_map access to internals of compatible maps.
2174 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2175 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2176 struct _Hash_merge_helper
<
2177 _GLIBCXX_STD_C::unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2181 template<typename
... _Tp
>
2182 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2183 template<typename
... _Tp
>
2184 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2186 friend unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2189 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2190 { return __map
._M_h
; }
2193 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2194 { return __map
._M_h
; }
2197 // Allow std::unordered_multimap access to internals of compatible maps.
2198 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2199 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2200 struct _Hash_merge_helper
<
2201 _GLIBCXX_STD_C::unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2205 template<typename
... _Tp
>
2206 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2207 template<typename
... _Tp
>
2208 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2210 friend unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2213 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2214 { return __map
._M_h
; }
2217 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2218 { return __map
._M_h
; }
2222 _GLIBCXX_END_NAMESPACE_VERSION
2225 #endif /* _UNORDERED_MAP_H */