libstdc++
unordered_set.h
Go to the documentation of this file.
1 // unordered_set implementation -*- C++ -*-
2 
3 // Copyright (C) 2010-2015 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  /**
69  * @brief A standard container composed of unique keys (containing
70  * at most one of each key value) in which the elements' keys are
71  * the elements themselves.
72  *
73  * @ingroup unordered_associative_containers
74  *
75  * @tparam _Value Type of key objects.
76  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
77 
78  * @tparam _Pred Predicate function object type, defaults to
79  * equal_to<_Value>.
80  *
81  * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
82  *
83  * Meets the requirements of a <a href="tables.html#65">container</a>, and
84  * <a href="tables.html#xx">unordered associative container</a>
85  *
86  * Base is _Hashtable, dispatched at compile time via template
87  * alias __uset_hashtable.
88  */
89  template<class _Value,
90  class _Hash = hash<_Value>,
91  class _Pred = std::equal_to<_Value>,
92  class _Alloc = std::allocator<_Value> >
94  {
96  _Hashtable _M_h;
97 
98  public:
99  // typedefs:
100  //@{
101  /// Public typedefs.
102  typedef typename _Hashtable::key_type key_type;
103  typedef typename _Hashtable::value_type value_type;
104  typedef typename _Hashtable::hasher hasher;
105  typedef typename _Hashtable::key_equal key_equal;
106  typedef typename _Hashtable::allocator_type allocator_type;
107  //@}
108 
109  //@{
110  /// Iterator-related typedefs.
111  typedef typename _Hashtable::pointer pointer;
112  typedef typename _Hashtable::const_pointer const_pointer;
113  typedef typename _Hashtable::reference reference;
114  typedef typename _Hashtable::const_reference const_reference;
115  typedef typename _Hashtable::iterator iterator;
116  typedef typename _Hashtable::const_iterator const_iterator;
117  typedef typename _Hashtable::local_iterator local_iterator;
118  typedef typename _Hashtable::const_local_iterator const_local_iterator;
119  typedef typename _Hashtable::size_type size_type;
120  typedef typename _Hashtable::difference_type difference_type;
121  //@}
122 
123  // construct/destroy/copy
124 
125  /// Default constructor.
126  unordered_set() = default;
127 
128  /**
129  * @brief Default constructor creates no elements.
130  * @param __n Minimal initial number of buckets.
131  * @param __hf A hash functor.
132  * @param __eql A key equality functor.
133  * @param __a An allocator object.
134  */
135  explicit
136  unordered_set(size_type __n,
137  const hasher& __hf = hasher(),
138  const key_equal& __eql = key_equal(),
139  const allocator_type& __a = allocator_type())
140  : _M_h(__n, __hf, __eql, __a)
141  { }
142 
143  /**
144  * @brief Builds an %unordered_set from a range.
145  * @param __first An input iterator.
146  * @param __last An input iterator.
147  * @param __n Minimal initial number of buckets.
148  * @param __hf A hash functor.
149  * @param __eql A key equality functor.
150  * @param __a An allocator object.
151  *
152  * Create an %unordered_set consisting of copies of the elements from
153  * [__first,__last). This is linear in N (where N is
154  * distance(__first,__last)).
155  */
156  template<typename _InputIterator>
157  unordered_set(_InputIterator __first, _InputIterator __last,
158  size_type __n = 0,
159  const hasher& __hf = hasher(),
160  const key_equal& __eql = key_equal(),
161  const allocator_type& __a = allocator_type())
162  : _M_h(__first, __last, __n, __hf, __eql, __a)
163  { }
164 
165  /// Copy constructor.
166  unordered_set(const unordered_set&) = default;
167 
168  /// Move constructor.
169  unordered_set(unordered_set&&) = default;
170 
171  /**
172  * @brief Creates an %unordered_set with no elements.
173  * @param __a An allocator object.
174  */
175  explicit
176  unordered_set(const allocator_type& __a)
177  : _M_h(__a)
178  { }
179 
180  /*
181  * @brief Copy constructor with allocator argument.
182  * @param __uset Input %unordered_set to copy.
183  * @param __a An allocator object.
184  */
185  unordered_set(const unordered_set& __uset,
186  const allocator_type& __a)
187  : _M_h(__uset._M_h, __a)
188  { }
189 
190  /*
191  * @brief Move constructor with allocator argument.
192  * @param __uset Input %unordered_set to move.
193  * @param __a An allocator object.
194  */
195  unordered_set(unordered_set&& __uset,
196  const allocator_type& __a)
197  : _M_h(std::move(__uset._M_h), __a)
198  { }
199 
200  /**
201  * @brief Builds an %unordered_set from an initializer_list.
202  * @param __l An initializer_list.
203  * @param __n Minimal initial number of buckets.
204  * @param __hf A hash functor.
205  * @param __eql A key equality functor.
206  * @param __a An allocator object.
207  *
208  * Create an %unordered_set consisting of copies of the elements in the
209  * list. This is linear in N (where N is @a __l.size()).
210  */
211  unordered_set(initializer_list<value_type> __l,
212  size_type __n = 0,
213  const hasher& __hf = hasher(),
214  const key_equal& __eql = key_equal(),
215  const allocator_type& __a = allocator_type())
216  : _M_h(__l, __n, __hf, __eql, __a)
217  { }
218 
219  /// Copy assignment operator.
221  operator=(const unordered_set&) = default;
222 
223  /// Move assignment operator.
225  operator=(unordered_set&&) = default;
226 
227  /**
228  * @brief %Unordered_set list assignment operator.
229  * @param __l An initializer_list.
230  *
231  * This function fills an %unordered_set with copies of the elements in
232  * the initializer list @a __l.
233  *
234  * Note that the assignment completely changes the %unordered_set and
235  * that the resulting %unordered_set's size is the same as the number
236  * of elements assigned. Old data may be lost.
237  */
239  operator=(initializer_list<value_type> __l)
240  {
241  _M_h = __l;
242  return *this;
243  }
244 
245  /// Returns the allocator object with which the %unordered_set was
246  /// constructed.
247  allocator_type
248  get_allocator() const noexcept
249  { return _M_h.get_allocator(); }
250 
251  // size and capacity:
252 
253  /// Returns true if the %unordered_set is empty.
254  bool
255  empty() const noexcept
256  { return _M_h.empty(); }
257 
258  /// Returns the size of the %unordered_set.
259  size_type
260  size() const noexcept
261  { return _M_h.size(); }
262 
263  /// Returns the maximum size of the %unordered_set.
264  size_type
265  max_size() const noexcept
266  { return _M_h.max_size(); }
267 
268  // iterators.
269 
270  //@{
271  /**
272  * Returns a read-only (constant) iterator that points to the first
273  * element in the %unordered_set.
274  */
275  iterator
276  begin() noexcept
277  { return _M_h.begin(); }
278 
279  const_iterator
280  begin() const noexcept
281  { return _M_h.begin(); }
282  //@}
283 
284  //@{
285  /**
286  * Returns a read-only (constant) iterator that points one past the last
287  * element in the %unordered_set.
288  */
289  iterator
290  end() noexcept
291  { return _M_h.end(); }
292 
293  const_iterator
294  end() const noexcept
295  { return _M_h.end(); }
296  //@}
297 
298  /**
299  * Returns a read-only (constant) iterator that points to the first
300  * element in the %unordered_set.
301  */
302  const_iterator
303  cbegin() const noexcept
304  { return _M_h.begin(); }
305 
306  /**
307  * Returns a read-only (constant) iterator that points one past the last
308  * element in the %unordered_set.
309  */
310  const_iterator
311  cend() const noexcept
312  { return _M_h.end(); }
313 
314  // modifiers.
315 
316  /**
317  * @brief Attempts to build and insert an element into the
318  * %unordered_set.
319  * @param __args Arguments used to generate an element.
320  * @return A pair, of which the first element is an iterator that points
321  * to the possibly inserted element, and the second is a bool
322  * that is true if the element was actually inserted.
323  *
324  * This function attempts to build and insert an element into the
325  * %unordered_set. An %unordered_set relies on unique keys and thus an
326  * element is only inserted if it is not already present in the
327  * %unordered_set.
328  *
329  * Insertion requires amortized constant time.
330  */
331  template<typename... _Args>
333  emplace(_Args&&... __args)
334  { return _M_h.emplace(std::forward<_Args>(__args)...); }
335 
336  /**
337  * @brief Attempts to insert an element into the %unordered_set.
338  * @param __pos An iterator that serves as a hint as to where the
339  * element should be inserted.
340  * @param __args Arguments used to generate the element to be
341  * inserted.
342  * @return An iterator that points to the element with key equivalent to
343  * the one generated from @a __args (may or may not be the
344  * element itself).
345  *
346  * This function is not concerned about whether the insertion took place,
347  * and thus does not return a boolean like the single-argument emplace()
348  * does. Note that the first parameter is only a hint and can
349  * potentially improve the performance of the insertion process. A bad
350  * hint would cause no gains in efficiency.
351  *
352  * For more on @a hinting, see:
353  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
354  *
355  * Insertion requires amortized constant time.
356  */
357  template<typename... _Args>
358  iterator
359  emplace_hint(const_iterator __pos, _Args&&... __args)
360  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
361 
362  //@{
363  /**
364  * @brief Attempts to insert an element into the %unordered_set.
365  * @param __x Element to be inserted.
366  * @return A pair, of which the first element is an iterator that points
367  * to the possibly inserted element, and the second is a bool
368  * that is true if the element was actually inserted.
369  *
370  * This function attempts to insert an element into the %unordered_set.
371  * An %unordered_set relies on unique keys and thus an element is only
372  * inserted if it is not already present in the %unordered_set.
373  *
374  * Insertion requires amortized constant time.
375  */
377  insert(const value_type& __x)
378  { return _M_h.insert(__x); }
379 
381  insert(value_type&& __x)
382  { return _M_h.insert(std::move(__x)); }
383  //@}
384 
385  //@{
386  /**
387  * @brief Attempts to insert an element into the %unordered_set.
388  * @param __hint An iterator that serves as a hint as to where the
389  * element should be inserted.
390  * @param __x Element to be inserted.
391  * @return An iterator that points to the element with key of
392  * @a __x (may or may not be the element passed in).
393  *
394  * This function is not concerned about whether the insertion took place,
395  * and thus does not return a boolean like the single-argument insert()
396  * does. Note that the first parameter is only a hint and can
397  * potentially improve the performance of the insertion process. A bad
398  * hint would cause no gains in efficiency.
399  *
400  * For more on @a hinting, see:
401  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
402  *
403  * Insertion requires amortized constant.
404  */
405  iterator
406  insert(const_iterator __hint, const value_type& __x)
407  { return _M_h.insert(__hint, __x); }
408 
409  iterator
410  insert(const_iterator __hint, value_type&& __x)
411  { return _M_h.insert(__hint, std::move(__x)); }
412  //@}
413 
414  /**
415  * @brief A template function that attempts to insert a range of
416  * elements.
417  * @param __first Iterator pointing to the start of the range to be
418  * inserted.
419  * @param __last Iterator pointing to the end of the range.
420  *
421  * Complexity similar to that of the range constructor.
422  */
423  template<typename _InputIterator>
424  void
425  insert(_InputIterator __first, _InputIterator __last)
426  { _M_h.insert(__first, __last); }
427 
428  /**
429  * @brief Attempts to insert a list of elements into the %unordered_set.
430  * @param __l A std::initializer_list<value_type> of elements
431  * to be inserted.
432  *
433  * Complexity similar to that of the range constructor.
434  */
435  void
436  insert(initializer_list<value_type> __l)
437  { _M_h.insert(__l); }
438 
439  //@{
440  /**
441  * @brief Erases an element from an %unordered_set.
442  * @param __position An iterator pointing to the element to be erased.
443  * @return An iterator pointing to the element immediately following
444  * @a __position prior to the element being erased. If no such
445  * element exists, end() is returned.
446  *
447  * This function erases an element, pointed to by the given iterator,
448  * from an %unordered_set. Note that this function only erases the
449  * element, and that if the element is itself a pointer, the pointed-to
450  * memory is not touched in any way. Managing the pointer is the user's
451  * responsibility.
452  */
453  iterator
454  erase(const_iterator __position)
455  { return _M_h.erase(__position); }
456 
457  // LWG 2059.
458  iterator
459  erase(iterator __position)
460  { return _M_h.erase(__position); }
461  //@}
462 
463  /**
464  * @brief Erases elements according to the provided key.
465  * @param __x Key of element to be erased.
466  * @return The number of elements erased.
467  *
468  * This function erases all the elements located by the given key from
469  * an %unordered_set. For an %unordered_set the result of this function
470  * can only be 0 (not present) or 1 (present).
471  * Note that this function only erases the element, and that if
472  * the element is itself a pointer, the pointed-to memory is not touched
473  * in any way. Managing the pointer is the user's responsibility.
474  */
475  size_type
476  erase(const key_type& __x)
477  { return _M_h.erase(__x); }
478 
479  /**
480  * @brief Erases a [__first,__last) range of elements from an
481  * %unordered_set.
482  * @param __first Iterator pointing to the start of the range to be
483  * erased.
484  * @param __last Iterator pointing to the end of the range to
485  * be erased.
486  * @return The iterator @a __last.
487  *
488  * This function erases a sequence of elements from an %unordered_set.
489  * Note that this function only erases the element, and that if
490  * the element is itself a pointer, the pointed-to memory is not touched
491  * in any way. Managing the pointer is the user's responsibility.
492  */
493  iterator
494  erase(const_iterator __first, const_iterator __last)
495  { return _M_h.erase(__first, __last); }
496 
497  /**
498  * Erases all elements in an %unordered_set. Note that this function only
499  * erases the elements, and that if the elements themselves are pointers,
500  * the pointed-to memory is not touched in any way. Managing the pointer
501  * is the user's responsibility.
502  */
503  void
504  clear() noexcept
505  { _M_h.clear(); }
506 
507  /**
508  * @brief Swaps data with another %unordered_set.
509  * @param __x An %unordered_set of the same element and allocator
510  * types.
511  *
512  * This exchanges the elements between two sets in constant time.
513  * Note that the global std::swap() function is specialized such that
514  * std::swap(s1,s2) will feed to this function.
515  */
516  void
518  noexcept( noexcept(_M_h.swap(__x._M_h)) )
519  { _M_h.swap(__x._M_h); }
520 
521  // observers.
522 
523  /// Returns the hash functor object with which the %unordered_set was
524  /// constructed.
525  hasher
527  { return _M_h.hash_function(); }
528 
529  /// Returns the key comparison object with which the %unordered_set was
530  /// constructed.
531  key_equal
532  key_eq() const
533  { return _M_h.key_eq(); }
534 
535  // lookup.
536 
537  //@{
538  /**
539  * @brief Tries to locate an element in an %unordered_set.
540  * @param __x Element to be located.
541  * @return Iterator pointing to sought-after element, or end() if not
542  * found.
543  *
544  * This function takes a key and tries to locate the element with which
545  * the key matches. If successful the function returns an iterator
546  * pointing to the sought after element. If unsuccessful it returns the
547  * past-the-end ( @c end() ) iterator.
548  */
549  iterator
550  find(const key_type& __x)
551  { return _M_h.find(__x); }
552 
553  const_iterator
554  find(const key_type& __x) const
555  { return _M_h.find(__x); }
556  //@}
557 
558  /**
559  * @brief Finds the number of elements.
560  * @param __x Element to located.
561  * @return Number of elements with specified key.
562  *
563  * This function only makes sense for unordered_multisets; for
564  * unordered_set the result will either be 0 (not present) or 1
565  * (present).
566  */
567  size_type
568  count(const key_type& __x) const
569  { return _M_h.count(__x); }
570 
571  //@{
572  /**
573  * @brief Finds a subsequence matching given key.
574  * @param __x Key to be located.
575  * @return Pair of iterators that possibly points to the subsequence
576  * matching given key.
577  *
578  * This function probably only makes sense for multisets.
579  */
581  equal_range(const key_type& __x)
582  { return _M_h.equal_range(__x); }
583 
585  equal_range(const key_type& __x) const
586  { return _M_h.equal_range(__x); }
587  //@}
588 
589  // bucket interface.
590 
591  /// Returns the number of buckets of the %unordered_set.
592  size_type
593  bucket_count() const noexcept
594  { return _M_h.bucket_count(); }
595 
596  /// Returns the maximum number of buckets of the %unordered_set.
597  size_type
598  max_bucket_count() const noexcept
599  { return _M_h.max_bucket_count(); }
600 
601  /*
602  * @brief Returns the number of elements in a given bucket.
603  * @param __n A bucket index.
604  * @return The number of elements in the bucket.
605  */
606  size_type
607  bucket_size(size_type __n) const
608  { return _M_h.bucket_size(__n); }
609 
610  /*
611  * @brief Returns the bucket index of a given element.
612  * @param __key A key instance.
613  * @return The key bucket index.
614  */
615  size_type
616  bucket(const key_type& __key) const
617  { return _M_h.bucket(__key); }
618 
619  //@{
620  /**
621  * @brief Returns a read-only (constant) iterator pointing to the first
622  * bucket element.
623  * @param __n The bucket index.
624  * @return A read-only local iterator.
625  */
626  local_iterator
627  begin(size_type __n)
628  { return _M_h.begin(__n); }
629 
630  const_local_iterator
631  begin(size_type __n) const
632  { return _M_h.begin(__n); }
633 
634  const_local_iterator
635  cbegin(size_type __n) const
636  { return _M_h.cbegin(__n); }
637  //@}
638 
639  //@{
640  /**
641  * @brief Returns a read-only (constant) iterator pointing to one past
642  * the last bucket elements.
643  * @param __n The bucket index.
644  * @return A read-only local iterator.
645  */
646  local_iterator
647  end(size_type __n)
648  { return _M_h.end(__n); }
649 
650  const_local_iterator
651  end(size_type __n) const
652  { return _M_h.end(__n); }
653 
654  const_local_iterator
655  cend(size_type __n) const
656  { return _M_h.cend(__n); }
657  //@}
658 
659  // hash policy.
660 
661  /// Returns the average number of elements per bucket.
662  float
663  load_factor() const noexcept
664  { return _M_h.load_factor(); }
665 
666  /// Returns a positive number that the %unordered_set tries to keep the
667  /// load factor less than or equal to.
668  float
669  max_load_factor() const noexcept
670  { return _M_h.max_load_factor(); }
671 
672  /**
673  * @brief Change the %unordered_set maximum load factor.
674  * @param __z The new maximum load factor.
675  */
676  void
677  max_load_factor(float __z)
678  { _M_h.max_load_factor(__z); }
679 
680  /**
681  * @brief May rehash the %unordered_set.
682  * @param __n The new number of buckets.
683  *
684  * Rehash will occur only if the new number of buckets respect the
685  * %unordered_set maximum load factor.
686  */
687  void
688  rehash(size_type __n)
689  { _M_h.rehash(__n); }
690 
691  /**
692  * @brief Prepare the %unordered_set for a specified number of
693  * elements.
694  * @param __n Number of elements required.
695  *
696  * Same as rehash(ceil(n / max_load_factor())).
697  */
698  void
699  reserve(size_type __n)
700  { _M_h.reserve(__n); }
701 
702  template<typename _Value1, typename _Hash1, typename _Pred1,
703  typename _Alloc1>
704  friend bool
707  };
708 
709  /**
710  * @brief A standard container composed of equivalent keys
711  * (possibly containing multiple of each key value) in which the
712  * elements' keys are the elements themselves.
713  *
714  * @ingroup unordered_associative_containers
715  *
716  * @tparam _Value Type of key objects.
717  * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
718  * @tparam _Pred Predicate function object type, defaults
719  * to equal_to<_Value>.
720  * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
721  *
722  * Meets the requirements of a <a href="tables.html#65">container</a>, and
723  * <a href="tables.html#xx">unordered associative container</a>
724  *
725  * Base is _Hashtable, dispatched at compile time via template
726  * alias __umset_hashtable.
727  */
728  template<class _Value,
729  class _Hash = hash<_Value>,
730  class _Pred = std::equal_to<_Value>,
731  class _Alloc = std::allocator<_Value> >
733  {
735  _Hashtable _M_h;
736 
737  public:
738  // typedefs:
739  //@{
740  /// Public typedefs.
741  typedef typename _Hashtable::key_type key_type;
742  typedef typename _Hashtable::value_type value_type;
743  typedef typename _Hashtable::hasher hasher;
744  typedef typename _Hashtable::key_equal key_equal;
745  typedef typename _Hashtable::allocator_type allocator_type;
746  //@}
747 
748  //@{
749  /// Iterator-related typedefs.
750  typedef typename _Hashtable::pointer pointer;
751  typedef typename _Hashtable::const_pointer const_pointer;
752  typedef typename _Hashtable::reference reference;
753  typedef typename _Hashtable::const_reference const_reference;
754  typedef typename _Hashtable::iterator iterator;
755  typedef typename _Hashtable::const_iterator const_iterator;
756  typedef typename _Hashtable::local_iterator local_iterator;
757  typedef typename _Hashtable::const_local_iterator const_local_iterator;
758  typedef typename _Hashtable::size_type size_type;
759  typedef typename _Hashtable::difference_type difference_type;
760  //@}
761 
762  // construct/destroy/copy
763 
764  /// Default constructor.
765  unordered_multiset() = default;
766 
767  /**
768  * @brief Default constructor creates no elements.
769  * @param __n Minimal initial number of buckets.
770  * @param __hf A hash functor.
771  * @param __eql A key equality functor.
772  * @param __a An allocator object.
773  */
774  explicit
775  unordered_multiset(size_type __n,
776  const hasher& __hf = hasher(),
777  const key_equal& __eql = key_equal(),
778  const allocator_type& __a = allocator_type())
779  : _M_h(__n, __hf, __eql, __a)
780  { }
781 
782  /**
783  * @brief Builds an %unordered_multiset from a range.
784  * @param __first An input iterator.
785  * @param __last An input iterator.
786  * @param __n Minimal initial number of buckets.
787  * @param __hf A hash functor.
788  * @param __eql A key equality functor.
789  * @param __a An allocator object.
790  *
791  * Create an %unordered_multiset consisting of copies of the elements
792  * from [__first,__last). This is linear in N (where N is
793  * distance(__first,__last)).
794  */
795  template<typename _InputIterator>
796  unordered_multiset(_InputIterator __first, _InputIterator __last,
797  size_type __n = 0,
798  const hasher& __hf = hasher(),
799  const key_equal& __eql = key_equal(),
800  const allocator_type& __a = allocator_type())
801  : _M_h(__first, __last, __n, __hf, __eql, __a)
802  { }
803 
804  /// Copy constructor.
805  unordered_multiset(const unordered_multiset&) = default;
806 
807  /// Move constructor.
809 
810  /**
811  * @brief Builds an %unordered_multiset from an initializer_list.
812  * @param __l An initializer_list.
813  * @param __n Minimal initial number of buckets.
814  * @param __hf A hash functor.
815  * @param __eql A key equality functor.
816  * @param __a An allocator object.
817  *
818  * Create an %unordered_multiset consisting of copies of the elements in
819  * the list. This is linear in N (where N is @a __l.size()).
820  */
821  unordered_multiset(initializer_list<value_type> __l,
822  size_type __n = 0,
823  const hasher& __hf = hasher(),
824  const key_equal& __eql = key_equal(),
825  const allocator_type& __a = allocator_type())
826  : _M_h(__l, __n, __hf, __eql, __a)
827  { }
828 
829  /// Copy assignment operator.
831  operator=(const unordered_multiset&) = default;
832 
833  /// Move assignment operator.
835  operator=(unordered_multiset&&) = default;
836 
837  /**
838  * @brief Creates an %unordered_multiset with no elements.
839  * @param __a An allocator object.
840  */
841  explicit
842  unordered_multiset(const allocator_type& __a)
843  : _M_h(__a)
844  { }
845 
846  /*
847  * @brief Copy constructor with allocator argument.
848  * @param __uset Input %unordered_multiset to copy.
849  * @param __a An allocator object.
850  */
851  unordered_multiset(const unordered_multiset& __umset,
852  const allocator_type& __a)
853  : _M_h(__umset._M_h, __a)
854  { }
855 
856  /*
857  * @brief Move constructor with allocator argument.
858  * @param __umset Input %unordered_multiset to move.
859  * @param __a An allocator object.
860  */
862  const allocator_type& __a)
863  : _M_h(std::move(__umset._M_h), __a)
864  { }
865 
866  /**
867  * @brief %Unordered_multiset list assignment operator.
868  * @param __l An initializer_list.
869  *
870  * This function fills an %unordered_multiset with copies of the elements
871  * in the initializer list @a __l.
872  *
873  * Note that the assignment completely changes the %unordered_multiset
874  * and that the resulting %unordered_set's size is the same as the number
875  * of elements assigned. Old data may be lost.
876  */
878  operator=(initializer_list<value_type> __l)
879  {
880  _M_h = __l;
881  return *this;
882  }
883 
884  /// Returns the allocator object with which the %unordered_multiset was
885  /// constructed.
886  allocator_type
887  get_allocator() const noexcept
888  { return _M_h.get_allocator(); }
889 
890  // size and capacity:
891 
892  /// Returns true if the %unordered_multiset is empty.
893  bool
894  empty() const noexcept
895  { return _M_h.empty(); }
896 
897  /// Returns the size of the %unordered_multiset.
898  size_type
899  size() const noexcept
900  { return _M_h.size(); }
901 
902  /// Returns the maximum size of the %unordered_multiset.
903  size_type
904  max_size() const noexcept
905  { return _M_h.max_size(); }
906 
907  // iterators.
908 
909  //@{
910  /**
911  * Returns a read-only (constant) iterator that points to the first
912  * element in the %unordered_multiset.
913  */
914  iterator
915  begin() noexcept
916  { return _M_h.begin(); }
917 
918  const_iterator
919  begin() const noexcept
920  { return _M_h.begin(); }
921  //@}
922 
923  //@{
924  /**
925  * Returns a read-only (constant) iterator that points one past the last
926  * element in the %unordered_multiset.
927  */
928  iterator
929  end() noexcept
930  { return _M_h.end(); }
931 
932  const_iterator
933  end() const noexcept
934  { return _M_h.end(); }
935  //@}
936 
937  /**
938  * Returns a read-only (constant) iterator that points to the first
939  * element in the %unordered_multiset.
940  */
941  const_iterator
942  cbegin() const noexcept
943  { return _M_h.begin(); }
944 
945  /**
946  * Returns a read-only (constant) iterator that points one past the last
947  * element in the %unordered_multiset.
948  */
949  const_iterator
950  cend() const noexcept
951  { return _M_h.end(); }
952 
953  // modifiers.
954 
955  /**
956  * @brief Builds and insert an element into the %unordered_multiset.
957  * @param __args Arguments used to generate an element.
958  * @return An iterator that points to the inserted element.
959  *
960  * Insertion requires amortized constant time.
961  */
962  template<typename... _Args>
963  iterator
964  emplace(_Args&&... __args)
965  { return _M_h.emplace(std::forward<_Args>(__args)...); }
966 
967  /**
968  * @brief Inserts an element into the %unordered_multiset.
969  * @param __pos An iterator that serves as a hint as to where the
970  * element should be inserted.
971  * @param __args Arguments used to generate the element to be
972  * inserted.
973  * @return An iterator that points to the inserted element.
974  *
975  * Note that the first parameter is only a hint and can potentially
976  * improve the performance of the insertion process. A bad hint would
977  * cause no gains in efficiency.
978  *
979  * For more on @a hinting, see:
980  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
981  *
982  * Insertion requires amortized constant time.
983  */
984  template<typename... _Args>
985  iterator
986  emplace_hint(const_iterator __pos, _Args&&... __args)
987  { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
988 
989  //@{
990  /**
991  * @brief Inserts an element into the %unordered_multiset.
992  * @param __x Element to be inserted.
993  * @return An iterator that points to the inserted element.
994  *
995  * Insertion requires amortized constant time.
996  */
997  iterator
998  insert(const value_type& __x)
999  { return _M_h.insert(__x); }
1000 
1001  iterator
1002  insert(value_type&& __x)
1003  { return _M_h.insert(std::move(__x)); }
1004  //@}
1005 
1006  //@{
1007  /**
1008  * @brief Inserts an element into the %unordered_multiset.
1009  * @param __hint An iterator that serves as a hint as to where the
1010  * element should be inserted.
1011  * @param __x Element to be inserted.
1012  * @return An iterator that points to the inserted element.
1013  *
1014  * Note that the first parameter is only a hint and can potentially
1015  * improve the performance of the insertion process. A bad hint would
1016  * cause no gains in efficiency.
1017  *
1018  * For more on @a hinting, see:
1019  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1020  *
1021  * Insertion requires amortized constant.
1022  */
1023  iterator
1024  insert(const_iterator __hint, const value_type& __x)
1025  { return _M_h.insert(__hint, __x); }
1026 
1027  iterator
1028  insert(const_iterator __hint, value_type&& __x)
1029  { return _M_h.insert(__hint, std::move(__x)); }
1030  //@}
1031 
1032  /**
1033  * @brief A template function that inserts a range of elements.
1034  * @param __first Iterator pointing to the start of the range to be
1035  * inserted.
1036  * @param __last Iterator pointing to the end of the range.
1037  *
1038  * Complexity similar to that of the range constructor.
1039  */
1040  template<typename _InputIterator>
1041  void
1042  insert(_InputIterator __first, _InputIterator __last)
1043  { _M_h.insert(__first, __last); }
1044 
1045  /**
1046  * @brief Inserts a list of elements into the %unordered_multiset.
1047  * @param __l A std::initializer_list<value_type> of elements to be
1048  * inserted.
1049  *
1050  * Complexity similar to that of the range constructor.
1051  */
1052  void
1053  insert(initializer_list<value_type> __l)
1054  { _M_h.insert(__l); }
1055 
1056  //@{
1057  /**
1058  * @brief Erases an element from an %unordered_multiset.
1059  * @param __position An iterator pointing to the element to be erased.
1060  * @return An iterator pointing to the element immediately following
1061  * @a __position prior to the element being erased. If no such
1062  * element exists, end() is returned.
1063  *
1064  * This function erases an element, pointed to by the given iterator,
1065  * from an %unordered_multiset.
1066  *
1067  * Note that this function only erases the element, and that if the
1068  * element is itself a pointer, the pointed-to memory is not touched in
1069  * any way. Managing the pointer is the user's responsibility.
1070  */
1071  iterator
1072  erase(const_iterator __position)
1073  { return _M_h.erase(__position); }
1074 
1075  // LWG 2059.
1076  iterator
1077  erase(iterator __position)
1078  { return _M_h.erase(__position); }
1079  //@}
1080 
1081 
1082  /**
1083  * @brief Erases elements according to the provided key.
1084  * @param __x Key of element to be erased.
1085  * @return The number of elements erased.
1086  *
1087  * This function erases all the elements located by the given key from
1088  * an %unordered_multiset.
1089  *
1090  * Note that this function only erases the element, and that if the
1091  * element is itself a pointer, the pointed-to memory is not touched in
1092  * any way. Managing the pointer is the user's responsibility.
1093  */
1094  size_type
1095  erase(const key_type& __x)
1096  { return _M_h.erase(__x); }
1097 
1098  /**
1099  * @brief Erases a [__first,__last) range of elements from an
1100  * %unordered_multiset.
1101  * @param __first Iterator pointing to the start of the range to be
1102  * erased.
1103  * @param __last Iterator pointing to the end of the range to
1104  * be erased.
1105  * @return The iterator @a __last.
1106  *
1107  * This function erases a sequence of elements from an
1108  * %unordered_multiset.
1109  *
1110  * Note that this function only erases the element, and that if
1111  * the element is itself a pointer, the pointed-to memory is not touched
1112  * in any way. Managing the pointer is the user's responsibility.
1113  */
1114  iterator
1115  erase(const_iterator __first, const_iterator __last)
1116  { return _M_h.erase(__first, __last); }
1117 
1118  /**
1119  * Erases all elements in an %unordered_multiset.
1120  *
1121  * Note that this function only erases the elements, and that if the
1122  * elements themselves are pointers, the pointed-to memory is not touched
1123  * in any way. Managing the pointer is the user's responsibility.
1124  */
1125  void
1126  clear() noexcept
1127  { _M_h.clear(); }
1128 
1129  /**
1130  * @brief Swaps data with another %unordered_multiset.
1131  * @param __x An %unordered_multiset of the same element and allocator
1132  * types.
1133  *
1134  * This exchanges the elements between two sets in constant time.
1135  * Note that the global std::swap() function is specialized such that
1136  * std::swap(s1,s2) will feed to this function.
1137  */
1138  void
1140  noexcept( noexcept(_M_h.swap(__x._M_h)) )
1141  { _M_h.swap(__x._M_h); }
1142 
1143  // observers.
1144 
1145  /// Returns the hash functor object with which the %unordered_multiset
1146  /// was constructed.
1147  hasher
1149  { return _M_h.hash_function(); }
1150 
1151  /// Returns the key comparison object with which the %unordered_multiset
1152  /// was constructed.
1153  key_equal
1154  key_eq() const
1155  { return _M_h.key_eq(); }
1156 
1157  // lookup.
1158 
1159  //@{
1160  /**
1161  * @brief Tries to locate an element in an %unordered_multiset.
1162  * @param __x Element to be located.
1163  * @return Iterator pointing to sought-after element, or end() if not
1164  * found.
1165  *
1166  * This function takes a key and tries to locate the element with which
1167  * the key matches. If successful the function returns an iterator
1168  * pointing to the sought after element. If unsuccessful it returns the
1169  * past-the-end ( @c end() ) iterator.
1170  */
1171  iterator
1172  find(const key_type& __x)
1173  { return _M_h.find(__x); }
1174 
1175  const_iterator
1176  find(const key_type& __x) const
1177  { return _M_h.find(__x); }
1178  //@}
1179 
1180  /**
1181  * @brief Finds the number of elements.
1182  * @param __x Element to located.
1183  * @return Number of elements with specified key.
1184  */
1185  size_type
1186  count(const key_type& __x) const
1187  { return _M_h.count(__x); }
1188 
1189  //@{
1190  /**
1191  * @brief Finds a subsequence matching given key.
1192  * @param __x Key to be located.
1193  * @return Pair of iterators that possibly points to the subsequence
1194  * matching given key.
1195  */
1197  equal_range(const key_type& __x)
1198  { return _M_h.equal_range(__x); }
1199 
1201  equal_range(const key_type& __x) const
1202  { return _M_h.equal_range(__x); }
1203  //@}
1204 
1205  // bucket interface.
1206 
1207  /// Returns the number of buckets of the %unordered_multiset.
1208  size_type
1209  bucket_count() const noexcept
1210  { return _M_h.bucket_count(); }
1211 
1212  /// Returns the maximum number of buckets of the %unordered_multiset.
1213  size_type
1214  max_bucket_count() const noexcept
1215  { return _M_h.max_bucket_count(); }
1216 
1217  /*
1218  * @brief Returns the number of elements in a given bucket.
1219  * @param __n A bucket index.
1220  * @return The number of elements in the bucket.
1221  */
1222  size_type
1223  bucket_size(size_type __n) const
1224  { return _M_h.bucket_size(__n); }
1225 
1226  /*
1227  * @brief Returns the bucket index of a given element.
1228  * @param __key A key instance.
1229  * @return The key bucket index.
1230  */
1231  size_type
1232  bucket(const key_type& __key) const
1233  { return _M_h.bucket(__key); }
1234 
1235  //@{
1236  /**
1237  * @brief Returns a read-only (constant) iterator pointing to the first
1238  * bucket element.
1239  * @param __n The bucket index.
1240  * @return A read-only local iterator.
1241  */
1242  local_iterator
1243  begin(size_type __n)
1244  { return _M_h.begin(__n); }
1245 
1246  const_local_iterator
1247  begin(size_type __n) const
1248  { return _M_h.begin(__n); }
1249 
1250  const_local_iterator
1251  cbegin(size_type __n) const
1252  { return _M_h.cbegin(__n); }
1253  //@}
1254 
1255  //@{
1256  /**
1257  * @brief Returns a read-only (constant) iterator pointing to one past
1258  * the last bucket elements.
1259  * @param __n The bucket index.
1260  * @return A read-only local iterator.
1261  */
1262  local_iterator
1263  end(size_type __n)
1264  { return _M_h.end(__n); }
1265 
1266  const_local_iterator
1267  end(size_type __n) const
1268  { return _M_h.end(__n); }
1269 
1270  const_local_iterator
1271  cend(size_type __n) const
1272  { return _M_h.cend(__n); }
1273  //@}
1274 
1275  // hash policy.
1276 
1277  /// Returns the average number of elements per bucket.
1278  float
1279  load_factor() const noexcept
1280  { return _M_h.load_factor(); }
1281 
1282  /// Returns a positive number that the %unordered_multiset tries to keep the
1283  /// load factor less than or equal to.
1284  float
1285  max_load_factor() const noexcept
1286  { return _M_h.max_load_factor(); }
1287 
1288  /**
1289  * @brief Change the %unordered_multiset maximum load factor.
1290  * @param __z The new maximum load factor.
1291  */
1292  void
1293  max_load_factor(float __z)
1294  { _M_h.max_load_factor(__z); }
1295 
1296  /**
1297  * @brief May rehash the %unordered_multiset.
1298  * @param __n The new number of buckets.
1299  *
1300  * Rehash will occur only if the new number of buckets respect the
1301  * %unordered_multiset maximum load factor.
1302  */
1303  void
1304  rehash(size_type __n)
1305  { _M_h.rehash(__n); }
1306 
1307  /**
1308  * @brief Prepare the %unordered_multiset for a specified number of
1309  * elements.
1310  * @param __n Number of elements required.
1311  *
1312  * Same as rehash(ceil(n / max_load_factor())).
1313  */
1314  void
1315  reserve(size_type __n)
1316  { _M_h.reserve(__n); }
1317 
1318  template<typename _Value1, typename _Hash1, typename _Pred1,
1319  typename _Alloc1>
1320  friend bool
1323  };
1324 
1325  template<class _Value, class _Hash, class _Pred, class _Alloc>
1326  inline void
1327  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1328  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1329  { __x.swap(__y); }
1330 
1331  template<class _Value, class _Hash, class _Pred, class _Alloc>
1332  inline void
1333  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1334  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1335  { __x.swap(__y); }
1336 
1337  template<class _Value, class _Hash, class _Pred, class _Alloc>
1338  inline bool
1339  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1340  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1341  { return __x._M_h._M_equal(__y._M_h); }
1342 
1343  template<class _Value, class _Hash, class _Pred, class _Alloc>
1344  inline bool
1345  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1346  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1347  { return !(__x == __y); }
1348 
1349  template<class _Value, class _Hash, class _Pred, class _Alloc>
1350  inline bool
1351  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1352  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1353  { return __x._M_h._M_equal(__y._M_h); }
1354 
1355  template<class _Value, class _Hash, class _Pred, class _Alloc>
1356  inline bool
1357  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1358  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1359  { return !(__x == __y); }
1360 
1361 _GLIBCXX_END_NAMESPACE_CONTAINER
1362 } // namespace std
1363 
1364 #endif /* _UNORDERED_SET_H */
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:176
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts 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::reference reference
Iterator-related typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
unordered_set()=default
Default constructor.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator begin() noexcept
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_set was constructed.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
_Hashtable::pointer pointer
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_iterator cbegin() const noexcept
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
const_iterator begin() const noexcept
iterator erase(iterator __position)
Erases an element from an unordered_multiset.
const_iterator cend() const noexcept
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::hasher hasher
Public typedefs.
float load_factor() const noexcept
Returns the average number of elements per bucket.
bool empty() const noexcept
Returns true if the unordered_set is empty.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
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.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::key_equal key_equal
Public typedefs.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator erase(iterator __position)
Erases an element from an unordered_set.
_Hashtable::reference reference
Iterator-related typedefs.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
const_iterator cend() const noexcept
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::hasher hasher
Public typedefs.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
_Hashtable::pointer pointer
Iterator-related typedefs.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Inserts an element into the unordered_multiset.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
Primary class template hash.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
_Hashtable::key_equal key_equal
Public typedefs.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
void clear() noexcept
iterator end() noexcept
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to insert an element 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.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
size_type size() const noexcept
Returns the size of the unordered_set.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
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...
_Hashtable::key_type key_type
Public typedefs.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
size_type max_size() const noexcept
Returns the maximum size of the 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
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and 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.
size_type size() const noexcept
Returns the size of the unordered_multiset.
void swap(unordered_multiset &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multiset.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
The standard allocator, as per [20.4].
Definition: allocator.h:92
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
Default range hashing function: use division to fold a large number into the range [0...
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
const_iterator begin() const noexcept
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
float load_factor() const noexcept
Returns the average number of elements per bucket.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator end() noexcept
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:93
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
_Hashtable::key_type key_type
Public typedefs.
const_iterator cbegin() const noexcept
_Hashtable::allocator_type allocator_type
Public typedefs.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
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.
One of the comparison functors.
Definition: stl_function.h:352
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
const_iterator end() const noexcept
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_multiset was constructed.
unordered_multiset()=default
Default constructor.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
iterator begin() noexcept
iterator emplace(_Args &&...__args)
Builds and insert an element into the unordered_multiset.
unordered_multiset & operator=(const unordered_multiset &)=default
Copy assignment operator.
_Hashtable::value_type value_type
Public typedefs.
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
_Hashtable::value_type value_type
Public typedefs.
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
void rehash(size_type __n)
May rehash the unordered_multiset.
_Hashtable::allocator_type allocator_type
Public typedefs.
ISO C++ entities toplevel namespace is std.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
void rehash(size_type __n)
May rehash the unordered_set.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.