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 
41 namespace 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>
81  class unordered_multimap;
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.
329  operator=(unordered_map&&) = default;
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.
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.
362  size_type
363  size() const noexcept
364  { return _M_h.size(); }
365 
366  /// Returns the maximum size of the %unordered_map.
367  size_type
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  */
377  iterator
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  */
387  begin() const noexcept
388  { return _M_h.begin(); }
389 
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  */
399  iterator
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  */
409  end() const noexcept
410  { return _M_h.end(); }
411 
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>
471  iterator
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
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.
495  iterator
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>
568  iterator
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>
578  iterator
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  */
643  iterator
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
649  iterator
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>
724  pair<iterator, bool>
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>
773  iterator
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>
785  iterator
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  */
810  iterator
811  erase(const_iterator __position)
812  { return _M_h.erase(__position); }
813 
814  // LWG 2059.
815  iterator
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  */
832  size_type
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  */
850  iterator
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.
927  key_equal
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  */
945  iterator
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 
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  */
978  size_type
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  */
1019  equal_range(const key_type& __x)
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  */
1056  mapped_type&
1057  operator[](const key_type& __k)
1058  { return _M_h[__k]; }
1059 
1060  mapped_type&
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  */
1073  mapped_type&
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 
1134  cbegin(size_type __n) const
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
1182  max_load_factor(float __z)
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>>
1237  unordered_map(initializer_list<pair<_Key, _Tp>>,
1238  typename unordered_map<int, int>::size_type = {},
1239  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1240  -> unordered_map<_Key, _Tp, _Hash, _Pred, _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)
1247  -> unordered_map<__iter_key_t<_InputIterator>,
1248  __iter_val_t<_InputIterator>,
1249  hash<__iter_key_t<_InputIterator>>,
1250  equal_to<__iter_key_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)
1257  -> unordered_map<__iter_key_t<_InputIterator>,
1258  __iter_val_t<_InputIterator>,
1259  hash<__iter_key_t<_InputIterator>>,
1260  equal_to<__iter_key_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)
1270  -> unordered_map<__iter_key_t<_InputIterator>,
1271  __iter_val_t<_InputIterator>, _Hash,
1272  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1273 
1274  template<typename _Key, typename _Tp, typename _Allocator,
1275  typename = _RequireAllocator<_Allocator>>
1276  unordered_map(initializer_list<pair<_Key, _Tp>>,
1278  _Allocator)
1279  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1280 
1281  template<typename _Key, typename _Tp, typename _Allocator,
1282  typename = _RequireAllocator<_Allocator>>
1283  unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1284  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1285 
1286  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1287  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1288  typename = _RequireAllocator<_Allocator>>
1289  unordered_map(initializer_list<pair<_Key, _Tp>>,
1291  _Hash, _Allocator)
1292  -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _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 =
1299  allocator<__detail::__range_to_alloc_type<_Rg>>>
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>
1308  unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
1309  _Allocator)
1310  -> unordered_map<__detail::__range_key_type<_Rg>,
1311  __detail::__range_mapped_type<_Rg>,
1312  hash<__detail::__range_key_type<_Rg>>,
1313  equal_to<__detail::__range_key_type<_Rg>>,
1314  _Allocator>;
1315 
1316  template<ranges::input_range _Rg,
1317  __allocator_like _Allocator>
1318  unordered_map(from_range_t, _Rg&&, _Allocator)
1319  -> unordered_map<__detail::__range_key_type<_Rg>,
1320  __detail::__range_mapped_type<_Rg>,
1321  hash<__detail::__range_key_type<_Rg>>,
1322  equal_to<__detail::__range_key_type<_Rg>>,
1323  _Allocator>;
1324 
1325  template<ranges::input_range _Rg,
1326  __not_allocator_like _Hash,
1327  __allocator_like _Allocator>
1328  unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
1329  _Hash, _Allocator)
1330  -> unordered_map<__detail::__range_key_type<_Rg>,
1331  __detail::__range_mapped_type<_Rg>,
1332  _Hash, equal_to<__detail::__range_key_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.
1404  unordered_multimap() = default;
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  */
1463  unordered_multimap(const unordered_multimap& __ummap,
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  */
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 
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.
1578  operator=(const unordered_multimap&) = default;
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.
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  */
1640  begin() const noexcept
1641  { return _M_h.begin(); }
1642 
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  */
1662  end() const noexcept
1663  { return _M_h.end(); }
1664 
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
1764  insert(const_iterator __hint, const value_type& __x)
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
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
1871  erase(const_iterator __position)
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 
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  */
2076  equal_range(const key_type& __x)
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 
2152  cbegin(size_type __n) const
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
2200  max_load_factor(float __z)
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,
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>>
2258  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2260  _Hash = _Hash(), _Pred = _Pred(),
2261  _Allocator = _Allocator())
2262  -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
2263 
2264  template<typename _InputIterator, typename _Allocator,
2265  typename = _RequireInputIter<_InputIterator>,
2266  typename = _RequireAllocator<_Allocator>>
2267  unordered_multimap(_InputIterator, _InputIterator,
2269  -> unordered_multimap<__iter_key_t<_InputIterator>,
2270  __iter_val_t<_InputIterator>,
2271  hash<__iter_key_t<_InputIterator>>,
2272  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2273 
2274  template<typename _InputIterator, typename _Allocator,
2275  typename = _RequireInputIter<_InputIterator>,
2276  typename = _RequireAllocator<_Allocator>>
2277  unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2278  -> unordered_multimap<__iter_key_t<_InputIterator>,
2279  __iter_val_t<_InputIterator>,
2280  hash<__iter_key_t<_InputIterator>>,
2281  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
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)
2290  -> unordered_multimap<__iter_key_t<_InputIterator>,
2291  __iter_val_t<_InputIterator>, _Hash,
2292  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
2293 
2294  template<typename _Key, typename _Tp, typename _Allocator,
2295  typename = _RequireAllocator<_Allocator>>
2296  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2298  _Allocator)
2299  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2300 
2301  template<typename _Key, typename _Tp, typename _Allocator,
2302  typename = _RequireAllocator<_Allocator>>
2303  unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2304  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
2305 
2306  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
2307  typename = _RequireNotAllocatorOrIntegral<_Hash>,
2308  typename = _RequireAllocator<_Allocator>>
2309  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
2311  _Hash, _Allocator)
2312  -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _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 =
2319  allocator<__detail::__range_to_alloc_type<_Rg>>>
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>
2330  unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
2331  _Allocator)
2332  -> unordered_multimap<__detail::__range_key_type<_Rg>,
2333  __detail::__range_mapped_type<_Rg>,
2334  hash<__detail::__range_key_type<_Rg>>,
2335  equal_to<__detail::__range_key_type<_Rg>>,
2336  _Allocator>;
2337 
2338  template<ranges::input_range _Rg,
2339  __allocator_like _Allocator>
2340  unordered_multimap(from_range_t, _Rg&&, _Allocator)
2341  -> unordered_multimap<__detail::__range_key_type<_Rg>,
2342  __detail::__range_mapped_type<_Rg>,
2343  hash<__detail::__range_key_type<_Rg>>,
2344  equal_to<__detail::__range_key_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)
2353  -> unordered_multimap<__detail::__range_key_type<_Rg>,
2354  __detail::__range_mapped_type<_Rg>,
2355  _Hash, equal_to<__detail::__range_key_type<_Rg>>,
2356  _Allocator>;
2357 #endif
2358 #endif
2359 
2360  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2361  inline void
2362  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2363  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
2369  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2370  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
2376  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2377  const unordered_map<_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_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2384  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2385  { return !(__x == __y); }
2386 #endif
2387 
2388  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2389  inline bool
2390  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2391  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
2397  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2398  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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 */
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
__detail::_Hashtable_traits< _Cache, false, false > __ummap_traits
Base types for unordered_multimap.
Definition: unordered_map.h:65
__detail::_Hashtable_traits< _Cache, false, true > __umap_traits
Base types for unordered_map.
Definition: unordered_map.h:48
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.
Definition: stl_function.h:371
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.
unordered_multimap & operator=(const unordered_multimap &)=default
Copy assignment operator.
_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.
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.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
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.
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(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.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_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.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
_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.
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.
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.
unordered_multimap & operator=(unordered_multimap &&)=default
Move assignment operator.
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.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
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.
__enable_if_t< is_constructible< value_type, _Pair && >::value, iterator > insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
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.
std::pair< iterator, bool > insert(const 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.
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.
_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.
pair< iterator, bool > insert_or_assign(const key_type &__k, _Obj &&__obj)
Attempts to insert a std::pair into the unordered_map.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
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.
pair< iterator, bool > try_emplace(const key_type &__k, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
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.
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.
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.
unordered_map & operator=(unordered_map &&)=default
Move assignment operator.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
_Hashtable::hasher hasher
Public typedefs.
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
const_iterator begin() const noexcept
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
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.
__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.
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.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
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.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert a std::pair into the 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.
__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.
_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