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_containers_ranges // 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 */
220 unordered_map(unordered_map&& __umap,
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_containers_ranges // 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 // _GLIBCXX_RESOLVE_LIB_DEFECTS
304 // 2713. More missing allocator-extended constructors for unordered containers
305 template<__detail::__container_compatible_range<value_type> _Rg>
306 unordered_map(from_range_t, _Rg&& __rg, const allocator_type& __a)
307 : _M_h(0, hasher(), key_equal(), __a)
308 { insert_range(std::forward<_Rg>(__rg)); }
309
310 template<__detail::__container_compatible_range<value_type> _Rg>
311 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
312 const allocator_type& __a)
313 : _M_h(__n, hasher(), key_equal(), __a)
314 { insert_range(std::forward<_Rg>(__rg)); }
315
316 template<__detail::__container_compatible_range<value_type> _Rg>
317 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
318 const hasher& __hf, const allocator_type& __a)
319 : _M_h(__n, __hf, key_equal(), __a)
320 { insert_range(std::forward<_Rg>(__rg)); }
321#endif
322
323 /// Copy assignment operator.
325 operator=(const unordered_map&) = default;
326
327 /// Move assignment operator.
330
331 /**
332 * @brief %Unordered_map list assignment operator.
333 * @param __l An initializer_list.
334 *
335 * This function fills an %unordered_map with copies of the elements in
336 * the initializer list @a __l.
337 *
338 * Note that the assignment completely changes the %unordered_map and
339 * that the resulting %unordered_map's size is the same as the number
340 * of elements assigned.
341 */
344 {
345 _M_h = __l;
346 return *this;
347 }
348
349 /// Returns the allocator object used by the %unordered_map.
350 allocator_type
351 get_allocator() const noexcept
352 { return _M_h.get_allocator(); }
353
354 // size and capacity:
355
356 /// Returns true if the %unordered_map is empty.
357 _GLIBCXX_NODISCARD bool
358 empty() const noexcept
359 { return _M_h.empty(); }
360
361 /// Returns the size of the %unordered_map.
363 size() const noexcept
364 { return _M_h.size(); }
365
366 /// Returns the maximum size of the %unordered_map.
368 max_size() const noexcept
369 { return _M_h.max_size(); }
370
371 // iterators.
372
373 /**
374 * Returns a read/write iterator that points to the first element in the
375 * %unordered_map.
376 */
378 begin() noexcept
379 { return _M_h.begin(); }
380
381 ///@{
382 /**
383 * Returns a read-only (constant) iterator that points to the first
384 * element in the %unordered_map.
385 */
386 const_iterator
387 begin() const noexcept
388 { return _M_h.begin(); }
389
390 const_iterator
391 cbegin() const noexcept
392 { return _M_h.begin(); }
393 ///@}
394
395 /**
396 * Returns a read/write iterator that points one past the last element in
397 * the %unordered_map.
398 */
400 end() noexcept
401 { return _M_h.end(); }
402
403 ///@{
404 /**
405 * Returns a read-only (constant) iterator that points one past the last
406 * element in the %unordered_map.
407 */
408 const_iterator
409 end() const noexcept
410 { return _M_h.end(); }
411
412 const_iterator
413 cend() const noexcept
414 { return _M_h.end(); }
415 ///@}
416
417 // modifiers.
418
419 /**
420 * @brief Attempts to build and insert a std::pair into the
421 * %unordered_map.
422 *
423 * @param __args Arguments used to generate a new pair instance (see
424 * std::piecewise_contruct for passing arguments to each
425 * part of the pair constructor).
426 *
427 * @return A pair, of which the first element is an iterator that points
428 * to the possibly inserted pair, and the second is a bool that
429 * is true if the pair was actually inserted.
430 *
431 * This function attempts to build and insert a (key, value) %pair into
432 * the %unordered_map.
433 * An %unordered_map relies on unique keys and thus a %pair is only
434 * inserted if its first element (the key) is not already present in the
435 * %unordered_map.
436 *
437 * Insertion requires amortized constant time.
438 */
439 template<typename... _Args>
441 emplace(_Args&&... __args)
442 { return _M_h.emplace(std::forward<_Args>(__args)...); }
443
444 /**
445 * @brief Attempts to build and insert a std::pair into the
446 * %unordered_map.
447 *
448 * @param __pos An iterator that serves as a hint as to where the pair
449 * should be inserted.
450 * @param __args Arguments used to generate a new pair instance (see
451 * std::piecewise_contruct for passing arguments to each
452 * part of the pair constructor).
453 * @return An iterator that points to the element with key of the
454 * std::pair built from @a __args (may or may not be that
455 * std::pair).
456 *
457 * This function is not concerned about whether the insertion took place,
458 * and thus does not return a boolean like the single-argument emplace()
459 * does.
460 * Note that the first parameter is only a hint and can potentially
461 * improve the performance of the insertion process. A bad hint would
462 * cause no gains in efficiency.
463 *
464 * See
465 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
466 * for more on @a hinting.
467 *
468 * Insertion requires amortized constant time.
469 */
470 template<typename... _Args>
472 emplace_hint(const_iterator __pos, _Args&&... __args)
473 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
474
475#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
476 /// Extract a node.
477 node_type
478 extract(const_iterator __pos)
479 {
480 __glibcxx_assert(__pos != end());
481 return _M_h.extract(__pos);
482 }
483
484 /// Extract a node.
485 node_type
486 extract(const key_type& __key)
487 { return _M_h.extract(__key); }
488
489 /// Re-insert an extracted node.
490 insert_return_type
491 insert(node_type&& __nh)
492 { return _M_h._M_reinsert_node(std::move(__nh)); }
493
494 /// Re-insert an extracted node.
496 insert(const_iterator, node_type&& __nh)
497 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
498#endif // node_extract
499
500#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
501 /**
502 * @brief Attempts to build and insert a std::pair into the
503 * %unordered_map.
504 *
505 * @param __k Key to use for finding a possibly existing pair in
506 * the unordered_map.
507 * @param __args Arguments used to generate the .second for a
508 * new pair instance.
509 *
510 * @return A pair, of which the first element is an iterator that points
511 * to the possibly inserted pair, and the second is a bool that
512 * is true if the pair was actually inserted.
513 *
514 * This function attempts to build and insert a (key, value) %pair into
515 * the %unordered_map.
516 * An %unordered_map relies on unique keys and thus a %pair is only
517 * inserted if its first element (the key) is not already present in the
518 * %unordered_map.
519 * If a %pair is not inserted, this function has no effect.
520 *
521 * Insertion requires amortized constant time.
522 */
523 template <typename... _Args>
525 try_emplace(const key_type& __k, _Args&&... __args)
526 {
527 return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
528 }
529
530 // move-capable overload
531 template <typename... _Args>
533 try_emplace(key_type&& __k, _Args&&... __args)
534 {
535 return _M_h.try_emplace(cend(), std::move(__k),
536 std::forward<_Args>(__args)...);
537 }
538
539 /**
540 * @brief Attempts to build and insert a std::pair into the
541 * %unordered_map.
542 *
543 * @param __hint An iterator that serves as a hint as to where the pair
544 * should be inserted.
545 * @param __k Key to use for finding a possibly existing pair in
546 * the unordered_map.
547 * @param __args Arguments used to generate the .second for a
548 * new pair instance.
549 * @return An iterator that points to the element with key of the
550 * std::pair built from @a __args (may or may not be that
551 * std::pair).
552 *
553 * This function is not concerned about whether the insertion took place,
554 * and thus does not return a boolean like the single-argument emplace()
555 * does. However, if insertion did not take place,
556 * this function has no effect.
557 * Note that the first parameter is only a hint and can potentially
558 * improve the performance of the insertion process. A bad hint would
559 * cause no gains in efficiency.
560 *
561 * See
562 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
563 * for more on @a hinting.
564 *
565 * Insertion requires amortized constant time.
566 */
567 template <typename... _Args>
569 try_emplace(const_iterator __hint, const key_type& __k,
570 _Args&&... __args)
571 {
572 return _M_h.try_emplace(__hint, __k,
573 std::forward<_Args>(__args)...).first;
574 }
575
576 // move-capable overload
577 template <typename... _Args>
579 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
580 {
581 return _M_h.try_emplace(__hint, std::move(__k),
582 std::forward<_Args>(__args)...).first;
583 }
584#endif // __glibcxx_unordered_map_try_emplace
585
586 ///@{
587 /**
588 * @brief Attempts to insert a std::pair into the %unordered_map.
589
590 * @param __x Pair to be inserted (see std::make_pair for easy
591 * creation of pairs).
592 *
593 * @return A pair, of which the first element is an iterator that
594 * points to the possibly inserted pair, and the second is
595 * a bool that is true if the pair was actually inserted.
596 *
597 * This function attempts to insert a (key, value) %pair into the
598 * %unordered_map. An %unordered_map relies on unique keys and thus a
599 * %pair is only inserted if its first element (the key) is not already
600 * present in the %unordered_map.
601 *
602 * Insertion requires amortized constant time.
603 */
605 insert(const value_type& __x)
606 { return _M_h.insert(__x); }
607
608 // _GLIBCXX_RESOLVE_LIB_DEFECTS
609 // 2354. Unnecessary copying when inserting into maps with braced-init
612 { return _M_h.insert(std::move(__x)); }
613
614 template<typename _Pair>
615 __enable_if_t<is_constructible<value_type, _Pair&&>::value,
617 insert(_Pair&& __x)
618 { return _M_h.emplace(std::forward<_Pair>(__x)); }
619 ///@}
620
621 ///@{
622 /**
623 * @brief Attempts to insert a std::pair into the %unordered_map.
624 * @param __hint An iterator that serves as a hint as to where the
625 * pair should be inserted.
626 * @param __x Pair to be inserted (see std::make_pair for easy creation
627 * of pairs).
628 * @return An iterator that points to the element with key of
629 * @a __x (may or may not be the %pair passed in).
630 *
631 * This function is not concerned about whether the insertion took place,
632 * and thus does not return a boolean like the single-argument insert()
633 * does. Note that the first parameter is only a hint and can
634 * potentially improve the performance of the insertion process. A bad
635 * hint would cause no gains in efficiency.
636 *
637 * See
638 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
639 * for more on @a hinting.
640 *
641 * Insertion requires amortized constant time.
642 */
644 insert(const_iterator __hint, const value_type& __x)
645 { return _M_h.insert(__hint, __x); }
646
647 // _GLIBCXX_RESOLVE_LIB_DEFECTS
648 // 2354. Unnecessary copying when inserting into maps with braced-init
651 { return _M_h.insert(__hint, std::move(__x)); }
652
653 template<typename _Pair>
654 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
655 insert(const_iterator __hint, _Pair&& __x)
656 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
657 ///@}
658
659 /**
660 * @brief A template function that attempts to insert a range of
661 * elements.
662 * @param __first Iterator pointing to the start of the range to be
663 * inserted.
664 * @param __last Iterator pointing to the end of the range.
665 *
666 * Complexity similar to that of the range constructor.
667 */
668 template<typename _InputIterator>
669 void
670 insert(_InputIterator __first, _InputIterator __last)
671 { _M_h.insert(__first, __last); }
672
673 /**
674 * @brief Attempts to insert a list of elements into the %unordered_map.
675 * @param __l A std::initializer_list<value_type> of elements
676 * to be inserted.
677 *
678 * Complexity similar to that of the range constructor.
679 */
680 void
682 { _M_h.insert(__l); }
683
684#if __glibcxx_containers_ranges // C++ >= 23
685 /**
686 * @brief Inserts a range of elements.
687 * @since C++23
688 * @param __rg An input range of elements that can be converted to
689 * the map's value type.
690 */
691 template<__detail::__container_compatible_range<value_type> _Rg>
692 void
693 insert_range(_Rg&& __rg)
694 {
695 auto __first = ranges::begin(__rg);
696 const auto __last = ranges::end(__rg);
697 for (; __first != __last; ++__first)
698 _M_h.emplace(*__first);
699 }
700#endif
701
702#ifdef __glibcxx_unordered_map_try_emplace // >= C++17 && HOSTED
703 /**
704 * @brief Attempts to insert a std::pair into the %unordered_map.
705 * @param __k Key to use for finding a possibly existing pair in
706 * the map.
707 * @param __obj Argument used to generate the .second for a pair
708 * instance.
709 *
710 * @return A pair, of which the first element is an iterator that
711 * points to the possibly inserted pair, and the second is
712 * a bool that is true if the pair was actually inserted.
713 *
714 * This function attempts to insert a (key, value) %pair into the
715 * %unordered_map. An %unordered_map relies on unique keys and thus a
716 * %pair is only inserted if its first element (the key) is not already
717 * present in the %unordered_map.
718 * If the %pair was already in the %unordered_map, the .second of
719 * the %pair is assigned from __obj.
720 *
721 * Insertion requires amortized constant time.
722 */
723 template <typename _Obj>
725 insert_or_assign(const key_type& __k, _Obj&& __obj)
726 {
727 auto __ret = _M_h.try_emplace(cend(), __k,
728 std::forward<_Obj>(__obj));
729 if (!__ret.second)
730 __ret.first->second = std::forward<_Obj>(__obj);
731 return __ret;
732 }
733
734 // move-capable overload
735 template <typename _Obj>
737 insert_or_assign(key_type&& __k, _Obj&& __obj)
738 {
739 auto __ret = _M_h.try_emplace(cend(), std::move(__k),
740 std::forward<_Obj>(__obj));
741 if (!__ret.second)
742 __ret.first->second = std::forward<_Obj>(__obj);
743 return __ret;
744 }
745
746 /**
747 * @brief Attempts to insert a std::pair into the %unordered_map.
748 * @param __hint An iterator that serves as a hint as to where the
749 * pair should be inserted.
750 * @param __k Key to use for finding a possibly existing pair in
751 * the unordered_map.
752 * @param __obj Argument used to generate the .second for a pair
753 * instance.
754 * @return An iterator that points to the element with key of
755 * @a __x (may or may not be the %pair passed in).
756 *
757 * This function is not concerned about whether the insertion took place,
758 * and thus does not return a boolean like the single-argument insert()
759 * does.
760 * If the %pair was already in the %unordered map, the .second of
761 * the %pair is assigned from __obj.
762 * Note that the first parameter is only a hint and can
763 * potentially improve the performance of the insertion process. A bad
764 * hint would cause no gains in efficiency.
765 *
766 * See
767 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
768 * for more on @a hinting.
769 *
770 * Insertion requires amortized constant time.
771 */
772 template <typename _Obj>
774 insert_or_assign(const_iterator __hint, const key_type& __k,
775 _Obj&& __obj)
776 {
777 auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
778 if (!__ret.second)
779 __ret.first->second = std::forward<_Obj>(__obj);
780 return __ret.first;
781 }
782
783 // move-capable overload
784 template <typename _Obj>
786 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
787 {
788 auto __ret = _M_h.try_emplace(__hint, std::move(__k),
789 std::forward<_Obj>(__obj));
790 if (!__ret.second)
791 __ret.first->second = std::forward<_Obj>(__obj);
792 return __ret.first;
793 }
794#endif // unordered_map_try_emplace
795
796 ///@{
797 /**
798 * @brief Erases an element from an %unordered_map.
799 * @param __position An iterator pointing to the element to be erased.
800 * @return An iterator pointing to the element immediately following
801 * @a __position prior to the element being erased. If no such
802 * element exists, end() is returned.
803 *
804 * This function erases an element, pointed to by the given iterator,
805 * from an %unordered_map.
806 * Note that this function only erases the element, and that if the
807 * element is itself a pointer, the pointed-to memory is not touched in
808 * any way. Managing the pointer is the user's responsibility.
809 */
812 { return _M_h.erase(__position); }
813
814 // LWG 2059.
816 erase(iterator __position)
817 { return _M_h.erase(__position); }
818 ///@}
819
820 /**
821 * @brief Erases elements according to the provided key.
822 * @param __x Key of element to be erased.
823 * @return The number of elements erased.
824 *
825 * This function erases all the elements located by the given key from
826 * an %unordered_map. For an %unordered_map the result of this function
827 * can only be 0 (not present) or 1 (present).
828 * Note that this function only erases the element, and that if the
829 * element is itself a pointer, the pointed-to memory is not touched in
830 * any way. Managing the pointer is the user's responsibility.
831 */
833 erase(const key_type& __x)
834 { return _M_h.erase(__x); }
835
836 /**
837 * @brief Erases a [__first,__last) range of elements from an
838 * %unordered_map.
839 * @param __first Iterator pointing to the start of the range to be
840 * erased.
841 * @param __last Iterator pointing to the end of the range to
842 * be erased.
843 * @return The iterator @a __last.
844 *
845 * This function erases a sequence of elements from an %unordered_map.
846 * Note that this function only erases the elements, and that if
847 * the element is itself a pointer, the pointed-to memory is not touched
848 * in any way. Managing the pointer is the user's responsibility.
849 */
852 { return _M_h.erase(__first, __last); }
853
854 /**
855 * Erases all elements in an %unordered_map.
856 * Note that this function only erases the elements, and that if the
857 * elements themselves are pointers, the pointed-to memory is not touched
858 * in any way. Managing the pointer is the user's responsibility.
859 */
860 void
861 clear() noexcept
862 { _M_h.clear(); }
863
864 /**
865 * @brief Swaps data with another %unordered_map.
866 * @param __x An %unordered_map of the same element and allocator
867 * types.
868 *
869 * This exchanges the elements between two %unordered_map in constant
870 * time.
871 * Note that the global std::swap() function is specialized such that
872 * std::swap(m1,m2) will feed to this function.
873 */
874 void
876 noexcept( noexcept(_M_h.swap(__x._M_h)) )
877 { _M_h.swap(__x._M_h); }
878
879#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
880 template<typename, typename, typename>
881 friend class std::_Hash_merge_helper;
882
883 template<typename _H2, typename _P2>
884 void
886 {
887 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
888 if (std::__addressof(__source) == this) [[__unlikely__]]
889 return;
890
891 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
892 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
893 }
894
895 template<typename _H2, typename _P2>
896 void
897 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
898 {
899 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
900 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
901 }
902
903 template<typename _H2, typename _P2>
904 void
905 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
906 {
907 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
908 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
909 }
910
911 template<typename _H2, typename _P2>
912 void
913 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
914 { merge(__source); }
915#endif // node_extract
916
917 // observers.
918
919 /// Returns the hash functor object with which the %unordered_map was
920 /// constructed.
921 hasher
923 { return _M_h.hash_function(); }
924
925 /// Returns the key comparison object with which the %unordered_map was
926 /// constructed.
928 key_eq() const
929 { return _M_h.key_eq(); }
930
931 // lookup.
932
933 ///@{
934 /**
935 * @brief Tries to locate an element in an %unordered_map.
936 * @param __x Key to be located.
937 * @return Iterator pointing to sought-after element, or end() if not
938 * found.
939 *
940 * This function takes a key and tries to locate the element with which
941 * the key matches. If successful the function returns an iterator
942 * pointing to the sought after element. If unsuccessful it returns the
943 * past-the-end ( @c end() ) iterator.
944 */
946 find(const key_type& __x)
947 { return _M_h.find(__x); }
948
949#if __cplusplus > 201703L
950 template<typename _Kt>
951 auto
952 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
953 { return _M_h._M_find_tr(__x); }
954#endif
955
956 const_iterator
957 find(const key_type& __x) const
958 { return _M_h.find(__x); }
959
960#if __cplusplus > 201703L
961 template<typename _Kt>
962 auto
963 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
964 { return _M_h._M_find_tr(__x); }
965#endif
966 ///@}
967
968 ///@{
969 /**
970 * @brief Finds the number of elements.
971 * @param __x Key to count.
972 * @return Number of elements with specified key.
973 *
974 * This function only makes sense for %unordered_multimap; for
975 * %unordered_map the result will either be 0 (not present) or 1
976 * (present).
977 */
979 count(const key_type& __x) const
980 { return _M_h.count(__x); }
981
982#if __cplusplus > 201703L
983 template<typename _Kt>
984 auto
985 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
986 { return _M_h._M_count_tr(__x); }
987#endif
988 ///@}
989
990#if __cplusplus > 201703L
991 ///@{
992 /**
993 * @brief Finds whether an element with the given key exists.
994 * @param __x Key of elements to be located.
995 * @return True if there is any element with the specified key.
996 */
997 bool
998 contains(const key_type& __x) const
999 { return _M_h.find(__x) != _M_h.end(); }
1000
1001 template<typename _Kt>
1002 auto
1003 contains(const _Kt& __x) const
1004 -> decltype(_M_h._M_find_tr(__x), void(), true)
1005 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1006 ///@}
1007#endif
1008
1009 ///@{
1010 /**
1011 * @brief Finds a subsequence matching given key.
1012 * @param __x Key to be located.
1013 * @return Pair of iterators that possibly points to the subsequence
1014 * matching given key.
1015 *
1016 * This function probably only makes sense for %unordered_multimap.
1017 */
1020 { return _M_h.equal_range(__x); }
1021
1022#if __cplusplus > 201703L
1023 template<typename _Kt>
1024 auto
1025 equal_range(const _Kt& __x)
1026 -> decltype(_M_h._M_equal_range_tr(__x))
1027 { return _M_h._M_equal_range_tr(__x); }
1028#endif
1029
1031 equal_range(const key_type& __x) const
1032 { return _M_h.equal_range(__x); }
1033
1034#if __cplusplus > 201703L
1035 template<typename _Kt>
1036 auto
1037 equal_range(const _Kt& __x) const
1038 -> decltype(_M_h._M_equal_range_tr(__x))
1039 { return _M_h._M_equal_range_tr(__x); }
1040#endif
1041 ///@}
1042
1043 ///@{
1044 /**
1045 * @brief Subscript ( @c [] ) access to %unordered_map data.
1046 * @param __k The key for which data should be retrieved.
1047 * @return A reference to the data of the (key,data) %pair.
1048 *
1049 * Allows for easy lookup with the subscript ( @c [] )operator. Returns
1050 * data associated with the key specified in subscript. If the key does
1051 * not exist, a pair with that key is created using default values, which
1052 * is then returned.
1053 *
1054 * Lookup requires constant time.
1055 */
1058 { return _M_h[__k]; }
1059
1062 { return _M_h[std::move(__k)]; }
1063 ///@}
1064
1065 ///@{
1066 /**
1067 * @brief Access to %unordered_map data.
1068 * @param __k The key for which data should be retrieved.
1069 * @return A reference to the data whose key is equal to @a __k, if
1070 * such a data is present in the %unordered_map.
1071 * @throw std::out_of_range If no such data is present.
1072 */
1074 at(const key_type& __k)
1075 { return _M_h.at(__k); }
1076
1077 const mapped_type&
1078 at(const key_type& __k) const
1079 { return _M_h.at(__k); }
1080 ///@}
1081
1082 // bucket interface.
1083
1084 /// Returns the number of buckets of the %unordered_map.
1085 size_type
1086 bucket_count() const noexcept
1087 { return _M_h.bucket_count(); }
1088
1089 /// Returns the maximum number of buckets of the %unordered_map.
1090 size_type
1091 max_bucket_count() const noexcept
1092 { return _M_h.max_bucket_count(); }
1093
1094 /*
1095 * @brief Returns the number of elements in a given bucket.
1096 * @param __n A bucket index.
1097 * @return The number of elements in the bucket.
1098 */
1099 size_type
1100 bucket_size(size_type __n) const
1101 { return _M_h.bucket_size(__n); }
1102
1103 /*
1104 * @brief Returns the bucket index of a given element.
1105 * @param __key A key instance.
1106 * @return The key bucket index.
1107 */
1108 size_type
1109 bucket(const key_type& __key) const
1110 { return _M_h.bucket(__key); }
1111
1112 /**
1113 * @brief Returns a read/write iterator pointing to the first bucket
1114 * element.
1115 * @param __n The bucket index.
1116 * @return A read/write local iterator.
1117 */
1120 { return _M_h.begin(__n); }
1121
1122 ///@{
1123 /**
1124 * @brief Returns a read-only (constant) iterator pointing to the first
1125 * bucket element.
1126 * @param __n The bucket index.
1127 * @return A read-only local iterator.
1128 */
1130 begin(size_type __n) const
1131 { return _M_h.begin(__n); }
1132
1135 { return _M_h.cbegin(__n); }
1136 ///@}
1137
1138 /**
1139 * @brief Returns a read/write iterator pointing to one past the last
1140 * bucket elements.
1141 * @param __n The bucket index.
1142 * @return A read/write local iterator.
1143 */
1146 { return _M_h.end(__n); }
1147
1148 ///@{
1149 /**
1150 * @brief Returns a read-only (constant) iterator pointing to one past
1151 * the last bucket elements.
1152 * @param __n The bucket index.
1153 * @return A read-only local iterator.
1154 */
1156 end(size_type __n) const
1157 { return _M_h.end(__n); }
1158
1160 cend(size_type __n) const
1161 { return _M_h.cend(__n); }
1162 ///@}
1163
1164 // hash policy.
1165
1166 /// Returns the average number of elements per bucket.
1167 float
1168 load_factor() const noexcept
1169 { return _M_h.load_factor(); }
1170
1171 /// Returns a positive number that the %unordered_map tries to keep the
1172 /// load factor less than or equal to.
1173 float
1174 max_load_factor() const noexcept
1175 { return _M_h.max_load_factor(); }
1176
1177 /**
1178 * @brief Change the %unordered_map maximum load factor.
1179 * @param __z The new maximum load factor.
1180 */
1181 void
1183 { _M_h.max_load_factor(__z); }
1184
1185 /**
1186 * @brief May rehash the %unordered_map.
1187 * @param __n The new number of buckets.
1188 *
1189 * Rehash will occur only if the new number of buckets respect the
1190 * %unordered_map maximum load factor.
1191 */
1192 void
1194 { _M_h.rehash(__n); }
1195
1196 /**
1197 * @brief Prepare the %unordered_map for a specified number of
1198 * elements.
1199 * @param __n Number of elements required.
1200 *
1201 * Same as rehash(ceil(n / max_load_factor())).
1202 */
1203 void
1205 { _M_h.reserve(__n); }
1206
1207 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1208 typename _Alloc1>
1209 friend bool
1212 };
1213
1214#if __cpp_deduction_guides >= 201606
1215
1216 template<typename _InputIterator,
1217 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1218 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1219 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1220 typename = _RequireInputIter<_InputIterator>,
1221 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1222 typename = _RequireNotAllocator<_Pred>,
1223 typename = _RequireAllocator<_Allocator>>
1224 unordered_map(_InputIterator, _InputIterator,
1225 typename unordered_map<int, int>::size_type = {},
1226 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1227 -> unordered_map<__iter_key_t<_InputIterator>,
1228 __iter_val_t<_InputIterator>,
1229 _Hash, _Pred, _Allocator>;
1230
1231 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1232 typename _Pred = equal_to<_Key>,
1233 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1234 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1235 typename = _RequireNotAllocator<_Pred>,
1236 typename = _RequireAllocator<_Allocator>>
1239 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1241
1242 template<typename _InputIterator, typename _Allocator,
1243 typename = _RequireInputIter<_InputIterator>,
1244 typename = _RequireAllocator<_Allocator>>
1245 unordered_map(_InputIterator, _InputIterator,
1246 typename unordered_map<int, int>::size_type, _Allocator)
1248 __iter_val_t<_InputIterator>,
1251 _Allocator>;
1252
1253 template<typename _InputIterator, typename _Allocator,
1254 typename = _RequireInputIter<_InputIterator>,
1255 typename = _RequireAllocator<_Allocator>>
1256 unordered_map(_InputIterator, _InputIterator, _Allocator)
1258 __iter_val_t<_InputIterator>,
1261 _Allocator>;
1262
1263 template<typename _InputIterator, typename _Hash, typename _Allocator,
1264 typename = _RequireInputIter<_InputIterator>,
1265 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1266 typename = _RequireAllocator<_Allocator>>
1267 unordered_map(_InputIterator, _InputIterator,
1269 _Hash, _Allocator)
1271 __iter_val_t<_InputIterator>, _Hash,
1273
1274 template<typename _Key, typename _Tp, typename _Allocator,
1275 typename = _RequireAllocator<_Allocator>>
1278 _Allocator)
1280
1281 template<typename _Key, typename _Tp, typename _Allocator,
1282 typename = _RequireAllocator<_Allocator>>
1285
1286 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1287 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1288 typename = _RequireAllocator<_Allocator>>
1291 _Hash, _Allocator)
1293
1294#if __glibcxx_containers_ranges // C++ >= 23
1295 template<ranges::input_range _Rg,
1296 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1297 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1298 __allocator_like _Allocator =
1300 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
1301 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1302 -> unordered_map<__detail::__range_key_type<_Rg>,
1303 __detail::__range_mapped_type<_Rg>,
1304 _Hash, _Pred, _Allocator>;
1305
1306 template<ranges::input_range _Rg,
1307 __allocator_like _Allocator>
1309 _Allocator)
1311 __detail::__range_mapped_type<_Rg>,
1314 _Allocator>;
1315
1316 template<ranges::input_range _Rg,
1317 __allocator_like _Allocator>
1318 unordered_map(from_range_t, _Rg&&, _Allocator)
1320 __detail::__range_mapped_type<_Rg>,
1323 _Allocator>;
1324
1325 template<ranges::input_range _Rg,
1326 __not_allocator_like _Hash,
1327 __allocator_like _Allocator>
1329 _Hash, _Allocator)
1331 __detail::__range_mapped_type<_Rg>,
1333 _Allocator>;
1334#endif
1335#endif
1336
1337 /**
1338 * @brief A standard container composed of equivalent keys
1339 * (possibly containing multiple of each key value) that associates
1340 * values of another type with the keys.
1341 *
1342 * @ingroup unordered_associative_containers
1343 * @headerfile unordered_map
1344 * @since C++11
1345 *
1346 * @tparam _Key Type of key objects.
1347 * @tparam _Tp Type of mapped objects.
1348 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1349 * @tparam _Pred Predicate function object type, defaults
1350 * to equal_to<_Value>.
1351 * @tparam _Alloc Allocator type, defaults to
1352 * std::allocator<std::pair<const _Key, _Tp>>.
1353 *
1354 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1355 * <a href="tables.html#xx">unordered associative container</a>
1356 *
1357 * The resulting value type of the container is std::pair<const _Key, _Tp>.
1358 *
1359 * Base is _Hashtable, dispatched at compile time via template
1360 * alias __ummap_hashtable.
1361 */
1362 template<typename _Key, typename _Tp,
1363 typename _Hash = hash<_Key>,
1364 typename _Pred = equal_to<_Key>,
1365 typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
1367 {
1368 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;
1369 _Hashtable _M_h;
1370
1371 public:
1372 // typedefs:
1373 ///@{
1374 /// Public typedefs.
1375 typedef typename _Hashtable::key_type key_type;
1376 typedef typename _Hashtable::value_type value_type;
1377 typedef typename _Hashtable::mapped_type mapped_type;
1378 typedef typename _Hashtable::hasher hasher;
1379 typedef typename _Hashtable::key_equal key_equal;
1380 typedef typename _Hashtable::allocator_type allocator_type;
1381 ///@}
1382
1383 ///@{
1384 /// Iterator-related typedefs.
1385 typedef typename _Hashtable::pointer pointer;
1386 typedef typename _Hashtable::const_pointer const_pointer;
1387 typedef typename _Hashtable::reference reference;
1388 typedef typename _Hashtable::const_reference const_reference;
1389 typedef typename _Hashtable::iterator iterator;
1390 typedef typename _Hashtable::const_iterator const_iterator;
1391 typedef typename _Hashtable::local_iterator local_iterator;
1392 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1393 typedef typename _Hashtable::size_type size_type;
1394 typedef typename _Hashtable::difference_type difference_type;
1395 ///@}
1396
1397#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1398 using node_type = typename _Hashtable::node_type;
1399#endif
1400
1401 //construct/destroy/copy
1402
1403 /// Default constructor.
1405
1406 /**
1407 * @brief Default constructor creates no elements.
1408 * @param __n Mnimal initial number of buckets.
1409 * @param __hf A hash functor.
1410 * @param __eql A key equality functor.
1411 * @param __a An allocator object.
1412 */
1413 explicit
1415 const hasher& __hf = hasher(),
1416 const key_equal& __eql = key_equal(),
1417 const allocator_type& __a = allocator_type())
1418 : _M_h(__n, __hf, __eql, __a)
1419 { }
1420
1421 /**
1422 * @brief Builds an %unordered_multimap from a range.
1423 * @param __first An input iterator.
1424 * @param __last An input iterator.
1425 * @param __n Minimal initial number of buckets.
1426 * @param __hf A hash functor.
1427 * @param __eql A key equality functor.
1428 * @param __a An allocator object.
1429 *
1430 * Create an %unordered_multimap consisting of copies of the elements
1431 * from [__first,__last). This is linear in N (where N is
1432 * distance(__first,__last)).
1433 */
1434 template<typename _InputIterator>
1435 unordered_multimap(_InputIterator __first, _InputIterator __last,
1436 size_type __n = 0,
1437 const hasher& __hf = hasher(),
1438 const key_equal& __eql = key_equal(),
1439 const allocator_type& __a = allocator_type())
1440 : _M_h(__first, __last, __n, __hf, __eql, __a)
1441 { }
1442
1443 /// Copy constructor.
1445
1446 /// Move constructor.
1448
1449 /**
1450 * @brief Creates an %unordered_multimap with no elements.
1451 * @param __a An allocator object.
1452 */
1453 explicit
1455 : _M_h(__a)
1456 { }
1457
1458 /*
1459 * @brief Copy constructor with allocator argument.
1460 * @param __uset Input %unordered_multimap to copy.
1461 * @param __a An allocator object.
1462 */
1464 const allocator_type& __a)
1465 : _M_h(__ummap._M_h, __a)
1466 { }
1467
1468 /*
1469 * @brief Move constructor with allocator argument.
1470 * @param __uset Input %unordered_multimap to move.
1471 * @param __a An allocator object.
1472 */
1473 unordered_multimap(unordered_multimap&& __ummap,
1474 const allocator_type& __a)
1475 noexcept( noexcept(_Hashtable(std::move(__ummap._M_h), __a)) )
1476 : _M_h(std::move(__ummap._M_h), __a)
1477 { }
1478
1479 /**
1480 * @brief Builds an %unordered_multimap from an initializer_list.
1481 * @param __l An initializer_list.
1482 * @param __n Minimal initial number of buckets.
1483 * @param __hf A hash functor.
1484 * @param __eql A key equality functor.
1485 * @param __a An allocator object.
1486 *
1487 * Create an %unordered_multimap consisting of copies of the elements in
1488 * the list. This is linear in N (where N is @a __l.size()).
1489 */
1491 size_type __n = 0,
1492 const hasher& __hf = hasher(),
1493 const key_equal& __eql = key_equal(),
1494 const allocator_type& __a = allocator_type())
1495 : _M_h(__l, __n, __hf, __eql, __a)
1496 { }
1497
1498 unordered_multimap(size_type __n, const allocator_type& __a)
1499 : unordered_multimap(__n, hasher(), key_equal(), __a)
1500 { }
1501
1502 unordered_multimap(size_type __n, const hasher& __hf,
1503 const allocator_type& __a)
1504 : unordered_multimap(__n, __hf, key_equal(), __a)
1505 { }
1506
1507 template<typename _InputIterator>
1508 unordered_multimap(_InputIterator __first, _InputIterator __last,
1509 size_type __n,
1510 const allocator_type& __a)
1511 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1512 { }
1513
1514 template<typename _InputIterator>
1515 unordered_multimap(_InputIterator __first, _InputIterator __last,
1516 size_type __n, const hasher& __hf,
1517 const allocator_type& __a)
1518 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1519 { }
1520
1521 unordered_multimap(initializer_list<value_type> __l,
1522 size_type __n,
1523 const allocator_type& __a)
1524 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1525 { }
1526
1527 unordered_multimap(initializer_list<value_type> __l,
1528 size_type __n, const hasher& __hf,
1529 const allocator_type& __a)
1530 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1531 { }
1532
1533#if __glibcxx_containers_ranges // C++ >= 23
1534 /**
1535 * @brief Builds an %unordered_multimap from a range.
1536 * @since C++23
1537 * @param __rg An input range of elements that can be converted to
1538 * the maps's value type.
1539 * @param __n Minimal initial number of buckets.
1540 * @param __hf A hash functor.
1541 * @param __eql A key equality functor.
1542 * @param __a An allocator object.
1543 *
1544 * Create an %unordered_multimap consisting of copies of the elements in
1545 * the range. This is linear in N (where N is `std::ranges::size(__rg)`).
1546 */
1547 template<__detail::__container_compatible_range<value_type> _Rg>
1548 unordered_multimap(from_range_t, _Rg&& __rg,
1549 size_type __n = 0,
1550 const hasher& __hf = hasher(),
1551 const key_equal& __eql = key_equal(),
1552 const allocator_type& __a = allocator_type())
1553 : _M_h(__n, __hf, __eql, __a)
1554 { insert_range(std::forward<_Rg>(__rg)); }
1555
1556 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1557 // 2713. More missing allocator-extended constructors for unordered containers
1558 template<__detail::__container_compatible_range<value_type> _Rg>
1559 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1560 : _M_h(0, hasher(), key_equal(), __a)
1561 { insert_range(std::forward<_Rg>(__rg)); }
1562
1563 template<__detail::__container_compatible_range<value_type> _Rg>
1564 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1565 const allocator_type& __a)
1566 : _M_h(__n, hasher(), key_equal(), __a)
1567 { insert_range(std::forward<_Rg>(__rg)); }
1568
1569 template<__detail::__container_compatible_range<value_type> _Rg>
1570 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1571 const hasher& __hf, const allocator_type& __a)
1572 : _M_h(__n, __hf, key_equal(), __a)
1573 { insert_range(std::forward<_Rg>(__rg)); }
1574#endif
1575
1576 /// Copy assignment operator.
1579
1580 /// Move assignment operator.
1583
1584 /**
1585 * @brief %Unordered_multimap list assignment operator.
1586 * @param __l An initializer_list.
1587 *
1588 * This function fills an %unordered_multimap with copies of the
1589 * elements in the initializer list @a __l.
1590 *
1591 * Note that the assignment completely changes the %unordered_multimap
1592 * and that the resulting %unordered_multimap's size is the same as the
1593 * number of elements assigned.
1594 */
1597 {
1598 _M_h = __l;
1599 return *this;
1600 }
1601
1602 /// Returns the allocator object used by the %unordered_multimap.
1603 allocator_type
1604 get_allocator() const noexcept
1605 { return _M_h.get_allocator(); }
1606
1607 // size and capacity:
1608
1609 /// Returns true if the %unordered_multimap is empty.
1610 _GLIBCXX_NODISCARD bool
1611 empty() const noexcept
1612 { return _M_h.empty(); }
1613
1614 /// Returns the size of the %unordered_multimap.
1615 size_type
1616 size() const noexcept
1617 { return _M_h.size(); }
1618
1619 /// Returns the maximum size of the %unordered_multimap.
1620 size_type
1621 max_size() const noexcept
1622 { return _M_h.max_size(); }
1623
1624 // iterators.
1625
1626 /**
1627 * Returns a read/write iterator that points to the first element in the
1628 * %unordered_multimap.
1629 */
1630 iterator
1631 begin() noexcept
1632 { return _M_h.begin(); }
1633
1634 ///@{
1635 /**
1636 * Returns a read-only (constant) iterator that points to the first
1637 * element in the %unordered_multimap.
1638 */
1639 const_iterator
1640 begin() const noexcept
1641 { return _M_h.begin(); }
1642
1643 const_iterator
1644 cbegin() const noexcept
1645 { return _M_h.begin(); }
1646 ///@}
1647
1648 /**
1649 * Returns a read/write iterator that points one past the last element in
1650 * the %unordered_multimap.
1651 */
1652 iterator
1653 end() noexcept
1654 { return _M_h.end(); }
1655
1656 ///@{
1657 /**
1658 * Returns a read-only (constant) iterator that points one past the last
1659 * element in the %unordered_multimap.
1660 */
1661 const_iterator
1662 end() const noexcept
1663 { return _M_h.end(); }
1664
1665 const_iterator
1666 cend() const noexcept
1667 { return _M_h.end(); }
1668 ///@}
1669
1670 // modifiers.
1671
1672 /**
1673 * @brief Attempts to build and insert a std::pair into the
1674 * %unordered_multimap.
1675 *
1676 * @param __args Arguments used to generate a new pair instance (see
1677 * std::piecewise_contruct for passing arguments to each
1678 * part of the pair constructor).
1679 *
1680 * @return An iterator that points to the inserted pair.
1681 *
1682 * This function attempts to build and insert a (key, value) %pair into
1683 * the %unordered_multimap.
1684 *
1685 * Insertion requires amortized constant time.
1686 */
1687 template<typename... _Args>
1688 iterator
1689 emplace(_Args&&... __args)
1690 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1691
1692 /**
1693 * @brief Attempts to build and insert a std::pair into the
1694 * %unordered_multimap.
1695 *
1696 * @param __pos An iterator that serves as a hint as to where the pair
1697 * should be inserted.
1698 * @param __args Arguments used to generate a new pair instance (see
1699 * std::piecewise_contruct for passing arguments to each
1700 * part of the pair constructor).
1701 * @return An iterator that points to the element with key of the
1702 * std::pair built from @a __args.
1703 *
1704 * Note that the first parameter is only a hint and can potentially
1705 * improve the performance of the insertion process. A bad hint would
1706 * cause no gains in efficiency.
1707 *
1708 * See
1709 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1710 * for more on @a hinting.
1711 *
1712 * Insertion requires amortized constant time.
1713 */
1714 template<typename... _Args>
1715 iterator
1716 emplace_hint(const_iterator __pos, _Args&&... __args)
1717 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1718
1719 ///@{
1720 /**
1721 * @brief Inserts a std::pair into the %unordered_multimap.
1722 * @param __x Pair to be inserted (see std::make_pair for easy
1723 * creation of pairs).
1724 *
1725 * @return An iterator that points to the inserted pair.
1726 *
1727 * Insertion requires amortized constant time.
1728 */
1729 iterator
1730 insert(const value_type& __x)
1731 { return _M_h.insert(__x); }
1732
1733 iterator
1735 { return _M_h.insert(std::move(__x)); }
1736
1737 template<typename _Pair>
1738 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1739 insert(_Pair&& __x)
1740 { return _M_h.emplace(std::forward<_Pair>(__x)); }
1741 ///@}
1742
1743 ///@{
1744 /**
1745 * @brief Inserts a std::pair into the %unordered_multimap.
1746 * @param __hint An iterator that serves as a hint as to where the
1747 * pair should be inserted.
1748 * @param __x Pair to be inserted (see std::make_pair for easy creation
1749 * of pairs).
1750 * @return An iterator that points to the element with key of
1751 * @a __x (may or may not be the %pair passed in).
1752 *
1753 * Note that the first parameter is only a hint and can potentially
1754 * improve the performance of the insertion process. A bad hint would
1755 * cause no gains in efficiency.
1756 *
1757 * See
1758 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1759 * for more on @a hinting.
1760 *
1761 * Insertion requires amortized constant time.
1762 */
1763 iterator
1765 { return _M_h.insert(__hint, __x); }
1766
1767 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1768 // 2354. Unnecessary copying when inserting into maps with braced-init
1769 iterator
1771 { return _M_h.insert(__hint, std::move(__x)); }
1772
1773 template<typename _Pair>
1774 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
1775 insert(const_iterator __hint, _Pair&& __x)
1776 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
1777 ///@}
1778
1779 /**
1780 * @brief A template function that attempts to insert a range of
1781 * elements.
1782 * @param __first Iterator pointing to the start of the range to be
1783 * inserted.
1784 * @param __last Iterator pointing to the end of the range.
1785 *
1786 * Complexity similar to that of the range constructor.
1787 */
1788 template<typename _InputIterator>
1789 void
1790 insert(_InputIterator __first, _InputIterator __last)
1791 { _M_h.insert(__first, __last); }
1792
1793 /**
1794 * @brief Attempts to insert a list of elements into the
1795 * %unordered_multimap.
1796 * @param __l A std::initializer_list<value_type> of elements
1797 * to be inserted.
1798 *
1799 * Complexity similar to that of the range constructor.
1800 */
1801 void
1803 { _M_h.insert(__l); }
1804
1805#if __glibcxx_containers_ranges // C++ >= 23
1806 /**
1807 * @brief Inserts a range of elements.
1808 * @since C++23
1809 * @param __rg An input range of elements that can be converted to
1810 * the maps's value type.
1811 */
1812 template<__detail::__container_compatible_range<value_type> _Rg>
1813 void
1814 insert_range(_Rg&& __rg)
1815 {
1816 auto __first = ranges::begin(__rg);
1817 const auto __last = ranges::end(__rg);
1818 if (__first == __last)
1819 return;
1820
1821 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1822 _M_h._M_rehash_insert(size_type(ranges::distance(__rg)));
1823 else
1824 _M_h._M_rehash_insert(1);
1825
1826 for (; __first != __last; ++__first)
1827 _M_h.emplace(*__first);
1828 }
1829#endif
1830
1831#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1832 /// Extract a node.
1833 node_type
1834 extract(const_iterator __pos)
1835 {
1836 __glibcxx_assert(__pos != end());
1837 return _M_h.extract(__pos);
1838 }
1839
1840 /// Extract a node.
1841 node_type
1842 extract(const key_type& __key)
1843 { return _M_h.extract(__key); }
1844
1845 /// Re-insert an extracted node.
1846 iterator
1847 insert(node_type&& __nh)
1848 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1849
1850 /// Re-insert an extracted node.
1851 iterator
1852 insert(const_iterator __hint, node_type&& __nh)
1853 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1854#endif // node_extract
1855
1856 ///@{
1857 /**
1858 * @brief Erases an element from an %unordered_multimap.
1859 * @param __position An iterator pointing to the element to be erased.
1860 * @return An iterator pointing to the element immediately following
1861 * @a __position prior to the element being erased. If no such
1862 * element exists, end() is returned.
1863 *
1864 * This function erases an element, pointed to by the given iterator,
1865 * from an %unordered_multimap.
1866 * Note that this function only erases the element, and that if the
1867 * element is itself a pointer, the pointed-to memory is not touched in
1868 * any way. Managing the pointer is the user's responsibility.
1869 */
1870 iterator
1872 { return _M_h.erase(__position); }
1873
1874 // LWG 2059.
1875 iterator
1876 erase(iterator __position)
1877 { return _M_h.erase(__position); }
1878 ///@}
1879
1880 /**
1881 * @brief Erases elements according to the provided key.
1882 * @param __x Key of elements to be erased.
1883 * @return The number of elements erased.
1884 *
1885 * This function erases all the elements located by the given key from
1886 * an %unordered_multimap.
1887 * Note that this function only erases the element, and that if the
1888 * element is itself a pointer, the pointed-to memory is not touched in
1889 * any way. Managing the pointer is the user's responsibility.
1890 */
1891 size_type
1892 erase(const key_type& __x)
1893 { return _M_h.erase(__x); }
1894
1895 /**
1896 * @brief Erases a [__first,__last) range of elements from an
1897 * %unordered_multimap.
1898 * @param __first Iterator pointing to the start of the range to be
1899 * erased.
1900 * @param __last Iterator pointing to the end of the range to
1901 * be erased.
1902 * @return The iterator @a __last.
1903 *
1904 * This function erases a sequence of elements from an
1905 * %unordered_multimap.
1906 * Note that this function only erases the elements, and that if
1907 * the element is itself a pointer, the pointed-to memory is not touched
1908 * in any way. Managing the pointer is the user's responsibility.
1909 */
1910 iterator
1912 { return _M_h.erase(__first, __last); }
1913
1914 /**
1915 * Erases all elements in an %unordered_multimap.
1916 * Note that this function only erases the elements, and that if the
1917 * elements themselves are pointers, the pointed-to memory is not touched
1918 * in any way. Managing the pointer is the user's responsibility.
1919 */
1920 void
1921 clear() noexcept
1922 { _M_h.clear(); }
1923
1924 /**
1925 * @brief Swaps data with another %unordered_multimap.
1926 * @param __x An %unordered_multimap of the same element and allocator
1927 * types.
1928 *
1929 * This exchanges the elements between two %unordered_multimap in
1930 * constant time.
1931 * Note that the global std::swap() function is specialized such that
1932 * std::swap(m1,m2) will feed to this function.
1933 */
1934 void
1936 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1937 { _M_h.swap(__x._M_h); }
1938
1939#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1940 template<typename, typename, typename>
1941 friend class std::_Hash_merge_helper;
1942
1943 template<typename _H2, typename _P2>
1944 void
1946 {
1947 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
1948 if (std::__addressof(__source) == this) [[__unlikely__]]
1949 return;
1950
1951 using _Merge_helper
1952 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1953 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1954 }
1955
1956 template<typename _H2, typename _P2>
1957 void
1958 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1959 {
1960 using _Merge_helper
1961 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1962 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1963 }
1964
1965 template<typename _H2, typename _P2>
1966 void
1967 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1968 {
1969 using _Merge_helper
1970 = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
1971 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1972 }
1973
1974 template<typename _H2, typename _P2>
1975 void
1976 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1977 { merge(__source); }
1978#endif // node_extract
1979
1980 // observers.
1981
1982 /// Returns the hash functor object with which the %unordered_multimap
1983 /// was constructed.
1984 hasher
1986 { return _M_h.hash_function(); }
1987
1988 /// Returns the key comparison object with which the %unordered_multimap
1989 /// was constructed.
1990 key_equal
1991 key_eq() const
1992 { return _M_h.key_eq(); }
1993
1994 // lookup.
1995
1996 ///@{
1997 /**
1998 * @brief Tries to locate an element in an %unordered_multimap.
1999 * @param __x Key to be located.
2000 * @return Iterator pointing to sought-after element, or end() if not
2001 * found.
2002 *
2003 * This function takes a key and tries to locate the element with which
2004 * the key matches. If successful the function returns an iterator
2005 * pointing to the sought after element. If unsuccessful it returns the
2006 * past-the-end ( @c end() ) iterator.
2007 */
2008 iterator
2009 find(const key_type& __x)
2010 { return _M_h.find(__x); }
2011
2012#if __cplusplus > 201703L
2013 template<typename _Kt>
2014 auto
2015 find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
2016 { return _M_h._M_find_tr(__x); }
2017#endif
2018
2019 const_iterator
2020 find(const key_type& __x) const
2021 { return _M_h.find(__x); }
2022
2023#if __cplusplus > 201703L
2024 template<typename _Kt>
2025 auto
2026 find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
2027 { return _M_h._M_find_tr(__x); }
2028#endif
2029 ///@}
2030
2031 ///@{
2032 /**
2033 * @brief Finds the number of elements.
2034 * @param __x Key to count.
2035 * @return Number of elements with specified key.
2036 */
2037 size_type
2038 count(const key_type& __x) const
2039 { return _M_h.count(__x); }
2040
2041#if __cplusplus > 201703L
2042 template<typename _Kt>
2043 auto
2044 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
2045 { return _M_h._M_count_tr(__x); }
2046#endif
2047 ///@}
2048
2049#if __cplusplus > 201703L
2050 ///@{
2051 /**
2052 * @brief Finds whether an element with the given key exists.
2053 * @param __x Key of elements to be located.
2054 * @return True if there is any element with the specified key.
2055 */
2056 bool
2057 contains(const key_type& __x) const
2058 { return _M_h.find(__x) != _M_h.end(); }
2059
2060 template<typename _Kt>
2061 auto
2062 contains(const _Kt& __x) const
2063 -> decltype(_M_h._M_find_tr(__x), void(), true)
2064 { return _M_h._M_find_tr(__x) != _M_h.end(); }
2065 ///@}
2066#endif
2067
2068 ///@{
2069 /**
2070 * @brief Finds a subsequence matching given key.
2071 * @param __x Key to be located.
2072 * @return Pair of iterators that possibly points to the subsequence
2073 * matching given key.
2074 */
2077 { return _M_h.equal_range(__x); }
2078
2079#if __cplusplus > 201703L
2080 template<typename _Kt>
2081 auto
2082 equal_range(const _Kt& __x)
2083 -> decltype(_M_h._M_equal_range_tr(__x))
2084 { return _M_h._M_equal_range_tr(__x); }
2085#endif
2086
2088 equal_range(const key_type& __x) const
2089 { return _M_h.equal_range(__x); }
2090
2091#if __cplusplus > 201703L
2092 template<typename _Kt>
2093 auto
2094 equal_range(const _Kt& __x) const
2095 -> decltype(_M_h._M_equal_range_tr(__x))
2096 { return _M_h._M_equal_range_tr(__x); }
2097#endif
2098 ///@}
2099
2100 // bucket interface.
2101
2102 /// Returns the number of buckets of the %unordered_multimap.
2103 size_type
2104 bucket_count() const noexcept
2105 { return _M_h.bucket_count(); }
2106
2107 /// Returns the maximum number of buckets of the %unordered_multimap.
2108 size_type
2109 max_bucket_count() const noexcept
2110 { return _M_h.max_bucket_count(); }
2111
2112 /*
2113 * @brief Returns the number of elements in a given bucket.
2114 * @param __n A bucket index.
2115 * @return The number of elements in the bucket.
2116 */
2117 size_type
2118 bucket_size(size_type __n) const
2119 { return _M_h.bucket_size(__n); }
2120
2121 /*
2122 * @brief Returns the bucket index of a given element.
2123 * @param __key A key instance.
2124 * @return The key bucket index.
2125 */
2126 size_type
2127 bucket(const key_type& __key) const
2128 { return _M_h.bucket(__key); }
2129
2130 /**
2131 * @brief Returns a read/write iterator pointing to the first bucket
2132 * element.
2133 * @param __n The bucket index.
2134 * @return A read/write local iterator.
2135 */
2138 { return _M_h.begin(__n); }
2139
2140 ///@{
2141 /**
2142 * @brief Returns a read-only (constant) iterator pointing to the first
2143 * bucket element.
2144 * @param __n The bucket index.
2145 * @return A read-only local iterator.
2146 */
2148 begin(size_type __n) const
2149 { return _M_h.begin(__n); }
2150
2153 { return _M_h.cbegin(__n); }
2154 ///@}
2155
2156 /**
2157 * @brief Returns a read/write iterator pointing to one past the last
2158 * bucket elements.
2159 * @param __n The bucket index.
2160 * @return A read/write local iterator.
2161 */
2164 { return _M_h.end(__n); }
2165
2166 ///@{
2167 /**
2168 * @brief Returns a read-only (constant) iterator pointing to one past
2169 * the last bucket elements.
2170 * @param __n The bucket index.
2171 * @return A read-only local iterator.
2172 */
2174 end(size_type __n) const
2175 { return _M_h.end(__n); }
2176
2178 cend(size_type __n) const
2179 { return _M_h.cend(__n); }
2180 ///@}
2181
2182 // hash policy.
2183
2184 /// Returns the average number of elements per bucket.
2185 float
2186 load_factor() const noexcept
2187 { return _M_h.load_factor(); }
2188
2189 /// Returns a positive number that the %unordered_multimap tries to keep
2190 /// the load factor less than or equal to.
2191 float
2192 max_load_factor() const noexcept
2193 { return _M_h.max_load_factor(); }
2194
2195 /**
2196 * @brief Change the %unordered_multimap maximum load factor.
2197 * @param __z The new maximum load factor.
2198 */
2199 void
2201 { _M_h.max_load_factor(__z); }
2202
2203 /**
2204 * @brief May rehash the %unordered_multimap.
2205 * @param __n The new number of buckets.
2206 *
2207 * Rehash will occur only if the new number of buckets respect the
2208 * %unordered_multimap maximum load factor.
2209 */
2210 void
2212 { _M_h.rehash(__n); }
2213
2214 /**
2215 * @brief Prepare the %unordered_multimap for a specified number of
2216 * elements.
2217 * @param __n Number of elements required.
2218 *
2219 * Same as rehash(ceil(n / max_load_factor())).
2220 */
2221 void
2223 { _M_h.reserve(__n); }
2224
2225 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
2226 typename _Alloc1>
2227 friend bool
2228 operator==(const unordered_multimap<_Key1, _Tp1,
2229 _Hash1, _Pred1, _Alloc1>&,
2230 const unordered_multimap<_Key1, _Tp1,
2231 _Hash1, _Pred1, _Alloc1>&);
2232 };
2233
2234#if __cpp_deduction_guides >= 201606
2235
2236 template<typename _InputIterator,
2237 typename _Hash = hash<__iter_key_t<_InputIterator>>,
2238 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
2239 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
2240 typename = _RequireInputIter<_InputIterator>,
2241 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2242 typename = _RequireNotAllocator<_Pred>,
2243 typename = _RequireAllocator<_Allocator>>
2244 unordered_multimap(_InputIterator, _InputIterator,
2245 unordered_multimap<int, int>::size_type = {},
2246 _Hash = _Hash(), _Pred = _Pred(),
2247 _Allocator = _Allocator())
2248 -> unordered_multimap<__iter_key_t<_InputIterator>,
2249 __iter_val_t<_InputIterator>, _Hash, _Pred,
2250 _Allocator>;
2251
2252 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
2253 typename _Pred = equal_to<_Key>,
2254 typename _Allocator = allocator<pair<const _Key, _Tp>>,
2255 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2256 typename = _RequireNotAllocator<_Pred>,
2257 typename = _RequireAllocator<_Allocator>>
2260 _Hash = _Hash(), _Pred = _Pred(),
2261 _Allocator = _Allocator())
2263
2264 template<typename _InputIterator, typename _Allocator,
2265 typename = _RequireInputIter<_InputIterator>,
2266 typename = _RequireAllocator<_Allocator>>
2267 unordered_multimap(_InputIterator, _InputIterator,
2270 __iter_val_t<_InputIterator>,
2273
2274 template<typename _InputIterator, typename _Allocator,
2275 typename = _RequireInputIter<_InputIterator>,
2276 typename = _RequireAllocator<_Allocator>>
2277 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2279 __iter_val_t<_InputIterator>,
2282
2283 template<typename _InputIterator, typename _Hash, typename _Allocator,
2284 typename = _RequireInputIter<_InputIterator>,
2285 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2286 typename = _RequireAllocator<_Allocator>>
2287 unordered_multimap(_InputIterator, _InputIterator,
2289 _Allocator)
2291 __iter_val_t<_InputIterator>, _Hash,
2293
2294 template<typename _Key, typename _Tp, typename _Allocator,
2295 typename = _RequireAllocator<_Allocator>>
2298 _Allocator)
2300
2301 template<typename _Key, typename _Tp, typename _Allocator,
2302 typename = _RequireAllocator<_Allocator>>
2305
2306 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2307 typename = _RequireNotAllocatorOrIntegral<_Hash>,
2308 typename = _RequireAllocator<_Allocator>>
2311 _Hash, _Allocator)
2313
2314#if __glibcxx_containers_ranges // C++ >= 23
2315 template<ranges::input_range _Rg,
2316 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
2317 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
2318 __allocator_like _Allocator =
2320 unordered_multimap(from_range_t, _Rg&&,
2322 _Hash = _Hash(), _Pred = _Pred(),
2323 _Allocator = _Allocator())
2324 -> unordered_multimap<__detail::__range_key_type<_Rg>,
2325 __detail::__range_mapped_type<_Rg>,
2326 _Hash, _Pred, _Allocator>;
2327
2328 template<ranges::input_range _Rg,
2329 __allocator_like _Allocator>
2331 _Allocator)
2333 __detail::__range_mapped_type<_Rg>,
2336 _Allocator>;
2337
2338 template<ranges::input_range _Rg,
2339 __allocator_like _Allocator>
2340 unordered_multimap(from_range_t, _Rg&&, _Allocator)
2342 __detail::__range_mapped_type<_Rg>,
2345 _Allocator>;
2346
2347 template<ranges::input_range _Rg,
2348 __not_allocator_like _Hash,
2349 __allocator_like _Allocator>
2350 unordered_multimap(from_range_t, _Rg&&,
2352 _Hash, _Allocator)
2354 __detail::__range_mapped_type<_Rg>,
2356 _Allocator>;
2357#endif
2358#endif
2359
2360 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2361 inline void
2364 noexcept(noexcept(__x.swap(__y)))
2365 { __x.swap(__y); }
2366
2367 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2368 inline void
2371 noexcept(noexcept(__x.swap(__y)))
2372 { __x.swap(__y); }
2373
2374 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2375 inline bool
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
2385 { return !(__x == __y); }
2386#endif
2387
2388 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2389 inline bool
2392 { return __x._M_h._M_equal(__y._M_h); }
2393
2394#if __cpp_impl_three_way_comparison < 201907L
2395 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2396 inline bool
2399 { return !(__x == __y); }
2400#endif
2401
2402_GLIBCXX_END_NAMESPACE_CONTAINER
2403
2404#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
2405 // Allow std::unordered_map access to internals of compatible maps.
2406 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2407 typename _Alloc, typename _Hash2, typename _Eq2>
2408 struct _Hash_merge_helper<
2409 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2410 _Hash2, _Eq2>
2411 {
2412 private:
2413 template<typename... _Tp>
2414 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2415 template<typename... _Tp>
2416 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2417
2418 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2419
2420 static auto&
2421 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2422 { return __map._M_h; }
2423
2424 static auto&
2425 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2426 { return __map._M_h; }
2427 };
2428
2429 // Allow std::unordered_multimap access to internals of compatible maps.
2430 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
2431 typename _Alloc, typename _Hash2, typename _Eq2>
2432 struct _Hash_merge_helper<
2433 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
2434 _Hash2, _Eq2>
2435 {
2436 private:
2437 template<typename... _Tp>
2438 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
2439 template<typename... _Tp>
2440 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
2441
2442 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
2443
2444 static auto&
2445 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2446 { return __map._M_h; }
2447
2448 static auto&
2449 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
2450 { return __map._M_h; }
2451 };
2452#endif // node_extract
2453
2454_GLIBCXX_END_NAMESPACE_VERSION
2455} // namespace std
2456
2457#endif /* _UNORDERED_MAP_H */
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
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
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
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
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.
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.
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.
__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.
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.
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
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.
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.
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.
unordered_multimap(unordered_multimap &&)=default
Move constructor.
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
__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.
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
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.
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.
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.
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.
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.
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 __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
iterator end() noexcept
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.
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.
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.
const_iterator begin() const noexcept
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
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.
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
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.
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.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
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.
void rehash(size_type __n)
May rehash the unordered_map.
const_iterator cbegin() const noexcept