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>,
51 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
52 typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
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>,
68 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
69 typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
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>
78 class unordered_multimap;
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>>>
109 class unordered_map
110 {
111 typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
112 _Hashtable _M_h;
113
114 public:
115 // typedefs:
116 ///@{
117 /// Public typedefs.
118 typedef typename _Hashtable::key_type key_type;
119 typedef typename _Hashtable::value_type value_type;
120 typedef typename _Hashtable::mapped_type mapped_type;
121 typedef typename _Hashtable::hasher hasher;
122 typedef typename _Hashtable::key_equal key_equal;
123 typedef typename _Hashtable::allocator_type allocator_type;
124 ///@}
125
126 ///@{
127 /// Iterator-related typedefs.
128 typedef typename _Hashtable::pointer pointer;
129 typedef typename _Hashtable::const_pointer const_pointer;
130 typedef typename _Hashtable::reference reference;
131 typedef typename _Hashtable::const_reference const_reference;
132 typedef typename _Hashtable::iterator iterator;
133 typedef typename _Hashtable::const_iterator const_iterator;
134 typedef typename _Hashtable::local_iterator local_iterator;
135 typedef typename _Hashtable::const_local_iterator const_local_iterator;
136 typedef typename _Hashtable::size_type size_type;
137 typedef typename _Hashtable::difference_type difference_type;
138 ///@}
139
140#if __cplusplus > 201402L
141 using node_type = typename _Hashtable::node_type;
142 using insert_return_type = typename _Hashtable::insert_return_type;
143#endif
144
145 //construct/destroy/copy
146
147 /// Default constructor.
148 unordered_map() = default;
149
150 /**
151 * @brief Default constructor creates no elements.
152 * @param __n Minimal initial number of buckets.
153 * @param __hf A hash functor.
154 * @param __eql A key equality functor.
155 * @param __a An allocator object.
156 */
157 explicit
158 unordered_map(size_type __n,
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.
191 unordered_map(unordered_map&&) = default;
192
193 /**
194 * @brief Creates an %unordered_map with no elements.
195 * @param __a An allocator object.
196 */
197 explicit
198 unordered_map(const allocator_type& __a)
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 */
234 unordered_map(initializer_list<value_type> __l,
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.
282 unordered_map&
283 operator=(unordered_map&&) = default;
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 */
296 unordered_map&
297 operator=(initializer_list<value_type> __l)
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 */
331 iterator
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 */
353 iterator
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>
394 std::pair<iterator, bool>
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>
425 iterator
426 emplace_hint(const_iterator __pos, _Args&&... __args)
427 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
428
429#if __cplusplus > 201402L
430 /// Extract a node.
431 node_type
432 extract(const_iterator __pos)
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.
449 iterator
450 insert(const_iterator, node_type&& __nh)
451 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
452#endif // C++17
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>
478 pair<iterator, bool>
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>
486 pair<iterator, bool>
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
523 try_emplace(const_iterator __hint, const key_type& __k,
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>
532 iterator
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 */
558 std::pair<iterator, bool>
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
564 std::pair<iterator, bool>
565 insert(value_type&& __x)
566 { return _M_h.insert(std::move(__x)); }
567
568 template<typename _Pair>
569 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
570 pair<iterator, bool>>
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 */
597 iterator
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
603 iterator
604 insert(const_iterator __hint, value_type&& __x)
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
635 insert(initializer_list<value_type> __l)
636 { _M_h.insert(__l); }
637
638
639#if __cplusplus > 201402L
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>
661 pair<iterator, bool>
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>
673 pair<iterator, bool>
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
711 insert_or_assign(const_iterator __hint, const key_type& __k,
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>
722 iterator
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
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
748 erase(const_iterator __position)
749 { return _M_h.erase(__position); }
750
751 // LWG 2059.
752 iterator
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 */
787 iterator
788 erase(const_iterator __first, const_iterator __last)
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
812 swap(unordered_map& __x)
813 noexcept( noexcept(_M_h.swap(__x._M_h)) )
814 { _M_h.swap(__x._M_h); }
815
816#if __cplusplus > 201402L
817 template<typename, typename, typename>
818 friend class std::_Hash_merge_helper;
819
820 template<typename _H2, typename _P2>
821 void
822 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
823 {
824 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
825 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
826 }
827
828 template<typename _H2, typename _P2>
829 void
830 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
831 { merge(__source); }
832
833 template<typename _H2, typename _P2>
834 void
835 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
836 {
837 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
838 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
839 }
840
841 template<typename _H2, typename _P2>
842 void
843 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
844 { merge(__source); }
845#endif // C++17
846
847 // observers.
848
849 /// Returns the hash functor object with which the %unordered_map was
850 /// constructed.
851 hasher
852 hash_function() const
853 { return _M_h.hash_function(); }
854
855 /// Returns the key comparison object with which the %unordered_map was
856 /// constructed.
857 key_equal
858 key_eq() const
859 { return _M_h.key_eq(); }
860
861 // lookup.
862
863 ///@{
864 /**
865 * @brief Tries to locate an element in an %unordered_map.
866 * @param __x Key to be located.
867 * @return Iterator pointing to sought-after element, or end() if not
868 * found.
869 *
870 * This function takes a key and tries to locate the element with which
871 * the key matches. If successful the function returns an iterator
872 * pointing to the sought after element. If unsuccessful it returns the
873 * past-the-end ( @c end() ) iterator.
874 */
875 iterator
876 find(const key_type& __x)
877 { return _M_h.find(__x); }
878
879#if __cplusplus > 201703L
880 template<typename _Kt>
881 auto
882 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
883 { return _M_h._M_find_tr(__x); }
884#endif
885
886 const_iterator
887 find(const key_type& __x) const
888 { return _M_h.find(__x); }
889
890#if __cplusplus > 201703L
891 template<typename _Kt>
892 auto
893 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
894 { return _M_h._M_find_tr(__x); }
895#endif
896 ///@}
897
898 ///@{
899 /**
900 * @brief Finds the number of elements.
901 * @param __x Key to count.
902 * @return Number of elements with specified key.
903 *
904 * This function only makes sense for %unordered_multimap; for
905 * %unordered_map the result will either be 0 (not present) or 1
906 * (present).
907 */
908 size_type
909 count(const key_type& __x) const
910 { return _M_h.count(__x); }
911
912#if __cplusplus > 201703L
913 template<typename _Kt>
914 auto
915 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
916 { return _M_h._M_count_tr(__x); }
917#endif
918 ///@}
919
920#if __cplusplus > 201703L
921 ///@{
922 /**
923 * @brief Finds whether an element with the given key exists.
924 * @param __x Key of elements to be located.
925 * @return True if there is any element with the specified key.
926 */
927 bool
928 contains(const key_type& __x) const
929 { return _M_h.find(__x) != _M_h.end(); }
930
931 template<typename _Kt>
932 auto
933 contains(const _Kt& __x) const
934 -> decltype(_M_h._M_find_tr(__x), void(), true)
935 { return _M_h._M_find_tr(__x) != _M_h.end(); }
936 ///@}
937#endif
938
939 ///@{
940 /**
941 * @brief Finds a subsequence matching given key.
942 * @param __x Key to be located.
943 * @return Pair of iterators that possibly points to the subsequence
944 * matching given key.
945 *
946 * This function probably only makes sense for %unordered_multimap.
947 */
948 std::pair<iterator, iterator>
949 equal_range(const key_type& __x)
950 { return _M_h.equal_range(__x); }
951
952#if __cplusplus > 201703L
953 template<typename _Kt>
954 auto
955 equal_range(const _Kt& __x)
956 -> decltype(_M_h._M_equal_range_tr(__x))
957 { return _M_h._M_equal_range_tr(__x); }
958#endif
959
960 std::pair<const_iterator, const_iterator>
961 equal_range(const key_type& __x) const
962 { return _M_h.equal_range(__x); }
963
964#if __cplusplus > 201703L
965 template<typename _Kt>
966 auto
967 equal_range(const _Kt& __x) const
968 -> decltype(_M_h._M_equal_range_tr(__x))
969 { return _M_h._M_equal_range_tr(__x); }
970#endif
971 ///@}
972
973 ///@{
974 /**
975 * @brief Subscript ( @c [] ) access to %unordered_map data.
976 * @param __k The key for which data should be retrieved.
977 * @return A reference to the data of the (key,data) %pair.
978 *
979 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
980 * data associated with the key specified in subscript. If the key does
981 * not exist, a pair with that key is created using default values, which
982 * is then returned.
983 *
984 * Lookup requires constant time.
985 */
986 mapped_type&
987 operator[](const key_type& __k)
988 { return _M_h[__k]; }
989
990 mapped_type&
991 operator[](key_type&& __k)
992 { return _M_h[std::move(__k)]; }
993 ///@}
994
995 ///@{
996 /**
997 * @brief Access to %unordered_map data.
998 * @param __k The key for which data should be retrieved.
999 * @return A reference to the data whose key is equal to @a __k, if
1000 * such a data is present in the %unordered_map.
1001 * @throw std::out_of_range If no such data is present.
1002 */
1003 mapped_type&
1004 at(const key_type& __k)
1005 { return _M_h.at(__k); }
1006
1007 const mapped_type&
1008 at(const key_type& __k) const
1009 { return _M_h.at(__k); }
1010 ///@}
1011
1012 // bucket interface.
1013
1014 /// Returns the number of buckets of the %unordered_map.
1015 size_type
1016 bucket_count() const noexcept
1017 { return _M_h.bucket_count(); }
1018
1019 /// Returns the maximum number of buckets of the %unordered_map.
1020 size_type
1021 max_bucket_count() const noexcept
1022 { return _M_h.max_bucket_count(); }
1023
1024 /*
1025 * @brief Returns the number of elements in a given bucket.
1026 * @param __n A bucket index.
1027 * @return The number of elements in the bucket.
1028 */
1029 size_type
1030 bucket_size(size_type __n) const
1031 { return _M_h.bucket_size(__n); }
1032
1033 /*
1034 * @brief Returns the bucket index of a given element.
1035 * @param __key A key instance.
1036 * @return The key bucket index.
1037 */
1038 size_type
1039 bucket(const key_type& __key) const
1040 { return _M_h.bucket(__key); }
1041
1042 /**
1043 * @brief Returns a read/write iterator pointing to the first bucket
1044 * element.
1045 * @param __n The bucket index.
1046 * @return A read/write local iterator.
1047 */
1048 local_iterator
1049 begin(size_type __n)
1050 { return _M_h.begin(__n); }
1051
1052 ///@{
1053 /**
1054 * @brief Returns a read-only (constant) iterator pointing to the first
1055 * bucket element.
1056 * @param __n The bucket index.
1057 * @return A read-only local iterator.
1058 */
1059 const_local_iterator
1060 begin(size_type __n) const
1061 { return _M_h.begin(__n); }
1062
1063 const_local_iterator
1064 cbegin(size_type __n) const
1065 { return _M_h.cbegin(__n); }
1066 ///@}
1067
1068 /**
1069 * @brief Returns a read/write iterator pointing to one past the last
1070 * bucket elements.
1071 * @param __n The bucket index.
1072 * @return A read/write local iterator.
1073 */
1074 local_iterator
1075 end(size_type __n)
1076 { return _M_h.end(__n); }
1077
1078 ///@{
1079 /**
1080 * @brief Returns a read-only (constant) iterator pointing to one past
1081 * the last bucket elements.
1082 * @param __n The bucket index.
1083 * @return A read-only local iterator.
1084 */
1085 const_local_iterator
1086 end(size_type __n) const
1087 { return _M_h.end(__n); }
1088
1089 const_local_iterator
1090 cend(size_type __n) const
1091 { return _M_h.cend(__n); }
1092 ///@}
1093
1094 // hash policy.
1095
1096 /// Returns the average number of elements per bucket.
1097 float
1098 load_factor() const noexcept
1099 { return _M_h.load_factor(); }
1100
1101 /// Returns a positive number that the %unordered_map tries to keep the
1102 /// load factor less than or equal to.
1103 float
1104 max_load_factor() const noexcept
1105 { return _M_h.max_load_factor(); }
1106
1107 /**
1108 * @brief Change the %unordered_map maximum load factor.
1109 * @param __z The new maximum load factor.
1110 */
1111 void
1112 max_load_factor(float __z)
1113 { _M_h.max_load_factor(__z); }
1114
1115 /**
1116 * @brief May rehash the %unordered_map.
1117 * @param __n The new number of buckets.
1118 *
1119 * Rehash will occur only if the new number of buckets respect the
1120 * %unordered_map maximum load factor.
1121 */
1122 void
1123 rehash(size_type __n)
1124 { _M_h.rehash(__n); }
1125
1126 /**
1127 * @brief Prepare the %unordered_map for a specified number of
1128 * elements.
1129 * @param __n Number of elements required.
1130 *
1131 * Same as rehash(ceil(n / max_load_factor())).
1132 */
1133 void
1134 reserve(size_type __n)
1135 { _M_h.reserve(__n); }
1136
1137 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1138 typename _Alloc1>
1139 friend bool
1140 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
1141 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
1142 };
1143
1144#if __cpp_deduction_guides >= 201606
1145
1146 template<typename _InputIterator,
1147 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1148 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1149 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1150 typename = _RequireInputIter<_InputIterator>,
1151 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1152 typename = _RequireNotAllocator<_Pred>,
1153 typename = _RequireAllocator<_Allocator>>
1154 unordered_map(_InputIterator, _InputIterator,
1155 typename unordered_map<int, int>::size_type = {},
1156 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1157 -> unordered_map<__iter_key_t<_InputIterator>,
1158 __iter_val_t<_InputIterator>,
1159 _Hash, _Pred, _Allocator>;
1160
1161 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1162 typename _Pred = equal_to<_Key>,
1163 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1164 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1165 typename = _RequireNotAllocator<_Pred>,
1166 typename = _RequireAllocator<_Allocator>>
1167 unordered_map(initializer_list<pair<_Key, _Tp>>,
1168 typename unordered_map<int, int>::size_type = {},
1169 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1170 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
1171
1172 template<typename _InputIterator, typename _Allocator,
1173 typename = _RequireInputIter<_InputIterator>,
1174 typename = _RequireAllocator<_Allocator>>
1175 unordered_map(_InputIterator, _InputIterator,
1176 typename unordered_map<int, int>::size_type, _Allocator)
1177 -> unordered_map<__iter_key_t<_InputIterator>,
1178 __iter_val_t<_InputIterator>,
1179 hash<__iter_key_t<_InputIterator>>,
1180 equal_to<__iter_key_t<_InputIterator>>,
1181 _Allocator>;
1182
1183 template<typename _InputIterator, typename _Allocator,
1184 typename = _RequireInputIter<_InputIterator>,
1185 typename = _RequireAllocator<_Allocator>>
1186 unordered_map(_InputIterator, _InputIterator, _Allocator)
1187 -> unordered_map<__iter_key_t<_InputIterator>,
1188 __iter_val_t<_InputIterator>,
1189 hash<__iter_key_t<_InputIterator>>,
1190 equal_to<__iter_key_t<_InputIterator>>,
1191 _Allocator>;
1192
1193 template<typename _InputIterator, typename _Hash, typename _Allocator,
1194 typename = _RequireInputIter<_InputIterator>,
1195 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1196 typename = _RequireAllocator<_Allocator>>
1197 unordered_map(_InputIterator, _InputIterator,
1198 typename unordered_map<int, int>::size_type,
1199 _Hash, _Allocator)
1200 -> unordered_map<__iter_key_t<_InputIterator>,
1201 __iter_val_t<_InputIterator>, _Hash,
1202 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1203
1204 template<typename _Key, typename _Tp, typename _Allocator,
1205 typename = _RequireAllocator<_Allocator>>
1206 unordered_map(initializer_list<pair<_Key, _Tp>>,
1207 typename unordered_map<int, int>::size_type,
1208 _Allocator)
1209 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1210
1211 template<typename _Key, typename _Tp, typename _Allocator,
1212 typename = _RequireAllocator<_Allocator>>
1213 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1214 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1215
1216 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1217 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1218 typename = _RequireAllocator<_Allocator>>
1219 unordered_map(initializer_list<pair<_Key, _Tp>>,
1220 typename unordered_map<int, int>::size_type,
1221 _Hash, _Allocator)
1222 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1223
1224#endif
1225
1226 /**
1227 * @brief A standard container composed of equivalent keys
1228 * (possibly containing multiple of each key value) that associates
1229 * values of another type with the keys.
1230 *
1231 * @ingroup unordered_associative_containers
1232 * @headerfile unordered_map
1233 * @since C++11
1234 *
1235 * @tparam _Key Type of key objects.
1236 * @tparam _Tp Type of mapped objects.
1237 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1238 * @tparam _Pred Predicate function object type, defaults
1239 * to equal_to<_Value>.
1240 * @tparam _Alloc Allocator type, defaults to
1241 * std::allocator<std::pair<const _Key, _Tp>>.
1242 *
1243 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1244 * <a href="tables.html#xx">unordered associative container</a>
1245 *
1246 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1247 *
1248 * Base is _Hashtable, dispatched at compile time via template
1249 * alias __ummap_hashtable.
1250 */
1251 template<typename _Key, typename _Tp,
1252 typename _Hash = hash<_Key>,
1253 typename _Pred = equal_to<_Key>,
1254 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1255 class unordered_multimap
1256 {
1257 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
1258 _Hashtable _M_h;
1259
1260 public:
1261 // typedefs:
1262 ///@{
1263 /// Public typedefs.
1264 typedef typename _Hashtable::key_type key_type;
1265 typedef typename _Hashtable::value_type value_type;
1266 typedef typename _Hashtable::mapped_type mapped_type;
1267 typedef typename _Hashtable::hasher hasher;
1268 typedef typename _Hashtable::key_equal key_equal;
1269 typedef typename _Hashtable::allocator_type allocator_type;
1270 ///@}
1271
1272 ///@{
1273 /// Iterator-related typedefs.
1274 typedef typename _Hashtable::pointer pointer;
1275 typedef typename _Hashtable::const_pointer const_pointer;
1276 typedef typename _Hashtable::reference reference;
1277 typedef typename _Hashtable::const_reference const_reference;
1278 typedef typename _Hashtable::iterator iterator;
1279 typedef typename _Hashtable::const_iterator const_iterator;
1280 typedef typename _Hashtable::local_iterator local_iterator;
1281 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1282 typedef typename _Hashtable::size_type size_type;
1283 typedef typename _Hashtable::difference_type difference_type;
1284 ///@}
1285
1286#if __cplusplus > 201402L
1287 using node_type = typename _Hashtable::node_type;
1288#endif
1289
1290 //construct/destroy/copy
1291
1292 /// Default constructor.
1293 unordered_multimap() = default;
1294
1295 /**
1296 * @brief Default constructor creates no elements.
1297 * @param __n Mnimal initial number of buckets.
1298 * @param __hf A hash functor.
1299 * @param __eql A key equality functor.
1300 * @param __a An allocator object.
1301 */
1302 explicit
1303 unordered_multimap(size_type __n,
1304 const hasher& __hf = hasher(),
1305 const key_equal& __eql = key_equal(),
1306 const allocator_type& __a = allocator_type())
1307 : _M_h(__n, __hf, __eql, __a)
1308 { }
1309
1310 /**
1311 * @brief Builds an %unordered_multimap from a range.
1312 * @param __first An input iterator.
1313 * @param __last An input iterator.
1314 * @param __n Minimal initial number of buckets.
1315 * @param __hf A hash functor.
1316 * @param __eql A key equality functor.
1317 * @param __a An allocator object.
1318 *
1319 * Create an %unordered_multimap consisting of copies of the elements
1320 * from [__first,__last). This is linear in N (where N is
1321 * distance(__first,__last)).
1322 */
1323 template<typename _InputIterator>
1324 unordered_multimap(_InputIterator __first, _InputIterator __last,
1325 size_type __n = 0,
1326 const hasher& __hf = hasher(),
1327 const key_equal& __eql = key_equal(),
1328 const allocator_type& __a = allocator_type())
1329 : _M_h(__first, __last, __n, __hf, __eql, __a)
1330 { }
1331
1332 /// Copy constructor.
1333 unordered_multimap(const unordered_multimap&) = default;
1334
1335 /// Move constructor.
1336 unordered_multimap(unordered_multimap&&) = default;
1337
1338 /**
1339 * @brief Creates an %unordered_multimap with no elements.
1340 * @param __a An allocator object.
1341 */
1342 explicit
1343 unordered_multimap(const allocator_type& __a)
1344 : _M_h(__a)
1345 { }
1346
1347 /*
1348 * @brief Copy constructor with allocator argument.
1349 * @param __uset Input %unordered_multimap to copy.
1350 * @param __a An allocator object.
1351 */
1352 unordered_multimap(const unordered_multimap& __ummap,
1353 const allocator_type& __a)
1354 : _M_h(__ummap._M_h, __a)
1355 { }
1356
1357 /*
1358 * @brief Move constructor with allocator argument.
1359 * @param __uset Input %unordered_multimap to move.
1360 * @param __a An allocator object.
1361 */
1362 unordered_multimap(unordered_multimap&& __ummap,
1363 const allocator_type& __a)
1364 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1365 : _M_h(std::move(__ummap._M_h), __a)
1366 { }
1367
1368 /**
1369 * @brief Builds an %unordered_multimap from an initializer_list.
1370 * @param __l An initializer_list.
1371 * @param __n Minimal initial number of buckets.
1372 * @param __hf A hash functor.
1373 * @param __eql A key equality functor.
1374 * @param __a An allocator object.
1375 *
1376 * Create an %unordered_multimap consisting of copies of the elements in
1377 * the list. This is linear in N (where N is @a __l.size()).
1378 */
1379 unordered_multimap(initializer_list<value_type> __l,
1380 size_type __n = 0,
1381 const hasher& __hf = hasher(),
1382 const key_equal& __eql = key_equal(),
1383 const allocator_type& __a = allocator_type())
1384 : _M_h(__l, __n, __hf, __eql, __a)
1385 { }
1386
1387 unordered_multimap(size_type __n, const allocator_type& __a)
1388 : unordered_multimap(__n, hasher(), key_equal(), __a)
1389 { }
1390
1391 unordered_multimap(size_type __n, const hasher& __hf,
1392 const allocator_type& __a)
1393 : unordered_multimap(__n, __hf, key_equal(), __a)
1394 { }
1395
1396 template<typename _InputIterator>
1397 unordered_multimap(_InputIterator __first, _InputIterator __last,
1398 size_type __n,
1399 const allocator_type& __a)
1400 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1401 { }
1402
1403 template<typename _InputIterator>
1404 unordered_multimap(_InputIterator __first, _InputIterator __last,
1405 size_type __n, const hasher& __hf,
1406 const allocator_type& __a)
1407 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1408 { }
1409
1410 unordered_multimap(initializer_list<value_type> __l,
1411 size_type __n,
1412 const allocator_type& __a)
1413 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1414 { }
1415
1416 unordered_multimap(initializer_list<value_type> __l,
1417 size_type __n, const hasher& __hf,
1418 const allocator_type& __a)
1419 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1420 { }
1421
1422 /// Copy assignment operator.
1423 unordered_multimap&
1424 operator=(const unordered_multimap&) = default;
1425
1426 /// Move assignment operator.
1427 unordered_multimap&
1428 operator=(unordered_multimap&&) = default;
1429
1430 /**
1431 * @brief %Unordered_multimap list assignment operator.
1432 * @param __l An initializer_list.
1433 *
1434 * This function fills an %unordered_multimap with copies of the
1435 * elements in the initializer list @a __l.
1436 *
1437 * Note that the assignment completely changes the %unordered_multimap
1438 * and that the resulting %unordered_multimap's size is the same as the
1439 * number of elements assigned.
1440 */
1441 unordered_multimap&
1442 operator=(initializer_list<value_type> __l)
1443 {
1444 _M_h = __l;
1445 return *this;
1446 }
1447
1448 /// Returns the allocator object used by the %unordered_multimap.
1449 allocator_type
1450 get_allocator() const noexcept
1451 { return _M_h.get_allocator(); }
1452
1453 // size and capacity:
1454
1455 /// Returns true if the %unordered_multimap is empty.
1456 _GLIBCXX_NODISCARD bool
1457 empty() const noexcept
1458 { return _M_h.empty(); }
1459
1460 /// Returns the size of the %unordered_multimap.
1461 size_type
1462 size() const noexcept
1463 { return _M_h.size(); }
1464
1465 /// Returns the maximum size of the %unordered_multimap.
1466 size_type
1467 max_size() const noexcept
1468 { return _M_h.max_size(); }
1469
1470 // iterators.
1471
1472 /**
1473 * Returns a read/write iterator that points to the first element in the
1474 * %unordered_multimap.
1475 */
1476 iterator
1477 begin() noexcept
1478 { return _M_h.begin(); }
1479
1480 ///@{
1481 /**
1482 * Returns a read-only (constant) iterator that points to the first
1483 * element in the %unordered_multimap.
1484 */
1485 const_iterator
1486 begin() const noexcept
1487 { return _M_h.begin(); }
1488
1489 const_iterator
1490 cbegin() const noexcept
1491 { return _M_h.begin(); }
1492 ///@}
1493
1494 /**
1495 * Returns a read/write iterator that points one past the last element in
1496 * the %unordered_multimap.
1497 */
1498 iterator
1499 end() noexcept
1500 { return _M_h.end(); }
1501
1502 ///@{
1503 /**
1504 * Returns a read-only (constant) iterator that points one past the last
1505 * element in the %unordered_multimap.
1506 */
1507 const_iterator
1508 end() const noexcept
1509 { return _M_h.end(); }
1510
1511 const_iterator
1512 cend() const noexcept
1513 { return _M_h.end(); }
1514 ///@}
1515
1516 // modifiers.
1517
1518 /**
1519 * @brief Attempts to build and insert a std::pair into the
1520 * %unordered_multimap.
1521 *
1522 * @param __args Arguments used to generate a new pair instance (see
1523 * std::piecewise_contruct for passing arguments to each
1524 * part of the pair constructor).
1525 *
1526 * @return An iterator that points to the inserted pair.
1527 *
1528 * This function attempts to build and insert a (key, value) %pair into
1529 * the %unordered_multimap.
1530 *
1531 * Insertion requires amortized constant time.
1532 */
1533 template<typename... _Args>
1534 iterator
1535 emplace(_Args&&... __args)
1536 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1537
1538 /**
1539 * @brief Attempts to build and insert a std::pair into the
1540 * %unordered_multimap.
1541 *
1542 * @param __pos An iterator that serves as a hint as to where the pair
1543 * should be inserted.
1544 * @param __args Arguments used to generate a new pair instance (see
1545 * std::piecewise_contruct for passing arguments to each
1546 * part of the pair constructor).
1547 * @return An iterator that points to the element with key of the
1548 * std::pair built from @a __args.
1549 *
1550 * Note that the first parameter is only a hint and can potentially
1551 * improve the performance of the insertion process. A bad hint would
1552 * cause no gains in efficiency.
1553 *
1554 * See
1555 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1556 * for more on @a hinting.
1557 *
1558 * Insertion requires amortized constant time.
1559 */
1560 template<typename... _Args>
1561 iterator
1562 emplace_hint(const_iterator __pos, _Args&&... __args)
1563 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1564
1565 ///@{
1566 /**
1567 * @brief Inserts a std::pair into the %unordered_multimap.
1568 * @param __x Pair to be inserted (see std::make_pair for easy
1569 * creation of pairs).
1570 *
1571 * @return An iterator that points to the inserted pair.
1572 *
1573 * Insertion requires amortized constant time.
1574 */
1575 iterator
1576 insert(const value_type& __x)
1577 { return _M_h.insert(__x); }
1578
1579 iterator
1580 insert(value_type&& __x)
1581 { return _M_h.insert(std::move(__x)); }
1582
1583 template<typename _Pair>
1584 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1585 insert(_Pair&& __x)
1586 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1587 ///@}
1588
1589 ///@{
1590 /**
1591 * @brief Inserts a std::pair into the %unordered_multimap.
1592 * @param __hint An iterator that serves as a hint as to where the
1593 * pair should be inserted.
1594 * @param __x Pair to be inserted (see std::make_pair for easy creation
1595 * of pairs).
1596 * @return An iterator that points to the element with key of
1597 * @a __x (may or may not be the %pair passed in).
1598 *
1599 * Note that the first parameter is only a hint and can potentially
1600 * improve the performance of the insertion process. A bad hint would
1601 * cause no gains in efficiency.
1602 *
1603 * See
1604 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1605 * for more on @a hinting.
1606 *
1607 * Insertion requires amortized constant time.
1608 */
1609 iterator
1610 insert(const_iterator __hint, const value_type& __x)
1611 { return _M_h.insert(__hint, __x); }
1612
1613 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1614 // 2354. Unnecessary copying when inserting into maps with braced-init
1615 iterator
1616 insert(const_iterator __hint, value_type&& __x)
1617 { return _M_h.insert(__hint, std::move(__x)); }
1618
1619 template<typename _Pair>
1620 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1621 insert(const_iterator __hint, _Pair&& __x)
1622 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1623 ///@}
1624
1625 /**
1626 * @brief A template function that attempts to insert a range of
1627 * elements.
1628 * @param __first Iterator pointing to the start of the range to be
1629 * inserted.
1630 * @param __last Iterator pointing to the end of the range.
1631 *
1632 * Complexity similar to that of the range constructor.
1633 */
1634 template<typename _InputIterator>
1635 void
1636 insert(_InputIterator __first, _InputIterator __last)
1637 { _M_h.insert(__first, __last); }
1638
1639 /**
1640 * @brief Attempts to insert a list of elements into the
1641 * %unordered_multimap.
1642 * @param __l A std::initializer_list<value_type> of elements
1643 * to be inserted.
1644 *
1645 * Complexity similar to that of the range constructor.
1646 */
1647 void
1648 insert(initializer_list<value_type> __l)
1649 { _M_h.insert(__l); }
1650
1651#if __cplusplus > 201402L
1652 /// Extract a node.
1653 node_type
1654 extract(const_iterator __pos)
1655 {
1656 __glibcxx_assert(__pos != end());
1657 return _M_h.extract(__pos);
1658 }
1659
1660 /// Extract a node.
1661 node_type
1662 extract(const key_type& __key)
1663 { return _M_h.extract(__key); }
1664
1665 /// Re-insert an extracted node.
1666 iterator
1667 insert(node_type&& __nh)
1668 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1669
1670 /// Re-insert an extracted node.
1671 iterator
1672 insert(const_iterator __hint, node_type&& __nh)
1673 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1674#endif // C++17
1675
1676 ///@{
1677 /**
1678 * @brief Erases an element from an %unordered_multimap.
1679 * @param __position An iterator pointing to the element to be erased.
1680 * @return An iterator pointing to the element immediately following
1681 * @a __position prior to the element being erased. If no such
1682 * element exists, end() is returned.
1683 *
1684 * This function erases an element, pointed to by the given iterator,
1685 * from an %unordered_multimap.
1686 * Note that this function only erases the element, and that if the
1687 * element is itself a pointer, the pointed-to memory is not touched in
1688 * any way. Managing the pointer is the user's responsibility.
1689 */
1690 iterator
1691 erase(const_iterator __position)
1692 { return _M_h.erase(__position); }
1693
1694 // LWG 2059.
1695 iterator
1696 erase(iterator __position)
1697 { return _M_h.erase(__position); }
1698 ///@}
1699
1700 /**
1701 * @brief Erases elements according to the provided key.
1702 * @param __x Key of elements to be erased.
1703 * @return The number of elements erased.
1704 *
1705 * This function erases all the elements located by the given key from
1706 * an %unordered_multimap.
1707 * Note that this function only erases the element, and that if the
1708 * element is itself a pointer, the pointed-to memory is not touched in
1709 * any way. Managing the pointer is the user's responsibility.
1710 */
1711 size_type
1712 erase(const key_type& __x)
1713 { return _M_h.erase(__x); }
1714
1715 /**
1716 * @brief Erases a [__first,__last) range of elements from an
1717 * %unordered_multimap.
1718 * @param __first Iterator pointing to the start of the range to be
1719 * erased.
1720 * @param __last Iterator pointing to the end of the range to
1721 * be erased.
1722 * @return The iterator @a __last.
1723 *
1724 * This function erases a sequence of elements from an
1725 * %unordered_multimap.
1726 * Note that this function only erases the elements, and that if
1727 * the element is itself a pointer, the pointed-to memory is not touched
1728 * in any way. Managing the pointer is the user's responsibility.
1729 */
1730 iterator
1731 erase(const_iterator __first, const_iterator __last)
1732 { return _M_h.erase(__first, __last); }
1733
1734 /**
1735 * Erases all elements in an %unordered_multimap.
1736 * Note that this function only erases the elements, and that if the
1737 * elements themselves are pointers, the pointed-to memory is not touched
1738 * in any way. Managing the pointer is the user's responsibility.
1739 */
1740 void
1741 clear() noexcept
1742 { _M_h.clear(); }
1743
1744 /**
1745 * @brief Swaps data with another %unordered_multimap.
1746 * @param __x An %unordered_multimap of the same element and allocator
1747 * types.
1748 *
1749 * This exchanges the elements between two %unordered_multimap in
1750 * constant time.
1751 * Note that the global std::swap() function is specialized such that
1752 * std::swap(m1,m2) will feed to this function.
1753 */
1754 void
1755 swap(unordered_multimap& __x)
1756 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1757 { _M_h.swap(__x._M_h); }
1758
1759#if __cplusplus > 201402L
1760 template<typename, typename, typename>
1761 friend class std::_Hash_merge_helper;
1762
1763 template<typename _H2, typename _P2>
1764 void
1765 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1766 {
1767 using _Merge_helper
1768 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1769 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1770 }
1771
1772 template<typename _H2, typename _P2>
1773 void
1774 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1775 { merge(__source); }
1776
1777 template<typename _H2, typename _P2>
1778 void
1779 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1780 {
1781 using _Merge_helper
1782 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1783 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1784 }
1785
1786 template<typename _H2, typename _P2>
1787 void
1788 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1789 { merge(__source); }
1790#endif // C++17
1791
1792 // observers.
1793
1794 /// Returns the hash functor object with which the %unordered_multimap
1795 /// was constructed.
1796 hasher
1797 hash_function() const
1798 { return _M_h.hash_function(); }
1799
1800 /// Returns the key comparison object with which the %unordered_multimap
1801 /// was constructed.
1802 key_equal
1803 key_eq() const
1804 { return _M_h.key_eq(); }
1805
1806 // lookup.
1807
1808 ///@{
1809 /**
1810 * @brief Tries to locate an element in an %unordered_multimap.
1811 * @param __x Key to be located.
1812 * @return Iterator pointing to sought-after element, or end() if not
1813 * found.
1814 *
1815 * This function takes a key and tries to locate the element with which
1816 * the key matches. If successful the function returns an iterator
1817 * pointing to the sought after element. If unsuccessful it returns the
1818 * past-the-end ( @c end() ) iterator.
1819 */
1820 iterator
1821 find(const key_type& __x)
1822 { return _M_h.find(__x); }
1823
1824#if __cplusplus > 201703L
1825 template<typename _Kt>
1826 auto
1827 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
1828 { return _M_h._M_find_tr(__x); }
1829#endif
1830
1831 const_iterator
1832 find(const key_type& __x) const
1833 { return _M_h.find(__x); }
1834
1835#if __cplusplus > 201703L
1836 template<typename _Kt>
1837 auto
1838 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
1839 { return _M_h._M_find_tr(__x); }
1840#endif
1841 ///@}
1842
1843 ///@{
1844 /**
1845 * @brief Finds the number of elements.
1846 * @param __x Key to count.
1847 * @return Number of elements with specified key.
1848 */
1849 size_type
1850 count(const key_type& __x) const
1851 { return _M_h.count(__x); }
1852
1853#if __cplusplus > 201703L
1854 template<typename _Kt>
1855 auto
1856 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1857 { return _M_h._M_count_tr(__x); }
1858#endif
1859 ///@}
1860
1861#if __cplusplus > 201703L
1862 ///@{
1863 /**
1864 * @brief Finds whether an element with the given key exists.
1865 * @param __x Key of elements to be located.
1866 * @return True if there is any element with the specified key.
1867 */
1868 bool
1869 contains(const key_type& __x) const
1870 { return _M_h.find(__x) != _M_h.end(); }
1871
1872 template<typename _Kt>
1873 auto
1874 contains(const _Kt& __x) const
1875 -> decltype(_M_h._M_find_tr(__x), void(), true)
1876 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1877 ///@}
1878#endif
1879
1880 ///@{
1881 /**
1882 * @brief Finds a subsequence matching given key.
1883 * @param __x Key to be located.
1884 * @return Pair of iterators that possibly points to the subsequence
1885 * matching given key.
1886 */
1887 std::pair<iterator, iterator>
1888 equal_range(const key_type& __x)
1889 { return _M_h.equal_range(__x); }
1890
1891#if __cplusplus > 201703L
1892 template<typename _Kt>
1893 auto
1894 equal_range(const _Kt& __x)
1895 -> decltype(_M_h._M_equal_range_tr(__x))
1896 { return _M_h._M_equal_range_tr(__x); }
1897#endif
1898
1899 std::pair<const_iterator, const_iterator>
1900 equal_range(const key_type& __x) const
1901 { return _M_h.equal_range(__x); }
1902
1903#if __cplusplus > 201703L
1904 template<typename _Kt>
1905 auto
1906 equal_range(const _Kt& __x) const
1907 -> decltype(_M_h._M_equal_range_tr(__x))
1908 { return _M_h._M_equal_range_tr(__x); }
1909#endif
1910 ///@}
1911
1912 // bucket interface.
1913
1914 /// Returns the number of buckets of the %unordered_multimap.
1915 size_type
1916 bucket_count() const noexcept
1917 { return _M_h.bucket_count(); }
1918
1919 /// Returns the maximum number of buckets of the %unordered_multimap.
1920 size_type
1921 max_bucket_count() const noexcept
1922 { return _M_h.max_bucket_count(); }
1923
1924 /*
1925 * @brief Returns the number of elements in a given bucket.
1926 * @param __n A bucket index.
1927 * @return The number of elements in the bucket.
1928 */
1929 size_type
1930 bucket_size(size_type __n) const
1931 { return _M_h.bucket_size(__n); }
1932
1933 /*
1934 * @brief Returns the bucket index of a given element.
1935 * @param __key A key instance.
1936 * @return The key bucket index.
1937 */
1938 size_type
1939 bucket(const key_type& __key) const
1940 { return _M_h.bucket(__key); }
1941
1942 /**
1943 * @brief Returns a read/write iterator pointing to the first bucket
1944 * element.
1945 * @param __n The bucket index.
1946 * @return A read/write local iterator.
1947 */
1948 local_iterator
1949 begin(size_type __n)
1950 { return _M_h.begin(__n); }
1951
1952 ///@{
1953 /**
1954 * @brief Returns a read-only (constant) iterator pointing to the first
1955 * bucket element.
1956 * @param __n The bucket index.
1957 * @return A read-only local iterator.
1958 */
1959 const_local_iterator
1960 begin(size_type __n) const
1961 { return _M_h.begin(__n); }
1962
1963 const_local_iterator
1964 cbegin(size_type __n) const
1965 { return _M_h.cbegin(__n); }
1966 ///@}
1967
1968 /**
1969 * @brief Returns a read/write iterator pointing to one past the last
1970 * bucket elements.
1971 * @param __n The bucket index.
1972 * @return A read/write local iterator.
1973 */
1974 local_iterator
1975 end(size_type __n)
1976 { return _M_h.end(__n); }
1977
1978 ///@{
1979 /**
1980 * @brief Returns a read-only (constant) iterator pointing to one past
1981 * the last bucket elements.
1982 * @param __n The bucket index.
1983 * @return A read-only local iterator.
1984 */
1985 const_local_iterator
1986 end(size_type __n) const
1987 { return _M_h.end(__n); }
1988
1989 const_local_iterator
1990 cend(size_type __n) const
1991 { return _M_h.cend(__n); }
1992 ///@}
1993
1994 // hash policy.
1995
1996 /// Returns the average number of elements per bucket.
1997 float
1998 load_factor() const noexcept
1999 { return _M_h.load_factor(); }
2000
2001 /// Returns a positive number that the %unordered_multimap tries to keep
2002 /// the load factor less than or equal to.
2003 float
2004 max_load_factor() const noexcept
2005 { return _M_h.max_load_factor(); }
2006
2007 /**
2008 * @brief Change the %unordered_multimap maximum load factor.
2009 * @param __z The new maximum load factor.
2010 */
2011 void
2012 max_load_factor(float __z)
2013 { _M_h.max_load_factor(__z); }
2014
2015 /**
2016 * @brief May rehash the %unordered_multimap.
2017 * @param __n The new number of buckets.
2018 *
2019 * Rehash will occur only if the new number of buckets respect the
2020 * %unordered_multimap maximum load factor.
2021 */
2022 void
2023 rehash(size_type __n)
2024 { _M_h.rehash(__n); }
2025
2026 /**
2027 * @brief Prepare the %unordered_multimap for a specified number of
2028 * elements.
2029 * @param __n Number of elements required.
2030 *
2031 * Same as rehash(ceil(n / max_load_factor())).
2032 */
2033 void
2034 reserve(size_type __n)
2035 { _M_h.reserve(__n); }
2036
2037 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
2038 typename _Alloc1>
2039 friend bool
2040 operator==(const unordered_multimap<_Key1, _Tp1,
2041 _Hash1, _Pred1, _Alloc1>&,
2042 const unordered_multimap<_Key1, _Tp1,
2043 _Hash1, _Pred1, _Alloc1>&);
2044 };
2045
2046#if __cpp_deduction_guides >= 201606
2047
2048 template<typename _InputIterator,
2049 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2050 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2051 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2052 typename = _RequireInputIter<_InputIterator>,
2053 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2054 typename = _RequireNotAllocator<_Pred>,
2055 typename = _RequireAllocator<_Allocator>>
2056 unordered_multimap(_InputIterator, _InputIterator,
2057 unordered_multimap<int, int>::size_type = {},
2058 _Hash = _Hash(), _Pred = _Pred(),
2059 _Allocator = _Allocator())
2060 -> unordered_multimap<__iter_key_t<_InputIterator>,
2061 __iter_val_t<_InputIterator>, _Hash, _Pred,
2062 _Allocator>;
2063
2064 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2065 typename _Pred = equal_to<_Key>,
2066 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2067 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2068 typename = _RequireNotAllocator<_Pred>,
2069 typename = _RequireAllocator<_Allocator>>
2070 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2071 unordered_multimap<int, int>::size_type = {},
2072 _Hash = _Hash(), _Pred = _Pred(),
2073 _Allocator = _Allocator())
2074 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2075
2076 template<typename _InputIterator, typename _Allocator,
2077 typename = _RequireInputIter<_InputIterator>,
2078 typename = _RequireAllocator<_Allocator>>
2079 unordered_multimap(_InputIterator, _InputIterator,
2080 unordered_multimap<int, int>::size_type, _Allocator)
2081 -> unordered_multimap<__iter_key_t<_InputIterator>,
2082 __iter_val_t<_InputIterator>,
2083 hash<__iter_key_t<_InputIterator>>,
2084 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2085
2086 template<typename _InputIterator, typename _Allocator,
2087 typename = _RequireInputIter<_InputIterator>,
2088 typename = _RequireAllocator<_Allocator>>
2089 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2090 -> unordered_multimap<__iter_key_t<_InputIterator>,
2091 __iter_val_t<_InputIterator>,
2092 hash<__iter_key_t<_InputIterator>>,
2093 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2094
2095 template<typename _InputIterator, typename _Hash, typename _Allocator,
2096 typename = _RequireInputIter<_InputIterator>,
2097 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2098 typename = _RequireAllocator<_Allocator>>
2099 unordered_multimap(_InputIterator, _InputIterator,
2100 unordered_multimap<int, int>::size_type, _Hash,
2101 _Allocator)
2102 -> unordered_multimap<__iter_key_t<_InputIterator>,
2103 __iter_val_t<_InputIterator>, _Hash,
2104 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2105
2106 template<typename _Key, typename _Tp, typename _Allocator,
2107 typename = _RequireAllocator<_Allocator>>
2108 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2109 unordered_multimap<int, int>::size_type,
2110 _Allocator)
2111 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2112
2113 template<typename _Key, typename _Tp, typename _Allocator,
2114 typename = _RequireAllocator<_Allocator>>
2115 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2116 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2117
2118 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2119 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2120 typename = _RequireAllocator<_Allocator>>
2121 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2122 unordered_multimap<int, int>::size_type,
2123 _Hash, _Allocator)
2124 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
2125
2126#endif
2127
2128 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2129 inline void
2130 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2131 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2132 noexcept(noexcept(__x.swap(__y)))
2133 { __x.swap(__y); }
2134
2135 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2136 inline void
2137 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2138 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2139 noexcept(noexcept(__x.swap(__y)))
2140 { __x.swap(__y); }
2141
2142 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2143 inline bool
2144 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2145 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2146 { return __x._M_h._M_equal(__y._M_h); }
2147
2148#if __cpp_impl_three_way_comparison < 201907L
2149 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2150 inline bool
2151 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2152 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2153 { return !(__x == __y); }
2154#endif
2155
2156 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2157 inline bool
2158 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2159 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2160 { return __x._M_h._M_equal(__y._M_h); }
2161
2162#if __cpp_impl_three_way_comparison < 201907L
2163 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2164 inline bool
2165 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2166 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2167 { return !(__x == __y); }
2168#endif
2169
2170_GLIBCXX_END_NAMESPACE_CONTAINER
2171
2172#if __cplusplus > 201402L
2173 // Allow std::unordered_map access to internals of compatible maps.
2174 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2175 typename _Alloc, typename _Hash2, typename _Eq2>
2176 struct _Hash_merge_helper<
2177 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2178 _Hash2, _Eq2>
2179 {
2180 private:
2181 template<typename... _Tp>
2182 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2183 template<typename... _Tp>
2184 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2185
2186 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2187
2188 static auto&
2189 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2190 { return __map._M_h; }
2191
2192 static auto&
2193 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2194 { return __map._M_h; }
2195 };
2196
2197 // Allow std::unordered_multimap access to internals of compatible maps.
2198 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2199 typename _Alloc, typename _Hash2, typename _Eq2>
2200 struct _Hash_merge_helper<
2201 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2202 _Hash2, _Eq2>
2203 {
2204 private:
2205 template<typename... _Tp>
2206 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2207 template<typename... _Tp>
2208 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2209
2210 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2211
2212 static auto&
2213 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2214 { return __map._M_h; }
2215
2216 static auto&
2217 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2218 { return __map._M_h; }
2219 };
2220#endif // C++17
2221
2222_GLIBCXX_END_NAMESPACE_VERSION
2223} // namespace std
2224
2225#endif /* _UNORDERED_MAP_H */
2226