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