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