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