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