1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2018 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
, typename
= typename
589 std::enable_if
<std::is_constructible
<value_type
,
590 _Pair
&&>::value
>::type
>
591 std::pair
<iterator
, bool>
593 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
598 * @brief Attempts to insert a std::pair into the %unordered_map.
599 * @param __hint An iterator that serves as a hint as to where the
600 * pair should be inserted.
601 * @param __x Pair to be inserted (see std::make_pair for easy creation
603 * @return An iterator that points to the element with key of
604 * @a __x (may or may not be the %pair passed in).
606 * This function is not concerned about whether the insertion took place,
607 * and thus does not return a boolean like the single-argument insert()
608 * does. Note that the first parameter is only a hint and can
609 * potentially improve the performance of the insertion process. A bad
610 * hint would cause no gains in efficiency.
613 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
614 * for more on @a hinting.
616 * Insertion requires amortized constant time.
619 insert(const_iterator __hint
, const value_type
& __x
)
620 { return _M_h
.insert(__hint
, __x
); }
622 // _GLIBCXX_RESOLVE_LIB_DEFECTS
623 // 2354. Unnecessary copying when inserting into maps with braced-init
625 insert(const_iterator __hint
, value_type
&& __x
)
626 { return _M_h
.insert(__hint
, std::move(__x
)); }
628 template<typename _Pair
, typename
= typename
629 std::enable_if
<std::is_constructible
<value_type
,
630 _Pair
&&>::value
>::type
>
632 insert(const_iterator __hint
, _Pair
&& __x
)
633 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
637 * @brief A template function that attempts to insert a range of
639 * @param __first Iterator pointing to the start of the range to be
641 * @param __last Iterator pointing to the end of the range.
643 * Complexity similar to that of the range constructor.
645 template<typename _InputIterator
>
647 insert(_InputIterator __first
, _InputIterator __last
)
648 { _M_h
.insert(__first
, __last
); }
651 * @brief Attempts to insert a list of elements into the %unordered_map.
652 * @param __l A std::initializer_list<value_type> of elements
655 * Complexity similar to that of the range constructor.
658 insert(initializer_list
<value_type
> __l
)
659 { _M_h
.insert(__l
); }
662 #if __cplusplus > 201402L
663 #define __cpp_lib_unordered_map_insertion 201411
665 * @brief Attempts to insert a std::pair into the %unordered_map.
666 * @param __k Key to use for finding a possibly existing pair in
668 * @param __obj Argument used to generate the .second for a pair
671 * @return A pair, of which the first element is an iterator that
672 * points to the possibly inserted pair, and the second is
673 * a bool that is true if the pair was actually inserted.
675 * This function attempts to insert a (key, value) %pair into the
676 * %unordered_map. An %unordered_map relies on unique keys and thus a
677 * %pair is only inserted if its first element (the key) is not already
678 * present in the %unordered_map.
679 * If the %pair was already in the %unordered_map, the .second of
680 * the %pair is assigned from __obj.
682 * Insertion requires amortized constant time.
684 template <typename _Obj
>
686 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
688 iterator __i
= find(__k
);
691 __i
= emplace(std::piecewise_construct
,
692 std::forward_as_tuple(__k
),
693 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
697 (*__i
).second
= std::forward
<_Obj
>(__obj
);
701 // move-capable overload
702 template <typename _Obj
>
704 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
706 iterator __i
= find(__k
);
709 __i
= emplace(std::piecewise_construct
,
710 std::forward_as_tuple(std::move(__k
)),
711 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
715 (*__i
).second
= std::forward
<_Obj
>(__obj
);
720 * @brief Attempts to insert a std::pair into the %unordered_map.
721 * @param __hint An iterator that serves as a hint as to where the
722 * pair should be inserted.
723 * @param __k Key to use for finding a possibly existing pair in
725 * @param __obj Argument used to generate the .second for a pair
727 * @return An iterator that points to the element with key of
728 * @a __x (may or may not be the %pair passed in).
730 * This function is not concerned about whether the insertion took place,
731 * and thus does not return a boolean like the single-argument insert()
733 * If the %pair was already in the %unordered map, the .second of
734 * the %pair is assigned from __obj.
735 * Note that the first parameter is only a hint and can
736 * potentially improve the performance of the insertion process. A bad
737 * hint would cause no gains in efficiency.
740 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
741 * for more on @a hinting.
743 * Insertion requires amortized constant time.
745 template <typename _Obj
>
747 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
750 iterator __i
= find(__k
);
753 return emplace_hint(__hint
, std::piecewise_construct
,
754 std::forward_as_tuple(__k
),
755 std::forward_as_tuple(
756 std::forward
<_Obj
>(__obj
)));
758 (*__i
).second
= std::forward
<_Obj
>(__obj
);
762 // move-capable overload
763 template <typename _Obj
>
765 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
767 iterator __i
= find(__k
);
770 return emplace_hint(__hint
, std::piecewise_construct
,
771 std::forward_as_tuple(std::move(__k
)),
772 std::forward_as_tuple(
773 std::forward
<_Obj
>(__obj
)));
775 (*__i
).second
= std::forward
<_Obj
>(__obj
);
782 * @brief Erases an element from an %unordered_map.
783 * @param __position An iterator pointing to the element to be erased.
784 * @return An iterator pointing to the element immediately following
785 * @a __position prior to the element being erased. If no such
786 * element exists, end() is returned.
788 * This function erases an element, pointed to by the given iterator,
789 * from an %unordered_map.
790 * Note that this function only erases the element, and that if the
791 * element is itself a pointer, the pointed-to memory is not touched in
792 * any way. Managing the pointer is the user's responsibility.
795 erase(const_iterator __position
)
796 { return _M_h
.erase(__position
); }
800 erase(iterator __position
)
801 { return _M_h
.erase(__position
); }
805 * @brief Erases elements according to the provided key.
806 * @param __x Key of element to be erased.
807 * @return The number of elements erased.
809 * This function erases all the elements located by the given key from
810 * an %unordered_map. For an %unordered_map the result of this function
811 * can only be 0 (not present) or 1 (present).
812 * Note that this function only erases the element, and that if the
813 * element is itself a pointer, the pointed-to memory is not touched in
814 * any way. Managing the pointer is the user's responsibility.
817 erase(const key_type
& __x
)
818 { return _M_h
.erase(__x
); }
821 * @brief Erases a [__first,__last) range of elements from an
823 * @param __first Iterator pointing to the start of the range to be
825 * @param __last Iterator pointing to the end of the range to
827 * @return The iterator @a __last.
829 * This function erases a sequence of elements from an %unordered_map.
830 * Note that this function only erases the elements, and that if
831 * the element is itself a pointer, the pointed-to memory is not touched
832 * in any way. Managing the pointer is the user's responsibility.
835 erase(const_iterator __first
, const_iterator __last
)
836 { return _M_h
.erase(__first
, __last
); }
839 * Erases all elements in an %unordered_map.
840 * Note that this function only erases the elements, and that if the
841 * elements themselves are pointers, the pointed-to memory is not touched
842 * in any way. Managing the pointer is the user's responsibility.
849 * @brief Swaps data with another %unordered_map.
850 * @param __x An %unordered_map of the same element and allocator
853 * This exchanges the elements between two %unordered_map in constant
855 * Note that the global std::swap() function is specialized such that
856 * std::swap(m1,m2) will feed to this function.
859 swap(unordered_map
& __x
)
860 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
861 { _M_h
.swap(__x
._M_h
); }
863 #if __cplusplus > 201402L
864 template<typename
, typename
, typename
>
865 friend class _Hash_merge_helper
;
867 template<typename _H2
, typename _P2
>
869 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
871 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
872 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
875 template<typename _H2
, typename _P2
>
877 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
880 template<typename _H2
, typename _P2
>
882 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
884 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
885 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
888 template<typename _H2
, typename _P2
>
890 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
896 /// Returns the hash functor object with which the %unordered_map was
899 hash_function() const
900 { return _M_h
.hash_function(); }
902 /// Returns the key comparison object with which the %unordered_map was
906 { return _M_h
.key_eq(); }
912 * @brief Tries to locate an element in an %unordered_map.
913 * @param __x Key to be located.
914 * @return Iterator pointing to sought-after element, or end() if not
917 * This function takes a key and tries to locate the element with which
918 * the key matches. If successful the function returns an iterator
919 * pointing to the sought after element. If unsuccessful it returns the
920 * past-the-end ( @c end() ) iterator.
923 find(const key_type
& __x
)
924 { return _M_h
.find(__x
); }
927 find(const key_type
& __x
) const
928 { return _M_h
.find(__x
); }
932 * @brief Finds the number of elements.
933 * @param __x Key to count.
934 * @return Number of elements with specified key.
936 * This function only makes sense for %unordered_multimap; for
937 * %unordered_map the result will either be 0 (not present) or 1
941 count(const key_type
& __x
) const
942 { return _M_h
.count(__x
); }
946 * @brief Finds a subsequence matching given key.
947 * @param __x Key to be located.
948 * @return Pair of iterators that possibly points to the subsequence
949 * matching given key.
951 * This function probably only makes sense for %unordered_multimap.
953 std::pair
<iterator
, iterator
>
954 equal_range(const key_type
& __x
)
955 { return _M_h
.equal_range(__x
); }
957 std::pair
<const_iterator
, const_iterator
>
958 equal_range(const key_type
& __x
) const
959 { return _M_h
.equal_range(__x
); }
964 * @brief Subscript ( @c [] ) access to %unordered_map data.
965 * @param __k The key for which data should be retrieved.
966 * @return A reference to the data of the (key,data) %pair.
968 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
969 * data associated with the key specified in subscript. If the key does
970 * not exist, a pair with that key is created using default values, which
973 * Lookup requires constant time.
976 operator[](const key_type
& __k
)
977 { return _M_h
[__k
]; }
980 operator[](key_type
&& __k
)
981 { return _M_h
[std::move(__k
)]; }
986 * @brief Access to %unordered_map data.
987 * @param __k The key for which data should be retrieved.
988 * @return A reference to the data whose key is equal to @a __k, if
989 * such a data is present in the %unordered_map.
990 * @throw std::out_of_range If no such data is present.
993 at(const key_type
& __k
)
994 { return _M_h
.at(__k
); }
997 at(const key_type
& __k
) const
998 { return _M_h
.at(__k
); }
1001 // bucket interface.
1003 /// Returns the number of buckets of the %unordered_map.
1005 bucket_count() const noexcept
1006 { return _M_h
.bucket_count(); }
1008 /// Returns the maximum number of buckets of the %unordered_map.
1010 max_bucket_count() const noexcept
1011 { return _M_h
.max_bucket_count(); }
1014 * @brief Returns the number of elements in a given bucket.
1015 * @param __n A bucket index.
1016 * @return The number of elements in the bucket.
1019 bucket_size(size_type __n
) const
1020 { return _M_h
.bucket_size(__n
); }
1023 * @brief Returns the bucket index of a given element.
1024 * @param __key A key instance.
1025 * @return The key bucket index.
1028 bucket(const key_type
& __key
) const
1029 { return _M_h
.bucket(__key
); }
1032 * @brief Returns a read/write iterator pointing to the first bucket
1034 * @param __n The bucket index.
1035 * @return A read/write local iterator.
1038 begin(size_type __n
)
1039 { return _M_h
.begin(__n
); }
1043 * @brief Returns a read-only (constant) iterator pointing to the first
1045 * @param __n The bucket index.
1046 * @return A read-only local iterator.
1048 const_local_iterator
1049 begin(size_type __n
) const
1050 { return _M_h
.begin(__n
); }
1052 const_local_iterator
1053 cbegin(size_type __n
) const
1054 { return _M_h
.cbegin(__n
); }
1058 * @brief Returns a read/write iterator pointing to one past the last
1060 * @param __n The bucket index.
1061 * @return A read/write local iterator.
1065 { return _M_h
.end(__n
); }
1069 * @brief Returns a read-only (constant) iterator pointing to one past
1070 * the last bucket elements.
1071 * @param __n The bucket index.
1072 * @return A read-only local iterator.
1074 const_local_iterator
1075 end(size_type __n
) const
1076 { return _M_h
.end(__n
); }
1078 const_local_iterator
1079 cend(size_type __n
) const
1080 { return _M_h
.cend(__n
); }
1085 /// Returns the average number of elements per bucket.
1087 load_factor() const noexcept
1088 { return _M_h
.load_factor(); }
1090 /// Returns a positive number that the %unordered_map tries to keep the
1091 /// load factor less than or equal to.
1093 max_load_factor() const noexcept
1094 { return _M_h
.max_load_factor(); }
1097 * @brief Change the %unordered_map maximum load factor.
1098 * @param __z The new maximum load factor.
1101 max_load_factor(float __z
)
1102 { _M_h
.max_load_factor(__z
); }
1105 * @brief May rehash the %unordered_map.
1106 * @param __n The new number of buckets.
1108 * Rehash will occur only if the new number of buckets respect the
1109 * %unordered_map maximum load factor.
1112 rehash(size_type __n
)
1113 { _M_h
.rehash(__n
); }
1116 * @brief Prepare the %unordered_map for a specified number of
1118 * @param __n Number of elements required.
1120 * Same as rehash(ceil(n / max_load_factor())).
1123 reserve(size_type __n
)
1124 { _M_h
.reserve(__n
); }
1126 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1129 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1130 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1133 #if __cpp_deduction_guides >= 201606
1135 template<typename _InputIterator
,
1136 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1137 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1138 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1139 typename
= _RequireInputIter
<_InputIterator
>,
1140 typename
= _RequireAllocator
<_Allocator
>>
1141 unordered_map(_InputIterator
, _InputIterator
,
1142 typename unordered_map
<int, int>::size_type
= {},
1143 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1144 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1145 __iter_val_t
<_InputIterator
>,
1146 _Hash
, _Pred
, _Allocator
>;
1148 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
1149 typename _Pred
= equal_to
<_Key
>,
1150 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
1151 typename
= _RequireAllocator
<_Allocator
>>
1152 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1153 typename unordered_map
<int, int>::size_type
= {},
1154 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
1155 -> unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
1157 template<typename _InputIterator
, typename _Allocator
,
1158 typename
= _RequireInputIter
<_InputIterator
>,
1159 typename
= _RequireAllocator
<_Allocator
>>
1160 unordered_map(_InputIterator
, _InputIterator
,
1161 typename unordered_map
<int, int>::size_type
, _Allocator
)
1162 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1163 __iter_val_t
<_InputIterator
>,
1164 hash
<__iter_key_t
<_InputIterator
>>,
1165 equal_to
<__iter_key_t
<_InputIterator
>>,
1168 template<typename _InputIterator
, typename _Allocator
,
1169 typename
= _RequireInputIter
<_InputIterator
>,
1170 typename
= _RequireAllocator
<_Allocator
>>
1171 unordered_map(_InputIterator
, _InputIterator
, _Allocator
)
1172 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1173 __iter_val_t
<_InputIterator
>,
1174 hash
<__iter_key_t
<_InputIterator
>>,
1175 equal_to
<__iter_key_t
<_InputIterator
>>,
1178 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
1179 typename
= _RequireInputIter
<_InputIterator
>,
1180 typename
= _RequireAllocator
<_Allocator
>>
1181 unordered_map(_InputIterator
, _InputIterator
,
1182 typename unordered_map
<int, int>::size_type
,
1184 -> unordered_map
<__iter_key_t
<_InputIterator
>,
1185 __iter_val_t
<_InputIterator
>, _Hash
,
1186 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
1188 template<typename _Key
, typename _Tp
, typename _Allocator
,
1189 typename
= _RequireAllocator
<_Allocator
>>
1190 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1191 typename unordered_map
<int, int>::size_type
,
1193 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1195 template<typename _Key
, typename _Tp
, typename _Allocator
,
1196 typename
= _RequireAllocator
<_Allocator
>>
1197 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
1198 -> unordered_map
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
1200 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
1201 typename
= _RequireAllocator
<_Allocator
>>
1202 unordered_map(initializer_list
<pair
<_Key
, _Tp
>>,
1203 typename unordered_map
<int, int>::size_type
,
1205 -> unordered_map
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
1210 * @brief A standard container composed of equivalent keys
1211 * (possibly containing multiple of each key value) that associates
1212 * values of another type with the keys.
1214 * @ingroup unordered_associative_containers
1216 * @tparam _Key Type of key objects.
1217 * @tparam _Tp Type of mapped objects.
1218 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1219 * @tparam _Pred Predicate function object type, defaults
1220 * to equal_to<_Value>.
1221 * @tparam _Alloc Allocator type, defaults to
1222 * std::allocator<std::pair<const _Key, _Tp>>.
1224 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1225 * <a href="tables.html#xx">unordered associative container</a>
1227 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1229 * Base is _Hashtable, dispatched at compile time via template
1230 * alias __ummap_hashtable.
1232 template<typename _Key
, typename _Tp
,
1233 typename _Hash
= hash
<_Key
>,
1234 typename _Pred
= equal_to
<_Key
>,
1235 typename _Alloc
= allocator
<std::pair
<const _Key
, _Tp
>>>
1236 class unordered_multimap
1238 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1244 /// Public typedefs.
1245 typedef typename
_Hashtable::key_type key_type
;
1246 typedef typename
_Hashtable::value_type value_type
;
1247 typedef typename
_Hashtable::mapped_type mapped_type
;
1248 typedef typename
_Hashtable::hasher hasher
;
1249 typedef typename
_Hashtable::key_equal key_equal
;
1250 typedef typename
_Hashtable::allocator_type allocator_type
;
1254 /// Iterator-related typedefs.
1255 typedef typename
_Hashtable::pointer pointer
;
1256 typedef typename
_Hashtable::const_pointer const_pointer
;
1257 typedef typename
_Hashtable::reference reference
;
1258 typedef typename
_Hashtable::const_reference const_reference
;
1259 typedef typename
_Hashtable::iterator iterator
;
1260 typedef typename
_Hashtable::const_iterator const_iterator
;
1261 typedef typename
_Hashtable::local_iterator local_iterator
;
1262 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1263 typedef typename
_Hashtable::size_type size_type
;
1264 typedef typename
_Hashtable::difference_type difference_type
;
1267 #if __cplusplus > 201402L
1268 using node_type
= typename
_Hashtable::node_type
;
1271 //construct/destroy/copy
1273 /// Default constructor.
1274 unordered_multimap() = default;
1277 * @brief Default constructor creates no elements.
1278 * @param __n Mnimal initial number of buckets.
1279 * @param __hf A hash functor.
1280 * @param __eql A key equality functor.
1281 * @param __a An allocator object.
1284 unordered_multimap(size_type __n
,
1285 const hasher
& __hf
= hasher(),
1286 const key_equal
& __eql
= key_equal(),
1287 const allocator_type
& __a
= allocator_type())
1288 : _M_h(__n
, __hf
, __eql
, __a
)
1292 * @brief Builds an %unordered_multimap from a range.
1293 * @param __first An input iterator.
1294 * @param __last An input iterator.
1295 * @param __n Minimal initial number of buckets.
1296 * @param __hf A hash functor.
1297 * @param __eql A key equality functor.
1298 * @param __a An allocator object.
1300 * Create an %unordered_multimap consisting of copies of the elements
1301 * from [__first,__last). This is linear in N (where N is
1302 * distance(__first,__last)).
1304 template<typename _InputIterator
>
1305 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1307 const hasher
& __hf
= hasher(),
1308 const key_equal
& __eql
= key_equal(),
1309 const allocator_type
& __a
= allocator_type())
1310 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1313 /// Copy constructor.
1314 unordered_multimap(const unordered_multimap
&) = default;
1316 /// Move constructor.
1317 unordered_multimap(unordered_multimap
&&) = default;
1320 * @brief Creates an %unordered_multimap with no elements.
1321 * @param __a An allocator object.
1324 unordered_multimap(const allocator_type
& __a
)
1329 * @brief Copy constructor with allocator argument.
1330 * @param __uset Input %unordered_multimap to copy.
1331 * @param __a An allocator object.
1333 unordered_multimap(const unordered_multimap
& __ummap
,
1334 const allocator_type
& __a
)
1335 : _M_h(__ummap
._M_h
, __a
)
1339 * @brief Move constructor with allocator argument.
1340 * @param __uset Input %unordered_multimap to move.
1341 * @param __a An allocator object.
1343 unordered_multimap(unordered_multimap
&& __ummap
,
1344 const allocator_type
& __a
)
1345 : _M_h(std::move(__ummap
._M_h
), __a
)
1349 * @brief Builds an %unordered_multimap from an initializer_list.
1350 * @param __l An initializer_list.
1351 * @param __n Minimal initial number of buckets.
1352 * @param __hf A hash functor.
1353 * @param __eql A key equality functor.
1354 * @param __a An allocator object.
1356 * Create an %unordered_multimap consisting of copies of the elements in
1357 * the list. This is linear in N (where N is @a __l.size()).
1359 unordered_multimap(initializer_list
<value_type
> __l
,
1361 const hasher
& __hf
= hasher(),
1362 const key_equal
& __eql
= key_equal(),
1363 const allocator_type
& __a
= allocator_type())
1364 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1367 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1368 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1371 unordered_multimap(size_type __n
, const hasher
& __hf
,
1372 const allocator_type
& __a
)
1373 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1376 template<typename _InputIterator
>
1377 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1379 const allocator_type
& __a
)
1380 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1383 template<typename _InputIterator
>
1384 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1385 size_type __n
, const hasher
& __hf
,
1386 const allocator_type
& __a
)
1387 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1390 unordered_multimap(initializer_list
<value_type
> __l
,
1392 const allocator_type
& __a
)
1393 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1396 unordered_multimap(initializer_list
<value_type
> __l
,
1397 size_type __n
, const hasher
& __hf
,
1398 const allocator_type
& __a
)
1399 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1402 /// Copy assignment operator.
1404 operator=(const unordered_multimap
&) = default;
1406 /// Move assignment operator.
1408 operator=(unordered_multimap
&&) = default;
1411 * @brief %Unordered_multimap list assignment operator.
1412 * @param __l An initializer_list.
1414 * This function fills an %unordered_multimap with copies of the
1415 * elements in the initializer list @a __l.
1417 * Note that the assignment completely changes the %unordered_multimap
1418 * and that the resulting %unordered_multimap's size is the same as the
1419 * number of elements assigned.
1422 operator=(initializer_list
<value_type
> __l
)
1428 /// Returns the allocator object used by the %unordered_multimap.
1430 get_allocator() const noexcept
1431 { return _M_h
.get_allocator(); }
1433 // size and capacity:
1435 /// Returns true if the %unordered_multimap is empty.
1437 empty() const noexcept
1438 { return _M_h
.empty(); }
1440 /// Returns the size of the %unordered_multimap.
1442 size() const noexcept
1443 { return _M_h
.size(); }
1445 /// Returns the maximum size of the %unordered_multimap.
1447 max_size() const noexcept
1448 { return _M_h
.max_size(); }
1453 * Returns a read/write iterator that points to the first element in the
1454 * %unordered_multimap.
1458 { return _M_h
.begin(); }
1462 * Returns a read-only (constant) iterator that points to the first
1463 * element in the %unordered_multimap.
1466 begin() const noexcept
1467 { return _M_h
.begin(); }
1470 cbegin() const noexcept
1471 { return _M_h
.begin(); }
1475 * Returns a read/write iterator that points one past the last element in
1476 * the %unordered_multimap.
1480 { return _M_h
.end(); }
1484 * Returns a read-only (constant) iterator that points one past the last
1485 * element in the %unordered_multimap.
1488 end() const noexcept
1489 { return _M_h
.end(); }
1492 cend() const noexcept
1493 { return _M_h
.end(); }
1499 * @brief Attempts to build and insert a std::pair into the
1500 * %unordered_multimap.
1502 * @param __args Arguments used to generate a new pair instance (see
1503 * std::piecewise_contruct for passing arguments to each
1504 * part of the pair constructor).
1506 * @return An iterator that points to the inserted pair.
1508 * This function attempts to build and insert a (key, value) %pair into
1509 * the %unordered_multimap.
1511 * Insertion requires amortized constant time.
1513 template<typename
... _Args
>
1515 emplace(_Args
&&... __args
)
1516 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1519 * @brief Attempts to build and insert a std::pair into the
1520 * %unordered_multimap.
1522 * @param __pos An iterator that serves as a hint as to where the pair
1523 * should be inserted.
1524 * @param __args Arguments used to generate a new pair instance (see
1525 * std::piecewise_contruct for passing arguments to each
1526 * part of the pair constructor).
1527 * @return An iterator that points to the element with key of the
1528 * std::pair built from @a __args.
1530 * Note that the first parameter is only a hint and can potentially
1531 * improve the performance of the insertion process. A bad hint would
1532 * cause no gains in efficiency.
1535 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1536 * for more on @a hinting.
1538 * Insertion requires amortized constant time.
1540 template<typename
... _Args
>
1542 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1543 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1547 * @brief Inserts a std::pair into the %unordered_multimap.
1548 * @param __x Pair to be inserted (see std::make_pair for easy
1549 * creation of pairs).
1551 * @return An iterator that points to the inserted pair.
1553 * Insertion requires amortized constant time.
1556 insert(const value_type
& __x
)
1557 { return _M_h
.insert(__x
); }
1560 insert(value_type
&& __x
)
1561 { return _M_h
.insert(std::move(__x
)); }
1563 template<typename _Pair
, typename
= typename
1564 std::enable_if
<std::is_constructible
<value_type
,
1565 _Pair
&&>::value
>::type
>
1568 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
1573 * @brief Inserts a std::pair into the %unordered_multimap.
1574 * @param __hint An iterator that serves as a hint as to where the
1575 * pair should be inserted.
1576 * @param __x Pair to be inserted (see std::make_pair for easy creation
1578 * @return An iterator that points to the element with key of
1579 * @a __x (may or may not be the %pair passed in).
1581 * Note that the first parameter is only a hint and can potentially
1582 * improve the performance of the insertion process. A bad hint would
1583 * cause no gains in efficiency.
1586 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1587 * for more on @a hinting.
1589 * Insertion requires amortized constant time.
1592 insert(const_iterator __hint
, const value_type
& __x
)
1593 { return _M_h
.insert(__hint
, __x
); }
1595 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1596 // 2354. Unnecessary copying when inserting into maps with braced-init
1598 insert(const_iterator __hint
, value_type
&& __x
)
1599 { return _M_h
.insert(__hint
, std::move(__x
)); }
1601 template<typename _Pair
, typename
= typename
1602 std::enable_if
<std::is_constructible
<value_type
,
1603 _Pair
&&>::value
>::type
>
1605 insert(const_iterator __hint
, _Pair
&& __x
)
1606 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
1610 * @brief A template function that attempts to insert a range of
1612 * @param __first Iterator pointing to the start of the range to be
1614 * @param __last Iterator pointing to the end of the range.
1616 * Complexity similar to that of the range constructor.
1618 template<typename _InputIterator
>
1620 insert(_InputIterator __first
, _InputIterator __last
)
1621 { _M_h
.insert(__first
, __last
); }
1624 * @brief Attempts to insert a list of elements into the
1625 * %unordered_multimap.
1626 * @param __l A std::initializer_list<value_type> of elements
1629 * Complexity similar to that of the range constructor.
1632 insert(initializer_list
<value_type
> __l
)
1633 { _M_h
.insert(__l
); }
1635 #if __cplusplus > 201402L
1638 extract(const_iterator __pos
)
1640 __glibcxx_assert(__pos
!= end());
1641 return _M_h
.extract(__pos
);
1646 extract(const key_type
& __key
)
1647 { return _M_h
.extract(__key
); }
1649 /// Re-insert an extracted node.
1651 insert(node_type
&& __nh
)
1652 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1654 /// Re-insert an extracted node.
1656 insert(const_iterator __hint
, node_type
&& __nh
)
1657 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1662 * @brief Erases an element from an %unordered_multimap.
1663 * @param __position An iterator pointing to the element to be erased.
1664 * @return An iterator pointing to the element immediately following
1665 * @a __position prior to the element being erased. If no such
1666 * element exists, end() is returned.
1668 * This function erases an element, pointed to by the given iterator,
1669 * from an %unordered_multimap.
1670 * Note that this function only erases the element, and that if the
1671 * element is itself a pointer, the pointed-to memory is not touched in
1672 * any way. Managing the pointer is the user's responsibility.
1675 erase(const_iterator __position
)
1676 { return _M_h
.erase(__position
); }
1680 erase(iterator __position
)
1681 { return _M_h
.erase(__position
); }
1685 * @brief Erases elements according to the provided key.
1686 * @param __x Key of elements to be erased.
1687 * @return The number of elements erased.
1689 * This function erases all the elements located by the given key from
1690 * an %unordered_multimap.
1691 * Note that this function only erases the element, and that if the
1692 * element is itself a pointer, the pointed-to memory is not touched in
1693 * any way. Managing the pointer is the user's responsibility.
1696 erase(const key_type
& __x
)
1697 { return _M_h
.erase(__x
); }
1700 * @brief Erases a [__first,__last) range of elements from an
1701 * %unordered_multimap.
1702 * @param __first Iterator pointing to the start of the range to be
1704 * @param __last Iterator pointing to the end of the range to
1706 * @return The iterator @a __last.
1708 * This function erases a sequence of elements from an
1709 * %unordered_multimap.
1710 * Note that this function only erases the elements, and that if
1711 * the element is itself a pointer, the pointed-to memory is not touched
1712 * in any way. Managing the pointer is the user's responsibility.
1715 erase(const_iterator __first
, const_iterator __last
)
1716 { return _M_h
.erase(__first
, __last
); }
1719 * Erases all elements in an %unordered_multimap.
1720 * Note that this function only erases the elements, and that if the
1721 * elements themselves are pointers, the pointed-to memory is not touched
1722 * in any way. Managing the pointer is the user's responsibility.
1729 * @brief Swaps data with another %unordered_multimap.
1730 * @param __x An %unordered_multimap of the same element and allocator
1733 * This exchanges the elements between two %unordered_multimap in
1735 * Note that the global std::swap() function is specialized such that
1736 * std::swap(m1,m2) will feed to this function.
1739 swap(unordered_multimap
& __x
)
1740 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1741 { _M_h
.swap(__x
._M_h
); }
1743 #if __cplusplus > 201402L
1744 template<typename
, typename
, typename
>
1745 friend class _Hash_merge_helper
;
1747 template<typename _H2
, typename _P2
>
1749 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1752 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1753 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1756 template<typename _H2
, typename _P2
>
1758 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1759 { merge(__source
); }
1761 template<typename _H2
, typename _P2
>
1763 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1766 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1767 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1770 template<typename _H2
, typename _P2
>
1772 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1773 { merge(__source
); }
1778 /// Returns the hash functor object with which the %unordered_multimap
1779 /// was constructed.
1781 hash_function() const
1782 { return _M_h
.hash_function(); }
1784 /// Returns the key comparison object with which the %unordered_multimap
1785 /// was constructed.
1788 { return _M_h
.key_eq(); }
1794 * @brief Tries to locate an element in an %unordered_multimap.
1795 * @param __x Key to be located.
1796 * @return Iterator pointing to sought-after element, or end() if not
1799 * This function takes a key and tries to locate the element with which
1800 * the key matches. If successful the function returns an iterator
1801 * pointing to the sought after element. If unsuccessful it returns the
1802 * past-the-end ( @c end() ) iterator.
1805 find(const key_type
& __x
)
1806 { return _M_h
.find(__x
); }
1809 find(const key_type
& __x
) const
1810 { return _M_h
.find(__x
); }
1814 * @brief Finds the number of elements.
1815 * @param __x Key to count.
1816 * @return Number of elements with specified key.
1819 count(const key_type
& __x
) const
1820 { return _M_h
.count(__x
); }
1824 * @brief Finds a subsequence matching given key.
1825 * @param __x Key to be located.
1826 * @return Pair of iterators that possibly points to the subsequence
1827 * matching given key.
1829 std::pair
<iterator
, iterator
>
1830 equal_range(const key_type
& __x
)
1831 { return _M_h
.equal_range(__x
); }
1833 std::pair
<const_iterator
, const_iterator
>
1834 equal_range(const key_type
& __x
) const
1835 { return _M_h
.equal_range(__x
); }
1838 // bucket interface.
1840 /// Returns the number of buckets of the %unordered_multimap.
1842 bucket_count() const noexcept
1843 { return _M_h
.bucket_count(); }
1845 /// Returns the maximum number of buckets of the %unordered_multimap.
1847 max_bucket_count() const noexcept
1848 { return _M_h
.max_bucket_count(); }
1851 * @brief Returns the number of elements in a given bucket.
1852 * @param __n A bucket index.
1853 * @return The number of elements in the bucket.
1856 bucket_size(size_type __n
) const
1857 { return _M_h
.bucket_size(__n
); }
1860 * @brief Returns the bucket index of a given element.
1861 * @param __key A key instance.
1862 * @return The key bucket index.
1865 bucket(const key_type
& __key
) const
1866 { return _M_h
.bucket(__key
); }
1869 * @brief Returns a read/write iterator pointing to the first bucket
1871 * @param __n The bucket index.
1872 * @return A read/write local iterator.
1875 begin(size_type __n
)
1876 { return _M_h
.begin(__n
); }
1880 * @brief Returns a read-only (constant) iterator pointing to the first
1882 * @param __n The bucket index.
1883 * @return A read-only local iterator.
1885 const_local_iterator
1886 begin(size_type __n
) const
1887 { return _M_h
.begin(__n
); }
1889 const_local_iterator
1890 cbegin(size_type __n
) const
1891 { return _M_h
.cbegin(__n
); }
1895 * @brief Returns a read/write iterator pointing to one past the last
1897 * @param __n The bucket index.
1898 * @return A read/write local iterator.
1902 { return _M_h
.end(__n
); }
1906 * @brief Returns a read-only (constant) iterator pointing to one past
1907 * the last bucket elements.
1908 * @param __n The bucket index.
1909 * @return A read-only local iterator.
1911 const_local_iterator
1912 end(size_type __n
) const
1913 { return _M_h
.end(__n
); }
1915 const_local_iterator
1916 cend(size_type __n
) const
1917 { return _M_h
.cend(__n
); }
1922 /// Returns the average number of elements per bucket.
1924 load_factor() const noexcept
1925 { return _M_h
.load_factor(); }
1927 /// Returns a positive number that the %unordered_multimap tries to keep
1928 /// the load factor less than or equal to.
1930 max_load_factor() const noexcept
1931 { return _M_h
.max_load_factor(); }
1934 * @brief Change the %unordered_multimap maximum load factor.
1935 * @param __z The new maximum load factor.
1938 max_load_factor(float __z
)
1939 { _M_h
.max_load_factor(__z
); }
1942 * @brief May rehash the %unordered_multimap.
1943 * @param __n The new number of buckets.
1945 * Rehash will occur only if the new number of buckets respect the
1946 * %unordered_multimap maximum load factor.
1949 rehash(size_type __n
)
1950 { _M_h
.rehash(__n
); }
1953 * @brief Prepare the %unordered_multimap for a specified number of
1955 * @param __n Number of elements required.
1957 * Same as rehash(ceil(n / max_load_factor())).
1960 reserve(size_type __n
)
1961 { _M_h
.reserve(__n
); }
1963 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1966 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1967 _Hash1
, _Pred1
, _Alloc1
>&,
1968 const unordered_multimap
<_Key1
, _Tp1
,
1969 _Hash1
, _Pred1
, _Alloc1
>&);
1972 #if __cpp_deduction_guides >= 201606
1974 template<typename _InputIterator
,
1975 typename _Hash
= hash
<__iter_key_t
<_InputIterator
>>,
1976 typename _Pred
= equal_to
<__iter_key_t
<_InputIterator
>>,
1977 typename _Allocator
= allocator
<__iter_to_alloc_t
<_InputIterator
>>,
1978 typename
= _RequireInputIter
<_InputIterator
>,
1979 typename
= _RequireAllocator
<_Allocator
>>
1980 unordered_multimap(_InputIterator
, _InputIterator
,
1981 unordered_multimap
<int, int>::size_type
= {},
1982 _Hash
= _Hash(), _Pred
= _Pred(),
1983 _Allocator
= _Allocator())
1984 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
1985 __iter_val_t
<_InputIterator
>, _Hash
, _Pred
,
1988 template<typename _Key
, typename _Tp
, typename _Hash
= hash
<_Key
>,
1989 typename _Pred
= equal_to
<_Key
>,
1990 typename _Allocator
= allocator
<pair
<const _Key
, _Tp
>>,
1991 typename
= _RequireAllocator
<_Allocator
>>
1992 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
1993 unordered_multimap
<int, int>::size_type
= {},
1994 _Hash
= _Hash(), _Pred
= _Pred(),
1995 _Allocator
= _Allocator())
1996 -> unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Allocator
>;
1998 template<typename _InputIterator
, typename _Allocator
,
1999 typename
= _RequireInputIter
<_InputIterator
>,
2000 typename
= _RequireAllocator
<_Allocator
>>
2001 unordered_multimap(_InputIterator
, _InputIterator
,
2002 unordered_multimap
<int, int>::size_type
, _Allocator
)
2003 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2004 __iter_val_t
<_InputIterator
>,
2005 hash
<__iter_key_t
<_InputIterator
>>,
2006 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2008 template<typename _InputIterator
, typename _Allocator
,
2009 typename
= _RequireInputIter
<_InputIterator
>,
2010 typename
= _RequireAllocator
<_Allocator
>>
2011 unordered_multimap(_InputIterator
, _InputIterator
, _Allocator
)
2012 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2013 __iter_val_t
<_InputIterator
>,
2014 hash
<__iter_key_t
<_InputIterator
>>,
2015 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2017 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
2018 typename
= _RequireInputIter
<_InputIterator
>,
2019 typename
= _RequireAllocator
<_Allocator
>>
2020 unordered_multimap(_InputIterator
, _InputIterator
,
2021 unordered_multimap
<int, int>::size_type
, _Hash
,
2023 -> unordered_multimap
<__iter_key_t
<_InputIterator
>,
2024 __iter_val_t
<_InputIterator
>, _Hash
,
2025 equal_to
<__iter_key_t
<_InputIterator
>>, _Allocator
>;
2027 template<typename _Key
, typename _Tp
, typename _Allocator
,
2028 typename
= _RequireAllocator
<_Allocator
>>
2029 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2030 unordered_multimap
<int, int>::size_type
,
2032 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2034 template<typename _Key
, typename _Tp
, typename _Allocator
,
2035 typename
= _RequireAllocator
<_Allocator
>>
2036 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>, _Allocator
)
2037 -> unordered_multimap
<_Key
, _Tp
, hash
<_Key
>, equal_to
<_Key
>, _Allocator
>;
2039 template<typename _Key
, typename _Tp
, typename _Hash
, typename _Allocator
,
2040 typename
= _RequireAllocator
<_Allocator
>>
2041 unordered_multimap(initializer_list
<pair
<_Key
, _Tp
>>,
2042 unordered_multimap
<int, int>::size_type
,
2044 -> unordered_multimap
<_Key
, _Tp
, _Hash
, equal_to
<_Key
>, _Allocator
>;
2048 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2050 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2051 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2052 noexcept(noexcept(__x
.swap(__y
)))
2055 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2057 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2058 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2059 noexcept(noexcept(__x
.swap(__y
)))
2062 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2064 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2065 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2066 { return __x
._M_h
._M_equal(__y
._M_h
); }
2068 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2070 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2071 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2072 { return !(__x
== __y
); }
2074 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2076 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2077 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2078 { return __x
._M_h
._M_equal(__y
._M_h
); }
2080 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
2082 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
2083 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
2084 { return !(__x
== __y
); }
2086 _GLIBCXX_END_NAMESPACE_CONTAINER
2088 #if __cplusplus > 201402L
2089 // Allow std::unordered_map access to internals of compatible maps.
2090 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2091 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2092 struct _Hash_merge_helper
<
2093 _GLIBCXX_STD_C::unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2097 template<typename
... _Tp
>
2098 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2099 template<typename
... _Tp
>
2100 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2102 friend unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2105 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2106 { return __map
._M_h
; }
2109 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2110 { return __map
._M_h
; }
2113 // Allow std::unordered_multimap access to internals of compatible maps.
2114 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
2115 typename _Alloc
, typename _Hash2
, typename _Eq2
>
2116 struct _Hash_merge_helper
<
2117 _GLIBCXX_STD_C::unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
2121 template<typename
... _Tp
>
2122 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
2123 template<typename
... _Tp
>
2124 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
2126 friend unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
2129 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2130 { return __map
._M_h
; }
2133 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
2134 { return __map
._M_h
; }
2138 _GLIBCXX_END_NAMESPACE_VERSION
2141 #endif /* _UNORDERED_MAP_H */