libstdc++
unordered_map.h
Go to the documentation of this file.
1// unordered_map implementation -*- C++ -*-
2
3// Copyright (C) 2010-2024 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#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
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 */
217 unordered_map(unordered_map&& __umap,
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.
278 unordered_map&
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.
304 allocator_type
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.
316 size_type
317 size() const noexcept
318 { return _M_h.size(); }
319
320 /// Returns the maximum size of the %unordered_map.
321 size_type
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 */
340 const_iterator
341 begin() const noexcept
342 { return _M_h.begin(); }
343
344 const_iterator
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 */
362 const_iterator
363 end() const noexcept
364 { return _M_h.end(); }
365
366 const_iterator
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#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
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#endif // node_extract
453
454#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
455 /**
456 * @brief Attempts to build and insert a std::pair into the
457 * %unordered_map.
458 *
459 * @param __k Key to use for finding a possibly existing pair in
460 * the unordered_map.
461 * @param __args Arguments used to generate the .second for a
462 * new pair instance.
463 *
464 * @return A pair, of which the first element is an iterator that points
465 * to the possibly inserted pair, and the second is a bool that
466 * is true if the pair was actually inserted.
467 *
468 * This function attempts to build and insert a (key, value) %pair into
469 * the %unordered_map.
470 * An %unordered_map relies on unique keys and thus a %pair is only
471 * inserted if its first element (the key) is not already present in the
472 * %unordered_map.
473 * If a %pair is not inserted, this function has no effect.
474 *
475 * Insertion requires amortized constant time.
476 */
477 template <typename... _Args>
479 try_emplace(const key_type& __k, _Args&&... __args)
480 {
481 return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
482 }
483
484 // move-capable overload
485 template <typename... _Args>
487 try_emplace(key_type&& __k, _Args&&... __args)
488 {
489 return _M_h.try_emplace(cend(), std::move(__k),
490 std::forward<_Args>(__args)...);
491 }
492
493 /**
494 * @brief Attempts to build and insert a std::pair into the
495 * %unordered_map.
496 *
497 * @param __hint An iterator that serves as a hint as to where the pair
498 * should be inserted.
499 * @param __k Key to use for finding a possibly existing pair in
500 * the unordered_map.
501 * @param __args Arguments used to generate the .second for a
502 * new pair instance.
503 * @return An iterator that points to the element with key of the
504 * std::pair built from @a __args (may or may not be that
505 * std::pair).
506 *
507 * This function is not concerned about whether the insertion took place,
508 * and thus does not return a boolean like the single-argument emplace()
509 * does. However, if insertion did not take place,
510 * this function has no effect.
511 * Note that the first parameter is only a hint and can potentially
512 * improve the performance of the insertion process. A bad hint would
513 * cause no gains in efficiency.
514 *
515 * See
516 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
517 * for more on @a hinting.
518 *
519 * Insertion requires amortized constant time.
520 */
521 template <typename... _Args>
522 iterator
524 _Args&&... __args)
525 {
526 return _M_h.try_emplace(__hint, __k,
527 std::forward<_Args>(__args)...).first;
528 }
529
530 // move-capable overload
531 template <typename... _Args>
533 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
534 {
535 return _M_h.try_emplace(__hint, std::move(__k),
536 std::forward<_Args>(__args)...).first;
537 }
538#endif // __glibcxx_unordered_map_try_emplace
539
540 ///@{
541 /**
542 * @brief Attempts to insert a std::pair into the %unordered_map.
543
544 * @param __x Pair to be inserted (see std::make_pair for easy
545 * creation of pairs).
546 *
547 * @return A pair, of which the first element is an iterator that
548 * points to the possibly inserted pair, and the second is
549 * a bool that is true if the pair was actually inserted.
550 *
551 * This function attempts to insert a (key, value) %pair into the
552 * %unordered_map. An %unordered_map relies on unique keys and thus a
553 * %pair is only inserted if its first element (the key) is not already
554 * present in the %unordered_map.
555 *
556 * Insertion requires amortized constant time.
557 */
559 insert(const value_type& __x)
560 { return _M_h.insert(__x); }
561
562 // _GLIBCXX_RESOLVE_LIB_DEFECTS
563 // 2354. Unnecessary copying when inserting into maps with braced-init
566 { return _M_h.insert(std::move(__x)); }
567
568 template<typename _Pair>
569 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
571 insert(_Pair&& __x)
572 { return _M_h.emplace(std::forward<_Pair>(__x)); }
573 ///@}
574
575 ///@{
576 /**
577 * @brief Attempts to insert a std::pair into the %unordered_map.
578 * @param __hint An iterator that serves as a hint as to where the
579 * pair should be inserted.
580 * @param __x Pair to be inserted (see std::make_pair for easy creation
581 * of pairs).
582 * @return An iterator that points to the element with key of
583 * @a __x (may or may not be the %pair passed in).
584 *
585 * This function is not concerned about whether the insertion took place,
586 * and thus does not return a boolean like the single-argument insert()
587 * does. Note that the first parameter is only a hint and can
588 * potentially improve the performance of the insertion process. A bad
589 * hint would cause no gains in efficiency.
590 *
591 * See
592 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
593 * for more on @a hinting.
594 *
595 * Insertion requires amortized constant time.
596 */
598 insert(const_iterator __hint, const value_type& __x)
599 { return _M_h.insert(__hint, __x); }
600
601 // _GLIBCXX_RESOLVE_LIB_DEFECTS
602 // 2354. Unnecessary copying when inserting into maps with braced-init
605 { return _M_h.insert(__hint, std::move(__x)); }
606
607 template<typename _Pair>
608 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
609 insert(const_iterator __hint, _Pair&& __x)
610 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
611 ///@}
612
613 /**
614 * @brief A template function that attempts to insert a range of
615 * elements.
616 * @param __first Iterator pointing to the start of the range to be
617 * inserted.
618 * @param __last Iterator pointing to the end of the range.
619 *
620 * Complexity similar to that of the range constructor.
621 */
622 template<typename _InputIterator>
623 void
624 insert(_InputIterator __first, _InputIterator __last)
625 { _M_h.insert(__first, __last); }
626
627 /**
628 * @brief Attempts to insert a list of elements into the %unordered_map.
629 * @param __l A std::initializer_list<value_type> of elements
630 * to be inserted.
631 *
632 * Complexity similar to that of the range constructor.
633 */
634 void
636 { _M_h.insert(__l); }
637
638
639#ifdef __glibcxx_unordered_map_try_emplace // >= C++17 && HOSTED
640 /**
641 * @brief Attempts to insert a std::pair into the %unordered_map.
642 * @param __k Key to use for finding a possibly existing pair in
643 * the map.
644 * @param __obj Argument used to generate the .second for a pair
645 * instance.
646 *
647 * @return A pair, of which the first element is an iterator that
648 * points to the possibly inserted pair, and the second is
649 * a bool that is true if the pair was actually inserted.
650 *
651 * This function attempts to insert a (key, value) %pair into the
652 * %unordered_map. An %unordered_map relies on unique keys and thus a
653 * %pair is only inserted if its first element (the key) is not already
654 * present in the %unordered_map.
655 * If the %pair was already in the %unordered_map, the .second of
656 * the %pair is assigned from __obj.
657 *
658 * Insertion requires amortized constant time.
659 */
660 template <typename _Obj>
662 insert_or_assign(const key_type& __k, _Obj&& __obj)
663 {
664 auto __ret = _M_h.try_emplace(cend(), __k,
665 std::forward<_Obj>(__obj));
666 if (!__ret.second)
667 __ret.first->second = std::forward<_Obj>(__obj);
668 return __ret;
669 }
670
671 // move-capable overload
672 template <typename _Obj>
674 insert_or_assign(key_type&& __k, _Obj&& __obj)
675 {
676 auto __ret = _M_h.try_emplace(cend(), std::move(__k),
677 std::forward<_Obj>(__obj));
678 if (!__ret.second)
679 __ret.first->second = std::forward<_Obj>(__obj);
680 return __ret;
681 }
682
683 /**
684 * @brief Attempts to insert a std::pair into the %unordered_map.
685 * @param __hint An iterator that serves as a hint as to where the
686 * pair should be inserted.
687 * @param __k Key to use for finding a possibly existing pair in
688 * the unordered_map.
689 * @param __obj Argument used to generate the .second for a pair
690 * instance.
691 * @return An iterator that points to the element with key of
692 * @a __x (may or may not be the %pair passed in).
693 *
694 * This function is not concerned about whether the insertion took place,
695 * and thus does not return a boolean like the single-argument insert()
696 * does.
697 * If the %pair was already in the %unordered map, the .second of
698 * the %pair is assigned from __obj.
699 * Note that the first parameter is only a hint and can
700 * potentially improve the performance of the insertion process. A bad
701 * hint would cause no gains in efficiency.
702 *
703 * See
704 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
705 * for more on @a hinting.
706 *
707 * Insertion requires amortized constant time.
708 */
709 template <typename _Obj>
710 iterator
712 _Obj&& __obj)
713 {
714 auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
715 if (!__ret.second)
716 __ret.first->second = std::forward<_Obj>(__obj);
717 return __ret.first;
718 }
719
720 // move-capable overload
721 template <typename _Obj>
723 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
724 {
725 auto __ret = _M_h.try_emplace(__hint, std::move(__k),
726 std::forward<_Obj>(__obj));
727 if (!__ret.second)
728 __ret.first->second = std::forward<_Obj>(__obj);
729 return __ret.first;
730 }
731#endif // unordered_map_try_emplace
732
733 ///@{
734 /**
735 * @brief Erases an element from an %unordered_map.
736 * @param __position An iterator pointing to the element to be erased.
737 * @return An iterator pointing to the element immediately following
738 * @a __position prior to the element being erased. If no such
739 * element exists, end() is returned.
740 *
741 * This function erases an element, pointed to by the given iterator,
742 * from an %unordered_map.
743 * Note that this function only erases the element, and that if the
744 * element is itself a pointer, the pointed-to memory is not touched in
745 * any way. Managing the pointer is the user's responsibility.
746 */
747 iterator
749 { return _M_h.erase(__position); }
750
751 // LWG 2059.
753 erase(iterator __position)
754 { return _M_h.erase(__position); }
755 ///@}
756
757 /**
758 * @brief Erases elements according to the provided key.
759 * @param __x Key of element to be erased.
760 * @return The number of elements erased.
761 *
762 * This function erases all the elements located by the given key from
763 * an %unordered_map. For an %unordered_map the result of this function
764 * can only be 0 (not present) or 1 (present).
765 * Note that this function only erases the element, and that if the
766 * element is itself a pointer, the pointed-to memory is not touched in
767 * any way. Managing the pointer is the user's responsibility.
768 */
769 size_type
770 erase(const key_type& __x)
771 { return _M_h.erase(__x); }
772
773 /**
774 * @brief Erases a [__first,__last) range of elements from an
775 * %unordered_map.
776 * @param __first Iterator pointing to the start of the range to be
777 * erased.
778 * @param __last Iterator pointing to the end of the range to
779 * be erased.
780 * @return The iterator @a __last.
781 *
782 * This function erases a sequence of elements from an %unordered_map.
783 * Note that this function only erases the elements, and that if
784 * the element is itself a pointer, the pointed-to memory is not touched
785 * in any way. Managing the pointer is the user's responsibility.
786 */
789 { return _M_h.erase(__first, __last); }
790
791 /**
792 * Erases all elements in an %unordered_map.
793 * Note that this function only erases the elements, and that if the
794 * elements themselves are pointers, the pointed-to memory is not touched
795 * in any way. Managing the pointer is the user's responsibility.
796 */
797 void
798 clear() noexcept
799 { _M_h.clear(); }
800
801 /**
802 * @brief Swaps data with another %unordered_map.
803 * @param __x An %unordered_map of the same element and allocator
804 * types.
805 *
806 * This exchanges the elements between two %unordered_map in constant
807 * time.
808 * Note that the global std::swap() function is specialized such that
809 * std::swap(m1,m2) will feed to this function.
810 */
811 void
813 noexcept( noexcept(_M_h.swap(__x._M_h)) )
814 { _M_h.swap(__x._M_h); }
815
816#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
817 template<typename, typename, typename>
818 friend class std::_Hash_merge_helper;
819
820 template<typename _H2, typename _P2>
821 void
823 {
824 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
825 if (std::__addressof(__source) == this) [[__unlikely__]]
826 return;
827
828 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
829 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
830 }
831
832 template<typename _H2, typename _P2>
833 void
834 merge(unordered_map<_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 {
844 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
845 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
846 }
847
848 template<typename _H2, typename _P2>
849 void
850 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
851 { merge(__source); }
852#endif // node_extract
853
854 // observers.
855
856 /// Returns the hash functor object with which the %unordered_map was
857 /// constructed.
858 hasher
860 { return _M_h.hash_function(); }
861
862 /// Returns the key comparison object with which the %unordered_map was
863 /// constructed.
865 key_eq() const
866 { return _M_h.key_eq(); }
867
868 // lookup.
869
870 ///@{
871 /**
872 * @brief Tries to locate an element in an %unordered_map.
873 * @param __x Key to be located.
874 * @return Iterator pointing to sought-after element, or end() if not
875 * found.
876 *
877 * This function takes a key and tries to locate the element with which
878 * the key matches. If successful the function returns an iterator
879 * pointing to the sought after element. If unsuccessful it returns the
880 * past-the-end ( @c end() ) iterator.
881 */
883 find(const key_type& __x)
884 { return _M_h.find(__x); }
885
886#if __cplusplus > 201703L
887 template<typename _Kt>
888 auto
889 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
890 { return _M_h._M_find_tr(__x); }
891#endif
892
893 const_iterator
894 find(const key_type& __x) const
895 { return _M_h.find(__x); }
896
897#if __cplusplus > 201703L
898 template<typename _Kt>
899 auto
900 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
901 { return _M_h._M_find_tr(__x); }
902#endif
903 ///@}
904
905 ///@{
906 /**
907 * @brief Finds the number of elements.
908 * @param __x Key to count.
909 * @return Number of elements with specified key.
910 *
911 * This function only makes sense for %unordered_multimap; for
912 * %unordered_map the result will either be 0 (not present) or 1
913 * (present).
914 */
915 size_type
916 count(const key_type& __x) const
917 { return _M_h.count(__x); }
918
919#if __cplusplus > 201703L
920 template<typename _Kt>
921 auto
922 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
923 { return _M_h._M_count_tr(__x); }
924#endif
925 ///@}
926
927#if __cplusplus > 201703L
928 ///@{
929 /**
930 * @brief Finds whether an element with the given key exists.
931 * @param __x Key of elements to be located.
932 * @return True if there is any element with the specified key.
933 */
934 bool
935 contains(const key_type& __x) const
936 { return _M_h.find(__x) != _M_h.end(); }
937
938 template<typename _Kt>
939 auto
940 contains(const _Kt& __x) const
941 -> decltype(_M_h._M_find_tr(__x), void(), true)
942 { return _M_h._M_find_tr(__x) != _M_h.end(); }
943 ///@}
944#endif
945
946 ///@{
947 /**
948 * @brief Finds a subsequence matching given key.
949 * @param __x Key to be located.
950 * @return Pair of iterators that possibly points to the subsequence
951 * matching given key.
952 *
953 * This function probably only makes sense for %unordered_multimap.
954 */
957 { return _M_h.equal_range(__x); }
958
959#if __cplusplus > 201703L
960 template<typename _Kt>
961 auto
962 equal_range(const _Kt& __x)
963 -> decltype(_M_h._M_equal_range_tr(__x))
964 { return _M_h._M_equal_range_tr(__x); }
965#endif
966
968 equal_range(const key_type& __x) const
969 { return _M_h.equal_range(__x); }
970
971#if __cplusplus > 201703L
972 template<typename _Kt>
973 auto
974 equal_range(const _Kt& __x) const
975 -> decltype(_M_h._M_equal_range_tr(__x))
976 { return _M_h._M_equal_range_tr(__x); }
977#endif
978 ///@}
979
980 ///@{
981 /**
982 * @brief Subscript ( @c [] ) access to %unordered_map data.
983 * @param __k The key for which data should be retrieved.
984 * @return A reference to the data of the (key,data) %pair.
985 *
986 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
987 * data associated with the key specified in subscript. If the key does
988 * not exist, a pair with that key is created using default values, which
989 * is then returned.
990 *
991 * Lookup requires constant time.
992 */
995 { return _M_h[__k]; }
996
999 { return _M_h[std::move(__k)]; }
1000 ///@}
1001
1002 ///@{
1003 /**
1004 * @brief Access to %unordered_map data.
1005 * @param __k The key for which data should be retrieved.
1006 * @return A reference to the data whose key is equal to @a __k, if
1007 * such a data is present in the %unordered_map.
1008 * @throw std::out_of_range If no such data is present.
1009 */
1011 at(const key_type& __k)
1012 { return _M_h.at(__k); }
1013
1014 const mapped_type&
1015 at(const key_type& __k) const
1016 { return _M_h.at(__k); }
1017 ///@}
1018
1019 // bucket interface.
1020
1021 /// Returns the number of buckets of the %unordered_map.
1022 size_type
1023 bucket_count() const noexcept
1024 { return _M_h.bucket_count(); }
1025
1026 /// Returns the maximum number of buckets of the %unordered_map.
1027 size_type
1028 max_bucket_count() const noexcept
1029 { return _M_h.max_bucket_count(); }
1030
1031 /*
1032 * @brief Returns the number of elements in a given bucket.
1033 * @param __n A bucket index.
1034 * @return The number of elements in the bucket.
1035 */
1036 size_type
1037 bucket_size(size_type __n) const
1038 { return _M_h.bucket_size(__n); }
1039
1040 /*
1041 * @brief Returns the bucket index of a given element.
1042 * @param __key A key instance.
1043 * @return The key bucket index.
1044 */
1045 size_type
1046 bucket(const key_type& __key) const
1047 { return _M_h.bucket(__key); }
1048
1049 /**
1050 * @brief Returns a read/write iterator pointing to the first bucket
1051 * element.
1052 * @param __n The bucket index.
1053 * @return A read/write local iterator.
1054 */
1057 { return _M_h.begin(__n); }
1058
1059 ///@{
1060 /**
1061 * @brief Returns a read-only (constant) iterator pointing to the first
1062 * bucket element.
1063 * @param __n The bucket index.
1064 * @return A read-only local iterator.
1065 */
1067 begin(size_type __n) const
1068 { return _M_h.begin(__n); }
1069
1072 { return _M_h.cbegin(__n); }
1073 ///@}
1074
1075 /**
1076 * @brief Returns a read/write iterator pointing to one past the last
1077 * bucket elements.
1078 * @param __n The bucket index.
1079 * @return A read/write local iterator.
1080 */
1083 { return _M_h.end(__n); }
1084
1085 ///@{
1086 /**
1087 * @brief Returns a read-only (constant) iterator pointing to one past
1088 * the last bucket elements.
1089 * @param __n The bucket index.
1090 * @return A read-only local iterator.
1091 */
1093 end(size_type __n) const
1094 { return _M_h.end(__n); }
1095
1097 cend(size_type __n) const
1098 { return _M_h.cend(__n); }
1099 ///@}
1100
1101 // hash policy.
1102
1103 /// Returns the average number of elements per bucket.
1104 float
1105 load_factor() const noexcept
1106 { return _M_h.load_factor(); }
1107
1108 /// Returns a positive number that the %unordered_map tries to keep the
1109 /// load factor less than or equal to.
1110 float
1111 max_load_factor() const noexcept
1112 { return _M_h.max_load_factor(); }
1113
1114 /**
1115 * @brief Change the %unordered_map maximum load factor.
1116 * @param __z The new maximum load factor.
1117 */
1118 void
1120 { _M_h.max_load_factor(__z); }
1121
1122 /**
1123 * @brief May rehash the %unordered_map.
1124 * @param __n The new number of buckets.
1125 *
1126 * Rehash will occur only if the new number of buckets respect the
1127 * %unordered_map maximum load factor.
1128 */
1129 void
1131 { _M_h.rehash(__n); }
1132
1133 /**
1134 * @brief Prepare the %unordered_map for a specified number of
1135 * elements.
1136 * @param __n Number of elements required.
1137 *
1138 * Same as rehash(ceil(n / max_load_factor())).
1139 */
1140 void
1142 { _M_h.reserve(__n); }
1143
1144 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1145 typename _Alloc1>
1146 friend bool
1149 };
1150
1151#if __cpp_deduction_guides >= 201606
1152
1153 template<typename _InputIterator,
1154 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1155 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1156 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1157 typename = _RequireInputIter<_InputIterator>,
1158 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1159 typename = _RequireNotAllocator<_Pred>,
1160 typename = _RequireAllocator<_Allocator>>
1161 unordered_map(_InputIterator, _InputIterator,
1162 typename unordered_map<int, int>::size_type = {},
1163 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1164 -> unordered_map<__iter_key_t<_InputIterator>,
1165 __iter_val_t<_InputIterator>,
1166 _Hash, _Pred, _Allocator>;
1167
1168 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1169 typename _Pred = equal_to<_Key>,
1170 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1171 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1172 typename = _RequireNotAllocator<_Pred>,
1173 typename = _RequireAllocator<_Allocator>>
1174 unordered_map(initializer_list<pair<_Key, _Tp>>,
1175 typename unordered_map<int, int>::size_type = {},
1176 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1177 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1178
1179 template<typename _InputIterator, typename _Allocator,
1180 typename = _RequireInputIter<_InputIterator>,
1181 typename = _RequireAllocator<_Allocator>>
1182 unordered_map(_InputIterator, _InputIterator,
1183 typename unordered_map<int, int>::size_type, _Allocator)
1184 -> unordered_map<__iter_key_t<_InputIterator>,
1185 __iter_val_t<_InputIterator>,
1186 hash<__iter_key_t<_InputIterator>>,
1187 equal_to<__iter_key_t<_InputIterator>>,
1188 _Allocator>;
1189
1190 template<typename _InputIterator, typename _Allocator,
1191 typename = _RequireInputIter<_InputIterator>,
1192 typename = _RequireAllocator<_Allocator>>
1193 unordered_map(_InputIterator, _InputIterator, _Allocator)
1194 -> unordered_map<__iter_key_t<_InputIterator>,
1195 __iter_val_t<_InputIterator>,
1196 hash<__iter_key_t<_InputIterator>>,
1197 equal_to<__iter_key_t<_InputIterator>>,
1198 _Allocator>;
1199
1200 template<typename _InputIterator, typename _Hash, typename _Allocator,
1201 typename = _RequireInputIter<_InputIterator>,
1202 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1203 typename = _RequireAllocator<_Allocator>>
1204 unordered_map(_InputIterator, _InputIterator,
1205 typename unordered_map<int, int>::size_type,
1206 _Hash, _Allocator)
1207 -> unordered_map<__iter_key_t<_InputIterator>,
1208 __iter_val_t<_InputIterator>, _Hash,
1209 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1210
1211 template<typename _Key, typename _Tp, typename _Allocator,
1212 typename = _RequireAllocator<_Allocator>>
1213 unordered_map(initializer_list<pair<_Key, _Tp>>,
1214 typename unordered_map<int, int>::size_type,
1215 _Allocator)
1216 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1217
1218 template<typename _Key, typename _Tp, typename _Allocator,
1219 typename = _RequireAllocator<_Allocator>>
1220 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1221 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1222
1223 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1224 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1225 typename = _RequireAllocator<_Allocator>>
1226 unordered_map(initializer_list<pair<_Key, _Tp>>,
1227 typename unordered_map<int, int>::size_type,
1228 _Hash, _Allocator)
1229 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1230
1231#endif
1232
1233 /**
1234 * @brief A standard container composed of equivalent keys
1235 * (possibly containing multiple of each key value) that associates
1236 * values of another type with the keys.
1237 *
1238 * @ingroup unordered_associative_containers
1239 * @headerfile unordered_map
1240 * @since C++11
1241 *
1242 * @tparam _Key Type of key objects.
1243 * @tparam _Tp Type of mapped objects.
1244 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1245 * @tparam _Pred Predicate function object type, defaults
1246 * to equal_to<_Value>.
1247 * @tparam _Alloc Allocator type, defaults to
1248 * std::allocator<std::pair<const _Key, _Tp>>.
1249 *
1250 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1251 * <a href="tables.html#xx">unordered associative container</a>
1252 *
1253 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1254 *
1255 * Base is _Hashtable, dispatched at compile time via template
1256 * alias __ummap_hashtable.
1257 */
1258 template<typename _Key, typename _Tp,
1259 typename _Hash = hash<_Key>,
1260 typename _Pred = equal_to<_Key>,
1261 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1263 {
1264 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
1265 _Hashtable _M_h;
1266
1267 public:
1268 // typedefs:
1269 ///@{
1270 /// Public typedefs.
1271 typedef typename _Hashtable::key_type key_type;
1272 typedef typename _Hashtable::value_type value_type;
1273 typedef typename _Hashtable::mapped_type mapped_type;
1274 typedef typename _Hashtable::hasher hasher;
1275 typedef typename _Hashtable::key_equal key_equal;
1276 typedef typename _Hashtable::allocator_type allocator_type;
1277 ///@}
1278
1279 ///@{
1280 /// Iterator-related typedefs.
1281 typedef typename _Hashtable::pointer pointer;
1282 typedef typename _Hashtable::const_pointer const_pointer;
1283 typedef typename _Hashtable::reference reference;
1284 typedef typename _Hashtable::const_reference const_reference;
1285 typedef typename _Hashtable::iterator iterator;
1286 typedef typename _Hashtable::const_iterator const_iterator;
1287 typedef typename _Hashtable::local_iterator local_iterator;
1288 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1289 typedef typename _Hashtable::size_type size_type;
1290 typedef typename _Hashtable::difference_type difference_type;
1291 ///@}
1292
1293#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1294 using node_type = typename _Hashtable::node_type;
1295#endif
1296
1297 //construct/destroy/copy
1298
1299 /// Default constructor.
1301
1302 /**
1303 * @brief Default constructor creates no elements.
1304 * @param __n Mnimal initial number of buckets.
1305 * @param __hf A hash functor.
1306 * @param __eql A key equality functor.
1307 * @param __a An allocator object.
1308 */
1309 explicit
1311 const hasher& __hf = hasher(),
1312 const key_equal& __eql = key_equal(),
1313 const allocator_type& __a = allocator_type())
1314 : _M_h(__n, __hf, __eql, __a)
1315 { }
1316
1317 /**
1318 * @brief Builds an %unordered_multimap from a range.
1319 * @param __first An input iterator.
1320 * @param __last An input iterator.
1321 * @param __n Minimal initial number of buckets.
1322 * @param __hf A hash functor.
1323 * @param __eql A key equality functor.
1324 * @param __a An allocator object.
1325 *
1326 * Create an %unordered_multimap consisting of copies of the elements
1327 * from [__first,__last). This is linear in N (where N is
1328 * distance(__first,__last)).
1329 */
1330 template<typename _InputIterator>
1331 unordered_multimap(_InputIterator __first, _InputIterator __last,
1332 size_type __n = 0,
1333 const hasher& __hf = hasher(),
1334 const key_equal& __eql = key_equal(),
1335 const allocator_type& __a = allocator_type())
1336 : _M_h(__first, __last, __n, __hf, __eql, __a)
1337 { }
1338
1339 /// Copy constructor.
1341
1342 /// Move constructor.
1344
1345 /**
1346 * @brief Creates an %unordered_multimap with no elements.
1347 * @param __a An allocator object.
1348 */
1349 explicit
1351 : _M_h(__a)
1352 { }
1353
1354 /*
1355 * @brief Copy constructor with allocator argument.
1356 * @param __uset Input %unordered_multimap to copy.
1357 * @param __a An allocator object.
1358 */
1360 const allocator_type& __a)
1361 : _M_h(__ummap._M_h, __a)
1362 { }
1363
1364 /*
1365 * @brief Move constructor with allocator argument.
1366 * @param __uset Input %unordered_multimap to move.
1367 * @param __a An allocator object.
1368 */
1369 unordered_multimap(unordered_multimap&& __ummap,
1370 const allocator_type& __a)
1371 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1372 : _M_h(std::move(__ummap._M_h), __a)
1373 { }
1374
1375 /**
1376 * @brief Builds an %unordered_multimap from an initializer_list.
1377 * @param __l An initializer_list.
1378 * @param __n Minimal initial number of buckets.
1379 * @param __hf A hash functor.
1380 * @param __eql A key equality functor.
1381 * @param __a An allocator object.
1382 *
1383 * Create an %unordered_multimap consisting of copies of the elements in
1384 * the list. This is linear in N (where N is @a __l.size()).
1385 */
1387 size_type __n = 0,
1388 const hasher& __hf = hasher(),
1389 const key_equal& __eql = key_equal(),
1390 const allocator_type& __a = allocator_type())
1391 : _M_h(__l, __n, __hf, __eql, __a)
1392 { }
1393
1394 unordered_multimap(size_type __n, const allocator_type& __a)
1395 : unordered_multimap(__n, hasher(), key_equal(), __a)
1396 { }
1397
1398 unordered_multimap(size_type __n, const hasher& __hf,
1399 const allocator_type& __a)
1400 : unordered_multimap(__n, __hf, key_equal(), __a)
1401 { }
1402
1403 template<typename _InputIterator>
1404 unordered_multimap(_InputIterator __first, _InputIterator __last,
1405 size_type __n,
1406 const allocator_type& __a)
1407 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1408 { }
1409
1410 template<typename _InputIterator>
1411 unordered_multimap(_InputIterator __first, _InputIterator __last,
1412 size_type __n, const hasher& __hf,
1413 const allocator_type& __a)
1414 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1415 { }
1416
1417 unordered_multimap(initializer_list<value_type> __l,
1418 size_type __n,
1419 const allocator_type& __a)
1420 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1421 { }
1422
1423 unordered_multimap(initializer_list<value_type> __l,
1424 size_type __n, const hasher& __hf,
1425 const allocator_type& __a)
1426 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1427 { }
1428
1429 /// Copy assignment operator.
1430 unordered_multimap&
1432
1433 /// Move assignment operator.
1436
1437 /**
1438 * @brief %Unordered_multimap list assignment operator.
1439 * @param __l An initializer_list.
1440 *
1441 * This function fills an %unordered_multimap with copies of the
1442 * elements in the initializer list @a __l.
1443 *
1444 * Note that the assignment completely changes the %unordered_multimap
1445 * and that the resulting %unordered_multimap's size is the same as the
1446 * number of elements assigned.
1447 */
1450 {
1451 _M_h = __l;
1452 return *this;
1453 }
1454
1455 /// Returns the allocator object used by the %unordered_multimap.
1456 allocator_type
1457 get_allocator() const noexcept
1458 { return _M_h.get_allocator(); }
1459
1460 // size and capacity:
1461
1462 /// Returns true if the %unordered_multimap is empty.
1463 _GLIBCXX_NODISCARD bool
1464 empty() const noexcept
1465 { return _M_h.empty(); }
1466
1467 /// Returns the size of the %unordered_multimap.
1468 size_type
1469 size() const noexcept
1470 { return _M_h.size(); }
1471
1472 /// Returns the maximum size of the %unordered_multimap.
1473 size_type
1474 max_size() const noexcept
1475 { return _M_h.max_size(); }
1476
1477 // iterators.
1478
1479 /**
1480 * Returns a read/write iterator that points to the first element in the
1481 * %unordered_multimap.
1482 */
1483 iterator
1484 begin() noexcept
1485 { return _M_h.begin(); }
1486
1487 ///@{
1488 /**
1489 * Returns a read-only (constant) iterator that points to the first
1490 * element in the %unordered_multimap.
1491 */
1492 const_iterator
1493 begin() const noexcept
1494 { return _M_h.begin(); }
1495
1496 const_iterator
1497 cbegin() const noexcept
1498 { return _M_h.begin(); }
1499 ///@}
1500
1501 /**
1502 * Returns a read/write iterator that points one past the last element in
1503 * the %unordered_multimap.
1504 */
1505 iterator
1506 end() noexcept
1507 { return _M_h.end(); }
1508
1509 ///@{
1510 /**
1511 * Returns a read-only (constant) iterator that points one past the last
1512 * element in the %unordered_multimap.
1513 */
1514 const_iterator
1515 end() const noexcept
1516 { return _M_h.end(); }
1517
1518 const_iterator
1519 cend() const noexcept
1520 { return _M_h.end(); }
1521 ///@}
1522
1523 // modifiers.
1524
1525 /**
1526 * @brief Attempts to build and insert a std::pair into the
1527 * %unordered_multimap.
1528 *
1529 * @param __args Arguments used to generate a new pair instance (see
1530 * std::piecewise_contruct for passing arguments to each
1531 * part of the pair constructor).
1532 *
1533 * @return An iterator that points to the inserted pair.
1534 *
1535 * This function attempts to build and insert a (key, value) %pair into
1536 * the %unordered_multimap.
1537 *
1538 * Insertion requires amortized constant time.
1539 */
1540 template<typename... _Args>
1541 iterator
1542 emplace(_Args&&... __args)
1543 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1544
1545 /**
1546 * @brief Attempts to build and insert a std::pair into the
1547 * %unordered_multimap.
1548 *
1549 * @param __pos An iterator that serves as a hint as to where the pair
1550 * should be inserted.
1551 * @param __args Arguments used to generate a new pair instance (see
1552 * std::piecewise_contruct for passing arguments to each
1553 * part of the pair constructor).
1554 * @return An iterator that points to the element with key of the
1555 * std::pair built from @a __args.
1556 *
1557 * Note that the first parameter is only a hint and can potentially
1558 * improve the performance of the insertion process. A bad hint would
1559 * cause no gains in efficiency.
1560 *
1561 * See
1562 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1563 * for more on @a hinting.
1564 *
1565 * Insertion requires amortized constant time.
1566 */
1567 template<typename... _Args>
1568 iterator
1569 emplace_hint(const_iterator __pos, _Args&&... __args)
1570 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1571
1572 ///@{
1573 /**
1574 * @brief Inserts a std::pair into the %unordered_multimap.
1575 * @param __x Pair to be inserted (see std::make_pair for easy
1576 * creation of pairs).
1577 *
1578 * @return An iterator that points to the inserted pair.
1579 *
1580 * Insertion requires amortized constant time.
1581 */
1582 iterator
1583 insert(const value_type& __x)
1584 { return _M_h.insert(__x); }
1585
1586 iterator
1588 { return _M_h.insert(std::move(__x)); }
1589
1590 template<typename _Pair>
1591 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1592 insert(_Pair&& __x)
1593 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1594 ///@}
1595
1596 ///@{
1597 /**
1598 * @brief Inserts a std::pair into the %unordered_multimap.
1599 * @param __hint An iterator that serves as a hint as to where the
1600 * pair should be inserted.
1601 * @param __x Pair to be inserted (see std::make_pair for easy creation
1602 * of pairs).
1603 * @return An iterator that points to the element with key of
1604 * @a __x (may or may not be the %pair passed in).
1605 *
1606 * Note that the first parameter is only a hint and can potentially
1607 * improve the performance of the insertion process. A bad hint would
1608 * cause no gains in efficiency.
1609 *
1610 * See
1611 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1612 * for more on @a hinting.
1613 *
1614 * Insertion requires amortized constant time.
1615 */
1616 iterator
1618 { return _M_h.insert(__hint, __x); }
1619
1620 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1621 // 2354. Unnecessary copying when inserting into maps with braced-init
1622 iterator
1624 { return _M_h.insert(__hint, std::move(__x)); }
1625
1626 template<typename _Pair>
1627 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1628 insert(const_iterator __hint, _Pair&& __x)
1629 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1630 ///@}
1631
1632 /**
1633 * @brief A template function that attempts to insert a range of
1634 * elements.
1635 * @param __first Iterator pointing to the start of the range to be
1636 * inserted.
1637 * @param __last Iterator pointing to the end of the range.
1638 *
1639 * Complexity similar to that of the range constructor.
1640 */
1641 template<typename _InputIterator>
1642 void
1643 insert(_InputIterator __first, _InputIterator __last)
1644 { _M_h.insert(__first, __last); }
1645
1646 /**
1647 * @brief Attempts to insert a list of elements into the
1648 * %unordered_multimap.
1649 * @param __l A std::initializer_list<value_type> of elements
1650 * to be inserted.
1651 *
1652 * Complexity similar to that of the range constructor.
1653 */
1654 void
1656 { _M_h.insert(__l); }
1657
1658#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1659 /// Extract a node.
1660 node_type
1662 {
1663 __glibcxx_assert(__pos != end());
1664 return _M_h.extract(__pos);
1665 }
1666
1667 /// Extract a node.
1668 node_type
1669 extract(const key_type& __key)
1670 { return _M_h.extract(__key); }
1671
1672 /// Re-insert an extracted node.
1673 iterator
1674 insert(node_type&& __nh)
1675 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1676
1677 /// Re-insert an extracted node.
1678 iterator
1679 insert(const_iterator __hint, node_type&& __nh)
1680 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1681#endif // node_extract
1682
1683 ///@{
1684 /**
1685 * @brief Erases an element from an %unordered_multimap.
1686 * @param __position An iterator pointing to the element to be erased.
1687 * @return An iterator pointing to the element immediately following
1688 * @a __position prior to the element being erased. If no such
1689 * element exists, end() is returned.
1690 *
1691 * This function erases an element, pointed to by the given iterator,
1692 * from an %unordered_multimap.
1693 * Note that this function only erases the element, and that if the
1694 * element is itself a pointer, the pointed-to memory is not touched in
1695 * any way. Managing the pointer is the user's responsibility.
1696 */
1697 iterator
1699 { return _M_h.erase(__position); }
1700
1701 // LWG 2059.
1702 iterator
1703 erase(iterator __position)
1704 { return _M_h.erase(__position); }
1705 ///@}
1706
1707 /**
1708 * @brief Erases elements according to the provided key.
1709 * @param __x Key of elements to be erased.
1710 * @return The number of elements erased.
1711 *
1712 * This function erases all the elements located by the given key from
1713 * an %unordered_multimap.
1714 * Note that this function only erases the element, and that if the
1715 * element is itself a pointer, the pointed-to memory is not touched in
1716 * any way. Managing the pointer is the user's responsibility.
1717 */
1718 size_type
1719 erase(const key_type& __x)
1720 { return _M_h.erase(__x); }
1721
1722 /**
1723 * @brief Erases a [__first,__last) range of elements from an
1724 * %unordered_multimap.
1725 * @param __first Iterator pointing to the start of the range to be
1726 * erased.
1727 * @param __last Iterator pointing to the end of the range to
1728 * be erased.
1729 * @return The iterator @a __last.
1730 *
1731 * This function erases a sequence of elements from an
1732 * %unordered_multimap.
1733 * Note that this function only erases the elements, and that if
1734 * the element is itself a pointer, the pointed-to memory is not touched
1735 * in any way. Managing the pointer is the user's responsibility.
1736 */
1737 iterator
1739 { return _M_h.erase(__first, __last); }
1740
1741 /**
1742 * Erases all elements in an %unordered_multimap.
1743 * Note that this function only erases the elements, and that if the
1744 * elements themselves are pointers, the pointed-to memory is not touched
1745 * in any way. Managing the pointer is the user's responsibility.
1746 */
1747 void
1748 clear() noexcept
1749 { _M_h.clear(); }
1750
1751 /**
1752 * @brief Swaps data with another %unordered_multimap.
1753 * @param __x An %unordered_multimap of the same element and allocator
1754 * types.
1755 *
1756 * This exchanges the elements between two %unordered_multimap in
1757 * constant time.
1758 * Note that the global std::swap() function is specialized such that
1759 * std::swap(m1,m2) will feed to this function.
1760 */
1761 void
1763 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1764 { _M_h.swap(__x._M_h); }
1765
1766#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1767 template<typename, typename, typename>
1768 friend class std::_Hash_merge_helper;
1769
1770 template<typename _H2, typename _P2>
1771 void
1773 {
1774 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
1775 if (std::__addressof(__source) == this) [[__unlikely__]]
1776 return;
1777
1778 using _Merge_helper
1779 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1780 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1781 }
1782
1783 template<typename _H2, typename _P2>
1784 void
1785 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1786 {
1787 using _Merge_helper
1788 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1789 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1790 }
1791
1792 template<typename _H2, typename _P2>
1793 void
1794 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1795 {
1796 using _Merge_helper
1797 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1798 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1799 }
1800
1801 template<typename _H2, typename _P2>
1802 void
1803 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1804 { merge(__source); }
1805#endif // node_extract
1806
1807 // observers.
1808
1809 /// Returns the hash functor object with which the %unordered_multimap
1810 /// was constructed.
1811 hasher
1813 { return _M_h.hash_function(); }
1814
1815 /// Returns the key comparison object with which the %unordered_multimap
1816 /// was constructed.
1817 key_equal
1818 key_eq() const
1819 { return _M_h.key_eq(); }
1820
1821 // lookup.
1822
1823 ///@{
1824 /**
1825 * @brief Tries to locate an element in an %unordered_multimap.
1826 * @param __x Key to be located.
1827 * @return Iterator pointing to sought-after element, or end() if not
1828 * found.
1829 *
1830 * This function takes a key and tries to locate the element with which
1831 * the key matches. If successful the function returns an iterator
1832 * pointing to the sought after element. If unsuccessful it returns the
1833 * past-the-end ( @c end() ) iterator.
1834 */
1835 iterator
1836 find(const key_type& __x)
1837 { return _M_h.find(__x); }
1838
1839#if __cplusplus > 201703L
1840 template<typename _Kt>
1841 auto
1842 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
1843 { return _M_h._M_find_tr(__x); }
1844#endif
1845
1846 const_iterator
1847 find(const key_type& __x) const
1848 { return _M_h.find(__x); }
1849
1850#if __cplusplus > 201703L
1851 template<typename _Kt>
1852 auto
1853 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
1854 { return _M_h._M_find_tr(__x); }
1855#endif
1856 ///@}
1857
1858 ///@{
1859 /**
1860 * @brief Finds the number of elements.
1861 * @param __x Key to count.
1862 * @return Number of elements with specified key.
1863 */
1864 size_type
1865 count(const key_type& __x) const
1866 { return _M_h.count(__x); }
1867
1868#if __cplusplus > 201703L
1869 template<typename _Kt>
1870 auto
1871 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1872 { return _M_h._M_count_tr(__x); }
1873#endif
1874 ///@}
1875
1876#if __cplusplus > 201703L
1877 ///@{
1878 /**
1879 * @brief Finds whether an element with the given key exists.
1880 * @param __x Key of elements to be located.
1881 * @return True if there is any element with the specified key.
1882 */
1883 bool
1884 contains(const key_type& __x) const
1885 { return _M_h.find(__x) != _M_h.end(); }
1886
1887 template<typename _Kt>
1888 auto
1889 contains(const _Kt& __x) const
1890 -> decltype(_M_h._M_find_tr(__x), void(), true)
1891 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1892 ///@}
1893#endif
1894
1895 ///@{
1896 /**
1897 * @brief Finds a subsequence matching given key.
1898 * @param __x Key to be located.
1899 * @return Pair of iterators that possibly points to the subsequence
1900 * matching given key.
1901 */
1904 { return _M_h.equal_range(__x); }
1905
1906#if __cplusplus > 201703L
1907 template<typename _Kt>
1908 auto
1909 equal_range(const _Kt& __x)
1910 -> decltype(_M_h._M_equal_range_tr(__x))
1911 { return _M_h._M_equal_range_tr(__x); }
1912#endif
1913
1915 equal_range(const key_type& __x) const
1916 { return _M_h.equal_range(__x); }
1917
1918#if __cplusplus > 201703L
1919 template<typename _Kt>
1920 auto
1921 equal_range(const _Kt& __x) const
1922 -> decltype(_M_h._M_equal_range_tr(__x))
1923 { return _M_h._M_equal_range_tr(__x); }
1924#endif
1925 ///@}
1926
1927 // bucket interface.
1928
1929 /// Returns the number of buckets of the %unordered_multimap.
1930 size_type
1931 bucket_count() const noexcept
1932 { return _M_h.bucket_count(); }
1933
1934 /// Returns the maximum number of buckets of the %unordered_multimap.
1935 size_type
1936 max_bucket_count() const noexcept
1937 { return _M_h.max_bucket_count(); }
1938
1939 /*
1940 * @brief Returns the number of elements in a given bucket.
1941 * @param __n A bucket index.
1942 * @return The number of elements in the bucket.
1943 */
1944 size_type
1945 bucket_size(size_type __n) const
1946 { return _M_h.bucket_size(__n); }
1947
1948 /*
1949 * @brief Returns the bucket index of a given element.
1950 * @param __key A key instance.
1951 * @return The key bucket index.
1952 */
1953 size_type
1954 bucket(const key_type& __key) const
1955 { return _M_h.bucket(__key); }
1956
1957 /**
1958 * @brief Returns a read/write iterator pointing to the first bucket
1959 * element.
1960 * @param __n The bucket index.
1961 * @return A read/write local iterator.
1962 */
1965 { return _M_h.begin(__n); }
1966
1967 ///@{
1968 /**
1969 * @brief Returns a read-only (constant) iterator pointing to the first
1970 * bucket element.
1971 * @param __n The bucket index.
1972 * @return A read-only local iterator.
1973 */
1975 begin(size_type __n) const
1976 { return _M_h.begin(__n); }
1977
1980 { return _M_h.cbegin(__n); }
1981 ///@}
1982
1983 /**
1984 * @brief Returns a read/write iterator pointing to one past the last
1985 * bucket elements.
1986 * @param __n The bucket index.
1987 * @return A read/write local iterator.
1988 */
1991 { return _M_h.end(__n); }
1992
1993 ///@{
1994 /**
1995 * @brief Returns a read-only (constant) iterator pointing to one past
1996 * the last bucket elements.
1997 * @param __n The bucket index.
1998 * @return A read-only local iterator.
1999 */
2001 end(size_type __n) const
2002 { return _M_h.end(__n); }
2003
2005 cend(size_type __n) const
2006 { return _M_h.cend(__n); }
2007 ///@}
2008
2009 // hash policy.
2010
2011 /// Returns the average number of elements per bucket.
2012 float
2013 load_factor() const noexcept
2014 { return _M_h.load_factor(); }
2015
2016 /// Returns a positive number that the %unordered_multimap tries to keep
2017 /// the load factor less than or equal to.
2018 float
2019 max_load_factor() const noexcept
2020 { return _M_h.max_load_factor(); }
2021
2022 /**
2023 * @brief Change the %unordered_multimap maximum load factor.
2024 * @param __z The new maximum load factor.
2025 */
2026 void
2028 { _M_h.max_load_factor(__z); }
2029
2030 /**
2031 * @brief May rehash the %unordered_multimap.
2032 * @param __n The new number of buckets.
2033 *
2034 * Rehash will occur only if the new number of buckets respect the
2035 * %unordered_multimap maximum load factor.
2036 */
2037 void
2039 { _M_h.rehash(__n); }
2040
2041 /**
2042 * @brief Prepare the %unordered_multimap for a specified number of
2043 * elements.
2044 * @param __n Number of elements required.
2045 *
2046 * Same as rehash(ceil(n / max_load_factor())).
2047 */
2048 void
2050 { _M_h.reserve(__n); }
2051
2052 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
2053 typename _Alloc1>
2054 friend bool
2055 operator==(const unordered_multimap<_Key1, _Tp1,
2056 _Hash1, _Pred1, _Alloc1>&,
2057 const unordered_multimap<_Key1, _Tp1,
2058 _Hash1, _Pred1, _Alloc1>&);
2059 };
2060
2061#if __cpp_deduction_guides >= 201606
2062
2063 template<typename _InputIterator,
2064 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2065 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2066 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2067 typename = _RequireInputIter<_InputIterator>,
2068 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2069 typename = _RequireNotAllocator<_Pred>,
2070 typename = _RequireAllocator<_Allocator>>
2071 unordered_multimap(_InputIterator, _InputIterator,
2072 unordered_multimap<int, int>::size_type = {},
2073 _Hash = _Hash(), _Pred = _Pred(),
2074 _Allocator = _Allocator())
2075 -> unordered_multimap<__iter_key_t<_InputIterator>,
2076 __iter_val_t<_InputIterator>, _Hash, _Pred,
2077 _Allocator>;
2078
2079 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2080 typename _Pred = equal_to<_Key>,
2081 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2082 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2083 typename = _RequireNotAllocator<_Pred>,
2084 typename = _RequireAllocator<_Allocator>>
2085 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2086 unordered_multimap<int, int>::size_type = {},
2087 _Hash = _Hash(), _Pred = _Pred(),
2088 _Allocator = _Allocator())
2089 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2090
2091 template<typename _InputIterator, typename _Allocator,
2092 typename = _RequireInputIter<_InputIterator>,
2093 typename = _RequireAllocator<_Allocator>>
2094 unordered_multimap(_InputIterator, _InputIterator,
2095 unordered_multimap<int, int>::size_type, _Allocator)
2096 -> unordered_multimap<__iter_key_t<_InputIterator>,
2097 __iter_val_t<_InputIterator>,
2098 hash<__iter_key_t<_InputIterator>>,
2099 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2100
2101 template<typename _InputIterator, typename _Allocator,
2102 typename = _RequireInputIter<_InputIterator>,
2103 typename = _RequireAllocator<_Allocator>>
2104 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2105 -> unordered_multimap<__iter_key_t<_InputIterator>,
2106 __iter_val_t<_InputIterator>,
2107 hash<__iter_key_t<_InputIterator>>,
2108 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2109
2110 template<typename _InputIterator, typename _Hash, typename _Allocator,
2111 typename = _RequireInputIter<_InputIterator>,
2112 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2113 typename = _RequireAllocator<_Allocator>>
2114 unordered_multimap(_InputIterator, _InputIterator,
2115 unordered_multimap<int, int>::size_type, _Hash,
2116 _Allocator)
2117 -> unordered_multimap<__iter_key_t<_InputIterator>,
2118 __iter_val_t<_InputIterator>, _Hash,
2119 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2120
2121 template<typename _Key, typename _Tp, typename _Allocator,
2122 typename = _RequireAllocator<_Allocator>>
2123 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2124 unordered_multimap<int, int>::size_type,
2125 _Allocator)
2126 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2127
2128 template<typename _Key, typename _Tp, typename _Allocator,
2129 typename = _RequireAllocator<_Allocator>>
2130 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2131 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2132
2133 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2134 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2135 typename = _RequireAllocator<_Allocator>>
2136 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2137 unordered_multimap<int, int>::size_type,
2138 _Hash, _Allocator)
2139 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2140
2141#endif
2142
2143 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2144 inline void
2145 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2146 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2147 noexcept(noexcept(__x.swap(__y)))
2148 { __x.swap(__y); }
2149
2150 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2151 inline void
2152 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2153 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2154 noexcept(noexcept(__x.swap(__y)))
2155 { __x.swap(__y); }
2156
2157 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2158 inline bool
2159 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2160 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2161 { return __x._M_h._M_equal(__y._M_h); }
2162
2163#if __cpp_impl_three_way_comparison < 201907L
2164 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2165 inline bool
2166 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2167 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2168 { return !(__x == __y); }
2169#endif
2170
2171 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2172 inline bool
2173 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2174 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2175 { return __x._M_h._M_equal(__y._M_h); }
2176
2177#if __cpp_impl_three_way_comparison < 201907L
2178 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2179 inline bool
2180 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2181 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2182 { return !(__x == __y); }
2183#endif
2184
2185_GLIBCXX_END_NAMESPACE_CONTAINER
2186
2187#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
2188 // Allow std::unordered_map access to internals of compatible maps.
2189 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2190 typename _Alloc, typename _Hash2, typename _Eq2>
2191 struct _Hash_merge_helper<
2192 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2193 _Hash2, _Eq2>
2194 {
2195 private:
2196 template<typename... _Tp>
2197 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2198 template<typename... _Tp>
2199 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2200
2201 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2202
2203 static auto&
2204 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2205 { return __map._M_h; }
2206
2207 static auto&
2208 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2209 { return __map._M_h; }
2210 };
2211
2212 // Allow std::unordered_multimap access to internals of compatible maps.
2213 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2214 typename _Alloc, typename _Hash2, typename _Eq2>
2215 struct _Hash_merge_helper<
2216 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2217 _Hash2, _Eq2>
2218 {
2219 private:
2220 template<typename... _Tp>
2221 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2222 template<typename... _Tp>
2223 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2224
2225 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2226
2227 static auto&
2228 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2229 { return __map._M_h; }
2230
2231 static auto&
2232 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2233 { return __map._M_h; }
2234 };
2235#endif // node_extract
2236
2237_GLIBCXX_END_NAMESPACE_VERSION
2238} // namespace std
2239
2240#endif /* _UNORDERED_MAP_H */
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:70
ISO C++ entities toplevel namespace is std.
__detail::_Hashtable_traits< _Cache, false, false > __ummap_traits
Base types for unordered_multimap.
__detail::_Hashtable_traits< _Cache, false, true > __umap_traits
Base types for unordered_map.
initializer_list
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
Definition memoryfwd.h:67
One of the comparison functors.
Struct holding two objects of arbitrary type.
Definition stl_pair.h:286
_T1 first
The first member.
Definition stl_pair.h:290
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.
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.
_Hashtable::size_type size_type
Iterator-related typedefs.
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.
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.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
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::iterator iterator
Iterator-related 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.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
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.
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.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
iterator insert(node_type &&__nh)
Re-insert an extracted node.
_Hashtable::value_type value_type
Public typedefs.
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
_Hashtable::key_equal key_equal
Public typedefs.
iterator end() noexcept
_Hashtable::key_type key_type
Public typedefs.
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.
_Hashtable::allocator_type allocator_type
Public typedefs.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
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.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
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.
_Hashtable::mapped_type mapped_type
Public typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::hasher hasher
Public typedefs.
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multimap.
unordered_multimap(unordered_multimap &&)=default
Move constructor.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
_Hashtable::reference reference
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.
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.
_Hashtable::pointer pointer
Iterator-related typedefs.
const_iterator cbegin() const noexcept
_Hashtable::const_pointer const_pointer
Iterator-related 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.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
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.
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.
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.
_Hashtable::reference reference
Iterator-related typedefs.
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::local_iterator local_iterator
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.
_Hashtable::allocator_type allocator_type
Public typedefs.
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.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
iterator end() noexcept
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.
_Hashtable::size_type size_type
Iterator-related typedefs.
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.
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.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
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
_Hashtable::key_equal key_equal
Public typedefs.
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
iterator erase(iterator __position)
Erases an element from an unordered_map.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
const_iterator cend() const noexcept
_Hashtable::value_type value_type
Public typedefs.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
_Hashtable::mapped_type mapped_type
Public 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.
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.
_Hashtable::iterator iterator
Iterator-related typedefs.
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::key_type key_type
Public typedefs.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::pointer pointer
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.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
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.
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::const_iterator const_iterator
Iterator-related typedefs.
insert_return_type insert(node_type &&__nh)
Re-insert an extracted node.
void rehash(size_type __n)
May rehash the unordered_map.
const_iterator cbegin() const noexcept