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