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