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