Update gcc-50 to SVN version 225979 (gcc-5-branch)
[dragonfly.git] / contrib / gcc-5.0 / libstdc++-v3 / include / bits / unordered_map.h
1 // unordered_map implementation -*- C++ -*-
2
3 // Copyright (C) 2010-2015 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>
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   /**
72    *  @brief A standard container composed of unique keys (containing
73    *  at most one of each key value) that associates values of another type
74    *  with the keys.
75    *
76    *  @ingroup unordered_associative_containers
77    *
78    *  @tparam  _Key    Type of key objects.
79    *  @tparam  _Tp     Type of mapped objects.
80    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
81    *  @tparam  _Pred   Predicate function object type, defaults
82    *                   to equal_to<_Value>.
83    *  @tparam  _Alloc  Allocator type, defaults to 
84    *                   std::allocator<std::pair<const _Key, _Tp>>.
85    *
86    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
87    *  <a href="tables.html#xx">unordered associative container</a>
88    *
89    * The resulting value type of the container is std::pair<const _Key, _Tp>.
90    *
91    *  Base is _Hashtable, dispatched at compile time via template
92    *  alias __umap_hashtable.
93    */
94   template<class _Key, class _Tp,
95            class _Hash = hash<_Key>,
96            class _Pred = std::equal_to<_Key>,
97            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
98     class unordered_map
99     {
100       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
101       _Hashtable _M_h;
102
103     public:
104       // typedefs:
105       //@{
106       /// Public typedefs.
107       typedef typename _Hashtable::key_type     key_type;
108       typedef typename _Hashtable::value_type   value_type;
109       typedef typename _Hashtable::mapped_type  mapped_type;
110       typedef typename _Hashtable::hasher       hasher;
111       typedef typename _Hashtable::key_equal    key_equal;
112       typedef typename _Hashtable::allocator_type allocator_type;
113       //@}
114
115       //@{
116       ///  Iterator-related typedefs.
117       typedef typename _Hashtable::pointer              pointer;
118       typedef typename _Hashtable::const_pointer        const_pointer;
119       typedef typename _Hashtable::reference            reference;
120       typedef typename _Hashtable::const_reference      const_reference;
121       typedef typename _Hashtable::iterator             iterator;
122       typedef typename _Hashtable::const_iterator       const_iterator;
123       typedef typename _Hashtable::local_iterator       local_iterator;
124       typedef typename _Hashtable::const_local_iterator const_local_iterator;
125       typedef typename _Hashtable::size_type            size_type;
126       typedef typename _Hashtable::difference_type      difference_type;
127       //@}
128
129       //construct/destroy/copy
130
131       /// Default constructor.
132       unordered_map() = default;
133
134       /**
135        *  @brief  Default constructor creates no elements.
136        *  @param __n  Minimal initial number of buckets.
137        *  @param __hf  A hash functor.
138        *  @param __eql  A key equality functor.
139        *  @param __a  An allocator object.
140        */
141       explicit
142       unordered_map(size_type __n,
143                     const hasher& __hf = hasher(),
144                     const key_equal& __eql = key_equal(),
145                     const allocator_type& __a = allocator_type())
146       : _M_h(__n, __hf, __eql, __a)
147       { }
148
149       /**
150        *  @brief  Builds an %unordered_map from a range.
151        *  @param  __first  An input iterator.
152        *  @param  __last  An input iterator.
153        *  @param __n  Minimal initial number of buckets.
154        *  @param __hf  A hash functor.
155        *  @param __eql  A key equality functor.
156        *  @param __a  An allocator object.
157        *
158        *  Create an %unordered_map consisting of copies of the elements from
159        *  [__first,__last).  This is linear in N (where N is
160        *  distance(__first,__last)).
161        */
162       template<typename _InputIterator>
163         unordered_map(_InputIterator __first, _InputIterator __last,
164                       size_type __n = 0,
165                       const hasher& __hf = hasher(),
166                       const key_equal& __eql = key_equal(),
167                       const allocator_type& __a = allocator_type())
168         : _M_h(__first, __last, __n, __hf, __eql, __a)
169         { }
170
171       /// Copy constructor.
172       unordered_map(const unordered_map&) = default;
173
174       /// Move constructor.
175       unordered_map(unordered_map&&) = default;
176
177       /**
178        *  @brief Creates an %unordered_map with no elements.
179        *  @param __a An allocator object.
180        */
181       explicit
182       unordered_map(const allocator_type& __a)
183         : _M_h(__a)
184       { }
185
186       /*
187        *  @brief Copy constructor with allocator argument.
188        * @param  __uset  Input %unordered_map to copy.
189        * @param  __a  An allocator object.
190        */
191       unordered_map(const unordered_map& __umap,
192                     const allocator_type& __a)
193       : _M_h(__umap._M_h, __a)
194       { }
195
196       /*
197        *  @brief  Move constructor with allocator argument.
198        *  @param  __uset Input %unordered_map to move.
199        *  @param  __a    An allocator object.
200        */
201       unordered_map(unordered_map&& __umap,
202                     const allocator_type& __a)
203       : _M_h(std::move(__umap._M_h), __a)
204       { }
205
206       /**
207        *  @brief  Builds an %unordered_map from an initializer_list.
208        *  @param  __l  An initializer_list.
209        *  @param __n  Minimal initial number of buckets.
210        *  @param __hf  A hash functor.
211        *  @param __eql  A key equality functor.
212        *  @param  __a  An allocator object.
213        *
214        *  Create an %unordered_map consisting of copies of the elements in the
215        *  list. This is linear in N (where N is @a __l.size()).
216        */
217       unordered_map(initializer_list<value_type> __l,
218                     size_type __n = 0,
219                     const hasher& __hf = hasher(),
220                     const key_equal& __eql = key_equal(),
221                     const allocator_type& __a = allocator_type())
222       : _M_h(__l, __n, __hf, __eql, __a)
223       { }
224
225       unordered_map(size_type __n, const allocator_type& __a)
226       : unordered_map(__n, hasher(), key_equal(), __a)
227       { }
228
229       unordered_map(size_type __n, const hasher& __hf,
230                     const allocator_type& __a)
231       : unordered_map(__n, __hf, key_equal(), __a)
232       { }
233
234       template<typename _InputIterator>
235         unordered_map(_InputIterator __first, _InputIterator __last,
236                       size_type __n,
237                       const allocator_type& __a)
238         : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
239         { }
240
241       template<typename _InputIterator>
242         unordered_map(_InputIterator __first, _InputIterator __last,
243                       size_type __n, const hasher& __hf,
244                       const allocator_type& __a)
245           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
246         { }
247
248       unordered_map(initializer_list<value_type> __l,
249                     size_type __n,
250                     const allocator_type& __a)
251       : unordered_map(__l, __n, hasher(), key_equal(), __a)
252       { }
253
254       unordered_map(initializer_list<value_type> __l,
255                     size_type __n, const hasher& __hf,
256                     const allocator_type& __a)
257       : unordered_map(__l, __n, __hf, key_equal(), __a)
258       { }
259
260       /// Copy assignment operator.
261       unordered_map&
262       operator=(const unordered_map&) = default;
263
264       /// Move assignment operator.
265       unordered_map&
266       operator=(unordered_map&&) = default;
267
268       /**
269        *  @brief  %Unordered_map list assignment operator.
270        *  @param  __l  An initializer_list.
271        *
272        *  This function fills an %unordered_map with copies of the elements in
273        *  the initializer list @a __l.
274        *
275        *  Note that the assignment completely changes the %unordered_map and
276        *  that the resulting %unordered_map's size is the same as the number
277        *  of elements assigned.  Old data may be lost.
278        */
279       unordered_map&
280       operator=(initializer_list<value_type> __l)
281       {
282         _M_h = __l;
283         return *this;
284       }
285
286       ///  Returns the allocator object with which the %unordered_map was
287       ///  constructed.
288       allocator_type
289       get_allocator() const noexcept
290       { return _M_h.get_allocator(); }
291
292       // size and capacity:
293
294       ///  Returns true if the %unordered_map is empty.
295       bool
296       empty() const noexcept
297       { return _M_h.empty(); }
298
299       ///  Returns the size of the %unordered_map.
300       size_type
301       size() const noexcept
302       { return _M_h.size(); }
303
304       ///  Returns the maximum size of the %unordered_map.
305       size_type
306       max_size() const noexcept
307       { return _M_h.max_size(); }
308
309       // iterators.
310
311       /**
312        *  Returns a read/write iterator that points to the first element in the
313        *  %unordered_map.
314        */
315       iterator
316       begin() noexcept
317       { return _M_h.begin(); }
318
319       //@{
320       /**
321        *  Returns a read-only (constant) iterator that points to the first
322        *  element in the %unordered_map.
323        */
324       const_iterator
325       begin() const noexcept
326       { return _M_h.begin(); }
327
328       const_iterator
329       cbegin() const noexcept
330       { return _M_h.begin(); }
331       //@}
332
333       /**
334        *  Returns a read/write iterator that points one past the last element in
335        *  the %unordered_map.
336        */
337       iterator
338       end() noexcept
339       { return _M_h.end(); }
340
341       //@{
342       /**
343        *  Returns a read-only (constant) iterator that points one past the last
344        *  element in the %unordered_map.
345        */
346       const_iterator
347       end() const noexcept
348       { return _M_h.end(); }
349
350       const_iterator
351       cend() const noexcept
352       { return _M_h.end(); }
353       //@}
354
355       // modifiers.
356
357       /**
358        *  @brief Attempts to build and insert a std::pair into the
359        *  %unordered_map.
360        *
361        *  @param __args  Arguments used to generate a new pair instance (see
362        *                std::piecewise_contruct for passing arguments to each
363        *                part of the pair constructor).
364        *
365        *  @return  A pair, of which the first element is an iterator that points
366        *           to the possibly inserted pair, and the second is a bool that
367        *           is true if the pair was actually inserted.
368        *
369        *  This function attempts to build and insert a (key, value) %pair into
370        *  the %unordered_map.
371        *  An %unordered_map relies on unique keys and thus a %pair is only
372        *  inserted if its first element (the key) is not already present in the
373        *  %unordered_map.
374        *
375        *  Insertion requires amortized constant time.
376        */
377       template<typename... _Args>
378         std::pair<iterator, bool>
379         emplace(_Args&&... __args)
380         { return _M_h.emplace(std::forward<_Args>(__args)...); }
381
382       /**
383        *  @brief Attempts to build and insert a std::pair into the
384        *  %unordered_map.
385        *
386        *  @param  __pos  An iterator that serves as a hint as to where the pair
387        *                should be inserted.
388        *  @param  __args  Arguments used to generate a new pair instance (see
389        *                 std::piecewise_contruct for passing arguments to each
390        *                 part of the pair constructor).
391        *  @return An iterator that points to the element with key of the
392        *          std::pair built from @a __args (may or may not be that
393        *          std::pair).
394        *
395        *  This function is not concerned about whether the insertion took place,
396        *  and thus does not return a boolean like the single-argument emplace()
397        *  does.
398        *  Note that the first parameter is only a hint and can potentially
399        *  improve the performance of the insertion process. A bad hint would
400        *  cause no gains in efficiency.
401        *
402        *  See
403        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
404        *  for more on @a hinting.
405        *
406        *  Insertion requires amortized constant time.
407        */
408       template<typename... _Args>
409         iterator
410         emplace_hint(const_iterator __pos, _Args&&... __args)
411         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
412
413       //@{
414       /**
415        *  @brief Attempts to insert a std::pair into the %unordered_map.
416
417        *  @param __x Pair to be inserted (see std::make_pair for easy
418        *             creation of pairs).
419        *
420        *  @return  A pair, of which the first element is an iterator that 
421        *           points to the possibly inserted pair, and the second is 
422        *           a bool that is true if the pair was actually inserted.
423        *
424        *  This function attempts to insert a (key, value) %pair into the
425        *  %unordered_map. An %unordered_map relies on unique keys and thus a
426        *  %pair is only inserted if its first element (the key) is not already
427        *  present in the %unordered_map.
428        *
429        *  Insertion requires amortized constant time.
430        */
431       std::pair<iterator, bool>
432       insert(const value_type& __x)
433       { return _M_h.insert(__x); }
434
435       template<typename _Pair, typename = typename
436                std::enable_if<std::is_constructible<value_type,
437                                                     _Pair&&>::value>::type>
438         std::pair<iterator, bool>
439         insert(_Pair&& __x)
440         { return _M_h.insert(std::forward<_Pair>(__x)); }
441       //@}
442
443       //@{
444       /**
445        *  @brief Attempts to insert a std::pair into the %unordered_map.
446        *  @param  __hint  An iterator that serves as a hint as to where the
447        *                 pair should be inserted.
448        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
449        *               of pairs).
450        *  @return An iterator that points to the element with key of
451        *           @a __x (may or may not be the %pair passed in).
452        *
453        *  This function is not concerned about whether the insertion took place,
454        *  and thus does not return a boolean like the single-argument insert()
455        *  does.  Note that the first parameter is only a hint and can
456        *  potentially improve the performance of the insertion process.  A bad
457        *  hint would cause no gains in efficiency.
458        *
459        *  See
460        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
461        *  for more on @a hinting.
462        *
463        *  Insertion requires amortized constant time.
464        */
465       iterator
466       insert(const_iterator __hint, const value_type& __x)
467       { return _M_h.insert(__hint, __x); }
468
469       template<typename _Pair, typename = typename
470                std::enable_if<std::is_constructible<value_type,
471                                                     _Pair&&>::value>::type>
472         iterator
473         insert(const_iterator __hint, _Pair&& __x)
474         { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
475       //@}
476
477       /**
478        *  @brief A template function that attempts to insert a range of
479        *  elements.
480        *  @param  __first  Iterator pointing to the start of the range to be
481        *                   inserted.
482        *  @param  __last  Iterator pointing to the end of the range.
483        *
484        *  Complexity similar to that of the range constructor.
485        */
486       template<typename _InputIterator>
487         void
488         insert(_InputIterator __first, _InputIterator __last)
489         { _M_h.insert(__first, __last); }
490
491       /**
492        *  @brief Attempts to insert a list of elements into the %unordered_map.
493        *  @param  __l  A std::initializer_list<value_type> of elements
494        *               to be inserted.
495        *
496        *  Complexity similar to that of the range constructor.
497        */
498       void
499       insert(initializer_list<value_type> __l)
500       { _M_h.insert(__l); }
501
502       //@{
503       /**
504        *  @brief Erases an element from an %unordered_map.
505        *  @param  __position  An iterator pointing to the element to be erased.
506        *  @return An iterator pointing to the element immediately following
507        *          @a __position prior to the element being erased. If no such
508        *          element exists, end() is returned.
509        *
510        *  This function erases an element, pointed to by the given iterator,
511        *  from an %unordered_map.
512        *  Note that this function only erases the element, and that if the
513        *  element is itself a pointer, the pointed-to memory is not touched in
514        *  any way.  Managing the pointer is the user's responsibility.
515        */
516       iterator
517       erase(const_iterator __position)
518       { return _M_h.erase(__position); }
519
520       // LWG 2059.
521       iterator
522       erase(iterator __position)
523       { return _M_h.erase(__position); }
524       //@}
525
526       /**
527        *  @brief Erases elements according to the provided key.
528        *  @param  __x  Key of element to be erased.
529        *  @return  The number of elements erased.
530        *
531        *  This function erases all the elements located by the given key from
532        *  an %unordered_map. For an %unordered_map the result of this function
533        *  can only be 0 (not present) or 1 (present).
534        *  Note that this function only erases the element, and that if the
535        *  element is itself a pointer, the pointed-to memory is not touched in
536        *  any way.  Managing the pointer is the user's responsibility.
537        */
538       size_type
539       erase(const key_type& __x)
540       { return _M_h.erase(__x); }
541
542       /**
543        *  @brief Erases a [__first,__last) range of elements from an
544        *  %unordered_map.
545        *  @param  __first  Iterator pointing to the start of the range to be
546        *                  erased.
547        *  @param __last  Iterator pointing to the end of the range to
548        *                be erased.
549        *  @return The iterator @a __last.
550        *
551        *  This function erases a sequence of elements from an %unordered_map.
552        *  Note that this function only erases the elements, and that if
553        *  the element is itself a pointer, the pointed-to memory is not touched
554        *  in any way.  Managing the pointer is the user's responsibility.
555        */
556       iterator
557       erase(const_iterator __first, const_iterator __last)
558       { return _M_h.erase(__first, __last); }
559
560       /**
561        *  Erases all elements in an %unordered_map.
562        *  Note that this function only erases the elements, and that if the
563        *  elements themselves are pointers, the pointed-to memory is not touched
564        *  in any way.  Managing the pointer is the user's responsibility.
565        */
566       void
567       clear() noexcept
568       { _M_h.clear(); }
569
570       /**
571        *  @brief  Swaps data with another %unordered_map.
572        *  @param  __x  An %unordered_map of the same element and allocator
573        *  types.
574        *
575        *  This exchanges the elements between two %unordered_map in constant
576        *  time.
577        *  Note that the global std::swap() function is specialized such that
578        *  std::swap(m1,m2) will feed to this function.
579        */
580       void
581       swap(unordered_map& __x)
582       noexcept( noexcept(_M_h.swap(__x._M_h)) )
583       { _M_h.swap(__x._M_h); }
584
585       // observers.
586
587       ///  Returns the hash functor object with which the %unordered_map was
588       ///  constructed.
589       hasher
590       hash_function() const
591       { return _M_h.hash_function(); }
592
593       ///  Returns the key comparison object with which the %unordered_map was
594       ///  constructed.
595       key_equal
596       key_eq() const
597       { return _M_h.key_eq(); }
598
599       // lookup.
600
601       //@{
602       /**
603        *  @brief Tries to locate an element in an %unordered_map.
604        *  @param  __x  Key to be located.
605        *  @return  Iterator pointing to sought-after element, or end() if not
606        *           found.
607        *
608        *  This function takes a key and tries to locate the element with which
609        *  the key matches.  If successful the function returns an iterator
610        *  pointing to the sought after element.  If unsuccessful it returns the
611        *  past-the-end ( @c end() ) iterator.
612        */
613       iterator
614       find(const key_type& __x)
615       { return _M_h.find(__x); }
616
617       const_iterator
618       find(const key_type& __x) const
619       { return _M_h.find(__x); }
620       //@}
621
622       /**
623        *  @brief  Finds the number of elements.
624        *  @param  __x  Key to count.
625        *  @return  Number of elements with specified key.
626        *
627        *  This function only makes sense for %unordered_multimap; for
628        *  %unordered_map the result will either be 0 (not present) or 1
629        *  (present).
630        */
631       size_type
632       count(const key_type& __x) const
633       { return _M_h.count(__x); }
634
635       //@{
636       /**
637        *  @brief Finds a subsequence matching given key.
638        *  @param  __x  Key to be located.
639        *  @return  Pair of iterators that possibly points to the subsequence
640        *           matching given key.
641        *
642        *  This function probably only makes sense for %unordered_multimap.
643        */
644       std::pair<iterator, iterator>
645       equal_range(const key_type& __x)
646       { return _M_h.equal_range(__x); }
647
648       std::pair<const_iterator, const_iterator>
649       equal_range(const key_type& __x) const
650       { return _M_h.equal_range(__x); }
651       //@}
652
653       //@{
654       /**
655        *  @brief  Subscript ( @c [] ) access to %unordered_map data.
656        *  @param  __k  The key for which data should be retrieved.
657        *  @return  A reference to the data of the (key,data) %pair.
658        *
659        *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
660        *  data associated with the key specified in subscript.  If the key does
661        *  not exist, a pair with that key is created using default values, which
662        *  is then returned.
663        *
664        *  Lookup requires constant time.
665        */
666       mapped_type&
667       operator[](const key_type& __k)
668       { return _M_h[__k]; }
669
670       mapped_type&
671       operator[](key_type&& __k)
672       { return _M_h[std::move(__k)]; }
673       //@}
674
675       //@{
676       /**
677        *  @brief  Access to %unordered_map data.
678        *  @param  __k  The key for which data should be retrieved.
679        *  @return  A reference to the data whose key is equal to @a __k, if
680        *           such a data is present in the %unordered_map.
681        *  @throw  std::out_of_range  If no such data is present.
682        */
683       mapped_type&
684       at(const key_type& __k)
685       { return _M_h.at(__k); }
686
687       const mapped_type&
688       at(const key_type& __k) const
689       { return _M_h.at(__k); }
690       //@}
691
692       // bucket interface.
693
694       /// Returns the number of buckets of the %unordered_map.
695       size_type
696       bucket_count() const noexcept
697       { return _M_h.bucket_count(); }
698
699       /// Returns the maximum number of buckets of the %unordered_map.
700       size_type
701       max_bucket_count() const noexcept
702       { return _M_h.max_bucket_count(); }
703
704       /*
705        * @brief  Returns the number of elements in a given bucket.
706        * @param  __n  A bucket index.
707        * @return  The number of elements in the bucket.
708        */
709       size_type
710       bucket_size(size_type __n) const
711       { return _M_h.bucket_size(__n); }
712
713       /*
714        * @brief  Returns the bucket index of a given element.
715        * @param  __key  A key instance.
716        * @return  The key bucket index.
717        */
718       size_type
719       bucket(const key_type& __key) const
720       { return _M_h.bucket(__key); }
721       
722       /**
723        *  @brief  Returns a read/write iterator pointing to the first bucket
724        *         element.
725        *  @param  __n The bucket index.
726        *  @return  A read/write local iterator.
727        */
728       local_iterator
729       begin(size_type __n)
730       { return _M_h.begin(__n); }
731
732       //@{
733       /**
734        *  @brief  Returns a read-only (constant) iterator pointing to the first
735        *         bucket element.
736        *  @param  __n The bucket index.
737        *  @return  A read-only local iterator.
738        */
739       const_local_iterator
740       begin(size_type __n) const
741       { return _M_h.begin(__n); }
742
743       const_local_iterator
744       cbegin(size_type __n) const
745       { return _M_h.cbegin(__n); }
746       //@}
747
748       /**
749        *  @brief  Returns a read/write iterator pointing to one past the last
750        *         bucket elements.
751        *  @param  __n The bucket index.
752        *  @return  A read/write local iterator.
753        */
754       local_iterator
755       end(size_type __n)
756       { return _M_h.end(__n); }
757
758       //@{
759       /**
760        *  @brief  Returns a read-only (constant) iterator pointing to one past
761        *         the last bucket elements.
762        *  @param  __n The bucket index.
763        *  @return  A read-only local iterator.
764        */
765       const_local_iterator
766       end(size_type __n) const
767       { return _M_h.end(__n); }
768
769       const_local_iterator
770       cend(size_type __n) const
771       { return _M_h.cend(__n); }
772       //@}
773
774       // hash policy.
775
776       /// Returns the average number of elements per bucket.
777       float
778       load_factor() const noexcept
779       { return _M_h.load_factor(); }
780
781       /// Returns a positive number that the %unordered_map tries to keep the
782       /// load factor less than or equal to.
783       float
784       max_load_factor() const noexcept
785       { return _M_h.max_load_factor(); }
786
787       /**
788        *  @brief  Change the %unordered_map maximum load factor.
789        *  @param  __z The new maximum load factor.
790        */
791       void
792       max_load_factor(float __z)
793       { _M_h.max_load_factor(__z); }
794
795       /**
796        *  @brief  May rehash the %unordered_map.
797        *  @param  __n The new number of buckets.
798        *
799        *  Rehash will occur only if the new number of buckets respect the
800        *  %unordered_map maximum load factor.
801        */
802       void
803       rehash(size_type __n)
804       { _M_h.rehash(__n); }
805
806       /**
807        *  @brief  Prepare the %unordered_map for a specified number of
808        *          elements.
809        *  @param  __n Number of elements required.
810        *
811        *  Same as rehash(ceil(n / max_load_factor())).
812        */
813       void
814       reserve(size_type __n)
815       { _M_h.reserve(__n); }
816
817       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
818                typename _Alloc1>
819         friend bool
820       operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
821                  const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
822     };
823
824   /**
825    *  @brief A standard container composed of equivalent keys
826    *  (possibly containing multiple of each key value) that associates
827    *  values of another type with the keys.
828    *
829    *  @ingroup unordered_associative_containers
830    *
831    *  @tparam  _Key    Type of key objects.
832    *  @tparam  _Tp     Type of mapped objects.
833    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
834    *  @tparam  _Pred   Predicate function object type, defaults
835    *                   to equal_to<_Value>.
836    *  @tparam  _Alloc  Allocator type, defaults to
837    *                   std::allocator<std::pair<const _Key, _Tp>>.
838    *
839    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
840    *  <a href="tables.html#xx">unordered associative container</a>
841    *
842    * The resulting value type of the container is std::pair<const _Key, _Tp>.
843    *
844    *  Base is _Hashtable, dispatched at compile time via template
845    *  alias __ummap_hashtable.
846    */
847   template<class _Key, class _Tp,
848            class _Hash = hash<_Key>,
849            class _Pred = std::equal_to<_Key>,
850            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
851     class unordered_multimap
852     {
853       typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
854       _Hashtable _M_h;
855
856     public:
857       // typedefs:
858       //@{
859       /// Public typedefs.
860       typedef typename _Hashtable::key_type     key_type;
861       typedef typename _Hashtable::value_type   value_type;
862       typedef typename _Hashtable::mapped_type  mapped_type;
863       typedef typename _Hashtable::hasher       hasher;
864       typedef typename _Hashtable::key_equal    key_equal;
865       typedef typename _Hashtable::allocator_type allocator_type;
866       //@}
867
868       //@{
869       ///  Iterator-related typedefs.
870       typedef typename _Hashtable::pointer              pointer;
871       typedef typename _Hashtable::const_pointer        const_pointer;
872       typedef typename _Hashtable::reference            reference;
873       typedef typename _Hashtable::const_reference      const_reference;
874       typedef typename _Hashtable::iterator             iterator;
875       typedef typename _Hashtable::const_iterator       const_iterator;
876       typedef typename _Hashtable::local_iterator       local_iterator;
877       typedef typename _Hashtable::const_local_iterator const_local_iterator;
878       typedef typename _Hashtable::size_type            size_type;
879       typedef typename _Hashtable::difference_type      difference_type;
880       //@}
881
882       //construct/destroy/copy
883
884       /// Default constructor.
885       unordered_multimap() = default;
886
887       /**
888        *  @brief  Default constructor creates no elements.
889        *  @param __n  Mnimal initial number of buckets.
890        *  @param __hf  A hash functor.
891        *  @param __eql  A key equality functor.
892        *  @param __a  An allocator object.
893        */
894       explicit
895       unordered_multimap(size_type __n,
896                          const hasher& __hf = hasher(),
897                          const key_equal& __eql = key_equal(),
898                          const allocator_type& __a = allocator_type())
899       : _M_h(__n, __hf, __eql, __a)
900       { }
901
902       /**
903        *  @brief  Builds an %unordered_multimap from a range.
904        *  @param  __first An input iterator.
905        *  @param  __last  An input iterator.
906        *  @param __n      Minimal initial number of buckets.
907        *  @param __hf     A hash functor.
908        *  @param __eql    A key equality functor.
909        *  @param __a      An allocator object.
910        *
911        *  Create an %unordered_multimap consisting of copies of the elements
912        *  from [__first,__last).  This is linear in N (where N is
913        *  distance(__first,__last)).
914        */
915       template<typename _InputIterator>
916         unordered_multimap(_InputIterator __first, _InputIterator __last,
917                            size_type __n = 0,
918                            const hasher& __hf = hasher(),
919                            const key_equal& __eql = key_equal(),
920                            const allocator_type& __a = allocator_type())
921         : _M_h(__first, __last, __n, __hf, __eql, __a)
922         { }
923
924       /// Copy constructor.
925       unordered_multimap(const unordered_multimap&) = default;
926
927       /// Move constructor.
928       unordered_multimap(unordered_multimap&&) = default;
929
930       /**
931        *  @brief Creates an %unordered_multimap with no elements.
932        *  @param __a An allocator object.
933        */
934       explicit
935       unordered_multimap(const allocator_type& __a)
936       : _M_h(__a)
937       { }
938
939       /*
940        *  @brief Copy constructor with allocator argument.
941        * @param  __uset  Input %unordered_multimap to copy.
942        * @param  __a  An allocator object.
943        */
944       unordered_multimap(const unordered_multimap& __ummap,
945                          const allocator_type& __a)
946       : _M_h(__ummap._M_h, __a)
947       { }
948
949       /*
950        *  @brief  Move constructor with allocator argument.
951        *  @param  __uset Input %unordered_multimap to move.
952        *  @param  __a    An allocator object.
953        */
954       unordered_multimap(unordered_multimap&& __ummap,
955                          const allocator_type& __a)
956       : _M_h(std::move(__ummap._M_h), __a)
957       { }
958
959       /**
960        *  @brief  Builds an %unordered_multimap from an initializer_list.
961        *  @param  __l  An initializer_list.
962        *  @param __n  Minimal initial number of buckets.
963        *  @param __hf  A hash functor.
964        *  @param __eql  A key equality functor.
965        *  @param  __a  An allocator object.
966        *
967        *  Create an %unordered_multimap consisting of copies of the elements in
968        *  the list. This is linear in N (where N is @a __l.size()).
969        */
970       unordered_multimap(initializer_list<value_type> __l,
971                          size_type __n = 0,
972                          const hasher& __hf = hasher(),
973                          const key_equal& __eql = key_equal(),
974                          const allocator_type& __a = allocator_type())
975       : _M_h(__l, __n, __hf, __eql, __a)
976       { }
977
978       unordered_multimap(size_type __n, const allocator_type& __a)
979       : unordered_multimap(__n, hasher(), key_equal(), __a)
980       { }
981
982       unordered_multimap(size_type __n, const hasher& __hf,
983                          const allocator_type& __a)
984       : unordered_multimap(__n, __hf, key_equal(), __a)
985       { }
986
987       template<typename _InputIterator>
988         unordered_multimap(_InputIterator __first, _InputIterator __last,
989                            size_type __n,
990                            const allocator_type& __a)
991         : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
992         { }
993
994       template<typename _InputIterator>
995         unordered_multimap(_InputIterator __first, _InputIterator __last,
996                            size_type __n, const hasher& __hf,
997                            const allocator_type& __a)
998         : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
999         { }
1000
1001       unordered_multimap(initializer_list<value_type> __l,
1002                          size_type __n,
1003                          const allocator_type& __a)
1004       : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1005       { }
1006
1007       unordered_multimap(initializer_list<value_type> __l,
1008                          size_type __n, const hasher& __hf,
1009                          const allocator_type& __a)
1010       : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1011       { }
1012
1013       /// Copy assignment operator.
1014       unordered_multimap&
1015       operator=(const unordered_multimap&) = default;
1016
1017       /// Move assignment operator.
1018       unordered_multimap&
1019       operator=(unordered_multimap&&) = default;
1020
1021       /**
1022        *  @brief  %Unordered_multimap list assignment operator.
1023        *  @param  __l  An initializer_list.
1024        *
1025        *  This function fills an %unordered_multimap with copies of the elements
1026        *  in the initializer list @a __l.
1027        *
1028        *  Note that the assignment completely changes the %unordered_multimap
1029        *  and that the resulting %unordered_multimap's size is the same as the
1030        *  number of elements assigned.  Old data may be lost.
1031        */
1032       unordered_multimap&
1033       operator=(initializer_list<value_type> __l)
1034       {
1035         _M_h = __l;
1036         return *this;
1037       }
1038
1039       ///  Returns the allocator object with which the %unordered_multimap was
1040       ///  constructed.
1041       allocator_type
1042       get_allocator() const noexcept
1043       { return _M_h.get_allocator(); }
1044
1045       // size and capacity:
1046
1047       ///  Returns true if the %unordered_multimap is empty.
1048       bool
1049       empty() const noexcept
1050       { return _M_h.empty(); }
1051
1052       ///  Returns the size of the %unordered_multimap.
1053       size_type
1054       size() const noexcept
1055       { return _M_h.size(); }
1056
1057       ///  Returns the maximum size of the %unordered_multimap.
1058       size_type
1059       max_size() const noexcept
1060       { return _M_h.max_size(); }
1061
1062       // iterators.
1063
1064       /**
1065        *  Returns a read/write iterator that points to the first element in the
1066        *  %unordered_multimap.
1067        */
1068       iterator
1069       begin() noexcept
1070       { return _M_h.begin(); }
1071
1072       //@{
1073       /**
1074        *  Returns a read-only (constant) iterator that points to the first
1075        *  element in the %unordered_multimap.
1076        */
1077       const_iterator
1078       begin() const noexcept
1079       { return _M_h.begin(); }
1080
1081       const_iterator
1082       cbegin() const noexcept
1083       { return _M_h.begin(); }
1084       //@}
1085
1086       /**
1087        *  Returns a read/write iterator that points one past the last element in
1088        *  the %unordered_multimap.
1089        */
1090       iterator
1091       end() noexcept
1092       { return _M_h.end(); }
1093
1094       //@{
1095       /**
1096        *  Returns a read-only (constant) iterator that points one past the last
1097        *  element in the %unordered_multimap.
1098        */
1099       const_iterator
1100       end() const noexcept
1101       { return _M_h.end(); }
1102
1103       const_iterator
1104       cend() const noexcept
1105       { return _M_h.end(); }
1106       //@}
1107
1108       // modifiers.
1109
1110       /**
1111        *  @brief Attempts to build and insert a std::pair into the
1112        *  %unordered_multimap.
1113        *
1114        *  @param __args  Arguments used to generate a new pair instance (see
1115        *                std::piecewise_contruct for passing arguments to each
1116        *                part of the pair constructor).
1117        *
1118        *  @return  An iterator that points to the inserted pair.
1119        *
1120        *  This function attempts to build and insert a (key, value) %pair into
1121        *  the %unordered_multimap.
1122        *
1123        *  Insertion requires amortized constant time.
1124        */
1125       template<typename... _Args>
1126         iterator
1127         emplace(_Args&&... __args)
1128         { return _M_h.emplace(std::forward<_Args>(__args)...); }
1129
1130       /**
1131        *  @brief Attempts to build and insert a std::pair into the
1132        *  %unordered_multimap.
1133        *
1134        *  @param  __pos  An iterator that serves as a hint as to where the pair
1135        *                should be inserted.
1136        *  @param  __args  Arguments used to generate a new pair instance (see
1137        *                 std::piecewise_contruct for passing arguments to each
1138        *                 part of the pair constructor).
1139        *  @return An iterator that points to the element with key of the
1140        *          std::pair built from @a __args.
1141        *
1142        *  Note that the first parameter is only a hint and can potentially
1143        *  improve the performance of the insertion process. A bad hint would
1144        *  cause no gains in efficiency.
1145        *
1146        *  See
1147        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1148        *  for more on @a hinting.
1149        *
1150        *  Insertion requires amortized constant time.
1151        */
1152       template<typename... _Args>
1153         iterator
1154         emplace_hint(const_iterator __pos, _Args&&... __args)
1155         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1156
1157       //@{
1158       /**
1159        *  @brief Inserts a std::pair into the %unordered_multimap.
1160        *  @param __x Pair to be inserted (see std::make_pair for easy
1161        *             creation of pairs).
1162        *
1163        *  @return  An iterator that points to the inserted pair.
1164        *
1165        *  Insertion requires amortized constant time.
1166        */
1167       iterator
1168       insert(const value_type& __x)
1169       { return _M_h.insert(__x); }
1170
1171       template<typename _Pair, typename = typename
1172                std::enable_if<std::is_constructible<value_type,
1173                                                     _Pair&&>::value>::type>
1174         iterator
1175         insert(_Pair&& __x)
1176         { return _M_h.insert(std::forward<_Pair>(__x)); }
1177       //@}
1178
1179       //@{
1180       /**
1181        *  @brief Inserts a std::pair into the %unordered_multimap.
1182        *  @param  __hint  An iterator that serves as a hint as to where the
1183        *                 pair should be inserted.
1184        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
1185        *               of pairs).
1186        *  @return An iterator that points to the element with key of
1187        *           @a __x (may or may not be the %pair passed in).
1188        *
1189        *  Note that the first parameter is only a hint and can potentially
1190        *  improve the performance of the insertion process.  A bad hint would
1191        *  cause no gains in efficiency.
1192        *
1193        *  See
1194        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1195        *  for more on @a hinting.
1196        *
1197        *  Insertion requires amortized constant time.
1198        */
1199       iterator
1200       insert(const_iterator __hint, const value_type& __x)
1201       { return _M_h.insert(__hint, __x); }
1202
1203       template<typename _Pair, typename = typename
1204                std::enable_if<std::is_constructible<value_type,
1205                                                     _Pair&&>::value>::type>
1206         iterator
1207         insert(const_iterator __hint, _Pair&& __x)
1208         { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
1209       //@}
1210
1211       /**
1212        *  @brief A template function that attempts to insert a range of
1213        *  elements.
1214        *  @param  __first  Iterator pointing to the start of the range to be
1215        *                   inserted.
1216        *  @param  __last  Iterator pointing to the end of the range.
1217        *
1218        *  Complexity similar to that of the range constructor.
1219        */
1220       template<typename _InputIterator>
1221         void
1222         insert(_InputIterator __first, _InputIterator __last)
1223         { _M_h.insert(__first, __last); }
1224
1225       /**
1226        *  @brief Attempts to insert a list of elements into the
1227        *  %unordered_multimap.
1228        *  @param  __l  A std::initializer_list<value_type> of elements
1229        *               to be inserted.
1230        *
1231        *  Complexity similar to that of the range constructor.
1232        */
1233       void
1234       insert(initializer_list<value_type> __l)
1235       { _M_h.insert(__l); }
1236
1237       //@{
1238       /**
1239        *  @brief Erases an element from an %unordered_multimap.
1240        *  @param  __position  An iterator pointing to the element to be erased.
1241        *  @return An iterator pointing to the element immediately following
1242        *          @a __position prior to the element being erased. If no such
1243        *          element exists, end() is returned.
1244        *
1245        *  This function erases an element, pointed to by the given iterator,
1246        *  from an %unordered_multimap.
1247        *  Note that this function only erases the element, and that if the
1248        *  element is itself a pointer, the pointed-to memory is not touched in
1249        *  any way.  Managing the pointer is the user's responsibility.
1250        */
1251       iterator
1252       erase(const_iterator __position)
1253       { return _M_h.erase(__position); }
1254
1255       // LWG 2059.
1256       iterator
1257       erase(iterator __position)
1258       { return _M_h.erase(__position); }
1259       //@}
1260
1261       /**
1262        *  @brief Erases elements according to the provided key.
1263        *  @param  __x  Key of elements to be erased.
1264        *  @return  The number of elements erased.
1265        *
1266        *  This function erases all the elements located by the given key from
1267        *  an %unordered_multimap.
1268        *  Note that this function only erases the element, and that if the
1269        *  element is itself a pointer, the pointed-to memory is not touched in
1270        *  any way.  Managing the pointer is the user's responsibility.
1271        */
1272       size_type
1273       erase(const key_type& __x)
1274       { return _M_h.erase(__x); }
1275
1276       /**
1277        *  @brief Erases a [__first,__last) range of elements from an
1278        *  %unordered_multimap.
1279        *  @param  __first  Iterator pointing to the start of the range to be
1280        *                  erased.
1281        *  @param __last  Iterator pointing to the end of the range to
1282        *                be erased.
1283        *  @return The iterator @a __last.
1284        *
1285        *  This function erases a sequence of elements from an
1286        *  %unordered_multimap.
1287        *  Note that this function only erases the elements, and that if
1288        *  the element is itself a pointer, the pointed-to memory is not touched
1289        *  in any way.  Managing the pointer is the user's responsibility.
1290        */
1291       iterator
1292       erase(const_iterator __first, const_iterator __last)
1293       { return _M_h.erase(__first, __last); }
1294
1295       /**
1296        *  Erases all elements in an %unordered_multimap.
1297        *  Note that this function only erases the elements, and that if the
1298        *  elements themselves are pointers, the pointed-to memory is not touched
1299        *  in any way.  Managing the pointer is the user's responsibility.
1300        */
1301       void
1302       clear() noexcept
1303       { _M_h.clear(); }
1304
1305       /**
1306        *  @brief  Swaps data with another %unordered_multimap.
1307        *  @param  __x  An %unordered_multimap of the same element and allocator
1308        *  types.
1309        *
1310        *  This exchanges the elements between two %unordered_multimap in
1311        *  constant time.
1312        *  Note that the global std::swap() function is specialized such that
1313        *  std::swap(m1,m2) will feed to this function.
1314        */
1315       void
1316       swap(unordered_multimap& __x)
1317       noexcept( noexcept(_M_h.swap(__x._M_h)) )
1318       { _M_h.swap(__x._M_h); }
1319
1320       // observers.
1321
1322       ///  Returns the hash functor object with which the %unordered_multimap
1323       ///  was constructed.
1324       hasher
1325       hash_function() const
1326       { return _M_h.hash_function(); }
1327
1328       ///  Returns the key comparison object with which the %unordered_multimap
1329       ///  was constructed.
1330       key_equal
1331       key_eq() const
1332       { return _M_h.key_eq(); }
1333
1334       // lookup.
1335
1336       //@{
1337       /**
1338        *  @brief Tries to locate an element in an %unordered_multimap.
1339        *  @param  __x  Key to be located.
1340        *  @return  Iterator pointing to sought-after element, or end() if not
1341        *           found.
1342        *
1343        *  This function takes a key and tries to locate the element with which
1344        *  the key matches.  If successful the function returns an iterator
1345        *  pointing to the sought after element.  If unsuccessful it returns the
1346        *  past-the-end ( @c end() ) iterator.
1347        */
1348       iterator
1349       find(const key_type& __x)
1350       { return _M_h.find(__x); }
1351
1352       const_iterator
1353       find(const key_type& __x) const
1354       { return _M_h.find(__x); }
1355       //@}
1356
1357       /**
1358        *  @brief  Finds the number of elements.
1359        *  @param  __x  Key to count.
1360        *  @return  Number of elements with specified key.
1361        */
1362       size_type
1363       count(const key_type& __x) const
1364       { return _M_h.count(__x); }
1365
1366       //@{
1367       /**
1368        *  @brief Finds a subsequence matching given key.
1369        *  @param  __x  Key to be located.
1370        *  @return  Pair of iterators that possibly points to the subsequence
1371        *           matching given key.
1372        */
1373       std::pair<iterator, iterator>
1374       equal_range(const key_type& __x)
1375       { return _M_h.equal_range(__x); }
1376
1377       std::pair<const_iterator, const_iterator>
1378       equal_range(const key_type& __x) const
1379       { return _M_h.equal_range(__x); }
1380       //@}
1381
1382       // bucket interface.
1383
1384       /// Returns the number of buckets of the %unordered_multimap.
1385       size_type
1386       bucket_count() const noexcept
1387       { return _M_h.bucket_count(); }
1388
1389       /// Returns the maximum number of buckets of the %unordered_multimap.
1390       size_type
1391       max_bucket_count() const noexcept
1392       { return _M_h.max_bucket_count(); }
1393
1394       /*
1395        * @brief  Returns the number of elements in a given bucket.
1396        * @param  __n  A bucket index.
1397        * @return  The number of elements in the bucket.
1398        */
1399       size_type
1400       bucket_size(size_type __n) const
1401       { return _M_h.bucket_size(__n); }
1402
1403       /*
1404        * @brief  Returns the bucket index of a given element.
1405        * @param  __key  A key instance.
1406        * @return  The key bucket index.
1407        */
1408       size_type
1409       bucket(const key_type& __key) const
1410       { return _M_h.bucket(__key); }
1411       
1412       /**
1413        *  @brief  Returns a read/write iterator pointing to the first bucket
1414        *         element.
1415        *  @param  __n The bucket index.
1416        *  @return  A read/write local iterator.
1417        */
1418       local_iterator
1419       begin(size_type __n)
1420       { return _M_h.begin(__n); }
1421
1422       //@{
1423       /**
1424        *  @brief  Returns a read-only (constant) iterator pointing to the first
1425        *         bucket element.
1426        *  @param  __n The bucket index.
1427        *  @return  A read-only local iterator.
1428        */
1429       const_local_iterator
1430       begin(size_type __n) const
1431       { return _M_h.begin(__n); }
1432
1433       const_local_iterator
1434       cbegin(size_type __n) const
1435       { return _M_h.cbegin(__n); }
1436       //@}
1437
1438       /**
1439        *  @brief  Returns a read/write iterator pointing to one past the last
1440        *         bucket elements.
1441        *  @param  __n The bucket index.
1442        *  @return  A read/write local iterator.
1443        */
1444       local_iterator
1445       end(size_type __n)
1446       { return _M_h.end(__n); }
1447
1448       //@{
1449       /**
1450        *  @brief  Returns a read-only (constant) iterator pointing to one past
1451        *         the last bucket elements.
1452        *  @param  __n The bucket index.
1453        *  @return  A read-only local iterator.
1454        */
1455       const_local_iterator
1456       end(size_type __n) const
1457       { return _M_h.end(__n); }
1458
1459       const_local_iterator
1460       cend(size_type __n) const
1461       { return _M_h.cend(__n); }
1462       //@}
1463
1464       // hash policy.
1465
1466       /// Returns the average number of elements per bucket.
1467       float
1468       load_factor() const noexcept
1469       { return _M_h.load_factor(); }
1470
1471       /// Returns a positive number that the %unordered_multimap tries to keep
1472       /// the load factor less than or equal to.
1473       float
1474       max_load_factor() const noexcept
1475       { return _M_h.max_load_factor(); }
1476
1477       /**
1478        *  @brief  Change the %unordered_multimap maximum load factor.
1479        *  @param  __z The new maximum load factor.
1480        */
1481       void
1482       max_load_factor(float __z)
1483       { _M_h.max_load_factor(__z); }
1484
1485       /**
1486        *  @brief  May rehash the %unordered_multimap.
1487        *  @param  __n The new number of buckets.
1488        *
1489        *  Rehash will occur only if the new number of buckets respect the
1490        *  %unordered_multimap maximum load factor.
1491        */
1492       void
1493       rehash(size_type __n)
1494       { _M_h.rehash(__n); }
1495
1496       /**
1497        *  @brief  Prepare the %unordered_multimap for a specified number of
1498        *          elements.
1499        *  @param  __n Number of elements required.
1500        *
1501        *  Same as rehash(ceil(n / max_load_factor())).
1502        */
1503       void
1504       reserve(size_type __n)
1505       { _M_h.reserve(__n); }
1506
1507       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
1508                typename _Alloc1>
1509         friend bool
1510         operator==(const unordered_multimap<_Key1, _Tp1,
1511                                             _Hash1, _Pred1, _Alloc1>&,
1512                    const unordered_multimap<_Key1, _Tp1,
1513                                             _Hash1, _Pred1, _Alloc1>&);
1514     };
1515
1516   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1517     inline void
1518     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1519          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1520     { __x.swap(__y); }
1521
1522   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1523     inline void
1524     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1525          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1526     { __x.swap(__y); }
1527
1528   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1529     inline bool
1530     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1531                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1532     { return __x._M_h._M_equal(__y._M_h); }
1533
1534   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1535     inline bool
1536     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1537                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1538     { return !(__x == __y); }
1539
1540   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1541     inline bool
1542     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1543                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1544     { return __x._M_h._M_equal(__y._M_h); }
1545
1546   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1547     inline bool
1548     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1549                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1550     { return !(__x == __y); }
1551
1552 _GLIBCXX_END_NAMESPACE_CONTAINER
1553 } // namespace std
1554
1555 #endif /* _UNORDERED_MAP_H */