1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010, 2011, 2012 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 allocator<_Key>.
85 * Meets the requirements of a <a href="tables.html#65">container</a>, and
86 * <a href="tables.html#xx">unordered associative container</a>
88 * The resulting value type of the container is std::pair<const _Key, _Tp>.
90 * Base is _Hashtable, dispatched at compile time via template
91 * alias __umap_hashtable.
93 template<class _Key
, class _Tp
,
94 class _Hash
= hash
<_Key
>,
95 class _Pred
= std::equal_to
<_Key
>,
96 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
99 typedef __umap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
106 typedef typename
_Hashtable::key_type key_type
;
107 typedef typename
_Hashtable::value_type value_type
;
108 typedef typename
_Hashtable::mapped_type mapped_type
;
109 typedef typename
_Hashtable::hasher hasher
;
110 typedef typename
_Hashtable::key_equal key_equal
;
111 typedef typename
_Hashtable::allocator_type allocator_type
;
115 /// Iterator-related typedefs.
116 typedef typename
allocator_type::pointer pointer
;
117 typedef typename
allocator_type::const_pointer const_pointer
;
118 typedef typename
allocator_type::reference reference
;
119 typedef typename
allocator_type::const_reference const_reference
;
120 typedef typename
_Hashtable::iterator iterator
;
121 typedef typename
_Hashtable::const_iterator const_iterator
;
122 typedef typename
_Hashtable::local_iterator local_iterator
;
123 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
124 typedef typename
_Hashtable::size_type size_type
;
125 typedef typename
_Hashtable::difference_type difference_type
;
128 //construct/destroy/copy
131 * @brief Default constructor creates no elements.
132 * @param __n Initial number of buckets.
133 * @param __hf A hash functor.
134 * @param __eql A key equality functor.
135 * @param __a An allocator object.
138 unordered_map(size_type __n
= 10,
139 const hasher
& __hf
= hasher(),
140 const key_equal
& __eql
= key_equal(),
141 const allocator_type
& __a
= allocator_type())
142 : _M_h(__n
, __hf
, __eql
, __a
)
146 * @brief Builds an %unordered_map from a range.
147 * @param __first An input iterator.
148 * @param __last An input iterator.
149 * @param __n Minimal initial number of buckets.
150 * @param __hf A hash functor.
151 * @param __eql A key equality functor.
152 * @param __a An allocator object.
154 * Create an %unordered_map consisting of copies of the elements from
155 * [__first,__last). This is linear in N (where N is
156 * distance(__first,__last)).
158 template<typename _InputIterator
>
159 unordered_map(_InputIterator __f
, _InputIterator __l
,
161 const hasher
& __hf
= hasher(),
162 const key_equal
& __eql
= key_equal(),
163 const allocator_type
& __a
= allocator_type())
164 : _M_h(__f
, __l
, __n
, __hf
, __eql
, __a
)
167 /// Copy constructor.
168 unordered_map(const unordered_map
&) = default;
170 /// Move constrcutor.
171 unordered_map(unordered_map
&&) = default;
174 * @brief Builds an %unordered_map from an initializer_list.
175 * @param __l An initializer_list.
176 * @param __n Minimal initial number of buckets.
177 * @param __hf A hash functor.
178 * @param __eql A key equality functor.
179 * @param __a An allocator object.
181 * Create an %unordered_map consisting of copies of the elements in the
182 * list. This is linear in N (where N is @a __l.size()).
184 unordered_map(initializer_list
<value_type
> __l
,
186 const hasher
& __hf
= hasher(),
187 const key_equal
& __eql
= key_equal(),
188 const allocator_type
& __a
= allocator_type())
189 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
192 /// Copy assignment operator.
194 operator=(const unordered_map
&) = default;
196 /// Move assignment operator.
198 operator=(unordered_map
&&) = default;
201 * @brief %Unordered_map list assignment operator.
202 * @param __l An initializer_list.
204 * This function fills an %unordered_map with copies of the elements in
205 * the initializer list @a __l.
207 * Note that the assignment completely changes the %unordered_map and
208 * that the resulting %unordered_map's size is the same as the number
209 * of elements assigned. Old data may be lost.
212 operator=(initializer_list
<value_type
> __l
)
218 /// Returns the allocator object with which the %unordered_map was
221 get_allocator() const noexcept
222 { return _M_h
.get_allocator(); }
224 // size and capacity:
226 /// Returns true if the %unordered_map is empty.
228 empty() const noexcept
229 { return _M_h
.empty(); }
231 /// Returns the size of the %unordered_map.
233 size() const noexcept
234 { return _M_h
.size(); }
236 /// Returns the maximum size of the %unordered_map.
238 max_size() const noexcept
239 { return _M_h
.max_size(); }
244 * Returns a read/write iterator that points to the first element in the
249 { return _M_h
.begin(); }
253 * Returns a read-only (constant) iterator that points to the first
254 * element in the %unordered_map.
257 begin() const noexcept
258 { return _M_h
.begin(); }
261 cbegin() const noexcept
262 { return _M_h
.begin(); }
266 * Returns a read/write iterator that points one past the last element in
267 * the %unordered_map.
271 { return _M_h
.end(); }
275 * Returns a read-only (constant) iterator that points one past the last
276 * element in the %unordered_map.
280 { return _M_h
.end(); }
283 cend() const noexcept
284 { return _M_h
.end(); }
290 * @brief Attempts to build and insert a std::pair into the %unordered_map.
292 * @param __args Arguments used to generate a new pair instance (see
293 * std::piecewise_contruct for passing arguments to each
294 * part of the pair constructor).
296 * @return A pair, of which the first element is an iterator that points
297 * to the possibly inserted pair, and the second is a bool that
298 * is true if the pair was actually inserted.
300 * This function attempts to build and insert a (key, value) %pair into
301 * the %unordered_map.
302 * An %unordered_map relies on unique keys and thus a %pair is only
303 * inserted if its first element (the key) is not already present in the
306 * Insertion requires amortized constant time.
308 template<typename
... _Args
>
309 std::pair
<iterator
, bool>
310 emplace(_Args
&&... __args
)
311 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
314 * @brief Attempts to build and insert a std::pair into the %unordered_map.
316 * @param __pos An iterator that serves as a hint as to where the pair
317 * should be inserted.
318 * @param __args Arguments used to generate a new pair instance (see
319 * std::piecewise_contruct for passing arguments to each
320 * part of the pair constructor).
321 * @return An iterator that points to the element with key of the
322 * std::pair built from @a __args (may or may not be that
325 * This function is not concerned about whether the insertion took place,
326 * and thus does not return a boolean like the single-argument emplace()
328 * Note that the first parameter is only a hint and can potentially
329 * improve the performance of the insertion process. A bad hint would
330 * cause no gains in efficiency.
333 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
334 * for more on @a hinting.
336 * Insertion requires amortized constant time.
338 template<typename
... _Args
>
340 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
341 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
345 * @brief Attempts to insert a std::pair into the %unordered_map.
347 * @param __x Pair to be inserted (see std::make_pair for easy
348 * creation of pairs).
350 * @return A pair, of which the first element is an iterator that
351 * points to the possibly inserted pair, and the second is
352 * a bool that is true if the pair was actually inserted.
354 * This function attempts to insert a (key, value) %pair into the
355 * %unordered_map. An %unordered_map relies on unique keys and thus a
356 * %pair is only inserted if its first element (the key) is not already
357 * present in the %unordered_map.
359 * Insertion requires amortized constant time.
361 std::pair
<iterator
, bool>
362 insert(const value_type
& __x
)
363 { return _M_h
.insert(__x
); }
365 template<typename _Pair
, typename
= typename
366 std::enable_if
<std::is_constructible
<value_type
,
367 _Pair
&&>::value
>::type
>
368 std::pair
<iterator
, bool>
370 { return _M_h
.insert(std::move(__x
)); }
375 * @brief Attempts to insert a std::pair into the %unordered_map.
376 * @param __hint An iterator that serves as a hint as to where the
377 * pair should be inserted.
378 * @param __x Pair to be inserted (see std::make_pair for easy creation
380 * @return An iterator that points to the element with key of
381 * @a __x (may or may not be the %pair passed in).
383 * This function is not concerned about whether the insertion took place,
384 * and thus does not return a boolean like the single-argument insert()
385 * does. Note that the first parameter is only a hint and can
386 * potentially improve the performance of the insertion process. A bad
387 * hint would cause no gains in efficiency.
390 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
391 * for more on @a hinting.
393 * Insertion requires amortized constant time.
396 insert(const_iterator __hint
, const value_type
& __x
)
397 { return _M_h
.insert(__hint
, __x
); }
399 template<typename _Pair
, typename
= typename
400 std::enable_if
<std::is_constructible
<value_type
,
401 _Pair
&&>::value
>::type
>
403 insert(const_iterator __hint
, _Pair
&& __x
)
404 { return _M_h
.insert(__hint
, std::move(__x
)); }
408 * @brief A template function that attempts to insert a range of
410 * @param __first Iterator pointing to the start of the range to be
412 * @param __last Iterator pointing to the end of the range.
414 * Complexity similar to that of the range constructor.
416 template<typename _InputIterator
>
418 insert(_InputIterator __first
, _InputIterator __last
)
419 { _M_h
.insert(__first
, __last
); }
422 * @brief Attempts to insert a list of elements into the %unordered_map.
423 * @param __l A std::initializer_list<value_type> of elements
426 * Complexity similar to that of the range constructor.
429 insert(initializer_list
<value_type
> __l
)
430 { _M_h
.insert(__l
); }
434 * @brief Erases an element from an %unordered_map.
435 * @param __position An iterator pointing to the element to be erased.
436 * @return An iterator pointing to the element immediately following
437 * @a __position prior to the element being erased. If no such
438 * element exists, end() is returned.
440 * This function erases an element, pointed to by the given iterator,
441 * from an %unordered_map.
442 * Note that this function only erases the element, and that if the
443 * element is itself a pointer, the pointed-to memory is not touched in
444 * any way. Managing the pointer is the user's responsibility.
447 erase(const_iterator __position
)
448 { return _M_h
.erase(__position
); }
453 { return _M_h
.erase(__it
); }
457 * @brief Erases elements according to the provided key.
458 * @param __x Key of element to be erased.
459 * @return The number of elements erased.
461 * This function erases all the elements located by the given key from
462 * an %unordered_map. For an %unordered_map the result of this function
463 * can only be 0 (not present) or 1 (present).
464 * Note that this function only erases the element, and that if the
465 * element is itself a pointer, the pointed-to memory is not touched in
466 * any way. Managing the pointer is the user's responsibility.
469 erase(const key_type
& __x
)
470 { return _M_h
.erase(__x
); }
473 * @brief Erases a [__first,__last) range of elements from an
475 * @param __first Iterator pointing to the start of the range to be
477 * @param __last Iterator pointing to the end of the range to
479 * @return The iterator @a __last.
481 * This function erases a sequence of elements from an %unordered_map.
482 * Note that this function only erases the elements, and that if
483 * the element is itself a pointer, the pointed-to memory is not touched
484 * in any way. Managing the pointer is the user's responsibility.
487 erase(const_iterator __first
, const_iterator __last
)
488 { return _M_h
.erase(__first
, __last
); }
491 * Erases all elements in an %unordered_map.
492 * Note that this function only erases the elements, and that if the
493 * elements themselves are pointers, the pointed-to memory is not touched
494 * in any way. Managing the pointer is the user's responsibility.
501 * @brief Swaps data with another %unordered_map.
502 * @param __x An %unordered_map of the same element and allocator
505 * This exchanges the elements between two %unordered_map in constant time.
506 * Note that the global std::swap() function is specialized such that
507 * std::swap(m1,m2) will feed to this function.
510 swap(unordered_map
& __x
)
511 { _M_h
.swap(__x
._M_h
); }
515 /// Returns the hash functor object with which the %unordered_map was
518 hash_function() const
519 { return _M_h
.hash_function(); }
521 /// Returns the key comparison object with which the %unordered_map was
525 { return _M_h
.key_eq(); }
531 * @brief Tries to locate an element in an %unordered_map.
532 * @param __x Key to be located.
533 * @return Iterator pointing to sought-after element, or end() if not
536 * This function takes a key and tries to locate the element with which
537 * the key matches. If successful the function returns an iterator
538 * pointing to the sought after element. If unsuccessful it returns the
539 * past-the-end ( @c end() ) iterator.
542 find(const key_type
& __x
)
543 { return _M_h
.find(__x
); }
546 find(const key_type
& __x
) const
547 { return _M_h
.find(__x
); }
551 * @brief Finds the number of elements.
552 * @param __x Key to count.
553 * @return Number of elements with specified key.
555 * This function only makes sense for %unordered_multimap; for
556 * %unordered_map the result will either be 0 (not present) or 1
560 count(const key_type
& __x
) const
561 { return _M_h
.count(__x
); }
565 * @brief Finds a subsequence matching given key.
566 * @param __x Key to be located.
567 * @return Pair of iterators that possibly points to the subsequence
568 * matching given key.
570 * This function probably only makes sense for %unordered_multimap.
572 std::pair
<iterator
, iterator
>
573 equal_range(const key_type
& __x
)
574 { return _M_h
.equal_range(__x
); }
576 std::pair
<const_iterator
, const_iterator
>
577 equal_range(const key_type
& __x
) const
578 { return _M_h
.equal_range(__x
); }
583 * @brief Subscript ( @c [] ) access to %unordered_map data.
584 * @param __k The key for which data should be retrieved.
585 * @return A reference to the data of the (key,data) %pair.
587 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
588 * data associated with the key specified in subscript. If the key does
589 * not exist, a pair with that key is created using default values, which
592 * Lookup requires constant time.
595 operator[](const key_type
& __k
)
596 { return _M_h
[__k
]; }
599 operator[](key_type
&& __k
)
600 { return _M_h
[std::move(__k
)]; }
605 * @brief Access to %unordered_map data.
606 * @param __k The key for which data should be retrieved.
607 * @return A reference to the data whose key is equal to @a __k, if
608 * such a data is present in the %unordered_map.
609 * @throw std::out_of_range If no such data is present.
612 at(const key_type
& __k
)
613 { return _M_h
.at(__k
); }
616 at(const key_type
& __k
) const
617 { return _M_h
.at(__k
); }
622 /// Returns the number of buckets of the %unordered_map.
624 bucket_count() const noexcept
625 { return _M_h
.bucket_count(); }
627 /// Returns the maximum number of buckets of the %unordered_map.
629 max_bucket_count() const noexcept
630 { return _M_h
.max_bucket_count(); }
633 * @brief Returns the number of elements in a given bucket.
634 * @param __n A bucket index.
635 * @return The number of elements in the bucket.
638 bucket_size(size_type __n
) const
639 { return _M_h
.bucket_size(__n
); }
642 * @brief Returns the bucket index of a given element.
643 * @param __key A key instance.
644 * @return The key bucket index.
647 bucket(const key_type
& __key
) const
648 { return _M_h
.bucket(__key
); }
651 * @brief Returns a read/write iterator pointing to the first bucket
653 * @param __n The bucket index.
654 * @return A read/write local iterator.
658 { return _M_h
.begin(__n
); }
662 * @brief Returns a read-only (constant) iterator pointing to the first
664 * @param __n The bucket index.
665 * @return A read-only local iterator.
668 begin(size_type __n
) const
669 { return _M_h
.begin(__n
); }
672 cbegin(size_type __n
) const
673 { return _M_h
.cbegin(__n
); }
677 * @brief Returns a read/write iterator pointing to one past the last
679 * @param __n The bucket index.
680 * @return A read/write local iterator.
684 { return _M_h
.end(__n
); }
688 * @brief Returns a read-only (constant) iterator pointing to one past
689 * the last bucket elements.
690 * @param __n The bucket index.
691 * @return A read-only local iterator.
694 end(size_type __n
) const
695 { return _M_h
.end(__n
); }
698 cend(size_type __n
) const
699 { return _M_h
.cend(__n
); }
704 /// Returns the average number of elements per bucket.
706 load_factor() const noexcept
707 { return _M_h
.load_factor(); }
709 /// Returns a positive number that the %unordered_map tries to keep the
710 /// load factor less than or equal to.
712 max_load_factor() const noexcept
713 { return _M_h
.max_load_factor(); }
716 * @brief Change the %unordered_map maximum load factor.
717 * @param __z The new maximum load factor.
720 max_load_factor(float __z
)
721 { _M_h
.max_load_factor(__z
); }
724 * @brief May rehash the %unordered_map.
725 * @param __n The new number of buckets.
727 * Rehash will occur only if the new number of buckets respect the
728 * %unordered_map maximum load factor.
731 rehash(size_type __n
)
732 { _M_h
.rehash(__n
); }
735 * @brief Prepare the %unordered_map for a specified number of
737 * @param __n Number of elements required.
739 * Same as rehash(ceil(n / max_load_factor())).
742 reserve(size_type __n
)
743 { _M_h
.reserve(__n
); }
745 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
748 operator==(const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&,
749 const unordered_map
<_Key1
, _Tp1
, _Hash1
, _Pred1
, _Alloc1
>&);
753 * @brief A standard container composed of equivalent keys
754 * (possibly containing multiple of each key value) that associates
755 * values of another type with the keys.
757 * @ingroup unordered_associative_containers
759 * @tparam _Key Type of key objects.
760 * @tparam _Tp Type of mapped objects.
761 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
762 * @tparam _Pred Predicate function object type, defaults
763 * to equal_to<_Value>.
764 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
766 * Meets the requirements of a <a href="tables.html#65">container</a>, and
767 * <a href="tables.html#xx">unordered associative container</a>
769 * The resulting value type of the container is std::pair<const _Key, _Tp>.
771 * Base is _Hashtable, dispatched at compile time via template
772 * alias __ummap_hashtable.
774 template<class _Key
, class _Tp
,
775 class _Hash
= hash
<_Key
>,
776 class _Pred
= std::equal_to
<_Key
>,
777 class _Alloc
= std::allocator
<std::pair
<const _Key
, _Tp
> > >
778 class unordered_multimap
780 typedef __ummap_hashtable
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
787 typedef typename
_Hashtable::key_type key_type
;
788 typedef typename
_Hashtable::value_type value_type
;
789 typedef typename
_Hashtable::mapped_type mapped_type
;
790 typedef typename
_Hashtable::hasher hasher
;
791 typedef typename
_Hashtable::key_equal key_equal
;
792 typedef typename
_Hashtable::allocator_type allocator_type
;
796 /// Iterator-related typedefs.
797 typedef typename
allocator_type::pointer pointer
;
798 typedef typename
allocator_type::const_pointer const_pointer
;
799 typedef typename
allocator_type::reference reference
;
800 typedef typename
allocator_type::const_reference const_reference
;
801 typedef typename
_Hashtable::iterator iterator
;
802 typedef typename
_Hashtable::const_iterator const_iterator
;
803 typedef typename
_Hashtable::local_iterator local_iterator
;
804 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
805 typedef typename
_Hashtable::size_type size_type
;
806 typedef typename
_Hashtable::difference_type difference_type
;
809 //construct/destroy/copy
812 * @brief Default constructor creates no elements.
813 * @param __n Initial number of buckets.
814 * @param __hf A hash functor.
815 * @param __eql A key equality functor.
816 * @param __a An allocator object.
819 unordered_multimap(size_type __n
= 10,
820 const hasher
& __hf
= hasher(),
821 const key_equal
& __eql
= key_equal(),
822 const allocator_type
& __a
= allocator_type())
823 : _M_h(__n
, __hf
, __eql
, __a
)
827 * @brief Builds an %unordered_multimap from a range.
828 * @param __first An input iterator.
829 * @param __last An input iterator.
830 * @param __n Minimal initial number of buckets.
831 * @param __hf A hash functor.
832 * @param __eql A key equality functor.
833 * @param __a An allocator object.
835 * Create an %unordered_multimap consisting of copies of the elements
836 * from [__first,__last). This is linear in N (where N is
837 * distance(__first,__last)).
839 template<typename _InputIterator
>
840 unordered_multimap(_InputIterator __f
, _InputIterator __l
,
842 const hasher
& __hf
= hasher(),
843 const key_equal
& __eql
= key_equal(),
844 const allocator_type
& __a
= allocator_type())
845 : _M_h(__f
, __l
, __n
, __hf
, __eql
, __a
)
848 /// Copy constructor.
849 unordered_multimap(const unordered_multimap
&) = default;
851 /// Move constrcutor.
852 unordered_multimap(unordered_multimap
&&) = default;
855 * @brief Builds an %unordered_multimap from an initializer_list.
856 * @param __l An initializer_list.
857 * @param __n Minimal initial number of buckets.
858 * @param __hf A hash functor.
859 * @param __eql A key equality functor.
860 * @param __a An allocator object.
862 * Create an %unordered_multimap consisting of copies of the elements in
863 * the list. This is linear in N (where N is @a __l.size()).
865 unordered_multimap(initializer_list
<value_type
> __l
,
867 const hasher
& __hf
= hasher(),
868 const key_equal
& __eql
= key_equal(),
869 const allocator_type
& __a
= allocator_type())
870 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
873 /// Copy assignment operator.
875 operator=(const unordered_multimap
&) = default;
877 /// Move assignment operator.
879 operator=(unordered_multimap
&&) = default;
882 * @brief %Unordered_multimap list assignment operator.
883 * @param __l An initializer_list.
885 * This function fills an %unordered_multimap with copies of the elements
886 * in the initializer list @a __l.
888 * Note that the assignment completely changes the %unordered_multimap
889 * and that the resulting %unordered_multimap's size is the same as the
890 * number of elements assigned. Old data may be lost.
893 operator=(initializer_list
<value_type
> __l
)
899 /// Returns the allocator object with which the %unordered_multimap was
902 get_allocator() const noexcept
903 { return _M_h
.get_allocator(); }
905 // size and capacity:
907 /// Returns true if the %unordered_multimap is empty.
909 empty() const noexcept
910 { return _M_h
.empty(); }
912 /// Returns the size of the %unordered_multimap.
914 size() const noexcept
915 { return _M_h
.size(); }
917 /// Returns the maximum size of the %unordered_multimap.
919 max_size() const noexcept
920 { return _M_h
.max_size(); }
925 * Returns a read/write iterator that points to the first element in the
926 * %unordered_multimap.
930 { return _M_h
.begin(); }
934 * Returns a read-only (constant) iterator that points to the first
935 * element in the %unordered_multimap.
938 begin() const noexcept
939 { return _M_h
.begin(); }
942 cbegin() const noexcept
943 { return _M_h
.begin(); }
947 * Returns a read/write iterator that points one past the last element in
948 * the %unordered_multimap.
952 { return _M_h
.end(); }
956 * Returns a read-only (constant) iterator that points one past the last
957 * element in the %unordered_multimap.
961 { return _M_h
.end(); }
964 cend() const noexcept
965 { return _M_h
.end(); }
971 * @brief Attempts to build and insert a std::pair into the
972 * %unordered_multimap.
974 * @param __args Arguments used to generate a new pair instance (see
975 * std::piecewise_contruct for passing arguments to each
976 * part of the pair constructor).
978 * @return An iterator that points to the inserted pair.
980 * This function attempts to build and insert a (key, value) %pair into
981 * the %unordered_multimap.
983 * Insertion requires amortized constant time.
985 template<typename
... _Args
>
987 emplace(_Args
&&... __args
)
988 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
991 * @brief Attempts to build and insert a std::pair into the %unordered_multimap.
993 * @param __pos An iterator that serves as a hint as to where the pair
994 * should be inserted.
995 * @param __args Arguments used to generate a new pair instance (see
996 * std::piecewise_contruct for passing arguments to each
997 * part of the pair constructor).
998 * @return An iterator that points to the element with key of the
999 * std::pair built from @a __args.
1001 * Note that the first parameter is only a hint and can potentially
1002 * improve the performance of the insertion process. A bad hint would
1003 * cause no gains in efficiency.
1006 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
1007 * for more on @a hinting.
1009 * Insertion requires amortized constant time.
1011 template<typename
... _Args
>
1013 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1014 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1018 * @brief Inserts a std::pair into the %unordered_multimap.
1019 * @param __x Pair to be inserted (see std::make_pair for easy
1020 * creation of pairs).
1022 * @return An iterator that points to the inserted pair.
1024 * Insertion requires amortized constant time.
1027 insert(const value_type
& __x
)
1028 { return _M_h
.insert(__x
); }
1030 template<typename _Pair
, typename
= typename
1031 std::enable_if
<std::is_constructible
<value_type
,
1032 _Pair
&&>::value
>::type
>
1035 { return _M_h
.insert(std::move(__x
)); }
1040 * @brief Inserts a std::pair into the %unordered_multimap.
1041 * @param __hint An iterator that serves as a hint as to where the
1042 * pair should be inserted.
1043 * @param __x Pair to be inserted (see std::make_pair for easy creation
1045 * @return An iterator that points to the element with key of
1046 * @a __x (may or may not be the %pair passed in).
1048 * Note that the first parameter is only a hint and can potentially
1049 * improve the performance of the insertion process. A bad hint would
1050 * cause no gains in efficiency.
1053 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
1054 * for more on @a hinting.
1056 * Insertion requires amortized constant time.
1059 insert(const_iterator __hint
, const value_type
& __x
)
1060 { return _M_h
.insert(__hint
, __x
); }
1062 template<typename _Pair
, typename
= typename
1063 std::enable_if
<std::is_constructible
<value_type
,
1064 _Pair
&&>::value
>::type
>
1066 insert(const_iterator __hint
, _Pair
&& __x
)
1067 { return _M_h
.insert(__hint
, std::move(__x
)); }
1071 * @brief A template function that attempts to insert a range of
1073 * @param __first Iterator pointing to the start of the range to be
1075 * @param __last Iterator pointing to the end of the range.
1077 * Complexity similar to that of the range constructor.
1079 template<typename _InputIterator
>
1081 insert(_InputIterator __first
, _InputIterator __last
)
1082 { _M_h
.insert(__first
, __last
); }
1085 * @brief Attempts to insert a list of elements into the
1086 * %unordered_multimap.
1087 * @param __l A std::initializer_list<value_type> of elements
1090 * Complexity similar to that of the range constructor.
1093 insert(initializer_list
<value_type
> __l
)
1094 { _M_h
.insert(__l
); }
1098 * @brief Erases an element from an %unordered_multimap.
1099 * @param __position An iterator pointing to the element to be erased.
1100 * @return An iterator pointing to the element immediately following
1101 * @a __position prior to the element being erased. If no such
1102 * element exists, end() is returned.
1104 * This function erases an element, pointed to by the given iterator,
1105 * from an %unordered_multimap.
1106 * Note that this function only erases the element, and that if the
1107 * element is itself a pointer, the pointed-to memory is not touched in
1108 * any way. Managing the pointer is the user's responsibility.
1111 erase(const_iterator __position
)
1112 { return _M_h
.erase(__position
); }
1116 erase(iterator __it
)
1117 { return _M_h
.erase(__it
); }
1121 * @brief Erases elements according to the provided key.
1122 * @param __x Key of elements to be erased.
1123 * @return The number of elements erased.
1125 * This function erases all the elements located by the given key from
1126 * an %unordered_multimap.
1127 * Note that this function only erases the element, and that if the
1128 * element is itself a pointer, the pointed-to memory is not touched in
1129 * any way. Managing the pointer is the user's responsibility.
1132 erase(const key_type
& __x
)
1133 { return _M_h
.erase(__x
); }
1136 * @brief Erases a [__first,__last) range of elements from an
1137 * %unordered_multimap.
1138 * @param __first Iterator pointing to the start of the range to be
1140 * @param __last Iterator pointing to the end of the range to
1142 * @return The iterator @a __last.
1144 * This function erases a sequence of elements from an
1145 * %unordered_multimap.
1146 * Note that this function only erases the elements, and that if
1147 * the element is itself a pointer, the pointed-to memory is not touched
1148 * in any way. Managing the pointer is the user's responsibility.
1151 erase(const_iterator __first
, const_iterator __last
)
1152 { return _M_h
.erase(__first
, __last
); }
1155 * Erases all elements in an %unordered_multimap.
1156 * Note that this function only erases the elements, and that if the
1157 * elements themselves are pointers, the pointed-to memory is not touched
1158 * in any way. Managing the pointer is the user's responsibility.
1165 * @brief Swaps data with another %unordered_multimap.
1166 * @param __x An %unordered_multimap of the same element and allocator
1169 * This exchanges the elements between two %unordered_multimap in
1171 * Note that the global std::swap() function is specialized such that
1172 * std::swap(m1,m2) will feed to this function.
1175 swap(unordered_multimap
& __x
)
1176 { _M_h
.swap(__x
._M_h
); }
1180 /// Returns the hash functor object with which the %unordered_multimap
1181 /// was constructed.
1183 hash_function() const
1184 { return _M_h
.hash_function(); }
1186 /// Returns the key comparison object with which the %unordered_multimap
1187 /// was constructed.
1190 { return _M_h
.key_eq(); }
1196 * @brief Tries to locate an element in an %unordered_multimap.
1197 * @param __x Key to be located.
1198 * @return Iterator pointing to sought-after element, or end() if not
1201 * This function takes a key and tries to locate the element with which
1202 * the key matches. If successful the function returns an iterator
1203 * pointing to the sought after element. If unsuccessful it returns the
1204 * past-the-end ( @c end() ) iterator.
1207 find(const key_type
& __x
)
1208 { return _M_h
.find(__x
); }
1211 find(const key_type
& __x
) const
1212 { return _M_h
.find(__x
); }
1216 * @brief Finds the number of elements.
1217 * @param __x Key to count.
1218 * @return Number of elements with specified key.
1221 count(const key_type
& __x
) const
1222 { return _M_h
.count(__x
); }
1226 * @brief Finds a subsequence matching given key.
1227 * @param __x Key to be located.
1228 * @return Pair of iterators that possibly points to the subsequence
1229 * matching given key.
1231 std::pair
<iterator
, iterator
>
1232 equal_range(const key_type
& __x
)
1233 { return _M_h
.equal_range(__x
); }
1235 std::pair
<const_iterator
, const_iterator
>
1236 equal_range(const key_type
& __x
) const
1237 { return _M_h
.equal_range(__x
); }
1240 // bucket interface.
1242 /// Returns the number of buckets of the %unordered_multimap.
1244 bucket_count() const noexcept
1245 { return _M_h
.bucket_count(); }
1247 /// Returns the maximum number of buckets of the %unordered_multimap.
1249 max_bucket_count() const noexcept
1250 { return _M_h
.max_bucket_count(); }
1253 * @brief Returns the number of elements in a given bucket.
1254 * @param __n A bucket index.
1255 * @return The number of elements in the bucket.
1258 bucket_size(size_type __n
) const
1259 { return _M_h
.bucket_size(__n
); }
1262 * @brief Returns the bucket index of a given element.
1263 * @param __key A key instance.
1264 * @return The key bucket index.
1267 bucket(const key_type
& __key
) const
1268 { return _M_h
.bucket(__key
); }
1271 * @brief Returns a read/write iterator pointing to the first bucket
1273 * @param __n The bucket index.
1274 * @return A read/write local iterator.
1277 begin(size_type __n
)
1278 { return _M_h
.begin(__n
); }
1282 * @brief Returns a read-only (constant) iterator pointing to the first
1284 * @param __n The bucket index.
1285 * @return A read-only local iterator.
1287 const_local_iterator
1288 begin(size_type __n
) const
1289 { return _M_h
.begin(__n
); }
1291 const_local_iterator
1292 cbegin(size_type __n
) const
1293 { return _M_h
.cbegin(__n
); }
1297 * @brief Returns a read/write iterator pointing to one past the last
1299 * @param __n The bucket index.
1300 * @return A read/write local iterator.
1304 { return _M_h
.end(__n
); }
1308 * @brief Returns a read-only (constant) iterator pointing to one past
1309 * the last bucket elements.
1310 * @param __n The bucket index.
1311 * @return A read-only local iterator.
1313 const_local_iterator
1314 end(size_type __n
) const
1315 { return _M_h
.end(__n
); }
1317 const_local_iterator
1318 cend(size_type __n
) const
1319 { return _M_h
.cend(__n
); }
1324 /// Returns the average number of elements per bucket.
1326 load_factor() const noexcept
1327 { return _M_h
.load_factor(); }
1329 /// Returns a positive number that the %unordered_multimap tries to keep
1330 /// the load factor less than or equal to.
1332 max_load_factor() const noexcept
1333 { return _M_h
.max_load_factor(); }
1336 * @brief Change the %unordered_multimap maximum load factor.
1337 * @param __z The new maximum load factor.
1340 max_load_factor(float __z
)
1341 { _M_h
.max_load_factor(__z
); }
1344 * @brief May rehash the %unordered_multimap.
1345 * @param __n The new number of buckets.
1347 * Rehash will occur only if the new number of buckets respect the
1348 * %unordered_multimap maximum load factor.
1351 rehash(size_type __n
)
1352 { _M_h
.rehash(__n
); }
1355 * @brief Prepare the %unordered_multimap for a specified number of
1357 * @param __n Number of elements required.
1359 * Same as rehash(ceil(n / max_load_factor())).
1362 reserve(size_type __n
)
1363 { _M_h
.reserve(__n
); }
1365 template<typename _Key1
, typename _Tp1
, typename _Hash1
, typename _Pred1
,
1368 operator==(const unordered_multimap
<_Key1
, _Tp1
,
1369 _Hash1
, _Pred1
, _Alloc1
>&,
1370 const unordered_multimap
<_Key1
, _Tp1
,
1371 _Hash1
, _Pred1
, _Alloc1
>&);
1374 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1376 swap(unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1377 unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1380 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1382 swap(unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1383 unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1386 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1388 operator==(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1389 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1390 { return __x
._M_h
._M_equal(__y
._M_h
); }
1392 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1394 operator!=(const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1395 const unordered_map
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1396 { return !(__x
== __y
); }
1398 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1400 operator==(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1401 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1402 { return __x
._M_h
._M_equal(__y
._M_h
); }
1404 template<class _Key
, class _Tp
, class _Hash
, class _Pred
, class _Alloc
>
1406 operator!=(const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __x
,
1407 const unordered_multimap
<_Key
, _Tp
, _Hash
, _Pred
, _Alloc
>& __y
)
1408 { return !(__x
== __y
); }
1410 _GLIBCXX_END_NAMESPACE_CONTAINER
1413 #endif /* _UNORDERED_MAP_H */