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