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