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