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