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