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