libstdc++
unordered_set.h
Go to the documentation of this file.
1// unordered_set implementation -*- C++ -*-
2
3// Copyright (C) 2010-2019 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_VERSION
36_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37
38 /// Base types for unordered_set.
39 template<bool _Cache>
41
42 template<typename _Value,
43 typename _Hash = hash<_Value>,
44 typename _Pred = std::equal_to<_Value>,
45 typename _Alloc = std::allocator<_Value>,
47 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
48 __detail::_Identity, _Pred, _Hash,
52
53 /// Base types for unordered_multiset.
54 template<bool _Cache>
56
57 template<typename _Value,
58 typename _Hash = hash<_Value>,
59 typename _Pred = std::equal_to<_Value>,
60 typename _Alloc = std::allocator<_Value>,
62 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
63 __detail::_Identity,
64 _Pred, _Hash,
68
69 template<class _Value, class _Hash, class _Pred, class _Alloc>
71
72 /**
73 * @brief A standard container composed of unique keys (containing
74 * at most one of each key value) in which the elements' keys are
75 * the elements themselves.
76 *
77 * @ingroup unordered_associative_containers
78 *
79 * @tparam _Value Type of key objects.
80 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
81
82 * @tparam _Pred Predicate function object type, defaults to
83 * equal_to<_Value>.
84 *
85 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
86 *
87 * Meets the requirements of a <a href="tables.html#65">container</a>, and
88 * <a href="tables.html#xx">unordered associative container</a>
89 *
90 * Base is _Hashtable, dispatched at compile time via template
91 * alias __uset_hashtable.
92 */
93 template<typename _Value,
94 typename _Hash = hash<_Value>,
95 typename _Pred = equal_to<_Value>,
96 typename _Alloc = allocator<_Value>>
98 {
100 _Hashtable _M_h;
101
102 public:
103 // typedefs:
104 ///@{
105 /// Public typedefs.
106 typedef typename _Hashtable::key_type key_type;
107 typedef typename _Hashtable::value_type value_type;
108 typedef typename _Hashtable::hasher hasher;
109 typedef typename _Hashtable::key_equal key_equal;
110 typedef typename _Hashtable::allocator_type allocator_type;
111 ///@}
112
113 ///@{
114 /// Iterator-related typedefs.
115 typedef typename _Hashtable::pointer pointer;
116 typedef typename _Hashtable::const_pointer const_pointer;
117 typedef typename _Hashtable::reference reference;
118 typedef typename _Hashtable::const_reference const_reference;
119 typedef typename _Hashtable::iterator iterator;
120 typedef typename _Hashtable::const_iterator const_iterator;
121 typedef typename _Hashtable::local_iterator local_iterator;
122 typedef typename _Hashtable::const_local_iterator const_local_iterator;
123 typedef typename _Hashtable::size_type size_type;
124 typedef typename _Hashtable::difference_type difference_type;
125 ///@}
126
127#if __cplusplus > 201402L
128 using node_type = typename _Hashtable::node_type;
129 using insert_return_type = typename _Hashtable::insert_return_type;
130#endif
131
132 // construct/destroy/copy
133
134 /// Default constructor.
135 unordered_set() = default;
136
137 /**
138 * @brief Default constructor creates no elements.
139 * @param __n Minimal initial number of buckets.
140 * @param __hf A hash functor.
141 * @param __eql A key equality functor.
142 * @param __a An allocator object.
143 */
144 explicit
146 const hasher& __hf = hasher(),
147 const key_equal& __eql = key_equal(),
148 const allocator_type& __a = allocator_type())
149 : _M_h(__n, __hf, __eql, __a)
150 { }
151
152 /**
153 * @brief Builds an %unordered_set from a range.
154 * @param __first An input iterator.
155 * @param __last An input iterator.
156 * @param __n Minimal initial number of buckets.
157 * @param __hf A hash functor.
158 * @param __eql A key equality functor.
159 * @param __a An allocator object.
160 *
161 * Create an %unordered_set consisting of copies of the elements from
162 * [__first,__last). This is linear in N (where N is
163 * distance(__first,__last)).
164 */
165 template<typename _InputIterator>
166 unordered_set(_InputIterator __first, _InputIterator __last,
167 size_type __n = 0,
168 const hasher& __hf = hasher(),
169 const key_equal& __eql = key_equal(),
170 const allocator_type& __a = allocator_type())
171 : _M_h(__first, __last, __n, __hf, __eql, __a)
172 { }
173
174 /// Copy constructor.
175 unordered_set(const unordered_set&) = default;
176
177 /// Move constructor.
179
180 /**
181 * @brief Creates an %unordered_set with no elements.
182 * @param __a An allocator object.
183 */
184 explicit
186 : _M_h(__a)
187 { }
188
189 /*
190 * @brief Copy constructor with allocator argument.
191 * @param __uset Input %unordered_set to copy.
192 * @param __a An allocator object.
193 */
194 unordered_set(const unordered_set& __uset,
195 const allocator_type& __a)
196 : _M_h(__uset._M_h, __a)
197 { }
198
199 /*
200 * @brief Move constructor with allocator argument.
201 * @param __uset Input %unordered_set to move.
202 * @param __a An allocator object.
203 */
205 const allocator_type& __a)
206 noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) )
207 : _M_h(std::move(__uset._M_h), __a)
208 { }
209
210 /**
211 * @brief Builds an %unordered_set from an initializer_list.
212 * @param __l An initializer_list.
213 * @param __n Minimal initial number of buckets.
214 * @param __hf A hash functor.
215 * @param __eql A key equality functor.
216 * @param __a An allocator object.
217 *
218 * Create an %unordered_set consisting of copies of the elements in the
219 * list. This is linear in N (where N is @a __l.size()).
220 */
222 size_type __n = 0,
223 const hasher& __hf = hasher(),
224 const key_equal& __eql = key_equal(),
225 const allocator_type& __a = allocator_type())
226 : _M_h(__l, __n, __hf, __eql, __a)
227 { }
228
229 unordered_set(size_type __n, const allocator_type& __a)
230 : unordered_set(__n, hasher(), key_equal(), __a)
231 { }
232
233 unordered_set(size_type __n, const hasher& __hf,
234 const allocator_type& __a)
235 : unordered_set(__n, __hf, key_equal(), __a)
236 { }
237
238 template<typename _InputIterator>
239 unordered_set(_InputIterator __first, _InputIterator __last,
240 size_type __n,
241 const allocator_type& __a)
242 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
243 { }
244
245 template<typename _InputIterator>
246 unordered_set(_InputIterator __first, _InputIterator __last,
247 size_type __n, const hasher& __hf,
248 const allocator_type& __a)
249 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
250 { }
251
252 unordered_set(initializer_list<value_type> __l,
253 size_type __n,
254 const allocator_type& __a)
255 : unordered_set(__l, __n, hasher(), key_equal(), __a)
256 { }
257
258 unordered_set(initializer_list<value_type> __l,
259 size_type __n, const hasher& __hf,
260 const allocator_type& __a)
261 : unordered_set(__l, __n, __hf, key_equal(), __a)
262 { }
263
264 /// Copy assignment operator.
266 operator=(const unordered_set&) = default;
267
268 /// Move assignment operator.
271
272 /**
273 * @brief %Unordered_set list assignment operator.
274 * @param __l An initializer_list.
275 *
276 * This function fills an %unordered_set with copies of the elements in
277 * the initializer list @a __l.
278 *
279 * Note that the assignment completely changes the %unordered_set and
280 * that the resulting %unordered_set's size is the same as the number
281 * of elements assigned.
282 */
285 {
286 _M_h = __l;
287 return *this;
288 }
289
290 /// Returns the allocator object used by the %unordered_set.
292 get_allocator() const noexcept
293 { return _M_h.get_allocator(); }
294
295 // size and capacity:
296
297 /// Returns true if the %unordered_set is empty.
298 _GLIBCXX_NODISCARD bool
299 empty() const noexcept
300 { return _M_h.empty(); }
301
302 /// Returns the size of the %unordered_set.
304 size() const noexcept
305 { return _M_h.size(); }
306
307 /// Returns the maximum size of the %unordered_set.
309 max_size() const noexcept
310 { return _M_h.max_size(); }
311
312 // iterators.
313
314 ///@{
315 /**
316 * Returns a read-only (constant) iterator that points to the first
317 * element in the %unordered_set.
318 */
320 begin() noexcept
321 { return _M_h.begin(); }
322
324 begin() const noexcept
325 { return _M_h.begin(); }
326 ///@}
327
328 ///@{
329 /**
330 * Returns a read-only (constant) iterator that points one past the last
331 * element in the %unordered_set.
332 */
334 end() noexcept
335 { return _M_h.end(); }
336
338 end() const noexcept
339 { return _M_h.end(); }
340 ///@}
341
342 /**
343 * Returns a read-only (constant) iterator that points to the first
344 * element in the %unordered_set.
345 */
347 cbegin() const noexcept
348 { return _M_h.begin(); }
349
350 /**
351 * Returns a read-only (constant) iterator that points one past the last
352 * element in the %unordered_set.
353 */
355 cend() const noexcept
356 { return _M_h.end(); }
357
358 // modifiers.
359
360 /**
361 * @brief Attempts to build and insert an element into the
362 * %unordered_set.
363 * @param __args Arguments used to generate an element.
364 * @return A pair, of which the first element is an iterator that points
365 * to the possibly inserted element, and the second is a bool
366 * that is true if the element was actually inserted.
367 *
368 * This function attempts to build and insert an element into the
369 * %unordered_set. An %unordered_set relies on unique keys and thus an
370 * element is only inserted if it is not already present in the
371 * %unordered_set.
372 *
373 * Insertion requires amortized constant time.
374 */
375 template<typename... _Args>
377 emplace(_Args&&... __args)
378 { return _M_h.emplace(std::forward<_Args>(__args)...); }
379
380 /**
381 * @brief Attempts to insert an element into the %unordered_set.
382 * @param __pos An iterator that serves as a hint as to where the
383 * element should be inserted.
384 * @param __args Arguments used to generate the element to be
385 * inserted.
386 * @return An iterator that points to the element with key equivalent to
387 * the one generated from @a __args (may or may not be the
388 * element itself).
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 emplace()
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 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
398 *
399 * Insertion requires amortized constant time.
400 */
401 template<typename... _Args>
403 emplace_hint(const_iterator __pos, _Args&&... __args)
404 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
405
406 ///@{
407 /**
408 * @brief Attempts to insert an element into the %unordered_set.
409 * @param __x Element to be inserted.
410 * @return A pair, of which the first element is an iterator that points
411 * to the possibly inserted element, and the second is a bool
412 * that is true if the element was actually inserted.
413 *
414 * This function attempts to insert an element into the %unordered_set.
415 * An %unordered_set relies on unique keys and thus an element is only
416 * inserted if it is not already present in the %unordered_set.
417 *
418 * Insertion requires amortized constant time.
419 */
421 insert(const value_type& __x)
422 { return _M_h.insert(__x); }
423
426 { return _M_h.insert(std::move(__x)); }
427 ///@}
428
429 ///@{
430 /**
431 * @brief Attempts to insert an element into the %unordered_set.
432 * @param __hint An iterator that serves as a hint as to where the
433 * element should be inserted.
434 * @param __x Element to be inserted.
435 * @return An iterator that points to the element with key of
436 * @a __x (may or may not be the element passed in).
437 *
438 * This function is not concerned about whether the insertion took place,
439 * and thus does not return a boolean like the single-argument insert()
440 * does. Note that the first parameter is only a hint and can
441 * potentially improve the performance of the insertion process. A bad
442 * hint would cause no gains in efficiency.
443 *
444 * For more on @a hinting, see:
445 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
446 *
447 * Insertion requires amortized constant.
448 */
450 insert(const_iterator __hint, const value_type& __x)
451 { return _M_h.insert(__hint, __x); }
452
455 { return _M_h.insert(__hint, std::move(__x)); }
456 ///@}
457
458 /**
459 * @brief A template function that attempts to insert a range of
460 * elements.
461 * @param __first Iterator pointing to the start of the range to be
462 * inserted.
463 * @param __last Iterator pointing to the end of the range.
464 *
465 * Complexity similar to that of the range constructor.
466 */
467 template<typename _InputIterator>
468 void
469 insert(_InputIterator __first, _InputIterator __last)
470 { _M_h.insert(__first, __last); }
471
472 /**
473 * @brief Attempts to insert a list of elements into the %unordered_set.
474 * @param __l A std::initializer_list<value_type> of elements
475 * to be inserted.
476 *
477 * Complexity similar to that of the range constructor.
478 */
479 void
481 { _M_h.insert(__l); }
482
483#if __cplusplus > 201402L
484 /// Extract a node.
485 node_type
486 extract(const_iterator __pos)
487 {
488 __glibcxx_assert(__pos != end());
489 return _M_h.extract(__pos);
490 }
491
492 /// Extract a node.
493 node_type
494 extract(const key_type& __key)
495 { return _M_h.extract(__key); }
496
497 /// Re-insert an extracted node.
498 insert_return_type
499 insert(node_type&& __nh)
500 { return _M_h._M_reinsert_node(std::move(__nh)); }
501
502 /// Re-insert an extracted node.
504 insert(const_iterator, node_type&& __nh)
505 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
506#endif // C++17
507
508 ///@{
509 /**
510 * @brief Erases an element from an %unordered_set.
511 * @param __position An iterator pointing to the element to be erased.
512 * @return An iterator pointing to the element immediately following
513 * @a __position prior to the element being erased. If no such
514 * element exists, end() is returned.
515 *
516 * This function erases an element, pointed to by the given iterator,
517 * from an %unordered_set. Note that this function only erases the
518 * element, and that if the element is itself a pointer, the pointed-to
519 * memory is not touched in any way. Managing the pointer is the user's
520 * responsibility.
521 */
524 { return _M_h.erase(__position); }
525
526 // LWG 2059.
528 erase(iterator __position)
529 { return _M_h.erase(__position); }
530 ///@}
531
532 /**
533 * @brief Erases elements according to the provided key.
534 * @param __x Key of element to be erased.
535 * @return The number of elements erased.
536 *
537 * This function erases all the elements located by the given key from
538 * an %unordered_set. For an %unordered_set the result of this function
539 * can only be 0 (not present) or 1 (present).
540 * Note that this function only erases the element, and that if
541 * the element is itself a pointer, the pointed-to memory is not touched
542 * in any way. Managing the pointer is the user's responsibility.
543 */
545 erase(const key_type& __x)
546 { return _M_h.erase(__x); }
547
548 /**
549 * @brief Erases a [__first,__last) range of elements from an
550 * %unordered_set.
551 * @param __first Iterator pointing to the start of the range to be
552 * erased.
553 * @param __last Iterator pointing to the end of the range to
554 * be erased.
555 * @return The iterator @a __last.
556 *
557 * This function erases a sequence of elements from an %unordered_set.
558 * Note that this function only erases the element, and that if
559 * the element is itself a pointer, the pointed-to memory is not touched
560 * in any way. Managing the pointer is the user's responsibility.
561 */
564 { return _M_h.erase(__first, __last); }
565
566 /**
567 * Erases all elements in an %unordered_set. Note that this function only
568 * erases the elements, and that if the elements themselves are pointers,
569 * the pointed-to memory is not touched in any way. Managing the pointer
570 * is the user's responsibility.
571 */
572 void
573 clear() noexcept
574 { _M_h.clear(); }
575
576 /**
577 * @brief Swaps data with another %unordered_set.
578 * @param __x An %unordered_set of the same element and allocator
579 * types.
580 *
581 * This exchanges the elements between two sets in constant time.
582 * Note that the global std::swap() function is specialized such that
583 * std::swap(s1,s2) will feed to this function.
584 */
585 void
587 noexcept( noexcept(_M_h.swap(__x._M_h)) )
588 { _M_h.swap(__x._M_h); }
589
590#if __cplusplus > 201402L
591 template<typename, typename, typename>
592 friend class std::_Hash_merge_helper;
593
594 template<typename _H2, typename _P2>
595 void
597 {
598 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
599 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
600 }
601
602 template<typename _H2, typename _P2>
603 void
604 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
605 { merge(__source); }
606
607 template<typename _H2, typename _P2>
608 void
609 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
610 {
611 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
612 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
613 }
614
615 template<typename _H2, typename _P2>
616 void
617 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
618 { merge(__source); }
619#endif // C++17
620
621 // observers.
622
623 /// Returns the hash functor object with which the %unordered_set was
624 /// constructed.
625 hasher
627 { return _M_h.hash_function(); }
628
629 /// Returns the key comparison object with which the %unordered_set was
630 /// constructed.
632 key_eq() const
633 { return _M_h.key_eq(); }
634
635 // lookup.
636
637 ///@{
638 /**
639 * @brief Tries to locate an element in an %unordered_set.
640 * @param __x Element to be located.
641 * @return Iterator pointing to sought-after element, or end() if not
642 * found.
643 *
644 * This function takes a key and tries to locate the element with which
645 * the key matches. If successful the function returns an iterator
646 * pointing to the sought after element. If unsuccessful it returns the
647 * past-the-end ( @c end() ) iterator.
648 */
650 find(const key_type& __x)
651 { return _M_h.find(__x); }
652
654 find(const key_type& __x) const
655 { return _M_h.find(__x); }
656 ///@}
657
658 /**
659 * @brief Finds the number of elements.
660 * @param __x Element to located.
661 * @return Number of elements with specified key.
662 *
663 * This function only makes sense for unordered_multisets; for
664 * unordered_set the result will either be 0 (not present) or 1
665 * (present).
666 */
668 count(const key_type& __x) const
669 { return _M_h.count(__x); }
670
671#if __cplusplus > 201703L
672 /**
673 * @brief Finds whether an element with the given key exists.
674 * @param __x Key of elements to be located.
675 * @return True if there is any element with the specified key.
676 */
677 bool
678 contains(const key_type& __x) const
679 { return _M_h.find(__x) != _M_h.end(); }
680#endif
681
682 ///@{
683 /**
684 * @brief Finds a subsequence matching given key.
685 * @param __x Key to be located.
686 * @return Pair of iterators that possibly points to the subsequence
687 * matching given key.
688 *
689 * This function probably only makes sense for multisets.
690 */
693 { return _M_h.equal_range(__x); }
694
696 equal_range(const key_type& __x) const
697 { return _M_h.equal_range(__x); }
698 ///@}
699
700 // bucket interface.
701
702 /// Returns the number of buckets of the %unordered_set.
704 bucket_count() const noexcept
705 { return _M_h.bucket_count(); }
706
707 /// Returns the maximum number of buckets of the %unordered_set.
709 max_bucket_count() const noexcept
710 { return _M_h.max_bucket_count(); }
711
712 /*
713 * @brief Returns the number of elements in a given bucket.
714 * @param __n A bucket index.
715 * @return The number of elements in the bucket.
716 */
718 bucket_size(size_type __n) const
719 { return _M_h.bucket_size(__n); }
720
721 /*
722 * @brief Returns the bucket index of a given element.
723 * @param __key A key instance.
724 * @return The key bucket index.
725 */
727 bucket(const key_type& __key) const
728 { return _M_h.bucket(__key); }
729
730 ///@{
731 /**
732 * @brief Returns a read-only (constant) iterator pointing to the first
733 * bucket element.
734 * @param __n The bucket index.
735 * @return A read-only local iterator.
736 */
739 { return _M_h.begin(__n); }
740
742 begin(size_type __n) const
743 { return _M_h.begin(__n); }
744
746 cbegin(size_type __n) const
747 { return _M_h.cbegin(__n); }
748 ///@}
749
750 ///@{
751 /**
752 * @brief Returns a read-only (constant) iterator pointing to one past
753 * the last bucket elements.
754 * @param __n The bucket index.
755 * @return A read-only local iterator.
756 */
759 { return _M_h.end(__n); }
760
762 end(size_type __n) const
763 { return _M_h.end(__n); }
764
766 cend(size_type __n) const
767 { return _M_h.cend(__n); }
768 ///@}
769
770 // hash policy.
771
772 /// Returns the average number of elements per bucket.
773 float
774 load_factor() const noexcept
775 { return _M_h.load_factor(); }
776
777 /// Returns a positive number that the %unordered_set tries to keep the
778 /// load factor less than or equal to.
779 float
780 max_load_factor() const noexcept
781 { return _M_h.max_load_factor(); }
782
783 /**
784 * @brief Change the %unordered_set maximum load factor.
785 * @param __z The new maximum load factor.
786 */
787 void
789 { _M_h.max_load_factor(__z); }
790
791 /**
792 * @brief May rehash the %unordered_set.
793 * @param __n The new number of buckets.
794 *
795 * Rehash will occur only if the new number of buckets respect the
796 * %unordered_set maximum load factor.
797 */
798 void
800 { _M_h.rehash(__n); }
801
802 /**
803 * @brief Prepare the %unordered_set for a specified number of
804 * elements.
805 * @param __n Number of elements required.
806 *
807 * Same as rehash(ceil(n / max_load_factor())).
808 */
809 void
811 { _M_h.reserve(__n); }
812
813 template<typename _Value1, typename _Hash1, typename _Pred1,
814 typename _Alloc1>
815 friend bool
818 };
819
820#if __cpp_deduction_guides >= 201606
821
822 template<typename _InputIterator,
823 typename _Hash =
824 hash<typename iterator_traits<_InputIterator>::value_type>,
825 typename _Pred =
826 equal_to<typename iterator_traits<_InputIterator>::value_type>,
827 typename _Allocator =
828 allocator<typename iterator_traits<_InputIterator>::value_type>,
829 typename = _RequireInputIter<_InputIterator>,
830 typename = _RequireNotAllocatorOrIntegral<_Hash>,
831 typename = _RequireNotAllocator<_Pred>,
832 typename = _RequireAllocator<_Allocator>>
833 unordered_set(_InputIterator, _InputIterator,
835 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
836 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
837 _Hash, _Pred, _Allocator>;
838
839 template<typename _Tp, typename _Hash = hash<_Tp>,
840 typename _Pred = equal_to<_Tp>,
841 typename _Allocator = allocator<_Tp>,
842 typename = _RequireNotAllocatorOrIntegral<_Hash>,
843 typename = _RequireNotAllocator<_Pred>,
844 typename = _RequireAllocator<_Allocator>>
845 unordered_set(initializer_list<_Tp>,
847 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
848 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
849
850 template<typename _InputIterator, typename _Allocator,
851 typename = _RequireInputIter<_InputIterator>,
852 typename = _RequireAllocator<_Allocator>>
853 unordered_set(_InputIterator, _InputIterator,
856 hash<
857 typename iterator_traits<_InputIterator>::value_type>,
858 equal_to<
859 typename iterator_traits<_InputIterator>::value_type>,
860 _Allocator>;
861
862 template<typename _InputIterator, typename _Hash, typename _Allocator,
863 typename = _RequireInputIter<_InputIterator>,
864 typename = _RequireNotAllocatorOrIntegral<_Hash>,
865 typename = _RequireAllocator<_Allocator>>
866 unordered_set(_InputIterator, _InputIterator,
868 _Hash, _Allocator)
870 _Hash,
871 equal_to<
872 typename iterator_traits<_InputIterator>::value_type>,
873 _Allocator>;
874
875 template<typename _Tp, typename _Allocator,
876 typename = _RequireAllocator<_Allocator>>
877 unordered_set(initializer_list<_Tp>,
879 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
880
881 template<typename _Tp, typename _Hash, typename _Allocator,
882 typename = _RequireNotAllocatorOrIntegral<_Hash>,
883 typename = _RequireAllocator<_Allocator>>
884 unordered_set(initializer_list<_Tp>,
885 unordered_set<int>::size_type, _Hash, _Allocator)
886 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
887
888#endif
889
890 /**
891 * @brief A standard container composed of equivalent keys
892 * (possibly containing multiple of each key value) in which the
893 * elements' keys are the elements themselves.
894 *
895 * @ingroup unordered_associative_containers
896 *
897 * @tparam _Value Type of key objects.
898 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
899 * @tparam _Pred Predicate function object type, defaults
900 * to equal_to<_Value>.
901 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
902 *
903 * Meets the requirements of a <a href="tables.html#65">container</a>, and
904 * <a href="tables.html#xx">unordered associative container</a>
905 *
906 * Base is _Hashtable, dispatched at compile time via template
907 * alias __umset_hashtable.
908 */
909 template<typename _Value,
910 typename _Hash = hash<_Value>,
911 typename _Pred = equal_to<_Value>,
912 typename _Alloc = allocator<_Value>>
914 {
916 _Hashtable _M_h;
917
918 public:
919 // typedefs:
920 ///@{
921 /// Public typedefs.
922 typedef typename _Hashtable::key_type key_type;
923 typedef typename _Hashtable::value_type value_type;
924 typedef typename _Hashtable::hasher hasher;
925 typedef typename _Hashtable::key_equal key_equal;
926 typedef typename _Hashtable::allocator_type allocator_type;
927 ///@}
928
929 ///@{
930 /// Iterator-related typedefs.
931 typedef typename _Hashtable::pointer pointer;
932 typedef typename _Hashtable::const_pointer const_pointer;
933 typedef typename _Hashtable::reference reference;
934 typedef typename _Hashtable::const_reference const_reference;
935 typedef typename _Hashtable::iterator iterator;
936 typedef typename _Hashtable::const_iterator const_iterator;
937 typedef typename _Hashtable::local_iterator local_iterator;
938 typedef typename _Hashtable::const_local_iterator const_local_iterator;
939 typedef typename _Hashtable::size_type size_type;
940 typedef typename _Hashtable::difference_type difference_type;
941 ///@}
942
943#if __cplusplus > 201402L
944 using node_type = typename _Hashtable::node_type;
945#endif
946
947 // construct/destroy/copy
948
949 /// Default constructor.
951
952 /**
953 * @brief Default constructor creates no elements.
954 * @param __n Minimal initial number of buckets.
955 * @param __hf A hash functor.
956 * @param __eql A key equality functor.
957 * @param __a An allocator object.
958 */
959 explicit
961 const hasher& __hf = hasher(),
962 const key_equal& __eql = key_equal(),
963 const allocator_type& __a = allocator_type())
964 : _M_h(__n, __hf, __eql, __a)
965 { }
966
967 /**
968 * @brief Builds an %unordered_multiset from a range.
969 * @param __first An input iterator.
970 * @param __last An input iterator.
971 * @param __n Minimal initial number of buckets.
972 * @param __hf A hash functor.
973 * @param __eql A key equality functor.
974 * @param __a An allocator object.
975 *
976 * Create an %unordered_multiset consisting of copies of the elements
977 * from [__first,__last). This is linear in N (where N is
978 * distance(__first,__last)).
979 */
980 template<typename _InputIterator>
981 unordered_multiset(_InputIterator __first, _InputIterator __last,
982 size_type __n = 0,
983 const hasher& __hf = hasher(),
984 const key_equal& __eql = key_equal(),
985 const allocator_type& __a = allocator_type())
986 : _M_h(__first, __last, __n, __hf, __eql, __a)
987 { }
988
989 /// Copy constructor.
991
992 /// Move constructor.
994
995 /**
996 * @brief Builds an %unordered_multiset from an initializer_list.
997 * @param __l An initializer_list.
998 * @param __n Minimal initial number of buckets.
999 * @param __hf A hash functor.
1000 * @param __eql A key equality functor.
1001 * @param __a An allocator object.
1002 *
1003 * Create an %unordered_multiset consisting of copies of the elements in
1004 * the list. This is linear in N (where N is @a __l.size()).
1005 */
1007 size_type __n = 0,
1008 const hasher& __hf = hasher(),
1009 const key_equal& __eql = key_equal(),
1010 const allocator_type& __a = allocator_type())
1011 : _M_h(__l, __n, __hf, __eql, __a)
1012 { }
1013
1014 /// Copy assignment operator.
1017
1018 /// Move assignment operator.
1021
1022 /**
1023 * @brief Creates an %unordered_multiset with no elements.
1024 * @param __a An allocator object.
1025 */
1026 explicit
1028 : _M_h(__a)
1029 { }
1030
1031 /*
1032 * @brief Copy constructor with allocator argument.
1033 * @param __uset Input %unordered_multiset to copy.
1034 * @param __a An allocator object.
1035 */
1037 const allocator_type& __a)
1038 : _M_h(__umset._M_h, __a)
1039 { }
1040
1041 /*
1042 * @brief Move constructor with allocator argument.
1043 * @param __umset Input %unordered_multiset to move.
1044 * @param __a An allocator object.
1045 */
1047 const allocator_type& __a)
1048 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1049 : _M_h(std::move(__umset._M_h), __a)
1050 { }
1051
1053 : unordered_multiset(__n, hasher(), key_equal(), __a)
1054 { }
1055
1056 unordered_multiset(size_type __n, const hasher& __hf,
1057 const allocator_type& __a)
1058 : unordered_multiset(__n, __hf, key_equal(), __a)
1059 { }
1060
1061 template<typename _InputIterator>
1062 unordered_multiset(_InputIterator __first, _InputIterator __last,
1063 size_type __n,
1064 const allocator_type& __a)
1065 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1066 { }
1067
1068 template<typename _InputIterator>
1069 unordered_multiset(_InputIterator __first, _InputIterator __last,
1070 size_type __n, const hasher& __hf,
1071 const allocator_type& __a)
1072 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1073 { }
1074
1075 unordered_multiset(initializer_list<value_type> __l,
1076 size_type __n,
1077 const allocator_type& __a)
1078 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1079 { }
1080
1081 unordered_multiset(initializer_list<value_type> __l,
1082 size_type __n, const hasher& __hf,
1083 const allocator_type& __a)
1084 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1085 { }
1086
1087 /**
1088 * @brief %Unordered_multiset list assignment operator.
1089 * @param __l An initializer_list.
1090 *
1091 * This function fills an %unordered_multiset with copies of the elements
1092 * in the initializer list @a __l.
1093 *
1094 * Note that the assignment completely changes the %unordered_multiset
1095 * and that the resulting %unordered_multiset's size is the same as the
1096 * number of elements assigned.
1097 */
1100 {
1101 _M_h = __l;
1102 return *this;
1103 }
1104
1105 /// Returns the allocator object used by the %unordered_multiset.
1107 get_allocator() const noexcept
1108 { return _M_h.get_allocator(); }
1109
1110 // size and capacity:
1111
1112 /// Returns true if the %unordered_multiset is empty.
1113 _GLIBCXX_NODISCARD bool
1114 empty() const noexcept
1115 { return _M_h.empty(); }
1116
1117 /// Returns the size of the %unordered_multiset.
1118 size_type
1119 size() const noexcept
1120 { return _M_h.size(); }
1121
1122 /// Returns the maximum size of the %unordered_multiset.
1123 size_type
1124 max_size() const noexcept
1125 { return _M_h.max_size(); }
1126
1127 // iterators.
1128
1129 ///@{
1130 /**
1131 * Returns a read-only (constant) iterator that points to the first
1132 * element in the %unordered_multiset.
1133 */
1134 iterator
1135 begin() noexcept
1136 { return _M_h.begin(); }
1137
1139 begin() const noexcept
1140 { return _M_h.begin(); }
1141 ///@}
1142
1143 ///@{
1144 /**
1145 * Returns a read-only (constant) iterator that points one past the last
1146 * element in the %unordered_multiset.
1147 */
1148 iterator
1149 end() noexcept
1150 { return _M_h.end(); }
1151
1153 end() const noexcept
1154 { return _M_h.end(); }
1155 ///@}
1156
1157 /**
1158 * Returns a read-only (constant) iterator that points to the first
1159 * element in the %unordered_multiset.
1160 */
1162 cbegin() const noexcept
1163 { return _M_h.begin(); }
1164
1165 /**
1166 * Returns a read-only (constant) iterator that points one past the last
1167 * element in the %unordered_multiset.
1168 */
1170 cend() const noexcept
1171 { return _M_h.end(); }
1172
1173 // modifiers.
1174
1175 /**
1176 * @brief Builds and insert an element into the %unordered_multiset.
1177 * @param __args Arguments used to generate an element.
1178 * @return An iterator that points to the inserted element.
1179 *
1180 * Insertion requires amortized constant time.
1181 */
1182 template<typename... _Args>
1183 iterator
1184 emplace(_Args&&... __args)
1185 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1186
1187 /**
1188 * @brief Inserts an element into the %unordered_multiset.
1189 * @param __pos An iterator that serves as a hint as to where the
1190 * element should be inserted.
1191 * @param __args Arguments used to generate the element to be
1192 * inserted.
1193 * @return An iterator that points to the inserted element.
1194 *
1195 * Note that the first parameter is only a hint and can potentially
1196 * improve the performance of the insertion process. A bad hint would
1197 * cause no gains in efficiency.
1198 *
1199 * For more on @a hinting, see:
1200 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1201 *
1202 * Insertion requires amortized constant time.
1203 */
1204 template<typename... _Args>
1205 iterator
1206 emplace_hint(const_iterator __pos, _Args&&... __args)
1207 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1208
1209 ///@{
1210 /**
1211 * @brief Inserts an element into the %unordered_multiset.
1212 * @param __x Element to be inserted.
1213 * @return An iterator that points to the inserted element.
1214 *
1215 * Insertion requires amortized constant time.
1216 */
1217 iterator
1218 insert(const value_type& __x)
1219 { return _M_h.insert(__x); }
1220
1221 iterator
1223 { return _M_h.insert(std::move(__x)); }
1224 ///@}
1225
1226 ///@{
1227 /**
1228 * @brief Inserts an element into the %unordered_multiset.
1229 * @param __hint An iterator that serves as a hint as to where the
1230 * element should be inserted.
1231 * @param __x Element to be inserted.
1232 * @return An iterator that points to the inserted element.
1233 *
1234 * Note that the first parameter is only a hint and can potentially
1235 * improve the performance of the insertion process. A bad hint would
1236 * cause no gains in efficiency.
1237 *
1238 * For more on @a hinting, see:
1239 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1240 *
1241 * Insertion requires amortized constant.
1242 */
1243 iterator
1245 { return _M_h.insert(__hint, __x); }
1246
1247 iterator
1249 { return _M_h.insert(__hint, std::move(__x)); }
1250 ///@}
1251
1252 /**
1253 * @brief A template function that inserts a range of elements.
1254 * @param __first Iterator pointing to the start of the range to be
1255 * inserted.
1256 * @param __last Iterator pointing to the end of the range.
1257 *
1258 * Complexity similar to that of the range constructor.
1259 */
1260 template<typename _InputIterator>
1261 void
1262 insert(_InputIterator __first, _InputIterator __last)
1263 { _M_h.insert(__first, __last); }
1264
1265 /**
1266 * @brief Inserts a list of elements into the %unordered_multiset.
1267 * @param __l A std::initializer_list<value_type> of elements to be
1268 * inserted.
1269 *
1270 * Complexity similar to that of the range constructor.
1271 */
1272 void
1274 { _M_h.insert(__l); }
1275
1276#if __cplusplus > 201402L
1277 /// Extract a node.
1278 node_type
1279 extract(const_iterator __pos)
1280 {
1281 __glibcxx_assert(__pos != end());
1282 return _M_h.extract(__pos);
1283 }
1284
1285 /// Extract a node.
1286 node_type
1287 extract(const key_type& __key)
1288 { return _M_h.extract(__key); }
1289
1290 /// Re-insert an extracted node.
1291 iterator
1292 insert(node_type&& __nh)
1293 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1294
1295 /// Re-insert an extracted node.
1296 iterator
1297 insert(const_iterator __hint, node_type&& __nh)
1298 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1299#endif // C++17
1300
1301 ///@{
1302 /**
1303 * @brief Erases an element from an %unordered_multiset.
1304 * @param __position An iterator pointing to the element to be erased.
1305 * @return An iterator pointing to the element immediately following
1306 * @a __position prior to the element being erased. If no such
1307 * element exists, end() is returned.
1308 *
1309 * This function erases an element, pointed to by the given iterator,
1310 * from an %unordered_multiset.
1311 *
1312 * Note that this function only erases the element, and that if the
1313 * element is itself a pointer, the pointed-to memory is not touched in
1314 * any way. Managing the pointer is the user's responsibility.
1315 */
1316 iterator
1318 { return _M_h.erase(__position); }
1319
1320 // LWG 2059.
1321 iterator
1322 erase(iterator __position)
1323 { return _M_h.erase(__position); }
1324 ///@}
1325
1326
1327 /**
1328 * @brief Erases elements according to the provided key.
1329 * @param __x Key of element to be erased.
1330 * @return The number of elements erased.
1331 *
1332 * This function erases all the elements located by the given key from
1333 * an %unordered_multiset.
1334 *
1335 * Note that this function only erases the element, and that if the
1336 * element is itself a pointer, the pointed-to memory is not touched in
1337 * any way. Managing the pointer is the user's responsibility.
1338 */
1339 size_type
1340 erase(const key_type& __x)
1341 { return _M_h.erase(__x); }
1342
1343 /**
1344 * @brief Erases a [__first,__last) range of elements from an
1345 * %unordered_multiset.
1346 * @param __first Iterator pointing to the start of the range to be
1347 * erased.
1348 * @param __last Iterator pointing to the end of the range to
1349 * be erased.
1350 * @return The iterator @a __last.
1351 *
1352 * This function erases a sequence of elements from an
1353 * %unordered_multiset.
1354 *
1355 * Note that this function only erases the element, and that if
1356 * the element is itself a pointer, the pointed-to memory is not touched
1357 * in any way. Managing the pointer is the user's responsibility.
1358 */
1359 iterator
1361 { return _M_h.erase(__first, __last); }
1362
1363 /**
1364 * Erases all elements in an %unordered_multiset.
1365 *
1366 * Note that this function only erases the elements, and that if the
1367 * elements themselves are pointers, the pointed-to memory is not touched
1368 * in any way. Managing the pointer is the user's responsibility.
1369 */
1370 void
1371 clear() noexcept
1372 { _M_h.clear(); }
1373
1374 /**
1375 * @brief Swaps data with another %unordered_multiset.
1376 * @param __x An %unordered_multiset of the same element and allocator
1377 * types.
1378 *
1379 * This exchanges the elements between two sets in constant time.
1380 * Note that the global std::swap() function is specialized such that
1381 * std::swap(s1,s2) will feed to this function.
1382 */
1383 void
1385 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1386 { _M_h.swap(__x._M_h); }
1387
1388#if __cplusplus > 201402L
1389 template<typename, typename, typename>
1390 friend class std::_Hash_merge_helper;
1391
1392 template<typename _H2, typename _P2>
1393 void
1395 {
1396 using _Merge_helper
1397 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1398 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1399 }
1400
1401 template<typename _H2, typename _P2>
1402 void
1403 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1404 { merge(__source); }
1405
1406 template<typename _H2, typename _P2>
1407 void
1408 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1409 {
1410 using _Merge_helper
1411 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1412 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1413 }
1414
1415 template<typename _H2, typename _P2>
1416 void
1417 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1418 { merge(__source); }
1419#endif // C++17
1420
1421 // observers.
1422
1423 /// Returns the hash functor object with which the %unordered_multiset
1424 /// was constructed.
1425 hasher
1427 { return _M_h.hash_function(); }
1428
1429 /// Returns the key comparison object with which the %unordered_multiset
1430 /// was constructed.
1431 key_equal
1432 key_eq() const
1433 { return _M_h.key_eq(); }
1434
1435 // lookup.
1436
1437 ///@{
1438 /**
1439 * @brief Tries to locate an element in an %unordered_multiset.
1440 * @param __x Element to be located.
1441 * @return Iterator pointing to sought-after element, or end() if not
1442 * found.
1443 *
1444 * This function takes a key and tries to locate the element with which
1445 * the key matches. If successful the function returns an iterator
1446 * pointing to the sought after element. If unsuccessful it returns the
1447 * past-the-end ( @c end() ) iterator.
1448 */
1449 iterator
1450 find(const key_type& __x)
1451 { return _M_h.find(__x); }
1452
1454 find(const key_type& __x) const
1455 { return _M_h.find(__x); }
1456 ///@}
1457
1458 /**
1459 * @brief Finds the number of elements.
1460 * @param __x Element to located.
1461 * @return Number of elements with specified key.
1462 */
1463 size_type
1464 count(const key_type& __x) const
1465 { return _M_h.count(__x); }
1466
1467#if __cplusplus > 201703L
1468 /**
1469 * @brief Finds whether an element with the given key exists.
1470 * @param __x Key of elements to be located.
1471 * @return True if there is any element with the specified key.
1472 */
1473 bool
1474 contains(const key_type& __x) const
1475 { return _M_h.find(__x) != _M_h.end(); }
1476#endif
1477
1478 ///@{
1479 /**
1480 * @brief Finds a subsequence matching given key.
1481 * @param __x Key to be located.
1482 * @return Pair of iterators that possibly points to the subsequence
1483 * matching given key.
1484 */
1487 { return _M_h.equal_range(__x); }
1488
1490 equal_range(const key_type& __x) const
1491 { return _M_h.equal_range(__x); }
1492 ///@}
1493
1494 // bucket interface.
1495
1496 /// Returns the number of buckets of the %unordered_multiset.
1497 size_type
1498 bucket_count() const noexcept
1499 { return _M_h.bucket_count(); }
1500
1501 /// Returns the maximum number of buckets of the %unordered_multiset.
1502 size_type
1503 max_bucket_count() const noexcept
1504 { return _M_h.max_bucket_count(); }
1505
1506 /*
1507 * @brief Returns the number of elements in a given bucket.
1508 * @param __n A bucket index.
1509 * @return The number of elements in the bucket.
1510 */
1511 size_type
1512 bucket_size(size_type __n) const
1513 { return _M_h.bucket_size(__n); }
1514
1515 /*
1516 * @brief Returns the bucket index of a given element.
1517 * @param __key A key instance.
1518 * @return The key bucket index.
1519 */
1520 size_type
1521 bucket(const key_type& __key) const
1522 { return _M_h.bucket(__key); }
1523
1524 ///@{
1525 /**
1526 * @brief Returns a read-only (constant) iterator pointing to the first
1527 * bucket element.
1528 * @param __n The bucket index.
1529 * @return A read-only local iterator.
1530 */
1533 { return _M_h.begin(__n); }
1534
1536 begin(size_type __n) const
1537 { return _M_h.begin(__n); }
1538
1541 { return _M_h.cbegin(__n); }
1542 ///@}
1543
1544 ///@{
1545 /**
1546 * @brief Returns a read-only (constant) iterator pointing to one past
1547 * the last bucket elements.
1548 * @param __n The bucket index.
1549 * @return A read-only local iterator.
1550 */
1553 { return _M_h.end(__n); }
1554
1556 end(size_type __n) const
1557 { return _M_h.end(__n); }
1558
1560 cend(size_type __n) const
1561 { return _M_h.cend(__n); }
1562 ///@}
1563
1564 // hash policy.
1565
1566 /// Returns the average number of elements per bucket.
1567 float
1568 load_factor() const noexcept
1569 { return _M_h.load_factor(); }
1570
1571 /// Returns a positive number that the %unordered_multiset tries to keep the
1572 /// load factor less than or equal to.
1573 float
1574 max_load_factor() const noexcept
1575 { return _M_h.max_load_factor(); }
1576
1577 /**
1578 * @brief Change the %unordered_multiset maximum load factor.
1579 * @param __z The new maximum load factor.
1580 */
1581 void
1583 { _M_h.max_load_factor(__z); }
1584
1585 /**
1586 * @brief May rehash the %unordered_multiset.
1587 * @param __n The new number of buckets.
1588 *
1589 * Rehash will occur only if the new number of buckets respect the
1590 * %unordered_multiset maximum load factor.
1591 */
1592 void
1594 { _M_h.rehash(__n); }
1595
1596 /**
1597 * @brief Prepare the %unordered_multiset for a specified number of
1598 * elements.
1599 * @param __n Number of elements required.
1600 *
1601 * Same as rehash(ceil(n / max_load_factor())).
1602 */
1603 void
1605 { _M_h.reserve(__n); }
1606
1607 template<typename _Value1, typename _Hash1, typename _Pred1,
1608 typename _Alloc1>
1609 friend bool
1612 };
1613
1614
1615#if __cpp_deduction_guides >= 201606
1616
1617 template<typename _InputIterator,
1618 typename _Hash =
1619 hash<typename iterator_traits<_InputIterator>::value_type>,
1620 typename _Pred =
1621 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1622 typename _Allocator =
1623 allocator<typename iterator_traits<_InputIterator>::value_type>,
1624 typename = _RequireInputIter<_InputIterator>,
1625 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1626 typename = _RequireNotAllocator<_Pred>,
1627 typename = _RequireAllocator<_Allocator>>
1628 unordered_multiset(_InputIterator, _InputIterator,
1630 _Hash = _Hash(), _Pred = _Pred(),
1631 _Allocator = _Allocator())
1632 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1633 _Hash, _Pred, _Allocator>;
1634
1635 template<typename _Tp, typename _Hash = hash<_Tp>,
1636 typename _Pred = equal_to<_Tp>,
1637 typename _Allocator = allocator<_Tp>,
1638 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1639 typename = _RequireNotAllocator<_Pred>,
1640 typename = _RequireAllocator<_Allocator>>
1641 unordered_multiset(initializer_list<_Tp>,
1643 _Hash = _Hash(), _Pred = _Pred(),
1644 _Allocator = _Allocator())
1645 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1646
1647 template<typename _InputIterator, typename _Allocator,
1648 typename = _RequireInputIter<_InputIterator>,
1649 typename = _RequireAllocator<_Allocator>>
1650 unordered_multiset(_InputIterator, _InputIterator,
1653 hash<typename
1654 iterator_traits<_InputIterator>::value_type>,
1655 equal_to<typename
1656 iterator_traits<_InputIterator>::value_type>,
1657 _Allocator>;
1658
1659 template<typename _InputIterator, typename _Hash, typename _Allocator,
1660 typename = _RequireInputIter<_InputIterator>,
1661 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1662 typename = _RequireAllocator<_Allocator>>
1663 unordered_multiset(_InputIterator, _InputIterator,
1665 _Hash, _Allocator)
1666 -> unordered_multiset<typename
1667 iterator_traits<_InputIterator>::value_type,
1668 _Hash,
1669 equal_to<
1670 typename
1671 iterator_traits<_InputIterator>::value_type>,
1672 _Allocator>;
1673
1674 template<typename _Tp, typename _Allocator,
1675 typename = _RequireAllocator<_Allocator>>
1676 unordered_multiset(initializer_list<_Tp>,
1678 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1679
1680 template<typename _Tp, typename _Hash, typename _Allocator,
1681 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1682 typename = _RequireAllocator<_Allocator>>
1683 unordered_multiset(initializer_list<_Tp>,
1684 unordered_multiset<int>::size_type, _Hash, _Allocator)
1685 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1686
1687#endif
1688
1689 template<class _Value, class _Hash, class _Pred, class _Alloc>
1690 inline void
1691 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1692 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1693 noexcept(noexcept(__x.swap(__y)))
1694 { __x.swap(__y); }
1695
1696 template<class _Value, class _Hash, class _Pred, class _Alloc>
1697 inline void
1698 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1699 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1700 noexcept(noexcept(__x.swap(__y)))
1701 { __x.swap(__y); }
1702
1703 template<class _Value, class _Hash, class _Pred, class _Alloc>
1704 inline bool
1705 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1706 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1707 { return __x._M_h._M_equal(__y._M_h); }
1708
1709 template<class _Value, class _Hash, class _Pred, class _Alloc>
1710 inline bool
1711 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1712 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1713 { return !(__x == __y); }
1714
1715 template<class _Value, class _Hash, class _Pred, class _Alloc>
1716 inline bool
1717 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1718 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1719 { return __x._M_h._M_equal(__y._M_h); }
1720
1721 template<class _Value, class _Hash, class _Pred, class _Alloc>
1722 inline bool
1723 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1724 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1725 { return !(__x == __y); }
1726
1727_GLIBCXX_END_NAMESPACE_CONTAINER
1728
1729#if __cplusplus > 201402L
1730 // Allow std::unordered_set access to internals of compatible sets.
1731 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1732 typename _Hash2, typename _Eq2>
1733 struct _Hash_merge_helper<
1734 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1735 {
1736 private:
1737 template<typename... _Tp>
1738 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1739 template<typename... _Tp>
1740 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1741
1742 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1743
1744 static auto&
1745 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1746 { return __set._M_h; }
1747
1748 static auto&
1749 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1750 { return __set._M_h; }
1751 };
1752
1753 // Allow std::unordered_multiset access to internals of compatible sets.
1754 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1755 typename _Hash2, typename _Eq2>
1756 struct _Hash_merge_helper<
1757 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1758 _Hash2, _Eq2>
1759 {
1760 private:
1761 template<typename... _Tp>
1762 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1763 template<typename... _Tp>
1764 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1765
1766 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1767
1768 static auto&
1769 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1770 { return __set._M_h; }
1771
1772 static auto&
1773 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1774 { return __set._M_h; }
1775 };
1776#endif // C++17
1777
1778_GLIBCXX_END_NAMESPACE_VERSION
1779} // namespace std
1780
1781#endif /* _UNORDERED_SET_H */
ISO C++ entities toplevel namespace is std.
initializer_list
Primary class template hash.
The standard allocator, as per [20.4].
Definition: allocator.h:112
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.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
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.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
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...
const_iterator cend() const noexcept
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator emplace(_Args &&... __args)
Builds and insert an element into the unordered_multiset.
unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from a range.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
_Hashtable::allocator_type allocator_type
Public typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
_Hashtable::value_type value_type
Public typedefs.
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::size_type size_type
Iterator-related typedefs.
_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.
_Hashtable::reference reference
Iterator-related typedefs.
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.
const_iterator begin() const noexcept
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.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
const_iterator end() const noexcept
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
iterator erase(iterator __position)
Erases an element from an 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_multiset.
_Hashtable::hasher hasher
Public typedefs.
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.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_multiset is empty.
_Hashtable::iterator iterator
Iterator-related typedefs.
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.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset(const unordered_multiset &)=default
Copy constructor.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multiset.
_Hashtable::key_equal key_equal
Public typedefs.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:98
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::iterator iterator
Iterator-related typedefs.
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.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the unordered_set is empty.
_Hashtable::reference reference
Iterator-related typedefs.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::value_type value_type
Public typedefs.
const_iterator cend() const noexcept
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
_Hashtable::key_type key_type
Public typedefs.
size_type count(const key_type &__x) const
Finds the number of elements.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
const_iterator begin() const noexcept
_Hashtable::hasher hasher
Public typedefs.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
_Hashtable::size_type size_type
Iterator-related typedefs.
const_iterator cbegin() const noexcept
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
iterator erase(iterator __position)
Erases an element from an unordered_set.
unordered_set(unordered_set &&)=default
Move constructor.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
_Hashtable::const_pointer const_pointer
Iterator-related typedefs.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
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.
std::pair< iterator, bool > insert(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.
_Hashtable::key_equal key_equal
Public typedefs.
size_type size() const noexcept
Returns the size of the unordered_set.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
_Hashtable::const_reference const_reference
Iterator-related typedefs.
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.
_Hashtable::allocator_type allocator_type
Public typedefs.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
const_iterator end() const noexcept
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 used by the unordered_set.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
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.