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