libstdc++
unordered_set.h
Go to the documentation of this file.
1 // unordered_set implementation -*- C++ -*-
2 
3 // Copyright (C) 2010-2019 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_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37 
38  /// Base types for unordered_set.
39  template<bool _Cache>
41 
42  template<typename _Value,
43  typename _Hash = hash<_Value>,
44  typename _Pred = std::equal_to<_Value>,
45  typename _Alloc = std::allocator<_Value>,
47  using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
48  __detail::_Identity, _Pred, _Hash,
52 
53  /// Base types for unordered_multiset.
54  template<bool _Cache>
56 
57  template<typename _Value,
58  typename _Hash = hash<_Value>,
59  typename _Pred = std::equal_to<_Value>,
60  typename _Alloc = std::allocator<_Value>,
62  using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
63  __detail::_Identity,
64  _Pred, _Hash,
68 
69  template<class _Value, class _Hash, class _Pred, class _Alloc>
71 
72  /**
73  * @brief A standard container composed of unique keys (containing
74  * at most one of each key value) in which the elements' keys are
75  * the elements themselves.
76  *
77  * @ingroup unordered_associative_containers
78  *
79  * @tparam _Value Type of key objects.
80  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
81 
82  * @tparam _Pred Predicate function object type, defaults to
83  * equal_to<_Value>.
84  *
85  * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
86  *
87  * Meets the requirements of a <a href="tables.html#65">container</a>, and
88  * <a href="tables.html#xx">unordered associative container</a>
89  *
90  * Base is _Hashtable, dispatched at compile time via template
91  * alias __uset_hashtable.
92  */
93  template<typename _Value,
94  typename _Hash = hash<_Value>,
95  typename _Pred = equal_to<_Value>,
96  typename _Alloc = allocator<_Value>>
98  {
100  _Hashtable _M_h;
101 
102  public:
103  // typedefs:
104  //@{
105  /// Public typedefs.
106  typedef typename _Hashtable::key_type key_type;
107  typedef typename _Hashtable::value_type value_type;
108  typedef typename _Hashtable::hasher hasher;
109  typedef typename _Hashtable::key_equal key_equal;
110  typedef typename _Hashtable::allocator_type allocator_type;
111  //@}
112 
113  //@{
114  /// Iterator-related typedefs.
115  typedef typename _Hashtable::pointer pointer;
116  typedef typename _Hashtable::const_pointer const_pointer;
117  typedef typename _Hashtable::reference reference;
118  typedef typename _Hashtable::const_reference const_reference;
119  typedef typename _Hashtable::iterator iterator;
120  typedef typename _Hashtable::const_iterator const_iterator;
121  typedef typename _Hashtable::local_iterator local_iterator;
122  typedef typename _Hashtable::const_local_iterator const_local_iterator;
123  typedef typename _Hashtable::size_type size_type;
124  typedef typename _Hashtable::difference_type difference_type;
125  //@}
126 
127 #if __cplusplus > 201402L
128  using node_type = typename _Hashtable::node_type;
129  using insert_return_type = typename _Hashtable::insert_return_type;
130 #endif
131 
132  // construct/destroy/copy
133 
134  /// Default constructor.
135  unordered_set() = default;
136 
137  /**
138  * @brief Default constructor creates no elements.
139  * @param __n Minimal initial number of buckets.
140  * @param __hf A hash functor.
141  * @param __eql A key equality functor.
142  * @param __a An allocator object.
143  */
144  explicit
146  const hasher& __hf = hasher(),
147  const key_equal& __eql = key_equal(),
148  const allocator_type& __a = allocator_type())
149  : _M_h(__n, __hf, __eql, __a)
150  { }
151 
152  /**
153  * @brief Builds an %unordered_set from a range.
154  * @param __first An input iterator.
155  * @param __last An input iterator.
156  * @param __n Minimal initial number of buckets.
157  * @param __hf A hash functor.
158  * @param __eql A key equality functor.
159  * @param __a An allocator object.
160  *
161  * Create an %unordered_set consisting of copies of the elements from
162  * [__first,__last). This is linear in N (where N is
163  * distance(__first,__last)).
164  */
165  template<typename _InputIterator>
166  unordered_set(_InputIterator __first, _InputIterator __last,
167  size_type __n = 0,
168  const hasher& __hf = hasher(),
169  const key_equal& __eql = key_equal(),
170  const allocator_type& __a = allocator_type())
171  : _M_h(__first, __last, __n, __hf, __eql, __a)
172  { }
173 
174  /// Copy constructor.
175  unordered_set(const unordered_set&) = default;
176 
177  /// Move constructor.
178  unordered_set(unordered_set&&) = default;
179 
180  /**
181  * @brief Creates an %unordered_set with no elements.
182  * @param __a An allocator object.
183  */
184  explicit
186  : _M_h(__a)
187  { }
188 
189  /*
190  * @brief Copy constructor with allocator argument.
191  * @param __uset Input %unordered_set to copy.
192  * @param __a An allocator object.
193  */
194  unordered_set(const unordered_set& __uset,
195  const allocator_type& __a)
196  : _M_h(__uset._M_h, __a)
197  { }
198 
199  /*
200  * @brief Move constructor with allocator argument.
201  * @param __uset Input %unordered_set to move.
202  * @param __a An allocator object.
203  */
204  unordered_set(unordered_set&& __uset,
205  const allocator_type& __a)
206  : _M_h(std::move(__uset._M_h), __a)
207  { }
208 
209  /**
210  * @brief Builds an %unordered_set from an initializer_list.
211  * @param __l An initializer_list.
212  * @param __n Minimal initial number of buckets.
213  * @param __hf A hash functor.
214  * @param __eql A key equality functor.
215  * @param __a An allocator object.
216  *
217  * Create an %unordered_set consisting of copies of the elements in the
218  * list. This is linear in N (where N is @a __l.size()).
219  */
221  size_type __n = 0,
222  const hasher& __hf = hasher(),
223  const key_equal& __eql = key_equal(),
224  const allocator_type& __a = allocator_type())
225  : _M_h(__l, __n, __hf, __eql, __a)
226  { }
227 
228  unordered_set(size_type __n, const allocator_type& __a)
229  : unordered_set(__n, hasher(), key_equal(), __a)
230  { }
231 
232  unordered_set(size_type __n, const hasher& __hf,
233  const allocator_type& __a)
234  : unordered_set(__n, __hf, key_equal(), __a)
235  { }
236 
237  template<typename _InputIterator>
238  unordered_set(_InputIterator __first, _InputIterator __last,
239  size_type __n,
240  const allocator_type& __a)
241  : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
242  { }
243 
244  template<typename _InputIterator>
245  unordered_set(_InputIterator __first, _InputIterator __last,
246  size_type __n, const hasher& __hf,
247  const allocator_type& __a)
248  : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
249  { }
250 
251  unordered_set(initializer_list<value_type> __l,
252  size_type __n,
253  const allocator_type& __a)
254  : unordered_set(__l, __n, hasher(), key_equal(), __a)
255  { }
256 
257  unordered_set(initializer_list<value_type> __l,
258  size_type __n, const hasher& __hf,
259  const allocator_type& __a)
260  : unordered_set(__l, __n, __hf, key_equal(), __a)
261  { }
262 
263  /// Copy assignment operator.
265  operator=(const unordered_set&) = default;
266 
267  /// Move assignment operator.
269  operator=(unordered_set&&) = default;
270 
271  /**
272  * @brief %Unordered_set list assignment operator.
273  * @param __l An initializer_list.
274  *
275  * This function fills an %unordered_set with copies of the elements in
276  * the initializer list @a __l.
277  *
278  * Note that the assignment completely changes the %unordered_set and
279  * that the resulting %unordered_set's size is the same as the number
280  * of elements assigned.
281  */
284  {
285  _M_h = __l;
286  return *this;
287  }
288 
289  /// Returns the allocator object used by the %unordered_set.
291  get_allocator() const noexcept
292  { return _M_h.get_allocator(); }
293 
294  // size and capacity:
295 
296  /// Returns true if the %unordered_set is empty.
297  _GLIBCXX_NODISCARD bool
298  empty() const noexcept
299  { return _M_h.empty(); }
300 
301  /// Returns the size of the %unordered_set.
302  size_type
303  size() const noexcept
304  { return _M_h.size(); }
305 
306  /// Returns the maximum size of the %unordered_set.
307  size_type
308  max_size() const noexcept
309  { return _M_h.max_size(); }
310 
311  // iterators.
312 
313  //@{
314  /**
315  * Returns a read-only (constant) iterator that points to the first
316  * element in the %unordered_set.
317  */
318  iterator
319  begin() noexcept
320  { return _M_h.begin(); }
321 
323  begin() const noexcept
324  { return _M_h.begin(); }
325  //@}
326 
327  //@{
328  /**
329  * Returns a read-only (constant) iterator that points one past the last
330  * element in the %unordered_set.
331  */
332  iterator
333  end() noexcept
334  { return _M_h.end(); }
335 
337  end() const noexcept
338  { return _M_h.end(); }
339  //@}
340 
341  /**
342  * Returns a read-only (constant) iterator that points to the first
343  * element in the %unordered_set.
344  */
346  cbegin() const noexcept
347  { return _M_h.begin(); }
348 
349  /**
350  * Returns a read-only (constant) iterator that points one past the last
351  * element in the %unordered_set.
352  */
354  cend() const noexcept
355  { return _M_h.end(); }
356 
357  // modifiers.
358 
359  /**
360  * @brief Attempts to build and insert an element into the
361  * %unordered_set.
362  * @param __args Arguments used to generate an element.
363  * @return A pair, of which the first element is an iterator that points
364  * to the possibly inserted element, and the second is a bool
365  * that is true if the element was actually inserted.
366  *
367  * This function attempts to build and insert an element into the
368  * %unordered_set. An %unordered_set relies on unique keys and thus an
369  * element is only inserted if it is not already present in the
370  * %unordered_set.
371  *
372  * Insertion requires amortized constant time.
373  */
374  template<typename... _Args>
376  emplace(_Args&&... __args)
377  { return _M_h.emplace(std::forward<_Args>(__args)...); }
378 
379  /**
380  * @brief Attempts to insert an element into the %unordered_set.
381  * @param __pos An iterator that serves as a hint as to where the
382  * element should be inserted.
383  * @param __args Arguments used to generate the element to be
384  * inserted.
385  * @return An iterator that points to the element with key equivalent to
386  * the one generated from @a __args (may or may not be the
387  * element itself).
388  *
389  * This function is not concerned about whether the insertion took place,
390  * and thus does not return a boolean like the single-argument emplace()
391  * does. Note that the first parameter is only a hint and can
392  * potentially improve the performance of the insertion process. A bad
393  * hint would cause no gains in efficiency.
394  *
395  * For more on @a hinting, see:
396  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
397  *
398  * Insertion requires amortized constant time.
399  */
400  template<typename... _Args>
401  iterator
402  emplace_hint(const_iterator __pos, _Args&&... __args)
403  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
404 
405  //@{
406  /**
407  * @brief Attempts to insert an element into the %unordered_set.
408  * @param __x Element to be inserted.
409  * @return A pair, of which the first element is an iterator that points
410  * to the possibly inserted element, and the second is a bool
411  * that is true if the element was actually inserted.
412  *
413  * This function attempts to insert an element into the %unordered_set.
414  * An %unordered_set relies on unique keys and thus an element is only
415  * inserted if it is not already present in the %unordered_set.
416  *
417  * Insertion requires amortized constant time.
418  */
420  insert(const value_type& __x)
421  { return _M_h.insert(__x); }
422 
425  { return _M_h.insert(std::move(__x)); }
426  //@}
427 
428  //@{
429  /**
430  * @brief Attempts to insert an element into the %unordered_set.
431  * @param __hint An iterator that serves as a hint as to where the
432  * element should be inserted.
433  * @param __x Element to be inserted.
434  * @return An iterator that points to the element with key of
435  * @a __x (may or may not be the element passed in).
436  *
437  * This function is not concerned about whether the insertion took place,
438  * and thus does not return a boolean like the single-argument insert()
439  * does. Note that the first parameter is only a hint and can
440  * potentially improve the performance of the insertion process. A bad
441  * hint would cause no gains in efficiency.
442  *
443  * For more on @a hinting, see:
444  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
445  *
446  * Insertion requires amortized constant.
447  */
448  iterator
449  insert(const_iterator __hint, const value_type& __x)
450  { return _M_h.insert(__hint, __x); }
451 
452  iterator
454  { return _M_h.insert(__hint, std::move(__x)); }
455  //@}
456 
457  /**
458  * @brief A template function that attempts to insert a range of
459  * elements.
460  * @param __first Iterator pointing to the start of the range to be
461  * inserted.
462  * @param __last Iterator pointing to the end of the range.
463  *
464  * Complexity similar to that of the range constructor.
465  */
466  template<typename _InputIterator>
467  void
468  insert(_InputIterator __first, _InputIterator __last)
469  { _M_h.insert(__first, __last); }
470 
471  /**
472  * @brief Attempts to insert a list of elements into the %unordered_set.
473  * @param __l A std::initializer_list<value_type> of elements
474  * to be inserted.
475  *
476  * Complexity similar to that of the range constructor.
477  */
478  void
480  { _M_h.insert(__l); }
481 
482 #if __cplusplus > 201402L
483  /// Extract a node.
484  node_type
485  extract(const_iterator __pos)
486  {
487  __glibcxx_assert(__pos != end());
488  return _M_h.extract(__pos);
489  }
490 
491  /// Extract a node.
492  node_type
493  extract(const key_type& __key)
494  { return _M_h.extract(__key); }
495 
496  /// Re-insert an extracted node.
497  insert_return_type
498  insert(node_type&& __nh)
499  { return _M_h._M_reinsert_node(std::move(__nh)); }
500 
501  /// Re-insert an extracted node.
502  iterator
503  insert(const_iterator, node_type&& __nh)
504  { return _M_h._M_reinsert_node(std::move(__nh)).position; }
505 #endif // C++17
506 
507  //@{
508  /**
509  * @brief Erases an element from an %unordered_set.
510  * @param __position An iterator pointing to the element to be erased.
511  * @return An iterator pointing to the element immediately following
512  * @a __position prior to the element being erased. If no such
513  * element exists, end() is returned.
514  *
515  * This function erases an element, pointed to by the given iterator,
516  * from an %unordered_set. Note that this function only erases the
517  * element, and that if the element is itself a pointer, the pointed-to
518  * memory is not touched in any way. Managing the pointer is the user's
519  * responsibility.
520  */
521  iterator
522  erase(const_iterator __position)
523  { return _M_h.erase(__position); }
524 
525  // LWG 2059.
526  iterator
527  erase(iterator __position)
528  { return _M_h.erase(__position); }
529  //@}
530 
531  /**
532  * @brief Erases elements according to the provided key.
533  * @param __x Key of element to be erased.
534  * @return The number of elements erased.
535  *
536  * This function erases all the elements located by the given key from
537  * an %unordered_set. For an %unordered_set the result of this function
538  * can only be 0 (not present) or 1 (present).
539  * Note that this function only erases the element, and that if
540  * the element is itself a pointer, the pointed-to memory is not touched
541  * in any way. Managing the pointer is the user's responsibility.
542  */
543  size_type
544  erase(const key_type& __x)
545  { return _M_h.erase(__x); }
546 
547  /**
548  * @brief Erases a [__first,__last) range of elements from an
549  * %unordered_set.
550  * @param __first Iterator pointing to the start of the range to be
551  * erased.
552  * @param __last Iterator pointing to the end of the range to
553  * be erased.
554  * @return The iterator @a __last.
555  *
556  * This function erases a sequence of elements from an %unordered_set.
557  * Note that this function only erases the element, and that if
558  * the element is itself a pointer, the pointed-to memory is not touched
559  * in any way. Managing the pointer is the user's responsibility.
560  */
561  iterator
563  { return _M_h.erase(__first, __last); }
564 
565  /**
566  * Erases all elements in an %unordered_set. Note that this function only
567  * erases the elements, and that if the elements themselves are pointers,
568  * the pointed-to memory is not touched in any way. Managing the pointer
569  * is the user's responsibility.
570  */
571  void
572  clear() noexcept
573  { _M_h.clear(); }
574 
575  /**
576  * @brief Swaps data with another %unordered_set.
577  * @param __x An %unordered_set of the same element and allocator
578  * types.
579  *
580  * This exchanges the elements between two sets in constant time.
581  * Note that the global std::swap() function is specialized such that
582  * std::swap(s1,s2) will feed to this function.
583  */
584  void
586  noexcept( noexcept(_M_h.swap(__x._M_h)) )
587  { _M_h.swap(__x._M_h); }
588 
589 #if __cplusplus > 201402L
590  template<typename, typename, typename>
591  friend class std::_Hash_merge_helper;
592 
593  template<typename _H2, typename _P2>
594  void
596  {
597  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
598  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
599  }
600 
601  template<typename _H2, typename _P2>
602  void
603  merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
604  { merge(__source); }
605 
606  template<typename _H2, typename _P2>
607  void
608  merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
609  {
610  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
611  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
612  }
613 
614  template<typename _H2, typename _P2>
615  void
616  merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
617  { merge(__source); }
618 #endif // C++17
619 
620  // observers.
621 
622  /// Returns the hash functor object with which the %unordered_set was
623  /// constructed.
624  hasher
626  { return _M_h.hash_function(); }
627 
628  /// Returns the key comparison object with which the %unordered_set was
629  /// constructed.
630  key_equal
631  key_eq() const
632  { return _M_h.key_eq(); }
633 
634  // lookup.
635 
636  //@{
637  /**
638  * @brief Tries to locate an element in an %unordered_set.
639  * @param __x Element to be located.
640  * @return Iterator pointing to sought-after element, or end() if not
641  * found.
642  *
643  * This function takes a key and tries to locate the element with which
644  * the key matches. If successful the function returns an iterator
645  * pointing to the sought after element. If unsuccessful it returns the
646  * past-the-end ( @c end() ) iterator.
647  */
648  iterator
649  find(const key_type& __x)
650  { return _M_h.find(__x); }
651 
653  find(const key_type& __x) const
654  { return _M_h.find(__x); }
655  //@}
656 
657  /**
658  * @brief Finds the number of elements.
659  * @param __x Element to located.
660  * @return Number of elements with specified key.
661  *
662  * This function only makes sense for unordered_multisets; for
663  * unordered_set the result will either be 0 (not present) or 1
664  * (present).
665  */
666  size_type
667  count(const key_type& __x) const
668  { return _M_h.count(__x); }
669 
670 #if __cplusplus > 201703L
671  /**
672  * @brief Finds whether an element with the given key exists.
673  * @param __x Key of elements to be located.
674  * @return True if there is any element with the specified key.
675  */
676  bool
677  contains(const key_type& __x) const
678  { return _M_h.find(__x) != _M_h.end(); }
679 #endif
680 
681  //@{
682  /**
683  * @brief Finds a subsequence matching given key.
684  * @param __x Key to be located.
685  * @return Pair of iterators that possibly points to the subsequence
686  * matching given key.
687  *
688  * This function probably only makes sense for multisets.
689  */
691  equal_range(const key_type& __x)
692  { return _M_h.equal_range(__x); }
693 
695  equal_range(const key_type& __x) const
696  { return _M_h.equal_range(__x); }
697  //@}
698 
699  // bucket interface.
700 
701  /// Returns the number of buckets of the %unordered_set.
702  size_type
703  bucket_count() const noexcept
704  { return _M_h.bucket_count(); }
705 
706  /// Returns the maximum number of buckets of the %unordered_set.
707  size_type
708  max_bucket_count() const noexcept
709  { return _M_h.max_bucket_count(); }
710 
711  /*
712  * @brief Returns the number of elements in a given bucket.
713  * @param __n A bucket index.
714  * @return The number of elements in the bucket.
715  */
716  size_type
717  bucket_size(size_type __n) const
718  { return _M_h.bucket_size(__n); }
719 
720  /*
721  * @brief Returns the bucket index of a given element.
722  * @param __key A key instance.
723  * @return The key bucket index.
724  */
725  size_type
726  bucket(const key_type& __key) const
727  { return _M_h.bucket(__key); }
728 
729  //@{
730  /**
731  * @brief Returns a read-only (constant) iterator pointing to the first
732  * bucket element.
733  * @param __n The bucket index.
734  * @return A read-only local iterator.
735  */
738  { return _M_h.begin(__n); }
739 
741  begin(size_type __n) const
742  { return _M_h.begin(__n); }
743 
745  cbegin(size_type __n) const
746  { return _M_h.cbegin(__n); }
747  //@}
748 
749  //@{
750  /**
751  * @brief Returns a read-only (constant) iterator pointing to one past
752  * the last bucket elements.
753  * @param __n The bucket index.
754  * @return A read-only local iterator.
755  */
758  { return _M_h.end(__n); }
759 
761  end(size_type __n) const
762  { return _M_h.end(__n); }
763 
765  cend(size_type __n) const
766  { return _M_h.cend(__n); }
767  //@}
768 
769  // hash policy.
770 
771  /// Returns the average number of elements per bucket.
772  float
773  load_factor() const noexcept
774  { return _M_h.load_factor(); }
775 
776  /// Returns a positive number that the %unordered_set tries to keep the
777  /// load factor less than or equal to.
778  float
779  max_load_factor() const noexcept
780  { return _M_h.max_load_factor(); }
781 
782  /**
783  * @brief Change the %unordered_set maximum load factor.
784  * @param __z The new maximum load factor.
785  */
786  void
787  max_load_factor(float __z)
788  { _M_h.max_load_factor(__z); }
789 
790  /**
791  * @brief May rehash the %unordered_set.
792  * @param __n The new number of buckets.
793  *
794  * Rehash will occur only if the new number of buckets respect the
795  * %unordered_set maximum load factor.
796  */
797  void
799  { _M_h.rehash(__n); }
800 
801  /**
802  * @brief Prepare the %unordered_set for a specified number of
803  * elements.
804  * @param __n Number of elements required.
805  *
806  * Same as rehash(ceil(n / max_load_factor())).
807  */
808  void
810  { _M_h.reserve(__n); }
811 
812  template<typename _Value1, typename _Hash1, typename _Pred1,
813  typename _Alloc1>
814  friend bool
817  };
818 
819 #if __cpp_deduction_guides >= 201606
820 
821  template<typename _InputIterator,
822  typename _Hash =
823  hash<typename iterator_traits<_InputIterator>::value_type>,
824  typename _Pred =
825  equal_to<typename iterator_traits<_InputIterator>::value_type>,
826  typename _Allocator =
827  allocator<typename iterator_traits<_InputIterator>::value_type>,
828  typename = _RequireInputIter<_InputIterator>,
829  typename = _RequireAllocator<_Allocator>>
830  unordered_set(_InputIterator, _InputIterator,
832  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
833  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
834  _Hash, _Pred, _Allocator>;
835 
836  template<typename _Tp, typename _Hash = hash<_Tp>,
837  typename _Pred = equal_to<_Tp>,
838  typename _Allocator = allocator<_Tp>,
839  typename = _RequireAllocator<_Allocator>>
840  unordered_set(initializer_list<_Tp>,
842  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
843  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
844 
845  template<typename _InputIterator, typename _Allocator,
846  typename = _RequireInputIter<_InputIterator>,
847  typename = _RequireAllocator<_Allocator>>
848  unordered_set(_InputIterator, _InputIterator,
849  unordered_set<int>::size_type, _Allocator)
851  hash<
852  typename iterator_traits<_InputIterator>::value_type>,
853  equal_to<
854  typename iterator_traits<_InputIterator>::value_type>,
855  _Allocator>;
856 
857  template<typename _InputIterator, typename _Hash, typename _Allocator,
858  typename = _RequireInputIter<_InputIterator>,
859  typename = _RequireAllocator<_Allocator>>
860  unordered_set(_InputIterator, _InputIterator,
862  _Hash, _Allocator)
864  _Hash,
865  equal_to<
866  typename iterator_traits<_InputIterator>::value_type>,
867  _Allocator>;
868 
869  template<typename _Tp, typename _Allocator,
870  typename = _RequireAllocator<_Allocator>>
871  unordered_set(initializer_list<_Tp>,
872  unordered_set<int>::size_type, _Allocator)
873  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
874 
875  template<typename _Tp, typename _Hash, typename _Allocator,
876  typename = _RequireAllocator<_Allocator>>
877  unordered_set(initializer_list<_Tp>,
878  unordered_set<int>::size_type, _Hash, _Allocator)
879  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
880 
881 #endif
882 
883  /**
884  * @brief A standard container composed of equivalent keys
885  * (possibly containing multiple of each key value) in which the
886  * elements' keys are the elements themselves.
887  *
888  * @ingroup unordered_associative_containers
889  *
890  * @tparam _Value Type of key objects.
891  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
892  * @tparam _Pred Predicate function object type, defaults
893  * to equal_to<_Value>.
894  * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
895  *
896  * Meets the requirements of a <a href="tables.html#65">container</a>, and
897  * <a href="tables.html#xx">unordered associative container</a>
898  *
899  * Base is _Hashtable, dispatched at compile time via template
900  * alias __umset_hashtable.
901  */
902  template<typename _Value,
903  typename _Hash = hash<_Value>,
904  typename _Pred = equal_to<_Value>,
905  typename _Alloc = allocator<_Value>>
906  class unordered_multiset
907  {
908  typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
909  _Hashtable _M_h;
910 
911  public:
912  // typedefs:
913  //@{
914  /// Public typedefs.
915  typedef typename _Hashtable::key_type key_type;
916  typedef typename _Hashtable::value_type value_type;
917  typedef typename _Hashtable::hasher hasher;
918  typedef typename _Hashtable::key_equal key_equal;
919  typedef typename _Hashtable::allocator_type allocator_type;
920  //@}
921 
922  //@{
923  /// Iterator-related typedefs.
924  typedef typename _Hashtable::pointer pointer;
925  typedef typename _Hashtable::const_pointer const_pointer;
926  typedef typename _Hashtable::reference reference;
927  typedef typename _Hashtable::const_reference const_reference;
928  typedef typename _Hashtable::iterator iterator;
929  typedef typename _Hashtable::const_iterator const_iterator;
930  typedef typename _Hashtable::local_iterator local_iterator;
931  typedef typename _Hashtable::const_local_iterator const_local_iterator;
932  typedef typename _Hashtable::size_type size_type;
933  typedef typename _Hashtable::difference_type difference_type;
934  //@}
935 
936 #if __cplusplus > 201402L
937  using node_type = typename _Hashtable::node_type;
938 #endif
939 
940  // construct/destroy/copy
941 
942  /// Default constructor.
943  unordered_multiset() = default;
944 
945  /**
946  * @brief Default constructor creates no elements.
947  * @param __n Minimal initial number of buckets.
948  * @param __hf A hash functor.
949  * @param __eql A key equality functor.
950  * @param __a An allocator object.
951  */
952  explicit
954  const hasher& __hf = hasher(),
955  const key_equal& __eql = key_equal(),
956  const allocator_type& __a = allocator_type())
957  : _M_h(__n, __hf, __eql, __a)
958  { }
959 
960  /**
961  * @brief Builds an %unordered_multiset from a range.
962  * @param __first An input iterator.
963  * @param __last An input iterator.
964  * @param __n Minimal initial number of buckets.
965  * @param __hf A hash functor.
966  * @param __eql A key equality functor.
967  * @param __a An allocator object.
968  *
969  * Create an %unordered_multiset consisting of copies of the elements
970  * from [__first,__last). This is linear in N (where N is
971  * distance(__first,__last)).
972  */
973  template<typename _InputIterator>
974  unordered_multiset(_InputIterator __first, _InputIterator __last,
975  size_type __n = 0,
976  const hasher& __hf = hasher(),
977  const key_equal& __eql = key_equal(),
978  const allocator_type& __a = allocator_type())
979  : _M_h(__first, __last, __n, __hf, __eql, __a)
980  { }
981 
982  /// Copy constructor.
983  unordered_multiset(const unordered_multiset&) = default;
984 
985  /// Move constructor.
987 
988  /**
989  * @brief Builds an %unordered_multiset from an initializer_list.
990  * @param __l An initializer_list.
991  * @param __n Minimal initial number of buckets.
992  * @param __hf A hash functor.
993  * @param __eql A key equality functor.
994  * @param __a An allocator object.
995  *
996  * Create an %unordered_multiset consisting of copies of the elements in
997  * the list. This is linear in N (where N is @a __l.size()).
998  */
1000  size_type __n = 0,
1001  const hasher& __hf = hasher(),
1002  const key_equal& __eql = key_equal(),
1003  const allocator_type& __a = allocator_type())
1004  : _M_h(__l, __n, __hf, __eql, __a)
1005  { }
1006 
1007  /// Copy assignment operator.
1009  operator=(const unordered_multiset&) = default;
1010 
1011  /// Move assignment operator.
1013  operator=(unordered_multiset&&) = default;
1014 
1015  /**
1016  * @brief Creates an %unordered_multiset with no elements.
1017  * @param __a An allocator object.
1018  */
1019  explicit
1021  : _M_h(__a)
1022  { }
1023 
1024  /*
1025  * @brief Copy constructor with allocator argument.
1026  * @param __uset Input %unordered_multiset to copy.
1027  * @param __a An allocator object.
1028  */
1029  unordered_multiset(const unordered_multiset& __umset,
1030  const allocator_type& __a)
1031  : _M_h(__umset._M_h, __a)
1032  { }
1033 
1034  /*
1035  * @brief Move constructor with allocator argument.
1036  * @param __umset Input %unordered_multiset to move.
1037  * @param __a An allocator object.
1038  */
1040  const allocator_type& __a)
1041  : _M_h(std::move(__umset._M_h), __a)
1042  { }
1043 
1045  : unordered_multiset(__n, hasher(), key_equal(), __a)
1046  { }
1047 
1048  unordered_multiset(size_type __n, const hasher& __hf,
1049  const allocator_type& __a)
1050  : unordered_multiset(__n, __hf, key_equal(), __a)
1051  { }
1052 
1053  template<typename _InputIterator>
1054  unordered_multiset(_InputIterator __first, _InputIterator __last,
1055  size_type __n,
1056  const allocator_type& __a)
1057  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1058  { }
1059 
1060  template<typename _InputIterator>
1061  unordered_multiset(_InputIterator __first, _InputIterator __last,
1062  size_type __n, const hasher& __hf,
1063  const allocator_type& __a)
1064  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1065  { }
1066 
1067  unordered_multiset(initializer_list<value_type> __l,
1068  size_type __n,
1069  const allocator_type& __a)
1070  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1071  { }
1072 
1073  unordered_multiset(initializer_list<value_type> __l,
1074  size_type __n, const hasher& __hf,
1075  const allocator_type& __a)
1076  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1077  { }
1078 
1079  /**
1080  * @brief %Unordered_multiset list assignment operator.
1081  * @param __l An initializer_list.
1082  *
1083  * This function fills an %unordered_multiset with copies of the elements
1084  * in the initializer list @a __l.
1085  *
1086  * Note that the assignment completely changes the %unordered_multiset
1087  * and that the resulting %unordered_multiset's size is the same as the
1088  * number of elements assigned.
1089  */
1092  {
1093  _M_h = __l;
1094  return *this;
1095  }
1096 
1097  /// Returns the allocator object used by the %unordered_multiset.
1099  get_allocator() const noexcept
1100  { return _M_h.get_allocator(); }
1101 
1102  // size and capacity:
1103 
1104  /// Returns true if the %unordered_multiset is empty.
1105  _GLIBCXX_NODISCARD bool
1106  empty() const noexcept
1107  { return _M_h.empty(); }
1108 
1109  /// Returns the size of the %unordered_multiset.
1110  size_type
1111  size() const noexcept
1112  { return _M_h.size(); }
1113 
1114  /// Returns the maximum size of the %unordered_multiset.
1115  size_type
1116  max_size() const noexcept
1117  { return _M_h.max_size(); }
1118 
1119  // iterators.
1120 
1121  //@{
1122  /**
1123  * Returns a read-only (constant) iterator that points to the first
1124  * element in the %unordered_multiset.
1125  */
1126  iterator
1127  begin() noexcept
1128  { return _M_h.begin(); }
1129 
1131  begin() const noexcept
1132  { return _M_h.begin(); }
1133  //@}
1134 
1135  //@{
1136  /**
1137  * Returns a read-only (constant) iterator that points one past the last
1138  * element in the %unordered_multiset.
1139  */
1140  iterator
1141  end() noexcept
1142  { return _M_h.end(); }
1143 
1145  end() const noexcept
1146  { return _M_h.end(); }
1147  //@}
1148 
1149  /**
1150  * Returns a read-only (constant) iterator that points to the first
1151  * element in the %unordered_multiset.
1152  */
1154  cbegin() const noexcept
1155  { return _M_h.begin(); }
1156 
1157  /**
1158  * Returns a read-only (constant) iterator that points one past the last
1159  * element in the %unordered_multiset.
1160  */
1162  cend() const noexcept
1163  { return _M_h.end(); }
1164 
1165  // modifiers.
1166 
1167  /**
1168  * @brief Builds and insert an element into the %unordered_multiset.
1169  * @param __args Arguments used to generate an element.
1170  * @return An iterator that points to the inserted element.
1171  *
1172  * Insertion requires amortized constant time.
1173  */
1174  template<typename... _Args>
1175  iterator
1176  emplace(_Args&&... __args)
1177  { return _M_h.emplace(std::forward<_Args>(__args)...); }
1178 
1179  /**
1180  * @brief Inserts an element into the %unordered_multiset.
1181  * @param __pos An iterator that serves as a hint as to where the
1182  * element should be inserted.
1183  * @param __args Arguments used to generate the element to be
1184  * inserted.
1185  * @return An iterator that points to the inserted element.
1186  *
1187  * Note that the first parameter is only a hint and can potentially
1188  * improve the performance of the insertion process. A bad hint would
1189  * cause no gains in efficiency.
1190  *
1191  * For more on @a hinting, see:
1192  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1193  *
1194  * Insertion requires amortized constant time.
1195  */
1196  template<typename... _Args>
1197  iterator
1198  emplace_hint(const_iterator __pos, _Args&&... __args)
1199  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1200 
1201  //@{
1202  /**
1203  * @brief Inserts an element into the %unordered_multiset.
1204  * @param __x Element to be inserted.
1205  * @return An iterator that points to the inserted element.
1206  *
1207  * Insertion requires amortized constant time.
1208  */
1209  iterator
1210  insert(const value_type& __x)
1211  { return _M_h.insert(__x); }
1212 
1213  iterator
1215  { return _M_h.insert(std::move(__x)); }
1216  //@}
1217 
1218  //@{
1219  /**
1220  * @brief Inserts an element into the %unordered_multiset.
1221  * @param __hint An iterator that serves as a hint as to where the
1222  * element should be inserted.
1223  * @param __x Element to be inserted.
1224  * @return An iterator that points to the inserted element.
1225  *
1226  * Note that the first parameter is only a hint and can potentially
1227  * improve the performance of the insertion process. A bad hint would
1228  * cause no gains in efficiency.
1229  *
1230  * For more on @a hinting, see:
1231  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1232  *
1233  * Insertion requires amortized constant.
1234  */
1235  iterator
1236  insert(const_iterator __hint, const value_type& __x)
1237  { return _M_h.insert(__hint, __x); }
1238 
1239  iterator
1241  { return _M_h.insert(__hint, std::move(__x)); }
1242  //@}
1243 
1244  /**
1245  * @brief A template function that inserts a range of elements.
1246  * @param __first Iterator pointing to the start of the range to be
1247  * inserted.
1248  * @param __last Iterator pointing to the end of the range.
1249  *
1250  * Complexity similar to that of the range constructor.
1251  */
1252  template<typename _InputIterator>
1253  void
1254  insert(_InputIterator __first, _InputIterator __last)
1255  { _M_h.insert(__first, __last); }
1256 
1257  /**
1258  * @brief Inserts a list of elements into the %unordered_multiset.
1259  * @param __l A std::initializer_list<value_type> of elements to be
1260  * inserted.
1261  *
1262  * Complexity similar to that of the range constructor.
1263  */
1264  void
1266  { _M_h.insert(__l); }
1267 
1268 #if __cplusplus > 201402L
1269  /// Extract a node.
1270  node_type
1271  extract(const_iterator __pos)
1272  {
1273  __glibcxx_assert(__pos != end());
1274  return _M_h.extract(__pos);
1275  }
1276 
1277  /// Extract a node.
1278  node_type
1279  extract(const key_type& __key)
1280  { return _M_h.extract(__key); }
1281 
1282  /// Re-insert an extracted node.
1283  iterator
1284  insert(node_type&& __nh)
1285  { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1286 
1287  /// Re-insert an extracted node.
1288  iterator
1289  insert(const_iterator __hint, node_type&& __nh)
1290  { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1291 #endif // C++17
1292 
1293  //@{
1294  /**
1295  * @brief Erases an element from an %unordered_multiset.
1296  * @param __position An iterator pointing to the element to be erased.
1297  * @return An iterator pointing to the element immediately following
1298  * @a __position prior to the element being erased. If no such
1299  * element exists, end() is returned.
1300  *
1301  * This function erases an element, pointed to by the given iterator,
1302  * from an %unordered_multiset.
1303  *
1304  * Note that this function only erases the element, and that if the
1305  * element is itself a pointer, the pointed-to memory is not touched in
1306  * any way. Managing the pointer is the user's responsibility.
1307  */
1308  iterator
1309  erase(const_iterator __position)
1310  { return _M_h.erase(__position); }
1311 
1312  // LWG 2059.
1313  iterator
1314  erase(iterator __position)
1315  { return _M_h.erase(__position); }
1316  //@}
1317 
1318 
1319  /**
1320  * @brief Erases elements according to the provided key.
1321  * @param __x Key of element to be erased.
1322  * @return The number of elements erased.
1323  *
1324  * This function erases all the elements located by the given key from
1325  * an %unordered_multiset.
1326  *
1327  * Note that this function only erases the element, and that if the
1328  * element is itself a pointer, the pointed-to memory is not touched in
1329  * any way. Managing the pointer is the user's responsibility.
1330  */
1331  size_type
1332  erase(const key_type& __x)
1333  { return _M_h.erase(__x); }
1334 
1335  /**
1336  * @brief Erases a [__first,__last) range of elements from an
1337  * %unordered_multiset.
1338  * @param __first Iterator pointing to the start of the range to be
1339  * erased.
1340  * @param __last Iterator pointing to the end of the range to
1341  * be erased.
1342  * @return The iterator @a __last.
1343  *
1344  * This function erases a sequence of elements from an
1345  * %unordered_multiset.
1346  *
1347  * Note that this function only erases the element, and that if
1348  * the element is itself a pointer, the pointed-to memory is not touched
1349  * in any way. Managing the pointer is the user's responsibility.
1350  */
1351  iterator
1353  { return _M_h.erase(__first, __last); }
1354 
1355  /**
1356  * Erases all elements in an %unordered_multiset.
1357  *
1358  * Note that this function only erases the elements, and that if the
1359  * elements themselves are pointers, the pointed-to memory is not touched
1360  * in any way. Managing the pointer is the user's responsibility.
1361  */
1362  void
1363  clear() noexcept
1364  { _M_h.clear(); }
1365 
1366  /**
1367  * @brief Swaps data with another %unordered_multiset.
1368  * @param __x An %unordered_multiset of the same element and allocator
1369  * types.
1370  *
1371  * This exchanges the elements between two sets in constant time.
1372  * Note that the global std::swap() function is specialized such that
1373  * std::swap(s1,s2) will feed to this function.
1374  */
1375  void
1377  noexcept( noexcept(_M_h.swap(__x._M_h)) )
1378  { _M_h.swap(__x._M_h); }
1379 
1380 #if __cplusplus > 201402L
1381  template<typename, typename, typename>
1382  friend class std::_Hash_merge_helper;
1383 
1384  template<typename _H2, typename _P2>
1385  void
1387  {
1388  using _Merge_helper
1389  = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1390  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1391  }
1392 
1393  template<typename _H2, typename _P2>
1394  void
1395  merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1396  { merge(__source); }
1397 
1398  template<typename _H2, typename _P2>
1399  void
1400  merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1401  {
1402  using _Merge_helper
1403  = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1404  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1405  }
1406 
1407  template<typename _H2, typename _P2>
1408  void
1409  merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1410  { merge(__source); }
1411 #endif // C++17
1412 
1413  // observers.
1414 
1415  /// Returns the hash functor object with which the %unordered_multiset
1416  /// was constructed.
1417  hasher
1419  { return _M_h.hash_function(); }
1420 
1421  /// Returns the key comparison object with which the %unordered_multiset
1422  /// was constructed.
1423  key_equal
1424  key_eq() const
1425  { return _M_h.key_eq(); }
1426 
1427  // lookup.
1428 
1429  //@{
1430  /**
1431  * @brief Tries to locate an element in an %unordered_multiset.
1432  * @param __x Element to be located.
1433  * @return Iterator pointing to sought-after element, or end() if not
1434  * found.
1435  *
1436  * This function takes a key and tries to locate the element with which
1437  * the key matches. If successful the function returns an iterator
1438  * pointing to the sought after element. If unsuccessful it returns the
1439  * past-the-end ( @c end() ) iterator.
1440  */
1441  iterator
1442  find(const key_type& __x)
1443  { return _M_h.find(__x); }
1444 
1446  find(const key_type& __x) const
1447  { return _M_h.find(__x); }
1448  //@}
1449 
1450  /**
1451  * @brief Finds the number of elements.
1452  * @param __x Element to located.
1453  * @return Number of elements with specified key.
1454  */
1455  size_type
1456  count(const key_type& __x) const
1457  { return _M_h.count(__x); }
1458 
1459 #if __cplusplus > 201703L
1460  /**
1461  * @brief Finds whether an element with the given key exists.
1462  * @param __x Key of elements to be located.
1463  * @return True if there is any element with the specified key.
1464  */
1465  bool
1466  contains(const key_type& __x) const
1467  { return _M_h.find(__x) != _M_h.end(); }
1468 #endif
1469 
1470  //@{
1471  /**
1472  * @brief Finds a subsequence matching given key.
1473  * @param __x Key to be located.
1474  * @return Pair of iterators that possibly points to the subsequence
1475  * matching given key.
1476  */
1478  equal_range(const key_type& __x)
1479  { return _M_h.equal_range(__x); }
1480 
1482  equal_range(const key_type& __x) const
1483  { return _M_h.equal_range(__x); }
1484  //@}
1485 
1486  // bucket interface.
1487 
1488  /// Returns the number of buckets of the %unordered_multiset.
1489  size_type
1490  bucket_count() const noexcept
1491  { return _M_h.bucket_count(); }
1492 
1493  /// Returns the maximum number of buckets of the %unordered_multiset.
1494  size_type
1495  max_bucket_count() const noexcept
1496  { return _M_h.max_bucket_count(); }
1497 
1498  /*
1499  * @brief Returns the number of elements in a given bucket.
1500  * @param __n A bucket index.
1501  * @return The number of elements in the bucket.
1502  */
1503  size_type
1504  bucket_size(size_type __n) const
1505  { return _M_h.bucket_size(__n); }
1506 
1507  /*
1508  * @brief Returns the bucket index of a given element.
1509  * @param __key A key instance.
1510  * @return The key bucket index.
1511  */
1512  size_type
1513  bucket(const key_type& __key) const
1514  { return _M_h.bucket(__key); }
1515 
1516  //@{
1517  /**
1518  * @brief Returns a read-only (constant) iterator pointing to the first
1519  * bucket element.
1520  * @param __n The bucket index.
1521  * @return A read-only local iterator.
1522  */
1525  { return _M_h.begin(__n); }
1526 
1528  begin(size_type __n) const
1529  { return _M_h.begin(__n); }
1530 
1532  cbegin(size_type __n) const
1533  { return _M_h.cbegin(__n); }
1534  //@}
1535 
1536  //@{
1537  /**
1538  * @brief Returns a read-only (constant) iterator pointing to one past
1539  * the last bucket elements.
1540  * @param __n The bucket index.
1541  * @return A read-only local iterator.
1542  */
1545  { return _M_h.end(__n); }
1546 
1548  end(size_type __n) const
1549  { return _M_h.end(__n); }
1550 
1552  cend(size_type __n) const
1553  { return _M_h.cend(__n); }
1554  //@}
1555 
1556  // hash policy.
1557 
1558  /// Returns the average number of elements per bucket.
1559  float
1560  load_factor() const noexcept
1561  { return _M_h.load_factor(); }
1562 
1563  /// Returns a positive number that the %unordered_multiset tries to keep the
1564  /// load factor less than or equal to.
1565  float
1566  max_load_factor() const noexcept
1567  { return _M_h.max_load_factor(); }
1568 
1569  /**
1570  * @brief Change the %unordered_multiset maximum load factor.
1571  * @param __z The new maximum load factor.
1572  */
1573  void
1574  max_load_factor(float __z)
1575  { _M_h.max_load_factor(__z); }
1576 
1577  /**
1578  * @brief May rehash the %unordered_multiset.
1579  * @param __n The new number of buckets.
1580  *
1581  * Rehash will occur only if the new number of buckets respect the
1582  * %unordered_multiset maximum load factor.
1583  */
1584  void
1586  { _M_h.rehash(__n); }
1587 
1588  /**
1589  * @brief Prepare the %unordered_multiset for a specified number of
1590  * elements.
1591  * @param __n Number of elements required.
1592  *
1593  * Same as rehash(ceil(n / max_load_factor())).
1594  */
1595  void
1597  { _M_h.reserve(__n); }
1598 
1599  template<typename _Value1, typename _Hash1, typename _Pred1,
1600  typename _Alloc1>
1601  friend bool
1604  };
1605 
1606 
1607 #if __cpp_deduction_guides >= 201606
1608 
1609  template<typename _InputIterator,
1610  typename _Hash =
1611  hash<typename iterator_traits<_InputIterator>::value_type>,
1612  typename _Pred =
1613  equal_to<typename iterator_traits<_InputIterator>::value_type>,
1614  typename _Allocator =
1615  allocator<typename iterator_traits<_InputIterator>::value_type>,
1616  typename = _RequireInputIter<_InputIterator>,
1617  typename = _RequireAllocator<_Allocator>>
1618  unordered_multiset(_InputIterator, _InputIterator,
1620  _Hash = _Hash(), _Pred = _Pred(),
1621  _Allocator = _Allocator())
1622  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1623  _Hash, _Pred, _Allocator>;
1624 
1625  template<typename _Tp, typename _Hash = hash<_Tp>,
1626  typename _Pred = equal_to<_Tp>,
1627  typename _Allocator = allocator<_Tp>,
1628  typename = _RequireAllocator<_Allocator>>
1629  unordered_multiset(initializer_list<_Tp>,
1631  _Hash = _Hash(), _Pred = _Pred(),
1632  _Allocator = _Allocator())
1633  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1634 
1635  template<typename _InputIterator, typename _Allocator,
1636  typename = _RequireInputIter<_InputIterator>,
1637  typename = _RequireAllocator<_Allocator>>
1638  unordered_multiset(_InputIterator, _InputIterator,
1641  hash<typename
1642  iterator_traits<_InputIterator>::value_type>,
1643  equal_to<typename
1644  iterator_traits<_InputIterator>::value_type>,
1645  _Allocator>;
1646 
1647  template<typename _InputIterator, typename _Hash, typename _Allocator,
1648  typename = _RequireInputIter<_InputIterator>,
1649  typename = _RequireAllocator<_Allocator>>
1650  unordered_multiset(_InputIterator, _InputIterator,
1652  _Hash, _Allocator)
1653  -> unordered_multiset<typename
1654  iterator_traits<_InputIterator>::value_type,
1655  _Hash,
1656  equal_to<
1657  typename
1658  iterator_traits<_InputIterator>::value_type>,
1659  _Allocator>;
1660 
1661  template<typename _Tp, typename _Allocator,
1662  typename = _RequireAllocator<_Allocator>>
1663  unordered_multiset(initializer_list<_Tp>,
1665  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1666 
1667  template<typename _Tp, typename _Hash, typename _Allocator,
1668  typename = _RequireAllocator<_Allocator>>
1669  unordered_multiset(initializer_list<_Tp>,
1670  unordered_multiset<int>::size_type, _Hash, _Allocator)
1671  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1672 
1673 #endif
1674 
1675  template<class _Value, class _Hash, class _Pred, class _Alloc>
1676  inline void
1677  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1678  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1679  noexcept(noexcept(__x.swap(__y)))
1680  { __x.swap(__y); }
1681 
1682  template<class _Value, class _Hash, class _Pred, class _Alloc>
1683  inline void
1684  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1685  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1686  noexcept(noexcept(__x.swap(__y)))
1687  { __x.swap(__y); }
1688 
1689  template<class _Value, class _Hash, class _Pred, class _Alloc>
1690  inline bool
1691  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1692  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1693  { return __x._M_h._M_equal(__y._M_h); }
1694 
1695  template<class _Value, class _Hash, class _Pred, class _Alloc>
1696  inline bool
1697  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1698  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1699  { return !(__x == __y); }
1700 
1701  template<class _Value, class _Hash, class _Pred, class _Alloc>
1702  inline bool
1703  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1704  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1705  { return __x._M_h._M_equal(__y._M_h); }
1706 
1707  template<class _Value, class _Hash, class _Pred, class _Alloc>
1708  inline bool
1709  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1710  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1711  { return !(__x == __y); }
1712 
1713 _GLIBCXX_END_NAMESPACE_CONTAINER
1714 
1715 #if __cplusplus > 201402L
1716  // Allow std::unordered_set access to internals of compatible sets.
1717  template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1718  typename _Hash2, typename _Eq2>
1719  struct _Hash_merge_helper<
1720  _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1721  {
1722  private:
1723  template<typename... _Tp>
1724  using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1725  template<typename... _Tp>
1726  using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1727 
1728  friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1729 
1730  static auto&
1731  _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1732  { return __set._M_h; }
1733 
1734  static auto&
1735  _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1736  { return __set._M_h; }
1737  };
1738 
1739  // Allow std::unordered_multiset access to internals of compatible sets.
1740  template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1741  typename _Hash2, typename _Eq2>
1742  struct _Hash_merge_helper<
1743  _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1744  _Hash2, _Eq2>
1745  {
1746  private:
1747  template<typename... _Tp>
1748  using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1749  template<typename... _Tp>
1750  using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1751 
1752  friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1753 
1754  static auto&
1755  _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1756  { return __set._M_h; }
1757 
1758  static auto&
1759  _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1760  { return __set._M_h; }
1761  };
1762 #endif // C++17
1763 
1764 _GLIBCXX_END_NAMESPACE_VERSION
1765 } // namespace std
1766 
1767 #endif /* _UNORDERED_SET_H */
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
float max_load_factor() const noexcept
Returns a positive number that the unordered_set tries to keep the load factor less than or equal to.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
void rehash(size_type __n)
May rehash the unordered_multiset.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
_Hashtable::value_type value_type
Public typedefs.
const_iterator cbegin() const noexcept
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
const_iterator cend() const noexcept
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:70
The standard allocator, as per [20.4].
Definition: allocator.h:112
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
void rehash(size_type __n)
May rehash the unordered_set.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
_Hashtable::allocator_type allocator_type
Public typedefs.
_Hashtable::key_equal key_equal
Public typedefs.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
size_type size() const noexcept
Returns the size of the unordered_set.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.
unordered_multiset(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from an initializer_list.
const_iterator end() const noexcept
_Hashtable::reference reference
Iterator-related typedefs.
void swap(unordered_multiset &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multiset.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
Primary class template hash.
Definition: system_error:142
_Hashtable::pointer pointer
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an unordered_set.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
ISO C++ entities toplevel namespace is std.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
initializer_list
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
unordered_set()=default
Default constructor.
float load_factor() const noexcept
Returns the average number of elements per bucket.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
iterator begin() noexcept
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
const_iterator end() const noexcept
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
_Hashtable::size_type size_type
Iterator-related typedefs.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
iterator end() noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
unordered_set(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from an initializer_list.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
void clear() noexcept
size_type count(const key_type &__x) const
Finds the number of elements.
_Hashtable::value_type value_type
Public typedefs.
unordered_set(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multiset.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the unordered_set.
size_type max_size() const noexcept
Returns the maximum size of the unordered_set.
unordered_set(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from a range.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
unordered_multiset(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::hasher hasher
Public typedefs.
iterator emplace(_Args &&... __args)
Builds and insert an element into the unordered_multiset.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_multiset is empty.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
iterator begin() noexcept
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
const_iterator cbegin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Inserts an element into the unordered_multiset.
const_iterator begin() const noexcept
float load_factor() const noexcept
Returns the average number of elements per bucket.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_set is empty.
_Hashtable::key_type key_type
Public typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to insert an element into the unordered_set.
_Hashtable::allocator_type allocator_type
Public typedefs.
_Hashtable::pointer pointer
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_set.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
One of the comparison functors.
Definition: stl_function.h:331
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
_Hashtable::reference reference
Iterator-related typedefs.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
const_iterator begin() const noexcept
iterator end() noexcept
iterator erase(iterator __position)
Erases an element from an unordered_multiset.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
const_iterator cend() const noexcept
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Common iterator class.
size_type size() const noexcept
Returns the size of the unordered_multiset.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::key_type key_type
Public typedefs.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
Default range hashing function: use division to fold a large number into the range [0,...
_Hashtable::iterator iterator
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:97
unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from a range.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset & operator=(const unordered_multiset &)=default
Copy assignment operator.
unordered_multiset()=default
Default constructor.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_Hashtable::size_type size_type
Iterator-related typedefs.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.