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