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
132 * @brief Default constructor creates no elements.
133 * @param __n Initial number of buckets.
134 * @param __hf A hash functor.
135 * @param __eql A key equality functor.
136 * @param __a An allocator object.
139 unordered_map(size_type __n
= 10,
140 const hasher
& __hf
= hasher(),
141 const key_equal
& __eql
= key_equal(),
142 const allocator_type
& __a
= allocator_type())
143 : _M_h(__n
, __hf
, __eql
, __a
)
147 * @brief Builds an %unordered_map from a range.
148 * @param __first An input iterator.
149 * @param __last An input iterator.
150 * @param __n Minimal initial number of buckets.
151 * @param __hf A hash functor.
152 * @param __eql A key equality functor.
153 * @param __a An allocator object.
155 * Create an %unordered_map consisting of copies of the elements from
156 * [__first,__last). This is linear in N (where N is
157 * distance(__first,__last)).
159 template<typename _InputIterator
>
160 unordered_map(_InputIterator __f
, _InputIterator __l
,
162 const hasher
& __hf
= hasher(),
163 const key_equal
& __eql
= key_equal(),
164 const allocator_type
& __a
= allocator_type())
165 : _M_h(__f
, __l
, __n
, __hf
, __eql
, __a
)
168 /// Copy constructor.
169 unordered_map(const unordered_map
&) = default;
171 /// Move constructor.
172 unordered_map(unordered_map
&&) = default;
175 * @brief Creates an %unordered_map with no elements.
176 * @param __a An allocator object.
179 unordered_map(const allocator_type
& __a
)
184 * @brief Copy constructor with allocator argument.
185 * @param __uset Input %unordered_map to copy.
186 * @param __a An allocator object.
188 unordered_map(const unordered_map
& __umap
,
189 const allocator_type
& __a
)
190 : _M_h(__umap
._M_h
, __a
)
194 * @brief Move constructor with allocator argument.
195 * @param __uset Input %unordered_map to move.
196 * @param __a An allocator object.
198 unordered_map(unordered_map
&& __umap
,
199 const allocator_type
& __a
)
200 : _M_h(std::move(__umap
._M_h
), __a
)
204 * @brief Builds an %unordered_map from an initializer_list.
205 * @param __l An initializer_list.
206 * @param __n Minimal initial number of buckets.
207 * @param __hf A hash functor.
208 * @param __eql A key equality functor.
209 * @param __a An allocator object.
211 * Create an %unordered_map consisting of copies of the elements in the
212 * list. This is linear in N (where N is @a __l.size()).
214 unordered_map(initializer_list
<value_type
> __l
,
216 const hasher
& __hf
= hasher(),
217 const key_equal
& __eql
= key_equal(),
218 const allocator_type
& __a
= allocator_type())
219 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
222 /// Copy assignment operator.
224 operator=(const unordered_map
&) = default;
226 /// Move assignment operator.
228 operator=(unordered_map
&&) = default;
231 * @brief %Unordered_map list assignment operator.
232 * @param __l An initializer_list.
234 * This function fills an %unordered_map with copies of the elements in
235 * the initializer list @a __l.
237 * Note that the assignment completely changes the %unordered_map and
238 * that the resulting %unordered_map's size is the same as the number
239 * of elements assigned. Old data may be lost.
242 operator=(initializer_list
<value_type
> __l
)
248 /// Returns the allocator object with which the %unordered_map was
251 get_allocator() const noexcept
252 { return _M_h
.get_allocator(); }
254 // size and capacity:
256 /// Returns true if the %unordered_map is empty.
258 empty() const noexcept
259 { return _M_h
.empty(); }
261 /// Returns the size of the %unordered_map.
263 size() const noexcept
264 { return _M_h
.size(); }
266 /// Returns the maximum size of the %unordered_map.
268 max_size() const noexcept
269 { return _M_h
.max_size(); }
274 * Returns a read/write iterator that points to the first element in the
279 { return _M_h
.begin(); }
283 * Returns a read-only (constant) iterator that points to the first
284 * element in the %unordered_map.
287 begin() const noexcept
288 { return _M_h
.begin(); }
291 cbegin() const noexcept
292 { return _M_h
.begin(); }
296 * Returns a read/write iterator that points one past the last element in
297 * the %unordered_map.
301 { return _M_h
.end(); }
305 * Returns a read-only (constant) iterator that points one past the last
306 * element in the %unordered_map.
310 { return _M_h
.end(); }
313 cend() const noexcept
314 { return _M_h
.end(); }
320 * @brief Attempts to build and insert a std::pair into the %unordered_map.
322 * @param __args Arguments used to generate a new pair instance (see
323 * std::piecewise_contruct for passing arguments to each
324 * part of the pair constructor).
326 * @return A pair, of which the first element is an iterator that points
327 * to the possibly inserted pair, and the second is a bool that
328 * is true if the pair was actually inserted.
330 * This function attempts to build and insert a (key, value) %pair into
331 * the %unordered_map.
332 * An %unordered_map relies on unique keys and thus a %pair is only
333 * inserted if its first element (the key) is not already present in the
336 * Insertion requires amortized constant time.
338 template<typename
... _Args
>
339 std::pair
<iterator
, bool>
340 emplace(_Args
&&... __args
)
341 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
344 * @brief Attempts to build and insert a std::pair into the %unordered_map.
346 * @param __pos An iterator that serves as a hint as to where the pair
347 * should be inserted.
348 * @param __args Arguments used to generate a new pair instance (see
349 * std::piecewise_contruct for passing arguments to each
350 * part of the pair constructor).
351 * @return An iterator that points to the element with key of the
352 * std::pair built from @a __args (may or may not be that
355 * This function is not concerned about whether the insertion took place,
356 * and thus does not return a boolean like the single-argument emplace()
358 * Note that the first parameter is only a hint and can potentially
359 * improve the performance of the insertion process. A bad hint would
360 * cause no gains in efficiency.
363 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
364 * for more on @a hinting.
366 * Insertion requires amortized constant time.
368 template<typename
... _Args
>
370 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
371 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
375 * @brief Attempts to insert a std::pair into the %unordered_map.
377 * @param __x Pair to be inserted (see std::make_pair for easy
378 * creation of pairs).
380 * @return A pair, of which the first element is an iterator that
381 * points to the possibly inserted pair, and the second is
382 * a bool that is true if the pair was actually inserted.
384 * This function attempts to insert a (key, value) %pair into the
385 * %unordered_map. An %unordered_map relies on unique keys and thus a
386 * %pair is only inserted if its first element (the key) is not already
387 * present in the %unordered_map.
389 * Insertion requires amortized constant time.
391 std::pair
<iterator
, bool>
392 insert(const value_type
& __x
)
393 { return _M_h
.insert(__x
); }
395 template<typename _Pair
, typename
= typename
396 std::enable_if
<std::is_constructible
<value_type
,
397 _Pair
&&>::value
>::type
>
398 std::pair
<iterator
, bool>
400 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
405 * @brief Attempts to insert a std::pair into the %unordered_map.
406 * @param __hint An iterator that serves as a hint as to where the
407 * pair should be inserted.
408 * @param __x Pair to be inserted (see std::make_pair for easy creation
410 * @return An iterator that points to the element with key of
411 * @a __x (may or may not be the %pair passed in).
413 * This function is not concerned about whether the insertion took place,
414 * and thus does not return a boolean like the single-argument insert()
415 * does. Note that the first parameter is only a hint and can
416 * potentially improve the performance of the insertion process. A bad
417 * hint would cause no gains in efficiency.
420 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
421 * for more on @a hinting.
423 * Insertion requires amortized constant time.
426 insert(const_iterator __hint
, const value_type
& __x
)
427 { return _M_h
.insert(__hint
, __x
); }
429 template<typename _Pair
, typename
= typename
430 std::enable_if
<std::is_constructible
<value_type
,
431 _Pair
&&>::value
>::type
>
433 insert(const_iterator __hint
, _Pair
&& __x
)
434 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
438 * @brief A template function that attempts to insert a range of
440 * @param __first Iterator pointing to the start of the range to be
442 * @param __last Iterator pointing to the end of the range.
444 * Complexity similar to that of the range constructor.
446 template<typename _InputIterator
>
448 insert(_InputIterator __first
, _InputIterator __last
)
449 { _M_h
.insert(__first
, __last
); }
452 * @brief Attempts to insert a list of elements into the %unordered_map.
453 * @param __l A std::initializer_list<value_type> of elements
456 * Complexity similar to that of the range constructor.
459 insert(initializer_list
<value_type
> __l
)
460 { _M_h
.insert(__l
); }
464 * @brief Erases an element from an %unordered_map.
465 * @param __position An iterator pointing to the element to be erased.
466 * @return An iterator pointing to the element immediately following
467 * @a __position prior to the element being erased. If no such
468 * element exists, end() is returned.
470 * This function erases an element, pointed to by the given iterator,
471 * from an %unordered_map.
472 * Note that this function only erases the element, and that if the
473 * element is itself a pointer, the pointed-to memory is not touched in
474 * any way. Managing the pointer is the user's responsibility.
477 erase(const_iterator __position
)
478 { return _M_h
.erase(__position
); }
483 { return _M_h
.erase(__it
); }
487 * @brief Erases elements according to the provided key.
488 * @param __x Key of element to be erased.
489 * @return The number of elements erased.
491 * This function erases all the elements located by the given key from
492 * an %unordered_map. For an %unordered_map the result of this function
493 * can only be 0 (not present) or 1 (present).
494 * Note that this function only erases the element, and that if the
495 * element is itself a pointer, the pointed-to memory is not touched in
496 * any way. Managing the pointer is the user's responsibility.
499 erase(const key_type
& __x
)
500 { return _M_h
.erase(__x
); }
503 * @brief Erases a [__first,__last) range of elements from an
505 * @param __first Iterator pointing to the start of the range to be
507 * @param __last Iterator pointing to the end of the range to
509 * @return The iterator @a __last.
511 * This function erases a sequence of elements from an %unordered_map.
512 * Note that this function only erases the elements, and that if
513 * the element is itself a pointer, the pointed-to memory is not touched
514 * in any way. Managing the pointer is the user's responsibility.
517 erase(const_iterator __first
, const_iterator __last
)
518 { return _M_h
.erase(__first
, __last
); }
521 * Erases all elements in an %unordered_map.
522 * Note that this function only erases the elements, and that if the
523 * elements themselves are pointers, the pointed-to memory is not touched
524 * in any way. Managing the pointer is the user's responsibility.
531 * @brief Swaps data with another %unordered_map.
532 * @param __x An %unordered_map of the same element and allocator
535 * This exchanges the elements between two %unordered_map in constant time.
536 * Note that the global std::swap() function is specialized such that
537 * std::swap(m1,m2) will feed to this function.
540 swap(unordered_map
& __x
)
541 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
542 { _M_h
.swap(__x
._M_h
); }
546 /// Returns the hash functor object with which the %unordered_map was
549 hash_function() const
550 { return _M_h
.hash_function(); }
552 /// Returns the key comparison object with which the %unordered_map was
556 { return _M_h
.key_eq(); }
562 * @brief Tries to locate an element in an %unordered_map.
563 * @param __x Key to be located.
564 * @return Iterator pointing to sought-after element, or end() if not
567 * This function takes a key and tries to locate the element with which
568 * the key matches. If successful the function returns an iterator
569 * pointing to the sought after element. If unsuccessful it returns the
570 * past-the-end ( @c end() ) iterator.
573 find(const key_type
& __x
)
574 { return _M_h
.find(__x
); }
577 find(const key_type
& __x
) const
578 { return _M_h
.find(__x
); }
582 * @brief Finds the number of elements.
583 * @param __x Key to count.
584 * @return Number of elements with specified key.
586 * This function only makes sense for %unordered_multimap; for
587 * %unordered_map the result will either be 0 (not present) or 1
591 count(const key_type
& __x
) const
592 { return _M_h
.count(__x
); }
596 * @brief Finds a subsequence matching given key.
597 * @param __x Key to be located.
598 * @return Pair of iterators that possibly points to the subsequence
599 * matching given key.
601 * This function probably only makes sense for %unordered_multimap.
603 std::pair
<iterator
, iterator
>
604 equal_range(const key_type
& __x
)
605 { return _M_h
.equal_range(__x
); }
607 std::pair
<const_iterator
, const_iterator
>
608 equal_range(const key_type
& __x
) const
609 { return _M_h
.equal_range(__x
); }
614 * @brief Subscript ( @c [] ) access to %unordered_map data.
615 * @param __k The key for which data should be retrieved.
616 * @return A reference to the data of the (key,data) %pair.
618 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
619 * data associated with the key specified in subscript. If the key does
620 * not exist, a pair with that key is created using default values, which
623 * Lookup requires constant time.
626 operator[](const key_type
& __k
)
627 { return _M_h
[__k
]; }
630 operator[](key_type
&& __k
)
631 { return _M_h
[std::move(__k
)]; }
636 * @brief Access to %unordered_map data.
637 * @param __k The key for which data should be retrieved.
638 * @return A reference to the data whose key is equal to @a __k, if
639 * such a data is present in the %unordered_map.
640 * @throw std::out_of_range If no such data is present.
643 at(const key_type
& __k
)
644 { return _M_h
.at(__k
); }
647 at(const key_type
& __k
) const
648 { return _M_h
.at(__k
); }
653 /// Returns the number of buckets of the %unordered_map.
655 bucket_count() const noexcept
656 { return _M_h
.bucket_count(); }
658 /// Returns the maximum number of buckets of the %unordered_map.
660 max_bucket_count() const noexcept
661 { return _M_h
.max_bucket_count(); }
664 * @brief Returns the number of elements in a given bucket.
665 * @param __n A bucket index.
666 * @return The number of elements in the bucket.
669 bucket_size(size_type __n
) const
670 { return _M_h
.bucket_size(__n
); }
673 * @brief Returns the bucket index of a given element.
674 * @param __key A key instance.
675 * @return The key bucket index.
678 bucket(const key_type
& __key
) const
679 { return _M_h
.bucket(__key
); }
682 * @brief Returns a read/write iterator pointing to the first bucket
684 * @param __n The bucket index.
685 * @return A read/write local iterator.
689 { return _M_h
.begin(__n
); }
693 * @brief Returns a read-only (constant) iterator pointing to the first
695 * @param __n The bucket index.
696 * @return A read-only local iterator.
699 begin(size_type __n
) const
700 { return _M_h
.begin(__n
); }
703 cbegin(size_type __n
) const
704 { return _M_h
.cbegin(__n
); }
708 * @brief Returns a read/write iterator pointing to one past the last
710 * @param __n The bucket index.
711 * @return A read/write local iterator.
715 { return _M_h
.end(__n
); }
719 * @brief Returns a read-only (constant) iterator pointing to one past
720 * the last bucket elements.
721 * @param __n The bucket index.
722 * @return A read-only local iterator.
725 end(size_type __n
) const
726 { return _M_h
.end(__n
); }
729 cend(size_type __n
) const
730 { return _M_h
.cend(__n
); }
735 /// Returns the average number of elements per bucket.
737 load_factor() const noexcept
738 { return _M_h
.load_factor(); }
740 /// Returns a positive number that the %unordered_map tries to keep the
741 /// load factor less than or equal to.
743 max_load_factor() const noexcept
744 { return _M_h
.max_load_factor(); }
747 * @brief Change the %unordered_map maximum load factor.
748 * @param __z The new maximum load factor.
751 max_load_factor(float __z
)
752 { _M_h
.max_load_factor(__z
); }
755 * @brief May rehash the %unordered_map.
756 * @param __n The new number of buckets.
758 * Rehash will occur only if the new number of buckets respect the
759 * %unordered_map maximum load factor.
762 rehash(size_type __n
)
763 { _M_h
.rehash(__n
); }
766 * @brief Prepare the %unordered_map for a specified number of
768 * @param __n Number of elements required.
770 * Same as rehash(ceil(n / max_load_factor())).
773 reserve(size_type __n
)
774 { _M_h
.reserve(__n
); }
776 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
779 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
780 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
784 * @brief A standard container composed of equivalent keys
785 * (possibly containing multiple of each key value) that associates
786 * values of another type with the keys.
788 * @ingroup unordered_associative_containers
790 * @tparam _Key Type of key objects.
791 * @tparam _Tp Type of mapped objects.
792 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
793 * @tparam _Pred Predicate function object type, defaults
794 * to equal_to<_Value>.
795 * @tparam _Alloc Allocator type, defaults to
796 * std::allocator<std::pair<const _Key, _Tp>>.
798 * Meets the requirements of a <a href="tables.html#65">container</a>, and
799 * <a href="tables.html#xx">unordered associative container</a>
801 * The resulting value type of the container is std::pair<const _Key, _Tp>.
803 * Base is _Hashtable, dispatched at compile time via template
804 * alias __ummap_hashtable.
806 template<class _Key
, class _Tp
,
807 class _Hash
= hash
<_Key
>,
808 class _Pred
= std::equal_to
<_Key
>,
809 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
810 class unordered_multimap
812 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
819 typedef typename
_Hashtable::key_type key_type
;
820 typedef typename
_Hashtable::value_type value_type
;
821 typedef typename
_Hashtable::mapped_type mapped_type
;
822 typedef typename
_Hashtable::hasher hasher
;
823 typedef typename
_Hashtable::key_equal key_equal
;
824 typedef typename
_Hashtable::allocator_type allocator_type
;
828 /// Iterator-related typedefs.
829 typedef typename
_Hashtable::pointer pointer
;
830 typedef typename
_Hashtable::const_pointer const_pointer
;
831 typedef typename
_Hashtable::reference reference
;
832 typedef typename
_Hashtable::const_reference const_reference
;
833 typedef typename
_Hashtable::iterator iterator
;
834 typedef typename
_Hashtable::const_iterator const_iterator
;
835 typedef typename
_Hashtable::local_iterator local_iterator
;
836 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
837 typedef typename
_Hashtable::size_type size_type
;
838 typedef typename
_Hashtable::difference_type difference_type
;
841 //construct/destroy/copy
844 * @brief Default constructor creates no elements.
845 * @param __n Initial number of buckets.
846 * @param __hf A hash functor.
847 * @param __eql A key equality functor.
848 * @param __a An allocator object.
851 unordered_multimap(size_type __n
= 10,
852 const hasher
& __hf
= hasher(),
853 const key_equal
& __eql
= key_equal(),
854 const allocator_type
& __a
= allocator_type())
855 : _M_h(__n
, __hf
, __eql
, __a
)
859 * @brief Builds an %unordered_multimap from a range.
860 * @param __first An input iterator.
861 * @param __last An input iterator.
862 * @param __n Minimal initial number of buckets.
863 * @param __hf A hash functor.
864 * @param __eql A key equality functor.
865 * @param __a An allocator object.
867 * Create an %unordered_multimap consisting of copies of the elements
868 * from [__first,__last). This is linear in N (where N is
869 * distance(__first,__last)).
871 template<typename _InputIterator
>
872 unordered_multimap(_InputIterator __f
, _InputIterator __l
,
874 const hasher
& __hf
= hasher(),
875 const key_equal
& __eql
= key_equal(),
876 const allocator_type
& __a
= allocator_type())
877 : _M_h(__f
, __l
, __n
, __hf
, __eql
, __a
)
880 /// Copy constructor.
881 unordered_multimap(const unordered_multimap
&) = default;
883 /// Move constructor.
884 unordered_multimap(unordered_multimap
&&) = default;
887 * @brief Creates an %unordered_multimap with no elements.
888 * @param __a An allocator object.
891 unordered_multimap(const allocator_type
& __a
)
896 * @brief Copy constructor with allocator argument.
897 * @param __uset Input %unordered_multimap to copy.
898 * @param __a An allocator object.
900 unordered_multimap(const unordered_multimap
& __ummap
,
901 const allocator_type
& __a
)
902 : _M_h(__ummap
._M_h
, __a
)
906 * @brief Move constructor with allocator argument.
907 * @param __uset Input %unordered_multimap to move.
908 * @param __a An allocator object.
910 unordered_multimap(unordered_multimap
&& __ummap
,
911 const allocator_type
& __a
)
912 : _M_h(std::move(__ummap
._M_h
), __a
)
916 * @brief Builds an %unordered_multimap from an initializer_list.
917 * @param __l An initializer_list.
918 * @param __n Minimal initial number of buckets.
919 * @param __hf A hash functor.
920 * @param __eql A key equality functor.
921 * @param __a An allocator object.
923 * Create an %unordered_multimap consisting of copies of the elements in
924 * the list. This is linear in N (where N is @a __l.size()).
926 unordered_multimap(initializer_list
<value_type
> __l
,
928 const hasher
& __hf
= hasher(),
929 const key_equal
& __eql
= key_equal(),
930 const allocator_type
& __a
= allocator_type())
931 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
934 /// Copy assignment operator.
936 operator=(const unordered_multimap
&) = default;
938 /// Move assignment operator.
940 operator=(unordered_multimap
&&) = default;
943 * @brief %Unordered_multimap list assignment operator.
944 * @param __l An initializer_list.
946 * This function fills an %unordered_multimap with copies of the elements
947 * in the initializer list @a __l.
949 * Note that the assignment completely changes the %unordered_multimap
950 * and that the resulting %unordered_multimap's size is the same as the
951 * number of elements assigned. Old data may be lost.
954 operator=(initializer_list
<value_type
> __l
)
960 /// Returns the allocator object with which the %unordered_multimap was
963 get_allocator() const noexcept
964 { return _M_h
.get_allocator(); }
966 // size and capacity:
968 /// Returns true if the %unordered_multimap is empty.
970 empty() const noexcept
971 { return _M_h
.empty(); }
973 /// Returns the size of the %unordered_multimap.
975 size() const noexcept
976 { return _M_h
.size(); }
978 /// Returns the maximum size of the %unordered_multimap.
980 max_size() const noexcept
981 { return _M_h
.max_size(); }
986 * Returns a read/write iterator that points to the first element in the
987 * %unordered_multimap.
991 { return _M_h
.begin(); }
995 * Returns a read-only (constant) iterator that points to the first
996 * element in the %unordered_multimap.
999 begin() const noexcept
1000 { return _M_h
.begin(); }
1003 cbegin() const noexcept
1004 { return _M_h
.begin(); }
1008 * Returns a read/write iterator that points one past the last element in
1009 * the %unordered_multimap.
1013 { return _M_h
.end(); }
1017 * Returns a read-only (constant) iterator that points one past the last
1018 * element in the %unordered_multimap.
1021 end() const noexcept
1022 { return _M_h
.end(); }
1025 cend() const noexcept
1026 { return _M_h
.end(); }
1032 * @brief Attempts to build and insert a std::pair into the
1033 * %unordered_multimap.
1035 * @param __args Arguments used to generate a new pair instance (see
1036 * std::piecewise_contruct for passing arguments to each
1037 * part of the pair constructor).
1039 * @return An iterator that points to the inserted pair.
1041 * This function attempts to build and insert a (key, value) %pair into
1042 * the %unordered_multimap.
1044 * Insertion requires amortized constant time.
1046 template<typename
... _Args
>
1048 emplace(_Args
&&... __args
)
1049 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1052 * @brief Attempts to build and insert a std::pair into the %unordered_multimap.
1054 * @param __pos An iterator that serves as a hint as to where the pair
1055 * should be inserted.
1056 * @param __args Arguments used to generate a new pair instance (see
1057 * std::piecewise_contruct for passing arguments to each
1058 * part of the pair constructor).
1059 * @return An iterator that points to the element with key of the
1060 * std::pair built from @a __args.
1062 * Note that the first parameter is only a hint and can potentially
1063 * improve the performance of the insertion process. A bad hint would
1064 * cause no gains in efficiency.
1067 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
1068 * for more on @a hinting.
1070 * Insertion requires amortized constant time.
1072 template<typename
... _Args
>
1074 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1075 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1079 * @brief Inserts a std::pair into the %unordered_multimap.
1080 * @param __x Pair to be inserted (see std::make_pair for easy
1081 * creation of pairs).
1083 * @return An iterator that points to the inserted pair.
1085 * Insertion requires amortized constant time.
1088 insert(const value_type
& __x
)
1089 { return _M_h
.insert(__x
); }
1091 template<typename _Pair
, typename
= typename
1092 std::enable_if
<std::is_constructible
<value_type
,
1093 _Pair
&&>::value
>::type
>
1096 { return _M_h
.insert(std::forward
<_Pair
>(__x
)); }
1101 * @brief Inserts a std::pair into the %unordered_multimap.
1102 * @param __hint An iterator that serves as a hint as to where the
1103 * pair should be inserted.
1104 * @param __x Pair to be inserted (see std::make_pair for easy creation
1106 * @return An iterator that points to the element with key of
1107 * @a __x (may or may not be the %pair passed in).
1109 * Note that the first parameter is only a hint and can potentially
1110 * improve the performance of the insertion process. A bad hint would
1111 * cause no gains in efficiency.
1114 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
1115 * for more on @a hinting.
1117 * Insertion requires amortized constant time.
1120 insert(const_iterator __hint
, const value_type
& __x
)
1121 { return _M_h
.insert(__hint
, __x
); }
1123 template<typename _Pair
, typename
= typename
1124 std::enable_if
<std::is_constructible
<value_type
,
1125 _Pair
&&>::value
>::type
>
1127 insert(const_iterator __hint
, _Pair
&& __x
)
1128 { return _M_h
.insert(__hint
, std::forward
<_Pair
>(__x
)); }
1132 * @brief A template function that attempts to insert a range of
1134 * @param __first Iterator pointing to the start of the range to be
1136 * @param __last Iterator pointing to the end of the range.
1138 * Complexity similar to that of the range constructor.
1140 template<typename _InputIterator
>
1142 insert(_InputIterator __first
, _InputIterator __last
)
1143 { _M_h
.insert(__first
, __last
); }
1146 * @brief Attempts to insert a list of elements into the
1147 * %unordered_multimap.
1148 * @param __l A std::initializer_list<value_type> of elements
1151 * Complexity similar to that of the range constructor.
1154 insert(initializer_list
<value_type
> __l
)
1155 { _M_h
.insert(__l
); }
1159 * @brief Erases an element from an %unordered_multimap.
1160 * @param __position An iterator pointing to the element to be erased.
1161 * @return An iterator pointing to the element immediately following
1162 * @a __position prior to the element being erased. If no such
1163 * element exists, end() is returned.
1165 * This function erases an element, pointed to by the given iterator,
1166 * from an %unordered_multimap.
1167 * Note that this function only erases the element, and that if the
1168 * element is itself a pointer, the pointed-to memory is not touched in
1169 * any way. Managing the pointer is the user's responsibility.
1172 erase(const_iterator __position
)
1173 { return _M_h
.erase(__position
); }
1177 erase(iterator __it
)
1178 { return _M_h
.erase(__it
); }
1182 * @brief Erases elements according to the provided key.
1183 * @param __x Key of elements to be erased.
1184 * @return The number of elements erased.
1186 * This function erases all the elements located by the given key from
1187 * an %unordered_multimap.
1188 * Note that this function only erases the element, and that if the
1189 * element is itself a pointer, the pointed-to memory is not touched in
1190 * any way. Managing the pointer is the user's responsibility.
1193 erase(const key_type
& __x
)
1194 { return _M_h
.erase(__x
); }
1197 * @brief Erases a [__first,__last) range of elements from an
1198 * %unordered_multimap.
1199 * @param __first Iterator pointing to the start of the range to be
1201 * @param __last Iterator pointing to the end of the range to
1203 * @return The iterator @a __last.
1205 * This function erases a sequence of elements from an
1206 * %unordered_multimap.
1207 * Note that this function only erases the elements, and that if
1208 * the element is itself a pointer, the pointed-to memory is not touched
1209 * in any way. Managing the pointer is the user's responsibility.
1212 erase(const_iterator __first
, const_iterator __last
)
1213 { return _M_h
.erase(__first
, __last
); }
1216 * Erases all elements in an %unordered_multimap.
1217 * Note that this function only erases the elements, and that if the
1218 * elements themselves are pointers, the pointed-to memory is not touched
1219 * in any way. Managing the pointer is the user's responsibility.
1226 * @brief Swaps data with another %unordered_multimap.
1227 * @param __x An %unordered_multimap of the same element and allocator
1230 * This exchanges the elements between two %unordered_multimap in
1232 * Note that the global std::swap() function is specialized such that
1233 * std::swap(m1,m2) will feed to this function.
1236 swap(unordered_multimap
& __x
)
1237 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1238 { _M_h
.swap(__x
._M_h
); }
1242 /// Returns the hash functor object with which the %unordered_multimap
1243 /// was constructed.
1245 hash_function() const
1246 { return _M_h
.hash_function(); }
1248 /// Returns the key comparison object with which the %unordered_multimap
1249 /// was constructed.
1252 { return _M_h
.key_eq(); }
1258 * @brief Tries to locate an element in an %unordered_multimap.
1259 * @param __x Key to be located.
1260 * @return Iterator pointing to sought-after element, or end() if not
1263 * This function takes a key and tries to locate the element with which
1264 * the key matches. If successful the function returns an iterator
1265 * pointing to the sought after element. If unsuccessful it returns the
1266 * past-the-end ( @c end() ) iterator.
1269 find(const key_type
& __x
)
1270 { return _M_h
.find(__x
); }
1273 find(const key_type
& __x
) const
1274 { return _M_h
.find(__x
); }
1278 * @brief Finds the number of elements.
1279 * @param __x Key to count.
1280 * @return Number of elements with specified key.
1283 count(const key_type
& __x
) const
1284 { return _M_h
.count(__x
); }
1288 * @brief Finds a subsequence matching given key.
1289 * @param __x Key to be located.
1290 * @return Pair of iterators that possibly points to the subsequence
1291 * matching given key.
1293 std::pair
<iterator
, iterator
>
1294 equal_range(const key_type
& __x
)
1295 { return _M_h
.equal_range(__x
); }
1297 std::pair
<const_iterator
, const_iterator
>
1298 equal_range(const key_type
& __x
) const
1299 { return _M_h
.equal_range(__x
); }
1302 // bucket interface.
1304 /// Returns the number of buckets of the %unordered_multimap.
1306 bucket_count() const noexcept
1307 { return _M_h
.bucket_count(); }
1309 /// Returns the maximum number of buckets of the %unordered_multimap.
1311 max_bucket_count() const noexcept
1312 { return _M_h
.max_bucket_count(); }
1315 * @brief Returns the number of elements in a given bucket.
1316 * @param __n A bucket index.
1317 * @return The number of elements in the bucket.
1320 bucket_size(size_type __n
) const
1321 { return _M_h
.bucket_size(__n
); }
1324 * @brief Returns the bucket index of a given element.
1325 * @param __key A key instance.
1326 * @return The key bucket index.
1329 bucket(const key_type
& __key
) const
1330 { return _M_h
.bucket(__key
); }
1333 * @brief Returns a read/write iterator pointing to the first bucket
1335 * @param __n The bucket index.
1336 * @return A read/write local iterator.
1339 begin(size_type __n
)
1340 { return _M_h
.begin(__n
); }
1344 * @brief Returns a read-only (constant) iterator pointing to the first
1346 * @param __n The bucket index.
1347 * @return A read-only local iterator.
1349 const_local_iterator
1350 begin(size_type __n
) const
1351 { return _M_h
.begin(__n
); }
1353 const_local_iterator
1354 cbegin(size_type __n
) const
1355 { return _M_h
.cbegin(__n
); }
1359 * @brief Returns a read/write iterator pointing to one past the last
1361 * @param __n The bucket index.
1362 * @return A read/write local iterator.
1366 { return _M_h
.end(__n
); }
1370 * @brief Returns a read-only (constant) iterator pointing to one past
1371 * the last bucket elements.
1372 * @param __n The bucket index.
1373 * @return A read-only local iterator.
1375 const_local_iterator
1376 end(size_type __n
) const
1377 { return _M_h
.end(__n
); }
1379 const_local_iterator
1380 cend(size_type __n
) const
1381 { return _M_h
.cend(__n
); }
1386 /// Returns the average number of elements per bucket.
1388 load_factor() const noexcept
1389 { return _M_h
.load_factor(); }
1391 /// Returns a positive number that the %unordered_multimap tries to keep
1392 /// the load factor less than or equal to.
1394 max_load_factor() const noexcept
1395 { return _M_h
.max_load_factor(); }
1398 * @brief Change the %unordered_multimap maximum load factor.
1399 * @param __z The new maximum load factor.
1402 max_load_factor(float __z
)
1403 { _M_h
.max_load_factor(__z
); }
1406 * @brief May rehash the %unordered_multimap.
1407 * @param __n The new number of buckets.
1409 * Rehash will occur only if the new number of buckets respect the
1410 * %unordered_multimap maximum load factor.
1413 rehash(size_type __n
)
1414 { _M_h
.rehash(__n
); }
1417 * @brief Prepare the %unordered_multimap for a specified number of
1419 * @param __n Number of elements required.
1421 * Same as rehash(ceil(n / max_load_factor())).
1424 reserve(size_type __n
)
1425 { _M_h
.reserve(__n
); }
1427 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1430 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1431 _Hash1
, _Pred1
, _Alloc1
>&,
1432 const unordered_multimap
<_Key1
, _Tp1
,
1433 _Hash1
, _Pred1
, _Alloc1
>&);
1436 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1438 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1439 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1442 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1444 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1445 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1448 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1450 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1451 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1452 { return __x
._M_h
._M_equal(__y
._M_h
); }
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
== __y
); }
1460 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1462 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1463 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1464 { return __x
._M_h
._M_equal(__y
._M_h
); }
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
== __y
); }
1472 _GLIBCXX_END_NAMESPACE_CONTAINER
1475 #endif /* _UNORDERED_MAP_H */