1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2019 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 : _M_h(std::move(__umap
._M_h
), __a
)
216 * @brief Builds an %unordered_map from an initializer_list.
217 * @param __l An initializer_list.
218 * @param __n Minimal initial number of buckets.
219 * @param __hf A hash functor.
220 * @param __eql A key equality functor.
221 * @param __a An allocator object.
223 * Create an %unordered_map consisting of copies of the elements in the
224 * list. This is linear in N (where N is @a __l.size()).
226 unordered_map(initializer_list
<value_type
> __l
,
228 const hasher
& __hf
= hasher(),
229 const key_equal
& __eql
= key_equal(),
230 const allocator_type
& __a
= allocator_type())
231 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
234 unordered_map(size_type __n
, const allocator_type
& __a
)
235 : unordered_map(__n
, hasher(), key_equal(), __a
)
238 unordered_map(size_type __n
, const hasher
& __hf
,
239 const allocator_type
& __a
)
240 : unordered_map(__n
, __hf
, key_equal(), __a
)
243 template<typename _InputIterator
>
244 unordered_map(_InputIterator __first
, _InputIterator __last
,
246 const allocator_type
& __a
)
247 : unordered_map(__first
, __last
, __n
, hasher(), key_equal(), __a
)
250 template<typename _InputIterator
>
251 unordered_map(_InputIterator __first
, _InputIterator __last
,
252 size_type __n
, const hasher
& __hf
,
253 const allocator_type
& __a
)
254 : unordered_map(__first
, __last
, __n
, __hf
, key_equal(), __a
)
257 unordered_map(initializer_list
<value_type
> __l
,
259 const allocator_type
& __a
)
260 : unordered_map(__l
, __n
, hasher(), key_equal(), __a
)
263 unordered_map(initializer_list
<value_type
> __l
,
264 size_type __n
, const hasher
& __hf
,
265 const allocator_type
& __a
)
266 : unordered_map(__l
, __n
, __hf
, key_equal(), __a
)
269 /// Copy assignment operator.
271 operator=(const unordered_map
&) = default;
273 /// Move assignment operator.
275 operator=(unordered_map
&&) = default;
278 * @brief %Unordered_map list assignment operator.
279 * @param __l An initializer_list.
281 * This function fills an %unordered_map with copies of the elements in
282 * the initializer list @a __l.
284 * Note that the assignment completely changes the %unordered_map and
285 * that the resulting %unordered_map's size is the same as the number
286 * of elements assigned.
289 operator=(initializer_list
<value_type
> __l
)
295 /// Returns the allocator object used by the %unordered_map.
297 get_allocator() const noexcept
298 { return _M_h
.get_allocator(); }
300 // size and capacity:
302 /// Returns true if the %unordered_map is empty.
304 empty() const noexcept
305 { return _M_h
.empty(); }
307 /// Returns the size of the %unordered_map.
309 size() const noexcept
310 { return _M_h
.size(); }
312 /// Returns the maximum size of the %unordered_map.
314 max_size() const noexcept
315 { return _M_h
.max_size(); }
320 * Returns a read/write iterator that points to the first element in the
325 { return _M_h
.begin(); }
329 * Returns a read-only (constant) iterator that points to the first
330 * element in the %unordered_map.
333 begin() const noexcept
334 { return _M_h
.begin(); }
337 cbegin() const noexcept
338 { return _M_h
.begin(); }
342 * Returns a read/write iterator that points one past the last element in
343 * the %unordered_map.
347 { return _M_h
.end(); }
351 * Returns a read-only (constant) iterator that points one past the last
352 * element in the %unordered_map.
356 { return _M_h
.end(); }
359 cend() const noexcept
360 { return _M_h
.end(); }
366 * @brief Attempts to build and insert a std::pair into the
369 * @param __args Arguments used to generate a new pair instance (see
370 * std::piecewise_contruct for passing arguments to each
371 * part of the pair constructor).
373 * @return A pair, of which the first element is an iterator that points
374 * to the possibly inserted pair, and the second is a bool that
375 * is true if the pair was actually inserted.
377 * This function attempts to build and insert a (key, value) %pair into
378 * the %unordered_map.
379 * An %unordered_map relies on unique keys and thus a %pair is only
380 * inserted if its first element (the key) is not already present in the
383 * Insertion requires amortized constant time.
385 template<typename
... _Args
>
386 std::pair
<iterator
, bool>
387 emplace(_Args
&&... __args
)
388 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
391 * @brief Attempts to build and insert a std::pair into the
394 * @param __pos An iterator that serves as a hint as to where the pair
395 * should be inserted.
396 * @param __args Arguments used to generate a new pair instance (see
397 * std::piecewise_contruct for passing arguments to each
398 * part of the pair constructor).
399 * @return An iterator that points to the element with key of the
400 * std::pair built from @a __args (may or may not be that
403 * This function is not concerned about whether the insertion took place,
404 * and thus does not return a boolean like the single-argument emplace()
406 * Note that the first parameter is only a hint and can potentially
407 * improve the performance of the insertion process. A bad hint would
408 * cause no gains in efficiency.
411 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
412 * for more on @a hinting.
414 * Insertion requires amortized constant time.
416 template<typename
... _Args
>
418 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
419 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
421 #if __cplusplus > 201402L
424 extract(const_iterator __pos
)
426 __glibcxx_assert(__pos
!= end());
427 return _M_h
.extract(__pos
);
432 extract(const key_type
& __key
)
433 { return _M_h
.extract(__key
); }
435 /// Re-insert an extracted node.
437 insert(node_type
&& __nh
)
438 { return _M_h
._M_reinsert_node(std::move(__nh
)); }
440 /// Re-insert an extracted node.
442 insert(const_iterator
, node_type
&& __nh
)
443 { return _M_h
._M_reinsert_node(std::move(__nh
)).position
; }
445 #define __cpp_lib_unordered_map_try_emplace 201411
447 * @brief Attempts to build and insert a std::pair into the
450 * @param __k Key to use for finding a possibly existing pair in
452 * @param __args Arguments used to generate the .second for a
455 * @return A pair, of which the first element is an iterator that points
456 * to the possibly inserted pair, and the second is a bool that
457 * is true if the pair was actually inserted.
459 * This function attempts to build and insert a (key, value) %pair into
460 * the %unordered_map.
461 * An %unordered_map relies on unique keys and thus a %pair is only
462 * inserted if its first element (the key) is not already present in the
464 * If a %pair is not inserted, this function has no effect.
466 * Insertion requires amortized constant time.
468 template <typename
... _Args
>
470 try_emplace(const key_type
& __k
, _Args
&&... __args
)
472 iterator __i
= find(__k
);
475 __i
= emplace(std::piecewise_construct
,
476 std::forward_as_tuple(__k
),
477 std::forward_as_tuple(
478 std::forward
<_Args
>(__args
)...))
485 // move-capable overload
486 template <typename
... _Args
>
488 try_emplace(key_type
&& __k
, _Args
&&... __args
)
490 iterator __i
= find(__k
);
493 __i
= emplace(std::piecewise_construct
,
494 std::forward_as_tuple(std::move(__k
)),
495 std::forward_as_tuple(
496 std::forward
<_Args
>(__args
)...))
504 * @brief Attempts to build and insert a std::pair into the
507 * @param __hint An iterator that serves as a hint as to where the pair
508 * should be inserted.
509 * @param __k Key to use for finding a possibly existing pair in
511 * @param __args Arguments used to generate the .second for a
513 * @return An iterator that points to the element with key of the
514 * std::pair built from @a __args (may or may not be that
517 * This function is not concerned about whether the insertion took place,
518 * and thus does not return a boolean like the single-argument emplace()
519 * does. However, if insertion did not take place,
520 * this function has no effect.
521 * Note that the first parameter is only a hint and can potentially
522 * improve the performance of the insertion process. A bad hint would
523 * cause no gains in efficiency.
526 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
527 * for more on @a hinting.
529 * Insertion requires amortized constant time.
531 template <typename
... _Args
>
533 try_emplace(const_iterator __hint
, const key_type
& __k
,
536 iterator __i
= find(__k
);
538 __i
= emplace_hint(__hint
, std::piecewise_construct
,
539 std::forward_as_tuple(__k
),
540 std::forward_as_tuple(
541 std::forward
<_Args
>(__args
)...));
545 // move-capable overload
546 template <typename
... _Args
>
548 try_emplace(const_iterator __hint
, key_type
&& __k
, _Args
&&... __args
)
550 iterator __i
= find(__k
);
552 __i
= emplace_hint(__hint
, std::piecewise_construct
,
553 std::forward_as_tuple(std::move(__k
)),
554 std::forward_as_tuple(
555 std::forward
<_Args
>(__args
)...));
562 * @brief Attempts to insert a std::pair into the %unordered_map.
564 * @param __x Pair to be inserted (see std::make_pair for easy
565 * creation of pairs).
567 * @return A pair, of which the first element is an iterator that
568 * points to the possibly inserted pair, and the second is
569 * a bool that is true if the pair was actually inserted.
571 * This function attempts to insert a (key, value) %pair into the
572 * %unordered_map. An %unordered_map relies on unique keys and thus a
573 * %pair is only inserted if its first element (the key) is not already
574 * present in the %unordered_map.
576 * Insertion requires amortized constant time.
578 std::pair
<iterator
, bool>
579 insert(const value_type
& __x
)
580 { return _M_h
.insert(__x
); }
582 // _GLIBCXX_RESOLVE_LIB_DEFECTS
583 // 2354. Unnecessary copying when inserting into maps with braced-init
584 std::pair
<iterator
, bool>
585 insert(value_type
&& __x
)
586 { return _M_h
.insert(std::move(__x
)); }
588 template<typename _Pair
>
589 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
,
590 pair
<iterator
, bool>>
592 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
597 * @brief Attempts to insert a std::pair into the %unordered_map.
598 * @param __hint An iterator that serves as a hint as to where the
599 * pair should be inserted.
600 * @param __x Pair to be inserted (see std::make_pair for easy creation
602 * @return An iterator that points to the element with key of
603 * @a __x (may or may not be the %pair passed in).
605 * This function is not concerned about whether the insertion took place,
606 * and thus does not return a boolean like the single-argument insert()
607 * does. Note that the first parameter is only a hint and can
608 * potentially improve the performance of the insertion process. A bad
609 * hint would cause no gains in efficiency.
612 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
613 * for more on @a hinting.
615 * Insertion requires amortized constant time.
618 insert(const_iterator __hint
, const value_type
& __x
)
619 { return _M_h
.insert(__hint
, __x
); }
621 // _GLIBCXX_RESOLVE_LIB_DEFECTS
622 // 2354. Unnecessary copying when inserting into maps with braced-init
624 insert(const_iterator __hint
, value_type
&& __x
)
625 { return _M_h
.insert(__hint
, std::move(__x
)); }
627 template<typename _Pair
>
628 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
629 insert(const_iterator __hint
, _Pair
&& __x
)
630 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
634 * @brief A template function that attempts to insert a range of
636 * @param __first Iterator pointing to the start of the range to be
638 * @param __last Iterator pointing to the end of the range.
640 * Complexity similar to that of the range constructor.
642 template<typename _InputIterator
>
644 insert(_InputIterator __first
, _InputIterator __last
)
645 { _M_h
.insert(__first
, __last
); }
648 * @brief Attempts to insert a list of elements into the %unordered_map.
649 * @param __l A std::initializer_list<value_type> of elements
652 * Complexity similar to that of the range constructor.
655 insert(initializer_list
<value_type
> __l
)
656 { _M_h
.insert(__l
); }
659 #if __cplusplus > 201402L
660 #define __cpp_lib_unordered_map_insertion 201411
662 * @brief Attempts to insert a std::pair into the %unordered_map.
663 * @param __k Key to use for finding a possibly existing pair in
665 * @param __obj Argument used to generate the .second for a pair
668 * @return A pair, of which the first element is an iterator that
669 * points to the possibly inserted pair, and the second is
670 * a bool that is true if the pair was actually inserted.
672 * This function attempts to insert a (key, value) %pair into the
673 * %unordered_map. An %unordered_map relies on unique keys and thus a
674 * %pair is only inserted if its first element (the key) is not already
675 * present in the %unordered_map.
676 * If the %pair was already in the %unordered_map, the .second of
677 * the %pair is assigned from __obj.
679 * Insertion requires amortized constant time.
681 template <typename _Obj
>
683 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
685 iterator __i
= find(__k
);
688 __i
= emplace(std::piecewise_construct
,
689 std::forward_as_tuple(__k
),
690 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
694 (*__i
).second
= std::forward
<_Obj
>(__obj
);
698 // move-capable overload
699 template <typename _Obj
>
701 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
703 iterator __i
= find(__k
);
706 __i
= emplace(std::piecewise_construct
,
707 std::forward_as_tuple(std::move(__k
)),
708 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
712 (*__i
).second
= std::forward
<_Obj
>(__obj
);
717 * @brief Attempts to insert a std::pair into the %unordered_map.
718 * @param __hint An iterator that serves as a hint as to where the
719 * pair should be inserted.
720 * @param __k Key to use for finding a possibly existing pair in
722 * @param __obj Argument used to generate the .second for a pair
724 * @return An iterator that points to the element with key of
725 * @a __x (may or may not be the %pair passed in).
727 * This function is not concerned about whether the insertion took place,
728 * and thus does not return a boolean like the single-argument insert()
730 * If the %pair was already in the %unordered map, the .second of
731 * the %pair is assigned from __obj.
732 * Note that the first parameter is only a hint and can
733 * potentially improve the performance of the insertion process. A bad
734 * hint would cause no gains in efficiency.
737 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
738 * for more on @a hinting.
740 * Insertion requires amortized constant time.
742 template <typename _Obj
>
744 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
747 iterator __i
= find(__k
);
750 return emplace_hint(__hint
, std::piecewise_construct
,
751 std::forward_as_tuple(__k
),
752 std::forward_as_tuple(
753 std::forward
<_Obj
>(__obj
)));
755 (*__i
).second
= std::forward
<_Obj
>(__obj
);
759 // move-capable overload
760 template <typename _Obj
>
762 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
764 iterator __i
= find(__k
);
767 return emplace_hint(__hint
, std::piecewise_construct
,
768 std::forward_as_tuple(std::move(__k
)),
769 std::forward_as_tuple(
770 std::forward
<_Obj
>(__obj
)));
772 (*__i
).second
= std::forward
<_Obj
>(__obj
);
779 * @brief Erases an element from an %unordered_map.
780 * @param __position An iterator pointing to the element to be erased.
781 * @return An iterator pointing to the element immediately following
782 * @a __position prior to the element being erased. If no such
783 * element exists, end() is returned.
785 * This function erases an element, pointed to by the given iterator,
786 * from an %unordered_map.
787 * Note that this function only erases the element, and that if the
788 * element is itself a pointer, the pointed-to memory is not touched in
789 * any way. Managing the pointer is the user's responsibility.
792 erase(const_iterator __position
)
793 { return _M_h
.erase(__position
); }
797 erase(iterator __position
)
798 { return _M_h
.erase(__position
); }
802 * @brief Erases elements according to the provided key.
803 * @param __x Key of element to be erased.
804 * @return The number of elements erased.
806 * This function erases all the elements located by the given key from
807 * an %unordered_map. For an %unordered_map the result of this function
808 * can only be 0 (not present) or 1 (present).
809 * Note that this function only erases the element, and that if the
810 * element is itself a pointer, the pointed-to memory is not touched in
811 * any way. Managing the pointer is the user's responsibility.
814 erase(const key_type
& __x
)
815 { return _M_h
.erase(__x
); }
818 * @brief Erases a [__first,__last) range of elements from an
820 * @param __first Iterator pointing to the start of the range to be
822 * @param __last Iterator pointing to the end of the range to
824 * @return The iterator @a __last.
826 * This function erases a sequence of elements from an %unordered_map.
827 * Note that this function only erases the elements, and that if
828 * the element is itself a pointer, the pointed-to memory is not touched
829 * in any way. Managing the pointer is the user's responsibility.
832 erase(const_iterator __first
, const_iterator __last
)
833 { return _M_h
.erase(__first
, __last
); }
836 * Erases all elements in an %unordered_map.
837 * Note that this function only erases the elements, and that if the
838 * elements themselves are pointers, the pointed-to memory is not touched
839 * in any way. Managing the pointer is the user's responsibility.
846 * @brief Swaps data with another %unordered_map.
847 * @param __x An %unordered_map of the same element and allocator
850 * This exchanges the elements between two %unordered_map in constant
852 * Note that the global std::swap() function is specialized such that
853 * std::swap(m1,m2) will feed to this function.
856 swap(unordered_map
& __x
)
857 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
858 { _M_h
.swap(__x
._M_h
); }
860 #if __cplusplus > 201402L
861 template<typename
, typename
, typename
>
862 friend class std::_Hash_merge_helper
;
864 template<typename _H2
, typename _P2
>
866 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
868 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
869 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
872 template<typename _H2
, typename _P2
>
874 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
877 template<typename _H2
, typename _P2
>
879 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
881 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
882 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
885 template<typename _H2
, typename _P2
>
887 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
893 /// Returns the hash functor object with which the %unordered_map was
896 hash_function() const
897 { return _M_h
.hash_function(); }
899 /// Returns the key comparison object with which the %unordered_map was
903 { return _M_h
.key_eq(); }
909 * @brief Tries to locate an element in an %unordered_map.
910 * @param __x Key to be located.
911 * @return Iterator pointing to sought-after element, or end() if not
914 * This function takes a key and tries to locate the element with which
915 * the key matches. If successful the function returns an iterator
916 * pointing to the sought after element. If unsuccessful it returns the
917 * past-the-end ( @c end() ) iterator.
920 find(const key_type
& __x
)
921 { return _M_h
.find(__x
); }
924 find(const key_type
& __x
) const
925 { return _M_h
.find(__x
); }
929 * @brief Finds the number of elements.
930 * @param __x Key to count.
931 * @return Number of elements with specified key.
933 * This function only makes sense for %unordered_multimap; for
934 * %unordered_map the result will either be 0 (not present) or 1
938 count(const key_type
& __x
) const
939 { return _M_h
.count(__x
); }
941 #if __cplusplus > 201703L
943 * @brief Finds whether an element with the given key exists.
944 * @param __x Key of elements to be located.
945 * @return True if there is any element with the specified key.
948 contains(const key_type
& __x
) const
949 { return _M_h
.find(__x
) != _M_h
.end(); }
954 * @brief Finds a subsequence matching given key.
955 * @param __x Key to be located.
956 * @return Pair of iterators that possibly points to the subsequence
957 * matching given key.
959 * This function probably only makes sense for %unordered_multimap.
961 std::pair
<iterator
, iterator
>
962 equal_range(const key_type
& __x
)
963 { return _M_h
.equal_range(__x
); }
965 std::pair
<const_iterator
, const_iterator
>
966 equal_range(const key_type
& __x
) const
967 { return _M_h
.equal_range(__x
); }
972 * @brief Subscript ( @c [] ) access to %unordered_map data.
973 * @param __k The key for which data should be retrieved.
974 * @return A reference to the data of the (key,data) %pair.
976 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
977 * data associated with the key specified in subscript. If the key does
978 * not exist, a pair with that key is created using default values, which
981 * Lookup requires constant time.
984 operator[](const key_type
& __k
)
985 { return _M_h
[__k
]; }
988 operator[](key_type
&& __k
)
989 { return _M_h
[std::move(__k
)]; }
994 * @brief Access to %unordered_map data.
995 * @param __k The key for which data should be retrieved.
996 * @return A reference to the data whose key is equal to @a __k, if
997 * such a data is present in the %unordered_map.
998 * @throw std::out_of_range If no such data is present.
1001 at(const key_type
& __k
)
1002 { return _M_h
.at(__k
); }
1005 at(const key_type
& __k
) const
1006 { return _M_h
.at(__k
); }
1009 // bucket interface.
1011 /// Returns the number of buckets of the %unordered_map.
1013 bucket_count() const noexcept
1014 { return _M_h
.bucket_count(); }
1016 /// Returns the maximum number of buckets of the %unordered_map.
1018 max_bucket_count() const noexcept
1019 { return _M_h
.max_bucket_count(); }
1022 * @brief Returns the number of elements in a given bucket.
1023 * @param __n A bucket index.
1024 * @return The number of elements in the bucket.
1027 bucket_size(size_type __n
) const
1028 { return _M_h
.bucket_size(__n
); }
1031 * @brief Returns the bucket index of a given element.
1032 * @param __key A key instance.
1033 * @return The key bucket index.
1036 bucket(const key_type
& __key
) const
1037 { return _M_h
.bucket(__key
); }
1040 * @brief Returns a read/write iterator pointing to the first bucket
1042 * @param __n The bucket index.
1043 * @return A read/write local iterator.
1046 begin(size_type __n
)
1047 { return _M_h
.begin(__n
); }
1051 * @brief Returns a read-only (constant) iterator pointing to the first
1053 * @param __n The bucket index.
1054 * @return A read-only local iterator.
1056 const_local_iterator
1057 begin(size_type __n
) const
1058 { return _M_h
.begin(__n
); }
1060 const_local_iterator
1061 cbegin(size_type __n
) const
1062 { return _M_h
.cbegin(__n
); }
1066 * @brief Returns a read/write iterator pointing to one past the last
1068 * @param __n The bucket index.
1069 * @return A read/write local iterator.
1073 { return _M_h
.end(__n
); }
1077 * @brief Returns a read-only (constant) iterator pointing to one past
1078 * the last bucket elements.
1079 * @param __n The bucket index.
1080 * @return A read-only local iterator.
1082 const_local_iterator
1083 end(size_type __n
) const
1084 { return _M_h
.end(__n
); }
1086 const_local_iterator
1087 cend(size_type __n
) const
1088 { return _M_h
.cend(__n
); }
1093 /// Returns the average number of elements per bucket.
1095 load_factor() const noexcept
1096 { return _M_h
.load_factor(); }
1098 /// Returns a positive number that the %unordered_map tries to keep the
1099 /// load factor less than or equal to.
1101 max_load_factor() const noexcept
1102 { return _M_h
.max_load_factor(); }
1105 * @brief Change the %unordered_map maximum load factor.
1106 * @param __z The new maximum load factor.
1109 max_load_factor(float __z
)
1110 { _M_h
.max_load_factor(__z
); }
1113 * @brief May rehash the %unordered_map.
1114 * @param __n The new number of buckets.
1116 * Rehash will occur only if the new number of buckets respect the
1117 * %unordered_map maximum load factor.
1120 rehash(size_type __n
)
1121 { _M_h
.rehash(__n
); }
1124 * @brief Prepare the %unordered_map for a specified number of
1126 * @param __n Number of elements required.
1128 * Same as rehash(ceil(n / max_load_factor())).
1131 reserve(size_type __n
)
1132 { _M_h
.reserve(__n
); }
1134 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1137 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1138 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1141 #if __cpp_deduction_guides >= 201606
1143 template<typename _InputIterator
,
1144 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1145 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1146 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1147 typename
= _RequireInputIter
<_InputIterator
>,
1148 typename
= _RequireAllocator
<_Allocator
>>
1149 unordered_map(_InputIterator
, _InputIterator
,
1150 typename unordered_map
<int, int>::size_type
= {},
1151 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1152 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1153 __iter_val_t
<_InputIterator
>,
1154 _Hash
, _Pred
, _Allocator
>;
1156 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
1157 typename _Pred
= equal_to
<_Key
>,
1158 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
1159 typename
= _RequireAllocator
<_Allocator
>>
1160 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1161 typename unordered_map
<int, int>::size_type
= {},
1162 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1163 -> unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
1165 template<typename _InputIterator
, typename _Allocator
,
1166 typename
= _RequireInputIter
<_InputIterator
>,
1167 typename
= _RequireAllocator
<_Allocator
>>
1168 unordered_map(_InputIterator
, _InputIterator
,
1169 typename unordered_map
<int, int>::size_type
, _Allocator
)
1170 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1171 __iter_val_t
<_InputIterator
>,
1172 hash
<__iter_key_t
<_InputIterator
>>,
1173 equal_to
<__iter_key_t
<_InputIterator
>>,
1176 template<typename _InputIterator
, typename _Allocator
,
1177 typename
= _RequireInputIter
<_InputIterator
>,
1178 typename
= _RequireAllocator
<_Allocator
>>
1179 unordered_map(_InputIterator
, _InputIterator
, _Allocator
)
1180 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1181 __iter_val_t
<_InputIterator
>,
1182 hash
<__iter_key_t
<_InputIterator
>>,
1183 equal_to
<__iter_key_t
<_InputIterator
>>,
1186 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
1187 typename
= _RequireInputIter
<_InputIterator
>,
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
= _RequireAllocator
<_Allocator
>>
1210 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1211 typename unordered_map
<int, int>::size_type
,
1213 -> unordered_map
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
1218 * @brief A standard container composed of equivalent keys
1219 * (possibly containing multiple of each key value) that associates
1220 * values of another type with the keys.
1222 * @ingroup unordered_associative_containers
1224 * @tparam _Key Type of key objects.
1225 * @tparam _Tp Type of mapped objects.
1226 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1227 * @tparam _Pred Predicate function object type, defaults
1228 * to equal_to<_Value>.
1229 * @tparam _Alloc Allocator type, defaults to
1230 * std::allocator<std::pair<const _Key, _Tp>>.
1232 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1233 * <a href="tables.html#xx">unordered associative container</a>
1235 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1237 * Base is _Hashtable, dispatched at compile time via template
1238 * alias __ummap_hashtable.
1240 template<typename _Key
, typename _Tp
,
1241 typename _Hash
= hash
<_Key
>,
1242 typename _Pred
= equal_to
<_Key
>,
1243 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
1244 class unordered_multimap
1246 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1252 /// Public typedefs.
1253 typedef typename
_Hashtable::key_type key_type
;
1254 typedef typename
_Hashtable::value_type value_type
;
1255 typedef typename
_Hashtable::mapped_type mapped_type
;
1256 typedef typename
_Hashtable::hasher hasher
;
1257 typedef typename
_Hashtable::key_equal key_equal
;
1258 typedef typename
_Hashtable::allocator_type allocator_type
;
1262 /// Iterator-related typedefs.
1263 typedef typename
_Hashtable::pointer pointer
;
1264 typedef typename
_Hashtable::const_pointer const_pointer
;
1265 typedef typename
_Hashtable::reference reference
;
1266 typedef typename
_Hashtable::const_reference const_reference
;
1267 typedef typename
_Hashtable::iterator iterator
;
1268 typedef typename
_Hashtable::const_iterator const_iterator
;
1269 typedef typename
_Hashtable::local_iterator local_iterator
;
1270 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1271 typedef typename
_Hashtable::size_type size_type
;
1272 typedef typename
_Hashtable::difference_type difference_type
;
1275 #if __cplusplus > 201402L
1276 using node_type
= typename
_Hashtable::node_type
;
1279 //construct/destroy/copy
1281 /// Default constructor.
1282 unordered_multimap() = default;
1285 * @brief Default constructor creates no elements.
1286 * @param __n Mnimal initial number of buckets.
1287 * @param __hf A hash functor.
1288 * @param __eql A key equality functor.
1289 * @param __a An allocator object.
1292 unordered_multimap(size_type __n
,
1293 const hasher
& __hf
= hasher(),
1294 const key_equal
& __eql
= key_equal(),
1295 const allocator_type
& __a
= allocator_type())
1296 : _M_h(__n
, __hf
, __eql
, __a
)
1300 * @brief Builds an %unordered_multimap from a range.
1301 * @param __first An input iterator.
1302 * @param __last An input iterator.
1303 * @param __n Minimal initial number of buckets.
1304 * @param __hf A hash functor.
1305 * @param __eql A key equality functor.
1306 * @param __a An allocator object.
1308 * Create an %unordered_multimap consisting of copies of the elements
1309 * from [__first,__last). This is linear in N (where N is
1310 * distance(__first,__last)).
1312 template<typename _InputIterator
>
1313 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1315 const hasher
& __hf
= hasher(),
1316 const key_equal
& __eql
= key_equal(),
1317 const allocator_type
& __a
= allocator_type())
1318 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1321 /// Copy constructor.
1322 unordered_multimap(const unordered_multimap
&) = default;
1324 /// Move constructor.
1325 unordered_multimap(unordered_multimap
&&) = default;
1328 * @brief Creates an %unordered_multimap with no elements.
1329 * @param __a An allocator object.
1332 unordered_multimap(const allocator_type
& __a
)
1337 * @brief Copy constructor with allocator argument.
1338 * @param __uset Input %unordered_multimap to copy.
1339 * @param __a An allocator object.
1341 unordered_multimap(const unordered_multimap
& __ummap
,
1342 const allocator_type
& __a
)
1343 : _M_h(__ummap
._M_h
, __a
)
1347 * @brief Move constructor with allocator argument.
1348 * @param __uset Input %unordered_multimap to move.
1349 * @param __a An allocator object.
1351 unordered_multimap(unordered_multimap
&& __ummap
,
1352 const allocator_type
& __a
)
1353 : _M_h(std::move(__ummap
._M_h
), __a
)
1357 * @brief Builds an %unordered_multimap from an initializer_list.
1358 * @param __l An initializer_list.
1359 * @param __n Minimal initial number of buckets.
1360 * @param __hf A hash functor.
1361 * @param __eql A key equality functor.
1362 * @param __a An allocator object.
1364 * Create an %unordered_multimap consisting of copies of the elements in
1365 * the list. This is linear in N (where N is @a __l.size()).
1367 unordered_multimap(initializer_list
<value_type
> __l
,
1369 const hasher
& __hf
= hasher(),
1370 const key_equal
& __eql
= key_equal(),
1371 const allocator_type
& __a
= allocator_type())
1372 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1375 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1376 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1379 unordered_multimap(size_type __n
, const hasher
& __hf
,
1380 const allocator_type
& __a
)
1381 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1384 template<typename _InputIterator
>
1385 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1387 const allocator_type
& __a
)
1388 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1391 template<typename _InputIterator
>
1392 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1393 size_type __n
, const hasher
& __hf
,
1394 const allocator_type
& __a
)
1395 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1398 unordered_multimap(initializer_list
<value_type
> __l
,
1400 const allocator_type
& __a
)
1401 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1404 unordered_multimap(initializer_list
<value_type
> __l
,
1405 size_type __n
, const hasher
& __hf
,
1406 const allocator_type
& __a
)
1407 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1410 /// Copy assignment operator.
1412 operator=(const unordered_multimap
&) = default;
1414 /// Move assignment operator.
1416 operator=(unordered_multimap
&&) = default;
1419 * @brief %Unordered_multimap list assignment operator.
1420 * @param __l An initializer_list.
1422 * This function fills an %unordered_multimap with copies of the
1423 * elements in the initializer list @a __l.
1425 * Note that the assignment completely changes the %unordered_multimap
1426 * and that the resulting %unordered_multimap's size is the same as the
1427 * number of elements assigned.
1430 operator=(initializer_list
<value_type
> __l
)
1436 /// Returns the allocator object used by the %unordered_multimap.
1438 get_allocator() const noexcept
1439 { return _M_h
.get_allocator(); }
1441 // size and capacity:
1443 /// Returns true if the %unordered_multimap is empty.
1445 empty() const noexcept
1446 { return _M_h
.empty(); }
1448 /// Returns the size of the %unordered_multimap.
1450 size() const noexcept
1451 { return _M_h
.size(); }
1453 /// Returns the maximum size of the %unordered_multimap.
1455 max_size() const noexcept
1456 { return _M_h
.max_size(); }
1461 * Returns a read/write iterator that points to the first element in the
1462 * %unordered_multimap.
1466 { return _M_h
.begin(); }
1470 * Returns a read-only (constant) iterator that points to the first
1471 * element in the %unordered_multimap.
1474 begin() const noexcept
1475 { return _M_h
.begin(); }
1478 cbegin() const noexcept
1479 { return _M_h
.begin(); }
1483 * Returns a read/write iterator that points one past the last element in
1484 * the %unordered_multimap.
1488 { return _M_h
.end(); }
1492 * Returns a read-only (constant) iterator that points one past the last
1493 * element in the %unordered_multimap.
1496 end() const noexcept
1497 { return _M_h
.end(); }
1500 cend() const noexcept
1501 { return _M_h
.end(); }
1507 * @brief Attempts to build and insert a std::pair into the
1508 * %unordered_multimap.
1510 * @param __args Arguments used to generate a new pair instance (see
1511 * std::piecewise_contruct for passing arguments to each
1512 * part of the pair constructor).
1514 * @return An iterator that points to the inserted pair.
1516 * This function attempts to build and insert a (key, value) %pair into
1517 * the %unordered_multimap.
1519 * Insertion requires amortized constant time.
1521 template<typename
... _Args
>
1523 emplace(_Args
&&... __args
)
1524 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1527 * @brief Attempts to build and insert a std::pair into the
1528 * %unordered_multimap.
1530 * @param __pos An iterator that serves as a hint as to where the pair
1531 * should be inserted.
1532 * @param __args Arguments used to generate a new pair instance (see
1533 * std::piecewise_contruct for passing arguments to each
1534 * part of the pair constructor).
1535 * @return An iterator that points to the element with key of the
1536 * std::pair built from @a __args.
1538 * Note that the first parameter is only a hint and can potentially
1539 * improve the performance of the insertion process. A bad hint would
1540 * cause no gains in efficiency.
1543 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1544 * for more on @a hinting.
1546 * Insertion requires amortized constant time.
1548 template<typename
... _Args
>
1550 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1551 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1555 * @brief Inserts a std::pair into the %unordered_multimap.
1556 * @param __x Pair to be inserted (see std::make_pair for easy
1557 * creation of pairs).
1559 * @return An iterator that points to the inserted pair.
1561 * Insertion requires amortized constant time.
1564 insert(const value_type
& __x
)
1565 { return _M_h
.insert(__x
); }
1568 insert(value_type
&& __x
)
1569 { return _M_h
.insert(std::move(__x
)); }
1571 template<typename _Pair
>
1572 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1574 { return _M_h
.emplace(std::forward
<_Pair
>(__x
)); }
1579 * @brief Inserts a std::pair into the %unordered_multimap.
1580 * @param __hint An iterator that serves as a hint as to where the
1581 * pair should be inserted.
1582 * @param __x Pair to be inserted (see std::make_pair for easy creation
1584 * @return An iterator that points to the element with key of
1585 * @a __x (may or may not be the %pair passed in).
1587 * Note that the first parameter is only a hint and can potentially
1588 * improve the performance of the insertion process. A bad hint would
1589 * cause no gains in efficiency.
1592 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1593 * for more on @a hinting.
1595 * Insertion requires amortized constant time.
1598 insert(const_iterator __hint
, const value_type
& __x
)
1599 { return _M_h
.insert(__hint
, __x
); }
1601 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1602 // 2354. Unnecessary copying when inserting into maps with braced-init
1604 insert(const_iterator __hint
, value_type
&& __x
)
1605 { return _M_h
.insert(__hint
, std::move(__x
)); }
1607 template<typename _Pair
>
1608 __enable_if_t
<is_constructible
<value_type
, _Pair
&&>::value
, iterator
>
1609 insert(const_iterator __hint
, _Pair
&& __x
)
1610 { return _M_h
.emplace_hint(__hint
, std::forward
<_Pair
>(__x
)); }
1614 * @brief A template function that attempts to insert a range of
1616 * @param __first Iterator pointing to the start of the range to be
1618 * @param __last Iterator pointing to the end of the range.
1620 * Complexity similar to that of the range constructor.
1622 template<typename _InputIterator
>
1624 insert(_InputIterator __first
, _InputIterator __last
)
1625 { _M_h
.insert(__first
, __last
); }
1628 * @brief Attempts to insert a list of elements into the
1629 * %unordered_multimap.
1630 * @param __l A std::initializer_list<value_type> of elements
1633 * Complexity similar to that of the range constructor.
1636 insert(initializer_list
<value_type
> __l
)
1637 { _M_h
.insert(__l
); }
1639 #if __cplusplus > 201402L
1642 extract(const_iterator __pos
)
1644 __glibcxx_assert(__pos
!= end());
1645 return _M_h
.extract(__pos
);
1650 extract(const key_type
& __key
)
1651 { return _M_h
.extract(__key
); }
1653 /// Re-insert an extracted node.
1655 insert(node_type
&& __nh
)
1656 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1658 /// Re-insert an extracted node.
1660 insert(const_iterator __hint
, node_type
&& __nh
)
1661 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1666 * @brief Erases an element from an %unordered_multimap.
1667 * @param __position An iterator pointing to the element to be erased.
1668 * @return An iterator pointing to the element immediately following
1669 * @a __position prior to the element being erased. If no such
1670 * element exists, end() is returned.
1672 * This function erases an element, pointed to by the given iterator,
1673 * from an %unordered_multimap.
1674 * Note that this function only erases the element, and that if the
1675 * element is itself a pointer, the pointed-to memory is not touched in
1676 * any way. Managing the pointer is the user's responsibility.
1679 erase(const_iterator __position
)
1680 { return _M_h
.erase(__position
); }
1684 erase(iterator __position
)
1685 { return _M_h
.erase(__position
); }
1689 * @brief Erases elements according to the provided key.
1690 * @param __x Key of elements to be erased.
1691 * @return The number of elements erased.
1693 * This function erases all the elements located by the given key from
1694 * an %unordered_multimap.
1695 * Note that this function only erases the element, and that if the
1696 * element is itself a pointer, the pointed-to memory is not touched in
1697 * any way. Managing the pointer is the user's responsibility.
1700 erase(const key_type
& __x
)
1701 { return _M_h
.erase(__x
); }
1704 * @brief Erases a [__first,__last) range of elements from an
1705 * %unordered_multimap.
1706 * @param __first Iterator pointing to the start of the range to be
1708 * @param __last Iterator pointing to the end of the range to
1710 * @return The iterator @a __last.
1712 * This function erases a sequence of elements from an
1713 * %unordered_multimap.
1714 * Note that this function only erases the elements, and that if
1715 * the element is itself a pointer, the pointed-to memory is not touched
1716 * in any way. Managing the pointer is the user's responsibility.
1719 erase(const_iterator __first
, const_iterator __last
)
1720 { return _M_h
.erase(__first
, __last
); }
1723 * Erases all elements in an %unordered_multimap.
1724 * Note that this function only erases the elements, and that if the
1725 * elements themselves are pointers, the pointed-to memory is not touched
1726 * in any way. Managing the pointer is the user's responsibility.
1733 * @brief Swaps data with another %unordered_multimap.
1734 * @param __x An %unordered_multimap of the same element and allocator
1737 * This exchanges the elements between two %unordered_multimap in
1739 * Note that the global std::swap() function is specialized such that
1740 * std::swap(m1,m2) will feed to this function.
1743 swap(unordered_multimap
& __x
)
1744 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1745 { _M_h
.swap(__x
._M_h
); }
1747 #if __cplusplus > 201402L
1748 template<typename
, typename
, typename
>
1749 friend class std::_Hash_merge_helper
;
1751 template<typename _H2
, typename _P2
>
1753 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1756 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1757 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1760 template<typename _H2
, typename _P2
>
1762 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1763 { merge(__source
); }
1765 template<typename _H2
, typename _P2
>
1767 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1770 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1771 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1774 template<typename _H2
, typename _P2
>
1776 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1777 { merge(__source
); }
1782 /// Returns the hash functor object with which the %unordered_multimap
1783 /// was constructed.
1785 hash_function() const
1786 { return _M_h
.hash_function(); }
1788 /// Returns the key comparison object with which the %unordered_multimap
1789 /// was constructed.
1792 { return _M_h
.key_eq(); }
1798 * @brief Tries to locate an element in an %unordered_multimap.
1799 * @param __x Key to be located.
1800 * @return Iterator pointing to sought-after element, or end() if not
1803 * This function takes a key and tries to locate the element with which
1804 * the key matches. If successful the function returns an iterator
1805 * pointing to the sought after element. If unsuccessful it returns the
1806 * past-the-end ( @c end() ) iterator.
1809 find(const key_type
& __x
)
1810 { return _M_h
.find(__x
); }
1813 find(const key_type
& __x
) const
1814 { return _M_h
.find(__x
); }
1818 * @brief Finds the number of elements.
1819 * @param __x Key to count.
1820 * @return Number of elements with specified key.
1823 count(const key_type
& __x
) const
1824 { return _M_h
.count(__x
); }
1826 #if __cplusplus > 201703L
1828 * @brief Finds whether an element with the given key exists.
1829 * @param __x Key of elements to be located.
1830 * @return True if there is any element with the specified key.
1833 contains(const key_type
& __x
) const
1834 { return _M_h
.find(__x
) != _M_h
.end(); }
1839 * @brief Finds a subsequence matching given key.
1840 * @param __x Key to be located.
1841 * @return Pair of iterators that possibly points to the subsequence
1842 * matching given key.
1844 std::pair
<iterator
, iterator
>
1845 equal_range(const key_type
& __x
)
1846 { return _M_h
.equal_range(__x
); }
1848 std::pair
<const_iterator
, const_iterator
>
1849 equal_range(const key_type
& __x
) const
1850 { return _M_h
.equal_range(__x
); }
1853 // bucket interface.
1855 /// Returns the number of buckets of the %unordered_multimap.
1857 bucket_count() const noexcept
1858 { return _M_h
.bucket_count(); }
1860 /// Returns the maximum number of buckets of the %unordered_multimap.
1862 max_bucket_count() const noexcept
1863 { return _M_h
.max_bucket_count(); }
1866 * @brief Returns the number of elements in a given bucket.
1867 * @param __n A bucket index.
1868 * @return The number of elements in the bucket.
1871 bucket_size(size_type __n
) const
1872 { return _M_h
.bucket_size(__n
); }
1875 * @brief Returns the bucket index of a given element.
1876 * @param __key A key instance.
1877 * @return The key bucket index.
1880 bucket(const key_type
& __key
) const
1881 { return _M_h
.bucket(__key
); }
1884 * @brief Returns a read/write iterator pointing to the first bucket
1886 * @param __n The bucket index.
1887 * @return A read/write local iterator.
1890 begin(size_type __n
)
1891 { return _M_h
.begin(__n
); }
1895 * @brief Returns a read-only (constant) iterator pointing to the first
1897 * @param __n The bucket index.
1898 * @return A read-only local iterator.
1900 const_local_iterator
1901 begin(size_type __n
) const
1902 { return _M_h
.begin(__n
); }
1904 const_local_iterator
1905 cbegin(size_type __n
) const
1906 { return _M_h
.cbegin(__n
); }
1910 * @brief Returns a read/write iterator pointing to one past the last
1912 * @param __n The bucket index.
1913 * @return A read/write local iterator.
1917 { return _M_h
.end(__n
); }
1921 * @brief Returns a read-only (constant) iterator pointing to one past
1922 * the last bucket elements.
1923 * @param __n The bucket index.
1924 * @return A read-only local iterator.
1926 const_local_iterator
1927 end(size_type __n
) const
1928 { return _M_h
.end(__n
); }
1930 const_local_iterator
1931 cend(size_type __n
) const
1932 { return _M_h
.cend(__n
); }
1937 /// Returns the average number of elements per bucket.
1939 load_factor() const noexcept
1940 { return _M_h
.load_factor(); }
1942 /// Returns a positive number that the %unordered_multimap tries to keep
1943 /// the load factor less than or equal to.
1945 max_load_factor() const noexcept
1946 { return _M_h
.max_load_factor(); }
1949 * @brief Change the %unordered_multimap maximum load factor.
1950 * @param __z The new maximum load factor.
1953 max_load_factor(float __z
)
1954 { _M_h
.max_load_factor(__z
); }
1957 * @brief May rehash the %unordered_multimap.
1958 * @param __n The new number of buckets.
1960 * Rehash will occur only if the new number of buckets respect the
1961 * %unordered_multimap maximum load factor.
1964 rehash(size_type __n
)
1965 { _M_h
.rehash(__n
); }
1968 * @brief Prepare the %unordered_multimap for a specified number of
1970 * @param __n Number of elements required.
1972 * Same as rehash(ceil(n / max_load_factor())).
1975 reserve(size_type __n
)
1976 { _M_h
.reserve(__n
); }
1978 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1981 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1982 _Hash1
, _Pred1
, _Alloc1
>&,
1983 const unordered_multimap
<_Key1
, _Tp1
,
1984 _Hash1
, _Pred1
, _Alloc1
>&);
1987 #if __cpp_deduction_guides >= 201606
1989 template<typename _InputIterator
,
1990 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1991 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1992 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1993 typename
= _RequireInputIter
<_InputIterator
>,
1994 typename
= _RequireAllocator
<_Allocator
>>
1995 unordered_multimap(_InputIterator
, _InputIterator
,
1996 unordered_multimap
<int, int>::size_type
= {},
1997 _Hash
= _Hash(), _Pred
= _Pred(),
1998 _Allocator
= _Allocator())
1999 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2000 __iter_val_t
<_InputIterator
>, _Hash
, _Pred
,
2003 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
2004 typename _Pred
= equal_to
<_Key
>,
2005 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
2006 typename
= _RequireAllocator
<_Allocator
>>
2007 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2008 unordered_multimap
<int, int>::size_type
= {},
2009 _Hash
= _Hash(), _Pred
= _Pred(),
2010 _Allocator
= _Allocator())
2011 -> unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
2013 template<typename _InputIterator
, typename _Allocator
,
2014 typename
= _RequireInputIter
<_InputIterator
>,
2015 typename
= _RequireAllocator
<_Allocator
>>
2016 unordered_multimap(_InputIterator
, _InputIterator
,
2017 unordered_multimap
<int, int>::size_type
, _Allocator
)
2018 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2019 __iter_val_t
<_InputIterator
>,
2020 hash
<__iter_key_t
<_InputIterator
>>,
2021 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2023 template<typename _InputIterator
, typename _Allocator
,
2024 typename
= _RequireInputIter
<_InputIterator
>,
2025 typename
= _RequireAllocator
<_Allocator
>>
2026 unordered_multimap(_InputIterator
, _InputIterator
, _Allocator
)
2027 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2028 __iter_val_t
<_InputIterator
>,
2029 hash
<__iter_key_t
<_InputIterator
>>,
2030 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2032 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
2033 typename
= _RequireInputIter
<_InputIterator
>,
2034 typename
= _RequireAllocator
<_Allocator
>>
2035 unordered_multimap(_InputIterator
, _InputIterator
,
2036 unordered_multimap
<int, int>::size_type
, _Hash
,
2038 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2039 __iter_val_t
<_InputIterator
>, _Hash
,
2040 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2042 template<typename _Key
, typename _Tp
, typename _Allocator
,
2043 typename
= _RequireAllocator
<_Allocator
>>
2044 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2045 unordered_multimap
<int, int>::size_type
,
2047 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2049 template<typename _Key
, typename _Tp
, typename _Allocator
,
2050 typename
= _RequireAllocator
<_Allocator
>>
2051 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
2052 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2054 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
2055 typename
= _RequireAllocator
<_Allocator
>>
2056 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2057 unordered_multimap
<int, int>::size_type
,
2059 -> unordered_multimap
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
2063 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2065 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2066 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2067 noexcept(noexcept(__x
.swap(__y
)))
2070 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2072 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2073 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2074 noexcept(noexcept(__x
.swap(__y
)))
2077 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2079 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2080 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2081 { return __x
._M_h
._M_equal(__y
._M_h
); }
2083 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2085 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2086 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2087 { return !(__x
== __y
); }
2089 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2091 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2092 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2093 { return __x
._M_h
._M_equal(__y
._M_h
); }
2095 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2097 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2098 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2099 { return !(__x
== __y
); }
2101 _GLIBCXX_END_NAMESPACE_CONTAINER
2103 #if __cplusplus > 201402L
2104 // Allow std::unordered_map access to internals of compatible maps.
2105 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2106 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2107 struct _Hash_merge_helper
<
2108 _GLIBCXX_STD_C::unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2112 template<typename
... _Tp
>
2113 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2114 template<typename
... _Tp
>
2115 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2117 friend unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2120 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2121 { return __map
._M_h
; }
2124 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2125 { return __map
._M_h
; }
2128 // Allow std::unordered_multimap access to internals of compatible maps.
2129 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2130 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2131 struct _Hash_merge_helper
<
2132 _GLIBCXX_STD_C::unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2136 template<typename
... _Tp
>
2137 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2138 template<typename
... _Tp
>
2139 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2141 friend unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2144 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2145 { return __map
._M_h
; }
2148 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2149 { return __map
._M_h
; }
2153 _GLIBCXX_END_NAMESPACE_VERSION
2156 #endif /* _UNORDERED_MAP_H */