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