unordered_set.h source code [include/c++/7/bits/unordered

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