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