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