libstdc++
unordered_set.h
Go to the documentation of this file.
00001 // unordered_set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/unordered_set.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{unordered_set}
00028  */
00029 
00030 #ifndef _UNORDERED_SET_H
00031 #define _UNORDERED_SET_H
00032 
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00036 
00037   /// Base types for unordered_set.
00038   template<bool _Cache>
00039     using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
00040 
00041   template<typename _Value,
00042        typename _Hash = hash<_Value>,
00043        typename _Pred = std::equal_to<_Value>,
00044        typename _Alloc = std::allocator<_Value>,
00045        typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
00046     using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
00047                     __detail::_Identity, _Pred, _Hash,
00048                     __detail::_Mod_range_hashing,
00049                     __detail::_Default_ranged_hash,
00050                     __detail::_Prime_rehash_policy, _Tr>;
00051 
00052   /// Base types for unordered_multiset.
00053   template<bool _Cache>
00054     using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
00055 
00056   template<typename _Value,
00057        typename _Hash = hash<_Value>,
00058        typename _Pred = std::equal_to<_Value>,
00059        typename _Alloc = std::allocator<_Value>,
00060        typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
00061     using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
00062                      __detail::_Identity,
00063                      _Pred, _Hash,
00064                      __detail::_Mod_range_hashing,
00065                      __detail::_Default_ranged_hash,
00066                      __detail::_Prime_rehash_policy, _Tr>;
00067 
00068   /**
00069    *  @brief A standard container composed of unique keys (containing
00070    *  at most one of each key value) in which the elements' keys are
00071    *  the elements themselves.
00072    *
00073    *  @ingroup unordered_associative_containers
00074    *
00075    *  @tparam  _Value  Type of key objects.
00076    *  @tparam  _Hash  Hashing function object type, defaults to hash<_Value>.
00077 
00078    *  @tparam _Pred Predicate function object type, defaults to
00079    *                equal_to<_Value>.
00080    *
00081    *  @tparam  _Alloc  Allocator type, defaults to allocator<_Key>.
00082    *
00083    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00084    *  <a href="tables.html#xx">unordered associative container</a>
00085    *
00086    *  Base is _Hashtable, dispatched at compile time via template
00087    *  alias __uset_hashtable.
00088    */
00089   template<class _Value,
00090        class _Hash = hash<_Value>,
00091        class _Pred = std::equal_to<_Value>,
00092        class _Alloc = std::allocator<_Value> >
00093     class unordered_set : __check_copy_constructible<_Alloc>
00094     {
00095       typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
00096       _Hashtable _M_h;
00097 
00098     public:
00099       // typedefs:
00100       //@{
00101       /// Public typedefs.
00102       typedef typename _Hashtable::key_type key_type;
00103       typedef typename _Hashtable::value_type   value_type;
00104       typedef typename _Hashtable::hasher   hasher;
00105       typedef typename _Hashtable::key_equal    key_equal;
00106       typedef typename _Hashtable::allocator_type allocator_type;
00107       //@}
00108 
00109       //@{
00110       ///  Iterator-related typedefs.
00111       typedef typename allocator_type::pointer      pointer;
00112       typedef typename allocator_type::const_pointer    const_pointer;
00113       typedef typename allocator_type::reference    reference;
00114       typedef typename allocator_type::const_reference  const_reference;
00115       typedef typename _Hashtable::iterator     iterator;
00116       typedef typename _Hashtable::const_iterator   const_iterator;
00117       typedef typename _Hashtable::local_iterator   local_iterator;
00118       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00119       typedef typename _Hashtable::size_type        size_type;
00120       typedef typename _Hashtable::difference_type  difference_type;
00121       //@}
00122 
00123       // construct/destroy/copy
00124       /**
00125        *  @brief  Default constructor creates no elements.
00126        *  @param __n  Initial number of buckets.
00127        *  @param __hf  A hash functor.
00128        *  @param __eql  A key equality functor.
00129        *  @param __a  An allocator object.
00130        */
00131       explicit
00132       unordered_set(size_type __n = 10,
00133             const hasher& __hf = hasher(),
00134             const key_equal& __eql = key_equal(),
00135             const allocator_type& __a = allocator_type())
00136       : _M_h(__n, __hf, __eql, __a)
00137       { }
00138 
00139       /**
00140        *  @brief  Builds an %unordered_set from a range.
00141        *  @param  __first  An input iterator.
00142        *  @param  __last  An input iterator.
00143        *  @param __n  Minimal initial number of buckets.
00144        *  @param __hf  A hash functor.
00145        *  @param __eql  A key equality functor.
00146        *  @param __a  An allocator object.
00147        *
00148        *  Create an %unordered_set consisting of copies of the elements from
00149        *  [__first,__last).  This is linear in N (where N is
00150        *  distance(__first,__last)).
00151        */
00152       template<typename _InputIterator>
00153     unordered_set(_InputIterator __f, _InputIterator __l,
00154               size_type __n = 0,
00155               const hasher& __hf = hasher(),
00156               const key_equal& __eql = key_equal(),
00157               const allocator_type& __a = allocator_type())
00158     : _M_h(__f, __l, __n, __hf, __eql, __a)
00159     { }
00160 
00161       /// Copy constructor.
00162       unordered_set(const unordered_set&) = default;
00163 
00164       /// Move constructor.
00165       unordered_set(unordered_set&&) = default;
00166 
00167       /**
00168        *  @brief  Builds an %unordered_set from an initializer_list.
00169        *  @param  __l  An initializer_list.
00170        *  @param __n  Minimal initial number of buckets.
00171        *  @param __hf  A hash functor.
00172        *  @param __eql  A key equality functor.
00173        *  @param  __a  An allocator object.
00174        *
00175        *  Create an %unordered_set consisting of copies of the elements in the
00176        *  list. This is linear in N (where N is @a __l.size()).
00177        */
00178       unordered_set(initializer_list<value_type> __l,
00179             size_type __n = 0,
00180             const hasher& __hf = hasher(),
00181             const key_equal& __eql = key_equal(),
00182             const allocator_type& __a = allocator_type())
00183     : _M_h(__l, __n, __hf, __eql, __a)
00184       { }
00185 
00186       /// Copy assignment operator.
00187       unordered_set&
00188       operator=(const unordered_set&) = default;
00189 
00190       /// Move assignment operator.
00191       unordered_set&
00192       operator=(unordered_set&&) = default;
00193 
00194       /**
00195        *  @brief  %Unordered_set list assignment operator.
00196        *  @param  __l  An initializer_list.
00197        *
00198        *  This function fills an %unordered_set with copies of the elements in
00199        *  the initializer list @a __l.
00200        *
00201        *  Note that the assignment completely changes the %unordered_set and
00202        *  that the resulting %unordered_set's size is the same as the number
00203        *  of elements assigned.  Old data may be lost.
00204        */
00205       unordered_set&
00206       operator=(initializer_list<value_type> __l)
00207       {
00208     _M_h = __l;
00209     return *this;
00210       }
00211 
00212       ///  Returns the allocator object with which the %unordered_set was
00213       ///  constructed.
00214       allocator_type
00215       get_allocator() const noexcept
00216       { return _M_h.get_allocator(); }
00217 
00218       // size and capacity:
00219 
00220       ///  Returns true if the %unordered_set is empty.
00221       bool
00222       empty() const noexcept
00223       { return _M_h.empty(); }
00224 
00225       ///  Returns the size of the %unordered_set.
00226       size_type
00227       size() const noexcept
00228       { return _M_h.size(); }
00229 
00230       ///  Returns the maximum size of the %unordered_set.
00231       size_type
00232       max_size() const noexcept
00233       { return _M_h.max_size(); }
00234 
00235       // iterators.
00236 
00237       //@{
00238       /**
00239        *  Returns a read-only (constant) iterator that points to the first
00240        *  element in the %unordered_set.
00241        */
00242       iterator
00243       begin() noexcept
00244       { return _M_h.begin(); }
00245 
00246       const_iterator
00247       begin() const noexcept
00248       { return _M_h.begin(); }
00249       //@}
00250 
00251       //@{
00252       /**
00253        *  Returns a read-only (constant) iterator that points one past the last
00254        *  element in the %unordered_set.
00255        */
00256       iterator
00257       end() noexcept
00258       { return _M_h.end(); }
00259 
00260       const_iterator
00261       end() const noexcept
00262       { return _M_h.end(); }
00263       //@}
00264 
00265       /**
00266        *  Returns a read-only (constant) iterator that points to the first
00267        *  element in the %unordered_set.
00268        */
00269       const_iterator
00270       cbegin() const noexcept
00271       { return _M_h.begin(); }
00272 
00273       /**
00274        *  Returns a read-only (constant) iterator that points one past the last
00275        *  element in the %unordered_set.
00276        */
00277       const_iterator
00278       cend() const noexcept
00279       { return _M_h.end(); }
00280 
00281       // modifiers.
00282 
00283       /**
00284        *  @brief Attempts to build and insert an element into the
00285        *  %unordered_set.
00286        *  @param __args  Arguments used to generate an element.
00287        *  @return  A pair, of which the first element is an iterator that points
00288        *           to the possibly inserted element, and the second is a bool
00289        *           that is true if the element was actually inserted.
00290        *
00291        *  This function attempts to build and insert an element into the
00292        *  %unordered_set. An %unordered_set relies on unique keys and thus an
00293        *  element is only inserted if it is not already present in the
00294        *  %unordered_set.
00295        *
00296        *  Insertion requires amortized constant time.
00297        */
00298       template<typename... _Args>
00299     std::pair<iterator, bool>
00300     emplace(_Args&&... __args)
00301     { return _M_h.emplace(std::forward<_Args>(__args)...); }
00302 
00303       /**
00304        *  @brief Attempts to insert an element into the %unordered_set.
00305        *  @param  __pos  An iterator that serves as a hint as to where the
00306        *                element should be inserted.
00307        *  @param  __args  Arguments used to generate the element to be
00308        *                 inserted.
00309        *  @return An iterator that points to the element with key equivalent to
00310        *          the one generated from @a __args (may or may not be the
00311        *          element itself).
00312        *
00313        *  This function is not concerned about whether the insertion took place,
00314        *  and thus does not return a boolean like the single-argument emplace()
00315        *  does.  Note that the first parameter is only a hint and can
00316        *  potentially improve the performance of the insertion process.  A bad
00317        *  hint would cause no gains in efficiency.
00318        *
00319        *  For more on @a hinting, see:
00320        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00321        *
00322        *  Insertion requires amortized constant time.
00323        */
00324       template<typename... _Args>
00325     iterator
00326     emplace_hint(const_iterator __pos, _Args&&... __args)
00327     { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
00328 
00329       //@{
00330       /**
00331        *  @brief Attempts to insert an element into the %unordered_set.
00332        *  @param  __x  Element to be inserted.
00333        *  @return  A pair, of which the first element is an iterator that points
00334        *           to the possibly inserted element, and the second is a bool
00335        *           that is true if the element was actually inserted.
00336        *
00337        *  This function attempts to insert an element into the %unordered_set.
00338        *  An %unordered_set relies on unique keys and thus an element is only
00339        *  inserted if it is not already present in the %unordered_set.
00340        *
00341        *  Insertion requires amortized constant time.
00342        */
00343       std::pair<iterator, bool>
00344       insert(const value_type& __x)
00345       { return _M_h.insert(__x); }
00346 
00347       std::pair<iterator, bool>
00348       insert(value_type&& __x)
00349       { return _M_h.insert(std::move(__x)); }
00350       //@}
00351 
00352       //@{
00353       /**
00354        *  @brief Attempts to insert an element into the %unordered_set.
00355        *  @param  __hint  An iterator that serves as a hint as to where the
00356        *                 element should be inserted.
00357        *  @param  __x  Element to be inserted.
00358        *  @return An iterator that points to the element with key of
00359        *           @a __x (may or may not be the element passed in).
00360        *
00361        *  This function is not concerned about whether the insertion took place,
00362        *  and thus does not return a boolean like the single-argument insert()
00363        *  does.  Note that the first parameter is only a hint and can
00364        *  potentially improve the performance of the insertion process.  A bad
00365        *  hint would cause no gains in efficiency.
00366        *
00367        *  For more on @a hinting, see:
00368        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00369        *
00370        *  Insertion requires amortized constant.
00371        */
00372       iterator
00373       insert(const_iterator __hint, const value_type& __x)
00374       { return _M_h.insert(__hint, __x); }
00375 
00376       iterator
00377       insert(const_iterator __hint, value_type&& __x)
00378       { return _M_h.insert(__hint, std::move(__x)); }
00379       //@}
00380 
00381       /**
00382        *  @brief A template function that attempts to insert a range of
00383        *  elements.
00384        *  @param  __first  Iterator pointing to the start of the range to be
00385        *                   inserted.
00386        *  @param  __last  Iterator pointing to the end of the range.
00387        *
00388        *  Complexity similar to that of the range constructor.
00389        */
00390       template<typename _InputIterator>
00391     void
00392     insert(_InputIterator __first, _InputIterator __last)
00393     { _M_h.insert(__first, __last); }
00394 
00395       /**
00396        *  @brief Attempts to insert a list of elements into the %unordered_set.
00397        *  @param  __l  A std::initializer_list<value_type> of elements
00398        *               to be inserted.
00399        *
00400        *  Complexity similar to that of the range constructor.
00401        */
00402       void
00403       insert(initializer_list<value_type> __l)
00404       { _M_h.insert(__l); }
00405 
00406       //@{
00407       /**
00408        *  @brief Erases an element from an %unordered_set.
00409        *  @param  __position  An iterator pointing to the element to be erased.
00410        *  @return An iterator pointing to the element immediately following
00411        *          @a __position prior to the element being erased. If no such
00412        *          element exists, end() is returned.
00413        *
00414        *  This function erases an element, pointed to by the given iterator,
00415        *  from an %unordered_set.  Note that this function only erases the
00416        *  element, and that if the element is itself a pointer, the pointed-to
00417        *  memory is not touched in any way.  Managing the pointer is the user's
00418        *  responsibility.
00419        */
00420       iterator
00421       erase(const_iterator __position)
00422       { return _M_h.erase(__position); }
00423 
00424       // LWG 2059.
00425       iterator
00426       erase(iterator __it)
00427       { return _M_h.erase(__it); }
00428       //@}
00429 
00430       /**
00431        *  @brief Erases elements according to the provided key.
00432        *  @param  __x  Key of element to be erased.
00433        *  @return  The number of elements erased.
00434        *
00435        *  This function erases all the elements located by the given key from
00436        *  an %unordered_set. For an %unordered_set the result of this function
00437        *  can only be 0 (not present) or 1 (present).
00438        *  Note that this function only erases the element, and that if
00439        *  the element is itself a pointer, the pointed-to memory is not touched
00440        *  in any way.  Managing the pointer is the user's responsibility.
00441        */
00442       size_type
00443       erase(const key_type& __x)
00444       { return _M_h.erase(__x); }
00445 
00446       /**
00447        *  @brief Erases a [__first,__last) range of elements from an
00448        *  %unordered_set.
00449        *  @param  __first  Iterator pointing to the start of the range to be
00450        *                  erased.
00451        *  @param __last  Iterator pointing to the end of the range to
00452        *                be erased.
00453        *  @return The iterator @a __last.
00454        *
00455        *  This function erases a sequence of elements from an %unordered_set.
00456        *  Note that this function only erases the element, and that if
00457        *  the element is itself a pointer, the pointed-to memory is not touched
00458        *  in any way.  Managing the pointer is the user's responsibility.
00459        */
00460       iterator
00461       erase(const_iterator __first, const_iterator __last)
00462       { return _M_h.erase(__first, __last); }
00463 
00464       /**
00465        *  Erases all elements in an %unordered_set. Note that this function only
00466        *  erases the elements, and that if the elements themselves are pointers,
00467        *  the pointed-to memory is not touched in any way. Managing the pointer
00468        *  is the user's responsibility.
00469        */
00470       void
00471       clear() noexcept
00472       { _M_h.clear(); }
00473 
00474       /**
00475        *  @brief  Swaps data with another %unordered_set.
00476        *  @param  __x  An %unordered_set of the same element and allocator
00477        *  types.
00478        *
00479        *  This exchanges the elements between two sets in constant time.
00480        *  Note that the global std::swap() function is specialized such that
00481        *  std::swap(s1,s2) will feed to this function.
00482        */
00483       void
00484       swap(unordered_set& __x)
00485       { _M_h.swap(__x._M_h); }
00486 
00487       // observers.
00488 
00489       ///  Returns the hash functor object with which the %unordered_set was
00490       ///  constructed.
00491       hasher
00492       hash_function() const
00493       { return _M_h.hash_function(); }
00494 
00495       ///  Returns the key comparison object with which the %unordered_set was
00496       ///  constructed.
00497       key_equal
00498       key_eq() const
00499       { return _M_h.key_eq(); }
00500 
00501       // lookup.
00502 
00503       //@{
00504       /**
00505        *  @brief Tries to locate an element in an %unordered_set.
00506        *  @param  __x  Element to be located.
00507        *  @return  Iterator pointing to sought-after element, or end() if not
00508        *           found.
00509        *
00510        *  This function takes a key and tries to locate the element with which
00511        *  the key matches.  If successful the function returns an iterator
00512        *  pointing to the sought after element.  If unsuccessful it returns the
00513        *  past-the-end ( @c end() ) iterator.
00514        */
00515       iterator
00516       find(const key_type& __x)
00517       { return _M_h.find(__x); }
00518 
00519       const_iterator
00520       find(const key_type& __x) const
00521       { return _M_h.find(__x); }
00522       //@}
00523 
00524       /**
00525        *  @brief  Finds the number of elements.
00526        *  @param  __x  Element to located.
00527        *  @return  Number of elements with specified key.
00528        *
00529        *  This function only makes sense for unordered_multisets; for
00530        *  unordered_set the result will either be 0 (not present) or 1
00531        *  (present).
00532        */
00533       size_type
00534       count(const key_type& __x) const
00535       { return _M_h.count(__x); }
00536 
00537       //@{
00538       /**
00539        *  @brief Finds a subsequence matching given key.
00540        *  @param  __x  Key to be located.
00541        *  @return  Pair of iterators that possibly points to the subsequence
00542        *           matching given key.
00543        *
00544        *  This function probably only makes sense for multisets.
00545        */
00546       std::pair<iterator, iterator>
00547       equal_range(const key_type& __x)
00548       { return _M_h.equal_range(__x); }
00549 
00550       std::pair<const_iterator, const_iterator>
00551       equal_range(const key_type& __x) const
00552       { return _M_h.equal_range(__x); }
00553       //@}
00554 
00555       // bucket interface.
00556 
00557       /// Returns the number of buckets of the %unordered_set.
00558       size_type
00559       bucket_count() const noexcept
00560       { return _M_h.bucket_count(); }
00561 
00562       /// Returns the maximum number of buckets of the %unordered_set.
00563       size_type
00564       max_bucket_count() const noexcept
00565       { return _M_h.max_bucket_count(); }
00566 
00567       /*
00568        * @brief  Returns the number of elements in a given bucket.
00569        * @param  __n  A bucket index.
00570        * @return  The number of elements in the bucket.
00571        */
00572       size_type
00573       bucket_size(size_type __n) const
00574       { return _M_h.bucket_size(__n); }
00575 
00576       /*
00577        * @brief  Returns the bucket index of a given element.
00578        * @param  __key  A key instance.
00579        * @return  The key bucket index.
00580        */
00581       size_type
00582       bucket(const key_type& __key) const
00583       { return _M_h.bucket(__key); }
00584 
00585       //@{
00586       /**
00587        *  @brief  Returns a read-only (constant) iterator pointing to the first
00588        *         bucket element.
00589        *  @param  __n The bucket index.
00590        *  @return  A read-only local iterator.
00591        */
00592       local_iterator
00593       begin(size_type __n)
00594       { return _M_h.begin(__n); }
00595 
00596       const_local_iterator
00597       begin(size_type __n) const
00598       { return _M_h.begin(__n); }
00599 
00600       const_local_iterator
00601       cbegin(size_type __n) const
00602       { return _M_h.cbegin(__n); }
00603       //@}
00604 
00605       //@{
00606       /**
00607        *  @brief  Returns a read-only (constant) iterator pointing to one past
00608        *         the last bucket elements.
00609        *  @param  __n The bucket index.
00610        *  @return  A read-only local iterator.
00611        */
00612       local_iterator
00613       end(size_type __n)
00614       { return _M_h.end(__n); }
00615 
00616       const_local_iterator
00617       end(size_type __n) const
00618       { return _M_h.end(__n); }
00619 
00620       const_local_iterator
00621       cend(size_type __n) const
00622       { return _M_h.cend(__n); }
00623       //@}
00624 
00625       // hash policy.
00626 
00627       /// Returns the average number of elements per bucket.
00628       float
00629       load_factor() const noexcept
00630       { return _M_h.load_factor(); }
00631 
00632       /// Returns a positive number that the %unordered_set tries to keep the
00633       /// load factor less than or equal to.
00634       float
00635       max_load_factor() const noexcept
00636       { return _M_h.max_load_factor(); }
00637 
00638       /**
00639        *  @brief  Change the %unordered_set maximum load factor.
00640        *  @param  __z The new maximum load factor.
00641        */
00642       void
00643       max_load_factor(float __z)
00644       { _M_h.max_load_factor(__z); }
00645 
00646       /**
00647        *  @brief  May rehash the %unordered_set.
00648        *  @param  __n The new number of buckets.
00649        *
00650        *  Rehash will occur only if the new number of buckets respect the
00651        *  %unordered_set maximum load factor.
00652        */
00653       void
00654       rehash(size_type __n)
00655       { _M_h.rehash(__n); }
00656 
00657       /**
00658        *  @brief  Prepare the %unordered_set for a specified number of
00659        *          elements.
00660        *  @param  __n Number of elements required.
00661        *
00662        *  Same as rehash(ceil(n / max_load_factor())).
00663        */
00664       void
00665       reserve(size_type __n)
00666       { _M_h.reserve(__n); }
00667 
00668       template<typename _Value1, typename _Hash1, typename _Pred1,
00669            typename _Alloc1>
00670         friend bool
00671       operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
00672          const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
00673     };
00674 
00675   /**
00676    *  @brief A standard container composed of equivalent keys
00677    *  (possibly containing multiple of each key value) in which the
00678    *  elements' keys are the elements themselves.
00679    *
00680    *  @ingroup unordered_associative_containers
00681    *
00682    *  @tparam  _Value  Type of key objects.
00683    *  @tparam  _Hash  Hashing function object type, defaults to hash<_Value>.
00684    *  @tparam  _Pred  Predicate function object type, defaults
00685    *                  to equal_to<_Value>.
00686    *  @tparam  _Alloc  Allocator type, defaults to allocator<_Key>.
00687    *
00688    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00689    *  <a href="tables.html#xx">unordered associative container</a>
00690    *
00691    *  Base is _Hashtable, dispatched at compile time via template
00692    *  alias __umset_hashtable.
00693    */
00694   template<class _Value,
00695        class _Hash = hash<_Value>,
00696        class _Pred = std::equal_to<_Value>,
00697        class _Alloc = std::allocator<_Value> >
00698     class unordered_multiset : __check_copy_constructible<_Alloc>
00699     {
00700       typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
00701       _Hashtable _M_h;
00702 
00703     public:
00704       // typedefs:
00705       //@{
00706       /// Public typedefs.
00707       typedef typename _Hashtable::key_type key_type;
00708       typedef typename _Hashtable::value_type   value_type;
00709       typedef typename _Hashtable::hasher   hasher;
00710       typedef typename _Hashtable::key_equal    key_equal;
00711       typedef typename _Hashtable::allocator_type allocator_type;
00712       //@}
00713 
00714       //@{
00715       ///  Iterator-related typedefs.
00716       typedef typename allocator_type::pointer      pointer;
00717       typedef typename allocator_type::const_pointer    const_pointer;
00718       typedef typename allocator_type::reference    reference;
00719       typedef typename allocator_type::const_reference  const_reference;
00720       typedef typename _Hashtable::iterator     iterator;
00721       typedef typename _Hashtable::const_iterator   const_iterator;
00722       typedef typename _Hashtable::local_iterator   local_iterator;
00723       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00724       typedef typename _Hashtable::size_type        size_type;
00725       typedef typename _Hashtable::difference_type  difference_type;
00726       //@}
00727 
00728       // construct/destroy/copy
00729       /**
00730        *  @brief  Default constructor creates no elements.
00731        *  @param __n  Initial number of buckets.
00732        *  @param __hf  A hash functor.
00733        *  @param __eql  A key equality functor.
00734        *  @param __a  An allocator object.
00735        */
00736       explicit
00737       unordered_multiset(size_type __n = 10,
00738              const hasher& __hf = hasher(),
00739              const key_equal& __eql = key_equal(),
00740              const allocator_type& __a = allocator_type())
00741       : _M_h(__n, __hf, __eql, __a)
00742       { }
00743 
00744       /**
00745        *  @brief  Builds an %unordered_multiset from a range.
00746        *  @param  __first  An input iterator.
00747        *  @param  __last  An input iterator.
00748        *  @param __n  Minimal initial number of buckets.
00749        *  @param __hf  A hash functor.
00750        *  @param __eql  A key equality functor.
00751        *  @param __a  An allocator object.
00752        *
00753        *  Create an %unordered_multiset consisting of copies of the elements
00754        *  from [__first,__last).  This is linear in N (where N is
00755        *  distance(__first,__last)).
00756        */
00757       template<typename _InputIterator>
00758     unordered_multiset(_InputIterator __f, _InputIterator __l,
00759                size_type __n = 0,
00760                const hasher& __hf = hasher(),
00761                const key_equal& __eql = key_equal(),
00762                const allocator_type& __a = allocator_type())
00763     : _M_h(__f, __l, __n, __hf, __eql, __a)
00764     { }
00765 
00766       /// Copy constructor.
00767       unordered_multiset(const unordered_multiset&) = default;
00768 
00769       /// Move constructor.
00770       unordered_multiset(unordered_multiset&&) = default;
00771 
00772       /**
00773        *  @brief  Builds an %unordered_multiset from an initializer_list.
00774        *  @param  __l  An initializer_list.
00775        *  @param __n  Minimal initial number of buckets.
00776        *  @param __hf  A hash functor.
00777        *  @param __eql  A key equality functor.
00778        *  @param  __a  An allocator object.
00779        *
00780        *  Create an %unordered_multiset consisting of copies of the elements in
00781        *  the list. This is linear in N (where N is @a __l.size()).
00782        */
00783       unordered_multiset(initializer_list<value_type> __l,
00784              size_type __n = 0,
00785              const hasher& __hf = hasher(),
00786              const key_equal& __eql = key_equal(),
00787              const allocator_type& __a = allocator_type())
00788     : _M_h(__l, __n, __hf, __eql, __a)
00789       { }
00790 
00791       /// Copy assignment operator.
00792       unordered_multiset&
00793       operator=(const unordered_multiset&) = default;
00794 
00795       /// Move assignment operator.
00796       unordered_multiset&
00797       operator=(unordered_multiset&& __x) = default;
00798 
00799       /**
00800        *  @brief  %Unordered_multiset list assignment operator.
00801        *  @param  __l  An initializer_list.
00802        *
00803        *  This function fills an %unordered_multiset with copies of the elements
00804        *  in the initializer list @a __l.
00805        *
00806        *  Note that the assignment completely changes the %unordered_multiset
00807        *  and that the resulting %unordered_set's size is the same as the number
00808        *  of elements assigned.  Old data may be lost.
00809        */
00810       unordered_multiset&
00811       operator=(initializer_list<value_type> __l)
00812       {
00813     _M_h = __l;
00814     return *this;
00815       }
00816 
00817       ///  Returns the allocator object with which the %unordered_multiset was
00818       ///  constructed.
00819       allocator_type
00820       get_allocator() const noexcept
00821       { return _M_h.get_allocator(); }
00822 
00823       // size and capacity:
00824 
00825       ///  Returns true if the %unordered_multiset is empty.
00826       bool
00827       empty() const noexcept
00828       { return _M_h.empty(); }
00829 
00830       ///  Returns the size of the %unordered_multiset.
00831       size_type
00832       size() const noexcept
00833       { return _M_h.size(); }
00834 
00835       ///  Returns the maximum size of the %unordered_multiset.
00836       size_type
00837       max_size() const noexcept
00838       { return _M_h.max_size(); }
00839 
00840       // iterators.
00841 
00842       //@{
00843       /**
00844        *  Returns a read-only (constant) iterator that points to the first
00845        *  element in the %unordered_multiset.
00846        */
00847       iterator
00848       begin() noexcept
00849       { return _M_h.begin(); }
00850 
00851       const_iterator
00852       begin() const noexcept
00853       { return _M_h.begin(); }
00854       //@}
00855 
00856       //@{
00857       /**
00858        *  Returns a read-only (constant) iterator that points one past the last
00859        *  element in the %unordered_multiset.
00860        */
00861       iterator
00862       end() noexcept
00863       { return _M_h.end(); }
00864 
00865       const_iterator
00866       end() const noexcept
00867       { return _M_h.end(); }
00868       //@}
00869 
00870       /**
00871        *  Returns a read-only (constant) iterator that points to the first
00872        *  element in the %unordered_multiset.
00873        */
00874       const_iterator
00875       cbegin() const noexcept
00876       { return _M_h.begin(); }
00877 
00878       /**
00879        *  Returns a read-only (constant) iterator that points one past the last
00880        *  element in the %unordered_multiset.
00881        */
00882       const_iterator
00883       cend() const noexcept
00884       { return _M_h.end(); }
00885 
00886       // modifiers.
00887 
00888       /**
00889        *  @brief Builds and insert an element into the %unordered_multiset.
00890        *  @param __args  Arguments used to generate an element.
00891        *  @return  An iterator that points to the inserted element.
00892        *
00893        *  Insertion requires amortized constant time.
00894        */
00895       template<typename... _Args>
00896     iterator
00897     emplace(_Args&&... __args)
00898     { return _M_h.emplace(std::forward<_Args>(__args)...); }
00899 
00900       /**
00901        *  @brief Inserts an element into the %unordered_multiset.
00902        *  @param  __pos  An iterator that serves as a hint as to where the
00903        *                element should be inserted.
00904        *  @param  __args  Arguments used to generate the element to be
00905        *                 inserted.
00906        *  @return An iterator that points to the inserted element.
00907        *
00908        *  Note that the first parameter is only a hint and can potentially
00909        *  improve the performance of the insertion process.  A bad hint would
00910        *  cause no gains in efficiency.
00911        *
00912        *  For more on @a hinting, see:
00913        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00914        *
00915        *  Insertion requires amortized constant time.
00916        */
00917       template<typename... _Args>
00918     iterator
00919     emplace_hint(const_iterator __pos, _Args&&... __args)
00920     { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
00921 
00922       //@{
00923       /**
00924        *  @brief Inserts an element into the %unordered_multiset.
00925        *  @param  __x  Element to be inserted.
00926        *  @return  An iterator that points to the inserted element.
00927        *
00928        *  Insertion requires amortized constant time.
00929        */
00930       iterator
00931       insert(const value_type& __x)
00932       { return _M_h.insert(__x); }
00933 
00934       iterator
00935       insert(value_type&& __x)
00936       { return _M_h.insert(std::move(__x)); }
00937       //@}
00938 
00939       //@{
00940       /**
00941        *  @brief Inserts an element into the %unordered_multiset.
00942        *  @param  __hint  An iterator that serves as a hint as to where the
00943        *                 element should be inserted.
00944        *  @param  __x  Element to be inserted.
00945        *  @return An iterator that points to the inserted element.
00946        *
00947        *  Note that the first parameter is only a hint and can potentially
00948        *  improve the performance of the insertion process.  A bad hint would
00949        *  cause no gains in efficiency.
00950        *
00951        *  For more on @a hinting, see:
00952        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00953        *
00954        *  Insertion requires amortized constant.
00955        */
00956       iterator
00957       insert(const_iterator __hint, const value_type& __x)
00958       { return _M_h.insert(__hint, __x); }
00959 
00960       iterator
00961       insert(const_iterator __hint, value_type&& __x)
00962       { return _M_h.insert(__hint, std::move(__x)); }
00963       //@}
00964 
00965       /**
00966        *  @brief A template function that inserts a range of elements.
00967        *  @param  __first  Iterator pointing to the start of the range to be
00968        *                   inserted.
00969        *  @param  __last  Iterator pointing to the end of the range.
00970        *
00971        *  Complexity similar to that of the range constructor.
00972        */
00973       template<typename _InputIterator>
00974     void
00975     insert(_InputIterator __first, _InputIterator __last)
00976     { _M_h.insert(__first, __last); }
00977 
00978       /**
00979        *  @brief Inserts a list of elements into the %unordered_multiset.
00980        *  @param  __l  A std::initializer_list<value_type> of elements to be
00981        *              inserted.
00982        *
00983        *  Complexity similar to that of the range constructor.
00984        */
00985       void
00986       insert(initializer_list<value_type> __l)
00987       { _M_h.insert(__l); }
00988 
00989       //@{
00990       /**
00991        *  @brief Erases an element from an %unordered_multiset.
00992        *  @param  __position  An iterator pointing to the element to be erased.
00993        *  @return An iterator pointing to the element immediately following
00994        *          @a __position prior to the element being erased. If no such
00995        *          element exists, end() is returned.
00996        *
00997        *  This function erases an element, pointed to by the given iterator,
00998        *  from an %unordered_multiset.
00999        *
01000        *  Note that this function only erases the element, and that if the
01001        *  element is itself a pointer, the pointed-to memory is not touched in
01002        *  any way.  Managing the pointer is the user's responsibility.
01003        */
01004       iterator
01005       erase(const_iterator __position)
01006       { return _M_h.erase(__position); }
01007 
01008       // LWG 2059.
01009       iterator
01010       erase(iterator __it)
01011       { return _M_h.erase(__it); }
01012       //@}
01013 
01014 
01015       /**
01016        *  @brief Erases elements according to the provided key.
01017        *  @param  __x  Key of element to be erased.
01018        *  @return  The number of elements erased.
01019        *
01020        *  This function erases all the elements located by the given key from
01021        *  an %unordered_multiset.
01022        *
01023        *  Note that this function only erases the element, and that if the
01024        *  element is itself a pointer, the pointed-to memory is not touched in
01025        *  any way.  Managing the pointer is the user's responsibility.
01026        */
01027       size_type
01028       erase(const key_type& __x)
01029       { return _M_h.erase(__x); }
01030 
01031       /**
01032        *  @brief Erases a [__first,__last) range of elements from an
01033        *  %unordered_multiset.
01034        *  @param  __first  Iterator pointing to the start of the range to be
01035        *                  erased.
01036        *  @param __last  Iterator pointing to the end of the range to
01037        *                be erased.
01038        *  @return The iterator @a __last.
01039        *
01040        *  This function erases a sequence of elements from an
01041        *  %unordered_multiset.
01042        *
01043        *  Note that this function only erases the element, and that if
01044        *  the element is itself a pointer, the pointed-to memory is not touched
01045        *  in any way.  Managing the pointer is the user's responsibility.
01046        */
01047       iterator
01048       erase(const_iterator __first, const_iterator __last)
01049       { return _M_h.erase(__first, __last); }
01050 
01051       /**
01052        *  Erases all elements in an %unordered_multiset.
01053        *
01054        *  Note that this function only erases the elements, and that if the
01055        *  elements themselves are pointers, the pointed-to memory is not touched
01056        *  in any way. Managing the pointer is the user's responsibility.
01057        */
01058       void
01059       clear() noexcept
01060       { _M_h.clear(); }
01061 
01062       /**
01063        *  @brief  Swaps data with another %unordered_multiset.
01064        *  @param  __x  An %unordered_multiset of the same element and allocator
01065        *  types.
01066        *
01067        *  This exchanges the elements between two sets in constant time.
01068        *  Note that the global std::swap() function is specialized such that
01069        *  std::swap(s1,s2) will feed to this function.
01070        */
01071       void
01072       swap(unordered_multiset& __x)
01073       { _M_h.swap(__x._M_h); }
01074 
01075       // observers.
01076 
01077       ///  Returns the hash functor object with which the %unordered_multiset
01078       ///  was constructed.
01079       hasher
01080       hash_function() const
01081       { return _M_h.hash_function(); }
01082 
01083       ///  Returns the key comparison object with which the %unordered_multiset
01084       ///  was constructed.
01085       key_equal
01086       key_eq() const
01087       { return _M_h.key_eq(); }
01088 
01089       // lookup.
01090 
01091       //@{
01092       /**
01093        *  @brief Tries to locate an element in an %unordered_multiset.
01094        *  @param  __x  Element to be located.
01095        *  @return  Iterator pointing to sought-after element, or end() if not
01096        *           found.
01097        *
01098        *  This function takes a key and tries to locate the element with which
01099        *  the key matches.  If successful the function returns an iterator
01100        *  pointing to the sought after element.  If unsuccessful it returns the
01101        *  past-the-end ( @c end() ) iterator.
01102        */
01103       iterator
01104       find(const key_type& __x)
01105       { return _M_h.find(__x); }
01106 
01107       const_iterator
01108       find(const key_type& __x) const
01109       { return _M_h.find(__x); }
01110       //@}
01111 
01112       /**
01113        *  @brief  Finds the number of elements.
01114        *  @param  __x  Element to located.
01115        *  @return  Number of elements with specified key.
01116        */
01117       size_type
01118       count(const key_type& __x) const
01119       { return _M_h.count(__x); }
01120 
01121       //@{
01122       /**
01123        *  @brief Finds a subsequence matching given key.
01124        *  @param  __x  Key to be located.
01125        *  @return  Pair of iterators that possibly points to the subsequence
01126        *           matching given key.
01127        */
01128       std::pair<iterator, iterator>
01129       equal_range(const key_type& __x)
01130       { return _M_h.equal_range(__x); }
01131 
01132       std::pair<const_iterator, const_iterator>
01133       equal_range(const key_type& __x) const
01134       { return _M_h.equal_range(__x); }
01135       //@}
01136 
01137       // bucket interface.
01138 
01139       /// Returns the number of buckets of the %unordered_multiset.
01140       size_type
01141       bucket_count() const noexcept
01142       { return _M_h.bucket_count(); }
01143 
01144       /// Returns the maximum number of buckets of the %unordered_multiset.
01145       size_type
01146       max_bucket_count() const noexcept
01147       { return _M_h.max_bucket_count(); }
01148 
01149       /*
01150        * @brief  Returns the number of elements in a given bucket.
01151        * @param  __n  A bucket index.
01152        * @return  The number of elements in the bucket.
01153        */
01154       size_type
01155       bucket_size(size_type __n) const
01156       { return _M_h.bucket_size(__n); }
01157 
01158       /*
01159        * @brief  Returns the bucket index of a given element.
01160        * @param  __key  A key instance.
01161        * @return  The key bucket index.
01162        */
01163       size_type
01164       bucket(const key_type& __key) const
01165       { return _M_h.bucket(__key); }
01166 
01167       //@{
01168       /**
01169        *  @brief  Returns a read-only (constant) iterator pointing to the first
01170        *         bucket element.
01171        *  @param  __n The bucket index.
01172        *  @return  A read-only local iterator.
01173        */
01174       local_iterator
01175       begin(size_type __n)
01176       { return _M_h.begin(__n); }
01177 
01178       const_local_iterator
01179       begin(size_type __n) const
01180       { return _M_h.begin(__n); }
01181 
01182       const_local_iterator
01183       cbegin(size_type __n) const
01184       { return _M_h.cbegin(__n); }
01185       //@}
01186 
01187       //@{
01188       /**
01189        *  @brief  Returns a read-only (constant) iterator pointing to one past
01190        *         the last bucket elements.
01191        *  @param  __n The bucket index.
01192        *  @return  A read-only local iterator.
01193        */
01194       local_iterator
01195       end(size_type __n)
01196       { return _M_h.end(__n); }
01197 
01198       const_local_iterator
01199       end(size_type __n) const
01200       { return _M_h.end(__n); }
01201 
01202       const_local_iterator
01203       cend(size_type __n) const
01204       { return _M_h.cend(__n); }
01205       //@}
01206 
01207       // hash policy.
01208 
01209       /// Returns the average number of elements per bucket.
01210       float
01211       load_factor() const noexcept
01212       { return _M_h.load_factor(); }
01213 
01214       /// Returns a positive number that the %unordered_multiset tries to keep the
01215       /// load factor less than or equal to.
01216       float
01217       max_load_factor() const noexcept
01218       { return _M_h.max_load_factor(); }
01219 
01220       /**
01221        *  @brief  Change the %unordered_multiset maximum load factor.
01222        *  @param  __z The new maximum load factor.
01223        */
01224       void
01225       max_load_factor(float __z)
01226       { _M_h.max_load_factor(__z); }
01227 
01228       /**
01229        *  @brief  May rehash the %unordered_multiset.
01230        *  @param  __n The new number of buckets.
01231        *
01232        *  Rehash will occur only if the new number of buckets respect the
01233        *  %unordered_multiset maximum load factor.
01234        */
01235       void
01236       rehash(size_type __n)
01237       { _M_h.rehash(__n); }
01238 
01239       /**
01240        *  @brief  Prepare the %unordered_multiset for a specified number of
01241        *          elements.
01242        *  @param  __n Number of elements required.
01243        *
01244        *  Same as rehash(ceil(n / max_load_factor())).
01245        */
01246       void
01247       reserve(size_type __n)
01248       { _M_h.reserve(__n); }
01249 
01250       template<typename _Value1, typename _Hash1, typename _Pred1,
01251            typename _Alloc1>
01252         friend bool
01253       operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
01254          const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
01255     };
01256 
01257   template<class _Value, class _Hash, class _Pred, class _Alloc>
01258     inline void
01259     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01260      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01261     { __x.swap(__y); }
01262 
01263   template<class _Value, class _Hash, class _Pred, class _Alloc>
01264     inline void
01265     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01266      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01267     { __x.swap(__y); }
01268 
01269   template<class _Value, class _Hash, class _Pred, class _Alloc>
01270     inline bool
01271     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01272            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01273     { return __x._M_h._M_equal(__y._M_h); }
01274 
01275   template<class _Value, class _Hash, class _Pred, class _Alloc>
01276     inline bool
01277     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01278            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01279     { return !(__x == __y); }
01280 
01281   template<class _Value, class _Hash, class _Pred, class _Alloc>
01282     inline bool
01283     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01284            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01285     { return __x._M_h._M_equal(__y._M_h); }
01286 
01287   template<class _Value, class _Hash, class _Pred, class _Alloc>
01288     inline bool
01289     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01290            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01291     { return !(__x == __y); }
01292 
01293 _GLIBCXX_END_NAMESPACE_CONTAINER
01294 } // namespace std
01295 
01296 #endif /* _UNORDERED_SET_H */