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