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