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