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
>;
72 * @brief A standard container composed of unique keys (containing
73 * at most one of each key value) that associates values of another type
76 * @ingroup unordered_associative_containers
78 * @tparam _Key Type of key objects.
79 * @tparam _Tp Type of mapped objects.
80 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
81 * @tparam _Pred Predicate function object type, defaults
82 * to equal_to<_Value>.
83 * @tparam _Alloc Allocator type, defaults to
84 * std::allocator<std::pair<const _Key, _Tp>>.
86 * Meets the requirements of a <a href="tables.html#65">container</a>, and
87 * <a href="tables.html#xx">unordered associative container</a>
89 * The resulting value type of the container is std::pair<const _Key, _Tp>.
91 * Base is _Hashtable, dispatched at compile time via template
92 * alias __umap_hashtable.
94 template<class _Key
, class _Tp
,
95 class _Hash
= hash
<_Key
>,
96 class _Pred
= std::equal_to
<_Key
>,
97 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
100 typedef __umap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
107 typedef typename
_Hashtable::key_type key_type
;
108 typedef typename
_Hashtable::value_type value_type
;
109 typedef typename
_Hashtable::mapped_type mapped_type
;
110 typedef typename
_Hashtable::hasher hasher
;
111 typedef typename
_Hashtable::key_equal key_equal
;
112 typedef typename
_Hashtable::allocator_type allocator_type
;
116 /// Iterator-related typedefs.
117 typedef typename
_Hashtable::pointer pointer
;
118 typedef typename
_Hashtable::const_pointer const_pointer
;
119 typedef typename
_Hashtable::reference reference
;
120 typedef typename
_Hashtable::const_reference const_reference
;
121 typedef typename
_Hashtable::iterator iterator
;
122 typedef typename
_Hashtable::const_iterator const_iterator
;
123 typedef typename
_Hashtable::local_iterator local_iterator
;
124 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
125 typedef typename
_Hashtable::size_type size_type
;
126 typedef typename
_Hashtable::difference_type difference_type
;
129 //construct/destroy/copy
131 /// Default constructor.
132 unordered_map() = default;
135 * @brief Default constructor creates no elements.
136 * @param __n Minimal initial number of buckets.
137 * @param __hf A hash functor.
138 * @param __eql A key equality functor.
139 * @param __a An allocator object.
142 unordered_map(size_type __n
,
143 const hasher
& __hf
= hasher(),
144 const key_equal
& __eql
= key_equal(),
145 const allocator_type
& __a
= allocator_type())
146 : _M_h(__n
, __hf
, __eql
, __a
)
150 * @brief Builds an %unordered_map from a range.
151 * @param __first An input iterator.
152 * @param __last An input iterator.
153 * @param __n Minimal initial number of buckets.
154 * @param __hf A hash functor.
155 * @param __eql A key equality functor.
156 * @param __a An allocator object.
158 * Create an %unordered_map consisting of copies of the elements from
159 * [__first,__last). This is linear in N (where N is
160 * distance(__first,__last)).
162 template<typename _InputIterator
>
163 unordered_map(_InputIterator __first
, _InputIterator __last
,
165 const hasher
& __hf
= hasher(),
166 const key_equal
& __eql
= key_equal(),
167 const allocator_type
& __a
= allocator_type())
168 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
171 /// Copy constructor.
172 unordered_map(const unordered_map
&) = default;
174 /// Move constructor.
175 unordered_map(unordered_map
&&) = default;
178 * @brief Creates an %unordered_map with no elements.
179 * @param __a An allocator object.
182 unordered_map(const allocator_type
& __a
)
187 * @brief Copy constructor with allocator argument.
188 * @param __uset Input %unordered_map to copy.
189 * @param __a An allocator object.
191 unordered_map(const unordered_map
& __umap
,
192 const allocator_type
& __a
)
193 : _M_h(__umap
._M_h
, __a
)
197 * @brief Move constructor with allocator argument.
198 * @param __uset Input %unordered_map to move.
199 * @param __a An allocator object.
201 unordered_map(unordered_map
&& __umap
,
202 const allocator_type
& __a
)
203 : _M_h(std::move(__umap
._M_h
), __a
)
207 * @brief Builds an %unordered_map from an initializer_list.
208 * @param __l An initializer_list.
209 * @param __n Minimal initial number of buckets.
210 * @param __hf A hash functor.
211 * @param __eql A key equality functor.
212 * @param __a An allocator object.
214 * Create an %unordered_map consisting of copies of the elements in the
215 * list. This is linear in N (where N is @a __l.size()).
217 unordered_map(initializer_list
<value_type
> __l
,
219 const hasher
& __hf
= hasher(),
220 const key_equal
& __eql
= key_equal(),
221 const allocator_type
& __a
= allocator_type())
222 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
225 unordered_map(size_type __n
, const allocator_type
& __a
)
226 : unordered_map(__n
, hasher(), key_equal(), __a
)
229 unordered_map(size_type __n
, const hasher
& __hf
,
230 const allocator_type
& __a
)
231 : unordered_map(__n
, __hf
, key_equal(), __a
)
234 template<typename _InputIterator
>
235 unordered_map(_InputIterator __first
, _InputIterator __last
,
237 const allocator_type
& __a
)
238 : unordered_map(__first
, __last
, __n
, hasher(), key_equal(), __a
)
241 template<typename _InputIterator
>
242 unordered_map(_InputIterator __first
, _InputIterator __last
,
243 size_type __n
, const hasher
& __hf
,
244 const allocator_type
& __a
)
245 : unordered_map(__first
, __last
, __n
, __hf
, key_equal(), __a
)
248 unordered_map(initializer_list
<value_type
> __l
,
250 const allocator_type
& __a
)
251 : unordered_map(__l
, __n
, hasher(), key_equal(), __a
)
254 unordered_map(initializer_list
<value_type
> __l
,
255 size_type __n
, const hasher
& __hf
,
256 const allocator_type
& __a
)
257 : unordered_map(__l
, __n
, __hf
, key_equal(), __a
)
260 /// Copy assignment operator.
262 operator=(const unordered_map
&) = default;
264 /// Move assignment operator.
266 operator=(unordered_map
&&) = default;
269 * @brief %Unordered_map list assignment operator.
270 * @param __l An initializer_list.
272 * This function fills an %unordered_map with copies of the elements in
273 * the initializer list @a __l.
275 * Note that the assignment completely changes the %unordered_map and
276 * that the resulting %unordered_map's size is the same as the number
277 * of elements assigned. Old data may be lost.
280 operator=(initializer_list
<value_type
> __l
)
286 /// Returns the allocator object with which the %unordered_map was
289 get_allocator() const noexcept
290 { return _M_h
.get_allocator(); }
292 // size and capacity:
294 /// Returns true if the %unordered_map is empty.
296 empty() const noexcept
297 { return _M_h
.empty(); }
299 /// Returns the size of the %unordered_map.
301 size() const noexcept
302 { return _M_h
.size(); }
304 /// Returns the maximum size of the %unordered_map.
306 max_size() const noexcept
307 { return _M_h
.max_size(); }
312 * Returns a read/write iterator that points to the first element in the
317 { return _M_h
.begin(); }
321 * Returns a read-only (constant) iterator that points to the first
322 * element in the %unordered_map.
325 begin() const noexcept
326 { return _M_h
.begin(); }
329 cbegin() const noexcept
330 { return _M_h
.begin(); }
334 * Returns a read/write iterator that points one past the last element in
335 * the %unordered_map.
339 { return _M_h
.end(); }
343 * Returns a read-only (constant) iterator that points one past the last
344 * element in the %unordered_map.
348 { return _M_h
.end(); }
351 cend() const noexcept
352 { return _M_h
.end(); }
358 * @brief Attempts to build and insert a std::pair into the
361 * @param __args Arguments used to generate a new pair instance (see
362 * std::piecewise_contruct for passing arguments to each
363 * part of the pair constructor).
365 * @return A pair, of which the first element is an iterator that points
366 * to the possibly inserted pair, and the second is a bool that
367 * is true if the pair was actually inserted.
369 * This function attempts to build and insert a (key, value) %pair into
370 * the %unordered_map.
371 * An %unordered_map relies on unique keys and thus a %pair is only
372 * inserted if its first element (the key) is not already present in the
375 * Insertion requires amortized constant time.
377 template<typename
... _Args
>
378 std::pair
<iterator
, bool>
379 emplace(_Args
&&... __args
)
380 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
383 * @brief Attempts to build and insert a std::pair into the
386 * @param __pos An iterator that serves as a hint as to where the pair
387 * should be inserted.
388 * @param __args Arguments used to generate a new pair instance (see
389 * std::piecewise_contruct for passing arguments to each
390 * part of the pair constructor).
391 * @return An iterator that points to the element with key of the
392 * std::pair built from @a __args (may or may not be that
395 * This function is not concerned about whether the insertion took place,
396 * and thus does not return a boolean like the single-argument emplace()
398 * Note that the first parameter is only a hint and can potentially
399 * improve the performance of the insertion process. A bad hint would
400 * cause no gains in efficiency.
403 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
404 * for more on @a hinting.
406 * Insertion requires amortized constant time.
408 template<typename
... _Args
>
410 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
411 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
414 #if __cplusplus > 201402L
415 #define __cpp_lib_unordered_map_try_emplace 201411
417 * @brief Attempts to build and insert a std::pair into the
420 * @param __k Key to use for finding a possibly existing pair in
422 * @param __args Arguments used to generate the .second for a
425 * @return A pair, of which the first element is an iterator that points
426 * to the possibly inserted pair, and the second is a bool that
427 * is true if the pair was actually inserted.
429 * This function attempts to build and insert a (key, value) %pair into
430 * the %unordered_map.
431 * An %unordered_map relies on unique keys and thus a %pair is only
432 * inserted if its first element (the key) is not already present in the
434 * If a %pair is not inserted, this function has no effect.
436 * Insertion requires amortized constant time.
438 template <typename
... _Args
>
440 try_emplace(const key_type
& __k
, _Args
&&... __args
)
442 iterator __i
= find(__k
);
445 __i
= emplace(std::piecewise_construct
,
446 std::forward_as_tuple(__k
),
447 std::forward_as_tuple(
448 std::forward
<_Args
>(__args
)...))
455 // move-capable overload
456 template <typename
... _Args
>
458 try_emplace(key_type
&& __k
, _Args
&&... __args
)
460 iterator __i
= find(__k
);
463 __i
= emplace(std::piecewise_construct
,
464 std::forward_as_tuple(std::move(__k
)),
465 std::forward_as_tuple(
466 std::forward
<_Args
>(__args
)...))
474 * @brief Attempts to build and insert a std::pair into the
477 * @param __hint An iterator that serves as a hint as to where the pair
478 * should be inserted.
479 * @param __k Key to use for finding a possibly existing pair in
481 * @param __args Arguments used to generate the .second for a
483 * @return An iterator that points to the element with key of the
484 * std::pair built from @a __args (may or may not be that
487 * This function is not concerned about whether the insertion took place,
488 * and thus does not return a boolean like the single-argument emplace()
489 * does. However, if insertion did not take place,
490 * this function has no effect.
491 * Note that the first parameter is only a hint and can potentially
492 * improve the performance of the insertion process. A bad hint would
493 * cause no gains in efficiency.
496 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
497 * for more on @a hinting.
499 * Insertion requires amortized constant time.
501 template <typename
... _Args
>
503 try_emplace(const_iterator __hint
, const key_type
& __k
,
506 iterator __i
= find(__k
);
508 __i
= emplace_hint(__hint
, std::piecewise_construct
,
509 std::forward_as_tuple(__k
),
510 std::forward_as_tuple(
511 std::forward
<_Args
>(__args
)...));
515 // move-capable overload
516 template <typename
... _Args
>
518 try_emplace(const_iterator __hint
, key_type
&& __k
, _Args
&&... __args
)
520 iterator __i
= find(__k
);
522 __i
= emplace_hint(__hint
, std::piecewise_construct
,
523 std::forward_as_tuple(std::move(__k
)),
524 std::forward_as_tuple(
525 std::forward
<_Args
>(__args
)...));
532 * @brief Attempts to insert a std::pair into the %unordered_map.
534 * @param __x Pair to be inserted (see std::make_pair for easy
535 * creation of pairs).
537 * @return A pair, of which the first element is an iterator that
538 * points to the possibly inserted pair, and the second is
539 * a bool that is true if the pair was actually inserted.
541 * This function attempts to insert a (key, value) %pair into the
542 * %unordered_map. An %unordered_map relies on unique keys and thus a
543 * %pair is only inserted if its first element (the key) is not already
544 * present in the %unordered_map.
546 * Insertion requires amortized constant time.
548 std::pair
<iterator
, bool>
549 insert(const value_type
& __x
)
550 { return _M_h
.insert(__x
); }
552 template<typename _Pair
, typename
= typename
553 std::enable_if
<std::is_constructible
<value_type
,
554 _Pair
&&>::value
>::type
>
555 std::pair
<iterator
, bool>
557 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
562 * @brief Attempts to insert a std::pair into the %unordered_map.
563 * @param __hint An iterator that serves as a hint as to where the
564 * pair should be inserted.
565 * @param __x Pair to be inserted (see std::make_pair for easy creation
567 * @return An iterator that points to the element with key of
568 * @a __x (may or may not be the %pair passed in).
570 * This function is not concerned about whether the insertion took place,
571 * and thus does not return a boolean like the single-argument insert()
572 * does. Note that the first parameter is only a hint and can
573 * potentially improve the performance of the insertion process. A bad
574 * hint would cause no gains in efficiency.
577 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
578 * for more on @a hinting.
580 * Insertion requires amortized constant time.
583 insert(const_iterator __hint
, const value_type
& __x
)
584 { return _M_h
.insert(__hint
, __x
); }
586 template<typename _Pair
, typename
= typename
587 std::enable_if
<std::is_constructible
<value_type
,
588 _Pair
&&>::value
>::type
>
590 insert(const_iterator __hint
, _Pair
&& __x
)
591 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
595 * @brief A template function that attempts to insert a range of
597 * @param __first Iterator pointing to the start of the range to be
599 * @param __last Iterator pointing to the end of the range.
601 * Complexity similar to that of the range constructor.
603 template<typename _InputIterator
>
605 insert(_InputIterator __first
, _InputIterator __last
)
606 { _M_h
.insert(__first
, __last
); }
609 * @brief Attempts to insert a list of elements into the %unordered_map.
610 * @param __l A std::initializer_list<value_type> of elements
613 * Complexity similar to that of the range constructor.
616 insert(initializer_list
<value_type
> __l
)
617 { _M_h
.insert(__l
); }
620 #if __cplusplus > 201402L
621 #define __cpp_lib_unordered_map_insertion 201411
623 * @brief Attempts to insert a std::pair into the %unordered_map.
624 * @param __k Key to use for finding a possibly existing pair in
626 * @param __obj Argument used to generate the .second for a pair
629 * @return A pair, of which the first element is an iterator that
630 * points to the possibly inserted pair, and the second is
631 * a bool that is true if the pair was actually inserted.
633 * This function attempts to insert a (key, value) %pair into the
634 * %unordered_map. An %unordered_map relies on unique keys and thus a
635 * %pair is only inserted if its first element (the key) is not already
636 * present in the %unordered_map.
637 * If the %pair was already in the %unordered_map, the .second of
638 * the %pair is assigned from __obj.
640 * Insertion requires amortized constant time.
642 template <typename _Obj
>
644 insert_or_assign(const key_type
& __k
, _Obj
&& __obj
)
646 iterator __i
= find(__k
);
649 __i
= emplace(std::piecewise_construct
,
650 std::forward_as_tuple(__k
),
651 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
655 (*__i
).second
= std::forward
<_Obj
>(__obj
);
659 // move-capable overload
660 template <typename _Obj
>
662 insert_or_assign(key_type
&& __k
, _Obj
&& __obj
)
664 iterator __i
= find(__k
);
667 __i
= emplace(std::piecewise_construct
,
668 std::forward_as_tuple(std::move(__k
)),
669 std::forward_as_tuple(std::forward
<_Obj
>(__obj
)))
673 (*__i
).second
= std::forward
<_Obj
>(__obj
);
678 * @brief Attempts to insert a std::pair into the %unordered_map.
679 * @param __hint An iterator that serves as a hint as to where the
680 * pair should be inserted.
681 * @param __k Key to use for finding a possibly existing pair in
683 * @param __obj Argument used to generate the .second for a pair
685 * @return An iterator that points to the element with key of
686 * @a __x (may or may not be the %pair passed in).
688 * This function is not concerned about whether the insertion took place,
689 * and thus does not return a boolean like the single-argument insert()
691 * If the %pair was already in the %unordered map, the .second of
692 * the %pair is assigned from __obj.
693 * Note that the first parameter is only a hint and can
694 * potentially improve the performance of the insertion process. A bad
695 * hint would cause no gains in efficiency.
698 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
699 * for more on @a hinting.
701 * Insertion requires amortized constant time.
703 template <typename _Obj
>
705 insert_or_assign(const_iterator __hint
, const key_type
& __k
,
708 iterator __i
= find(__k
);
711 return emplace_hint(__hint
, std::piecewise_construct
,
712 std::forward_as_tuple(__k
),
713 std::forward_as_tuple(
714 std::forward
<_Obj
>(__obj
)));
716 (*__i
).second
= std::forward
<_Obj
>(__obj
);
720 // move-capable overload
721 template <typename _Obj
>
723 insert_or_assign(const_iterator __hint
, key_type
&& __k
, _Obj
&& __obj
)
725 iterator __i
= find(__k
);
728 return emplace_hint(__hint
, std::piecewise_construct
,
729 std::forward_as_tuple(std::move(__k
)),
730 std::forward_as_tuple(
731 std::forward
<_Obj
>(__obj
)));
733 (*__i
).second
= std::forward
<_Obj
>(__obj
);
740 * @brief Erases an element from an %unordered_map.
741 * @param __position An iterator pointing to the element to be erased.
742 * @return An iterator pointing to the element immediately following
743 * @a __position prior to the element being erased. If no such
744 * element exists, end() is returned.
746 * This function erases an element, pointed to by the given iterator,
747 * from an %unordered_map.
748 * Note that this function only erases the element, and that if the
749 * element is itself a pointer, the pointed-to memory is not touched in
750 * any way. Managing the pointer is the user's responsibility.
753 erase(const_iterator __position
)
754 { return _M_h
.erase(__position
); }
758 erase(iterator __position
)
759 { return _M_h
.erase(__position
); }
763 * @brief Erases elements according to the provided key.
764 * @param __x Key of element to be erased.
765 * @return The number of elements erased.
767 * This function erases all the elements located by the given key from
768 * an %unordered_map. For an %unordered_map the result of this function
769 * can only be 0 (not present) or 1 (present).
770 * Note that this function only erases the element, and that if the
771 * element is itself a pointer, the pointed-to memory is not touched in
772 * any way. Managing the pointer is the user's responsibility.
775 erase(const key_type
& __x
)
776 { return _M_h
.erase(__x
); }
779 * @brief Erases a [__first,__last) range of elements from an
781 * @param __first Iterator pointing to the start of the range to be
783 * @param __last Iterator pointing to the end of the range to
785 * @return The iterator @a __last.
787 * This function erases a sequence of elements from an %unordered_map.
788 * Note that this function only erases the elements, and that if
789 * the element is itself a pointer, the pointed-to memory is not touched
790 * in any way. Managing the pointer is the user's responsibility.
793 erase(const_iterator __first
, const_iterator __last
)
794 { return _M_h
.erase(__first
, __last
); }
797 * Erases all elements in an %unordered_map.
798 * Note that this function only erases the elements, and that if the
799 * elements themselves are pointers, the pointed-to memory is not touched
800 * in any way. Managing the pointer is the user's responsibility.
807 * @brief Swaps data with another %unordered_map.
808 * @param __x An %unordered_map of the same element and allocator
811 * This exchanges the elements between two %unordered_map in constant
813 * Note that the global std::swap() function is specialized such that
814 * std::swap(m1,m2) will feed to this function.
817 swap(unordered_map
& __x
)
818 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
819 { _M_h
.swap(__x
._M_h
); }
823 /// Returns the hash functor object with which the %unordered_map was
826 hash_function() const
827 { return _M_h
.hash_function(); }
829 /// Returns the key comparison object with which the %unordered_map was
833 { return _M_h
.key_eq(); }
839 * @brief Tries to locate an element in an %unordered_map.
840 * @param __x Key to be located.
841 * @return Iterator pointing to sought-after element, or end() if not
844 * This function takes a key and tries to locate the element with which
845 * the key matches. If successful the function returns an iterator
846 * pointing to the sought after element. If unsuccessful it returns the
847 * past-the-end ( @c end() ) iterator.
850 find(const key_type
& __x
)
851 { return _M_h
.find(__x
); }
854 find(const key_type
& __x
) const
855 { return _M_h
.find(__x
); }
859 * @brief Finds the number of elements.
860 * @param __x Key to count.
861 * @return Number of elements with specified key.
863 * This function only makes sense for %unordered_multimap; for
864 * %unordered_map the result will either be 0 (not present) or 1
868 count(const key_type
& __x
) const
869 { return _M_h
.count(__x
); }
873 * @brief Finds a subsequence matching given key.
874 * @param __x Key to be located.
875 * @return Pair of iterators that possibly points to the subsequence
876 * matching given key.
878 * This function probably only makes sense for %unordered_multimap.
880 std::pair
<iterator
, iterator
>
881 equal_range(const key_type
& __x
)
882 { return _M_h
.equal_range(__x
); }
884 std::pair
<const_iterator
, const_iterator
>
885 equal_range(const key_type
& __x
) const
886 { return _M_h
.equal_range(__x
); }
891 * @brief Subscript ( @c [] ) access to %unordered_map data.
892 * @param __k The key for which data should be retrieved.
893 * @return A reference to the data of the (key,data) %pair.
895 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
896 * data associated with the key specified in subscript. If the key does
897 * not exist, a pair with that key is created using default values, which
900 * Lookup requires constant time.
903 operator[](const key_type
& __k
)
904 { return _M_h
[__k
]; }
907 operator[](key_type
&& __k
)
908 { return _M_h
[std::move(__k
)]; }
913 * @brief Access to %unordered_map data.
914 * @param __k The key for which data should be retrieved.
915 * @return A reference to the data whose key is equal to @a __k, if
916 * such a data is present in the %unordered_map.
917 * @throw std::out_of_range If no such data is present.
920 at(const key_type
& __k
)
921 { return _M_h
.at(__k
); }
924 at(const key_type
& __k
) const
925 { return _M_h
.at(__k
); }
930 /// Returns the number of buckets of the %unordered_map.
932 bucket_count() const noexcept
933 { return _M_h
.bucket_count(); }
935 /// Returns the maximum number of buckets of the %unordered_map.
937 max_bucket_count() const noexcept
938 { return _M_h
.max_bucket_count(); }
941 * @brief Returns the number of elements in a given bucket.
942 * @param __n A bucket index.
943 * @return The number of elements in the bucket.
946 bucket_size(size_type __n
) const
947 { return _M_h
.bucket_size(__n
); }
950 * @brief Returns the bucket index of a given element.
951 * @param __key A key instance.
952 * @return The key bucket index.
955 bucket(const key_type
& __key
) const
956 { return _M_h
.bucket(__key
); }
959 * @brief Returns a read/write iterator pointing to the first bucket
961 * @param __n The bucket index.
962 * @return A read/write local iterator.
966 { return _M_h
.begin(__n
); }
970 * @brief Returns a read-only (constant) iterator pointing to the first
972 * @param __n The bucket index.
973 * @return A read-only local iterator.
976 begin(size_type __n
) const
977 { return _M_h
.begin(__n
); }
980 cbegin(size_type __n
) const
981 { return _M_h
.cbegin(__n
); }
985 * @brief Returns a read/write iterator pointing to one past the last
987 * @param __n The bucket index.
988 * @return A read/write local iterator.
992 { return _M_h
.end(__n
); }
996 * @brief Returns a read-only (constant) iterator pointing to one past
997 * the last bucket elements.
998 * @param __n The bucket index.
999 * @return A read-only local iterator.
1001 const_local_iterator
1002 end(size_type __n
) const
1003 { return _M_h
.end(__n
); }
1005 const_local_iterator
1006 cend(size_type __n
) const
1007 { return _M_h
.cend(__n
); }
1012 /// Returns the average number of elements per bucket.
1014 load_factor() const noexcept
1015 { return _M_h
.load_factor(); }
1017 /// Returns a positive number that the %unordered_map tries to keep the
1018 /// load factor less than or equal to.
1020 max_load_factor() const noexcept
1021 { return _M_h
.max_load_factor(); }
1024 * @brief Change the %unordered_map maximum load factor.
1025 * @param __z The new maximum load factor.
1028 max_load_factor(float __z
)
1029 { _M_h
.max_load_factor(__z
); }
1032 * @brief May rehash the %unordered_map.
1033 * @param __n The new number of buckets.
1035 * Rehash will occur only if the new number of buckets respect the
1036 * %unordered_map maximum load factor.
1039 rehash(size_type __n
)
1040 { _M_h
.rehash(__n
); }
1043 * @brief Prepare the %unordered_map for a specified number of
1045 * @param __n Number of elements required.
1047 * Same as rehash(ceil(n / max_load_factor())).
1050 reserve(size_type __n
)
1051 { _M_h
.reserve(__n
); }
1053 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1056 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
1057 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
1061 * @brief A standard container composed of equivalent keys
1062 * (possibly containing multiple of each key value) that associates
1063 * values of another type with the keys.
1065 * @ingroup unordered_associative_containers
1067 * @tparam _Key Type of key objects.
1068 * @tparam _Tp Type of mapped objects.
1069 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1070 * @tparam _Pred Predicate function object type, defaults
1071 * to equal_to<_Value>.
1072 * @tparam _Alloc Allocator type, defaults to
1073 * std::allocator<std::pair<const _Key, _Tp>>.
1075 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1076 * <a href="tables.html#xx">unordered associative container</a>
1078 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1080 * Base is _Hashtable, dispatched at compile time via template
1081 * alias __ummap_hashtable.
1083 template<class _Key
, class _Tp
,
1084 class _Hash
= hash
<_Key
>,
1085 class _Pred
= std::equal_to
<_Key
>,
1086 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
1087 class unordered_multimap
1089 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
1095 /// Public typedefs.
1096 typedef typename
_Hashtable::key_type key_type
;
1097 typedef typename
_Hashtable::value_type value_type
;
1098 typedef typename
_Hashtable::mapped_type mapped_type
;
1099 typedef typename
_Hashtable::hasher hasher
;
1100 typedef typename
_Hashtable::key_equal key_equal
;
1101 typedef typename
_Hashtable::allocator_type allocator_type
;
1105 /// Iterator-related typedefs.
1106 typedef typename
_Hashtable::pointer pointer
;
1107 typedef typename
_Hashtable::const_pointer const_pointer
;
1108 typedef typename
_Hashtable::reference reference
;
1109 typedef typename
_Hashtable::const_reference const_reference
;
1110 typedef typename
_Hashtable::iterator iterator
;
1111 typedef typename
_Hashtable::const_iterator const_iterator
;
1112 typedef typename
_Hashtable::local_iterator local_iterator
;
1113 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
1114 typedef typename
_Hashtable::size_type size_type
;
1115 typedef typename
_Hashtable::difference_type difference_type
;
1118 //construct/destroy/copy
1120 /// Default constructor.
1121 unordered_multimap() = default;
1124 * @brief Default constructor creates no elements.
1125 * @param __n Mnimal initial number of buckets.
1126 * @param __hf A hash functor.
1127 * @param __eql A key equality functor.
1128 * @param __a An allocator object.
1131 unordered_multimap(size_type __n
,
1132 const hasher
& __hf
= hasher(),
1133 const key_equal
& __eql
= key_equal(),
1134 const allocator_type
& __a
= allocator_type())
1135 : _M_h(__n
, __hf
, __eql
, __a
)
1139 * @brief Builds an %unordered_multimap from a range.
1140 * @param __first An input iterator.
1141 * @param __last An input iterator.
1142 * @param __n Minimal initial number of buckets.
1143 * @param __hf A hash functor.
1144 * @param __eql A key equality functor.
1145 * @param __a An allocator object.
1147 * Create an %unordered_multimap consisting of copies of the elements
1148 * from [__first,__last). This is linear in N (where N is
1149 * distance(__first,__last)).
1151 template<typename _InputIterator
>
1152 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1154 const hasher
& __hf
= hasher(),
1155 const key_equal
& __eql
= key_equal(),
1156 const allocator_type
& __a
= allocator_type())
1157 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
1160 /// Copy constructor.
1161 unordered_multimap(const unordered_multimap
&) = default;
1163 /// Move constructor.
1164 unordered_multimap(unordered_multimap
&&) = default;
1167 * @brief Creates an %unordered_multimap with no elements.
1168 * @param __a An allocator object.
1171 unordered_multimap(const allocator_type
& __a
)
1176 * @brief Copy constructor with allocator argument.
1177 * @param __uset Input %unordered_multimap to copy.
1178 * @param __a An allocator object.
1180 unordered_multimap(const unordered_multimap
& __ummap
,
1181 const allocator_type
& __a
)
1182 : _M_h(__ummap
._M_h
, __a
)
1186 * @brief Move constructor with allocator argument.
1187 * @param __uset Input %unordered_multimap to move.
1188 * @param __a An allocator object.
1190 unordered_multimap(unordered_multimap
&& __ummap
,
1191 const allocator_type
& __a
)
1192 : _M_h(std::move(__ummap
._M_h
), __a
)
1196 * @brief Builds an %unordered_multimap from an initializer_list.
1197 * @param __l An initializer_list.
1198 * @param __n Minimal initial number of buckets.
1199 * @param __hf A hash functor.
1200 * @param __eql A key equality functor.
1201 * @param __a An allocator object.
1203 * Create an %unordered_multimap consisting of copies of the elements in
1204 * the list. This is linear in N (where N is @a __l.size()).
1206 unordered_multimap(initializer_list
<value_type
> __l
,
1208 const hasher
& __hf
= hasher(),
1209 const key_equal
& __eql
= key_equal(),
1210 const allocator_type
& __a
= allocator_type())
1211 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
1214 unordered_multimap(size_type __n
, const allocator_type
& __a
)
1215 : unordered_multimap(__n
, hasher(), key_equal(), __a
)
1218 unordered_multimap(size_type __n
, const hasher
& __hf
,
1219 const allocator_type
& __a
)
1220 : unordered_multimap(__n
, __hf
, key_equal(), __a
)
1223 template<typename _InputIterator
>
1224 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1226 const allocator_type
& __a
)
1227 : unordered_multimap(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1230 template<typename _InputIterator
>
1231 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
1232 size_type __n
, const hasher
& __hf
,
1233 const allocator_type
& __a
)
1234 : unordered_multimap(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1237 unordered_multimap(initializer_list
<value_type
> __l
,
1239 const allocator_type
& __a
)
1240 : unordered_multimap(__l
, __n
, hasher(), key_equal(), __a
)
1243 unordered_multimap(initializer_list
<value_type
> __l
,
1244 size_type __n
, const hasher
& __hf
,
1245 const allocator_type
& __a
)
1246 : unordered_multimap(__l
, __n
, __hf
, key_equal(), __a
)
1249 /// Copy assignment operator.
1251 operator=(const unordered_multimap
&) = default;
1253 /// Move assignment operator.
1255 operator=(unordered_multimap
&&) = default;
1258 * @brief %Unordered_multimap list assignment operator.
1259 * @param __l An initializer_list.
1261 * This function fills an %unordered_multimap with copies of the elements
1262 * in the initializer list @a __l.
1264 * Note that the assignment completely changes the %unordered_multimap
1265 * and that the resulting %unordered_multimap's size is the same as the
1266 * number of elements assigned. Old data may be lost.
1269 operator=(initializer_list
<value_type
> __l
)
1275 /// Returns the allocator object with which the %unordered_multimap was
1278 get_allocator() const noexcept
1279 { return _M_h
.get_allocator(); }
1281 // size and capacity:
1283 /// Returns true if the %unordered_multimap is empty.
1285 empty() const noexcept
1286 { return _M_h
.empty(); }
1288 /// Returns the size of the %unordered_multimap.
1290 size() const noexcept
1291 { return _M_h
.size(); }
1293 /// Returns the maximum size of the %unordered_multimap.
1295 max_size() const noexcept
1296 { return _M_h
.max_size(); }
1301 * Returns a read/write iterator that points to the first element in the
1302 * %unordered_multimap.
1306 { return _M_h
.begin(); }
1310 * Returns a read-only (constant) iterator that points to the first
1311 * element in the %unordered_multimap.
1314 begin() const noexcept
1315 { return _M_h
.begin(); }
1318 cbegin() const noexcept
1319 { return _M_h
.begin(); }
1323 * Returns a read/write iterator that points one past the last element in
1324 * the %unordered_multimap.
1328 { return _M_h
.end(); }
1332 * Returns a read-only (constant) iterator that points one past the last
1333 * element in the %unordered_multimap.
1336 end() const noexcept
1337 { return _M_h
.end(); }
1340 cend() const noexcept
1341 { return _M_h
.end(); }
1347 * @brief Attempts to build and insert a std::pair into the
1348 * %unordered_multimap.
1350 * @param __args Arguments used to generate a new pair instance (see
1351 * std::piecewise_contruct for passing arguments to each
1352 * part of the pair constructor).
1354 * @return An iterator that points to the inserted pair.
1356 * This function attempts to build and insert a (key, value) %pair into
1357 * the %unordered_multimap.
1359 * Insertion requires amortized constant time.
1361 template<typename
... _Args
>
1363 emplace(_Args
&&... __args
)
1364 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1367 * @brief Attempts to build and insert a std::pair into the
1368 * %unordered_multimap.
1370 * @param __pos An iterator that serves as a hint as to where the pair
1371 * should be inserted.
1372 * @param __args Arguments used to generate a new pair instance (see
1373 * std::piecewise_contruct for passing arguments to each
1374 * part of the pair constructor).
1375 * @return An iterator that points to the element with key of the
1376 * std::pair built from @a __args.
1378 * Note that the first parameter is only a hint and can potentially
1379 * improve the performance of the insertion process. A bad hint would
1380 * cause no gains in efficiency.
1383 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1384 * for more on @a hinting.
1386 * Insertion requires amortized constant time.
1388 template<typename
... _Args
>
1390 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1391 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1395 * @brief Inserts a std::pair into the %unordered_multimap.
1396 * @param __x Pair to be inserted (see std::make_pair for easy
1397 * creation of pairs).
1399 * @return An iterator that points to the inserted pair.
1401 * Insertion requires amortized constant time.
1404 insert(const value_type
& __x
)
1405 { return _M_h
.insert(__x
); }
1407 template<typename _Pair
, typename
= typename
1408 std::enable_if
<std::is_constructible
<value_type
,
1409 _Pair
&&>::value
>::type
>
1412 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
1417 * @brief Inserts a std::pair into the %unordered_multimap.
1418 * @param __hint An iterator that serves as a hint as to where the
1419 * pair should be inserted.
1420 * @param __x Pair to be inserted (see std::make_pair for easy creation
1422 * @return An iterator that points to the element with key of
1423 * @a __x (may or may not be the %pair passed in).
1425 * Note that the first parameter is only a hint and can potentially
1426 * improve the performance of the insertion process. A bad hint would
1427 * cause no gains in efficiency.
1430 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1431 * for more on @a hinting.
1433 * Insertion requires amortized constant time.
1436 insert(const_iterator __hint
, const value_type
& __x
)
1437 { return _M_h
.insert(__hint
, __x
); }
1439 template<typename _Pair
, typename
= typename
1440 std::enable_if
<std::is_constructible
<value_type
,
1441 _Pair
&&>::value
>::type
>
1443 insert(const_iterator __hint
, _Pair
&& __x
)
1444 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
1448 * @brief A template function that attempts to insert a range of
1450 * @param __first Iterator pointing to the start of the range to be
1452 * @param __last Iterator pointing to the end of the range.
1454 * Complexity similar to that of the range constructor.
1456 template<typename _InputIterator
>
1458 insert(_InputIterator __first
, _InputIterator __last
)
1459 { _M_h
.insert(__first
, __last
); }
1462 * @brief Attempts to insert a list of elements into the
1463 * %unordered_multimap.
1464 * @param __l A std::initializer_list<value_type> of elements
1467 * Complexity similar to that of the range constructor.
1470 insert(initializer_list
<value_type
> __l
)
1471 { _M_h
.insert(__l
); }
1475 * @brief Erases an element from an %unordered_multimap.
1476 * @param __position An iterator pointing to the element to be erased.
1477 * @return An iterator pointing to the element immediately following
1478 * @a __position prior to the element being erased. If no such
1479 * element exists, end() is returned.
1481 * This function erases an element, pointed to by the given iterator,
1482 * from an %unordered_multimap.
1483 * Note that this function only erases the element, and that if the
1484 * element is itself a pointer, the pointed-to memory is not touched in
1485 * any way. Managing the pointer is the user's responsibility.
1488 erase(const_iterator __position
)
1489 { return _M_h
.erase(__position
); }
1493 erase(iterator __position
)
1494 { return _M_h
.erase(__position
); }
1498 * @brief Erases elements according to the provided key.
1499 * @param __x Key of elements to be erased.
1500 * @return The number of elements erased.
1502 * This function erases all the elements located by the given key from
1503 * an %unordered_multimap.
1504 * Note that this function only erases the element, and that if the
1505 * element is itself a pointer, the pointed-to memory is not touched in
1506 * any way. Managing the pointer is the user's responsibility.
1509 erase(const key_type
& __x
)
1510 { return _M_h
.erase(__x
); }
1513 * @brief Erases a [__first,__last) range of elements from an
1514 * %unordered_multimap.
1515 * @param __first Iterator pointing to the start of the range to be
1517 * @param __last Iterator pointing to the end of the range to
1519 * @return The iterator @a __last.
1521 * This function erases a sequence of elements from an
1522 * %unordered_multimap.
1523 * Note that this function only erases the elements, and that if
1524 * the element is itself a pointer, the pointed-to memory is not touched
1525 * in any way. Managing the pointer is the user's responsibility.
1528 erase(const_iterator __first
, const_iterator __last
)
1529 { return _M_h
.erase(__first
, __last
); }
1532 * Erases all elements in an %unordered_multimap.
1533 * Note that this function only erases the elements, and that if the
1534 * elements themselves are pointers, the pointed-to memory is not touched
1535 * in any way. Managing the pointer is the user's responsibility.
1542 * @brief Swaps data with another %unordered_multimap.
1543 * @param __x An %unordered_multimap of the same element and allocator
1546 * This exchanges the elements between two %unordered_multimap in
1548 * Note that the global std::swap() function is specialized such that
1549 * std::swap(m1,m2) will feed to this function.
1552 swap(unordered_multimap
& __x
)
1553 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1554 { _M_h
.swap(__x
._M_h
); }
1558 /// Returns the hash functor object with which the %unordered_multimap
1559 /// was constructed.
1561 hash_function() const
1562 { return _M_h
.hash_function(); }
1564 /// Returns the key comparison object with which the %unordered_multimap
1565 /// was constructed.
1568 { return _M_h
.key_eq(); }
1574 * @brief Tries to locate an element in an %unordered_multimap.
1575 * @param __x Key to be located.
1576 * @return Iterator pointing to sought-after element, or end() if not
1579 * This function takes a key and tries to locate the element with which
1580 * the key matches. If successful the function returns an iterator
1581 * pointing to the sought after element. If unsuccessful it returns the
1582 * past-the-end ( @c end() ) iterator.
1585 find(const key_type
& __x
)
1586 { return _M_h
.find(__x
); }
1589 find(const key_type
& __x
) const
1590 { return _M_h
.find(__x
); }
1594 * @brief Finds the number of elements.
1595 * @param __x Key to count.
1596 * @return Number of elements with specified key.
1599 count(const key_type
& __x
) const
1600 { return _M_h
.count(__x
); }
1604 * @brief Finds a subsequence matching given key.
1605 * @param __x Key to be located.
1606 * @return Pair of iterators that possibly points to the subsequence
1607 * matching given key.
1609 std::pair
<iterator
, iterator
>
1610 equal_range(const key_type
& __x
)
1611 { return _M_h
.equal_range(__x
); }
1613 std::pair
<const_iterator
, const_iterator
>
1614 equal_range(const key_type
& __x
) const
1615 { return _M_h
.equal_range(__x
); }
1618 // bucket interface.
1620 /// Returns the number of buckets of the %unordered_multimap.
1622 bucket_count() const noexcept
1623 { return _M_h
.bucket_count(); }
1625 /// Returns the maximum number of buckets of the %unordered_multimap.
1627 max_bucket_count() const noexcept
1628 { return _M_h
.max_bucket_count(); }
1631 * @brief Returns the number of elements in a given bucket.
1632 * @param __n A bucket index.
1633 * @return The number of elements in the bucket.
1636 bucket_size(size_type __n
) const
1637 { return _M_h
.bucket_size(__n
); }
1640 * @brief Returns the bucket index of a given element.
1641 * @param __key A key instance.
1642 * @return The key bucket index.
1645 bucket(const key_type
& __key
) const
1646 { return _M_h
.bucket(__key
); }
1649 * @brief Returns a read/write iterator pointing to the first bucket
1651 * @param __n The bucket index.
1652 * @return A read/write local iterator.
1655 begin(size_type __n
)
1656 { return _M_h
.begin(__n
); }
1660 * @brief Returns a read-only (constant) iterator pointing to the first
1662 * @param __n The bucket index.
1663 * @return A read-only local iterator.
1665 const_local_iterator
1666 begin(size_type __n
) const
1667 { return _M_h
.begin(__n
); }
1669 const_local_iterator
1670 cbegin(size_type __n
) const
1671 { return _M_h
.cbegin(__n
); }
1675 * @brief Returns a read/write iterator pointing to one past the last
1677 * @param __n The bucket index.
1678 * @return A read/write local iterator.
1682 { return _M_h
.end(__n
); }
1686 * @brief Returns a read-only (constant) iterator pointing to one past
1687 * the last bucket elements.
1688 * @param __n The bucket index.
1689 * @return A read-only local iterator.
1691 const_local_iterator
1692 end(size_type __n
) const
1693 { return _M_h
.end(__n
); }
1695 const_local_iterator
1696 cend(size_type __n
) const
1697 { return _M_h
.cend(__n
); }
1702 /// Returns the average number of elements per bucket.
1704 load_factor() const noexcept
1705 { return _M_h
.load_factor(); }
1707 /// Returns a positive number that the %unordered_multimap tries to keep
1708 /// the load factor less than or equal to.
1710 max_load_factor() const noexcept
1711 { return _M_h
.max_load_factor(); }
1714 * @brief Change the %unordered_multimap maximum load factor.
1715 * @param __z The new maximum load factor.
1718 max_load_factor(float __z
)
1719 { _M_h
.max_load_factor(__z
); }
1722 * @brief May rehash the %unordered_multimap.
1723 * @param __n The new number of buckets.
1725 * Rehash will occur only if the new number of buckets respect the
1726 * %unordered_multimap maximum load factor.
1729 rehash(size_type __n
)
1730 { _M_h
.rehash(__n
); }
1733 * @brief Prepare the %unordered_multimap for a specified number of
1735 * @param __n Number of elements required.
1737 * Same as rehash(ceil(n / max_load_factor())).
1740 reserve(size_type __n
)
1741 { _M_h
.reserve(__n
); }
1743 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1746 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1747 _Hash1
, _Pred1
, _Alloc1
>&,
1748 const unordered_multimap
<_Key1
, _Tp1
,
1749 _Hash1
, _Pred1
, _Alloc1
>&);
1752 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1754 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1755 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1756 noexcept(noexcept(__x
.swap(__y
)))
1759 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1761 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1762 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1763 noexcept(noexcept(__x
.swap(__y
)))
1766 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1768 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1769 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1770 { return __x
._M_h
._M_equal(__y
._M_h
); }
1772 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1774 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1775 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1776 { return !(__x
== __y
); }
1778 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1780 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1781 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1782 { return __x
._M_h
._M_equal(__y
._M_h
); }
1784 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1786 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1787 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1788 { return !(__x
== __y
); }
1790 _GLIBCXX_END_NAMESPACE_CONTAINER
1793 #endif /* _UNORDERED_MAP_H */