Clang Project

include/c++/7/bits/unordered_map.h
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
33namespace std _GLIBCXX_VISIBILITY(default)
34{
35_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36
37  /// Base types for unordered_map.
38  template<bool _Cache>
39    using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
40
41  template<typename _Key,
42    typename _Tp,
43    typename _Hash = hash<_Key>,
44    typename _Pred = std::equal_to<_Key>,
45    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
46    typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
47    using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
48                                        _Alloc, __detail::_Select1st,
49         _Pred, _Hash,
50         __detail::_Mod_range_hashing,
51         __detail::_Default_ranged_hash,
52         __detail::_Prime_rehash_policy, _Tr>;
53
54  /// Base types for unordered_multimap.
55  template<bool _Cache>
56    using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
57
58  template<typename _Key,
59    typename _Tp,
60    typename _Hash = hash<_Key>,
61    typename _Pred = std::equal_to<_Key>,
62    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
63    typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
64    using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
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>
72    class unordered_multimap;
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>,
100    class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
101    class unordered_map
102    {
103      typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
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       */
225      unordered_map(initializer_list<value_type> __l,
226     size_type __n = 0,
227     const hasher& __hf = hasher(),
228     const key_equal& __eql = key_equal(),
229     const allocator_type& __a = allocator_type())
230      : _M_h(__l, __n, __hf, __eql, __a)
231      { }
232
233      unordered_map(size_type __n, const allocator_type& __a)
234      : unordered_map(__n, hasher(), key_equal(), __a)
235      { }
236
237      unordered_map(size_type __n, const hasher& __hf,
238     const allocator_type& __a)
239      : unordered_map(__n, __hf, key_equal(), __a)
240      { }
241
242      template<typename _InputIterator>
243 unordered_map(_InputIterator __first, _InputIterator __last,
244       size_type __n,
245       const allocator_type& __a)
246 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
247 { }
248
249      template<typename _InputIterator>
250 unordered_map(_InputIterator __first, _InputIterator __last,
251       size_type __n, const hasher& __hf,
252       const allocator_type& __a)
253   : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
254 { }
255
256      unordered_map(initializer_list<value_type> __l,
257     size_type __n,
258     const allocator_type& __a)
259      : unordered_map(__l, __n, hasher(), key_equal(), __a)
260      { }
261
262      unordered_map(initializer_list<value_type> __l,
263     size_type __n, const hasher& __hf,
264     const allocator_type& __a)
265      : unordered_map(__l, __n, __hf, key_equal(), __a)
266      { }
267
268      /// Copy assignment operator.
269      unordered_map&
270      operator=(const unordered_map&) = default;
271
272      /// Move assignment operator.
273      unordered_map&
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       */
287      unordered_map&
288      operator=(initializer_list<value_type> __l)
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>
385 std::pair<iterator, bool>
386 emplace(_Args&&... __args)
387 { return _M_h.emplace(std::forward<_Args>(__args)...); }
388
389      /**
390       *  @brief Attempts to build and insert a std::pair into the
391       *  %unordered_map.
392       *
393       *  @param  __pos  An iterator that serves as a hint as to where the pair
394       *                should be inserted.
395       *  @param  __args  Arguments used to generate a new pair instance (see
396       *          std::piecewise_contruct for passing arguments to each
397       *          part of the pair constructor).
398       *  @return An iterator that points to the element with key of the
399       *          std::pair built from @a __args (may or may not be that
400       *          std::pair).
401       *
402       *  This function is not concerned about whether the insertion took place,
403       *  and thus does not return a boolean like the single-argument emplace()
404       *  does.
405       *  Note that the first parameter is only a hint and can potentially
406       *  improve the performance of the insertion process. A bad hint would
407       *  cause no gains in efficiency.
408       *
409       *  See
410       *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
411       *  for more on @a hinting.
412       *
413       *  Insertion requires amortized constant time.
414       */
415      template<typename... _Args>
416 iterator
417 emplace_hint(const_iterator __pos, _Args&&... __args)
418 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
419
420#if __cplusplus > 201402L
421      /// Extract a node.
422      node_type
423      extract(const_iterator __pos)
424      {
425 __glibcxx_assert(__pos != end());
426 return _M_h.extract(__pos);
427      }
428
429      /// Extract a node.
430      node_type
431      extract(const key_type& __key)
432      { return _M_h.extract(__key); }
433
434      /// Re-insert an extracted node.
435      insert_return_type
436      insert(node_type&& __nh)
437      { return _M_h._M_reinsert_node(std::move(__nh)); }
438
439      /// Re-insert an extracted node.
440      iterator
441      insert(const_iterator, node_type&& __nh)
442      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
443
444#define __cpp_lib_unordered_map_try_emplace 201411
445      /**
446       *  @brief Attempts to build and insert a std::pair into the
447       *  %unordered_map.
448       *
449       *  @param __k    Key to use for finding a possibly existing pair in
450       *                the unordered_map.
451       *  @param __args  Arguments used to generate the .second for a 
452       *                new pair instance.
453       *
454       *  @return  A pair, of which the first element is an iterator that points
455       *           to the possibly inserted pair, and the second is a bool that
456       *           is true if the pair was actually inserted.
457       *
458       *  This function attempts to build and insert a (key, value) %pair into
459       *  the %unordered_map.
460       *  An %unordered_map relies on unique keys and thus a %pair is only
461       *  inserted if its first element (the key) is not already present in the
462       *  %unordered_map.
463       *  If a %pair is not inserted, this function has no effect.
464       *
465       *  Insertion requires amortized constant time.
466       */
467      template <typename... _Args>
468        pair<iterator, bool>
469        try_emplace(const key_type& __k, _Args&&... __args)
470        {
471          iterator __i = find(__k);
472          if (__i == end())
473            {
474              __i = emplace(std::piecewise_construct,
475                            std::forward_as_tuple(__k),
476                            std::forward_as_tuple(
477                              std::forward<_Args>(__args)...))
478                .first;
479              return {__i, true};
480            }
481          return {__i, false};
482        }
483
484      // move-capable overload
485      template <typename... _Args>
486        pair<iterator, bool>
487        try_emplace(key_type&& __k, _Args&&... __args)
488        {
489          iterator __i = find(__k);
490          if (__i == end())
491            {
492              __i = emplace(std::piecewise_construct,
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())
537            __i = emplace_hint(__hint, std::piecewise_construct,
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())
551            __i = emplace_hint(__hint, std::piecewise_construct,
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       */
577      std::pair<iterator, bool>
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
583      std::pair<iterator, bool>
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,
589       pair<iterator, bool>>
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
654      insert(initializer_list<value_type> __l)
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>
681        pair<iterator, bool>
682        insert_or_assign(const key_type& __k, _Obj&& __obj)
683        {
684          iterator __i = find(__k);
685          if (__i == end())
686            {
687              __i = emplace(std::piecewise_construct,
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>
699        pair<iterator, bool>
700        insert_or_assign(key_type&& __k, _Obj&& __obj)
701        {
702          iterator __i = find(__k);
703          if (__i == end())
704            {
705              __i = emplace(std::piecewise_construct,
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
855      swap(unordered_map& __x)
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
865 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
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
873 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
874 { merge(__source); }
875
876      template<typename _H2, typename _P2>
877 void
878 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
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
886 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
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
895      hash_function() const
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       */
949      std::pair<iterator, iterator>
950      equal_range(const key_type& __x)
951      { return _M_h.equal_range(__x); }
952
953      std::pair<const_iterator, const_iterator>
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
1125 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
1126    const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
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>,
1155    class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
1156    class unordered_multimap
1157    {
1158      typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
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.
1237      unordered_multimap(unordered_multimap&&) = default;
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       */
1263      unordered_multimap(unordered_multimap&& __ummap,
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       */
1279      unordered_multimap(initializer_list<value_type> __l,
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
1310      unordered_multimap(initializer_list<value_type> __l,
1311  size_type __n,
1312  const allocator_type& __a)
1313      : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1314      { }
1315
1316      unordered_multimap(initializer_list<value_type> __l,
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.
1323      unordered_multimap&
1324      operator=(const unordered_multimap&) = default;
1325
1326      /// Move assignment operator.
1327      unordered_multimap&
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       */
1341      unordered_multimap&
1342      operator=(initializer_list<value_type> __l)
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
1548      insert(initializer_list<value_type> __l)
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
1655      swap(unordered_multimap& __x)
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
1665 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
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
1674 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1675 { merge(__source); }
1676
1677      template<typename _H2, typename _P2>
1678 void
1679 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
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
1688 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
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
1697      hash_function() const
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       */
1745      std::pair<iterator, iterator>
1746      equal_range(const key_type& __x)
1747      { return _M_h.equal_range(__x); }
1748
1749      std::pair<const_iterator, const_iterator>
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
1890    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1891  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
1897    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1898  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1899    noexcept(noexcept(__x.swap(__y)))
1900    { __x.swap(__y); }
1901
1902  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1903    inline bool
1904    operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1905        const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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,
1911        const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1912    { return !(__x == __y); }
1913
1914  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1915    inline bool
1916    operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1917        const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
1922    operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1923        const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
1943      friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
1944
1945      static auto&
1946      _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
1947      { return __map._M_h; }
1948
1949      static auto&
1950      _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
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
1967      friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
1968
1969      static auto&
1970      _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
1971      { return __map._M_h; }
1972
1973      static auto&
1974      _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
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 */
1983
std::unordered_map::_M_h
std::unordered_map::get_allocator
std::unordered_map::empty
std::unordered_map::size
std::unordered_map::max_size
std::unordered_map::begin
std::unordered_map::begin
std::unordered_map::cbegin
std::unordered_map::end
std::unordered_map::end
std::unordered_map::cend
std::unordered_map::emplace
std::unordered_map::emplace_hint
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::insert
std::unordered_map::erase
std::unordered_map::erase
std::unordered_map::erase
std::unordered_map::erase
std::unordered_map::clear
std::unordered_map::swap
std::unordered_map::hash_function
std::unordered_map::key_eq
std::unordered_map::find
std::unordered_map::find
std::unordered_map::count
std::unordered_map::equal_range
std::unordered_map::equal_range
std::unordered_map::at
std::unordered_map::at
std::unordered_map::bucket_count
std::unordered_map::max_bucket_count
std::unordered_map::bucket_size
std::unordered_map::bucket
std::unordered_map::begin
std::unordered_map::begin
std::unordered_map::cbegin
std::unordered_map::end
std::unordered_map::end
std::unordered_map::cend
std::unordered_map::load_factor
std::unordered_map::max_load_factor
std::unordered_map::max_load_factor
std::unordered_map::rehash
std::unordered_map::reserve
std::unordered_multimap::_M_h
std::unordered_multimap::get_allocator
std::unordered_multimap::empty
std::unordered_multimap::size
std::unordered_multimap::max_size
std::unordered_multimap::begin
std::unordered_multimap::begin
std::unordered_multimap::cbegin
std::unordered_multimap::end
std::unordered_multimap::end
std::unordered_multimap::cend
std::unordered_multimap::emplace
std::unordered_multimap::emplace_hint
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::insert
std::unordered_multimap::erase
std::unordered_multimap::erase
std::unordered_multimap::erase
std::unordered_multimap::erase
std::unordered_multimap::clear
std::unordered_multimap::swap
std::unordered_multimap::hash_function
std::unordered_multimap::key_eq
std::unordered_multimap::find
std::unordered_multimap::find
std::unordered_multimap::count
std::unordered_multimap::equal_range
std::unordered_multimap::equal_range
std::unordered_multimap::bucket_count
std::unordered_multimap::max_bucket_count
std::unordered_multimap::bucket_size
std::unordered_multimap::bucket
std::unordered_multimap::begin
std::unordered_multimap::begin
std::unordered_multimap::cbegin
std::unordered_multimap::end
std::unordered_multimap::end
std::unordered_multimap::cend
std::unordered_multimap::load_factor
std::unordered_multimap::max_load_factor
std::unordered_multimap::max_load_factor
std::unordered_multimap::rehash
std::unordered_multimap::reserve
CodeThinker, Enjoy your reading code