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