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