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