libstdc++
unordered_set.h
Go to the documentation of this file.
1 // unordered_set implementation -*- C++ -*-
2 
3 // Copyright (C) 2010-2018 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  : _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 
252  size_type __n,
253  const allocator_type& __a)
254  : unordered_set(__l, __n, hasher(), key_equal(), __a)
255  { }
256 
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.
290  allocator_type
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  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 
322  const_iterator
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 
336  const_iterator
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  */
345  const_iterator
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  */
353  const_iterator
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 
424  insert(value_type&& __x)
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
453  insert(const_iterator __hint, value_type&& __x)
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
562  erase(const_iterator __first, const_iterator __last)
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
604  { merge(__source); }
605 
606  template<typename _H2, typename _P2>
607  void
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
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 
652  const_iterator
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  //@{
671  /**
672  * @brief Finds a subsequence matching given key.
673  * @param __x Key to be located.
674  * @return Pair of iterators that possibly points to the subsequence
675  * matching given key.
676  *
677  * This function probably only makes sense for multisets.
678  */
680  equal_range(const key_type& __x)
681  { return _M_h.equal_range(__x); }
682 
684  equal_range(const key_type& __x) const
685  { return _M_h.equal_range(__x); }
686  //@}
687 
688  // bucket interface.
689 
690  /// Returns the number of buckets of the %unordered_set.
691  size_type
692  bucket_count() const noexcept
693  { return _M_h.bucket_count(); }
694 
695  /// Returns the maximum number of buckets of the %unordered_set.
696  size_type
697  max_bucket_count() const noexcept
698  { return _M_h.max_bucket_count(); }
699 
700  /*
701  * @brief Returns the number of elements in a given bucket.
702  * @param __n A bucket index.
703  * @return The number of elements in the bucket.
704  */
705  size_type
706  bucket_size(size_type __n) const
707  { return _M_h.bucket_size(__n); }
708 
709  /*
710  * @brief Returns the bucket index of a given element.
711  * @param __key A key instance.
712  * @return The key bucket index.
713  */
714  size_type
715  bucket(const key_type& __key) const
716  { return _M_h.bucket(__key); }
717 
718  //@{
719  /**
720  * @brief Returns a read-only (constant) iterator pointing to the first
721  * bucket element.
722  * @param __n The bucket index.
723  * @return A read-only local iterator.
724  */
725  local_iterator
726  begin(size_type __n)
727  { return _M_h.begin(__n); }
728 
729  const_local_iterator
730  begin(size_type __n) const
731  { return _M_h.begin(__n); }
732 
733  const_local_iterator
734  cbegin(size_type __n) const
735  { return _M_h.cbegin(__n); }
736  //@}
737 
738  //@{
739  /**
740  * @brief Returns a read-only (constant) iterator pointing to one past
741  * the last bucket elements.
742  * @param __n The bucket index.
743  * @return A read-only local iterator.
744  */
745  local_iterator
746  end(size_type __n)
747  { return _M_h.end(__n); }
748 
749  const_local_iterator
750  end(size_type __n) const
751  { return _M_h.end(__n); }
752 
753  const_local_iterator
754  cend(size_type __n) const
755  { return _M_h.cend(__n); }
756  //@}
757 
758  // hash policy.
759 
760  /// Returns the average number of elements per bucket.
761  float
762  load_factor() const noexcept
763  { return _M_h.load_factor(); }
764 
765  /// Returns a positive number that the %unordered_set tries to keep the
766  /// load factor less than or equal to.
767  float
768  max_load_factor() const noexcept
769  { return _M_h.max_load_factor(); }
770 
771  /**
772  * @brief Change the %unordered_set maximum load factor.
773  * @param __z The new maximum load factor.
774  */
775  void
776  max_load_factor(float __z)
777  { _M_h.max_load_factor(__z); }
778 
779  /**
780  * @brief May rehash the %unordered_set.
781  * @param __n The new number of buckets.
782  *
783  * Rehash will occur only if the new number of buckets respect the
784  * %unordered_set maximum load factor.
785  */
786  void
787  rehash(size_type __n)
788  { _M_h.rehash(__n); }
789 
790  /**
791  * @brief Prepare the %unordered_set for a specified number of
792  * elements.
793  * @param __n Number of elements required.
794  *
795  * Same as rehash(ceil(n / max_load_factor())).
796  */
797  void
798  reserve(size_type __n)
799  { _M_h.reserve(__n); }
800 
801  template<typename _Value1, typename _Hash1, typename _Pred1,
802  typename _Alloc1>
803  friend bool
806  };
807 
808 #if __cpp_deduction_guides >= 201606
809 
810  template<typename _InputIterator,
811  typename _Hash =
813  typename _Pred =
815  typename _Allocator =
817  typename = _RequireInputIter<_InputIterator>,
818  typename = _RequireAllocator<_Allocator>>
819  unordered_set(_InputIterator, _InputIterator,
821  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
822  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
823  _Hash, _Pred, _Allocator>;
824 
825  template<typename _Tp, typename _Hash = hash<_Tp>,
826  typename _Pred = equal_to<_Tp>,
827  typename _Allocator = allocator<_Tp>,
828  typename = _RequireAllocator<_Allocator>>
831  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
833 
834  template<typename _InputIterator, typename _Allocator,
835  typename = _RequireInputIter<_InputIterator>,
836  typename = _RequireAllocator<_Allocator>>
837  unordered_set(_InputIterator, _InputIterator,
838  unordered_set<int>::size_type, _Allocator)
840  hash<
841  typename iterator_traits<_InputIterator>::value_type>,
842  equal_to<
843  typename iterator_traits<_InputIterator>::value_type>,
844  _Allocator>;
845 
846  template<typename _InputIterator, typename _Hash, typename _Allocator,
847  typename = _RequireInputIter<_InputIterator>,
848  typename = _RequireAllocator<_Allocator>>
849  unordered_set(_InputIterator, _InputIterator,
851  _Hash, _Allocator)
853  _Hash,
854  equal_to<
855  typename iterator_traits<_InputIterator>::value_type>,
856  _Allocator>;
857 
858  template<typename _Tp, typename _Allocator,
859  typename = _RequireAllocator<_Allocator>>
861  unordered_set<int>::size_type, _Allocator)
863 
864  template<typename _Tp, typename _Hash, typename _Allocator,
865  typename = _RequireAllocator<_Allocator>>
867  unordered_set<int>::size_type, _Hash, _Allocator)
869 
870 #endif
871 
872  /**
873  * @brief A standard container composed of equivalent keys
874  * (possibly containing multiple of each key value) in which the
875  * elements' keys are the elements themselves.
876  *
877  * @ingroup unordered_associative_containers
878  *
879  * @tparam _Value Type of key objects.
880  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
881  * @tparam _Pred Predicate function object type, defaults
882  * to equal_to<_Value>.
883  * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
884  *
885  * Meets the requirements of a <a href="tables.html#65">container</a>, and
886  * <a href="tables.html#xx">unordered associative container</a>
887  *
888  * Base is _Hashtable, dispatched at compile time via template
889  * alias __umset_hashtable.
890  */
891  template<typename _Value,
892  typename _Hash = hash<_Value>,
893  typename _Pred = equal_to<_Value>,
894  typename _Alloc = allocator<_Value>>
895  class unordered_multiset
896  {
898  _Hashtable _M_h;
899 
900  public:
901  // typedefs:
902  //@{
903  /// Public typedefs.
904  typedef typename _Hashtable::key_type key_type;
905  typedef typename _Hashtable::value_type value_type;
906  typedef typename _Hashtable::hasher hasher;
907  typedef typename _Hashtable::key_equal key_equal;
908  typedef typename _Hashtable::allocator_type allocator_type;
909  //@}
910 
911  //@{
912  /// Iterator-related typedefs.
913  typedef typename _Hashtable::pointer pointer;
914  typedef typename _Hashtable::const_pointer const_pointer;
915  typedef typename _Hashtable::reference reference;
916  typedef typename _Hashtable::const_reference const_reference;
917  typedef typename _Hashtable::iterator iterator;
918  typedef typename _Hashtable::const_iterator const_iterator;
919  typedef typename _Hashtable::local_iterator local_iterator;
920  typedef typename _Hashtable::const_local_iterator const_local_iterator;
921  typedef typename _Hashtable::size_type size_type;
922  typedef typename _Hashtable::difference_type difference_type;
923  //@}
924 
925 #if __cplusplus > 201402L
926  using node_type = typename _Hashtable::node_type;
927 #endif
928 
929  // construct/destroy/copy
930 
931  /// Default constructor.
932  unordered_multiset() = default;
933 
934  /**
935  * @brief Default constructor creates no elements.
936  * @param __n Minimal initial number of buckets.
937  * @param __hf A hash functor.
938  * @param __eql A key equality functor.
939  * @param __a An allocator object.
940  */
941  explicit
942  unordered_multiset(size_type __n,
943  const hasher& __hf = hasher(),
944  const key_equal& __eql = key_equal(),
945  const allocator_type& __a = allocator_type())
946  : _M_h(__n, __hf, __eql, __a)
947  { }
948 
949  /**
950  * @brief Builds an %unordered_multiset from a range.
951  * @param __first An input iterator.
952  * @param __last An input iterator.
953  * @param __n Minimal initial number of buckets.
954  * @param __hf A hash functor.
955  * @param __eql A key equality functor.
956  * @param __a An allocator object.
957  *
958  * Create an %unordered_multiset consisting of copies of the elements
959  * from [__first,__last). This is linear in N (where N is
960  * distance(__first,__last)).
961  */
962  template<typename _InputIterator>
963  unordered_multiset(_InputIterator __first, _InputIterator __last,
964  size_type __n = 0,
965  const hasher& __hf = hasher(),
966  const key_equal& __eql = key_equal(),
967  const allocator_type& __a = allocator_type())
968  : _M_h(__first, __last, __n, __hf, __eql, __a)
969  { }
970 
971  /// Copy constructor.
972  unordered_multiset(const unordered_multiset&) = default;
973 
974  /// Move constructor.
976 
977  /**
978  * @brief Builds an %unordered_multiset from an initializer_list.
979  * @param __l An initializer_list.
980  * @param __n Minimal initial number of buckets.
981  * @param __hf A hash functor.
982  * @param __eql A key equality functor.
983  * @param __a An allocator object.
984  *
985  * Create an %unordered_multiset consisting of copies of the elements in
986  * the list. This is linear in N (where N is @a __l.size()).
987  */
989  size_type __n = 0,
990  const hasher& __hf = hasher(),
991  const key_equal& __eql = key_equal(),
992  const allocator_type& __a = allocator_type())
993  : _M_h(__l, __n, __hf, __eql, __a)
994  { }
995 
996  /// Copy assignment operator.
998  operator=(const unordered_multiset&) = default;
999 
1000  /// Move assignment operator.
1002  operator=(unordered_multiset&&) = default;
1003 
1004  /**
1005  * @brief Creates an %unordered_multiset with no elements.
1006  * @param __a An allocator object.
1007  */
1008  explicit
1009  unordered_multiset(const allocator_type& __a)
1010  : _M_h(__a)
1011  { }
1012 
1013  /*
1014  * @brief Copy constructor with allocator argument.
1015  * @param __uset Input %unordered_multiset to copy.
1016  * @param __a An allocator object.
1017  */
1018  unordered_multiset(const unordered_multiset& __umset,
1019  const allocator_type& __a)
1020  : _M_h(__umset._M_h, __a)
1021  { }
1022 
1023  /*
1024  * @brief Move constructor with allocator argument.
1025  * @param __umset Input %unordered_multiset to move.
1026  * @param __a An allocator object.
1027  */
1029  const allocator_type& __a)
1030  : _M_h(std::move(__umset._M_h), __a)
1031  { }
1032 
1033  unordered_multiset(size_type __n, const allocator_type& __a)
1034  : unordered_multiset(__n, hasher(), key_equal(), __a)
1035  { }
1036 
1037  unordered_multiset(size_type __n, const hasher& __hf,
1038  const allocator_type& __a)
1039  : unordered_multiset(__n, __hf, key_equal(), __a)
1040  { }
1041 
1042  template<typename _InputIterator>
1043  unordered_multiset(_InputIterator __first, _InputIterator __last,
1044  size_type __n,
1045  const allocator_type& __a)
1046  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1047  { }
1048 
1049  template<typename _InputIterator>
1050  unordered_multiset(_InputIterator __first, _InputIterator __last,
1051  size_type __n, const hasher& __hf,
1052  const allocator_type& __a)
1053  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1054  { }
1055 
1057  size_type __n,
1058  const allocator_type& __a)
1059  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1060  { }
1061 
1063  size_type __n, const hasher& __hf,
1064  const allocator_type& __a)
1065  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1066  { }
1067 
1068  /**
1069  * @brief %Unordered_multiset list assignment operator.
1070  * @param __l An initializer_list.
1071  *
1072  * This function fills an %unordered_multiset with copies of the elements
1073  * in the initializer list @a __l.
1074  *
1075  * Note that the assignment completely changes the %unordered_multiset
1076  * and that the resulting %unordered_multiset's size is the same as the
1077  * number of elements assigned.
1078  */
1081  {
1082  _M_h = __l;
1083  return *this;
1084  }
1085 
1086  /// Returns the allocator object used by the %unordered_multiset.
1087  allocator_type
1088  get_allocator() const noexcept
1089  { return _M_h.get_allocator(); }
1090 
1091  // size and capacity:
1092 
1093  /// Returns true if the %unordered_multiset is empty.
1094  bool
1095  empty() const noexcept
1096  { return _M_h.empty(); }
1097 
1098  /// Returns the size of the %unordered_multiset.
1099  size_type
1100  size() const noexcept
1101  { return _M_h.size(); }
1102 
1103  /// Returns the maximum size of the %unordered_multiset.
1104  size_type
1105  max_size() const noexcept
1106  { return _M_h.max_size(); }
1107 
1108  // iterators.
1109 
1110  //@{
1111  /**
1112  * Returns a read-only (constant) iterator that points to the first
1113  * element in the %unordered_multiset.
1114  */
1115  iterator
1116  begin() noexcept
1117  { return _M_h.begin(); }
1118 
1119  const_iterator
1120  begin() const noexcept
1121  { return _M_h.begin(); }
1122  //@}
1123 
1124  //@{
1125  /**
1126  * Returns a read-only (constant) iterator that points one past the last
1127  * element in the %unordered_multiset.
1128  */
1129  iterator
1130  end() noexcept
1131  { return _M_h.end(); }
1132 
1133  const_iterator
1134  end() const noexcept
1135  { return _M_h.end(); }
1136  //@}
1137 
1138  /**
1139  * Returns a read-only (constant) iterator that points to the first
1140  * element in the %unordered_multiset.
1141  */
1142  const_iterator
1143  cbegin() const noexcept
1144  { return _M_h.begin(); }
1145 
1146  /**
1147  * Returns a read-only (constant) iterator that points one past the last
1148  * element in the %unordered_multiset.
1149  */
1150  const_iterator
1151  cend() const noexcept
1152  { return _M_h.end(); }
1153 
1154  // modifiers.
1155 
1156  /**
1157  * @brief Builds and insert an element into the %unordered_multiset.
1158  * @param __args Arguments used to generate an element.
1159  * @return An iterator that points to the inserted element.
1160  *
1161  * Insertion requires amortized constant time.
1162  */
1163  template<typename... _Args>
1164  iterator
1165  emplace(_Args&&... __args)
1166  { return _M_h.emplace(std::forward<_Args>(__args)...); }
1167 
1168  /**
1169  * @brief Inserts an element into the %unordered_multiset.
1170  * @param __pos An iterator that serves as a hint as to where the
1171  * element should be inserted.
1172  * @param __args Arguments used to generate the element to be
1173  * inserted.
1174  * @return An iterator that points to the inserted element.
1175  *
1176  * Note that the first parameter is only a hint and can potentially
1177  * improve the performance of the insertion process. A bad hint would
1178  * cause no gains in efficiency.
1179  *
1180  * For more on @a hinting, see:
1181  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1182  *
1183  * Insertion requires amortized constant time.
1184  */
1185  template<typename... _Args>
1186  iterator
1187  emplace_hint(const_iterator __pos, _Args&&... __args)
1188  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1189 
1190  //@{
1191  /**
1192  * @brief Inserts an element into the %unordered_multiset.
1193  * @param __x Element to be inserted.
1194  * @return An iterator that points to the inserted element.
1195  *
1196  * Insertion requires amortized constant time.
1197  */
1198  iterator
1199  insert(const value_type& __x)
1200  { return _M_h.insert(__x); }
1201 
1202  iterator
1203  insert(value_type&& __x)
1204  { return _M_h.insert(std::move(__x)); }
1205  //@}
1206 
1207  //@{
1208  /**
1209  * @brief Inserts an element into the %unordered_multiset.
1210  * @param __hint An iterator that serves as a hint as to where the
1211  * element should be inserted.
1212  * @param __x Element to be inserted.
1213  * @return An iterator that points to the inserted element.
1214  *
1215  * Note that the first parameter is only a hint and can potentially
1216  * improve the performance of the insertion process. A bad hint would
1217  * cause no gains in efficiency.
1218  *
1219  * For more on @a hinting, see:
1220  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1221  *
1222  * Insertion requires amortized constant.
1223  */
1224  iterator
1225  insert(const_iterator __hint, const value_type& __x)
1226  { return _M_h.insert(__hint, __x); }
1227 
1228  iterator
1229  insert(const_iterator __hint, value_type&& __x)
1230  { return _M_h.insert(__hint, std::move(__x)); }
1231  //@}
1232 
1233  /**
1234  * @brief A template function that inserts a range of elements.
1235  * @param __first Iterator pointing to the start of the range to be
1236  * inserted.
1237  * @param __last Iterator pointing to the end of the range.
1238  *
1239  * Complexity similar to that of the range constructor.
1240  */
1241  template<typename _InputIterator>
1242  void
1243  insert(_InputIterator __first, _InputIterator __last)
1244  { _M_h.insert(__first, __last); }
1245 
1246  /**
1247  * @brief Inserts a list of elements into the %unordered_multiset.
1248  * @param __l A std::initializer_list<value_type> of elements to be
1249  * inserted.
1250  *
1251  * Complexity similar to that of the range constructor.
1252  */
1253  void
1255  { _M_h.insert(__l); }
1256 
1257 #if __cplusplus > 201402L
1258  /// Extract a node.
1259  node_type
1260  extract(const_iterator __pos)
1261  {
1262  __glibcxx_assert(__pos != end());
1263  return _M_h.extract(__pos);
1264  }
1265 
1266  /// Extract a node.
1267  node_type
1268  extract(const key_type& __key)
1269  { return _M_h.extract(__key); }
1270 
1271  /// Re-insert an extracted node.
1272  iterator
1273  insert(node_type&& __nh)
1274  { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1275 
1276  /// Re-insert an extracted node.
1277  iterator
1278  insert(const_iterator __hint, node_type&& __nh)
1279  { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1280 #endif // C++17
1281 
1282  //@{
1283  /**
1284  * @brief Erases an element from an %unordered_multiset.
1285  * @param __position An iterator pointing to the element to be erased.
1286  * @return An iterator pointing to the element immediately following
1287  * @a __position prior to the element being erased. If no such
1288  * element exists, end() is returned.
1289  *
1290  * This function erases an element, pointed to by the given iterator,
1291  * from an %unordered_multiset.
1292  *
1293  * Note that this function only erases the element, and that if the
1294  * element is itself a pointer, the pointed-to memory is not touched in
1295  * any way. Managing the pointer is the user's responsibility.
1296  */
1297  iterator
1298  erase(const_iterator __position)
1299  { return _M_h.erase(__position); }
1300 
1301  // LWG 2059.
1302  iterator
1303  erase(iterator __position)
1304  { return _M_h.erase(__position); }
1305  //@}
1306 
1307 
1308  /**
1309  * @brief Erases elements according to the provided key.
1310  * @param __x Key of element to be erased.
1311  * @return The number of elements erased.
1312  *
1313  * This function erases all the elements located by the given key from
1314  * an %unordered_multiset.
1315  *
1316  * Note that this function only erases the element, and that if the
1317  * element is itself a pointer, the pointed-to memory is not touched in
1318  * any way. Managing the pointer is the user's responsibility.
1319  */
1320  size_type
1321  erase(const key_type& __x)
1322  { return _M_h.erase(__x); }
1323 
1324  /**
1325  * @brief Erases a [__first,__last) range of elements from an
1326  * %unordered_multiset.
1327  * @param __first Iterator pointing to the start of the range to be
1328  * erased.
1329  * @param __last Iterator pointing to the end of the range to
1330  * be erased.
1331  * @return The iterator @a __last.
1332  *
1333  * This function erases a sequence of elements from an
1334  * %unordered_multiset.
1335  *
1336  * Note that this function only erases the element, and that if
1337  * the element is itself a pointer, the pointed-to memory is not touched
1338  * in any way. Managing the pointer is the user's responsibility.
1339  */
1340  iterator
1341  erase(const_iterator __first, const_iterator __last)
1342  { return _M_h.erase(__first, __last); }
1343 
1344  /**
1345  * Erases all elements in an %unordered_multiset.
1346  *
1347  * Note that this function only erases the elements, and that if the
1348  * elements themselves are pointers, the pointed-to memory is not touched
1349  * in any way. Managing the pointer is the user's responsibility.
1350  */
1351  void
1352  clear() noexcept
1353  { _M_h.clear(); }
1354 
1355  /**
1356  * @brief Swaps data with another %unordered_multiset.
1357  * @param __x An %unordered_multiset of the same element and allocator
1358  * types.
1359  *
1360  * This exchanges the elements between two sets in constant time.
1361  * Note that the global std::swap() function is specialized such that
1362  * std::swap(s1,s2) will feed to this function.
1363  */
1364  void
1366  noexcept( noexcept(_M_h.swap(__x._M_h)) )
1367  { _M_h.swap(__x._M_h); }
1368 
1369 #if __cplusplus > 201402L
1370  template<typename, typename, typename>
1371  friend class std::_Hash_merge_helper;
1372 
1373  template<typename _H2, typename _P2>
1374  void
1376  {
1377  using _Merge_helper
1378  = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1379  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1380  }
1381 
1382  template<typename _H2, typename _P2>
1383  void
1385  { merge(__source); }
1386 
1387  template<typename _H2, typename _P2>
1388  void
1390  {
1391  using _Merge_helper
1392  = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1393  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1394  }
1395 
1396  template<typename _H2, typename _P2>
1397  void
1398  merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1399  { merge(__source); }
1400 #endif // C++17
1401 
1402  // observers.
1403 
1404  /// Returns the hash functor object with which the %unordered_multiset
1405  /// was constructed.
1406  hasher
1408  { return _M_h.hash_function(); }
1409 
1410  /// Returns the key comparison object with which the %unordered_multiset
1411  /// was constructed.
1412  key_equal
1413  key_eq() const
1414  { return _M_h.key_eq(); }
1415 
1416  // lookup.
1417 
1418  //@{
1419  /**
1420  * @brief Tries to locate an element in an %unordered_multiset.
1421  * @param __x Element to be located.
1422  * @return Iterator pointing to sought-after element, or end() if not
1423  * found.
1424  *
1425  * This function takes a key and tries to locate the element with which
1426  * the key matches. If successful the function returns an iterator
1427  * pointing to the sought after element. If unsuccessful it returns the
1428  * past-the-end ( @c end() ) iterator.
1429  */
1430  iterator
1431  find(const key_type& __x)
1432  { return _M_h.find(__x); }
1433 
1434  const_iterator
1435  find(const key_type& __x) const
1436  { return _M_h.find(__x); }
1437  //@}
1438 
1439  /**
1440  * @brief Finds the number of elements.
1441  * @param __x Element to located.
1442  * @return Number of elements with specified key.
1443  */
1444  size_type
1445  count(const key_type& __x) const
1446  { return _M_h.count(__x); }
1447 
1448  //@{
1449  /**
1450  * @brief Finds a subsequence matching given key.
1451  * @param __x Key to be located.
1452  * @return Pair of iterators that possibly points to the subsequence
1453  * matching given key.
1454  */
1456  equal_range(const key_type& __x)
1457  { return _M_h.equal_range(__x); }
1458 
1460  equal_range(const key_type& __x) const
1461  { return _M_h.equal_range(__x); }
1462  //@}
1463 
1464  // bucket interface.
1465 
1466  /// Returns the number of buckets of the %unordered_multiset.
1467  size_type
1468  bucket_count() const noexcept
1469  { return _M_h.bucket_count(); }
1470 
1471  /// Returns the maximum number of buckets of the %unordered_multiset.
1472  size_type
1473  max_bucket_count() const noexcept
1474  { return _M_h.max_bucket_count(); }
1475 
1476  /*
1477  * @brief Returns the number of elements in a given bucket.
1478  * @param __n A bucket index.
1479  * @return The number of elements in the bucket.
1480  */
1481  size_type
1482  bucket_size(size_type __n) const
1483  { return _M_h.bucket_size(__n); }
1484 
1485  /*
1486  * @brief Returns the bucket index of a given element.
1487  * @param __key A key instance.
1488  * @return The key bucket index.
1489  */
1490  size_type
1491  bucket(const key_type& __key) const
1492  { return _M_h.bucket(__key); }
1493 
1494  //@{
1495  /**
1496  * @brief Returns a read-only (constant) iterator pointing to the first
1497  * bucket element.
1498  * @param __n The bucket index.
1499  * @return A read-only local iterator.
1500  */
1501  local_iterator
1502  begin(size_type __n)
1503  { return _M_h.begin(__n); }
1504 
1505  const_local_iterator
1506  begin(size_type __n) const
1507  { return _M_h.begin(__n); }
1508 
1509  const_local_iterator
1510  cbegin(size_type __n) const
1511  { return _M_h.cbegin(__n); }
1512  //@}
1513 
1514  //@{
1515  /**
1516  * @brief Returns a read-only (constant) iterator pointing to one past
1517  * the last bucket elements.
1518  * @param __n The bucket index.
1519  * @return A read-only local iterator.
1520  */
1521  local_iterator
1522  end(size_type __n)
1523  { return _M_h.end(__n); }
1524 
1525  const_local_iterator
1526  end(size_type __n) const
1527  { return _M_h.end(__n); }
1528 
1529  const_local_iterator
1530  cend(size_type __n) const
1531  { return _M_h.cend(__n); }
1532  //@}
1533 
1534  // hash policy.
1535 
1536  /// Returns the average number of elements per bucket.
1537  float
1538  load_factor() const noexcept
1539  { return _M_h.load_factor(); }
1540 
1541  /// Returns a positive number that the %unordered_multiset tries to keep the
1542  /// load factor less than or equal to.
1543  float
1544  max_load_factor() const noexcept
1545  { return _M_h.max_load_factor(); }
1546 
1547  /**
1548  * @brief Change the %unordered_multiset maximum load factor.
1549  * @param __z The new maximum load factor.
1550  */
1551  void
1552  max_load_factor(float __z)
1553  { _M_h.max_load_factor(__z); }
1554 
1555  /**
1556  * @brief May rehash the %unordered_multiset.
1557  * @param __n The new number of buckets.
1558  *
1559  * Rehash will occur only if the new number of buckets respect the
1560  * %unordered_multiset maximum load factor.
1561  */
1562  void
1563  rehash(size_type __n)
1564  { _M_h.rehash(__n); }
1565 
1566  /**
1567  * @brief Prepare the %unordered_multiset for a specified number of
1568  * elements.
1569  * @param __n Number of elements required.
1570  *
1571  * Same as rehash(ceil(n / max_load_factor())).
1572  */
1573  void
1574  reserve(size_type __n)
1575  { _M_h.reserve(__n); }
1576 
1577  template<typename _Value1, typename _Hash1, typename _Pred1,
1578  typename _Alloc1>
1579  friend bool
1582  };
1583 
1584 
1585 #if __cpp_deduction_guides >= 201606
1586 
1587  template<typename _InputIterator,
1588  typename _Hash =
1590  typename _Pred =
1592  typename _Allocator =
1594  typename = _RequireInputIter<_InputIterator>,
1595  typename = _RequireAllocator<_Allocator>>
1596  unordered_multiset(_InputIterator, _InputIterator,
1598  _Hash = _Hash(), _Pred = _Pred(),
1599  _Allocator = _Allocator())
1600  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1601  _Hash, _Pred, _Allocator>;
1602 
1603  template<typename _Tp, typename _Hash = hash<_Tp>,
1604  typename _Pred = equal_to<_Tp>,
1605  typename _Allocator = allocator<_Tp>,
1606  typename = _RequireAllocator<_Allocator>>
1609  _Hash = _Hash(), _Pred = _Pred(),
1610  _Allocator = _Allocator())
1612 
1613  template<typename _InputIterator, typename _Allocator,
1614  typename = _RequireInputIter<_InputIterator>,
1615  typename = _RequireAllocator<_Allocator>>
1616  unordered_multiset(_InputIterator, _InputIterator,
1619  hash<typename
1620  iterator_traits<_InputIterator>::value_type>,
1621  equal_to<typename
1622  iterator_traits<_InputIterator>::value_type>,
1623  _Allocator>;
1624 
1625  template<typename _InputIterator, typename _Hash, typename _Allocator,
1626  typename = _RequireInputIter<_InputIterator>,
1627  typename = _RequireAllocator<_Allocator>>
1628  unordered_multiset(_InputIterator, _InputIterator,
1630  _Hash, _Allocator)
1631  -> unordered_multiset<typename
1632  iterator_traits<_InputIterator>::value_type,
1633  _Hash,
1634  equal_to<
1635  typename
1636  iterator_traits<_InputIterator>::value_type>,
1637  _Allocator>;
1638 
1639  template<typename _Tp, typename _Allocator,
1640  typename = _RequireAllocator<_Allocator>>
1643  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1644 
1645  template<typename _Tp, typename _Hash, typename _Allocator,
1646  typename = _RequireAllocator<_Allocator>>
1648  unordered_multiset<int>::size_type, _Hash, _Allocator)
1650 
1651 #endif
1652 
1653  template<class _Value, class _Hash, class _Pred, class _Alloc>
1654  inline void
1657  noexcept(noexcept(__x.swap(__y)))
1658  { __x.swap(__y); }
1659 
1660  template<class _Value, class _Hash, class _Pred, class _Alloc>
1661  inline void
1664  noexcept(noexcept(__x.swap(__y)))
1665  { __x.swap(__y); }
1666 
1667  template<class _Value, class _Hash, class _Pred, class _Alloc>
1668  inline bool
1669  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1671  { return __x._M_h._M_equal(__y._M_h); }
1672 
1673  template<class _Value, class _Hash, class _Pred, class _Alloc>
1674  inline bool
1675  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1677  { return !(__x == __y); }
1678 
1679  template<class _Value, class _Hash, class _Pred, class _Alloc>
1680  inline bool
1683  { return __x._M_h._M_equal(__y._M_h); }
1684 
1685  template<class _Value, class _Hash, class _Pred, class _Alloc>
1686  inline bool
1689  { return !(__x == __y); }
1690 
1691 _GLIBCXX_END_NAMESPACE_CONTAINER
1692 
1693 #if __cplusplus > 201402L
1694  // Allow std::unordered_set access to internals of compatible sets.
1695  template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1696  typename _Hash2, typename _Eq2>
1697  struct _Hash_merge_helper<
1698  _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1699  {
1700  private:
1701  template<typename... _Tp>
1702  using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1703  template<typename... _Tp>
1704  using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1705 
1707 
1708  static auto&
1709  _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1710  { return __set._M_h; }
1711 
1712  static auto&
1714  { return __set._M_h; }
1715  };
1716 
1717  // Allow std::unordered_multiset access to internals of compatible sets.
1718  template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1719  typename _Hash2, typename _Eq2>
1720  struct _Hash_merge_helper<
1721  _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1722  _Hash2, _Eq2>
1723  {
1724  private:
1725  template<typename... _Tp>
1726  using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1727  template<typename... _Tp>
1728  using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1729 
1731 
1732  static auto&
1733  _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1734  { return __set._M_h; }
1735 
1736  static auto&
1738  { return __set._M_h; }
1739  };
1740 #endif // C++17
1741 
1742 _GLIBCXX_END_NAMESPACE_VERSION
1743 } // namespace std
1744 
1745 #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.
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
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:108
_Hashtable::difference_type difference_type
Iterator-related typedefs.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
ISO C++ entities toplevel namespace is std.
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.
_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.
_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.
bool empty() const noexcept
Returns true if the unordered_set is empty.
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.
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.