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