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