1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010-2014 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 /// Copy assignment operator.
227 operator=(const unordered_map
&) = default;
229 /// Move assignment operator.
231 operator=(unordered_map
&&) = default;
234 * @brief %Unordered_map list assignment operator.
235 * @param __l An initializer_list.
237 * This function fills an %unordered_map with copies of the elements in
238 * the initializer list @a __l.
240 * Note that the assignment completely changes the %unordered_map and
241 * that the resulting %unordered_map's size is the same as the number
242 * of elements assigned. Old data may be lost.
245 operator=(initializer_list
<value_type
> __l
)
251 /// Returns the allocator object with which the %unordered_map was
254 get_allocator() const noexcept
255 { return _M_h
.get_allocator(); }
257 // size and capacity:
259 /// Returns true if the %unordered_map is empty.
261 empty() const noexcept
262 { return _M_h
.empty(); }
264 /// Returns the size of the %unordered_map.
266 size() const noexcept
267 { return _M_h
.size(); }
269 /// Returns the maximum size of the %unordered_map.
271 max_size() const noexcept
272 { return _M_h
.max_size(); }
277 * Returns a read/write iterator that points to the first element in the
282 { return _M_h
.begin(); }
286 * Returns a read-only (constant) iterator that points to the first
287 * element in the %unordered_map.
290 begin() const noexcept
291 { return _M_h
.begin(); }
294 cbegin() const noexcept
295 { return _M_h
.begin(); }
299 * Returns a read/write iterator that points one past the last element in
300 * the %unordered_map.
304 { return _M_h
.end(); }
308 * Returns a read-only (constant) iterator that points one past the last
309 * element in the %unordered_map.
313 { return _M_h
.end(); }
316 cend() const noexcept
317 { return _M_h
.end(); }
323 * @brief Attempts to build and insert a std::pair into the %unordered_map.
325 * @param __args Arguments used to generate a new pair instance (see
326 * std::piecewise_contruct for passing arguments to each
327 * part of the pair constructor).
329 * @return A pair, of which the first element is an iterator that points
330 * to the possibly inserted pair, and the second is a bool that
331 * is true if the pair was actually inserted.
333 * This function attempts to build and insert a (key, value) %pair into
334 * the %unordered_map.
335 * An %unordered_map relies on unique keys and thus a %pair is only
336 * inserted if its first element (the key) is not already present in the
339 * Insertion requires amortized constant time.
341 template<typename
... _Args
>
342 std::pair
<iterator
, bool>
343 emplace(_Args
&&... __args
)
344 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
347 * @brief Attempts to build and insert a std::pair into the %unordered_map.
349 * @param __pos An iterator that serves as a hint as to where the pair
350 * should be inserted.
351 * @param __args Arguments used to generate a new pair instance (see
352 * std::piecewise_contruct for passing arguments to each
353 * part of the pair constructor).
354 * @return An iterator that points to the element with key of the
355 * std::pair built from @a __args (may or may not be that
358 * This function is not concerned about whether the insertion took place,
359 * and thus does not return a boolean like the single-argument emplace()
361 * Note that the first parameter is only a hint and can potentially
362 * improve the performance of the insertion process. A bad hint would
363 * cause no gains in efficiency.
366 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
367 * for more on @a hinting.
369 * Insertion requires amortized constant time.
371 template<typename
... _Args
>
373 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
374 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
378 * @brief Attempts to insert a std::pair into the %unordered_map.
380 * @param __x Pair to be inserted (see std::make_pair for easy
381 * creation of pairs).
383 * @return A pair, of which the first element is an iterator that
384 * points to the possibly inserted pair, and the second is
385 * a bool that is true if the pair was actually inserted.
387 * This function attempts to insert a (key, value) %pair into the
388 * %unordered_map. An %unordered_map relies on unique keys and thus a
389 * %pair is only inserted if its first element (the key) is not already
390 * present in the %unordered_map.
392 * Insertion requires amortized constant time.
394 std::pair
<iterator
, bool>
395 insert(const value_type
& __x
)
396 { return _M_h
.insert(__x
); }
398 template<typename _Pair
, typename
= typename
399 std::enable_if
<std::is_constructible
<value_type
,
400 _Pair
&&>::value
>::type
>
401 std::pair
<iterator
, bool>
403 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
408 * @brief Attempts to insert a std::pair into the %unordered_map.
409 * @param __hint An iterator that serves as a hint as to where the
410 * pair should be inserted.
411 * @param __x Pair to be inserted (see std::make_pair for easy creation
413 * @return An iterator that points to the element with key of
414 * @a __x (may or may not be the %pair passed in).
416 * This function is not concerned about whether the insertion took place,
417 * and thus does not return a boolean like the single-argument insert()
418 * does. Note that the first parameter is only a hint and can
419 * potentially improve the performance of the insertion process. A bad
420 * hint would cause no gains in efficiency.
423 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
424 * for more on @a hinting.
426 * Insertion requires amortized constant time.
429 insert(const_iterator __hint
, const value_type
& __x
)
430 { return _M_h
.insert(__hint
, __x
); }
432 template<typename _Pair
, typename
= typename
433 std::enable_if
<std::is_constructible
<value_type
,
434 _Pair
&&>::value
>::type
>
436 insert(const_iterator __hint
, _Pair
&& __x
)
437 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
441 * @brief A template function that attempts to insert a range of
443 * @param __first Iterator pointing to the start of the range to be
445 * @param __last Iterator pointing to the end of the range.
447 * Complexity similar to that of the range constructor.
449 template<typename _InputIterator
>
451 insert(_InputIterator __first
, _InputIterator __last
)
452 { _M_h
.insert(__first
, __last
); }
455 * @brief Attempts to insert a list of elements into the %unordered_map.
456 * @param __l A std::initializer_list<value_type> of elements
459 * Complexity similar to that of the range constructor.
462 insert(initializer_list
<value_type
> __l
)
463 { _M_h
.insert(__l
); }
467 * @brief Erases an element from an %unordered_map.
468 * @param __position An iterator pointing to the element to be erased.
469 * @return An iterator pointing to the element immediately following
470 * @a __position prior to the element being erased. If no such
471 * element exists, end() is returned.
473 * This function erases an element, pointed to by the given iterator,
474 * from an %unordered_map.
475 * Note that this function only erases the element, and that if the
476 * element is itself a pointer, the pointed-to memory is not touched in
477 * any way. Managing the pointer is the user's responsibility.
480 erase(const_iterator __position
)
481 { return _M_h
.erase(__position
); }
485 erase(iterator __position
)
486 { return _M_h
.erase(__position
); }
490 * @brief Erases elements according to the provided key.
491 * @param __x Key of element to be erased.
492 * @return The number of elements erased.
494 * This function erases all the elements located by the given key from
495 * an %unordered_map. For an %unordered_map the result of this function
496 * can only be 0 (not present) or 1 (present).
497 * Note that this function only erases the element, and that if the
498 * element is itself a pointer, the pointed-to memory is not touched in
499 * any way. Managing the pointer is the user's responsibility.
502 erase(const key_type
& __x
)
503 { return _M_h
.erase(__x
); }
506 * @brief Erases a [__first,__last) range of elements from an
508 * @param __first Iterator pointing to the start of the range to be
510 * @param __last Iterator pointing to the end of the range to
512 * @return The iterator @a __last.
514 * This function erases a sequence of elements from an %unordered_map.
515 * Note that this function only erases the elements, and that if
516 * the element is itself a pointer, the pointed-to memory is not touched
517 * in any way. Managing the pointer is the user's responsibility.
520 erase(const_iterator __first
, const_iterator __last
)
521 { return _M_h
.erase(__first
, __last
); }
524 * Erases all elements in an %unordered_map.
525 * Note that this function only erases the elements, and that if the
526 * elements themselves are pointers, the pointed-to memory is not touched
527 * in any way. Managing the pointer is the user's responsibility.
534 * @brief Swaps data with another %unordered_map.
535 * @param __x An %unordered_map of the same element and allocator
538 * This exchanges the elements between two %unordered_map in constant time.
539 * Note that the global std::swap() function is specialized such that
540 * std::swap(m1,m2) will feed to this function.
543 swap(unordered_map
& __x
)
544 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
545 { _M_h
.swap(__x
._M_h
); }
549 /// Returns the hash functor object with which the %unordered_map was
552 hash_function() const
553 { return _M_h
.hash_function(); }
555 /// Returns the key comparison object with which the %unordered_map was
559 { return _M_h
.key_eq(); }
565 * @brief Tries to locate an element in an %unordered_map.
566 * @param __x Key to be located.
567 * @return Iterator pointing to sought-after element, or end() if not
570 * This function takes a key and tries to locate the element with which
571 * the key matches. If successful the function returns an iterator
572 * pointing to the sought after element. If unsuccessful it returns the
573 * past-the-end ( @c end() ) iterator.
576 find(const key_type
& __x
)
577 { return _M_h
.find(__x
); }
580 find(const key_type
& __x
) const
581 { return _M_h
.find(__x
); }
585 * @brief Finds the number of elements.
586 * @param __x Key to count.
587 * @return Number of elements with specified key.
589 * This function only makes sense for %unordered_multimap; for
590 * %unordered_map the result will either be 0 (not present) or 1
594 count(const key_type
& __x
) const
595 { return _M_h
.count(__x
); }
599 * @brief Finds a subsequence matching given key.
600 * @param __x Key to be located.
601 * @return Pair of iterators that possibly points to the subsequence
602 * matching given key.
604 * This function probably only makes sense for %unordered_multimap.
606 std::pair
<iterator
, iterator
>
607 equal_range(const key_type
& __x
)
608 { return _M_h
.equal_range(__x
); }
610 std::pair
<const_iterator
, const_iterator
>
611 equal_range(const key_type
& __x
) const
612 { return _M_h
.equal_range(__x
); }
617 * @brief Subscript ( @c [] ) access to %unordered_map data.
618 * @param __k The key for which data should be retrieved.
619 * @return A reference to the data of the (key,data) %pair.
621 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
622 * data associated with the key specified in subscript. If the key does
623 * not exist, a pair with that key is created using default values, which
626 * Lookup requires constant time.
629 operator[](const key_type
& __k
)
630 { return _M_h
[__k
]; }
633 operator[](key_type
&& __k
)
634 { return _M_h
[std::move(__k
)]; }
639 * @brief Access to %unordered_map data.
640 * @param __k The key for which data should be retrieved.
641 * @return A reference to the data whose key is equal to @a __k, if
642 * such a data is present in the %unordered_map.
643 * @throw std::out_of_range If no such data is present.
646 at(const key_type
& __k
)
647 { return _M_h
.at(__k
); }
650 at(const key_type
& __k
) const
651 { return _M_h
.at(__k
); }
656 /// Returns the number of buckets of the %unordered_map.
658 bucket_count() const noexcept
659 { return _M_h
.bucket_count(); }
661 /// Returns the maximum number of buckets of the %unordered_map.
663 max_bucket_count() const noexcept
664 { return _M_h
.max_bucket_count(); }
667 * @brief Returns the number of elements in a given bucket.
668 * @param __n A bucket index.
669 * @return The number of elements in the bucket.
672 bucket_size(size_type __n
) const
673 { return _M_h
.bucket_size(__n
); }
676 * @brief Returns the bucket index of a given element.
677 * @param __key A key instance.
678 * @return The key bucket index.
681 bucket(const key_type
& __key
) const
682 { return _M_h
.bucket(__key
); }
685 * @brief Returns a read/write iterator pointing to the first bucket
687 * @param __n The bucket index.
688 * @return A read/write local iterator.
692 { return _M_h
.begin(__n
); }
696 * @brief Returns a read-only (constant) iterator pointing to the first
698 * @param __n The bucket index.
699 * @return A read-only local iterator.
702 begin(size_type __n
) const
703 { return _M_h
.begin(__n
); }
706 cbegin(size_type __n
) const
707 { return _M_h
.cbegin(__n
); }
711 * @brief Returns a read/write iterator pointing to one past the last
713 * @param __n The bucket index.
714 * @return A read/write local iterator.
718 { return _M_h
.end(__n
); }
722 * @brief Returns a read-only (constant) iterator pointing to one past
723 * the last bucket elements.
724 * @param __n The bucket index.
725 * @return A read-only local iterator.
728 end(size_type __n
) const
729 { return _M_h
.end(__n
); }
732 cend(size_type __n
) const
733 { return _M_h
.cend(__n
); }
738 /// Returns the average number of elements per bucket.
740 load_factor() const noexcept
741 { return _M_h
.load_factor(); }
743 /// Returns a positive number that the %unordered_map tries to keep the
744 /// load factor less than or equal to.
746 max_load_factor() const noexcept
747 { return _M_h
.max_load_factor(); }
750 * @brief Change the %unordered_map maximum load factor.
751 * @param __z The new maximum load factor.
754 max_load_factor(float __z
)
755 { _M_h
.max_load_factor(__z
); }
758 * @brief May rehash the %unordered_map.
759 * @param __n The new number of buckets.
761 * Rehash will occur only if the new number of buckets respect the
762 * %unordered_map maximum load factor.
765 rehash(size_type __n
)
766 { _M_h
.rehash(__n
); }
769 * @brief Prepare the %unordered_map for a specified number of
771 * @param __n Number of elements required.
773 * Same as rehash(ceil(n / max_load_factor())).
776 reserve(size_type __n
)
777 { _M_h
.reserve(__n
); }
779 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
782 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
783 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
787 * @brief A standard container composed of equivalent keys
788 * (possibly containing multiple of each key value) that associates
789 * values of another type with the keys.
791 * @ingroup unordered_associative_containers
793 * @tparam _Key Type of key objects.
794 * @tparam _Tp Type of mapped objects.
795 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
796 * @tparam _Pred Predicate function object type, defaults
797 * to equal_to<_Value>.
798 * @tparam _Alloc Allocator type, defaults to
799 * std::allocator<std::pair<const _Key, _Tp>>.
801 * Meets the requirements of a <a href="tables.html#65">container</a>, and
802 * <a href="tables.html#xx">unordered associative container</a>
804 * The resulting value type of the container is std::pair<const _Key, _Tp>.
806 * Base is _Hashtable, dispatched at compile time via template
807 * alias __ummap_hashtable.
809 template<class _Key
, class _Tp
,
810 class _Hash
= hash
<_Key
>,
811 class _Pred
= std::equal_to
<_Key
>,
812 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
813 class unordered_multimap
815 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
822 typedef typename
_Hashtable::key_type key_type
;
823 typedef typename
_Hashtable::value_type value_type
;
824 typedef typename
_Hashtable::mapped_type mapped_type
;
825 typedef typename
_Hashtable::hasher hasher
;
826 typedef typename
_Hashtable::key_equal key_equal
;
827 typedef typename
_Hashtable::allocator_type allocator_type
;
831 /// Iterator-related typedefs.
832 typedef typename
_Hashtable::pointer pointer
;
833 typedef typename
_Hashtable::const_pointer const_pointer
;
834 typedef typename
_Hashtable::reference reference
;
835 typedef typename
_Hashtable::const_reference const_reference
;
836 typedef typename
_Hashtable::iterator iterator
;
837 typedef typename
_Hashtable::const_iterator const_iterator
;
838 typedef typename
_Hashtable::local_iterator local_iterator
;
839 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
840 typedef typename
_Hashtable::size_type size_type
;
841 typedef typename
_Hashtable::difference_type difference_type
;
844 //construct/destroy/copy
846 /// Default constructor.
847 unordered_multimap() = default;
850 * @brief Default constructor creates no elements.
851 * @param __n Mnimal initial number of buckets.
852 * @param __hf A hash functor.
853 * @param __eql A key equality functor.
854 * @param __a An allocator object.
857 unordered_multimap(size_type __n
,
858 const hasher
& __hf
= hasher(),
859 const key_equal
& __eql
= key_equal(),
860 const allocator_type
& __a
= allocator_type())
861 : _M_h(__n
, __hf
, __eql
, __a
)
865 * @brief Builds an %unordered_multimap from a range.
866 * @param __first An input iterator.
867 * @param __last An input iterator.
868 * @param __n Minimal initial number of buckets.
869 * @param __hf A hash functor.
870 * @param __eql A key equality functor.
871 * @param __a An allocator object.
873 * Create an %unordered_multimap consisting of copies of the elements
874 * from [__first,__last). This is linear in N (where N is
875 * distance(__first,__last)).
877 template<typename _InputIterator
>
878 unordered_multimap(_InputIterator __first
, _InputIterator __last
,
880 const hasher
& __hf
= hasher(),
881 const key_equal
& __eql
= key_equal(),
882 const allocator_type
& __a
= allocator_type())
883 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
886 /// Copy constructor.
887 unordered_multimap(const unordered_multimap
&) = default;
889 /// Move constructor.
890 unordered_multimap(unordered_multimap
&&) = default;
893 * @brief Creates an %unordered_multimap with no elements.
894 * @param __a An allocator object.
897 unordered_multimap(const allocator_type
& __a
)
902 * @brief Copy constructor with allocator argument.
903 * @param __uset Input %unordered_multimap to copy.
904 * @param __a An allocator object.
906 unordered_multimap(const unordered_multimap
& __ummap
,
907 const allocator_type
& __a
)
908 : _M_h(__ummap
._M_h
, __a
)
912 * @brief Move constructor with allocator argument.
913 * @param __uset Input %unordered_multimap to move.
914 * @param __a An allocator object.
916 unordered_multimap(unordered_multimap
&& __ummap
,
917 const allocator_type
& __a
)
918 : _M_h(std::move(__ummap
._M_h
), __a
)
922 * @brief Builds an %unordered_multimap from an initializer_list.
923 * @param __l An initializer_list.
924 * @param __n Minimal initial number of buckets.
925 * @param __hf A hash functor.
926 * @param __eql A key equality functor.
927 * @param __a An allocator object.
929 * Create an %unordered_multimap consisting of copies of the elements in
930 * the list. This is linear in N (where N is @a __l.size()).
932 unordered_multimap(initializer_list
<value_type
> __l
,
934 const hasher
& __hf
= hasher(),
935 const key_equal
& __eql
= key_equal(),
936 const allocator_type
& __a
= allocator_type())
937 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
940 /// Copy assignment operator.
942 operator=(const unordered_multimap
&) = default;
944 /// Move assignment operator.
946 operator=(unordered_multimap
&&) = default;
949 * @brief %Unordered_multimap list assignment operator.
950 * @param __l An initializer_list.
952 * This function fills an %unordered_multimap with copies of the elements
953 * in the initializer list @a __l.
955 * Note that the assignment completely changes the %unordered_multimap
956 * and that the resulting %unordered_multimap's size is the same as the
957 * number of elements assigned. Old data may be lost.
960 operator=(initializer_list
<value_type
> __l
)
966 /// Returns the allocator object with which the %unordered_multimap was
969 get_allocator() const noexcept
970 { return _M_h
.get_allocator(); }
972 // size and capacity:
974 /// Returns true if the %unordered_multimap is empty.
976 empty() const noexcept
977 { return _M_h
.empty(); }
979 /// Returns the size of the %unordered_multimap.
981 size() const noexcept
982 { return _M_h
.size(); }
984 /// Returns the maximum size of the %unordered_multimap.
986 max_size() const noexcept
987 { return _M_h
.max_size(); }
992 * Returns a read/write iterator that points to the first element in the
993 * %unordered_multimap.
997 { return _M_h
.begin(); }
1001 * Returns a read-only (constant) iterator that points to the first
1002 * element in the %unordered_multimap.
1005 begin() const noexcept
1006 { return _M_h
.begin(); }
1009 cbegin() const noexcept
1010 { return _M_h
.begin(); }
1014 * Returns a read/write iterator that points one past the last element in
1015 * the %unordered_multimap.
1019 { return _M_h
.end(); }
1023 * Returns a read-only (constant) iterator that points one past the last
1024 * element in the %unordered_multimap.
1027 end() const noexcept
1028 { return _M_h
.end(); }
1031 cend() const noexcept
1032 { return _M_h
.end(); }
1038 * @brief Attempts to build and insert a std::pair into the
1039 * %unordered_multimap.
1041 * @param __args Arguments used to generate a new pair instance (see
1042 * std::piecewise_contruct for passing arguments to each
1043 * part of the pair constructor).
1045 * @return An iterator that points to the inserted pair.
1047 * This function attempts to build and insert a (key, value) %pair into
1048 * the %unordered_multimap.
1050 * Insertion requires amortized constant time.
1052 template<typename
... _Args
>
1054 emplace(_Args
&&... __args
)
1055 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1058 * @brief Attempts to build and insert a std::pair into the %unordered_multimap.
1060 * @param __pos An iterator that serves as a hint as to where the pair
1061 * should be inserted.
1062 * @param __args Arguments used to generate a new pair instance (see
1063 * std::piecewise_contruct for passing arguments to each
1064 * part of the pair constructor).
1065 * @return An iterator that points to the element with key of the
1066 * std::pair built from @a __args.
1068 * Note that the first parameter is only a hint and can potentially
1069 * improve the performance of the insertion process. A bad hint would
1070 * cause no gains in efficiency.
1073 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1074 * for more on @a hinting.
1076 * Insertion requires amortized constant time.
1078 template<typename
... _Args
>
1080 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1081 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1085 * @brief Inserts a std::pair into the %unordered_multimap.
1086 * @param __x Pair to be inserted (see std::make_pair for easy
1087 * creation of pairs).
1089 * @return An iterator that points to the inserted pair.
1091 * Insertion requires amortized constant time.
1094 insert(const value_type
& __x
)
1095 { return _M_h
.insert(__x
); }
1097 template<typename _Pair
, typename
= typename
1098 std::enable_if
<std::is_constructible
<value_type
,
1099 _Pair
&&>::value
>::type
>
1102 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
1107 * @brief Inserts a std::pair into the %unordered_multimap.
1108 * @param __hint An iterator that serves as a hint as to where the
1109 * pair should be inserted.
1110 * @param __x Pair to be inserted (see std::make_pair for easy creation
1112 * @return An iterator that points to the element with key of
1113 * @a __x (may or may not be the %pair passed in).
1115 * Note that the first parameter is only a hint and can potentially
1116 * improve the performance of the insertion process. A bad hint would
1117 * cause no gains in efficiency.
1120 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1121 * for more on @a hinting.
1123 * Insertion requires amortized constant time.
1126 insert(const_iterator __hint
, const value_type
& __x
)
1127 { return _M_h
.insert(__hint
, __x
); }
1129 template<typename _Pair
, typename
= typename
1130 std::enable_if
<std::is_constructible
<value_type
,
1131 _Pair
&&>::value
>::type
>
1133 insert(const_iterator __hint
, _Pair
&& __x
)
1134 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
1138 * @brief A template function that attempts to insert a range of
1140 * @param __first Iterator pointing to the start of the range to be
1142 * @param __last Iterator pointing to the end of the range.
1144 * Complexity similar to that of the range constructor.
1146 template<typename _InputIterator
>
1148 insert(_InputIterator __first
, _InputIterator __last
)
1149 { _M_h
.insert(__first
, __last
); }
1152 * @brief Attempts to insert a list of elements into the
1153 * %unordered_multimap.
1154 * @param __l A std::initializer_list<value_type> of elements
1157 * Complexity similar to that of the range constructor.
1160 insert(initializer_list
<value_type
> __l
)
1161 { _M_h
.insert(__l
); }
1165 * @brief Erases an element from an %unordered_multimap.
1166 * @param __position An iterator pointing to the element to be erased.
1167 * @return An iterator pointing to the element immediately following
1168 * @a __position prior to the element being erased. If no such
1169 * element exists, end() is returned.
1171 * This function erases an element, pointed to by the given iterator,
1172 * from an %unordered_multimap.
1173 * Note that this function only erases the element, and that if the
1174 * element is itself a pointer, the pointed-to memory is not touched in
1175 * any way. Managing the pointer is the user's responsibility.
1178 erase(const_iterator __position
)
1179 { return _M_h
.erase(__position
); }
1183 erase(iterator __position
)
1184 { return _M_h
.erase(__position
); }
1188 * @brief Erases elements according to the provided key.
1189 * @param __x Key of elements to be erased.
1190 * @return The number of elements erased.
1192 * This function erases all the elements located by the given key from
1193 * an %unordered_multimap.
1194 * Note that this function only erases the element, and that if the
1195 * element is itself a pointer, the pointed-to memory is not touched in
1196 * any way. Managing the pointer is the user's responsibility.
1199 erase(const key_type
& __x
)
1200 { return _M_h
.erase(__x
); }
1203 * @brief Erases a [__first,__last) range of elements from an
1204 * %unordered_multimap.
1205 * @param __first Iterator pointing to the start of the range to be
1207 * @param __last Iterator pointing to the end of the range to
1209 * @return The iterator @a __last.
1211 * This function erases a sequence of elements from an
1212 * %unordered_multimap.
1213 * Note that this function only erases the elements, and that if
1214 * the element is itself a pointer, the pointed-to memory is not touched
1215 * in any way. Managing the pointer is the user's responsibility.
1218 erase(const_iterator __first
, const_iterator __last
)
1219 { return _M_h
.erase(__first
, __last
); }
1222 * Erases all elements in an %unordered_multimap.
1223 * Note that this function only erases the elements, and that if the
1224 * elements themselves are pointers, the pointed-to memory is not touched
1225 * in any way. Managing the pointer is the user's responsibility.
1232 * @brief Swaps data with another %unordered_multimap.
1233 * @param __x An %unordered_multimap of the same element and allocator
1236 * This exchanges the elements between two %unordered_multimap in
1238 * Note that the global std::swap() function is specialized such that
1239 * std::swap(m1,m2) will feed to this function.
1242 swap(unordered_multimap
& __x
)
1243 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1244 { _M_h
.swap(__x
._M_h
); }
1248 /// Returns the hash functor object with which the %unordered_multimap
1249 /// was constructed.
1251 hash_function() const
1252 { return _M_h
.hash_function(); }
1254 /// Returns the key comparison object with which the %unordered_multimap
1255 /// was constructed.
1258 { return _M_h
.key_eq(); }
1264 * @brief Tries to locate an element in an %unordered_multimap.
1265 * @param __x Key to be located.
1266 * @return Iterator pointing to sought-after element, or end() if not
1269 * This function takes a key and tries to locate the element with which
1270 * the key matches. If successful the function returns an iterator
1271 * pointing to the sought after element. If unsuccessful it returns the
1272 * past-the-end ( @c end() ) iterator.
1275 find(const key_type
& __x
)
1276 { return _M_h
.find(__x
); }
1279 find(const key_type
& __x
) const
1280 { return _M_h
.find(__x
); }
1284 * @brief Finds the number of elements.
1285 * @param __x Key to count.
1286 * @return Number of elements with specified key.
1289 count(const key_type
& __x
) const
1290 { return _M_h
.count(__x
); }
1294 * @brief Finds a subsequence matching given key.
1295 * @param __x Key to be located.
1296 * @return Pair of iterators that possibly points to the subsequence
1297 * matching given key.
1299 std::pair
<iterator
, iterator
>
1300 equal_range(const key_type
& __x
)
1301 { return _M_h
.equal_range(__x
); }
1303 std::pair
<const_iterator
, const_iterator
>
1304 equal_range(const key_type
& __x
) const
1305 { return _M_h
.equal_range(__x
); }
1308 // bucket interface.
1310 /// Returns the number of buckets of the %unordered_multimap.
1312 bucket_count() const noexcept
1313 { return _M_h
.bucket_count(); }
1315 /// Returns the maximum number of buckets of the %unordered_multimap.
1317 max_bucket_count() const noexcept
1318 { return _M_h
.max_bucket_count(); }
1321 * @brief Returns the number of elements in a given bucket.
1322 * @param __n A bucket index.
1323 * @return The number of elements in the bucket.
1326 bucket_size(size_type __n
) const
1327 { return _M_h
.bucket_size(__n
); }
1330 * @brief Returns the bucket index of a given element.
1331 * @param __key A key instance.
1332 * @return The key bucket index.
1335 bucket(const key_type
& __key
) const
1336 { return _M_h
.bucket(__key
); }
1339 * @brief Returns a read/write iterator pointing to the first bucket
1341 * @param __n The bucket index.
1342 * @return A read/write local iterator.
1345 begin(size_type __n
)
1346 { return _M_h
.begin(__n
); }
1350 * @brief Returns a read-only (constant) iterator pointing to the first
1352 * @param __n The bucket index.
1353 * @return A read-only local iterator.
1355 const_local_iterator
1356 begin(size_type __n
) const
1357 { return _M_h
.begin(__n
); }
1359 const_local_iterator
1360 cbegin(size_type __n
) const
1361 { return _M_h
.cbegin(__n
); }
1365 * @brief Returns a read/write iterator pointing to one past the last
1367 * @param __n The bucket index.
1368 * @return A read/write local iterator.
1372 { return _M_h
.end(__n
); }
1376 * @brief Returns a read-only (constant) iterator pointing to one past
1377 * the last bucket elements.
1378 * @param __n The bucket index.
1379 * @return A read-only local iterator.
1381 const_local_iterator
1382 end(size_type __n
) const
1383 { return _M_h
.end(__n
); }
1385 const_local_iterator
1386 cend(size_type __n
) const
1387 { return _M_h
.cend(__n
); }
1392 /// Returns the average number of elements per bucket.
1394 load_factor() const noexcept
1395 { return _M_h
.load_factor(); }
1397 /// Returns a positive number that the %unordered_multimap tries to keep
1398 /// the load factor less than or equal to.
1400 max_load_factor() const noexcept
1401 { return _M_h
.max_load_factor(); }
1404 * @brief Change the %unordered_multimap maximum load factor.
1405 * @param __z The new maximum load factor.
1408 max_load_factor(float __z
)
1409 { _M_h
.max_load_factor(__z
); }
1412 * @brief May rehash the %unordered_multimap.
1413 * @param __n The new number of buckets.
1415 * Rehash will occur only if the new number of buckets respect the
1416 * %unordered_multimap maximum load factor.
1419 rehash(size_type __n
)
1420 { _M_h
.rehash(__n
); }
1423 * @brief Prepare the %unordered_multimap for a specified number of
1425 * @param __n Number of elements required.
1427 * Same as rehash(ceil(n / max_load_factor())).
1430 reserve(size_type __n
)
1431 { _M_h
.reserve(__n
); }
1433 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1436 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1437 _Hash1
, _Pred1
, _Alloc1
>&,
1438 const unordered_multimap
<_Key1
, _Tp1
,
1439 _Hash1
, _Pred1
, _Alloc1
>&);
1442 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1444 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1445 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1448 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1450 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1451 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1454 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1456 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1457 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1458 { return __x
._M_h
._M_equal(__y
._M_h
); }
1460 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1462 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1463 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1464 { return !(__x
== __y
); }
1466 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1468 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1469 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1470 { return __x
._M_h
._M_equal(__y
._M_h
); }
1472 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1474 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1475 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1476 { return !(__x
== __y
); }
1478 _GLIBCXX_END_NAMESPACE_CONTAINER
1481 #endif /* _UNORDERED_MAP_H */