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