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