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