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