l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.9/include/bits/unordered_set.h

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