libstdc++
unordered_map.h
Go to the documentation of this file.
1// unordered_map implementation -*- C++ -*-
2
3// Copyright (C) 2010-2019 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 {
495 std::forward_as_tuple(std::move(__k)),
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())
554 std::forward_as_tuple(std::move(__k)),
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#define __cpp_lib_unordered_map_insertion 201411 // non-standard macro
662 /**
663 * @brief Attempts to insert a std::pair into the %unordered_map.
664 * @param __k Key to use for finding a possibly existing pair in
665 * the map.
666 * @param __obj Argument used to generate the .second for a pair
667 * instance.
668 *
669 * @return A pair, of which the first element is an iterator that
670 * points to the possibly inserted pair, and the second is
671 * a bool that is true if the pair was actually inserted.
672 *
673 * This function attempts to insert a (key, value) %pair into the
674 * %unordered_map. An %unordered_map relies on unique keys and thus a
675 * %pair is only inserted if its first element (the key) is not already
676 * present in the %unordered_map.
677 * If the %pair was already in the %unordered_map, the .second of
678 * the %pair is assigned from __obj.
679 *
680 * Insertion requires amortized constant time.
681 */
682 template <typename _Obj>
684 insert_or_assign(const key_type& __k, _Obj&& __obj)
685 {
686 iterator __i = find(__k);
687 if (__i == end())
688 {
691 std::forward_as_tuple(std::forward<_Obj>(__obj)))
692 .first;
693 return {__i, true};
694 }
695 (*__i).second = std::forward<_Obj>(__obj);
696 return {__i, false};
697 }
698
699 // move-capable overload
700 template <typename _Obj>
701 pair<iterator, bool>
702 insert_or_assign(key_type&& __k, _Obj&& __obj)
703 {
704 iterator __i = find(__k);
705 if (__i == end())
706 {
708 std::forward_as_tuple(std::move(__k)),
709 std::forward_as_tuple(std::forward<_Obj>(__obj)))
710 .first;
711 return {__i, true};
712 }
713 (*__i).second = std::forward<_Obj>(__obj);
714 return {__i, false};
715 }
716
717 /**
718 * @brief Attempts to insert a std::pair into the %unordered_map.
719 * @param __hint An iterator that serves as a hint as to where the
720 * pair should be inserted.
721 * @param __k Key to use for finding a possibly existing pair in
722 * the unordered_map.
723 * @param __obj Argument used to generate the .second for a pair
724 * instance.
725 * @return An iterator that points to the element with key of
726 * @a __x (may or may not be the %pair passed in).
727 *
728 * This function is not concerned about whether the insertion took place,
729 * and thus does not return a boolean like the single-argument insert()
730 * does.
731 * If the %pair was already in the %unordered map, the .second of
732 * the %pair is assigned from __obj.
733 * Note that the first parameter is only a hint and can
734 * potentially improve the performance of the insertion process. A bad
735 * hint would cause no gains in efficiency.
736 *
737 * See
738 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
739 * for more on @a hinting.
740 *
741 * Insertion requires amortized constant time.
742 */
743 template <typename _Obj>
745 insert_or_assign(const_iterator __hint, const key_type& __k,
746 _Obj&& __obj)
747 {
748 iterator __i = find(__k);
749 if (__i == end())
750 {
754 std::forward<_Obj>(__obj)));
755 }
756 (*__i).second = std::forward<_Obj>(__obj);
757 return __i;
758 }
759
760 // move-capable overload
761 template <typename _Obj>
763 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
764 {
765 iterator __i = find(__k);
766 if (__i == end())
767 {
769 std::forward_as_tuple(std::move(__k)),
771 std::forward<_Obj>(__obj)));
772 }
773 (*__i).second = std::forward<_Obj>(__obj);
774 return __i;
775 }
776#endif
777
778 ///@{
779 /**
780 * @brief Erases an element from an %unordered_map.
781 * @param __position An iterator pointing to the element to be erased.
782 * @return An iterator pointing to the element immediately following
783 * @a __position prior to the element being erased. If no such
784 * element exists, end() is returned.
785 *
786 * This function erases an element, pointed to by the given iterator,
787 * from an %unordered_map.
788 * Note that this function only erases the element, and that if the
789 * element is itself a pointer, the pointed-to memory is not touched in
790 * any way. Managing the pointer is the user's responsibility.
791 */
794 { return _M_h.erase(__position); }
795
796 // LWG 2059.
798 erase(iterator __position)
799 { return _M_h.erase(__position); }
800 ///@}
801
802 /**
803 * @brief Erases elements according to the provided key.
804 * @param __x Key of element to be erased.
805 * @return The number of elements erased.
806 *
807 * This function erases all the elements located by the given key from
808 * an %unordered_map. For an %unordered_map the result of this function
809 * can only be 0 (not present) or 1 (present).
810 * Note that this function only erases the element, and that if the
811 * element is itself a pointer, the pointed-to memory is not touched in
812 * any way. Managing the pointer is the user's responsibility.
813 */
815 erase(const key_type& __x)
816 { return _M_h.erase(__x); }
817
818 /**
819 * @brief Erases a [__first,__last) range of elements from an
820 * %unordered_map.
821 * @param __first Iterator pointing to the start of the range to be
822 * erased.
823 * @param __last Iterator pointing to the end of the range to
824 * be erased.
825 * @return The iterator @a __last.
826 *
827 * This function erases a sequence of elements from an %unordered_map.
828 * Note that this function only erases the elements, and that if
829 * the element is itself a pointer, the pointed-to memory is not touched
830 * in any way. Managing the pointer is the user's responsibility.
831 */
834 { return _M_h.erase(__first, __last); }
835
836 /**
837 * Erases all elements in an %unordered_map.
838 * Note that this function only erases the elements, and that if the
839 * elements themselves are pointers, the pointed-to memory is not touched
840 * in any way. Managing the pointer is the user's responsibility.
841 */
842 void
843 clear() noexcept
844 { _M_h.clear(); }
845
846 /**
847 * @brief Swaps data with another %unordered_map.
848 * @param __x An %unordered_map of the same element and allocator
849 * types.
850 *
851 * This exchanges the elements between two %unordered_map in constant
852 * time.
853 * Note that the global std::swap() function is specialized such that
854 * std::swap(m1,m2) will feed to this function.
855 */
856 void
858 noexcept( noexcept(_M_h.swap(__x._M_h)) )
859 { _M_h.swap(__x._M_h); }
860
861#if __cplusplus > 201402L
862 template<typename, typename, typename>
863 friend class std::_Hash_merge_helper;
864
865 template<typename _H2, typename _P2>
866 void
868 {
869 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
870 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
871 }
872
873 template<typename _H2, typename _P2>
874 void
875 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
876 { merge(__source); }
877
878 template<typename _H2, typename _P2>
879 void
880 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
881 {
882 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
883 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
884 }
885
886 template<typename _H2, typename _P2>
887 void
888 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
889 { merge(__source); }
890#endif // C++17
891
892 // observers.
893
894 /// Returns the hash functor object with which the %unordered_map was
895 /// constructed.
896 hasher
898 { return _M_h.hash_function(); }
899
900 /// Returns the key comparison object with which the %unordered_map was
901 /// constructed.
903 key_eq() const
904 { return _M_h.key_eq(); }
905
906 // lookup.
907
908 ///@{
909 /**
910 * @brief Tries to locate an element in an %unordered_map.
911 * @param __x Key to be located.
912 * @return Iterator pointing to sought-after element, or end() if not
913 * found.
914 *
915 * This function takes a key and tries to locate the element with which
916 * the key matches. If successful the function returns an iterator
917 * pointing to the sought after element. If unsuccessful it returns the
918 * past-the-end ( @c end() ) iterator.
919 */
921 find(const key_type& __x)
922 { return _M_h.find(__x); }
923
925 find(const key_type& __x) const
926 { return _M_h.find(__x); }
927 ///@}
928
929 /**
930 * @brief Finds the number of elements.
931 * @param __x Key to count.
932 * @return Number of elements with specified key.
933 *
934 * This function only makes sense for %unordered_multimap; for
935 * %unordered_map the result will either be 0 (not present) or 1
936 * (present).
937 */
939 count(const key_type& __x) const
940 { return _M_h.count(__x); }
941
942#if __cplusplus > 201703L
943 /**
944 * @brief Finds whether an element with the given key exists.
945 * @param __x Key of elements to be located.
946 * @return True if there is any element with the specified key.
947 */
948 bool
949 contains(const key_type& __x) const
950 { return _M_h.find(__x) != _M_h.end(); }
951#endif
952
953 ///@{
954 /**
955 * @brief Finds a subsequence matching given key.
956 * @param __x Key to be located.
957 * @return Pair of iterators that possibly points to the subsequence
958 * matching given key.
959 *
960 * This function probably only makes sense for %unordered_multimap.
961 */
964 { return _M_h.equal_range(__x); }
965
967 equal_range(const key_type& __x) const
968 { return _M_h.equal_range(__x); }
969 ///@}
970
971 ///@{
972 /**
973 * @brief Subscript ( @c [] ) access to %unordered_map data.
974 * @param __k The key for which data should be retrieved.
975 * @return A reference to the data of the (key,data) %pair.
976 *
977 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
978 * data associated with the key specified in subscript. If the key does
979 * not exist, a pair with that key is created using default values, which
980 * is then returned.
981 *
982 * Lookup requires constant time.
983 */
986 { return _M_h[__k]; }
987
990 { return _M_h[std::move(__k)]; }
991 ///@}
992
993 ///@{
994 /**
995 * @brief Access to %unordered_map data.
996 * @param __k The key for which data should be retrieved.
997 * @return A reference to the data whose key is equal to @a __k, if
998 * such a data is present in the %unordered_map.
999 * @throw std::out_of_range If no such data is present.
1000 */
1002 at(const key_type& __k)
1003 { return _M_h.at(__k); }
1004
1005 const mapped_type&
1006 at(const key_type& __k) const
1007 { return _M_h.at(__k); }
1008 ///@}
1009
1010 // bucket interface.
1011
1012 /// Returns the number of buckets of the %unordered_map.
1013 size_type
1014 bucket_count() const noexcept
1015 { return _M_h.bucket_count(); }
1016
1017 /// Returns the maximum number of buckets of the %unordered_map.
1018 size_type
1019 max_bucket_count() const noexcept
1020 { return _M_h.max_bucket_count(); }
1021
1022 /*
1023 * @brief Returns the number of elements in a given bucket.
1024 * @param __n A bucket index.
1025 * @return The number of elements in the bucket.
1026 */
1027 size_type
1028 bucket_size(size_type __n) const
1029 { return _M_h.bucket_size(__n); }
1030
1031 /*
1032 * @brief Returns the bucket index of a given element.
1033 * @param __key A key instance.
1034 * @return The key bucket index.
1035 */
1036 size_type
1037 bucket(const key_type& __key) const
1038 { return _M_h.bucket(__key); }
1039
1040 /**
1041 * @brief Returns a read/write iterator pointing to the first bucket
1042 * element.
1043 * @param __n The bucket index.
1044 * @return A read/write local iterator.
1045 */
1048 { return _M_h.begin(__n); }
1049
1050 ///@{
1051 /**
1052 * @brief Returns a read-only (constant) iterator pointing to the first
1053 * bucket element.
1054 * @param __n The bucket index.
1055 * @return A read-only local iterator.
1056 */
1058 begin(size_type __n) const
1059 { return _M_h.begin(__n); }
1060
1063 { return _M_h.cbegin(__n); }
1064 ///@}
1065
1066 /**
1067 * @brief Returns a read/write iterator pointing to one past the last
1068 * bucket elements.
1069 * @param __n The bucket index.
1070 * @return A read/write local iterator.
1071 */
1074 { return _M_h.end(__n); }
1075
1076 ///@{
1077 /**
1078 * @brief Returns a read-only (constant) iterator pointing to one past
1079 * the last bucket elements.
1080 * @param __n The bucket index.
1081 * @return A read-only local iterator.
1082 */
1084 end(size_type __n) const
1085 { return _M_h.end(__n); }
1086
1088 cend(size_type __n) const
1089 { return _M_h.cend(__n); }
1090 ///@}
1091
1092 // hash policy.
1093
1094 /// Returns the average number of elements per bucket.
1095 float
1096 load_factor() const noexcept
1097 { return _M_h.load_factor(); }
1098
1099 /// Returns a positive number that the %unordered_map tries to keep the
1100 /// load factor less than or equal to.
1101 float
1102 max_load_factor() const noexcept
1103 { return _M_h.max_load_factor(); }
1104
1105 /**
1106 * @brief Change the %unordered_map maximum load factor.
1107 * @param __z The new maximum load factor.
1108 */
1109 void
1111 { _M_h.max_load_factor(__z); }
1112
1113 /**
1114 * @brief May rehash the %unordered_map.
1115 * @param __n The new number of buckets.
1116 *
1117 * Rehash will occur only if the new number of buckets respect the
1118 * %unordered_map maximum load factor.
1119 */
1120 void
1122 { _M_h.rehash(__n); }
1123
1124 /**
1125 * @brief Prepare the %unordered_map for a specified number of
1126 * elements.
1127 * @param __n Number of elements required.
1128 *
1129 * Same as rehash(ceil(n / max_load_factor())).
1130 */
1131 void
1133 { _M_h.reserve(__n); }
1134
1135 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1136 typename _Alloc1>
1137 friend bool
1140 };
1141
1142#if __cpp_deduction_guides >= 201606
1143
1144 template<typename _InputIterator,
1145 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1146 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1147 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1148 typename = _RequireInputIter<_InputIterator>,
1149 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1150 typename = _RequireNotAllocator<_Pred>,
1151 typename = _RequireAllocator<_Allocator>>
1152 unordered_map(_InputIterator, _InputIterator,
1154 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1155 -> unordered_map<__iter_key_t<_InputIterator>,
1156 __iter_val_t<_InputIterator>,
1157 _Hash, _Pred, _Allocator>;
1158
1159 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1160 typename _Pred = equal_to<_Key>,
1161 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1162 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1163 typename = _RequireNotAllocator<_Pred>,
1164 typename = _RequireAllocator<_Allocator>>
1165 unordered_map(initializer_list<pair<_Key, _Tp>>,
1167 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1168 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1169
1170 template<typename _InputIterator, typename _Allocator,
1171 typename = _RequireInputIter<_InputIterator>,
1172 typename = _RequireAllocator<_Allocator>>
1173 unordered_map(_InputIterator, _InputIterator,
1174 typename unordered_map<int, int>::size_type, _Allocator)
1175 -> unordered_map<__iter_key_t<_InputIterator>,
1176 __iter_val_t<_InputIterator>,
1177 hash<__iter_key_t<_InputIterator>>,
1178 equal_to<__iter_key_t<_InputIterator>>,
1179 _Allocator>;
1180
1181 template<typename _InputIterator, typename _Allocator,
1182 typename = _RequireInputIter<_InputIterator>,
1183 typename = _RequireAllocator<_Allocator>>
1184 unordered_map(_InputIterator, _InputIterator, _Allocator)
1185 -> unordered_map<__iter_key_t<_InputIterator>,
1186 __iter_val_t<_InputIterator>,
1187 hash<__iter_key_t<_InputIterator>>,
1188 equal_to<__iter_key_t<_InputIterator>>,
1189 _Allocator>;
1190
1191 template<typename _InputIterator, typename _Hash, typename _Allocator,
1192 typename = _RequireInputIter<_InputIterator>,
1193 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1194 typename = _RequireAllocator<_Allocator>>
1195 unordered_map(_InputIterator, _InputIterator,
1197 _Hash, _Allocator)
1198 -> unordered_map<__iter_key_t<_InputIterator>,
1199 __iter_val_t<_InputIterator>, _Hash,
1200 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1201
1202 template<typename _Key, typename _Tp, typename _Allocator,
1203 typename = _RequireAllocator<_Allocator>>
1204 unordered_map(initializer_list<pair<_Key, _Tp>>,
1206 _Allocator)
1207 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1208
1209 template<typename _Key, typename _Tp, typename _Allocator,
1210 typename = _RequireAllocator<_Allocator>>
1211 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1212 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1213
1214 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1215 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1216 typename = _RequireAllocator<_Allocator>>
1217 unordered_map(initializer_list<pair<_Key, _Tp>>,
1219 _Hash, _Allocator)
1220 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1221
1222#endif
1223
1224 /**
1225 * @brief A standard container composed of equivalent keys
1226 * (possibly containing multiple of each key value) that associates
1227 * values of another type with the keys.
1228 *
1229 * @ingroup unordered_associative_containers
1230 *
1231 * @tparam _Key Type of key objects.
1232 * @tparam _Tp Type of mapped objects.
1233 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1234 * @tparam _Pred Predicate function object type, defaults
1235 * to equal_to<_Value>.
1236 * @tparam _Alloc Allocator type, defaults to
1237 * std::allocator<std::pair<const _Key, _Tp>>.
1238 *
1239 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1240 * <a href="tables.html#xx">unordered associative container</a>
1241 *
1242 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1243 *
1244 * Base is _Hashtable, dispatched at compile time via template
1245 * alias __ummap_hashtable.
1246 */
1247 template<typename _Key, typename _Tp,
1248 typename _Hash = hash<_Key>,
1249 typename _Pred = equal_to<_Key>,
1250 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1252 {
1254 _Hashtable _M_h;
1255
1256 public:
1257 // typedefs:
1258 ///@{
1259 /// Public typedefs.
1260 typedef typename _Hashtable::key_type key_type;
1261 typedef typename _Hashtable::value_type value_type;
1262 typedef typename _Hashtable::mapped_type mapped_type;
1263 typedef typename _Hashtable::hasher hasher;
1264 typedef typename _Hashtable::key_equal key_equal;
1265 typedef typename _Hashtable::allocator_type allocator_type;
1266 ///@}
1267
1268 ///@{
1269 /// Iterator-related typedefs.
1270 typedef typename _Hashtable::pointer pointer;
1271 typedef typename _Hashtable::const_pointer const_pointer;
1272 typedef typename _Hashtable::reference reference;
1273 typedef typename _Hashtable::const_reference const_reference;
1274 typedef typename _Hashtable::iterator iterator;
1275 typedef typename _Hashtable::const_iterator const_iterator;
1276 typedef typename _Hashtable::local_iterator local_iterator;
1277 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1278 typedef typename _Hashtable::size_type size_type;
1279 typedef typename _Hashtable::difference_type difference_type;
1280 ///@}
1281
1282#if __cplusplus > 201402L
1283 using node_type = typename _Hashtable::node_type;
1284#endif
1285
1286 //construct/destroy/copy
1287
1288 /// Default constructor.
1290
1291 /**
1292 * @brief Default constructor creates no elements.
1293 * @param __n Mnimal initial number of buckets.
1294 * @param __hf A hash functor.
1295 * @param __eql A key equality functor.
1296 * @param __a An allocator object.
1297 */
1298 explicit
1300 const hasher& __hf = hasher(),
1301 const key_equal& __eql = key_equal(),
1302 const allocator_type& __a = allocator_type())
1303 : _M_h(__n, __hf, __eql, __a)
1304 { }
1305
1306 /**
1307 * @brief Builds an %unordered_multimap from a range.
1308 * @param __first An input iterator.
1309 * @param __last An input iterator.
1310 * @param __n Minimal initial number of buckets.
1311 * @param __hf A hash functor.
1312 * @param __eql A key equality functor.
1313 * @param __a An allocator object.
1314 *
1315 * Create an %unordered_multimap consisting of copies of the elements
1316 * from [__first,__last). This is linear in N (where N is
1317 * distance(__first,__last)).
1318 */
1319 template<typename _InputIterator>
1320 unordered_multimap(_InputIterator __first, _InputIterator __last,
1321 size_type __n = 0,
1322 const hasher& __hf = hasher(),
1323 const key_equal& __eql = key_equal(),
1324 const allocator_type& __a = allocator_type())
1325 : _M_h(__first, __last, __n, __hf, __eql, __a)
1326 { }
1327
1328 /// Copy constructor.
1330
1331 /// Move constructor.
1333
1334 /**
1335 * @brief Creates an %unordered_multimap with no elements.
1336 * @param __a An allocator object.
1337 */
1338 explicit
1340 : _M_h(__a)
1341 { }
1342
1343 /*
1344 * @brief Copy constructor with allocator argument.
1345 * @param __uset Input %unordered_multimap to copy.
1346 * @param __a An allocator object.
1347 */
1349 const allocator_type& __a)
1350 : _M_h(__ummap._M_h, __a)
1351 { }
1352
1353 /*
1354 * @brief Move constructor with allocator argument.
1355 * @param __uset Input %unordered_multimap to move.
1356 * @param __a An allocator object.
1357 */
1359 const allocator_type& __a)
1360 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1361 : _M_h(std::move(__ummap._M_h), __a)
1362 { }
1363
1364 /**
1365 * @brief Builds an %unordered_multimap from an initializer_list.
1366 * @param __l An initializer_list.
1367 * @param __n Minimal initial number of buckets.
1368 * @param __hf A hash functor.
1369 * @param __eql A key equality functor.
1370 * @param __a An allocator object.
1371 *
1372 * Create an %unordered_multimap consisting of copies of the elements in
1373 * the list. This is linear in N (where N is @a __l.size()).
1374 */
1376 size_type __n = 0,
1377 const hasher& __hf = hasher(),
1378 const key_equal& __eql = key_equal(),
1379 const allocator_type& __a = allocator_type())
1380 : _M_h(__l, __n, __hf, __eql, __a)
1381 { }
1382
1384 : unordered_multimap(__n, hasher(), key_equal(), __a)
1385 { }
1386
1387 unordered_multimap(size_type __n, const hasher& __hf,
1388 const allocator_type& __a)
1389 : unordered_multimap(__n, __hf, key_equal(), __a)
1390 { }
1391
1392 template<typename _InputIterator>
1393 unordered_multimap(_InputIterator __first, _InputIterator __last,
1394 size_type __n,
1395 const allocator_type& __a)
1396 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1397 { }
1398
1399 template<typename _InputIterator>
1400 unordered_multimap(_InputIterator __first, _InputIterator __last,
1401 size_type __n, const hasher& __hf,
1402 const allocator_type& __a)
1403 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1404 { }
1405
1406 unordered_multimap(initializer_list<value_type> __l,
1407 size_type __n,
1408 const allocator_type& __a)
1409 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1410 { }
1411
1412 unordered_multimap(initializer_list<value_type> __l,
1413 size_type __n, const hasher& __hf,
1414 const allocator_type& __a)
1415 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1416 { }
1417
1418 /// Copy assignment operator.
1421
1422 /// Move assignment operator.
1425
1426 /**
1427 * @brief %Unordered_multimap list assignment operator.
1428 * @param __l An initializer_list.
1429 *
1430 * This function fills an %unordered_multimap with copies of the
1431 * elements in the initializer list @a __l.
1432 *
1433 * Note that the assignment completely changes the %unordered_multimap
1434 * and that the resulting %unordered_multimap's size is the same as the
1435 * number of elements assigned.
1436 */
1439 {
1440 _M_h = __l;
1441 return *this;
1442 }
1443
1444 /// Returns the allocator object used by the %unordered_multimap.
1446 get_allocator() const noexcept
1447 { return _M_h.get_allocator(); }
1448
1449 // size and capacity:
1450
1451 /// Returns true if the %unordered_multimap is empty.
1452 _GLIBCXX_NODISCARD bool
1453 empty() const noexcept
1454 { return _M_h.empty(); }
1455
1456 /// Returns the size of the %unordered_multimap.
1457 size_type
1458 size() const noexcept
1459 { return _M_h.size(); }
1460
1461 /// Returns the maximum size of the %unordered_multimap.
1462 size_type
1463 max_size() const noexcept
1464 { return _M_h.max_size(); }
1465
1466 // iterators.
1467
1468 /**
1469 * Returns a read/write iterator that points to the first element in the
1470 * %unordered_multimap.
1471 */
1472 iterator
1473 begin() noexcept
1474 { return _M_h.begin(); }
1475
1476 ///@{
1477 /**
1478 * Returns a read-only (constant) iterator that points to the first
1479 * element in the %unordered_multimap.
1480 */
1482 begin() const noexcept
1483 { return _M_h.begin(); }
1484
1486 cbegin() const noexcept
1487 { return _M_h.begin(); }
1488 ///@}
1489
1490 /**
1491 * Returns a read/write iterator that points one past the last element in
1492 * the %unordered_multimap.
1493 */
1494 iterator
1495 end() noexcept
1496 { return _M_h.end(); }
1497
1498 ///@{
1499 /**
1500 * Returns a read-only (constant) iterator that points one past the last
1501 * element in the %unordered_multimap.
1502 */
1504 end() const noexcept
1505 { return _M_h.end(); }
1506
1508 cend() const noexcept
1509 { return _M_h.end(); }
1510 ///@}
1511
1512 // modifiers.
1513
1514 /**
1515 * @brief Attempts to build and insert a std::pair into the
1516 * %unordered_multimap.
1517 *
1518 * @param __args Arguments used to generate a new pair instance (see
1519 * std::piecewise_contruct for passing arguments to each
1520 * part of the pair constructor).
1521 *
1522 * @return An iterator that points to the inserted pair.
1523 *
1524 * This function attempts to build and insert a (key, value) %pair into
1525 * the %unordered_multimap.
1526 *
1527 * Insertion requires amortized constant time.
1528 */
1529 template<typename... _Args>
1530 iterator
1531 emplace(_Args&&... __args)
1532 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1533
1534 /**
1535 * @brief Attempts to build and insert a std::pair into the
1536 * %unordered_multimap.
1537 *
1538 * @param __pos An iterator that serves as a hint as to where the pair
1539 * should be inserted.
1540 * @param __args Arguments used to generate a new pair instance (see
1541 * std::piecewise_contruct for passing arguments to each
1542 * part of the pair constructor).
1543 * @return An iterator that points to the element with key of the
1544 * std::pair built from @a __args.
1545 *
1546 * Note that the first parameter is only a hint and can potentially
1547 * improve the performance of the insertion process. A bad hint would
1548 * cause no gains in efficiency.
1549 *
1550 * See
1551 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1552 * for more on @a hinting.
1553 *
1554 * Insertion requires amortized constant time.
1555 */
1556 template<typename... _Args>
1557 iterator
1558 emplace_hint(const_iterator __pos, _Args&&... __args)
1559 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1560
1561 ///@{
1562 /**
1563 * @brief Inserts a std::pair into the %unordered_multimap.
1564 * @param __x Pair to be inserted (see std::make_pair for easy
1565 * creation of pairs).
1566 *
1567 * @return An iterator that points to the inserted pair.
1568 *
1569 * Insertion requires amortized constant time.
1570 */
1571 iterator
1572 insert(const value_type& __x)
1573 { return _M_h.insert(__x); }
1574
1575 iterator
1577 { return _M_h.insert(std::move(__x)); }
1578
1579 template<typename _Pair>
1580 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1581 insert(_Pair&& __x)
1582 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1583 ///@}
1584
1585 ///@{
1586 /**
1587 * @brief Inserts a std::pair into the %unordered_multimap.
1588 * @param __hint An iterator that serves as a hint as to where the
1589 * pair should be inserted.
1590 * @param __x Pair to be inserted (see std::make_pair for easy creation
1591 * of pairs).
1592 * @return An iterator that points to the element with key of
1593 * @a __x (may or may not be the %pair passed in).
1594 *
1595 * Note that the first parameter is only a hint and can potentially
1596 * improve the performance of the insertion process. A bad hint would
1597 * cause no gains in efficiency.
1598 *
1599 * See
1600 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1601 * for more on @a hinting.
1602 *
1603 * Insertion requires amortized constant time.
1604 */
1605 iterator
1607 { return _M_h.insert(__hint, __x); }
1608
1609 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1610 // 2354. Unnecessary copying when inserting into maps with braced-init
1611 iterator
1613 { return _M_h.insert(__hint, std::move(__x)); }
1614
1615 template<typename _Pair>
1616 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1617 insert(const_iterator __hint, _Pair&& __x)
1618 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1619 ///@}
1620
1621 /**
1622 * @brief A template function that attempts to insert a range of
1623 * elements.
1624 * @param __first Iterator pointing to the start of the range to be
1625 * inserted.
1626 * @param __last Iterator pointing to the end of the range.
1627 *
1628 * Complexity similar to that of the range constructor.
1629 */
1630 template<typename _InputIterator>
1631 void
1632 insert(_InputIterator __first, _InputIterator __last)
1633 { _M_h.insert(__first, __last); }
1634
1635 /**
1636 * @brief Attempts to insert a list of elements into the
1637 * %unordered_multimap.
1638 * @param __l A std::initializer_list<value_type> of elements
1639 * to be inserted.
1640 *
1641 * Complexity similar to that of the range constructor.
1642 */
1643 void
1645 { _M_h.insert(__l); }
1646
1647#if __cplusplus > 201402L
1648 /// Extract a node.
1649 node_type
1650 extract(const_iterator __pos)
1651 {
1652 __glibcxx_assert(__pos != end());
1653 return _M_h.extract(__pos);
1654 }
1655
1656 /// Extract a node.
1657 node_type
1658 extract(const key_type& __key)
1659 { return _M_h.extract(__key); }
1660
1661 /// Re-insert an extracted node.
1662 iterator
1663 insert(node_type&& __nh)
1664 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1665
1666 /// Re-insert an extracted node.
1667 iterator
1668 insert(const_iterator __hint, node_type&& __nh)
1669 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1670#endif // C++17
1671
1672 ///@{
1673 /**
1674 * @brief Erases an element from an %unordered_multimap.
1675 * @param __position An iterator pointing to the element to be erased.
1676 * @return An iterator pointing to the element immediately following
1677 * @a __position prior to the element being erased. If no such
1678 * element exists, end() is returned.
1679 *
1680 * This function erases an element, pointed to by the given iterator,
1681 * from an %unordered_multimap.
1682 * Note that this function only erases the element, and that if the
1683 * element is itself a pointer, the pointed-to memory is not touched in
1684 * any way. Managing the pointer is the user's responsibility.
1685 */
1686 iterator
1688 { return _M_h.erase(__position); }
1689
1690 // LWG 2059.
1691 iterator
1692 erase(iterator __position)
1693 { return _M_h.erase(__position); }
1694 ///@}
1695
1696 /**
1697 * @brief Erases elements according to the provided key.
1698 * @param __x Key of elements to be erased.
1699 * @return The number of elements erased.
1700 *
1701 * This function erases all the elements located by the given key from
1702 * an %unordered_multimap.
1703 * Note that this function only erases the element, and that if the
1704 * element is itself a pointer, the pointed-to memory is not touched in
1705 * any way. Managing the pointer is the user's responsibility.
1706 */
1707 size_type
1708 erase(const key_type& __x)
1709 { return _M_h.erase(__x); }
1710
1711 /**
1712 * @brief Erases a [__first,__last) range of elements from an
1713 * %unordered_multimap.
1714 * @param __first Iterator pointing to the start of the range to be
1715 * erased.
1716 * @param __last Iterator pointing to the end of the range to
1717 * be erased.
1718 * @return The iterator @a __last.
1719 *
1720 * This function erases a sequence of elements from an
1721 * %unordered_multimap.
1722 * Note that this function only erases the elements, and that if
1723 * the element is itself a pointer, the pointed-to memory is not touched
1724 * in any way. Managing the pointer is the user's responsibility.
1725 */
1726 iterator
1728 { return _M_h.erase(__first, __last); }
1729
1730 /**
1731 * Erases all elements in an %unordered_multimap.
1732 * Note that this function only erases the elements, and that if the
1733 * elements themselves are pointers, the pointed-to memory is not touched
1734 * in any way. Managing the pointer is the user's responsibility.
1735 */
1736 void
1737 clear() noexcept
1738 { _M_h.clear(); }
1739
1740 /**
1741 * @brief Swaps data with another %unordered_multimap.
1742 * @param __x An %unordered_multimap of the same element and allocator
1743 * types.
1744 *
1745 * This exchanges the elements between two %unordered_multimap in
1746 * constant time.
1747 * Note that the global std::swap() function is specialized such that
1748 * std::swap(m1,m2) will feed to this function.
1749 */
1750 void
1752 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1753 { _M_h.swap(__x._M_h); }
1754
1755#if __cplusplus > 201402L
1756 template<typename, typename, typename>
1757 friend class std::_Hash_merge_helper;
1758
1759 template<typename _H2, typename _P2>
1760 void
1762 {
1763 using _Merge_helper
1764 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1765 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1766 }
1767
1768 template<typename _H2, typename _P2>
1769 void
1770 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1771 { merge(__source); }
1772
1773 template<typename _H2, typename _P2>
1774 void
1775 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1776 {
1777 using _Merge_helper
1778 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1779 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1780 }
1781
1782 template<typename _H2, typename _P2>
1783 void
1784 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1785 { merge(__source); }
1786#endif // C++17
1787
1788 // observers.
1789
1790 /// Returns the hash functor object with which the %unordered_multimap
1791 /// was constructed.
1792 hasher
1794 { return _M_h.hash_function(); }
1795
1796 /// Returns the key comparison object with which the %unordered_multimap
1797 /// was constructed.
1798 key_equal
1799 key_eq() const
1800 { return _M_h.key_eq(); }
1801
1802 // lookup.
1803
1804 ///@{
1805 /**
1806 * @brief Tries to locate an element in an %unordered_multimap.
1807 * @param __x Key to be located.
1808 * @return Iterator pointing to sought-after element, or end() if not
1809 * found.
1810 *
1811 * This function takes a key and tries to locate the element with which
1812 * the key matches. If successful the function returns an iterator
1813 * pointing to the sought after element. If unsuccessful it returns the
1814 * past-the-end ( @c end() ) iterator.
1815 */
1816 iterator
1817 find(const key_type& __x)
1818 { return _M_h.find(__x); }
1819
1821 find(const key_type& __x) const
1822 { return _M_h.find(__x); }
1823 ///@}
1824
1825 /**
1826 * @brief Finds the number of elements.
1827 * @param __x Key to count.
1828 * @return Number of elements with specified key.
1829 */
1830 size_type
1831 count(const key_type& __x) const
1832 { return _M_h.count(__x); }
1833
1834#if __cplusplus > 201703L
1835 /**
1836 * @brief Finds whether an element with the given key exists.
1837 * @param __x Key of elements to be located.
1838 * @return True if there is any element with the specified key.
1839 */
1840 bool
1841 contains(const key_type& __x) const
1842 { return _M_h.find(__x) != _M_h.end(); }
1843#endif
1844
1845 ///@{
1846 /**
1847 * @brief Finds a subsequence matching given key.
1848 * @param __x Key to be located.
1849 * @return Pair of iterators that possibly points to the subsequence
1850 * matching given key.
1851 */
1854 { return _M_h.equal_range(__x); }
1855
1857 equal_range(const key_type& __x) const
1858 { return _M_h.equal_range(__x); }
1859 ///@}
1860
1861 // bucket interface.
1862
1863 /// Returns the number of buckets of the %unordered_multimap.
1864 size_type
1865 bucket_count() const noexcept
1866 { return _M_h.bucket_count(); }
1867
1868 /// Returns the maximum number of buckets of the %unordered_multimap.
1869 size_type
1870 max_bucket_count() const noexcept
1871 { return _M_h.max_bucket_count(); }
1872
1873 /*
1874 * @brief Returns the number of elements in a given bucket.
1875 * @param __n A bucket index.
1876 * @return The number of elements in the bucket.
1877 */
1878 size_type
1879 bucket_size(size_type __n) const
1880 { return _M_h.bucket_size(__n); }
1881
1882 /*
1883 * @brief Returns the bucket index of a given element.
1884 * @param __key A key instance.
1885 * @return The key bucket index.
1886 */
1887 size_type
1888 bucket(const key_type& __key) const
1889 { return _M_h.bucket(__key); }
1890
1891 /**
1892 * @brief Returns a read/write iterator pointing to the first bucket
1893 * element.
1894 * @param __n The bucket index.
1895 * @return A read/write local iterator.
1896 */
1899 { return _M_h.begin(__n); }
1900
1901 ///@{
1902 /**
1903 * @brief Returns a read-only (constant) iterator pointing to the first
1904 * bucket element.
1905 * @param __n The bucket index.
1906 * @return A read-only local iterator.
1907 */
1909 begin(size_type __n) const
1910 { return _M_h.begin(__n); }
1911
1914 { return _M_h.cbegin(__n); }
1915 ///@}
1916
1917 /**
1918 * @brief Returns a read/write iterator pointing to one past the last
1919 * bucket elements.
1920 * @param __n The bucket index.
1921 * @return A read/write local iterator.
1922 */
1925 { return _M_h.end(__n); }
1926
1927 ///@{
1928 /**
1929 * @brief Returns a read-only (constant) iterator pointing to one past
1930 * the last bucket elements.
1931 * @param __n The bucket index.
1932 * @return A read-only local iterator.
1933 */
1935 end(size_type __n) const
1936 { return _M_h.end(__n); }
1937
1939 cend(size_type __n) const
1940 { return _M_h.cend(__n); }
1941 ///@}
1942
1943 // hash policy.
1944
1945 /// Returns the average number of elements per bucket.
1946 float
1947 load_factor() const noexcept
1948 { return _M_h.load_factor(); }
1949
1950 /// Returns a positive number that the %unordered_multimap tries to keep
1951 /// the load factor less than or equal to.
1952 float
1953 max_load_factor() const noexcept
1954 { return _M_h.max_load_factor(); }
1955
1956 /**
1957 * @brief Change the %unordered_multimap maximum load factor.
1958 * @param __z The new maximum load factor.
1959 */
1960 void
1962 { _M_h.max_load_factor(__z); }
1963
1964 /**
1965 * @brief May rehash the %unordered_multimap.
1966 * @param __n The new number of buckets.
1967 *
1968 * Rehash will occur only if the new number of buckets respect the
1969 * %unordered_multimap maximum load factor.
1970 */
1971 void
1973 { _M_h.rehash(__n); }
1974
1975 /**
1976 * @brief Prepare the %unordered_multimap for a specified number of
1977 * elements.
1978 * @param __n Number of elements required.
1979 *
1980 * Same as rehash(ceil(n / max_load_factor())).
1981 */
1982 void
1984 { _M_h.reserve(__n); }
1985
1986 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1987 typename _Alloc1>
1988 friend bool
1989 operator==(const unordered_multimap<_Key1, _Tp1,
1990 _Hash1, _Pred1, _Alloc1>&,
1991 const unordered_multimap<_Key1, _Tp1,
1992 _Hash1, _Pred1, _Alloc1>&);
1993 };
1994
1995#if __cpp_deduction_guides >= 201606
1996
1997 template<typename _InputIterator,
1998 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1999 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2000 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2001 typename = _RequireInputIter<_InputIterator>,
2002 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2003 typename = _RequireNotAllocator<_Pred>,
2004 typename = _RequireAllocator<_Allocator>>
2005 unordered_multimap(_InputIterator, _InputIterator,
2007 _Hash = _Hash(), _Pred = _Pred(),
2008 _Allocator = _Allocator())
2009 -> unordered_multimap<__iter_key_t<_InputIterator>,
2010 __iter_val_t<_InputIterator>, _Hash, _Pred,
2011 _Allocator>;
2012
2013 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2014 typename _Pred = equal_to<_Key>,
2015 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2016 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2017 typename = _RequireNotAllocator<_Pred>,
2018 typename = _RequireAllocator<_Allocator>>
2019 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2021 _Hash = _Hash(), _Pred = _Pred(),
2022 _Allocator = _Allocator())
2023 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2024
2025 template<typename _InputIterator, typename _Allocator,
2026 typename = _RequireInputIter<_InputIterator>,
2027 typename = _RequireAllocator<_Allocator>>
2028 unordered_multimap(_InputIterator, _InputIterator,
2030 -> unordered_multimap<__iter_key_t<_InputIterator>,
2031 __iter_val_t<_InputIterator>,
2032 hash<__iter_key_t<_InputIterator>>,
2033 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2034
2035 template<typename _InputIterator, typename _Allocator,
2036 typename = _RequireInputIter<_InputIterator>,
2037 typename = _RequireAllocator<_Allocator>>
2038 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2039 -> unordered_multimap<__iter_key_t<_InputIterator>,
2040 __iter_val_t<_InputIterator>,
2041 hash<__iter_key_t<_InputIterator>>,
2042 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2043
2044 template<typename _InputIterator, typename _Hash, typename _Allocator,
2045 typename = _RequireInputIter<_InputIterator>,
2046 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2047 typename = _RequireAllocator<_Allocator>>
2048 unordered_multimap(_InputIterator, _InputIterator,
2050 _Allocator)
2051 -> unordered_multimap<__iter_key_t<_InputIterator>,
2052 __iter_val_t<_InputIterator>, _Hash,
2053 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2054
2055 template<typename _Key, typename _Tp, typename _Allocator,
2056 typename = _RequireAllocator<_Allocator>>
2057 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2059 _Allocator)
2060 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2061
2062 template<typename _Key, typename _Tp, typename _Allocator,
2063 typename = _RequireAllocator<_Allocator>>
2064 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2065 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2066
2067 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2068 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2069 typename = _RequireAllocator<_Allocator>>
2070 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2072 _Hash, _Allocator)
2073 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2074
2075#endif
2076
2077 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2078 inline void
2079 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2080 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2081 noexcept(noexcept(__x.swap(__y)))
2082 { __x.swap(__y); }
2083
2084 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2085 inline void
2086 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2087 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2088 noexcept(noexcept(__x.swap(__y)))
2089 { __x.swap(__y); }
2090
2091 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2092 inline bool
2093 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2094 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2095 { return __x._M_h._M_equal(__y._M_h); }
2096
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
2103 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2104 inline bool
2105 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2106 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2107 { return __x._M_h._M_equal(__y._M_h); }
2108
2109 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2110 inline bool
2111 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2112 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2113 { return !(__x == __y); }
2114
2115_GLIBCXX_END_NAMESPACE_CONTAINER
2116
2117#if __cplusplus > 201402L
2118 // Allow std::unordered_map access to internals of compatible maps.
2119 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2120 typename _Alloc, typename _Hash2, typename _Eq2>
2121 struct _Hash_merge_helper<
2122 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2123 _Hash2, _Eq2>
2124 {
2125 private:
2126 template<typename... _Tp>
2127 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2128 template<typename... _Tp>
2129 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2130
2131 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2132
2133 static auto&
2134 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2135 { return __map._M_h; }
2136
2137 static auto&
2138 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2139 { return __map._M_h; }
2140 };
2141
2142 // Allow std::unordered_multimap access to internals of compatible maps.
2143 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2144 typename _Alloc, typename _Hash2, typename _Eq2>
2145 struct _Hash_merge_helper<
2146 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2147 _Hash2, _Eq2>
2148 {
2149 private:
2150 template<typename... _Tp>
2151 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2152 template<typename... _Tp>
2153 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2154
2155 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2156
2157 static auto&
2158 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2159 { return __map._M_h; }
2160
2161 static auto&
2162 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2163 { return __map._M_h; }
2164 };
2165#endif // C++17
2166
2167_GLIBCXX_END_NAMESPACE_VERSION
2168} // namespace std
2169
2170#endif /* _UNORDERED_MAP_H */
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
Definition: tuple:1482
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
ISO C++ entities toplevel namespace is std.
initializer_list
Primary class template hash.
The standard allocator, as per [20.4].
Definition: allocator.h:112
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:210
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.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_multimap is empty.
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.
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.
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.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_map is empty.
_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