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