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,
68  __detail::_Mod_range_hashing,
69  __detail::_Default_ranged_hash,
70  __detail::_Prime_rehash_policy, _Tr>;
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
151  unordered_map(size_type __n,
152  const hasher& __hf = hasher(),
153  const key_equal& __eql = key_equal(),
154  const allocator_type& __a = allocator_type())
155  : _M_h(__n, __hf, __eql, __a)
156  { }
157 
158  /**
159  * @brief Builds an %unordered_map from a range.
160  * @param __first An input iterator.
161  * @param __last An input iterator.
162  * @param __n Minimal initial number of buckets.
163  * @param __hf A hash functor.
164  * @param __eql A key equality functor.
165  * @param __a An allocator object.
166  *
167  * Create an %unordered_map consisting of copies of the elements from
168  * [__first,__last). This is linear in N (where N is
169  * distance(__first,__last)).
170  */
171  template<typename _InputIterator>
172  unordered_map(_InputIterator __first, _InputIterator __last,
173  size_type __n = 0,
174  const hasher& __hf = hasher(),
175  const key_equal& __eql = key_equal(),
176  const allocator_type& __a = allocator_type())
177  : _M_h(__first, __last, __n, __hf, __eql, __a)
178  { }
179 
180  /// Copy constructor.
181  unordered_map(const unordered_map&) = default;
182 
183  /// Move constructor.
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
191  unordered_map(const allocator_type& __a)
192  : _M_h(__a)
193  { }
194 
195  /*
196  * @brief Copy constructor with allocator argument.
197  * @param __uset Input %unordered_map to copy.
198  * @param __a An allocator object.
199  */
200  unordered_map(const unordered_map& __umap,
201  const allocator_type& __a)
202  : _M_h(__umap._M_h, __a)
203  { }
204 
205  /*
206  * @brief Move constructor with allocator argument.
207  * @param __uset Input %unordered_map to move.
208  * @param __a An allocator object.
209  */
210  unordered_map(unordered_map&& __umap,
211  const allocator_type& __a)
212  : _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 
258  size_type __n,
259  const allocator_type& __a)
260  : unordered_map(__l, __n, hasher(), key_equal(), __a)
261  { }
262 
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.
296  allocator_type
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  */
332  const_iterator
333  begin() const noexcept
334  { return _M_h.begin(); }
335 
336  const_iterator
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  */
354  const_iterator
355  end() const noexcept
356  { return _M_h.end(); }
357 
358  const_iterator
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>
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>
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
585  insert(value_type&& __x)
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
625  insert(const_iterator __hint, value_type&& __x)
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>
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
835  erase(const_iterator __first, const_iterator __last)
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 _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
878  { merge(__source); }
879 
880  template<typename _H2, typename _P2>
881  void
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
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 
926  const_iterator
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&
980  operator[](key_type&& __k)
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  */
1037  local_iterator
1038  begin(size_type __n)
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  */
1048  const_local_iterator
1049  begin(size_type __n) const
1050  { return _M_h.begin(__n); }
1051 
1052  const_local_iterator
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  */
1063  local_iterator
1064  end(size_type __n)
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  */
1074  const_local_iterator
1075  end(size_type __n) const
1076  { return _M_h.end(__n); }
1077 
1078  const_local_iterator
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
1112  rehash(size_type __n)
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
1123  reserve(size_type __n)
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>>
1153  typename unordered_map<int, int>::size_type = {},
1154  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _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)
1163  __iter_val_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)
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)
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>>
1192  _Allocator)
1194 
1195  template<typename _Key, typename _Tp, typename _Allocator,
1196  typename = _RequireAllocator<_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>>
1204  _Hash, _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  {
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
1284  unordered_multimap(size_type __n,
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
1324  unordered_multimap(const allocator_type& __a)
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 
1367  unordered_multimap(size_type __n, const allocator_type& __a)
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 
1391  size_type __n,
1392  const allocator_type& __a)
1393  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1394  { }
1395 
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.
1429  allocator_type
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  */
1465  const_iterator
1466  begin() const noexcept
1467  { return _M_h.begin(); }
1468 
1469  const_iterator
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  */
1487  const_iterator
1488  end() const noexcept
1489  { return _M_h.end(); }
1490 
1491  const_iterator
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
1560  insert(value_type&& __x)
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
1598  insert(const_iterator __hint, value_type&& __x)
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
1715  erase(const_iterator __first, const_iterator __last)
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 _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
1759  { merge(__source); }
1760 
1761  template<typename _H2, typename _P2>
1762  void
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
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 
1808  const_iterator
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  */
1874  local_iterator
1875  begin(size_type __n)
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  */
1885  const_local_iterator
1886  begin(size_type __n) const
1887  { return _M_h.begin(__n); }
1888 
1889  const_local_iterator
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  */
1900  local_iterator
1901  end(size_type __n)
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  */
1911  const_local_iterator
1912  end(size_type __n) const
1913  { return _M_h.end(__n); }
1914 
1915  const_local_iterator
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
1949  rehash(size_type __n)
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
1960  reserve(size_type __n)
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>>
1994  _Hash = _Hash(), _Pred = _Pred(),
1995  _Allocator = _Allocator())
1997 
1998  template<typename _InputIterator, typename _Allocator,
1999  typename = _RequireInputIter<_InputIterator>,
2000  typename = _RequireAllocator<_Allocator>>
2001  unordered_multimap(_InputIterator, _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)
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)
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>>
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>>
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>>
2043  _Hash, _Allocator)
2045 
2046 #endif
2047 
2048  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2049  inline void
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
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,
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,
2072  { return !(__x == __y); }
2073 
2074  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2075  inline bool
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
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 
2103 
2104  static auto&
2106  { return __map._M_h; }
2107 
2108  static auto&
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 
2127 
2128  static auto&
2130  { return __map._M_h; }
2131 
2132  static auto&
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 */
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.
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
iterator end() noexcept
iterator begin() noexcept
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::iterator 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.
_Hashtable::reference reference
Iterator-related typedefs.
const_iterator cbegin() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
size_type max_size() const noexcept
Returns the maximum size of the unordered_map.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
iterator erase(iterator __position)
Erases an element from an unordered_map.
void max_load_factor(float __z)
Change the unordered_map maximum load factor.
iterator erase(iterator __position)
Erases an element from an unordered_multimap.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_map.
const mapped_type & at(const key_type &__k) const
Access to unordered_map data.
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1987
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_map(const allocator_type &__a)
Creates an unordered_map with no elements.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
float load_factor() const noexcept
Returns the average number of elements per bucket.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multimap tries to keep the load factor less than or equa...
Primary class template hash.
Definition: system_error:142
iterator insert(const_iterator __hint, value_type &&__x)
Inserts a std::pair into the unordered_multimap.
iterator end() noexcept
size_type size() const noexcept
Returns the size of the unordered_multimap.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_multimap.
iterator emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_multimap.
const_iterator cbegin() const noexcept
local_iterator end(size_type __n)
Returns a read/write iterator pointing to one past the last bucket elements.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
const_iterator cend() const noexcept
_Hashtable::key_type key_type
Public typedefs.
void reserve(size_type __n)
Prepare the unordered_map for a specified number of elements.
iterator insert(_Pair &&__x)
Inserts a std::pair into the unordered_multimap.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_map.
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.
_Hashtable::mapped_type mapped_type
Public typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
void swap(unordered_multimap &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another 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::pointer pointer
Iterator-related typedefs.
const_iterator begin() const noexcept
void rehash(size_type __n)
May rehash the unordered_map.
iterator insert(const_iterator __hint, _Pair &&__x)
Inserts a std::pair into the unordered_multimap.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multimap.
_Hashtable::allocator_type allocator_type
Public typedefs.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:73
const_iterator end() const noexcept
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_map.
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
void reserve(size_type __n)
Prepare the unordered_multimap for a specified number of elements.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
_Hashtable::key_type key_type
Public typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
key_equal key_eq() const
Returns the key comparison object with which the unordered_map was constructed.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_map.
_Hashtable::hasher hasher
Public typedefs.
bool empty() const noexcept
Returns true if the unordered_map is empty.
_Hashtable::mapped_type mapped_type
Public typedefs.
_Hashtable::value_type value_type
Public typedefs.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multimap.
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...
_Hashtable::iterator iterator
Iterator-related typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multimap.
hasher hash_function() const
Returns the hash functor object with which the unordered_map was constructed.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
hasher hash_function() const
Returns the hash functor object with which the unordered_multimap was constructed.
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, 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.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:198
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
ISO C++ entities toplevel namespace is std.
One of the comparison functors.
Definition: stl_function.h:331
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_map.
const_iterator cend() const noexcept
void max_load_factor(float __z)
Change the unordered_multimap maximum load factor.
size_type size() const noexcept
Returns the size of the unordered_map.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::pointer pointer
Iterator-related typedefs.
is_constructible
Definition: type_traits:932
unordered_multimap(const allocator_type &__a)
Creates an unordered_multimap with no elements.
The standard allocator, as per [20.4].
Definition: allocator.h:108
Default ranged hash function H. In principle it should be a function object composed from objects of ...
mapped_type & operator[](key_type &&__k)
Subscript ( [] ) access to unordered_map data.
_Hashtable::reference reference
Iterator-related typedefs.
iterator insert(const_iterator __hint, _Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
iterator insert(const value_type &__x)
Inserts a std::pair into the unordered_multimap.
bool empty() const noexcept
Returns true if the unordered_multimap is empty.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) that associat...
size_type count(const key_type &__x) const
Finds the number of elements.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator insert(value_type &&__x)
Inserts a std::pair into the unordered_multimap.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_map.
_Hashtable::allocator_type allocator_type
Public typedefs.
_Hashtable::value_type value_type
Public typedefs.
const_iterator begin() const noexcept
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multimap.
void rehash(size_type __n)
May rehash the unordered_multimap.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multimap.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert a std::pair into the unordered_map.
initializer_list
const_iterator end() const noexcept
key_equal key_eq() const
Returns the key comparison object with which the unordered_multimap was constructed.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multimap.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
_Hashtable::hasher hasher
Public 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.
_Hashtable::key_equal key_equal
Public typedefs.
mapped_type & at(const key_type &__k)
Access to unordered_map data.
unordered_map & operator=(initializer_list< value_type > __l)
Unordered_map list assignment operator.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert a std::pair into the unordered_map.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
local_iterator begin(size_type __n)
Returns a read/write iterator pointing to the first bucket element.
unordered_map & operator=(const unordered_map &)=default
Copy assignment operator.
unordered_multimap & operator=(initializer_list< value_type > __l)
Unordered_multimap list assignment operator.
iterator erase(const_iterator __position)
Erases an element from an unordered_map.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_map()=default
Default constructor.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert a std::pair into the unordered_map.
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.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_map.
Default range hashing function: use division to fold a large number into the range [0...
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multimap.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
void clear() noexcept
iterator erase(const_iterator __position)
Erases an element from an unordered_multimap.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
std::pair< iterator, bool > insert(_Pair &&__x)
Attempts to insert a std::pair into the unordered_map.
iterator begin() noexcept
iterator insert(const_iterator __hint, const value_type &__x)
Inserts a std::pair into the unordered_multimap.
float load_factor() const noexcept
Returns the average number of elements per bucket.
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.
mapped_type & operator[](const key_type &__k)
Subscript ( [] ) access to unordered_map data.