1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2016 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_CONTAINER
37 /// Base types for unordered_map.
39 using __umap_traits
= __detail::_Hashtable_traits
<_Cache
, false, true>;
41 template<typename _Key
,
43 typename _Hash
= hash
<_Key
>,
44 typename _Pred
= std::equal_to
<_Key
>,
45 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
46 typename _Tr
= __umap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
47 using __umap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
48 _Alloc
, __detail::_Select1st
,
50 __detail::_Mod_range_hashing
,
51 __detail::_Default_ranged_hash
,
52 __detail::_Prime_rehash_policy
, _Tr
>;
54 /// Base types for unordered_multimap.
56 using __ummap_traits
= __detail::_Hashtable_traits
<_Cache
, false, false>;
58 template<typename _Key
,
60 typename _Hash
= hash
<_Key
>,
61 typename _Pred
= std::equal_to
<_Key
>,
62 typename _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> >,
63 typename _Tr
= __ummap_traits
<__cache_default
<_Key
, _Hash
>::value
>>
64 using __ummap_hashtable
= _Hashtable
<_Key
, std::pair
<const _Key
, _Tp
>,
65 _Alloc
, __detail::_Select1st
,
67 __detail::_Mod_range_hashing
,
68 __detail::_Default_ranged_hash
,
69 __detail::_Prime_rehash_policy
, _Tr
>;
71 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
72 class unordered_multimap
;
75 * @brief A standard container composed of unique keys (containing
76 * at most one of each key value) that associates values of another type
79 * @ingroup unordered_associative_containers
81 * @tparam _Key Type of key objects.
82 * @tparam _Tp Type of mapped objects.
83 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
84 * @tparam _Pred Predicate function object type, defaults
85 * to equal_to<_Value>.
86 * @tparam _Alloc Allocator type, defaults to
87 * std::allocator<std::pair<const _Key, _Tp>>.
89 * Meets the requirements of a <a href="tables.html#65">container</a>, and
90 * <a href="tables.html#xx">unordered associative container</a>
92 * The resulting value type of the container is std::pair<const _Key, _Tp>.
94 * Base is _Hashtable, dispatched at compile time via template
95 * alias __umap_hashtable.
97 template<class _Key
, class _Tp
,
98 class _Hash
= hash
<_Key
>,
99 class _Pred
= std::equal_to
<_Key
>,
100 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
103 typedef __umap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
110 typedef typename
_Hashtable::key_type key_type
;
111 typedef typename
_Hashtable::value_type value_type
;
112 typedef typename
_Hashtable::mapped_type mapped_type
;
113 typedef typename
_Hashtable::hasher hasher
;
114 typedef typename
_Hashtable::key_equal key_equal
;
115 typedef typename
_Hashtable::allocator_type allocator_type
;
119 /// Iterator-related typedefs.
120 typedef typename
_Hashtable::pointer pointer
;
121 typedef typename
_Hashtable::const_pointer const_pointer
;
122 typedef typename
_Hashtable::reference reference
;
123 typedef typename
_Hashtable::const_reference const_reference
;
124 typedef typename
_Hashtable::iterator iterator
;
125 typedef typename
_Hashtable::const_iterator const_iterator
;
126 typedef typename
_Hashtable::local_iterator local_iterator
;
127 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
128 typedef typename
_Hashtable::size_type size_type
;
129 typedef typename
_Hashtable::difference_type difference_type
;
132 #if __cplusplus > 201402L
133 using node_type
= typename
_Hashtable::node_type
;
134 using insert_return_type
= typename
_Hashtable::insert_return_type
;
137 //construct/destroy/copy
139 /// Default constructor.
140 unordered_map() = default;
143 * @brief Default constructor creates no elements.
144 * @param __n Minimal initial number of buckets.
145 * @param __hf A hash functor.
146 * @param __eql A key equality functor.
147 * @param __a An allocator object.
150 unordered_map(size_type __n
,
151 const hasher
& __hf
= hasher(),
152 const key_equal
& __eql
= key_equal(),
153 const allocator_type
& __a
= allocator_type())
154 : _M_h(__n
, __hf
, __eql
, __a
)
158 * @brief Builds an %unordered_map from a range.
159 * @param __first An input iterator.
160 * @param __last An input iterator.
161 * @param __n Minimal initial number of buckets.
162 * @param __hf A hash functor.
163 * @param __eql A key equality functor.
164 * @param __a An allocator object.
166 * Create an %unordered_map consisting of copies of the elements from
167 * [__first,__last). This is linear in N (where N is
168 * distance(__first,__last)).
170 template<typename _InputIterator
>
171 unordered_map(_InputIterator __first
, _InputIterator __last
,
173 const hasher
& __hf
= hasher(),
174 const key_equal
& __eql
= key_equal(),
175 const allocator_type
& __a
= allocator_type())
176 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
179 /// Copy constructor.
180 unordered_map(const unordered_map
&) = default;
182 /// Move constructor.
183 unordered_map(unordered_map
&&) = default;
186 * @brief Creates an %unordered_map with no elements.
187 * @param __a An allocator object.
190 unordered_map(const allocator_type
& __a
)
195 * @brief Copy constructor with allocator argument.
196 * @param __uset Input %unordered_map to copy.
197 * @param __a An allocator object.
199 unordered_map(const unordered_map
& __umap
,
200 const allocator_type
& __a
)
201 : _M_h(__umap
._M_h
, __a
)
205 * @brief Move constructor with allocator argument.
206 * @param __uset Input %unordered_map to move.
207 * @param __a An allocator object.
209 unordered_map(unordered_map
&& __umap
,
210 const allocator_type
& __a
)
211 : _M_h(std::move(__umap
._M_h
), __a
)
215 * @brief Builds an %unordered_map from an initializer_list.
216 * @param __l An initializer_list.
217 * @param __n Minimal initial number of buckets.
218 * @param __hf A hash functor.
219 * @param __eql A key equality functor.
220 * @param __a An allocator object.
222 * Create an %unordered_map consisting of copies of the elements in the
223 * list. This is linear in N (where N is @a __l.size()).
225 unordered_map(initializer_list
<value_type
> __l
,
227 const hasher
& __hf
= hasher(),
228 const key_equal
& __eql
= key_equal(),
229 const allocator_type
& __a
= allocator_type())
230 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
233 unordered_map(size_type __n
, const allocator_type
& __a
)
234 : unordered_map(__n
, hasher(), key_equal(), __a
)
237 unordered_map(size_type __n
, const hasher
& __hf
,
238 const allocator_type
& __a
)
239 : unordered_map(__n
, __hf
, key_equal(), __a
)
242 template<typename _InputIterator
>
243 unordered_map(_InputIterator __first
, _InputIterator __last
,
245 const allocator_type
& __a
)
246 : unordered_map(__first
, __last
, __n
, hasher(), key_equal(), __a
)
249 template<typename _InputIterator
>
250 unordered_map(_InputIterator __first
, _InputIterator __last
,
251 size_type __n
, const hasher
& __hf
,
252 const allocator_type
& __a
)
253 : unordered_map(__first
, __last
, __n
, __hf
, key_equal(), __a
)
256 unordered_map(initializer_list
<value_type
> __l
,
258 const allocator_type
& __a
)
259 : unordered_map(__l
, __n
, hasher(), key_equal(), __a
)
262 unordered_map(initializer_list
<value_type
> __l
,
263 size_type __n
, const hasher
& __hf
,
264 const allocator_type
& __a
)
265 : unordered_map(__l
, __n
, __hf
, key_equal(), __a
)
268 /// Copy assignment operator.
270 operator=(const unordered_map
&) = default;
272 /// Move assignment operator.
274 operator=(unordered_map
&&) = default;
277 * @brief %Unordered_map list assignment operator.
278 * @param __l An initializer_list.
280 * This function fills an %unordered_map with copies of the elements in
281 * the initializer list @a __l.
283 * Note that the assignment completely changes the %unordered_map and
284 * that the resulting %unordered_map's size is the same as the number
285 * of elements assigned.
288 operator=(initializer_list
<value_type
> __l
)
294 /// Returns the allocator object used by the %unordered_map.
296 get_allocator() const noexcept
297 { return _M_h
.get_allocator(); }
299 // size and capacity:
301 /// Returns true if the %unordered_map is empty.
303 empty() const noexcept
304 { return _M_h
.empty(); }
306 /// Returns the size of the %unordered_map.
308 size() const noexcept
309 { return _M_h
.size(); }
311 /// Returns the maximum size of the %unordered_map.
313 max_size() const noexcept
314 { return _M_h
.max_size(); }
319 * Returns a read/write iterator that points to the first element in the
324 { return _M_h
.begin(); }
328 * Returns a read-only (constant) iterator that points to the first
329 * element in the %unordered_map.
332 begin() const noexcept
333 { return _M_h
.begin(); }
336 cbegin() const noexcept
337 { return _M_h
.begin(); }
341 * Returns a read/write iterator that points one past the last element in
342 * the %unordered_map.
346 { return _M_h
.end(); }
350 * Returns a read-only (constant) iterator that points one past the last
351 * element in the %unordered_map.
355 { return _M_h
.end(); }
358 cend() const noexcept
359 { return _M_h
.end(); }
365 * @brief Attempts to build and insert a std::pair into the
368 * @param __args Arguments used to generate a new pair instance (see
369 * std::piecewise_contruct for passing arguments to each
370 * part of the pair constructor).
372 * @return A pair, of which the first element is an iterator that points
373 * to the possibly inserted pair, and the second is a bool that
374 * is true if the pair was actually inserted.
376 * This function attempts to build and insert a (key, value) %pair into
377 * the %unordered_map.
378 * An %unordered_map relies on unique keys and thus a %pair is only
379 * inserted if its first element (the key) is not already present in the
382 * Insertion requires amortized constant time.
384 template<typename
... _Args
>
385 std::pair
<iterator
, bool>
386 emplace(_Args
&&... __args
)
387 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
390 * @brief Attempts to build and insert a std::pair into the
393 * @param __pos An iterator that serves as a hint as to where the pair
394 * should be inserted.
395 * @param __args Arguments used to generate a new pair instance (see
396 * std::piecewise_contruct for passing arguments to each
397 * part of the pair constructor).
398 * @return An iterator that points to the element with key of the
399 * std::pair built from @a __args (may or may not be that
402 * This function is not concerned about whether the insertion took place,
403 * and thus does not return a boolean like the single-argument emplace()
405 * Note that the first parameter is only a hint and can potentially
406 * improve the performance of the insertion process. A bad hint would
407 * cause no gains in efficiency.
410 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
411 * for more on @a hinting.
413 * Insertion requires amortized constant time.
415 template<typename
... _Args
>
417 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
418 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
420 #if __cplusplus > 201402L
423 extract(const_iterator __pos
)
425 __glibcxx_assert(__pos
!= end());
426 return _M_h
.extract(__pos
);
431 extract(const key_type
& __key
)
432 { return _M_h
.extract(__key
); }
434 /// Re-insert an extracted node.
436 insert(node_type
&& __nh
)
437 { return _M_h
._M_reinsert_node(std::move(__nh
)); }
439 /// Re-insert an extracted node.
441 insert(const_iterator
, node_type
&& __nh
)
442 { return _M_h
._M_reinsert_node(std::move(__nh
)).position
; }
444 #define __cpp_lib_unordered_map_try_emplace 201411
446 * @brief Attempts to build and insert a std::pair into the
449 * @param __k Key to use for finding a possibly existing pair in
451 * @param __args Arguments used to generate the .second for a
454 * @return A pair, of which the first element is an iterator that points
455 * to the possibly inserted pair, and the second is a bool that
456 * is true if the pair was actually inserted.
458 * This function attempts to build and insert a (key, value) %pair into
459 * the %unordered_map.
460 * An %unordered_map relies on unique keys and thus a %pair is only
461 * inserted if its first element (the key) is not already present in the
463 * If a %pair is not inserted, this function has no effect.
465 * Insertion requires amortized constant time.
467 template <typename
... _Args
>
469 try_emplace(const key_type
& __k
, _Args
&&... __args
)
471 iterator __i
= find(__k
);
474 __i
= emplace(std::piecewise_construct
,
475 std::forward_as_tuple(__k
),
476 std::forward_as_tuple(
477 std::forward
<_Args
>(__args
)...))
484 // move-capable overload
485 template <typename
... _Args
>
487 try_emplace(key_type
&& __k
, _Args
&&... __args
)
489 iterator __i
= find(__k
);
492 __i
= emplace(std::piecewise_construct
,
493 std::forward_as_tuple(std::move(__k
)),
494 std::forward_as_tuple(
495 std::forward
<_Args
>(__args
)...))
503 * @brief Attempts to build and insert a std::pair into the
506 * @param __hint An iterator that serves as a hint as to where the pair
507 * should be inserted.
508 * @param __k Key to use for finding a possibly existing pair in
510 * @param __args Arguments used to generate the .second for a
512 * @return An iterator that points to the element with key of the
513 * std::pair built from @a __args (may or may not be that
516 * This function is not concerned about whether the insertion took place,
517 * and thus does not return a boolean like the single-argument emplace()
518 * does. However, if insertion did not take place,
519 * this function has no effect.
520 * Note that the first parameter is only a hint and can potentially
521 * improve the performance of the insertion process. A bad hint would
522 * cause no gains in efficiency.
525 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
526 * for more on @a hinting.
528 * Insertion requires amortized constant time.
530 template <typename
... _Args
>
532 try_emplace(const_iterator __hint
, const key_type
& __k
,
535 iterator __i
= find(__k
);
537 __i
= emplace_hint(__hint
, std::piecewise_construct
,
538 std::forward_as_tuple(__k
),
539 std::forward_as_tuple(
540 std::forward
<_Args
>(__args
)...));
544 // move-capable overload
545 template <typename
... _Args
>
547 try_emplace(const_iterator __hint
, key_type
&& __k
, _Args
&&... __args
)
549 iterator __i
= find(__k
);
551 __i
= emplace_hint(__hint
, std::piecewise_construct
,
552 std::forward_as_tuple(std::move(__k
)),
553 std::forward_as_tuple(
554 std::forward
<_Args
>(__args
)...));
561 * @brief Attempts to insert a std::pair into the %unordered_map.
563 * @param __x Pair to be inserted (see std::make_pair for easy
564 * creation of pairs).
566 * @return A pair, of which the first element is an iterator that
567 * points to the possibly inserted pair, and the second is
568 * a bool that is true if the pair was actually inserted.
570 * This function attempts to insert a (key, value) %pair into the
571 * %unordered_map. An %unordered_map relies on unique keys and thus a
572 * %pair is only inserted if its first element (the key) is not already
573 * present in the %unordered_map.
575 * Insertion requires amortized constant time.
577 std::pair
<iterator
, bool>
578 insert(const value_type
& __x
)
579 { return _M_h
.insert(__x
); }
581 template<typename _Pair
, typename
= typename
582 std::enable_if
<std::is_constructible
<value_type
,
583 _Pair
&&>::value
>::type
>
584 std::pair
<iterator
, bool>
586 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
591 * @brief Attempts to insert a std::pair into the %unordered_map.
592 * @param __hint An iterator that serves as a hint as to where the
593 * pair should be inserted.
594 * @param __x Pair to be inserted (see std::make_pair for easy creation
596 * @return An iterator that points to the element with key of
597 * @a __x (may or may not be the %pair passed in).
599 * This function is not concerned about whether the insertion took place,
600 * and thus does not return a boolean like the single-argument insert()
601 * does. Note that the first parameter is only a hint and can
602 * potentially improve the performance of the insertion process. A bad
603 * hint would cause no gains in efficiency.
606 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
607 * for more on @a hinting.
609 * Insertion requires amortized constant time.
612 insert(const_iterator __hint
, const value_type
& __x
)
613 { return _M_h
.insert(__hint
, __x
); }
615 template<typename _Pair
, typename
= typename
616 std::enable_if
<std::is_constructible
<value_type
,
617 _Pair
&&>::value
>::type
>
619 insert(const_iterator __hint
, _Pair
&& __x
)
620 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
624 * @brief A template function that attempts to insert a range of
626 * @param __first Iterator pointing to the start of the range to be
628 * @param __last Iterator pointing to the end of the range.
630 * Complexity similar to that of the range constructor.
632 template<typename _InputIterator
>
634 insert(_InputIterator __first
, _InputIterator __last
)
635 { _M_h
.insert(__first
, __last
); }
638 * @brief Attempts to insert a list of elements into the %unordered_map.
639 * @param __l A std::initializer_list<value_type> of elements
642 * Complexity similar to that of the range constructor.
645 insert(initializer_list
<value_type
> __l
)
646 { _M_h
.insert(__l
); }
649 #if __cplusplus > 201402L
650 #define __cpp_lib_unordered_map_insertion 201411
652 * @brief Attempts to insert a std::pair into the %unordered_map.
653 * @param __k Key to use for finding a possibly existing pair in
655 * @param __obj Argument used to generate the .second for a pair
658 * @return A pair, of which the first element is an iterator that
659 * points to the possibly inserted pair, and the second is
660 * a bool that is true if the pair was actually inserted.
662 * This function attempts to insert a (key, value) %pair into the
663 * %unordered_map. An %unordered_map relies on unique keys and thus a
664 * %pair is only inserted if its first element (the key) is not already
665 * present in the %unordered_map.
666 * If the %pair was already in the %unordered_map, the .second of
667 * the %pair is assigned from __obj.
669 * Insertion requires amortized constant time.
671 template <typename _Obj
>
673 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
675 iterator __i
= find(__k
);
678 __i
= emplace(std::piecewise_construct
,
679 std::forward_as_tuple(__k
),
680 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
684 (*__i
).second
= std::forward
<_Obj
>(__obj
);
688 // move-capable overload
689 template <typename _Obj
>
691 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
693 iterator __i
= find(__k
);
696 __i
= emplace(std::piecewise_construct
,
697 std::forward_as_tuple(std::move(__k
)),
698 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
702 (*__i
).second
= std::forward
<_Obj
>(__obj
);
707 * @brief Attempts to insert a std::pair into the %unordered_map.
708 * @param __hint An iterator that serves as a hint as to where the
709 * pair should be inserted.
710 * @param __k Key to use for finding a possibly existing pair in
712 * @param __obj Argument used to generate the .second for a pair
714 * @return An iterator that points to the element with key of
715 * @a __x (may or may not be the %pair passed in).
717 * This function is not concerned about whether the insertion took place,
718 * and thus does not return a boolean like the single-argument insert()
720 * If the %pair was already in the %unordered map, the .second of
721 * the %pair is assigned from __obj.
722 * Note that the first parameter is only a hint and can
723 * potentially improve the performance of the insertion process. A bad
724 * hint would cause no gains in efficiency.
727 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
728 * for more on @a hinting.
730 * Insertion requires amortized constant time.
732 template <typename _Obj
>
734 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
737 iterator __i
= find(__k
);
740 return emplace_hint(__hint
, std::piecewise_construct
,
741 std::forward_as_tuple(__k
),
742 std::forward_as_tuple(
743 std::forward
<_Obj
>(__obj
)));
745 (*__i
).second
= std::forward
<_Obj
>(__obj
);
749 // move-capable overload
750 template <typename _Obj
>
752 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
754 iterator __i
= find(__k
);
757 return emplace_hint(__hint
, std::piecewise_construct
,
758 std::forward_as_tuple(std::move(__k
)),
759 std::forward_as_tuple(
760 std::forward
<_Obj
>(__obj
)));
762 (*__i
).second
= std::forward
<_Obj
>(__obj
);
769 * @brief Erases an element from an %unordered_map.
770 * @param __position An iterator pointing to the element to be erased.
771 * @return An iterator pointing to the element immediately following
772 * @a __position prior to the element being erased. If no such
773 * element exists, end() is returned.
775 * This function erases an element, pointed to by the given iterator,
776 * from an %unordered_map.
777 * Note that this function only erases the element, and that if the
778 * element is itself a pointer, the pointed-to memory is not touched in
779 * any way. Managing the pointer is the user's responsibility.
782 erase(const_iterator __position
)
783 { return _M_h
.erase(__position
); }
787 erase(iterator __position
)
788 { return _M_h
.erase(__position
); }
792 * @brief Erases elements according to the provided key.
793 * @param __x Key of element to be erased.
794 * @return The number of elements erased.
796 * This function erases all the elements located by the given key from
797 * an %unordered_map. For an %unordered_map the result of this function
798 * can only be 0 (not present) or 1 (present).
799 * Note that this function only erases the element, and that if the
800 * element is itself a pointer, the pointed-to memory is not touched in
801 * any way. Managing the pointer is the user's responsibility.
804 erase(const key_type
& __x
)
805 { return _M_h
.erase(__x
); }
808 * @brief Erases a [__first,__last) range of elements from an
810 * @param __first Iterator pointing to the start of the range to be
812 * @param __last Iterator pointing to the end of the range to
814 * @return The iterator @a __last.
816 * This function erases a sequence of elements from an %unordered_map.
817 * Note that this function only erases the elements, and that if
818 * the element is itself a pointer, the pointed-to memory is not touched
819 * in any way. Managing the pointer is the user's responsibility.
822 erase(const_iterator __first
, const_iterator __last
)
823 { return _M_h
.erase(__first
, __last
); }
826 * Erases all elements in an %unordered_map.
827 * Note that this function only erases the elements, and that if the
828 * elements themselves are pointers, the pointed-to memory is not touched
829 * in any way. Managing the pointer is the user's responsibility.
836 * @brief Swaps data with another %unordered_map.
837 * @param __x An %unordered_map of the same element and allocator
840 * This exchanges the elements between two %unordered_map in constant
842 * Note that the global std::swap() function is specialized such that
843 * std::swap(m1,m2) will feed to this function.
846 swap(unordered_map
& __x
)
847 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
848 { _M_h
.swap(__x
._M_h
); }
850 #if __cplusplus > 201402L
851 template<typename
, typename
, typename
>
852 friend class _Hash_merge_helper
;
854 template<typename _H2
, typename _P2
>
856 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
858 using _Merge_helper
= _Hash_merge_helper
<unordered_map
, _H2
, _P2
>;
859 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
862 template<typename _H2
, typename _P2
>
864 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
867 template<typename _H2
, typename _P2
>
869 merge(unordered_multimap
<_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_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
883 /// Returns the hash functor object with which the %unordered_map was
886 hash_function() const
887 { return _M_h
.hash_function(); }
889 /// Returns the key comparison object with which the %unordered_map was
893 { return _M_h
.key_eq(); }
899 * @brief Tries to locate an element in an %unordered_map.
900 * @param __x Key to be located.
901 * @return Iterator pointing to sought-after element, or end() if not
904 * This function takes a key and tries to locate the element with which
905 * the key matches. If successful the function returns an iterator
906 * pointing to the sought after element. If unsuccessful it returns the
907 * past-the-end ( @c end() ) iterator.
910 find(const key_type
& __x
)
911 { return _M_h
.find(__x
); }
914 find(const key_type
& __x
) const
915 { return _M_h
.find(__x
); }
919 * @brief Finds the number of elements.
920 * @param __x Key to count.
921 * @return Number of elements with specified key.
923 * This function only makes sense for %unordered_multimap; for
924 * %unordered_map the result will either be 0 (not present) or 1
928 count(const key_type
& __x
) const
929 { return _M_h
.count(__x
); }
933 * @brief Finds a subsequence matching given key.
934 * @param __x Key to be located.
935 * @return Pair of iterators that possibly points to the subsequence
936 * matching given key.
938 * This function probably only makes sense for %unordered_multimap.
940 std::pair
<iterator
, iterator
>
941 equal_range(const key_type
& __x
)
942 { return _M_h
.equal_range(__x
); }
944 std::pair
<const_iterator
, const_iterator
>
945 equal_range(const key_type
& __x
) const
946 { return _M_h
.equal_range(__x
); }
951 * @brief Subscript ( @c [] ) access to %unordered_map data.
952 * @param __k The key for which data should be retrieved.
953 * @return A reference to the data of the (key,data) %pair.
955 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
956 * data associated with the key specified in subscript. If the key does
957 * not exist, a pair with that key is created using default values, which
960 * Lookup requires constant time.
963 operator[](const key_type
& __k
)
964 { return _M_h
[__k
]; }
967 operator[](key_type
&& __k
)
968 { return _M_h
[std::move(__k
)]; }
973 * @brief Access to %unordered_map data.
974 * @param __k The key for which data should be retrieved.
975 * @return A reference to the data whose key is equal to @a __k, if
976 * such a data is present in the %unordered_map.
977 * @throw std::out_of_range If no such data is present.
980 at(const key_type
& __k
)
981 { return _M_h
.at(__k
); }
984 at(const key_type
& __k
) const
985 { return _M_h
.at(__k
); }
990 /// Returns the number of buckets of the %unordered_map.
992 bucket_count() const noexcept
993 { return _M_h
.bucket_count(); }
995 /// Returns the maximum number of buckets of the %unordered_map.
997 max_bucket_count() const noexcept
998 { return _M_h
.max_bucket_count(); }
1001 * @brief Returns the number of elements in a given bucket.
1002 * @param __n A bucket index.
1003 * @return The number of elements in the bucket.
1006 bucket_size(size_type __n
) const
1007 { return _M_h
.bucket_size(__n
); }
1010 * @brief Returns the bucket index of a given element.
1011 * @param __key A key instance.
1012 * @return The key bucket index.
1015 bucket(const key_type
& __key
) const
1016 { return _M_h
.bucket(__key
); }
1019 * @brief Returns a read/write iterator pointing to the first bucket
1021 * @param __n The bucket index.
1022 * @return A read/write local iterator.
1025 begin(size_type __n
)
1026 { return _M_h
.begin(__n
); }
1030 * @brief Returns a read-only (constant) iterator pointing to the first
1032 * @param __n The bucket index.
1033 * @return A read-only local iterator.
1035 const_local_iterator
1036 begin(size_type __n
) const
1037 { return _M_h
.begin(__n
); }
1039 const_local_iterator
1040 cbegin(size_type __n
) const
1041 { return _M_h
.cbegin(__n
); }
1045 * @brief Returns a read/write iterator pointing to one past the last
1047 * @param __n The bucket index.
1048 * @return A read/write local iterator.
1052 { return _M_h
.end(__n
); }
1056 * @brief Returns a read-only (constant) iterator pointing to one past
1057 * the last bucket elements.
1058 * @param __n The bucket index.
1059 * @return A read-only local iterator.
1061 const_local_iterator
1062 end(size_type __n
) const
1063 { return _M_h
.end(__n
); }
1065 const_local_iterator
1066 cend(size_type __n
) const
1067 { return _M_h
.cend(__n
); }
1072 /// Returns the average number of elements per bucket.
1074 load_factor() const noexcept
1075 { return _M_h
.load_factor(); }
1077 /// Returns a positive number that the %unordered_map tries to keep the
1078 /// load factor less than or equal to.
1080 max_load_factor() const noexcept
1081 { return _M_h
.max_load_factor(); }
1084 * @brief Change the %unordered_map maximum load factor.
1085 * @param __z The new maximum load factor.
1088 max_load_factor(float __z
)
1089 { _M_h
.max_load_factor(__z
); }
1092 * @brief May rehash the %unordered_map.
1093 * @param __n The new number of buckets.
1095 * Rehash will occur only if the new number of buckets respect the
1096 * %unordered_map maximum load factor.
1099 rehash(size_type __n
)
1100 { _M_h
.rehash(__n
); }
1103 * @brief Prepare the %unordered_map for a specified number of
1105 * @param __n Number of elements required.
1107 * Same as rehash(ceil(n / max_load_factor())).
1110 reserve(size_type __n
)
1111 { _M_h
.reserve(__n
); }
1113 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1116 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1117 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1121 * @brief A standard container composed of equivalent keys
1122 * (possibly containing multiple of each key value) that associates
1123 * values of another type with the keys.
1125 * @ingroup unordered_associative_containers
1127 * @tparam _Key Type of key objects.
1128 * @tparam _Tp Type of mapped objects.
1129 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1130 * @tparam _Pred Predicate function object type, defaults
1131 * to equal_to<_Value>.
1132 * @tparam _Alloc Allocator type, defaults to
1133 * std::allocator<std::pair<const _Key, _Tp>>.
1135 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1136 * <a href="tables.html#xx">unordered associative container</a>
1138 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1140 * Base is _Hashtable, dispatched at compile time via template
1141 * alias __ummap_hashtable.
1143 template<class _Key
, class _Tp
,
1144 class _Hash
= hash
<_Key
>,
1145 class _Pred
= std::equal_to
<_Key
>,
1146 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
1147 class unordered_multimap
1149 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1155 /// Public typedefs.
1156 typedef typename
_Hashtable::key_type key_type
;
1157 typedef typename
_Hashtable::value_type value_type
;
1158 typedef typename
_Hashtable::mapped_type mapped_type
;
1159 typedef typename
_Hashtable::hasher hasher
;
1160 typedef typename
_Hashtable::key_equal key_equal
;
1161 typedef typename
_Hashtable::allocator_type allocator_type
;
1165 /// Iterator-related typedefs.
1166 typedef typename
_Hashtable::pointer pointer
;
1167 typedef typename
_Hashtable::const_pointer const_pointer
;
1168 typedef typename
_Hashtable::reference reference
;
1169 typedef typename
_Hashtable::const_reference const_reference
;
1170 typedef typename
_Hashtable::iterator iterator
;
1171 typedef typename
_Hashtable::const_iterator const_iterator
;
1172 typedef typename
_Hashtable::local_iterator local_iterator
;
1173 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1174 typedef typename
_Hashtable::size_type size_type
;
1175 typedef typename
_Hashtable::difference_type difference_type
;
1178 #if __cplusplus > 201402L
1179 using node_type
= typename
_Hashtable::node_type
;
1182 //construct/destroy/copy
1184 /// Default constructor.
1185 unordered_multimap() = default;
1188 * @brief Default constructor creates no elements.
1189 * @param __n Mnimal initial number of buckets.
1190 * @param __hf A hash functor.
1191 * @param __eql A key equality functor.
1192 * @param __a An allocator object.
1195 unordered_multimap(size_type __n
,
1196 const hasher
& __hf
= hasher(),
1197 const key_equal
& __eql
= key_equal(),
1198 const allocator_type
& __a
= allocator_type())
1199 : _M_h(__n
, __hf
, __eql
, __a
)
1203 * @brief Builds an %unordered_multimap from a range.
1204 * @param __first An input iterator.
1205 * @param __last An input iterator.
1206 * @param __n Minimal initial number of buckets.
1207 * @param __hf A hash functor.
1208 * @param __eql A key equality functor.
1209 * @param __a An allocator object.
1211 * Create an %unordered_multimap consisting of copies of the elements
1212 * from [__first,__last). This is linear in N (where N is
1213 * distance(__first,__last)).
1215 template<typename _InputIterator
>
1216 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1218 const hasher
& __hf
= hasher(),
1219 const key_equal
& __eql
= key_equal(),
1220 const allocator_type
& __a
= allocator_type())
1221 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1224 /// Copy constructor.
1225 unordered_multimap(const unordered_multimap
&) = default;
1227 /// Move constructor.
1228 unordered_multimap(unordered_multimap
&&) = default;
1231 * @brief Creates an %unordered_multimap with no elements.
1232 * @param __a An allocator object.
1235 unordered_multimap(const allocator_type
& __a
)
1240 * @brief Copy constructor with allocator argument.
1241 * @param __uset Input %unordered_multimap to copy.
1242 * @param __a An allocator object.
1244 unordered_multimap(const unordered_multimap
& __ummap
,
1245 const allocator_type
& __a
)
1246 : _M_h(__ummap
._M_h
, __a
)
1250 * @brief Move constructor with allocator argument.
1251 * @param __uset Input %unordered_multimap to move.
1252 * @param __a An allocator object.
1254 unordered_multimap(unordered_multimap
&& __ummap
,
1255 const allocator_type
& __a
)
1256 : _M_h(std::move(__ummap
._M_h
), __a
)
1260 * @brief Builds an %unordered_multimap from an initializer_list.
1261 * @param __l An initializer_list.
1262 * @param __n Minimal initial number of buckets.
1263 * @param __hf A hash functor.
1264 * @param __eql A key equality functor.
1265 * @param __a An allocator object.
1267 * Create an %unordered_multimap consisting of copies of the elements in
1268 * the list. This is linear in N (where N is @a __l.size()).
1270 unordered_multimap(initializer_list
<value_type
> __l
,
1272 const hasher
& __hf
= hasher(),
1273 const key_equal
& __eql
= key_equal(),
1274 const allocator_type
& __a
= allocator_type())
1275 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1278 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1279 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1282 unordered_multimap(size_type __n
, const hasher
& __hf
,
1283 const allocator_type
& __a
)
1284 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1287 template<typename _InputIterator
>
1288 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1290 const allocator_type
& __a
)
1291 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1294 template<typename _InputIterator
>
1295 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1296 size_type __n
, const hasher
& __hf
,
1297 const allocator_type
& __a
)
1298 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1301 unordered_multimap(initializer_list
<value_type
> __l
,
1303 const allocator_type
& __a
)
1304 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1307 unordered_multimap(initializer_list
<value_type
> __l
,
1308 size_type __n
, const hasher
& __hf
,
1309 const allocator_type
& __a
)
1310 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1313 /// Copy assignment operator.
1315 operator=(const unordered_multimap
&) = default;
1317 /// Move assignment operator.
1319 operator=(unordered_multimap
&&) = default;
1322 * @brief %Unordered_multimap list assignment operator.
1323 * @param __l An initializer_list.
1325 * This function fills an %unordered_multimap with copies of the
1326 * elements in the initializer list @a __l.
1328 * Note that the assignment completely changes the %unordered_multimap
1329 * and that the resulting %unordered_multimap's size is the same as the
1330 * number of elements assigned.
1333 operator=(initializer_list
<value_type
> __l
)
1339 /// Returns the allocator object used by the %unordered_multimap.
1341 get_allocator() const noexcept
1342 { return _M_h
.get_allocator(); }
1344 // size and capacity:
1346 /// Returns true if the %unordered_multimap is empty.
1348 empty() const noexcept
1349 { return _M_h
.empty(); }
1351 /// Returns the size of the %unordered_multimap.
1353 size() const noexcept
1354 { return _M_h
.size(); }
1356 /// Returns the maximum size of the %unordered_multimap.
1358 max_size() const noexcept
1359 { return _M_h
.max_size(); }
1364 * Returns a read/write iterator that points to the first element in the
1365 * %unordered_multimap.
1369 { return _M_h
.begin(); }
1373 * Returns a read-only (constant) iterator that points to the first
1374 * element in the %unordered_multimap.
1377 begin() const noexcept
1378 { return _M_h
.begin(); }
1381 cbegin() const noexcept
1382 { return _M_h
.begin(); }
1386 * Returns a read/write iterator that points one past the last element in
1387 * the %unordered_multimap.
1391 { return _M_h
.end(); }
1395 * Returns a read-only (constant) iterator that points one past the last
1396 * element in the %unordered_multimap.
1399 end() const noexcept
1400 { return _M_h
.end(); }
1403 cend() const noexcept
1404 { return _M_h
.end(); }
1410 * @brief Attempts to build and insert a std::pair into the
1411 * %unordered_multimap.
1413 * @param __args Arguments used to generate a new pair instance (see
1414 * std::piecewise_contruct for passing arguments to each
1415 * part of the pair constructor).
1417 * @return An iterator that points to the inserted pair.
1419 * This function attempts to build and insert a (key, value) %pair into
1420 * the %unordered_multimap.
1422 * Insertion requires amortized constant time.
1424 template<typename
... _Args
>
1426 emplace(_Args
&&... __args
)
1427 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1430 * @brief Attempts to build and insert a std::pair into the
1431 * %unordered_multimap.
1433 * @param __pos An iterator that serves as a hint as to where the pair
1434 * should be inserted.
1435 * @param __args Arguments used to generate a new pair instance (see
1436 * std::piecewise_contruct for passing arguments to each
1437 * part of the pair constructor).
1438 * @return An iterator that points to the element with key of the
1439 * std::pair built from @a __args.
1441 * Note that the first parameter is only a hint and can potentially
1442 * improve the performance of the insertion process. A bad hint would
1443 * cause no gains in efficiency.
1446 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1447 * for more on @a hinting.
1449 * Insertion requires amortized constant time.
1451 template<typename
... _Args
>
1453 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1454 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1458 * @brief Inserts a std::pair into the %unordered_multimap.
1459 * @param __x Pair to be inserted (see std::make_pair for easy
1460 * creation of pairs).
1462 * @return An iterator that points to the inserted pair.
1464 * Insertion requires amortized constant time.
1467 insert(const value_type
& __x
)
1468 { return _M_h
.insert(__x
); }
1470 template<typename _Pair
, typename
= typename
1471 std::enable_if
<std::is_constructible
<value_type
,
1472 _Pair
&&>::value
>::type
>
1475 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
1480 * @brief Inserts a std::pair into the %unordered_multimap.
1481 * @param __hint An iterator that serves as a hint as to where the
1482 * pair should be inserted.
1483 * @param __x Pair to be inserted (see std::make_pair for easy creation
1485 * @return An iterator that points to the element with key of
1486 * @a __x (may or may not be the %pair passed in).
1488 * Note that the first parameter is only a hint and can potentially
1489 * improve the performance of the insertion process. A bad hint would
1490 * cause no gains in efficiency.
1493 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1494 * for more on @a hinting.
1496 * Insertion requires amortized constant time.
1499 insert(const_iterator __hint
, const value_type
& __x
)
1500 { return _M_h
.insert(__hint
, __x
); }
1502 template<typename _Pair
, typename
= typename
1503 std::enable_if
<std::is_constructible
<value_type
,
1504 _Pair
&&>::value
>::type
>
1506 insert(const_iterator __hint
, _Pair
&& __x
)
1507 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
1511 * @brief A template function that attempts to insert a range of
1513 * @param __first Iterator pointing to the start of the range to be
1515 * @param __last Iterator pointing to the end of the range.
1517 * Complexity similar to that of the range constructor.
1519 template<typename _InputIterator
>
1521 insert(_InputIterator __first
, _InputIterator __last
)
1522 { _M_h
.insert(__first
, __last
); }
1525 * @brief Attempts to insert a list of elements into the
1526 * %unordered_multimap.
1527 * @param __l A std::initializer_list<value_type> of elements
1530 * Complexity similar to that of the range constructor.
1533 insert(initializer_list
<value_type
> __l
)
1534 { _M_h
.insert(__l
); }
1536 #if __cplusplus > 201402L
1539 extract(const_iterator __pos
)
1541 __glibcxx_assert(__pos
!= end());
1542 return _M_h
.extract(__pos
);
1547 extract(const key_type
& __key
)
1548 { return _M_h
.extract(__key
); }
1550 /// Re-insert an extracted node.
1552 insert(node_type
&& __nh
)
1553 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1555 /// Re-insert an extracted node.
1557 insert(const_iterator __hint
, node_type
&& __nh
)
1558 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1563 * @brief Erases an element from an %unordered_multimap.
1564 * @param __position An iterator pointing to the element to be erased.
1565 * @return An iterator pointing to the element immediately following
1566 * @a __position prior to the element being erased. If no such
1567 * element exists, end() is returned.
1569 * This function erases an element, pointed to by the given iterator,
1570 * from an %unordered_multimap.
1571 * Note that this function only erases the element, and that if the
1572 * element is itself a pointer, the pointed-to memory is not touched in
1573 * any way. Managing the pointer is the user's responsibility.
1576 erase(const_iterator __position
)
1577 { return _M_h
.erase(__position
); }
1581 erase(iterator __position
)
1582 { return _M_h
.erase(__position
); }
1586 * @brief Erases elements according to the provided key.
1587 * @param __x Key of elements to be erased.
1588 * @return The number of elements erased.
1590 * This function erases all the elements located by the given key from
1591 * an %unordered_multimap.
1592 * Note that this function only erases the element, and that if the
1593 * element is itself a pointer, the pointed-to memory is not touched in
1594 * any way. Managing the pointer is the user's responsibility.
1597 erase(const key_type
& __x
)
1598 { return _M_h
.erase(__x
); }
1601 * @brief Erases a [__first,__last) range of elements from an
1602 * %unordered_multimap.
1603 * @param __first Iterator pointing to the start of the range to be
1605 * @param __last Iterator pointing to the end of the range to
1607 * @return The iterator @a __last.
1609 * This function erases a sequence of elements from an
1610 * %unordered_multimap.
1611 * Note that this function only erases the elements, and that if
1612 * the element is itself a pointer, the pointed-to memory is not touched
1613 * in any way. Managing the pointer is the user's responsibility.
1616 erase(const_iterator __first
, const_iterator __last
)
1617 { return _M_h
.erase(__first
, __last
); }
1620 * Erases all elements in an %unordered_multimap.
1621 * Note that this function only erases the elements, and that if the
1622 * elements themselves are pointers, the pointed-to memory is not touched
1623 * in any way. Managing the pointer is the user's responsibility.
1630 * @brief Swaps data with another %unordered_multimap.
1631 * @param __x An %unordered_multimap of the same element and allocator
1634 * This exchanges the elements between two %unordered_multimap in
1636 * Note that the global std::swap() function is specialized such that
1637 * std::swap(m1,m2) will feed to this function.
1640 swap(unordered_multimap
& __x
)
1641 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1642 { _M_h
.swap(__x
._M_h
); }
1644 #if __cplusplus > 201402L
1645 template<typename
, typename
, typename
>
1646 friend class _Hash_merge_helper
;
1648 template<typename _H2
, typename _P2
>
1650 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1653 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1654 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1657 template<typename _H2
, typename _P2
>
1659 merge(unordered_multimap
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1660 { merge(__source
); }
1662 template<typename _H2
, typename _P2
>
1664 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>& __source
)
1667 = _Hash_merge_helper
<unordered_multimap
, _H2
, _P2
>;
1668 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1671 template<typename _H2
, typename _P2
>
1673 merge(unordered_map
<_Key
, _Tp
, _H2
, _P2
, _Alloc
>&& __source
)
1674 { merge(__source
); }
1679 /// Returns the hash functor object with which the %unordered_multimap
1680 /// was constructed.
1682 hash_function() const
1683 { return _M_h
.hash_function(); }
1685 /// Returns the key comparison object with which the %unordered_multimap
1686 /// was constructed.
1689 { return _M_h
.key_eq(); }
1695 * @brief Tries to locate an element in an %unordered_multimap.
1696 * @param __x Key to be located.
1697 * @return Iterator pointing to sought-after element, or end() if not
1700 * This function takes a key and tries to locate the element with which
1701 * the key matches. If successful the function returns an iterator
1702 * pointing to the sought after element. If unsuccessful it returns the
1703 * past-the-end ( @c end() ) iterator.
1706 find(const key_type
& __x
)
1707 { return _M_h
.find(__x
); }
1710 find(const key_type
& __x
) const
1711 { return _M_h
.find(__x
); }
1715 * @brief Finds the number of elements.
1716 * @param __x Key to count.
1717 * @return Number of elements with specified key.
1720 count(const key_type
& __x
) const
1721 { return _M_h
.count(__x
); }
1725 * @brief Finds a subsequence matching given key.
1726 * @param __x Key to be located.
1727 * @return Pair of iterators that possibly points to the subsequence
1728 * matching given key.
1730 std::pair
<iterator
, iterator
>
1731 equal_range(const key_type
& __x
)
1732 { return _M_h
.equal_range(__x
); }
1734 std::pair
<const_iterator
, const_iterator
>
1735 equal_range(const key_type
& __x
) const
1736 { return _M_h
.equal_range(__x
); }
1739 // bucket interface.
1741 /// Returns the number of buckets of the %unordered_multimap.
1743 bucket_count() const noexcept
1744 { return _M_h
.bucket_count(); }
1746 /// Returns the maximum number of buckets of the %unordered_multimap.
1748 max_bucket_count() const noexcept
1749 { return _M_h
.max_bucket_count(); }
1752 * @brief Returns the number of elements in a given bucket.
1753 * @param __n A bucket index.
1754 * @return The number of elements in the bucket.
1757 bucket_size(size_type __n
) const
1758 { return _M_h
.bucket_size(__n
); }
1761 * @brief Returns the bucket index of a given element.
1762 * @param __key A key instance.
1763 * @return The key bucket index.
1766 bucket(const key_type
& __key
) const
1767 { return _M_h
.bucket(__key
); }
1770 * @brief Returns a read/write iterator pointing to the first bucket
1772 * @param __n The bucket index.
1773 * @return A read/write local iterator.
1776 begin(size_type __n
)
1777 { return _M_h
.begin(__n
); }
1781 * @brief Returns a read-only (constant) iterator pointing to the first
1783 * @param __n The bucket index.
1784 * @return A read-only local iterator.
1786 const_local_iterator
1787 begin(size_type __n
) const
1788 { return _M_h
.begin(__n
); }
1790 const_local_iterator
1791 cbegin(size_type __n
) const
1792 { return _M_h
.cbegin(__n
); }
1796 * @brief Returns a read/write iterator pointing to one past the last
1798 * @param __n The bucket index.
1799 * @return A read/write local iterator.
1803 { return _M_h
.end(__n
); }
1807 * @brief Returns a read-only (constant) iterator pointing to one past
1808 * the last bucket elements.
1809 * @param __n The bucket index.
1810 * @return A read-only local iterator.
1812 const_local_iterator
1813 end(size_type __n
) const
1814 { return _M_h
.end(__n
); }
1816 const_local_iterator
1817 cend(size_type __n
) const
1818 { return _M_h
.cend(__n
); }
1823 /// Returns the average number of elements per bucket.
1825 load_factor() const noexcept
1826 { return _M_h
.load_factor(); }
1828 /// Returns a positive number that the %unordered_multimap tries to keep
1829 /// the load factor less than or equal to.
1831 max_load_factor() const noexcept
1832 { return _M_h
.max_load_factor(); }
1835 * @brief Change the %unordered_multimap maximum load factor.
1836 * @param __z The new maximum load factor.
1839 max_load_factor(float __z
)
1840 { _M_h
.max_load_factor(__z
); }
1843 * @brief May rehash the %unordered_multimap.
1844 * @param __n The new number of buckets.
1846 * Rehash will occur only if the new number of buckets respect the
1847 * %unordered_multimap maximum load factor.
1850 rehash(size_type __n
)
1851 { _M_h
.rehash(__n
); }
1854 * @brief Prepare the %unordered_multimap for a specified number of
1856 * @param __n Number of elements required.
1858 * Same as rehash(ceil(n / max_load_factor())).
1861 reserve(size_type __n
)
1862 { _M_h
.reserve(__n
); }
1864 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1867 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1868 _Hash1
, _Pred1
, _Alloc1
>&,
1869 const unordered_multimap
<_Key1
, _Tp1
,
1870 _Hash1
, _Pred1
, _Alloc1
>&);
1873 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1875 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1876 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1877 noexcept(noexcept(__x
.swap(__y
)))
1880 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1882 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1883 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1884 noexcept(noexcept(__x
.swap(__y
)))
1887 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1889 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1890 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1891 { return __x
._M_h
._M_equal(__y
._M_h
); }
1893 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1895 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1896 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1897 { return !(__x
== __y
); }
1899 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1901 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1902 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1903 { return __x
._M_h
._M_equal(__y
._M_h
); }
1905 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1907 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1908 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1909 { return !(__x
== __y
); }
1911 _GLIBCXX_END_NAMESPACE_CONTAINER
1913 #if __cplusplus > 201402L
1914 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1915 // Allow std::unordered_map access to internals of compatible maps.
1916 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
1917 typename _Alloc
, typename _Hash2
, typename _Eq2
>
1918 struct _Hash_merge_helper
<
1919 _GLIBCXX_STD_C::unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
1923 template<typename
... _Tp
>
1924 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
1925 template<typename
... _Tp
>
1926 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
1928 friend unordered_map
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
1931 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
1932 { return __map
._M_h
; }
1935 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
1936 { return __map
._M_h
; }
1939 // Allow std::unordered_multimap access to internals of compatible maps.
1940 template<typename _Key
, typename _Val
, typename _Hash1
, typename _Eq1
,
1941 typename _Alloc
, typename _Hash2
, typename _Eq2
>
1942 struct _Hash_merge_helper
<
1943 _GLIBCXX_STD_C::unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>,
1947 template<typename
... _Tp
>
1948 using unordered_map
= _GLIBCXX_STD_C::unordered_map
<_Tp
...>;
1949 template<typename
... _Tp
>
1950 using unordered_multimap
= _GLIBCXX_STD_C::unordered_multimap
<_Tp
...>;
1952 friend unordered_multimap
<_Key
, _Val
, _Hash1
, _Eq1
, _Alloc
>;
1955 _S_get_table(unordered_map
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
1956 { return __map
._M_h
; }
1959 _S_get_table(unordered_multimap
<_Key
, _Val
, _Hash2
, _Eq2
, _Alloc
>& __map
)
1960 { return __map
._M_h
; }
1962 _GLIBCXX_END_NAMESPACE_VERSION
1967 #endif /* _UNORDERED_MAP_H */