libstdc++
unordered_map.h
Go to the documentation of this file.
1// unordered_map implementation -*- C++ -*-
2
3// Copyright (C) 2010-2020 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
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}
28 */
29
30#ifndef _UNORDERED_MAP_H
31#define _UNORDERED_MAP_H
32
33namespace std _GLIBCXX_VISIBILITY(default)
34{
35_GLIBCXX_BEGIN_NAMESPACE_VERSION
36_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37
38 /// Base types for unordered_map.
39 template<bool _Cache>
41
42 template<typename _Key,
43 typename _Tp,
44 typename _Hash = hash<_Key>,
45 typename _Pred = std::equal_to<_Key>,
49 _Alloc, __detail::_Select1st,
50 _Pred, _Hash,
54
55 /// Base types for unordered_multimap.
56 template<bool _Cache>
58
59 template<typename _Key,
60 typename _Tp,
61 typename _Hash = hash<_Key>,
62 typename _Pred = std::equal_to<_Key>,
66 _Alloc, __detail::_Select1st,
67 _Pred, _Hash,
71
72 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
74
75 /**
76 * @brief A standard container composed of unique keys (containing
77 * at most one of each key value) that associates values of another type
78 * with the keys.
79 *
80 * @ingroup unordered_associative_containers
81 *
82 * @tparam _Key Type of key objects.
83 * @tparam _Tp Type of mapped objects.
84 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
85 * @tparam _Pred Predicate function object type, defaults
86 * to equal_to<_Value>.
87 * @tparam _Alloc Allocator type, defaults to
88 * std::allocator<std::pair<const _Key, _Tp>>.
89 *
90 * Meets the requirements of a <a href="tables.html#65">container</a>, and
91 * <a href="tables.html#xx">unordered associative container</a>
92 *
93 * The resulting value type of the container is std::pair<const _Key, _Tp>.
94 *
95 * Base is _Hashtable, dispatched at compile time via template
96 * alias __umap_hashtable.
97 */
98 template<typename _Key, typename _Tp,
99 typename _Hash = hash<_Key>,
100 typename _Pred = equal_to<_Key>,
101 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
103 {
105 _Hashtable _M_h;
106
107 public:
108 // typedefs:
109 ///@{
110 /// Public typedefs.
111 typedef typename _Hashtable::key_type key_type;
112 typedef typename _Hashtable::value_type value_type;
113 typedef typename _Hashtable::mapped_type mapped_type;
114 typedef typename _Hashtable::hasher hasher;
115 typedef typename _Hashtable::key_equal key_equal;
116 typedef typename _Hashtable::allocator_type allocator_type;
117 ///@}
118
119 ///@{
120 /// Iterator-related typedefs.
121 typedef typename _Hashtable::pointer pointer;
122 typedef typename _Hashtable::const_pointer const_pointer;
123 typedef typename _Hashtable::reference reference;
124 typedef typename _Hashtable::const_reference const_reference;
125 typedef typename _Hashtable::iterator iterator;
126 typedef typename _Hashtable::const_iterator const_iterator;
127 typedef typename _Hashtable::local_iterator local_iterator;
128 typedef typename _Hashtable::const_local_iterator const_local_iterator;
129 typedef typename _Hashtable::size_type size_type;
130 typedef typename _Hashtable::difference_type difference_type;
131 ///@}
132
133#if __cplusplus > 201402L
134 using node_type = typename _Hashtable::node_type;
135 using insert_return_type = typename _Hashtable::insert_return_type;
136#endif
137
138 //construct/destroy/copy
139
140 /// Default constructor.
141 unordered_map() = default;
142
143 /**
144 * @brief Default constructor creates no elements.
145 * @param __n Minimal initial number of buckets.
146 * @param __hf A hash functor.
147 * @param __eql A key equality functor.
148 * @param __a An allocator object.
149 */
150 explicit
152 const hasher& __hf = hasher(),
153 const key_equal& __eql = key_equal(),
154 const allocator_type& __a = allocator_type())
155 : _M_h(__n, __hf, __eql, __a)
156 { }
157
158 /**
159 * @brief Builds an %unordered_map from a range.
160 * @param __first An input iterator.
161 * @param __last An input iterator.
162 * @param __n Minimal initial number of buckets.
163 * @param __hf A hash functor.
164 * @param __eql A key equality functor.
165 * @param __a An allocator object.
166 *
167 * Create an %unordered_map consisting of copies of the elements from
168 * [__first,__last). This is linear in N (where N is
169 * distance(__first,__last)).
170 */
171 template<typename _InputIterator>
172 unordered_map(_InputIterator __first, _InputIterator __last,
173 size_type __n = 0,
174 const hasher& __hf = hasher(),
175 const key_equal& __eql = key_equal(),
176 const allocator_type& __a = allocator_type())
177 : _M_h(__first, __last, __n, __hf, __eql, __a)
178 { }
179
180 /// Copy constructor.
181 unordered_map(const unordered_map&) = default;
182
183 /// Move constructor.
185
186 /**
187 * @brief Creates an %unordered_map with no elements.
188 * @param __a An allocator object.
189 */
190 explicit
192 : _M_h(__a)
193 { }
194
195 /*
196 * @brief Copy constructor with allocator argument.
197 * @param __uset Input %unordered_map to copy.
198 * @param __a An allocator object.
199 */
200 unordered_map(const unordered_map& __umap,
201 const allocator_type& __a)
202 : _M_h(__umap._M_h, __a)
203 { }
204
205 /*
206 * @brief Move constructor with allocator argument.
207 * @param __uset Input %unordered_map to move.
208 * @param __a An allocator object.
209 */
211 const allocator_type& __a)
212 noexcept( noexcept(_Hashtable(std::move(__umap._M_h), __a)) )
213 : _M_h(std::move(__umap._M_h), __a)
214 { }
215
216 /**
217 * @brief Builds an %unordered_map from an initializer_list.
218 * @param __l An initializer_list.
219 * @param __n Minimal initial number of buckets.
220 * @param __hf A hash functor.
221 * @param __eql A key equality functor.
222 * @param __a An allocator object.
223 *
224 * Create an %unordered_map consisting of copies of the elements in the
225 * list. This is linear in N (where N is @a __l.size()).
226 */
228 size_type __n = 0,
229 const hasher& __hf = hasher(),
230 const key_equal& __eql = key_equal(),
231 const allocator_type& __a = allocator_type())
232 : _M_h(__l, __n, __hf, __eql, __a)
233 { }
234
235 unordered_map(size_type __n, const allocator_type& __a)
236 : unordered_map(__n, hasher(), key_equal(), __a)
237 { }
238
239 unordered_map(size_type __n, const hasher& __hf,
240 const allocator_type& __a)
241 : unordered_map(__n, __hf, key_equal(), __a)
242 { }
243
244 template<typename _InputIterator>
245 unordered_map(_InputIterator __first, _InputIterator __last,
246 size_type __n,
247 const allocator_type& __a)
248 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
249 { }
250
251 template<typename _InputIterator>
252 unordered_map(_InputIterator __first, _InputIterator __last,
253 size_type __n, const hasher& __hf,
254 const allocator_type& __a)
255 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
256 { }
257
258 unordered_map(initializer_list<value_type> __l,
259 size_type __n,
260 const allocator_type& __a)
261 : unordered_map(__l, __n, hasher(), key_equal(), __a)
262 { }
263
264 unordered_map(initializer_list<value_type> __l,
265 size_type __n, const hasher& __hf,
266 const allocator_type& __a)
267 : unordered_map(__l, __n, __hf, key_equal(), __a)
268 { }
269
270 /// Copy assignment operator.
272 operator=(const unordered_map&) = default;
273
274 /// Move assignment operator.
277
278 /**
279 * @brief %Unordered_map list assignment operator.
280 * @param __l An initializer_list.
281 *
282 * This function fills an %unordered_map with copies of the elements in
283 * the initializer list @a __l.
284 *
285 * Note that the assignment completely changes the %unordered_map and
286 * that the resulting %unordered_map's size is the same as the number
287 * of elements assigned.
288 */
291 {
292 _M_h = __l;
293 return *this;
294 }
295
296 /// Returns the allocator object used by the %unordered_map.
298 get_allocator() const noexcept
299 { return _M_h.get_allocator(); }
300
301 // size and capacity:
302
303 /// Returns true if the %unordered_map is empty.
304 _GLIBCXX_NODISCARD bool
305 empty() const noexcept
306 { return _M_h.empty(); }
307
308 /// Returns the size of the %unordered_map.
310 size() const noexcept
311 { return _M_h.size(); }
312
313 /// Returns the maximum size of the %unordered_map.
315 max_size() const noexcept
316 { return _M_h.max_size(); }
317
318 // iterators.
319
320 /**
321 * Returns a read/write iterator that points to the first element in the
322 * %unordered_map.
323 */
325 begin() noexcept
326 { return _M_h.begin(); }
327
328 ///@{
329 /**
330 * Returns a read-only (constant) iterator that points to the first
331 * element in the %unordered_map.
332 */
334 begin() const noexcept
335 { return _M_h.begin(); }
336
338 cbegin() const noexcept
339 { return _M_h.begin(); }
340 ///@}
341
342 /**
343 * Returns a read/write iterator that points one past the last element in
344 * the %unordered_map.
345 */
347 end() noexcept
348 { return _M_h.end(); }
349
350 ///@{
351 /**
352 * Returns a read-only (constant) iterator that points one past the last
353 * element in the %unordered_map.
354 */
356 end() const noexcept
357 { return _M_h.end(); }
358
360 cend() const noexcept
361 { return _M_h.end(); }
362 ///@}
363
364 // modifiers.
365
366 /**
367 * @brief Attempts to build and insert a std::pair into the
368 * %unordered_map.
369 *
370 * @param __args Arguments used to generate a new pair instance (see
371 * std::piecewise_contruct for passing arguments to each
372 * part of the pair constructor).
373 *
374 * @return A pair, of which the first element is an iterator that points
375 * to the possibly inserted pair, and the second is a bool that
376 * is true if the pair was actually inserted.
377 *
378 * This function attempts to build and insert a (key, value) %pair into
379 * the %unordered_map.
380 * An %unordered_map relies on unique keys and thus a %pair is only
381 * inserted if its first element (the key) is not already present in the
382 * %unordered_map.
383 *
384 * Insertion requires amortized constant time.
385 */
386 template<typename... _Args>
388 emplace(_Args&&... __args)
389 { return _M_h.emplace(std::forward<_Args>(__args)...); }
390
391 /**
392 * @brief Attempts to build and insert a std::pair into the
393 * %unordered_map.
394 *
395 * @param __pos An iterator that serves as a hint as to where the pair
396 * should be inserted.
397 * @param __args Arguments used to generate a new pair instance (see
398 * std::piecewise_contruct for passing arguments to each
399 * part of the pair constructor).
400 * @return An iterator that points to the element with key of the
401 * std::pair built from @a __args (may or may not be that
402 * std::pair).
403 *
404 * This function is not concerned about whether the insertion took place,
405 * and thus does not return a boolean like the single-argument emplace()
406 * does.
407 * Note that the first parameter is only a hint and can potentially
408 * improve the performance of the insertion process. A bad hint would
409 * cause no gains in efficiency.
410 *
411 * See
412 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
413 * for more on @a hinting.
414 *
415 * Insertion requires amortized constant time.
416 */
417 template<typename... _Args>
419 emplace_hint(const_iterator __pos, _Args&&... __args)
420 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
421
422#if __cplusplus > 201402L
423 /// Extract a node.
424 node_type
425 extract(const_iterator __pos)
426 {
427 __glibcxx_assert(__pos != end());
428 return _M_h.extract(__pos);
429 }
430
431 /// Extract a node.
432 node_type
433 extract(const key_type& __key)
434 { return _M_h.extract(__key); }
435
436 /// Re-insert an extracted node.
437 insert_return_type
438 insert(node_type&& __nh)
439 { return _M_h._M_reinsert_node(std::move(__nh)); }
440
441 /// Re-insert an extracted node.
443 insert(const_iterator, node_type&& __nh)
444 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
445
446#define __cpp_lib_unordered_map_try_emplace 201411
447 /**
448 * @brief Attempts to build and insert a std::pair into the
449 * %unordered_map.
450 *
451 * @param __k Key to use for finding a possibly existing pair in
452 * the unordered_map.
453 * @param __args Arguments used to generate the .second for a
454 * new pair instance.
455 *
456 * @return A pair, of which the first element is an iterator that points
457 * to the possibly inserted pair, and the second is a bool that
458 * is true if the pair was actually inserted.
459 *
460 * This function attempts to build and insert a (key, value) %pair into
461 * the %unordered_map.
462 * An %unordered_map relies on unique keys and thus a %pair is only
463 * inserted if its first element (the key) is not already present in the
464 * %unordered_map.
465 * If a %pair is not inserted, this function has no effect.
466 *
467 * Insertion requires amortized constant time.
468 */
469 template <typename... _Args>
470 pair<iterator, bool>
471 try_emplace(const key_type& __k, _Args&&... __args)
472 {
473 iterator __i = find(__k);
474 if (__i == end())
475 {
479 std::forward<_Args>(__args)...))
480 .first;
481 return {__i, true};
482 }
483 return {__i, false};
484 }
485
486 // move-capable overload
487 template <typename... _Args>
488 pair<iterator, bool>
489 try_emplace(key_type&& __k, _Args&&... __args)
490 {
491 iterator __i = find(__k);
492 if (__i == end())
493 {
497 std::forward<_Args>(__args)...))
498 .first;
499 return {__i, true};
500 }
501 return {__i, false};
502 }
503
504 /**
505 * @brief Attempts to build and insert a std::pair into the
506 * %unordered_map.
507 *
508 * @param __hint An iterator that serves as a hint as to where the pair
509 * should be inserted.
510 * @param __k Key to use for finding a possibly existing pair in
511 * the unordered_map.
512 * @param __args Arguments used to generate the .second for a
513 * new pair instance.
514 * @return An iterator that points to the element with key of the
515 * std::pair built from @a __args (may or may not be that
516 * std::pair).
517 *
518 * This function is not concerned about whether the insertion took place,
519 * and thus does not return a boolean like the single-argument emplace()
520 * does. However, if insertion did not take place,
521 * this function has no effect.
522 * Note that the first parameter is only a hint and can potentially
523 * improve the performance of the insertion process. A bad hint would
524 * cause no gains in efficiency.
525 *
526 * See
527 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
528 * for more on @a hinting.
529 *
530 * Insertion requires amortized constant time.
531 */
532 template <typename... _Args>
534 try_emplace(const_iterator __hint, const key_type& __k,
535 _Args&&... __args)
536 {
537 iterator __i = find(__k);
538 if (__i == end())
542 std::forward<_Args>(__args)...));
543 return __i;
544 }
545
546 // move-capable overload
547 template <typename... _Args>
549 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
550 {
551 iterator __i = find(__k);
552 if (__i == end())
556 std::forward<_Args>(__args)...));
557 return __i;
558 }
559#endif // C++17
560
561 ///@{
562 /**
563 * @brief Attempts to insert a std::pair into the %unordered_map.
564
565 * @param __x Pair to be inserted (see std::make_pair for easy
566 * creation of pairs).
567 *
568 * @return A pair, of which the first element is an iterator that
569 * points to the possibly inserted pair, and the second is
570 * a bool that is true if the pair was actually inserted.
571 *
572 * This function attempts to insert a (key, value) %pair into the
573 * %unordered_map. An %unordered_map relies on unique keys and thus a
574 * %pair is only inserted if its first element (the key) is not already
575 * present in the %unordered_map.
576 *
577 * Insertion requires amortized constant time.
578 */
580 insert(const value_type& __x)
581 { return _M_h.insert(__x); }
582
583 // _GLIBCXX_RESOLVE_LIB_DEFECTS
584 // 2354. Unnecessary copying when inserting into maps with braced-init
587 { return _M_h.insert(std::move(__x)); }
588
589 template<typename _Pair>
590 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
592 insert(_Pair&& __x)
593 { return _M_h.emplace(std::forward<_Pair>(__x)); }
594 ///@}
595
596 ///@{
597 /**
598 * @brief Attempts to insert a std::pair into the %unordered_map.
599 * @param __hint An iterator that serves as a hint as to where the
600 * pair should be inserted.
601 * @param __x Pair to be inserted (see std::make_pair for easy creation
602 * of pairs).
603 * @return An iterator that points to the element with key of
604 * @a __x (may or may not be the %pair passed in).
605 *
606 * This function is not concerned about whether the insertion took place,
607 * and thus does not return a boolean like the single-argument insert()
608 * does. Note that the first parameter is only a hint and can
609 * potentially improve the performance of the insertion process. A bad
610 * hint would cause no gains in efficiency.
611 *
612 * See
613 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
614 * for more on @a hinting.
615 *
616 * Insertion requires amortized constant time.
617 */
619 insert(const_iterator __hint, const value_type& __x)
620 { return _M_h.insert(__hint, __x); }
621
622 // _GLIBCXX_RESOLVE_LIB_DEFECTS
623 // 2354. Unnecessary copying when inserting into maps with braced-init
626 { return _M_h.insert(__hint, std::move(__x)); }
627
628 template<typename _Pair>
629 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
630 insert(const_iterator __hint, _Pair&& __x)
631 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
632 ///@}
633
634 /**
635 * @brief A template function that attempts to insert a range of
636 * elements.
637 * @param __first Iterator pointing to the start of the range to be
638 * inserted.
639 * @param __last Iterator pointing to the end of the range.
640 *
641 * Complexity similar to that of the range constructor.
642 */
643 template<typename _InputIterator>
644 void
645 insert(_InputIterator __first, _InputIterator __last)
646 { _M_h.insert(__first, __last); }
647
648 /**
649 * @brief Attempts to insert a list of elements into the %unordered_map.
650 * @param __l A std::initializer_list<value_type> of elements
651 * to be inserted.
652 *
653 * Complexity similar to that of the range constructor.
654 */
655 void
657 { _M_h.insert(__l); }
658
659
660#if __cplusplus > 201402L
661 /**
662 * @brief Attempts to insert a std::pair into the %unordered_map.
663 * @param __k Key to use for finding a possibly existing pair in
664 * the map.
665 * @param __obj Argument used to generate the .second for a pair
666 * instance.
667 *
668 * @return A pair, of which the first element is an iterator that
669 * points to the possibly inserted pair, and the second is
670 * a bool that is true if the pair was actually inserted.
671 *
672 * This function attempts to insert a (key, value) %pair into the
673 * %unordered_map. An %unordered_map relies on unique keys and thus a
674 * %pair is only inserted if its first element (the key) is not already
675 * present in the %unordered_map.
676 * If the %pair was already in the %unordered_map, the .second of
677 * the %pair is assigned from __obj.
678 *
679 * Insertion requires amortized constant time.
680 */
681 template <typename _Obj>
683 insert_or_assign(const key_type& __k, _Obj&& __obj)
684 {
685 iterator __i = find(__k);
686 if (__i == end())
687 {
690 std::forward_as_tuple(std::forward<_Obj>(__obj)))
691 .first;
692 return {__i, true};
693 }
694 (*__i).second = std::forward<_Obj>(__obj);
695 return {__i, false};
696 }
697
698 // move-capable overload
699 template <typename _Obj>
700 pair<iterator, bool>
701 insert_or_assign(key_type&& __k, _Obj&& __obj)
702 {
703 iterator __i = find(__k);
704 if (__i == end())
705 {
708 std::forward_as_tuple(std::forward<_Obj>(__obj)))
709 .first;
710 return {__i, true};
711 }
712 (*__i).second = std::forward<_Obj>(__obj);
713 return {__i, false};
714 }
715
716 /**
717 * @brief Attempts to insert a std::pair into the %unordered_map.
718 * @param __hint An iterator that serves as a hint as to where the
719 * pair should be inserted.
720 * @param __k Key to use for finding a possibly existing pair in
721 * the unordered_map.
722 * @param __obj Argument used to generate the .second for a pair
723 * instance.
724 * @return An iterator that points to the element with key of
725 * @a __x (may or may not be the %pair passed in).
726 *
727 * This function is not concerned about whether the insertion took place,
728 * and thus does not return a boolean like the single-argument insert()
729 * does.
730 * If the %pair was already in the %unordered map, the .second of
731 * the %pair is assigned from __obj.
732 * Note that the first parameter is only a hint and can
733 * potentially improve the performance of the insertion process. A bad
734 * hint would cause no gains in efficiency.
735 *
736 * See
737 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
738 * for more on @a hinting.
739 *
740 * Insertion requires amortized constant time.
741 */
742 template <typename _Obj>
744 insert_or_assign(const_iterator __hint, const key_type& __k,
745 _Obj&& __obj)
746 {
747 iterator __i = find(__k);
748 if (__i == end())
749 {
753 std::forward<_Obj>(__obj)));
754 }
755 (*__i).second = std::forward<_Obj>(__obj);
756 return __i;
757 }
758
759 // move-capable overload
760 template <typename _Obj>
762 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
763 {
764 iterator __i = find(__k);
765 if (__i == end())
766 {
770 std::forward<_Obj>(__obj)));
771 }
772 (*__i).second = std::forward<_Obj>(__obj);
773 return __i;
774 }
775#endif
776
777 ///@{
778 /**
779 * @brief Erases an element from an %unordered_map.
780 * @param __position An iterator pointing to the element to be erased.
781 * @return An iterator pointing to the element immediately following
782 * @a __position prior to the element being erased. If no such
783 * element exists, end() is returned.
784 *
785 * This function erases an element, pointed to by the given iterator,
786 * from an %unordered_map.
787 * Note that this function only erases the element, and that if the
788 * element is itself a pointer, the pointed-to memory is not touched in
789 * any way. Managing the pointer is the user's responsibility.
790 */
793 { return _M_h.erase(__position); }
794
795 // LWG 2059.
797 erase(iterator __position)
798 { return _M_h.erase(__position); }
799 ///@}
800
801 /**
802 * @brief Erases elements according to the provided key.
803 * @param __x Key of element to be erased.
804 * @return The number of elements erased.
805 *
806 * This function erases all the elements located by the given key from
807 * an %unordered_map. For an %unordered_map the result of this function
808 * can only be 0 (not present) or 1 (present).
809 * Note that this function only erases the element, and that if the
810 * element is itself a pointer, the pointed-to memory is not touched in
811 * any way. Managing the pointer is the user's responsibility.
812 */
814 erase(const key_type& __x)
815 { return _M_h.erase(__x); }
816
817 /**
818 * @brief Erases a [__first,__last) range of elements from an
819 * %unordered_map.
820 * @param __first Iterator pointing to the start of the range to be
821 * erased.
822 * @param __last Iterator pointing to the end of the range to
823 * be erased.
824 * @return The iterator @a __last.
825 *
826 * This function erases a sequence of elements from an %unordered_map.
827 * Note that this function only erases the elements, and that if
828 * the element is itself a pointer, the pointed-to memory is not touched
829 * in any way. Managing the pointer is the user's responsibility.
830 */
833 { return _M_h.erase(__first, __last); }
834
835 /**
836 * Erases all elements in an %unordered_map.
837 * Note that this function only erases the elements, and that if the
838 * elements themselves are pointers, the pointed-to memory is not touched
839 * in any way. Managing the pointer is the user's responsibility.
840 */
841 void
842 clear() noexcept
843 { _M_h.clear(); }
844
845 /**
846 * @brief Swaps data with another %unordered_map.
847 * @param __x An %unordered_map of the same element and allocator
848 * types.
849 *
850 * This exchanges the elements between two %unordered_map in constant
851 * time.
852 * Note that the global std::swap() function is specialized such that
853 * std::swap(m1,m2) will feed to this function.
854 */
855 void
857 noexcept( noexcept(_M_h.swap(__x._M_h)) )
858 { _M_h.swap(__x._M_h); }
859
860#if __cplusplus > 201402L
861 template<typename, typename, typename>
862 friend class std::_Hash_merge_helper;
863
864 template<typename _H2, typename _P2>
865 void
867 {
868 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
869 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
870 }
871
872 template<typename _H2, typename _P2>
873 void
874 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
875 { merge(__source); }
876
877 template<typename _H2, typename _P2>
878 void
879 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
880 {
881 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
882 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
883 }
884
885 template<typename _H2, typename _P2>
886 void
887 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
888 { merge(__source); }
889#endif // C++17
890
891 // observers.
892
893 /// Returns the hash functor object with which the %unordered_map was
894 /// constructed.
895 hasher
897 { return _M_h.hash_function(); }
898
899 /// Returns the key comparison object with which the %unordered_map was
900 /// constructed.
902 key_eq() const
903 { return _M_h.key_eq(); }
904
905 // lookup.
906
907 ///@{
908 /**
909 * @brief Tries to locate an element in an %unordered_map.
910 * @param __x Key to be located.
911 * @return Iterator pointing to sought-after element, or end() if not
912 * found.
913 *
914 * This function takes a key and tries to locate the element with which
915 * the key matches. If successful the function returns an iterator
916 * pointing to the sought after element. If unsuccessful it returns the
917 * past-the-end ( @c end() ) iterator.
918 */
920 find(const key_type& __x)
921 { return _M_h.find(__x); }
922
924 find(const key_type& __x) const
925 { return _M_h.find(__x); }
926 ///@}
927
928 /**
929 * @brief Finds the number of elements.
930 * @param __x Key to count.
931 * @return Number of elements with specified key.
932 *
933 * This function only makes sense for %unordered_multimap; for
934 * %unordered_map the result will either be 0 (not present) or 1
935 * (present).
936 */
938 count(const key_type& __x) const
939 { return _M_h.count(__x); }
940
941#if __cplusplus > 201703L
942 /**
943 * @brief Finds whether an element with the given key exists.
944 * @param __x Key of elements to be located.
945 * @return True if there is any element with the specified key.
946 */
947 bool
948 contains(const key_type& __x) const
949 { return _M_h.find(__x) != _M_h.end(); }
950#endif
951
952 ///@{
953 /**
954 * @brief Finds a subsequence matching given key.
955 * @param __x Key to be located.
956 * @return Pair of iterators that possibly points to the subsequence
957 * matching given key.
958 *
959 * This function probably only makes sense for %unordered_multimap.
960 */
963 { return _M_h.equal_range(__x); }
964
966 equal_range(const key_type& __x) const
967 { return _M_h.equal_range(__x); }
968 ///@}
969
970 ///@{
971 /**
972 * @brief Subscript ( @c [] ) access to %unordered_map data.
973 * @param __k The key for which data should be retrieved.
974 * @return A reference to the data of the (key,data) %pair.
975 *
976 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
977 * data associated with the key specified in subscript. If the key does
978 * not exist, a pair with that key is created using default values, which
979 * is then returned.
980 *
981 * Lookup requires constant time.
982 */
985 { return _M_h[__k]; }
986
989 { return _M_h[std::move(__k)]; }
990 ///@}
991
992 ///@{
993 /**
994 * @brief Access to %unordered_map data.
995 * @param __k The key for which data should be retrieved.
996 * @return A reference to the data whose key is equal to @a __k, if
997 * such a data is present in the %unordered_map.
998 * @throw std::out_of_range If no such data is present.
999 */
1001 at(const key_type& __k)
1002 { return _M_h.at(__k); }
1003
1004 const mapped_type&
1005 at(const key_type& __k) const
1006 { return _M_h.at(__k); }
1007 ///@}
1008
1009 // bucket interface.
1010
1011 /// Returns the number of buckets of the %unordered_map.
1012 size_type
1013 bucket_count() const noexcept
1014 { return _M_h.bucket_count(); }
1015
1016 /// Returns the maximum number of buckets of the %unordered_map.
1017 size_type
1018 max_bucket_count() const noexcept
1019 { return _M_h.max_bucket_count(); }
1020
1021 /*
1022 * @brief Returns the number of elements in a given bucket.
1023 * @param __n A bucket index.
1024 * @return The number of elements in the bucket.
1025 */
1026 size_type
1027 bucket_size(size_type __n) const
1028 { return _M_h.bucket_size(__n); }
1029
1030 /*
1031 * @brief Returns the bucket index of a given element.
1032 * @param __key A key instance.
1033 * @return The key bucket index.
1034 */
1035 size_type
1036 bucket(const key_type& __key) const
1037 { return _M_h.bucket(__key); }
1038
1039 /**
1040 * @brief Returns a read/write iterator pointing to the first bucket
1041 * element.
1042 * @param __n The bucket index.
1043 * @return A read/write local iterator.
1044 */
1047 { return _M_h.begin(__n); }
1048
1049 ///@{
1050 /**
1051 * @brief Returns a read-only (constant) iterator pointing to the first
1052 * bucket element.
1053 * @param __n The bucket index.
1054 * @return A read-only local iterator.
1055 */
1057 begin(size_type __n) const
1058 { return _M_h.begin(__n); }
1059
1062 { return _M_h.cbegin(__n); }
1063 ///@}
1064
1065 /**
1066 * @brief Returns a read/write iterator pointing to one past the last
1067 * bucket elements.
1068 * @param __n The bucket index.
1069 * @return A read/write local iterator.
1070 */
1073 { return _M_h.end(__n); }
1074
1075 ///@{
1076 /**
1077 * @brief Returns a read-only (constant) iterator pointing to one past
1078 * the last bucket elements.
1079 * @param __n The bucket index.
1080 * @return A read-only local iterator.
1081 */
1083 end(size_type __n) const
1084 { return _M_h.end(__n); }
1085
1087 cend(size_type __n) const
1088 { return _M_h.cend(__n); }
1089 ///@}
1090
1091 // hash policy.
1092
1093 /// Returns the average number of elements per bucket.
1094 float
1095 load_factor() const noexcept
1096 { return _M_h.load_factor(); }
1097
1098 /// Returns a positive number that the %unordered_map tries to keep the
1099 /// load factor less than or equal to.
1100 float
1101 max_load_factor() const noexcept
1102 { return _M_h.max_load_factor(); }
1103
1104 /**
1105 * @brief Change the %unordered_map maximum load factor.
1106 * @param __z The new maximum load factor.
1107 */
1108 void
1110 { _M_h.max_load_factor(__z); }
1111
1112 /**
1113 * @brief May rehash the %unordered_map.
1114 * @param __n The new number of buckets.
1115 *
1116 * Rehash will occur only if the new number of buckets respect the
1117 * %unordered_map maximum load factor.
1118 */
1119 void
1121 { _M_h.rehash(__n); }
1122
1123 /**
1124 * @brief Prepare the %unordered_map for a specified number of
1125 * elements.
1126 * @param __n Number of elements required.
1127 *
1128 * Same as rehash(ceil(n / max_load_factor())).
1129 */
1130 void
1132 { _M_h.reserve(__n); }
1133
1134 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1135 typename _Alloc1>
1136 friend bool
1139 };
1140
1141#if __cpp_deduction_guides >= 201606
1142
1143 template<typename _InputIterator,
1144 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1145 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1146 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1147 typename = _RequireInputIter<_InputIterator>,
1148 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1149 typename = _RequireNotAllocator<_Pred>,
1150 typename = _RequireAllocator<_Allocator>>
1151 unordered_map(_InputIterator, _InputIterator,
1153 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1154 -> unordered_map<__iter_key_t<_InputIterator>,
1155 __iter_val_t<_InputIterator>,
1156 _Hash, _Pred, _Allocator>;
1157
1158 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1159 typename _Pred = equal_to<_Key>,
1160 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1161 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1162 typename = _RequireNotAllocator<_Pred>,
1163 typename = _RequireAllocator<_Allocator>>
1164 unordered_map(initializer_list<pair<_Key, _Tp>>,
1166 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1167 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1168
1169 template<typename _InputIterator, typename _Allocator,
1170 typename = _RequireInputIter<_InputIterator>,
1171 typename = _RequireAllocator<_Allocator>>
1172 unordered_map(_InputIterator, _InputIterator,
1173 typename unordered_map<int, int>::size_type, _Allocator)
1174 -> unordered_map<__iter_key_t<_InputIterator>,
1175 __iter_val_t<_InputIterator>,
1176 hash<__iter_key_t<_InputIterator>>,
1177 equal_to<__iter_key_t<_InputIterator>>,
1178 _Allocator>;
1179
1180 template<typename _InputIterator, typename _Allocator,
1181 typename = _RequireInputIter<_InputIterator>,
1182 typename = _RequireAllocator<_Allocator>>
1183 unordered_map(_InputIterator, _InputIterator, _Allocator)
1184 -> unordered_map<__iter_key_t<_InputIterator>,
1185 __iter_val_t<_InputIterator>,
1186 hash<__iter_key_t<_InputIterator>>,
1187 equal_to<__iter_key_t<_InputIterator>>,
1188 _Allocator>;
1189
1190 template<typename _InputIterator, typename _Hash, typename _Allocator,
1191 typename = _RequireInputIter<_InputIterator>,
1192 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1193 typename = _RequireAllocator<_Allocator>>
1194 unordered_map(_InputIterator, _InputIterator,
1196 _Hash, _Allocator)
1197 -> unordered_map<__iter_key_t<_InputIterator>,
1198 __iter_val_t<_InputIterator>, _Hash,
1199 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1200
1201 template<typename _Key, typename _Tp, typename _Allocator,
1202 typename = _RequireAllocator<_Allocator>>
1203 unordered_map(initializer_list<pair<_Key, _Tp>>,
1205 _Allocator)
1206 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1207
1208 template<typename _Key, typename _Tp, typename _Allocator,
1209 typename = _RequireAllocator<_Allocator>>
1210 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1211 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1212
1213 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1214 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1215 typename = _RequireAllocator<_Allocator>>
1216 unordered_map(initializer_list<pair<_Key, _Tp>>,
1218 _Hash, _Allocator)
1219 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1220
1221#endif
1222
1223 /**
1224 * @brief A standard container composed of equivalent keys
1225 * (possibly containing multiple of each key value) that associates
1226 * values of another type with the keys.
1227 *
1228 * @ingroup unordered_associative_containers
1229 *
1230 * @tparam _Key Type of key objects.
1231 * @tparam _Tp Type of mapped objects.
1232 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1233 * @tparam _Pred Predicate function object type, defaults
1234 * to equal_to<_Value>.
1235 * @tparam _Alloc Allocator type, defaults to
1236 * std::allocator<std::pair<const _Key, _Tp>>.
1237 *
1238 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1239 * <a href="tables.html#xx">unordered associative container</a>
1240 *
1241 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1242 *
1243 * Base is _Hashtable, dispatched at compile time via template
1244 * alias __ummap_hashtable.
1245 */
1246 template<typename _Key, typename _Tp,
1247 typename _Hash = hash<_Key>,
1248 typename _Pred = equal_to<_Key>,
1249 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1251 {
1253 _Hashtable _M_h;
1254
1255 public:
1256 // typedefs:
1257 ///@{
1258 /// Public typedefs.
1259 typedef typename _Hashtable::key_type key_type;
1260 typedef typename _Hashtable::value_type value_type;
1261 typedef typename _Hashtable::mapped_type mapped_type;
1262 typedef typename _Hashtable::hasher hasher;
1263 typedef typename _Hashtable::key_equal key_equal;
1264 typedef typename _Hashtable::allocator_type allocator_type;
1265 ///@}
1266
1267 ///@{
1268 /// Iterator-related typedefs.
1269 typedef typename _Hashtable::pointer pointer;
1270 typedef typename _Hashtable::const_pointer const_pointer;
1271 typedef typename _Hashtable::reference reference;
1272 typedef typename _Hashtable::const_reference const_reference;
1273 typedef typename _Hashtable::iterator iterator;
1274 typedef typename _Hashtable::const_iterator const_iterator;
1275 typedef typename _Hashtable::local_iterator local_iterator;
1276 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1277 typedef typename _Hashtable::size_type size_type;
1278 typedef typename _Hashtable::difference_type difference_type;
1279 ///@}
1280
1281#if __cplusplus > 201402L
1282 using node_type = typename _Hashtable::node_type;
1283#endif
1284
1285 //construct/destroy/copy
1286
1287 /// Default constructor.
1289
1290 /**
1291 * @brief Default constructor creates no elements.
1292 * @param __n Mnimal initial number of buckets.
1293 * @param __hf A hash functor.
1294 * @param __eql A key equality functor.
1295 * @param __a An allocator object.
1296 */
1297 explicit
1299 const hasher& __hf = hasher(),
1300 const key_equal& __eql = key_equal(),
1301 const allocator_type& __a = allocator_type())
1302 : _M_h(__n, __hf, __eql, __a)
1303 { }
1304
1305 /**
1306 * @brief Builds an %unordered_multimap from a range.
1307 * @param __first An input iterator.
1308 * @param __last An input iterator.
1309 * @param __n Minimal initial number of buckets.
1310 * @param __hf A hash functor.
1311 * @param __eql A key equality functor.
1312 * @param __a An allocator object.
1313 *
1314 * Create an %unordered_multimap consisting of copies of the elements
1315 * from [__first,__last). This is linear in N (where N is
1316 * distance(__first,__last)).
1317 */
1318 template<typename _InputIterator>
1319 unordered_multimap(_InputIterator __first, _InputIterator __last,
1320 size_type __n = 0,
1321 const hasher& __hf = hasher(),
1322 const key_equal& __eql = key_equal(),
1323 const allocator_type& __a = allocator_type())
1324 : _M_h(__first, __last, __n, __hf, __eql, __a)
1325 { }
1326
1327 /// Copy constructor.
1329
1330 /// Move constructor.
1332
1333 /**
1334 * @brief Creates an %unordered_multimap with no elements.
1335 * @param __a An allocator object.
1336 */
1337 explicit
1339 : _M_h(__a)
1340 { }
1341
1342 /*
1343 * @brief Copy constructor with allocator argument.
1344 * @param __uset Input %unordered_multimap to copy.
1345 * @param __a An allocator object.
1346 */
1348 const allocator_type& __a)
1349 : _M_h(__ummap._M_h, __a)
1350 { }
1351
1352 /*
1353 * @brief Move constructor with allocator argument.
1354 * @param __uset Input %unordered_multimap to move.
1355 * @param __a An allocator object.
1356 */
1358 const allocator_type& __a)
1359 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1360 : _M_h(std::move(__ummap._M_h), __a)
1361 { }
1362
1363 /**
1364 * @brief Builds an %unordered_multimap from an initializer_list.
1365 * @param __l An initializer_list.
1366 * @param __n Minimal initial number of buckets.
1367 * @param __hf A hash functor.
1368 * @param __eql A key equality functor.
1369 * @param __a An allocator object.
1370 *
1371 * Create an %unordered_multimap consisting of copies of the elements in
1372 * the list. This is linear in N (where N is @a __l.size()).
1373 */
1375 size_type __n = 0,
1376 const hasher& __hf = hasher(),
1377 const key_equal& __eql = key_equal(),
1378 const allocator_type& __a = allocator_type())
1379 : _M_h(__l, __n, __hf, __eql, __a)
1380 { }
1381
1383 : unordered_multimap(__n, hasher(), key_equal(), __a)
1384 { }
1385
1386 unordered_multimap(size_type __n, const hasher& __hf,
1387 const allocator_type& __a)
1388 : unordered_multimap(__n, __hf, key_equal(), __a)
1389 { }
1390
1391 template<typename _InputIterator>
1392 unordered_multimap(_InputIterator __first, _InputIterator __last,
1393 size_type __n,
1394 const allocator_type& __a)
1395 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1396 { }
1397
1398 template<typename _InputIterator>
1399 unordered_multimap(_InputIterator __first, _InputIterator __last,
1400 size_type __n, const hasher& __hf,
1401 const allocator_type& __a)
1402 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1403 { }
1404
1405 unordered_multimap(initializer_list<value_type> __l,
1406 size_type __n,
1407 const allocator_type& __a)
1408 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1409 { }
1410
1411 unordered_multimap(initializer_list<value_type> __l,
1412 size_type __n, const hasher& __hf,
1413 const allocator_type& __a)
1414 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1415 { }
1416
1417 /// Copy assignment operator.
1420
1421 /// Move assignment operator.
1424
1425 /**
1426 * @brief %Unordered_multimap list assignment operator.
1427 * @param __l An initializer_list.
1428 *
1429 * This function fills an %unordered_multimap with copies of the
1430 * elements in the initializer list @a __l.
1431 *
1432 * Note that the assignment completely changes the %unordered_multimap
1433 * and that the resulting %unordered_multimap's size is the same as the
1434 * number of elements assigned.
1435 */
1438 {
1439 _M_h = __l;
1440 return *this;
1441 }
1442
1443 /// Returns the allocator object used by the %unordered_multimap.
1445 get_allocator() const noexcept
1446 { return _M_h.get_allocator(); }
1447
1448 // size and capacity:
1449
1450 /// Returns true if the %unordered_multimap is empty.
1451 _GLIBCXX_NODISCARD bool
1452 empty() const noexcept
1453 { return _M_h.empty(); }
1454
1455 /// Returns the size of the %unordered_multimap.
1456 size_type
1457 size() const noexcept
1458 { return _M_h.size(); }
1459
1460 /// Returns the maximum size of the %unordered_multimap.
1461 size_type
1462 max_size() const noexcept
1463 { return _M_h.max_size(); }
1464
1465 // iterators.
1466
1467 /**
1468 * Returns a read/write iterator that points to the first element in the
1469 * %unordered_multimap.
1470 */
1471 iterator
1472 begin() noexcept
1473 { return _M_h.begin(); }
1474
1475 ///@{
1476 /**
1477 * Returns a read-only (constant) iterator that points to the first
1478 * element in the %unordered_multimap.
1479 */
1481 begin() const noexcept
1482 { return _M_h.begin(); }
1483
1485 cbegin() const noexcept
1486 { return _M_h.begin(); }
1487 ///@}
1488
1489 /**
1490 * Returns a read/write iterator that points one past the last element in
1491 * the %unordered_multimap.
1492 */
1493 iterator
1494 end() noexcept
1495 { return _M_h.end(); }
1496
1497 ///@{
1498 /**
1499 * Returns a read-only (constant) iterator that points one past the last
1500 * element in the %unordered_multimap.
1501 */
1503 end() const noexcept
1504 { return _M_h.end(); }
1505
1507 cend() const noexcept
1508 { return _M_h.end(); }
1509 ///@}
1510
1511 // modifiers.
1512
1513 /**
1514 * @brief Attempts to build and insert a std::pair into the
1515 * %unordered_multimap.
1516 *
1517 * @param __args Arguments used to generate a new pair instance (see
1518 * std::piecewise_contruct for passing arguments to each
1519 * part of the pair constructor).
1520 *
1521 * @return An iterator that points to the inserted pair.
1522 *
1523 * This function attempts to build and insert a (key, value) %pair into
1524 * the %unordered_multimap.
1525 *
1526 * Insertion requires amortized constant time.
1527 */
1528 template<typename... _Args>
1529 iterator
1530 emplace(_Args&&... __args)
1531 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1532
1533 /**
1534 * @brief Attempts to build and insert a std::pair into the
1535 * %unordered_multimap.
1536 *
1537 * @param __pos An iterator that serves as a hint as to where the pair
1538 * should be inserted.
1539 * @param __args Arguments used to generate a new pair instance (see
1540 * std::piecewise_contruct for passing arguments to each
1541 * part of the pair constructor).
1542 * @return An iterator that points to the element with key of the
1543 * std::pair built from @a __args.
1544 *
1545 * Note that the first parameter is only a hint and can potentially
1546 * improve the performance of the insertion process. A bad hint would
1547 * cause no gains in efficiency.
1548 *
1549 * See
1550 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1551 * for more on @a hinting.
1552 *
1553 * Insertion requires amortized constant time.
1554 */
1555 template<typename... _Args>
1556 iterator
1557 emplace_hint(const_iterator __pos, _Args&&... __args)
1558 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1559
1560 ///@{
1561 /**
1562 * @brief Inserts a std::pair into the %unordered_multimap.
1563 * @param __x Pair to be inserted (see std::make_pair for easy
1564 * creation of pairs).
1565 *
1566 * @return An iterator that points to the inserted pair.
1567 *
1568 * Insertion requires amortized constant time.
1569 */
1570 iterator
1571 insert(const value_type& __x)
1572 { return _M_h.insert(__x); }
1573
1574 iterator
1576 { return _M_h.insert(std::move(__x)); }
1577
1578 template<typename _Pair>
1579 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1580 insert(_Pair&& __x)
1581 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1582 ///@}
1583
1584 ///@{
1585 /**
1586 * @brief Inserts a std::pair into the %unordered_multimap.
1587 * @param __hint An iterator that serves as a hint as to where the
1588 * pair should be inserted.
1589 * @param __x Pair to be inserted (see std::make_pair for easy creation
1590 * of pairs).
1591 * @return An iterator that points to the element with key of
1592 * @a __x (may or may not be the %pair passed in).
1593 *
1594 * Note that the first parameter is only a hint and can potentially
1595 * improve the performance of the insertion process. A bad hint would
1596 * cause no gains in efficiency.
1597 *
1598 * See
1599 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1600 * for more on @a hinting.
1601 *
1602 * Insertion requires amortized constant time.
1603 */
1604 iterator
1606 { return _M_h.insert(__hint, __x); }
1607
1608 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1609 // 2354. Unnecessary copying when inserting into maps with braced-init
1610 iterator
1612 { return _M_h.insert(__hint, std::move(__x)); }
1613
1614 template<typename _Pair>
1615 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1616 insert(const_iterator __hint, _Pair&& __x)
1617 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1618 ///@}
1619
1620 /**
1621 * @brief A template function that attempts to insert a range of
1622 * elements.
1623 * @param __first Iterator pointing to the start of the range to be
1624 * inserted.
1625 * @param __last Iterator pointing to the end of the range.
1626 *
1627 * Complexity similar to that of the range constructor.
1628 */
1629 template<typename _InputIterator>
1630 void
1631 insert(_InputIterator __first, _InputIterator __last)
1632 { _M_h.insert(__first, __last); }
1633
1634 /**
1635 * @brief Attempts to insert a list of elements into the
1636 * %unordered_multimap.
1637 * @param __l A std::initializer_list<value_type> of elements
1638 * to be inserted.
1639 *
1640 * Complexity similar to that of the range constructor.
1641 */
1642 void
1644 { _M_h.insert(__l); }
1645
1646#if __cplusplus > 201402L
1647 /// Extract a node.
1648 node_type
1649 extract(const_iterator __pos)
1650 {
1651 __glibcxx_assert(__pos != end());
1652 return _M_h.extract(__pos);
1653 }
1654
1655 /// Extract a node.
1656 node_type
1657 extract(const key_type& __key)
1658 { return _M_h.extract(__key); }
1659
1660 /// Re-insert an extracted node.
1661 iterator
1662 insert(node_type&& __nh)
1663 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1664
1665 /// Re-insert an extracted node.
1666 iterator
1667 insert(const_iterator __hint, node_type&& __nh)
1668 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1669#endif // C++17
1670
1671 ///@{
1672 /**
1673 * @brief Erases an element from an %unordered_multimap.
1674 * @param __position An iterator pointing to the element to be erased.
1675 * @return An iterator pointing to the element immediately following
1676 * @a __position prior to the element being erased. If no such
1677 * element exists, end() is returned.
1678 *
1679 * This function erases an element, pointed to by the given iterator,
1680 * from an %unordered_multimap.
1681 * Note that this function only erases the element, and that if the
1682 * element is itself a pointer, the pointed-to memory is not touched in
1683 * any way. Managing the pointer is the user's responsibility.
1684 */
1685 iterator
1687 { return _M_h.erase(__position); }
1688
1689 // LWG 2059.
1690 iterator
1691 erase(iterator __position)
1692 { return _M_h.erase(__position); }
1693 ///@}
1694
1695 /**
1696 * @brief Erases elements according to the provided key.
1697 * @param __x Key of elements to be erased.
1698 * @return The number of elements erased.
1699 *
1700 * This function erases all the elements located by the given key from
1701 * an %unordered_multimap.
1702 * Note that this function only erases the element, and that if the
1703 * element is itself a pointer, the pointed-to memory is not touched in
1704 * any way. Managing the pointer is the user's responsibility.
1705 */
1706 size_type
1707 erase(const key_type& __x)
1708 { return _M_h.erase(__x); }
1709
1710 /**
1711 * @brief Erases a [__first,__last) range of elements from an
1712 * %unordered_multimap.
1713 * @param __first Iterator pointing to the start of the range to be
1714 * erased.
1715 * @param __last Iterator pointing to the end of the range to
1716 * be erased.
1717 * @return The iterator @a __last.
1718 *
1719 * This function erases a sequence of elements from an
1720 * %unordered_multimap.
1721 * Note that this function only erases the elements, and that if
1722 * the element is itself a pointer, the pointed-to memory is not touched
1723 * in any way. Managing the pointer is the user's responsibility.
1724 */
1725 iterator
1727 { return _M_h.erase(__first, __last); }
1728
1729 /**
1730 * Erases all elements in an %unordered_multimap.
1731 * Note that this function only erases the elements, and that if the
1732 * elements themselves are pointers, the pointed-to memory is not touched
1733 * in any way. Managing the pointer is the user's responsibility.
1734 */
1735 void
1736 clear() noexcept
1737 { _M_h.clear(); }
1738
1739 /**
1740 * @brief Swaps data with another %unordered_multimap.
1741 * @param __x An %unordered_multimap of the same element and allocator
1742 * types.
1743 *
1744 * This exchanges the elements between two %unordered_multimap in
1745 * constant time.
1746 * Note that the global std::swap() function is specialized such that
1747 * std::swap(m1,m2) will feed to this function.
1748 */
1749 void
1751 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1752 { _M_h.swap(__x._M_h); }
1753
1754#if __cplusplus > 201402L
1755 template<typename, typename, typename>
1756 friend class std::_Hash_merge_helper;
1757
1758 template<typename _H2, typename _P2>
1759 void
1761 {
1762 using _Merge_helper
1763 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1764 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1765 }
1766
1767 template<typename _H2, typename _P2>
1768 void
1769 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1770 { merge(__source); }
1771
1772 template<typename _H2, typename _P2>
1773 void
1774 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1775 {
1776 using _Merge_helper
1777 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1778 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1779 }
1780
1781 template<typename _H2, typename _P2>
1782 void
1783 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1784 { merge(__source); }
1785#endif // C++17
1786
1787 // observers.
1788
1789 /// Returns the hash functor object with which the %unordered_multimap
1790 /// was constructed.
1791 hasher
1793 { return _M_h.hash_function(); }
1794
1795 /// Returns the key comparison object with which the %unordered_multimap
1796 /// was constructed.
1797 key_equal
1798 key_eq() const
1799 { return _M_h.key_eq(); }
1800
1801 // lookup.
1802
1803 ///@{
1804 /**
1805 * @brief Tries to locate an element in an %unordered_multimap.
1806 * @param __x Key to be located.
1807 * @return Iterator pointing to sought-after element, or end() if not
1808 * found.
1809 *
1810 * This function takes a key and tries to locate the element with which
1811 * the key matches. If successful the function returns an iterator
1812 * pointing to the sought after element. If unsuccessful it returns the
1813 * past-the-end ( @c end() ) iterator.
1814 */
1815 iterator
1816 find(const key_type& __x)
1817 { return _M_h.find(__x); }
1818
1820 find(const key_type& __x) const
1821 { return _M_h.find(__x); }
1822 ///@}
1823
1824 /**
1825 * @brief Finds the number of elements.
1826 * @param __x Key to count.
1827 * @return Number of elements with specified key.
1828 */
1829 size_type
1830 count(const key_type& __x) const
1831 { return _M_h.count(__x); }
1832
1833#if __cplusplus > 201703L
1834 /**
1835 * @brief Finds whether an element with the given key exists.
1836 * @param __x Key of elements to be located.
1837 * @return True if there is any element with the specified key.
1838 */
1839 bool
1840 contains(const key_type& __x) const
1841 { return _M_h.find(__x) != _M_h.end(); }
1842#endif
1843
1844 ///@{
1845 /**
1846 * @brief Finds a subsequence matching given key.
1847 * @param __x Key to be located.
1848 * @return Pair of iterators that possibly points to the subsequence
1849 * matching given key.
1850 */
1853 { return _M_h.equal_range(__x); }
1854
1856 equal_range(const key_type& __x) const
1857 { return _M_h.equal_range(__x); }
1858 ///@}
1859
1860 // bucket interface.
1861
1862 /// Returns the number of buckets of the %unordered_multimap.
1863 size_type
1864 bucket_count() const noexcept
1865 { return _M_h.bucket_count(); }
1866
1867 /// Returns the maximum number of buckets of the %unordered_multimap.
1868 size_type
1869 max_bucket_count() const noexcept
1870 { return _M_h.max_bucket_count(); }
1871
1872 /*
1873 * @brief Returns the number of elements in a given bucket.
1874 * @param __n A bucket index.
1875 * @return The number of elements in the bucket.
1876 */
1877 size_type
1878 bucket_size(size_type __n) const
1879 { return _M_h.bucket_size(__n); }
1880
1881 /*
1882 * @brief Returns the bucket index of a given element.
1883 * @param __key A key instance.
1884 * @return The key bucket index.
1885 */
1886 size_type
1887 bucket(const key_type& __key) const
1888 { return _M_h.bucket(__key); }
1889
1890 /**
1891 * @brief Returns a read/write iterator pointing to the first bucket
1892 * element.
1893 * @param __n The bucket index.
1894 * @return A read/write local iterator.
1895 */
1898 { return _M_h.begin(__n); }
1899
1900 ///@{
1901 /**
1902 * @brief Returns a read-only (constant) iterator pointing to the first
1903 * bucket element.
1904 * @param __n The bucket index.
1905 * @return A read-only local iterator.
1906 */
1908 begin(size_type __n) const
1909 { return _M_h.begin(__n); }
1910
1913 { return _M_h.cbegin(__n); }
1914 ///@}
1915
1916 /**
1917 * @brief Returns a read/write iterator pointing to one past the last
1918 * bucket elements.
1919 * @param __n The bucket index.
1920 * @return A read/write local iterator.
1921 */
1924 { return _M_h.end(__n); }
1925
1926 ///@{
1927 /**
1928 * @brief Returns a read-only (constant) iterator pointing to one past
1929 * the last bucket elements.
1930 * @param __n The bucket index.
1931 * @return A read-only local iterator.
1932 */
1934 end(size_type __n) const
1935 { return _M_h.end(__n); }
1936
1938 cend(size_type __n) const
1939 { return _M_h.cend(__n); }
1940 ///@}
1941
1942 // hash policy.
1943
1944 /// Returns the average number of elements per bucket.
1945 float
1946 load_factor() const noexcept
1947 { return _M_h.load_factor(); }
1948
1949 /// Returns a positive number that the %unordered_multimap tries to keep
1950 /// the load factor less than or equal to.
1951 float
1952 max_load_factor() const noexcept
1953 { return _M_h.max_load_factor(); }
1954
1955 /**
1956 * @brief Change the %unordered_multimap maximum load factor.
1957 * @param __z The new maximum load factor.
1958 */
1959 void
1961 { _M_h.max_load_factor(__z); }
1962
1963 /**
1964 * @brief May rehash the %unordered_multimap.
1965 * @param __n The new number of buckets.
1966 *
1967 * Rehash will occur only if the new number of buckets respect the
1968 * %unordered_multimap maximum load factor.
1969 */
1970 void
1972 { _M_h.rehash(__n); }
1973
1974 /**
1975 * @brief Prepare the %unordered_multimap for a specified number of
1976 * elements.
1977 * @param __n Number of elements required.
1978 *
1979 * Same as rehash(ceil(n / max_load_factor())).
1980 */
1981 void
1983 { _M_h.reserve(__n); }
1984
1985 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1986 typename _Alloc1>
1987 friend bool
1988 operator==(const unordered_multimap<_Key1, _Tp1,
1989 _Hash1, _Pred1, _Alloc1>&,
1990 const unordered_multimap<_Key1, _Tp1,
1991 _Hash1, _Pred1, _Alloc1>&);
1992 };
1993
1994#if __cpp_deduction_guides >= 201606
1995
1996 template<typename _InputIterator,
1997 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1998 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1999 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2000 typename = _RequireInputIter<_InputIterator>,
2001 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2002 typename = _RequireNotAllocator<_Pred>,
2003 typename = _RequireAllocator<_Allocator>>
2004 unordered_multimap(_InputIterator, _InputIterator,
2006 _Hash = _Hash(), _Pred = _Pred(),
2007 _Allocator = _Allocator())
2008 -> unordered_multimap<__iter_key_t<_InputIterator>,
2009 __iter_val_t<_InputIterator>, _Hash, _Pred,
2010 _Allocator>;
2011
2012 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2013 typename _Pred = equal_to<_Key>,
2014 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2015 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2016 typename = _RequireNotAllocator<_Pred>,
2017 typename = _RequireAllocator<_Allocator>>
2018 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2020 _Hash = _Hash(), _Pred = _Pred(),
2021 _Allocator = _Allocator())
2022 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2023
2024 template<typename _InputIterator, typename _Allocator,
2025 typename = _RequireInputIter<_InputIterator>,
2026 typename = _RequireAllocator<_Allocator>>
2027 unordered_multimap(_InputIterator, _InputIterator,
2029 -> unordered_multimap<__iter_key_t<_InputIterator>,
2030 __iter_val_t<_InputIterator>,
2031 hash<__iter_key_t<_InputIterator>>,
2032 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2033
2034 template<typename _InputIterator, typename _Allocator,
2035 typename = _RequireInputIter<_InputIterator>,
2036 typename = _RequireAllocator<_Allocator>>
2037 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2038 -> unordered_multimap<__iter_key_t<_InputIterator>,
2039 __iter_val_t<_InputIterator>,
2040 hash<__iter_key_t<_InputIterator>>,
2041 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2042
2043 template<typename _InputIterator, typename _Hash, typename _Allocator,
2044 typename = _RequireInputIter<_InputIterator>,
2045 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2046 typename = _RequireAllocator<_Allocator>>
2047 unordered_multimap(_InputIterator, _InputIterator,
2049 _Allocator)
2050 -> unordered_multimap<__iter_key_t<_InputIterator>,
2051 __iter_val_t<_InputIterator>, _Hash,
2052 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2053
2054 template<typename _Key, typename _Tp, typename _Allocator,
2055 typename = _RequireAllocator<_Allocator>>
2056 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2058 _Allocator)
2059 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2060
2061 template<typename _Key, typename _Tp, typename _Allocator,
2062 typename = _RequireAllocator<_Allocator>>
2063 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2064 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2065
2066 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2067 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2068 typename = _RequireAllocator<_Allocator>>
2069 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2071 _Hash, _Allocator)
2072 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2073
2074#endif
2075
2076 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2077 inline void
2078 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2079 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2080 noexcept(noexcept(__x.swap(__y)))
2081 { __x.swap(__y); }
2082
2083 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2084 inline void
2085 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2086 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2087 noexcept(noexcept(__x.swap(__y)))
2088 { __x.swap(__y); }
2089
2090 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2091 inline bool
2092 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2093 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2094 { return __x._M_h._M_equal(__y._M_h); }
2095
2096#if __cpp_impl_three_way_comparison < 201907L
2097 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2098 inline bool
2099 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2100 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2101 { return !(__x == __y); }
2102#endif
2103
2104 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2105 inline bool
2106 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2107 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2108 { return __x._M_h._M_equal(__y._M_h); }
2109
2110#if __cpp_impl_three_way_comparison < 201907L
2111 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2112 inline bool
2113 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2114 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2115 { return !(__x == __y); }
2116#endif
2117
2118_GLIBCXX_END_NAMESPACE_CONTAINER
2119
2120#if __cplusplus > 201402L
2121 // Allow std::unordered_map access to internals of compatible maps.
2122 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2123 typename _Alloc, typename _Hash2, typename _Eq2>
2124 struct _Hash_merge_helper<
2125 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2126 _Hash2, _Eq2>
2127 {
2128 private:
2129 template<typename... _Tp>
2130 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2131 template<typename... _Tp>
2132 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2133
2134 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2135
2136 static auto&
2137 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2138 { return __map._M_h; }
2139
2140 static auto&
2141 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2142 { return __map._M_h; }
2143 };
2144
2145 // Allow std::unordered_multimap access to internals of compatible maps.
2146 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2147 typename _Alloc, typename _Hash2, typename _Eq2>
2148 struct _Hash_merge_helper<
2149 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2150 _Hash2, _Eq2>
2151 {
2152 private:
2153 template<typename... _Tp>
2154 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2155 template<typename... _Tp>
2156 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2157
2158 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2159
2160 static auto&
2161 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2162 { return __map._M_h; }
2163
2164 static auto&
2165 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2166 { return __map._M_h; }
2167 };
2168#endif // C++17
2169
2170_GLIBCXX_END_NAMESPACE_VERSION
2171} // namespace std
2172
2173#endif /* _UNORDERED_MAP_H */
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
Definition: tuple:1503
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
Definition: stl_pair.h:83
ISO C++ entities toplevel namespace is std.
initializer_list
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:123
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Common iterator class.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
float load_factor() const noexcept
Returns the average number of elements per bucket.
_Hashtable::reference reference
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_multimap.
const_iterator end() const noexcept
size_type erase(const key_type &__x)
Erases elements according to the provided key.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
_Hashtable::iterator iterator
Iterator-related typedefs.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
iterator begin() noexcept
const_iterator begin() const noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
size_type count(const key_type &__x) const
Finds the number of elements.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
_Hashtable::mapped_type mapped_type
Public typedefs.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
unordered_multimap(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
_Hashtable::value_type value_type
Public typedefs.
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
iterator end() noexcept
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
unordered_multimap()=default
Default constructor.
iterator insert(value_type &&__x)
Inserts a std::pair into the unordered_multimap.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from a range.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
unordered_multimap(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multimap from an initializer_list.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multimap.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::pointer pointer
Iterator-related typedefs.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
unordered_multimap(unordered_multimap &&)=default
Move constructor.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
void swap(unordered_multimap &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multimap.
void rehash(size_type __n)
May rehash the unordered_multimap.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
const_iterator cend() const noexcept
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
const_iterator cbegin() const noexcept
_Hashtable::key_type key_type
Public typedefs.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
size_type size() const noexcept
Returns the size of the unordered_multimap.
unordered_multimap(const unordered_multimap &)=default
Copy constructor.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts a std::pair into the unordered_multimap.
_Hashtable::key_equal key_equal
Public typedefs.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multimap.
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) that associat...
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::iterator iterator
Iterator-related typedefs.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_map.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
_Hashtable::reference reference
Iterator-related typedefs.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
iterator end() noexcept
_Hashtable::allocator_type allocator_type
Public typedefs.
unordered_map(const unordered_map &)=default
Copy constructor.
size_type count(const key_type &__x) const
Finds the number of elements.
bool empty() const noexcept
Returns true if the unordered_map is empty.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
unordered_map(unordered_map &&)=default
Move constructor.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
const_iterator end() const noexcept
unordered_map()=default
Default constructor.
_Hashtable::mapped_type mapped_type
Public typedefs.
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_map(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type size() const noexcept
Returns the size of the unordered_map.
__enable_if_t< is_constructible< value_type, _Pair && >::value, pair< iterator, bool > > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::hasher hasher
Public typedefs.
unordered_map(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from a range.
void clear() noexcept
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
const_iterator begin() const noexcept
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_map.
const_iterator cend() const noexcept
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
_Hashtable::pointer pointer
Iterator-related typedefs.
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
_Hashtable::key_type key_type
Public typedefs.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
iterator begin() noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
unordered_map(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_map from an initializer_list.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
float load_factor() const noexcept
Returns the average number of elements per bucket.
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
float max_load_factor() const noexcept
Returns a positive number that the unordered_map tries to keep the load factor less than or equal to.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
_Hashtable::value_type value_type
Public typedefs.
void rehash(size_type __n)
May rehash the unordered_map.
const_iterator cbegin() const noexcept