1// unordered_set implementation -*- C++ -*-
2
3// Copyright (C) 2010-2022 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>
40 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
41
42 template<typename _Value,
43 typename _Hash = hash<_Value>,
44 typename _Pred = std::equal_to<_Value>,
45 typename _Alloc = std::allocator<_Value>,
46 typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
47 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
48 __detail::_Identity, _Pred, _Hash,
49 __detail::_Mod_range_hashing,
50 __detail::_Default_ranged_hash,
51 __detail::_Prime_rehash_policy, _Tr>;
52
53 /// Base types for unordered_multiset.
54 template<bool _Cache>
55 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
56
57 template<typename _Value,
58 typename _Hash = hash<_Value>,
59 typename _Pred = std::equal_to<_Value>,
60 typename _Alloc = std::allocator<_Value>,
61 typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
62 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
63 __detail::_Identity,
64 _Pred, _Hash,
65 __detail::_Mod_range_hashing,
66 __detail::_Default_ranged_hash,
67 __detail::_Prime_rehash_policy, _Tr>;
68
69 template<class _Value, class _Hash, class _Pred, class _Alloc>
70 class unordered_multiset;
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>>
97 class unordered_set
98 {
99 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
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.
178 unordered_set(unordered_set&&) = default;
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 */
204 unordered_set(unordered_set&& __uset,
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 */
221 unordered_set(initializer_list<value_type> __l,
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.
265 unordered_set&
266 operator=(const unordered_set&) = default;
267
268 /// Move assignment operator.
269 unordered_set&
270 operator=(unordered_set&&) = default;
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 */
283 unordered_set&
284 operator=(initializer_list<value_type> __l)
285 {
286 _M_h = __l;
287 return *this;
288 }
289
290 /// Returns the allocator object used by the %unordered_set.
291 allocator_type
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.
303 size_type
304 size() const noexcept
305 { return _M_h.size(); }
306
307 /// Returns the maximum size of the %unordered_set.
308 size_type
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 */
319 iterator
320 begin() noexcept
321 { return _M_h.begin(); }
322
323 const_iterator
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 */
333 iterator
334 end() noexcept
335 { return _M_h.end(); }
336
337 const_iterator
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 */
346 const_iterator
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 */
354 const_iterator
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>
376 std::pair<iterator, bool>
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>
402 iterator
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 */
420 std::pair<iterator, bool>
421 insert(const value_type& __x)
422 { return _M_h.insert(__x); }
423
424 std::pair<iterator, bool>
425 insert(value_type&& __x)
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 */
449 iterator
450 insert(const_iterator __hint, const value_type& __x)
451 { return _M_h.insert(__hint, __x); }
452
453 iterator
454 insert(const_iterator __hint, value_type&& __x)
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
480 insert(initializer_list<value_type> __l)
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.
503 iterator
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 */
522 iterator
523 erase(const_iterator __position)
524 { return _M_h.erase(__position); }
525
526 // LWG 2059.
527 iterator
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 */
544 size_type
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 */
562 iterator
563 erase(const_iterator __first, const_iterator __last)
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
586 swap(unordered_set& __x)
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
596 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
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
626 hash_function() const
627 { return _M_h.hash_function(); }
628
629 /// Returns the key comparison object with which the %unordered_set was
630 /// constructed.
631 key_equal
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 */
649 iterator
650 find(const key_type& __x)
651 { return _M_h.find(__x); }
652
653#if __cplusplus > 201703L
654 template<typename _Kt>
655 auto
656 find(const _Kt& __k)
657 -> decltype(_M_h._M_find_tr(__k))
658 { return _M_h._M_find_tr(__k); }
659#endif
660
661 const_iterator
662 find(const key_type& __x) const
663 { return _M_h.find(__x); }
664
665#if __cplusplus > 201703L
666 template<typename _Kt>
667 auto
668 find(const _Kt& __k) const
669 -> decltype(_M_h._M_find_tr(__k))
670 { return _M_h._M_find_tr(__k); }
671#endif
672 ///@}
673
674 ///@{
675 /**
676 * @brief Finds the number of elements.
677 * @param __x Element to located.
678 * @return Number of elements with specified key.
679 *
680 * This function only makes sense for unordered_multisets; for
681 * unordered_set the result will either be 0 (not present) or 1
682 * (present).
683 */
684 size_type
685 count(const key_type& __x) const
686 { return _M_h.count(__x); }
687
688#if __cplusplus > 201703L
689 template<typename _Kt>
690 auto
691 count(const _Kt& __k) const
692 -> decltype(_M_h._M_count_tr(__k))
693 { return _M_h._M_count_tr(__k); }
694#endif
695 ///@}
696
697#if __cplusplus > 201703L
698 ///@{
699 /**
700 * @brief Finds whether an element with the given key exists.
701 * @param __x Key of elements to be located.
702 * @return True if there is any element with the specified key.
703 */
704 bool
705 contains(const key_type& __x) const
706 { return _M_h.find(__x) != _M_h.end(); }
707
708 template<typename _Kt>
709 auto
710 contains(const _Kt& __k) const
711 -> decltype(_M_h._M_find_tr(__k), void(), true)
712 { return _M_h._M_find_tr(__k) != _M_h.end(); }
713 ///@}
714#endif
715
716 ///@{
717 /**
718 * @brief Finds a subsequence matching given key.
719 * @param __x Key to be located.
720 * @return Pair of iterators that possibly points to the subsequence
721 * matching given key.
722 *
723 * This function probably only makes sense for multisets.
724 */
725 std::pair<iterator, iterator>
726 equal_range(const key_type& __x)
727 { return _M_h.equal_range(__x); }
728
729#if __cplusplus > 201703L
730 template<typename _Kt>
731 auto
732 equal_range(const _Kt& __k)
733 -> decltype(_M_h._M_equal_range_tr(__k))
734 { return _M_h._M_equal_range_tr(__k); }
735#endif
736
737 std::pair<const_iterator, const_iterator>
738 equal_range(const key_type& __x) const
739 { return _M_h.equal_range(__x); }
740
741#if __cplusplus > 201703L
742 template<typename _Kt>
743 auto
744 equal_range(const _Kt& __k) const
745 -> decltype(_M_h._M_equal_range_tr(__k))
746 { return _M_h._M_equal_range_tr(__k); }
747#endif
748 ///@}
749
750 // bucket interface.
751
752 /// Returns the number of buckets of the %unordered_set.
753 size_type
754 bucket_count() const noexcept
755 { return _M_h.bucket_count(); }
756
757 /// Returns the maximum number of buckets of the %unordered_set.
758 size_type
759 max_bucket_count() const noexcept
760 { return _M_h.max_bucket_count(); }
761
762 /*
763 * @brief Returns the number of elements in a given bucket.
764 * @param __n A bucket index.
765 * @return The number of elements in the bucket.
766 */
767 size_type
768 bucket_size(size_type __n) const
769 { return _M_h.bucket_size(__n); }
770
771 /*
772 * @brief Returns the bucket index of a given element.
773 * @param __key A key instance.
774 * @return The key bucket index.
775 */
776 size_type
777 bucket(const key_type& __key) const
778 { return _M_h.bucket(__key); }
779
780 ///@{
781 /**
782 * @brief Returns a read-only (constant) iterator pointing to the first
783 * bucket element.
784 * @param __n The bucket index.
785 * @return A read-only local iterator.
786 */
787 local_iterator
788 begin(size_type __n)
789 { return _M_h.begin(__n); }
790
791 const_local_iterator
792 begin(size_type __n) const
793 { return _M_h.begin(__n); }
794
795 const_local_iterator
796 cbegin(size_type __n) const
797 { return _M_h.cbegin(__n); }
798 ///@}
799
800 ///@{
801 /**
802 * @brief Returns a read-only (constant) iterator pointing to one past
803 * the last bucket elements.
804 * @param __n The bucket index.
805 * @return A read-only local iterator.
806 */
807 local_iterator
808 end(size_type __n)
809 { return _M_h.end(__n); }
810
811 const_local_iterator
812 end(size_type __n) const
813 { return _M_h.end(__n); }
814
815 const_local_iterator
816 cend(size_type __n) const
817 { return _M_h.cend(__n); }
818 ///@}
819
820 // hash policy.
821
822 /// Returns the average number of elements per bucket.
823 float
824 load_factor() const noexcept
825 { return _M_h.load_factor(); }
826
827 /// Returns a positive number that the %unordered_set tries to keep the
828 /// load factor less than or equal to.
829 float
830 max_load_factor() const noexcept
831 { return _M_h.max_load_factor(); }
832
833 /**
834 * @brief Change the %unordered_set maximum load factor.
835 * @param __z The new maximum load factor.
836 */
837 void
838 max_load_factor(float __z)
839 { _M_h.max_load_factor(__z); }
840
841 /**
842 * @brief May rehash the %unordered_set.
843 * @param __n The new number of buckets.
844 *
845 * Rehash will occur only if the new number of buckets respect the
846 * %unordered_set maximum load factor.
847 */
848 void
849 rehash(size_type __n)
850 { _M_h.rehash(__n); }
851
852 /**
853 * @brief Prepare the %unordered_set for a specified number of
854 * elements.
855 * @param __n Number of elements required.
856 *
857 * Same as rehash(ceil(n / max_load_factor())).
858 */
859 void
860 reserve(size_type __n)
861 { _M_h.reserve(__n); }
862
863 template<typename _Value1, typename _Hash1, typename _Pred1,
864 typename _Alloc1>
865 friend bool
866 operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
867 const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
868 };
869
870#if __cpp_deduction_guides >= 201606
871
872 template<typename _InputIterator,
873 typename _Hash =
874 hash<typename iterator_traits<_InputIterator>::value_type>,
875 typename _Pred =
876 equal_to<typename iterator_traits<_InputIterator>::value_type>,
877 typename _Allocator =
878 allocator<typename iterator_traits<_InputIterator>::value_type>,
879 typename = _RequireInputIter<_InputIterator>,
880 typename = _RequireNotAllocatorOrIntegral<_Hash>,
881 typename = _RequireNotAllocator<_Pred>,
882 typename = _RequireAllocator<_Allocator>>
883 unordered_set(_InputIterator, _InputIterator,
884 unordered_set<int>::size_type = {},
885 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
886 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
887 _Hash, _Pred, _Allocator>;
888
889 template<typename _Tp, typename _Hash = hash<_Tp>,
890 typename _Pred = equal_to<_Tp>,
891 typename _Allocator = allocator<_Tp>,
892 typename = _RequireNotAllocatorOrIntegral<_Hash>,
893 typename = _RequireNotAllocator<_Pred>,
894 typename = _RequireAllocator<_Allocator>>
895 unordered_set(initializer_list<_Tp>,
896 unordered_set<int>::size_type = {},
897 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
898 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
899
900 template<typename _InputIterator, typename _Allocator,
901 typename = _RequireInputIter<_InputIterator>,
902 typename = _RequireAllocator<_Allocator>>
903 unordered_set(_InputIterator, _InputIterator,
904 unordered_set<int>::size_type, _Allocator)
905 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
906 hash<
907 typename iterator_traits<_InputIterator>::value_type>,
908 equal_to<
909 typename iterator_traits<_InputIterator>::value_type>,
910 _Allocator>;
911
912 template<typename _InputIterator, typename _Hash, typename _Allocator,
913 typename = _RequireInputIter<_InputIterator>,
914 typename = _RequireNotAllocatorOrIntegral<_Hash>,
915 typename = _RequireAllocator<_Allocator>>
916 unordered_set(_InputIterator, _InputIterator,
917 unordered_set<int>::size_type,
918 _Hash, _Allocator)
919 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
920 _Hash,
921 equal_to<
922 typename iterator_traits<_InputIterator>::value_type>,
923 _Allocator>;
924
925 template<typename _Tp, typename _Allocator,
926 typename = _RequireAllocator<_Allocator>>
927 unordered_set(initializer_list<_Tp>,
928 unordered_set<int>::size_type, _Allocator)
929 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
930
931 template<typename _Tp, typename _Hash, typename _Allocator,
932 typename = _RequireNotAllocatorOrIntegral<_Hash>,
933 typename = _RequireAllocator<_Allocator>>
934 unordered_set(initializer_list<_Tp>,
935 unordered_set<int>::size_type, _Hash, _Allocator)
936 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
937
938#endif
939
940 /**
941 * @brief A standard container composed of equivalent keys
942 * (possibly containing multiple of each key value) in which the
943 * elements' keys are the elements themselves.
944 *
945 * @ingroup unordered_associative_containers
946 *
947 * @tparam _Value Type of key objects.
948 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
949 * @tparam _Pred Predicate function object type, defaults
950 * to equal_to<_Value>.
951 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
952 *
953 * Meets the requirements of a <a href="tables.html#65">container</a>, and
954 * <a href="tables.html#xx">unordered associative container</a>
955 *
956 * Base is _Hashtable, dispatched at compile time via template
957 * alias __umset_hashtable.
958 */
959 template<typename _Value,
960 typename _Hash = hash<_Value>,
961 typename _Pred = equal_to<_Value>,
962 typename _Alloc = allocator<_Value>>
963 class unordered_multiset
964 {
965 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
966 _Hashtable _M_h;
967
968 public:
969 // typedefs:
970 ///@{
971 /// Public typedefs.
972 typedef typename _Hashtable::key_type key_type;
973 typedef typename _Hashtable::value_type value_type;
974 typedef typename _Hashtable::hasher hasher;
975 typedef typename _Hashtable::key_equal key_equal;
976 typedef typename _Hashtable::allocator_type allocator_type;
977 ///@}
978
979 ///@{
980 /// Iterator-related typedefs.
981 typedef typename _Hashtable::pointer pointer;
982 typedef typename _Hashtable::const_pointer const_pointer;
983 typedef typename _Hashtable::reference reference;
984 typedef typename _Hashtable::const_reference const_reference;
985 typedef typename _Hashtable::iterator iterator;
986 typedef typename _Hashtable::const_iterator const_iterator;
987 typedef typename _Hashtable::local_iterator local_iterator;
988 typedef typename _Hashtable::const_local_iterator const_local_iterator;
989 typedef typename _Hashtable::size_type size_type;
990 typedef typename _Hashtable::difference_type difference_type;
991 ///@}
992
993#if __cplusplus > 201402L
994 using node_type = typename _Hashtable::node_type;
995#endif
996
997 // construct/destroy/copy
998
999 /// Default constructor.
1000 unordered_multiset() = default;
1001
1002 /**
1003 * @brief Default constructor creates no elements.
1004 * @param __n Minimal initial number of buckets.
1005 * @param __hf A hash functor.
1006 * @param __eql A key equality functor.
1007 * @param __a An allocator object.
1008 */
1009 explicit
1010 unordered_multiset(size_type __n,
1011 const hasher& __hf = hasher(),
1012 const key_equal& __eql = key_equal(),
1013 const allocator_type& __a = allocator_type())
1014 : _M_h(__n, __hf, __eql, __a)
1015 { }
1016
1017 /**
1018 * @brief Builds an %unordered_multiset from a range.
1019 * @param __first An input iterator.
1020 * @param __last An input iterator.
1021 * @param __n Minimal initial number of buckets.
1022 * @param __hf A hash functor.
1023 * @param __eql A key equality functor.
1024 * @param __a An allocator object.
1025 *
1026 * Create an %unordered_multiset consisting of copies of the elements
1027 * from [__first,__last). This is linear in N (where N is
1028 * distance(__first,__last)).
1029 */
1030 template<typename _InputIterator>
1031 unordered_multiset(_InputIterator __first, _InputIterator __last,
1032 size_type __n = 0,
1033 const hasher& __hf = hasher(),
1034 const key_equal& __eql = key_equal(),
1035 const allocator_type& __a = allocator_type())
1036 : _M_h(__first, __last, __n, __hf, __eql, __a)
1037 { }
1038
1039 /// Copy constructor.
1040 unordered_multiset(const unordered_multiset&) = default;
1041
1042 /// Move constructor.
1043 unordered_multiset(unordered_multiset&&) = default;
1044
1045 /**
1046 * @brief Builds an %unordered_multiset from an initializer_list.
1047 * @param __l An initializer_list.
1048 * @param __n Minimal initial number of buckets.
1049 * @param __hf A hash functor.
1050 * @param __eql A key equality functor.
1051 * @param __a An allocator object.
1052 *
1053 * Create an %unordered_multiset consisting of copies of the elements in
1054 * the list. This is linear in N (where N is @a __l.size()).
1055 */
1056 unordered_multiset(initializer_list<value_type> __l,
1057 size_type __n = 0,
1058 const hasher& __hf = hasher(),
1059 const key_equal& __eql = key_equal(),
1060 const allocator_type& __a = allocator_type())
1061 : _M_h(__l, __n, __hf, __eql, __a)
1062 { }
1063
1064 /// Copy assignment operator.
1065 unordered_multiset&
1066 operator=(const unordered_multiset&) = default;
1067
1068 /// Move assignment operator.
1069 unordered_multiset&
1070 operator=(unordered_multiset&&) = default;
1071
1072 /**
1073 * @brief Creates an %unordered_multiset with no elements.
1074 * @param __a An allocator object.
1075 */
1076 explicit
1077 unordered_multiset(const allocator_type& __a)
1078 : _M_h(__a)
1079 { }
1080
1081 /*
1082 * @brief Copy constructor with allocator argument.
1083 * @param __uset Input %unordered_multiset to copy.
1084 * @param __a An allocator object.
1085 */
1086 unordered_multiset(const unordered_multiset& __umset,
1087 const allocator_type& __a)
1088 : _M_h(__umset._M_h, __a)
1089 { }
1090
1091 /*
1092 * @brief Move constructor with allocator argument.
1093 * @param __umset Input %unordered_multiset to move.
1094 * @param __a An allocator object.
1095 */
1096 unordered_multiset(unordered_multiset&& __umset,
1097 const allocator_type& __a)
1098 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1099 : _M_h(std::move(__umset._M_h), __a)
1100 { }
1101
1102 unordered_multiset(size_type __n, const allocator_type& __a)
1103 : unordered_multiset(__n, hasher(), key_equal(), __a)
1104 { }
1105
1106 unordered_multiset(size_type __n, const hasher& __hf,
1107 const allocator_type& __a)
1108 : unordered_multiset(__n, __hf, key_equal(), __a)
1109 { }
1110
1111 template<typename _InputIterator>
1112 unordered_multiset(_InputIterator __first, _InputIterator __last,
1113 size_type __n,
1114 const allocator_type& __a)
1115 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1116 { }
1117
1118 template<typename _InputIterator>
1119 unordered_multiset(_InputIterator __first, _InputIterator __last,
1120 size_type __n, const hasher& __hf,
1121 const allocator_type& __a)
1122 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1123 { }
1124
1125 unordered_multiset(initializer_list<value_type> __l,
1126 size_type __n,
1127 const allocator_type& __a)
1128 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1129 { }
1130
1131 unordered_multiset(initializer_list<value_type> __l,
1132 size_type __n, const hasher& __hf,
1133 const allocator_type& __a)
1134 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1135 { }
1136
1137 /**
1138 * @brief %Unordered_multiset list assignment operator.
1139 * @param __l An initializer_list.
1140 *
1141 * This function fills an %unordered_multiset with copies of the elements
1142 * in the initializer list @a __l.
1143 *
1144 * Note that the assignment completely changes the %unordered_multiset
1145 * and that the resulting %unordered_multiset's size is the same as the
1146 * number of elements assigned.
1147 */
1148 unordered_multiset&
1149 operator=(initializer_list<value_type> __l)
1150 {
1151 _M_h = __l;
1152 return *this;
1153 }
1154
1155 /// Returns the allocator object used by the %unordered_multiset.
1156 allocator_type
1157 get_allocator() const noexcept
1158 { return _M_h.get_allocator(); }
1159
1160 // size and capacity:
1161
1162 /// Returns true if the %unordered_multiset is empty.
1163 _GLIBCXX_NODISCARD bool
1164 empty() const noexcept
1165 { return _M_h.empty(); }
1166
1167 /// Returns the size of the %unordered_multiset.
1168 size_type
1169 size() const noexcept
1170 { return _M_h.size(); }
1171
1172 /// Returns the maximum size of the %unordered_multiset.
1173 size_type
1174 max_size() const noexcept
1175 { return _M_h.max_size(); }
1176
1177 // iterators.
1178
1179 ///@{
1180 /**
1181 * Returns a read-only (constant) iterator that points to the first
1182 * element in the %unordered_multiset.
1183 */
1184 iterator
1185 begin() noexcept
1186 { return _M_h.begin(); }
1187
1188 const_iterator
1189 begin() const noexcept
1190 { return _M_h.begin(); }
1191 ///@}
1192
1193 ///@{
1194 /**
1195 * Returns a read-only (constant) iterator that points one past the last
1196 * element in the %unordered_multiset.
1197 */
1198 iterator
1199 end() noexcept
1200 { return _M_h.end(); }
1201
1202 const_iterator
1203 end() const noexcept
1204 { return _M_h.end(); }
1205 ///@}
1206
1207 /**
1208 * Returns a read-only (constant) iterator that points to the first
1209 * element in the %unordered_multiset.
1210 */
1211 const_iterator
1212 cbegin() const noexcept
1213 { return _M_h.begin(); }
1214
1215 /**
1216 * Returns a read-only (constant) iterator that points one past the last
1217 * element in the %unordered_multiset.
1218 */
1219 const_iterator
1220 cend() const noexcept
1221 { return _M_h.end(); }
1222
1223 // modifiers.
1224
1225 /**
1226 * @brief Builds and insert an element into the %unordered_multiset.
1227 * @param __args Arguments used to generate an element.
1228 * @return An iterator that points to the inserted element.
1229 *
1230 * Insertion requires amortized constant time.
1231 */
1232 template<typename... _Args>
1233 iterator
1234 emplace(_Args&&... __args)
1235 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1236
1237 /**
1238 * @brief Inserts an element into the %unordered_multiset.
1239 * @param __pos An iterator that serves as a hint as to where the
1240 * element should be inserted.
1241 * @param __args Arguments used to generate the element to be
1242 * inserted.
1243 * @return An iterator that points to the inserted element.
1244 *
1245 * Note that the first parameter is only a hint and can potentially
1246 * improve the performance of the insertion process. A bad hint would
1247 * cause no gains in efficiency.
1248 *
1249 * For more on @a hinting, see:
1250 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1251 *
1252 * Insertion requires amortized constant time.
1253 */
1254 template<typename... _Args>
1255 iterator
1256 emplace_hint(const_iterator __pos, _Args&&... __args)
1257 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1258
1259 ///@{
1260 /**
1261 * @brief Inserts an element into the %unordered_multiset.
1262 * @param __x Element to be inserted.
1263 * @return An iterator that points to the inserted element.
1264 *
1265 * Insertion requires amortized constant time.
1266 */
1267 iterator
1268 insert(const value_type& __x)
1269 { return _M_h.insert(__x); }
1270
1271 iterator
1272 insert(value_type&& __x)
1273 { return _M_h.insert(std::move(__x)); }
1274 ///@}
1275
1276 ///@{
1277 /**
1278 * @brief Inserts an element into the %unordered_multiset.
1279 * @param __hint An iterator that serves as a hint as to where the
1280 * element should be inserted.
1281 * @param __x Element to be inserted.
1282 * @return An iterator that points to the inserted element.
1283 *
1284 * Note that the first parameter is only a hint and can potentially
1285 * improve the performance of the insertion process. A bad hint would
1286 * cause no gains in efficiency.
1287 *
1288 * For more on @a hinting, see:
1289 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1290 *
1291 * Insertion requires amortized constant.
1292 */
1293 iterator
1294 insert(const_iterator __hint, const value_type& __x)
1295 { return _M_h.insert(__hint, __x); }
1296
1297 iterator
1298 insert(const_iterator __hint, value_type&& __x)
1299 { return _M_h.insert(__hint, std::move(__x)); }
1300 ///@}
1301
1302 /**
1303 * @brief A template function that inserts a range of elements.
1304 * @param __first Iterator pointing to the start of the range to be
1305 * inserted.
1306 * @param __last Iterator pointing to the end of the range.
1307 *
1308 * Complexity similar to that of the range constructor.
1309 */
1310 template<typename _InputIterator>
1311 void
1312 insert(_InputIterator __first, _InputIterator __last)
1313 { _M_h.insert(__first, __last); }
1314
1315 /**
1316 * @brief Inserts a list of elements into the %unordered_multiset.
1317 * @param __l A std::initializer_list<value_type> of elements to be
1318 * inserted.
1319 *
1320 * Complexity similar to that of the range constructor.
1321 */
1322 void
1323 insert(initializer_list<value_type> __l)
1324 { _M_h.insert(__l); }
1325
1326#if __cplusplus > 201402L
1327 /// Extract a node.
1328 node_type
1329 extract(const_iterator __pos)
1330 {
1331 __glibcxx_assert(__pos != end());
1332 return _M_h.extract(__pos);
1333 }
1334
1335 /// Extract a node.
1336 node_type
1337 extract(const key_type& __key)
1338 { return _M_h.extract(__key); }
1339
1340 /// Re-insert an extracted node.
1341 iterator
1342 insert(node_type&& __nh)
1343 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1344
1345 /// Re-insert an extracted node.
1346 iterator
1347 insert(const_iterator __hint, node_type&& __nh)
1348 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1349#endif // C++17
1350
1351 ///@{
1352 /**
1353 * @brief Erases an element from an %unordered_multiset.
1354 * @param __position An iterator pointing to the element to be erased.
1355 * @return An iterator pointing to the element immediately following
1356 * @a __position prior to the element being erased. If no such
1357 * element exists, end() is returned.
1358 *
1359 * This function erases an element, pointed to by the given iterator,
1360 * from an %unordered_multiset.
1361 *
1362 * Note that this function only erases the element, and that if the
1363 * element is itself a pointer, the pointed-to memory is not touched in
1364 * any way. Managing the pointer is the user's responsibility.
1365 */
1366 iterator
1367 erase(const_iterator __position)
1368 { return _M_h.erase(__position); }
1369
1370 // LWG 2059.
1371 iterator
1372 erase(iterator __position)
1373 { return _M_h.erase(__position); }
1374 ///@}
1375
1376
1377 /**
1378 * @brief Erases elements according to the provided key.
1379 * @param __x Key of element to be erased.
1380 * @return The number of elements erased.
1381 *
1382 * This function erases all the elements located by the given key from
1383 * an %unordered_multiset.
1384 *
1385 * Note that this function only erases the element, and that if the
1386 * element is itself a pointer, the pointed-to memory is not touched in
1387 * any way. Managing the pointer is the user's responsibility.
1388 */
1389 size_type
1390 erase(const key_type& __x)
1391 { return _M_h.erase(__x); }
1392
1393 /**
1394 * @brief Erases a [__first,__last) range of elements from an
1395 * %unordered_multiset.
1396 * @param __first Iterator pointing to the start of the range to be
1397 * erased.
1398 * @param __last Iterator pointing to the end of the range to
1399 * be erased.
1400 * @return The iterator @a __last.
1401 *
1402 * This function erases a sequence of elements from an
1403 * %unordered_multiset.
1404 *
1405 * Note that this function only erases the element, and that if
1406 * the element is itself a pointer, the pointed-to memory is not touched
1407 * in any way. Managing the pointer is the user's responsibility.
1408 */
1409 iterator
1410 erase(const_iterator __first, const_iterator __last)
1411 { return _M_h.erase(__first, __last); }
1412
1413 /**
1414 * Erases all elements in an %unordered_multiset.
1415 *
1416 * Note that this function only erases the elements, and that if the
1417 * elements themselves are pointers, the pointed-to memory is not touched
1418 * in any way. Managing the pointer is the user's responsibility.
1419 */
1420 void
1421 clear() noexcept
1422 { _M_h.clear(); }
1423
1424 /**
1425 * @brief Swaps data with another %unordered_multiset.
1426 * @param __x An %unordered_multiset of the same element and allocator
1427 * types.
1428 *
1429 * This exchanges the elements between two sets in constant time.
1430 * Note that the global std::swap() function is specialized such that
1431 * std::swap(s1,s2) will feed to this function.
1432 */
1433 void
1434 swap(unordered_multiset& __x)
1435 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1436 { _M_h.swap(__x._M_h); }
1437
1438#if __cplusplus > 201402L
1439 template<typename, typename, typename>
1440 friend class std::_Hash_merge_helper;
1441
1442 template<typename _H2, typename _P2>
1443 void
1444 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1445 {
1446 using _Merge_helper
1447 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1448 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1449 }
1450
1451 template<typename _H2, typename _P2>
1452 void
1453 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1454 { merge(__source); }
1455
1456 template<typename _H2, typename _P2>
1457 void
1458 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1459 {
1460 using _Merge_helper
1461 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1462 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1463 }
1464
1465 template<typename _H2, typename _P2>
1466 void
1467 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1468 { merge(__source); }
1469#endif // C++17
1470
1471 // observers.
1472
1473 /// Returns the hash functor object with which the %unordered_multiset
1474 /// was constructed.
1475 hasher
1476 hash_function() const
1477 { return _M_h.hash_function(); }
1478
1479 /// Returns the key comparison object with which the %unordered_multiset
1480 /// was constructed.
1481 key_equal
1482 key_eq() const
1483 { return _M_h.key_eq(); }
1484
1485 // lookup.
1486
1487 ///@{
1488 /**
1489 * @brief Tries to locate an element in an %unordered_multiset.
1490 * @param __x Element to be located.
1491 * @return Iterator pointing to sought-after element, or end() if not
1492 * found.
1493 *
1494 * This function takes a key and tries to locate the element with which
1495 * the key matches. If successful the function returns an iterator
1496 * pointing to the sought after element. If unsuccessful it returns the
1497 * past-the-end ( @c end() ) iterator.
1498 */
1499 iterator
1500 find(const key_type& __x)
1501 { return _M_h.find(__x); }
1502
1503#if __cplusplus > 201703L
1504 template<typename _Kt>
1505 auto
1506 find(const _Kt& __x)
1507 -> decltype(_M_h._M_find_tr(__x))
1508 { return _M_h._M_find_tr(__x); }
1509#endif
1510
1511 const_iterator
1512 find(const key_type& __x) const
1513 { return _M_h.find(__x); }
1514
1515#if __cplusplus > 201703L
1516 template<typename _Kt>
1517 auto
1518 find(const _Kt& __x) const
1519 -> decltype(_M_h._M_find_tr(__x))
1520 { return _M_h._M_find_tr(__x); }
1521#endif
1522 ///@}
1523
1524 ///@{
1525 /**
1526 * @brief Finds the number of elements.
1527 * @param __x Element to located.
1528 * @return Number of elements with specified key.
1529 */
1530 size_type
1531 count(const key_type& __x) const
1532 { return _M_h.count(__x); }
1533
1534#if __cplusplus > 201703L
1535 template<typename _Kt>
1536 auto
1537 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1538 { return _M_h._M_count_tr(__x); }
1539#endif
1540 ///@}
1541
1542#if __cplusplus > 201703L
1543 ///@{
1544 /**
1545 * @brief Finds whether an element with the given key exists.
1546 * @param __x Key of elements to be located.
1547 * @return True if there is any element with the specified key.
1548 */
1549 bool
1550 contains(const key_type& __x) const
1551 { return _M_h.find(__x) != _M_h.end(); }
1552
1553 template<typename _Kt>
1554 auto
1555 contains(const _Kt& __x) const
1556 -> decltype(_M_h._M_find_tr(__x), void(), true)
1557 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1558 ///@}
1559#endif
1560
1561 ///@{
1562 /**
1563 * @brief Finds a subsequence matching given key.
1564 * @param __x Key to be located.
1565 * @return Pair of iterators that possibly points to the subsequence
1566 * matching given key.
1567 */
1568 std::pair<iterator, iterator>
1569 equal_range(const key_type& __x)
1570 { return _M_h.equal_range(__x); }
1571
1572#if __cplusplus > 201703L
1573 template<typename _Kt>
1574 auto
1575 equal_range(const _Kt& __x)
1576 -> decltype(_M_h._M_equal_range_tr(__x))
1577 { return _M_h._M_equal_range_tr(__x); }
1578#endif
1579
1580 std::pair<const_iterator, const_iterator>
1581 equal_range(const key_type& __x) const
1582 { return _M_h.equal_range(__x); }
1583
1584#if __cplusplus > 201703L
1585 template<typename _Kt>
1586 auto
1587 equal_range(const _Kt& __x) const
1588 -> decltype(_M_h._M_equal_range_tr(__x))
1589 { return _M_h._M_equal_range_tr(__x); }
1590#endif
1591 ///@}
1592
1593 // bucket interface.
1594
1595 /// Returns the number of buckets of the %unordered_multiset.
1596 size_type
1597 bucket_count() const noexcept
1598 { return _M_h.bucket_count(); }
1599
1600 /// Returns the maximum number of buckets of the %unordered_multiset.
1601 size_type
1602 max_bucket_count() const noexcept
1603 { return _M_h.max_bucket_count(); }
1604
1605 /*
1606 * @brief Returns the number of elements in a given bucket.
1607 * @param __n A bucket index.
1608 * @return The number of elements in the bucket.
1609 */
1610 size_type
1611 bucket_size(size_type __n) const
1612 { return _M_h.bucket_size(__n); }
1613
1614 /*
1615 * @brief Returns the bucket index of a given element.
1616 * @param __key A key instance.
1617 * @return The key bucket index.
1618 */
1619 size_type
1620 bucket(const key_type& __key) const
1621 { return _M_h.bucket(__key); }
1622
1623 ///@{
1624 /**
1625 * @brief Returns a read-only (constant) iterator pointing to the first
1626 * bucket element.
1627 * @param __n The bucket index.
1628 * @return A read-only local iterator.
1629 */
1630 local_iterator
1631 begin(size_type __n)
1632 { return _M_h.begin(__n); }
1633
1634 const_local_iterator
1635 begin(size_type __n) const
1636 { return _M_h.begin(__n); }
1637
1638 const_local_iterator
1639 cbegin(size_type __n) const
1640 { return _M_h.cbegin(__n); }
1641 ///@}
1642
1643 ///@{
1644 /**
1645 * @brief Returns a read-only (constant) iterator pointing to one past
1646 * the last bucket elements.
1647 * @param __n The bucket index.
1648 * @return A read-only local iterator.
1649 */
1650 local_iterator
1651 end(size_type __n)
1652 { return _M_h.end(__n); }
1653
1654 const_local_iterator
1655 end(size_type __n) const
1656 { return _M_h.end(__n); }
1657
1658 const_local_iterator
1659 cend(size_type __n) const
1660 { return _M_h.cend(__n); }
1661 ///@}
1662
1663 // hash policy.
1664
1665 /// Returns the average number of elements per bucket.
1666 float
1667 load_factor() const noexcept
1668 { return _M_h.load_factor(); }
1669
1670 /// Returns a positive number that the %unordered_multiset tries to keep the
1671 /// load factor less than or equal to.
1672 float
1673 max_load_factor() const noexcept
1674 { return _M_h.max_load_factor(); }
1675
1676 /**
1677 * @brief Change the %unordered_multiset maximum load factor.
1678 * @param __z The new maximum load factor.
1679 */
1680 void
1681 max_load_factor(float __z)
1682 { _M_h.max_load_factor(__z); }
1683
1684 /**
1685 * @brief May rehash the %unordered_multiset.
1686 * @param __n The new number of buckets.
1687 *
1688 * Rehash will occur only if the new number of buckets respect the
1689 * %unordered_multiset maximum load factor.
1690 */
1691 void
1692 rehash(size_type __n)
1693 { _M_h.rehash(__n); }
1694
1695 /**
1696 * @brief Prepare the %unordered_multiset for a specified number of
1697 * elements.
1698 * @param __n Number of elements required.
1699 *
1700 * Same as rehash(ceil(n / max_load_factor())).
1701 */
1702 void
1703 reserve(size_type __n)
1704 { _M_h.reserve(__n); }
1705
1706 template<typename _Value1, typename _Hash1, typename _Pred1,
1707 typename _Alloc1>
1708 friend bool
1709 operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
1710 const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
1711 };
1712
1713
1714#if __cpp_deduction_guides >= 201606
1715
1716 template<typename _InputIterator,
1717 typename _Hash =
1718 hash<typename iterator_traits<_InputIterator>::value_type>,
1719 typename _Pred =
1720 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1721 typename _Allocator =
1722 allocator<typename iterator_traits<_InputIterator>::value_type>,
1723 typename = _RequireInputIter<_InputIterator>,
1724 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1725 typename = _RequireNotAllocator<_Pred>,
1726 typename = _RequireAllocator<_Allocator>>
1727 unordered_multiset(_InputIterator, _InputIterator,
1728 unordered_multiset<int>::size_type = {},
1729 _Hash = _Hash(), _Pred = _Pred(),
1730 _Allocator = _Allocator())
1731 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1732 _Hash, _Pred, _Allocator>;
1733
1734 template<typename _Tp, typename _Hash = hash<_Tp>,
1735 typename _Pred = equal_to<_Tp>,
1736 typename _Allocator = allocator<_Tp>,
1737 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1738 typename = _RequireNotAllocator<_Pred>,
1739 typename = _RequireAllocator<_Allocator>>
1740 unordered_multiset(initializer_list<_Tp>,
1741 unordered_multiset<int>::size_type = {},
1742 _Hash = _Hash(), _Pred = _Pred(),
1743 _Allocator = _Allocator())
1744 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1745
1746 template<typename _InputIterator, typename _Allocator,
1747 typename = _RequireInputIter<_InputIterator>,
1748 typename = _RequireAllocator<_Allocator>>
1749 unordered_multiset(_InputIterator, _InputIterator,
1750 unordered_multiset<int>::size_type, _Allocator)
1751 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1752 hash<typename
1753 iterator_traits<_InputIterator>::value_type>,
1754 equal_to<typename
1755 iterator_traits<_InputIterator>::value_type>,
1756 _Allocator>;
1757
1758 template<typename _InputIterator, typename _Hash, typename _Allocator,
1759 typename = _RequireInputIter<_InputIterator>,
1760 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1761 typename = _RequireAllocator<_Allocator>>
1762 unordered_multiset(_InputIterator, _InputIterator,
1763 unordered_multiset<int>::size_type,
1764 _Hash, _Allocator)
1765 -> unordered_multiset<typename
1766 iterator_traits<_InputIterator>::value_type,
1767 _Hash,
1768 equal_to<
1769 typename
1770 iterator_traits<_InputIterator>::value_type>,
1771 _Allocator>;
1772
1773 template<typename _Tp, typename _Allocator,
1774 typename = _RequireAllocator<_Allocator>>
1775 unordered_multiset(initializer_list<_Tp>,
1776 unordered_multiset<int>::size_type, _Allocator)
1777 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1778
1779 template<typename _Tp, typename _Hash, typename _Allocator,
1780 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1781 typename = _RequireAllocator<_Allocator>>
1782 unordered_multiset(initializer_list<_Tp>,
1783 unordered_multiset<int>::size_type, _Hash, _Allocator)
1784 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1785
1786#endif
1787
1788 template<class _Value, class _Hash, class _Pred, class _Alloc>
1789 inline void
1790 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1791 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1792 noexcept(noexcept(__x.swap(__y)))
1793 { __x.swap(__y); }
1794
1795 template<class _Value, class _Hash, class _Pred, class _Alloc>
1796 inline void
1797 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1798 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1799 noexcept(noexcept(__x.swap(__y)))
1800 { __x.swap(__y); }
1801
1802 template<class _Value, class _Hash, class _Pred, class _Alloc>
1803 inline bool
1804 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1805 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1806 { return __x._M_h._M_equal(__y._M_h); }
1807
1808#if __cpp_impl_three_way_comparison < 201907L
1809 template<class _Value, class _Hash, class _Pred, class _Alloc>
1810 inline bool
1811 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1812 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1813 { return !(__x == __y); }
1814#endif
1815
1816 template<class _Value, class _Hash, class _Pred, class _Alloc>
1817 inline bool
1818 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1819 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1820 { return __x._M_h._M_equal(__y._M_h); }
1821
1822#if __cpp_impl_three_way_comparison < 201907L
1823 template<class _Value, class _Hash, class _Pred, class _Alloc>
1824 inline bool
1825 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1826 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1827 { return !(__x == __y); }
1828#endif
1829
1830_GLIBCXX_END_NAMESPACE_CONTAINER
1831
1832#if __cplusplus > 201402L
1833 // Allow std::unordered_set access to internals of compatible sets.
1834 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1835 typename _Hash2, typename _Eq2>
1836 struct _Hash_merge_helper<
1837 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1838 {
1839 private:
1840 template<typename... _Tp>
1841 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1842 template<typename... _Tp>
1843 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1844
1845 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1846
1847 static auto&
1848 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1849 { return __set._M_h; }
1850
1851 static auto&
1852 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1853 { return __set._M_h; }
1854 };
1855
1856 // Allow std::unordered_multiset access to internals of compatible sets.
1857 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1858 typename _Hash2, typename _Eq2>
1859 struct _Hash_merge_helper<
1860 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1861 _Hash2, _Eq2>
1862 {
1863 private:
1864 template<typename... _Tp>
1865 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1866 template<typename... _Tp>
1867 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1868
1869 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1870
1871 static auto&
1872 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1873 { return __set._M_h; }
1874
1875 static auto&
1876 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1877 { return __set._M_h; }
1878 };
1879#endif // C++17
1880
1881_GLIBCXX_END_NAMESPACE_VERSION
1882} // namespace std
1883
1884#endif /* _UNORDERED_SET_H */
1885