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