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