1	// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
2	// Copyright (C) 2005-2011 Daniel James.
3	// Copyright (C) 2022-2023 Christian Mazakas
4	// Copyright (C) 2024 Joaquin M Lopez Munoz.
5	// Distributed under the Boost Software License, Version 1.0. (See accompanying
6	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7
8	// See http://www.boost.org/libs/unordered for documentation
9
10	#ifndef BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
11	#define BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
12
13	#include <boost/config.hpp>
14	#if defined(BOOST_HAS_PRAGMA_ONCE)
15	#pragma once
16	#endif
17
18	#include <boost/unordered/detail/map.hpp>
19	#include <boost/unordered/detail/serialize_fca_container.hpp>
20	#include <boost/unordered/detail/throw_exception.hpp>
21	#include <boost/unordered/detail/type_traits.hpp>
22
23	#include <boost/container_hash/hash.hpp>
24
25	#include <initializer_list>
26
27	#if defined(BOOST_MSVC)
28	#pragma warning(push)
29	// conditional expression is constant
30	#pragma warning(disable : 4127)
31	#if BOOST_MSVC >= 1400
32	// the inline specifier cannot be used when a friend declaration refers to a
33	// specialization of a function template
34	#pragma warning(disable : 4396)
35	#endif
36	#endif
37
38	namespace boost {
39	namespace unordered {
40	template <class K, class T, class H, class P, class A> class unordered_map
41	{
42	template <typename, typename, typename, typename, typename>
43	friend class unordered_multimap;
44
45	public:
46	typedef K key_type;
47	typedef T mapped_type;
48	typedef std::pair<const K, T> value_type;
49	typedef typename boost::unordered::detail::type_identity<H>::type hasher;
50	typedef
51	typename boost::unordered::detail::type_identity<P>::type key_equal;
52	typedef typename boost::unordered::detail::type_identity<A>::type
53	allocator_type;
54
55	private:
56	typedef boost::unordered::detail::map<A, K, T, H, P> types;
57	typedef typename types::value_allocator_traits value_allocator_traits;
58	typedef typename types::table table;
59
60	public:
61	typedef typename value_allocator_traits::pointer pointer;
62	typedef typename value_allocator_traits::const_pointer const_pointer;
63
64	typedef value_type& reference;
65	typedef value_type const& const_reference;
66
67	typedef std::size_t size_type;
68	typedef std::ptrdiff_t difference_type;
69
70	typedef typename table::iterator iterator;
71	typedef typename table::c_iterator const_iterator;
72	typedef typename table::l_iterator local_iterator;
73	typedef typename table::cl_iterator const_local_iterator;
74	typedef typename types::node_type node_type;
75	typedef typename types::insert_return_type insert_return_type;
76
77	private:
78	table table_;
79
80	public:
81	// constructors
82
83	unordered_map();
84
85	explicit unordered_map(size_type, const hasher& = hasher(),
86	const key_equal& = key_equal(),
87	const allocator_type& = allocator_type());
88
89	template <class InputIt>
90	unordered_map(InputIt, InputIt,
91	size_type = boost::unordered::detail::default_bucket_count,
92	const hasher& = hasher(), const key_equal& = key_equal(),
93	const allocator_type& = allocator_type());
94
95	unordered_map(unordered_map const&);
96
97	unordered_map(unordered_map&& other)
98	noexcept(table::nothrow_move_constructible)
99	: table_(other.table_, boost::unordered::detail::move_tag())
100	{
101	// The move is done in table_
102	}
103
104	explicit unordered_map(allocator_type const&);
105
106	unordered_map(unordered_map const&, allocator_type const&);
107
108	unordered_map(unordered_map&&, allocator_type const&);
109
110	unordered_map(std::initializer_list<value_type>,
111	size_type = boost::unordered::detail::default_bucket_count,
112	const hasher& = hasher(), const key_equal& l = key_equal(),
113	const allocator_type& = allocator_type());
114
115	explicit unordered_map(size_type, const allocator_type&);
116
117	explicit unordered_map(size_type, const hasher&, const allocator_type&);
118
119	template <class InputIterator>
120	unordered_map(InputIterator, InputIterator, const allocator_type&);
121
122	template <class InputIt>
123	unordered_map(InputIt, InputIt, size_type, const allocator_type&);
124
125	template <class InputIt>
126	unordered_map(
127	InputIt, InputIt, size_type, const hasher&, const allocator_type&);
128
129	unordered_map(std::initializer_list<value_type>, const allocator_type&);
130
131	unordered_map(
132	std::initializer_list<value_type>, size_type, const allocator_type&);
133
134	unordered_map(std::initializer_list<value_type>, size_type, const hasher&,
135	const allocator_type&);
136
137	// Destructor
138
139	~unordered_map() noexcept;
140
141	// Assign
142
143	unordered_map& operator=(unordered_map const& x)
144	{
145	table_.assign(x.table_, std::true_type());
146	return *this;
147	}
148
149	unordered_map& operator=(unordered_map&& x)
150	noexcept(value_allocator_traits::is_always_equal::value&&
151	std::is_nothrow_move_assignable<H>::value&&
152	std::is_nothrow_move_assignable<P>::value)
153	{
154	table_.move_assign(x.table_, std::true_type());
155	return *this;
156	}
157
158	unordered_map& operator=(std::initializer_list<value_type>);
159
160	allocator_type get_allocator() const noexcept
161	{
162	return allocator_type(table_.node_alloc());
163	}
164
165	// // iterators
166
167	iterator begin() noexcept { return table_.begin(); }
168
169	const_iterator begin() const noexcept
170	{
171	return const_iterator(table_.begin());
172	}
173
174	iterator end() noexcept { return iterator(); }
175
176	const_iterator end() const noexcept { return const_iterator(); }
177
178	const_iterator cbegin() const noexcept
179	{
180	return const_iterator(table_.begin());
181	}
182
183	const_iterator cend() const noexcept { return const_iterator(); }
184
185	// size and capacity
186
187	BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
188	{
189	return table_.size_ == 0;
190	}
191
192	size_type size() const noexcept { return table_.size_; }
193
194	size_type max_size() const noexcept;
195
196	// emplace
197
198	template <class... Args> std::pair<iterator, bool> emplace(Args&&... args)
199	{
200	return table_.emplace_unique(
201	table::extractor::extract(std::forward<Args>(args)...),
202	std::forward<Args>(args)...);
203	}
204
205	template <class... Args>
206	iterator emplace_hint(const_iterator hint, Args&&... args)
207	{
208	return table_.emplace_hint_unique(hint,
209	table::extractor::extract(std::forward<Args>(args)...),
210	std::forward<Args>(args)...);
211	}
212
213	std::pair<iterator, bool> insert(value_type const& x)
214	{
215	return this->emplace(x);
216	}
217
218	std::pair<iterator, bool> insert(value_type&& x)
219	{
220	return this->emplace(std::move(x));
221	}
222
223	template <class P2>
224	typename boost::enable_if<std::is_constructible<value_type, P2&&>,
225	std::pair<iterator, bool> >::type
226	insert(P2&& obj)
227	{
228	return this->emplace(std::forward<P2>(obj));
229	}
230
231	iterator insert(const_iterator hint, value_type const& x)
232	{
233	return this->emplace_hint(hint, x);
234	}
235
236	iterator insert(const_iterator hint, value_type&& x)
237	{
238	return this->emplace_hint(hint, std::move(x));
239	}
240
241	template <class P2>
242	typename boost::enable_if<std::is_constructible<value_type, P2&&>,
243	iterator>::type
244	insert(const_iterator hint, P2&& obj)
245	{
246	return this->emplace_hint(hint, std::forward<P2>(obj));
247	}
248
249	template <class InputIt> void insert(InputIt, InputIt);
250
251	void insert(std::initializer_list<value_type>);
252
253	// extract
254
255	node_type extract(const_iterator position)
256	{
257	return node_type(
258	table_.extract_by_iterator_unique(position),
259	allocator_type(table_.node_alloc()));
260	}
261
262	node_type extract(const key_type& k)
263	{
264	return node_type(
265	table_.extract_by_key_impl(k),
266	allocator_type(table_.node_alloc()));
267	}
268
269	template <class Key>
270	typename boost::enable_if_c<
271	detail::transparent_non_iterable<Key, unordered_map>::value,
272	node_type>::type
273	extract(Key&& k)
274	{
275	return node_type(
276	table_.extract_by_key_impl(std::forward<Key>(k)),
277	allocator_type(table_.node_alloc()));
278	}
279
280	insert_return_type insert(node_type&& np)
281	{
282	insert_return_type result;
283	table_.move_insert_node_type_unique((node_type&)np, result);
284	return result;
285	}
286
287	iterator insert(const_iterator hint, node_type&& np)
288	{
289	return table_.move_insert_node_type_with_hint_unique(hint, np);
290	}
291
292	template <class... Args>
293	std::pair<iterator, bool> try_emplace(key_type const& k, Args&&... args)
294	{
295	return table_.try_emplace_unique(k, std::forward<Args>(args)...);
296	}
297
298	template <class... Args>
299	std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args)
300	{
301	return table_.try_emplace_unique(
302	std::move(k), std::forward<Args>(args)...);
303	}
304
305	template <class Key, class... Args>
306	typename boost::enable_if_c<
307	detail::transparent_non_iterable<Key, unordered_map>::value,
308	std::pair<iterator, bool> >::type
309	try_emplace(Key&& k, Args&&... args)
310	{
311	return table_.try_emplace_unique(
312	std::forward<Key>(k), std::forward<Args>(args)...);
313	}
314
315	template <class... Args>
316	iterator try_emplace(
317	const_iterator hint, key_type const& k, Args&&... args)
318	{
319	return table_.try_emplace_hint_unique(
320	hint, k, std::forward<Args>(args)...);
321	}
322
323	template <class... Args>
324	iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args)
325	{
326	return table_.try_emplace_hint_unique(
327	hint, std::move(k), std::forward<Args>(args)...);
328	}
329
330	template <class Key, class... Args>
331	typename boost::enable_if_c<
332	detail::transparent_non_iterable<Key, unordered_map>::value,
333	iterator>::type
334	try_emplace(const_iterator hint, Key&& k, Args&&... args)
335	{
336	return table_.try_emplace_hint_unique(
337	hint, std::forward<Key>(k), std::forward<Args>(args)...);
338	}
339
340	template <class M>
341	std::pair<iterator, bool> insert_or_assign(key_type const& k, M&& obj)
342	{
343	return table_.insert_or_assign_unique(k, std::forward<M>(obj));
344	}
345
346	template <class M>
347	std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj)
348	{
349	return table_.insert_or_assign_unique(
350	std::move(k), std::forward<M>(obj));
351	}
352
353	template <class Key, class M>
354	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
355	std::pair<iterator, bool> >::type
356	insert_or_assign(Key&& k, M&& obj)
357	{
358	return table_.insert_or_assign_unique(
359	std::forward<Key>(k), std::forward<M>(obj));
360	}
361
362	template <class M>
363	iterator insert_or_assign(const_iterator, key_type const& k, M&& obj)
364	{
365	return table_.insert_or_assign_unique(k, std::forward<M>(obj)).first;
366	}
367
368	template <class M>
369	iterator insert_or_assign(const_iterator, key_type&& k, M&& obj)
370	{
371	return table_
372	.insert_or_assign_unique(std::move(k), std::forward<M>(obj))
373	.first;
374	}
375
376	template <class Key, class M>
377	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
378	iterator>::type
379	insert_or_assign(const_iterator, Key&& k, M&& obj)
380	{
381	return table_
382	.insert_or_assign_unique(std::forward<Key>(k), std::forward<M>(obj))
383	.first;
384	}
385
386	iterator erase(iterator);
387	iterator erase(const_iterator);
388	size_type erase(const key_type&);
389	iterator erase(const_iterator, const_iterator);
390
391	template <class Key>
392	typename boost::enable_if_c<
393	detail::transparent_non_iterable<Key, unordered_map>::value,
394	size_type>::type
395	erase(Key&& k)
396	{
397	return table_.erase_key_unique_impl(std::forward<Key>(k));
398	}
399
400	BOOST_UNORDERED_DEPRECATED("Use erase instead")
401	void quick_erase(const_iterator it) { erase(it); }
402	BOOST_UNORDERED_DEPRECATED("Use erase instead")
403	void erase_return_void(const_iterator it) { erase(it); }
404
405	void swap(unordered_map&)
406	noexcept(value_allocator_traits::is_always_equal::value&&
407	boost::unordered::detail::is_nothrow_swappable<H>::value&&
408	boost::unordered::detail::is_nothrow_swappable<P>::value);
409	void clear() noexcept { table_.clear_impl(); }
410
411	template <typename H2, typename P2>
412	void merge(boost::unordered_map<K, T, H2, P2, A>& source);
413
414	template <typename H2, typename P2>
415	void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
416
417	template <typename H2, typename P2>
418	void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
419
420	template <typename H2, typename P2>
421	void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
422
423	// observers
424
425	hasher hash_function() const;
426	key_equal key_eq() const;
427
428	// lookup
429
430	iterator find(const key_type&);
431	const_iterator find(const key_type&) const;
432
433	template <class Key>
434	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
435	iterator>::type
436	find(const Key& key)
437	{
438	return table_.find(key);
439	}
440
441	template <class Key>
442	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
443	const_iterator>::type
444	find(const Key& key) const
445	{
446	return const_iterator(table_.find(key));
447	}
448
449	template <class CompatibleKey, class CompatibleHash,
450	class CompatiblePredicate>
451	iterator find(CompatibleKey const&, CompatibleHash const&,
452	CompatiblePredicate const&);
453
454	template <class CompatibleKey, class CompatibleHash,
455	class CompatiblePredicate>
456	const_iterator find(CompatibleKey const&, CompatibleHash const&,
457	CompatiblePredicate const&) const;
458
459	bool contains(const key_type& k) const
460	{
461	return table_.find(k) != this->end();
462	}
463
464	template <class Key>
465	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
466	bool>::type
467	contains(const Key& k) const
468	{
469	return table_.find(k) != this->end();
470	}
471
472	size_type count(const key_type&) const;
473
474	template <class Key>
475	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
476	size_type>::type
477	count(const Key& k) const
478	{
479	return (table_.find(k) != this->end() ? 1 : 0);
480	}
481
482	std::pair<iterator, iterator> equal_range(const key_type&);
483	std::pair<const_iterator, const_iterator> equal_range(
484	const key_type&) const;
485
486	template <class Key>
487	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
488	std::pair<iterator, iterator> >::type
489	equal_range(const Key& key)
490	{
491	iterator first = table_.find(key);
492	iterator last = first;
493	if (last != this->end()) {
494	++last;
495	}
496
497	return std::make_pair(first, last);
498	}
499
500	template <class Key>
501	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
502	std::pair<const_iterator, const_iterator> >::type
503	equal_range(const Key& key) const
504	{
505	iterator first = table_.find(key);
506	iterator last = first;
507	if (last != this->end()) {
508	++last;
509	}
510
511	return std::make_pair(first, last);
512	}
513
514	mapped_type& operator[](const key_type&);
515	mapped_type& operator[](key_type&&);
516
517	template <class Key>
518	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
519	mapped_type&>::type
520	operator[](Key&& k);
521
522	mapped_type& at(const key_type&);
523	mapped_type const& at(const key_type&) const;
524
525	template <class Key>
526	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
527	mapped_type&>::type
528	at(Key&& k);
529
530	template <class Key>
531	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
532	mapped_type const&>::type
533	at(Key&& k) const;
534
535	// bucket interface
536
537	size_type bucket_count() const noexcept { return table_.bucket_count(); }
538
539	size_type max_bucket_count() const noexcept
540	{
541	return table_.max_bucket_count();
542	}
543
544	size_type bucket_size(size_type) const;
545
546	size_type bucket(const key_type& k) const
547	{
548	return table_.hash_to_bucket(table_.hash(k));
549	}
550
551	template <class Key>
552	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
553	size_type>::type
554	bucket(Key&& k) const
555	{
556	return table_.hash_to_bucket(table_.hash(std::forward<Key>(k)));
557	}
558
559	local_iterator begin(size_type n) { return table_.begin(n); }
560
561	const_local_iterator begin(size_type n) const
562	{
563	return const_local_iterator(table_.begin(n));
564	}
565
566	local_iterator end(size_type) { return local_iterator(); }
567	const_local_iterator end(size_type) const
568	{
569	return const_local_iterator();
570	}
571
572	const_local_iterator cbegin(size_type n) const
573	{
574	return const_local_iterator(table_.begin(n));
575	}
576
577	const_local_iterator cend(size_type) const
578	{
579	return const_local_iterator();
580	}
581
582	// hash policy
583
584	float load_factor() const noexcept;
585	float max_load_factor() const noexcept { return table_.mlf_; }
586	void max_load_factor(float) noexcept;
587	void rehash(size_type);
588	void reserve(size_type);
589
590	#if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
591	friend bool operator==
592	<K, T, H, P, A>(unordered_map const&, unordered_map const&);
593	friend bool operator!=
594	<K, T, H, P, A>(unordered_map const&, unordered_map const&);
595	#endif
596	}; // class template unordered_map
597
598	template <class Archive, class K, class T, class H, class P, class A>
599	void serialize(
600	Archive& ar, unordered_map<K, T, H, P, A>& m, unsigned int version)
601	{
602	detail::serialize_fca_container(ar, m, version);
603	}
604
605	#if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
606
607	template <class InputIterator,
608	class Hash =
609	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
610	class Pred =
611	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
612	class Allocator = std::allocator<
613	boost::unordered::detail::iter_to_alloc_t<InputIterator> >,
614	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
615	class = std::enable_if_t<detail::is_hash_v<Hash> >,
616	class = std::enable_if_t<detail::is_pred_v<Pred> >,
617	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
618	unordered_map(InputIterator, InputIterator,
619	std::size_t = boost::unordered::detail::default_bucket_count,
620	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
621	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
622	boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred,
623	Allocator>;
624
625	template <class Key, class T,
626	class Hash = boost::hash<std::remove_const_t<Key> >,
627	class Pred = std::equal_to<std::remove_const_t<Key> >,
628	class Allocator = std::allocator<std::pair<const Key, T> >,
629	class = std::enable_if_t<detail::is_hash_v<Hash> >,
630	class = std::enable_if_t<detail::is_pred_v<Pred> >,
631	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
632	unordered_map(std::initializer_list<std::pair<Key, T> >,
633	std::size_t = boost::unordered::detail::default_bucket_count,
634	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
635	-> unordered_map<std::remove_const_t<Key>, T, Hash, Pred, Allocator>;
636
637	template <class InputIterator, class Allocator,
638	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
639	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
640	unordered_map(InputIterator, InputIterator, std::size_t, Allocator)
641	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
642	boost::unordered::detail::iter_val_t<InputIterator>,
643	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
644	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
645	Allocator>;
646
647	template <class InputIterator, class Allocator,
648	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
649	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
650	unordered_map(InputIterator, InputIterator, Allocator)
651	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
652	boost::unordered::detail::iter_val_t<InputIterator>,
653	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
654	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
655	Allocator>;
656
657	template <class InputIterator, class Hash, class Allocator,
658	class = std::enable_if_t<detail::is_hash_v<Hash> >,
659	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
660	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
661	unordered_map(InputIterator, InputIterator, std::size_t, Hash, Allocator)
662	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
663	boost::unordered::detail::iter_val_t<InputIterator>, Hash,
664	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
665	Allocator>;
666
667	template <class Key, class T, class Allocator,
668	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
669	unordered_map(std::initializer_list<std::pair<Key, T> >, std::size_t,
670	Allocator) -> unordered_map<std::remove_const_t<Key>, T,
671	boost::hash<std::remove_const_t<Key> >,
672	std::equal_to<std::remove_const_t<Key> >, Allocator>;
673
674	template <class Key, class T, class Allocator,
675	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
676	unordered_map(std::initializer_list<std::pair<Key, T> >, Allocator)
677	-> unordered_map<std::remove_const_t<Key>, T,
678	boost::hash<std::remove_const_t<Key> >,
679	std::equal_to<std::remove_const_t<Key> >, Allocator>;
680
681	template <class Key, class T, class Hash, class Allocator,
682	class = std::enable_if_t<detail::is_hash_v<Hash> >,
683	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
684	unordered_map(std::initializer_list<std::pair<Key, T> >, std::size_t, Hash,
685	Allocator) -> unordered_map<std::remove_const_t<Key>, T, Hash,
686	std::equal_to<std::remove_const_t<Key> >, Allocator>;
687
688	#endif
689
690	template <class K, class T, class H, class P, class A>
691	class unordered_multimap
692	{
693	template <typename, typename, typename, typename, typename>
694	friend class unordered_map;
695
696	public:
697	typedef K key_type;
698	typedef T mapped_type;
699	typedef std::pair<const K, T> value_type;
700	typedef typename boost::unordered::detail::type_identity<H>::type hasher;
701	typedef
702	typename boost::unordered::detail::type_identity<P>::type key_equal;
703	typedef typename boost::unordered::detail::type_identity<A>::type
704	allocator_type;
705
706	private:
707	typedef boost::unordered::detail::map<A, K, T, H, P> types;
708	typedef typename types::value_allocator_traits value_allocator_traits;
709	typedef typename types::table table;
710
711	public:
712	typedef typename value_allocator_traits::pointer pointer;
713	typedef typename value_allocator_traits::const_pointer const_pointer;
714
715	typedef value_type& reference;
716	typedef value_type const& const_reference;
717
718	typedef std::size_t size_type;
719	typedef std::ptrdiff_t difference_type;
720
721	typedef typename table::iterator iterator;
722	typedef typename table::c_iterator const_iterator;
723	typedef typename table::l_iterator local_iterator;
724	typedef typename table::cl_iterator const_local_iterator;
725	typedef typename types::node_type node_type;
726
727	private:
728	table table_;
729
730	public:
731	// constructors
732
733	unordered_multimap();
734
735	explicit unordered_multimap(size_type, const hasher& = hasher(),
736	const key_equal& = key_equal(),
737	const allocator_type& = allocator_type());
738
739	template <class InputIt>
740	unordered_multimap(InputIt, InputIt,
741	size_type = boost::unordered::detail::default_bucket_count,
742	const hasher& = hasher(), const key_equal& = key_equal(),
743	const allocator_type& = allocator_type());
744
745	unordered_multimap(unordered_multimap const&);
746
747	unordered_multimap(unordered_multimap&& other)
748	noexcept(table::nothrow_move_constructible)
749	: table_(other.table_, boost::unordered::detail::move_tag())
750	{
751	// The move is done in table_
752	}
753
754	explicit unordered_multimap(allocator_type const&);
755
756	unordered_multimap(unordered_multimap const&, allocator_type const&);
757
758	unordered_multimap(unordered_multimap&&, allocator_type const&);
759
760	unordered_multimap(std::initializer_list<value_type>,
761	size_type = boost::unordered::detail::default_bucket_count,
762	const hasher& = hasher(), const key_equal& l = key_equal(),
763	const allocator_type& = allocator_type());
764
765	explicit unordered_multimap(size_type, const allocator_type&);
766
767	explicit unordered_multimap(
768	size_type, const hasher&, const allocator_type&);
769
770	template <class InputIterator>
771	unordered_multimap(InputIterator, InputIterator, const allocator_type&);
772
773	template <class InputIt>
774	unordered_multimap(InputIt, InputIt, size_type, const allocator_type&);
775
776	template <class InputIt>
777	unordered_multimap(
778	InputIt, InputIt, size_type, const hasher&, const allocator_type&);
779
780	unordered_multimap(
781	std::initializer_list<value_type>, const allocator_type&);
782
783	unordered_multimap(
784	std::initializer_list<value_type>, size_type, const allocator_type&);
785
786	unordered_multimap(std::initializer_list<value_type>, size_type,
787	const hasher&, const allocator_type&);
788
789	// Destructor
790
791	~unordered_multimap() noexcept;
792
793	// Assign
794
795	unordered_multimap& operator=(unordered_multimap const& x)
796	{
797	table_.assign(x.table_, std::false_type());
798	return *this;
799	}
800
801	unordered_multimap& operator=(unordered_multimap&& x)
802	noexcept(value_allocator_traits::is_always_equal::value&&
803	std::is_nothrow_move_assignable<H>::value&&
804	std::is_nothrow_move_assignable<P>::value)
805	{
806	table_.move_assign(x.table_, std::false_type());
807	return *this;
808	}
809
810	unordered_multimap& operator=(std::initializer_list<value_type>);
811
812	allocator_type get_allocator() const noexcept
813	{
814	return allocator_type(table_.node_alloc());
815	}
816
817	// iterators
818
819	iterator begin() noexcept { return iterator(table_.begin()); }
820
821	const_iterator begin() const noexcept
822	{
823	return const_iterator(table_.begin());
824	}
825
826	iterator end() noexcept { return iterator(); }
827
828	const_iterator end() const noexcept { return const_iterator(); }
829
830	const_iterator cbegin() const noexcept
831	{
832	return const_iterator(table_.begin());
833	}
834
835	const_iterator cend() const noexcept { return const_iterator(); }
836
837	// size and capacity
838
839	BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
840	{
841	return table_.size_ == 0;
842	}
843
844	size_type size() const noexcept { return table_.size_; }
845
846	size_type max_size() const noexcept;
847
848	// emplace
849
850	template <class... Args> iterator emplace(Args&&... args)
851	{
852	return iterator(table_.emplace_equiv(
853	boost::unordered::detail::func::construct_node_from_args(
854	table_.node_alloc(), std::forward<Args>(args)...)));
855	}
856
857	template <class... Args>
858	iterator emplace_hint(const_iterator hint, Args&&... args)
859	{
860	return iterator(table_.emplace_hint_equiv(
861	hint, boost::unordered::detail::func::construct_node_from_args(
862	table_.node_alloc(), std::forward<Args>(args)...)));
863	}
864
865	iterator insert(value_type const& x) { return this->emplace(x); }
866
867	iterator insert(value_type&& x) { return this->emplace(std::move(x)); }
868
869	template <class P2>
870	typename boost::enable_if<std::is_constructible<value_type, P2&&>,
871	iterator>::type
872	insert(P2&& obj)
873	{
874	return this->emplace(std::forward<P2>(obj));
875	}
876
877	iterator insert(const_iterator hint, value_type const& x)
878	{
879	return this->emplace_hint(hint, x);
880	}
881
882	iterator insert(const_iterator hint, value_type&& x)
883	{
884	return this->emplace_hint(hint, std::move(x));
885	}
886
887	template <class P2>
888	typename boost::enable_if<std::is_constructible<value_type, P2&&>,
889	iterator>::type
890	insert(const_iterator hint, P2&& obj)
891	{
892	return this->emplace_hint(hint, std::forward<P2>(obj));
893	}
894
895	template <class InputIt> void insert(InputIt, InputIt);
896
897	void insert(std::initializer_list<value_type>);
898
899	// extract
900
901	node_type extract(const_iterator position)
902	{
903	return node_type(
904	table_.extract_by_iterator_equiv(position), table_.node_alloc());
905	}
906
907	node_type extract(const key_type& k)
908	{
909	return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
910	}
911
912	template <class Key>
913	typename boost::enable_if_c<
914	detail::transparent_non_iterable<Key, unordered_multimap>::value,
915	node_type>::type
916	extract(const Key& k)
917	{
918	return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
919	}
920
921	iterator insert(node_type&& np)
922	{
923	return table_.move_insert_node_type_equiv(np);
924	}
925
926	iterator insert(const_iterator hint, node_type&& np)
927	{
928	return table_.move_insert_node_type_with_hint_equiv(hint, np);
929	}
930
931	iterator erase(iterator);
932	iterator erase(const_iterator);
933	size_type erase(const key_type&);
934	iterator erase(const_iterator, const_iterator);
935
936	template <class Key>
937	typename boost::enable_if_c<
938	detail::transparent_non_iterable<Key, unordered_multimap>::value,
939	size_type>::type
940	erase(Key&& k)
941	{
942	return table_.erase_key_equiv_impl(std::forward<Key>(k));
943	}
944
945	BOOST_UNORDERED_DEPRECATED("Use erase instead")
946	void quick_erase(const_iterator it) { erase(it); }
947	BOOST_UNORDERED_DEPRECATED("Use erase instead")
948	void erase_return_void(const_iterator it) { erase(it); }
949
950	void swap(unordered_multimap&)
951	noexcept(value_allocator_traits::is_always_equal::value&&
952	boost::unordered::detail::is_nothrow_swappable<H>::value&&
953	boost::unordered::detail::is_nothrow_swappable<P>::value);
954	void clear() noexcept { table_.clear_impl(); }
955
956	template <typename H2, typename P2>
957	void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
958
959	template <typename H2, typename P2>
960	void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
961
962	template <typename H2, typename P2>
963	void merge(boost::unordered_map<K, T, H2, P2, A>& source);
964
965	template <typename H2, typename P2>
966	void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
967
968	// observers
969
970	hasher hash_function() const;
971	key_equal key_eq() const;
972
973	// lookup
974
975	iterator find(const key_type&);
976	const_iterator find(const key_type&) const;
977
978	template <class Key>
979	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
980	iterator>::type
981	find(const Key& key)
982	{
983	return table_.find(key);
984	}
985
986	template <class Key>
987	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
988	const_iterator>::type
989	find(const Key& key) const
990	{
991	return const_iterator(table_.find(key));
992	}
993
994	template <class CompatibleKey, class CompatibleHash,
995	class CompatiblePredicate>
996	iterator find(CompatibleKey const&, CompatibleHash const&,
997	CompatiblePredicate const&);
998
999	template <class CompatibleKey, class CompatibleHash,
1000	class CompatiblePredicate>
1001	const_iterator find(CompatibleKey const&, CompatibleHash const&,
1002	CompatiblePredicate const&) const;
1003
1004	bool contains(key_type const& k) const
1005	{
1006	return table_.find(k) != this->end();
1007	}
1008
1009	template <class Key>
1010	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1011	bool>::type
1012	contains(const Key& k) const
1013	{
1014	return table_.find(k) != this->end();
1015	}
1016
1017	size_type count(const key_type&) const;
1018
1019	template <class Key>
1020	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1021	size_type>::type
1022	count(const Key& k) const
1023	{
1024	return table_.group_count(k);
1025	}
1026
1027	std::pair<iterator, iterator> equal_range(const key_type&);
1028	std::pair<const_iterator, const_iterator> equal_range(
1029	const key_type&) const;
1030
1031	template <class Key>
1032	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1033	std::pair<iterator, iterator> >::type
1034	equal_range(const Key& key)
1035	{
1036	iterator p = table_.find(key);
1037	return std::make_pair(p, table_.next_group(key, p));
1038	}
1039
1040	template <class Key>
1041	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1042	std::pair<const_iterator, const_iterator> >::type
1043	equal_range(const Key& key) const
1044	{
1045	iterator p = table_.find(key);
1046	return std::make_pair(
1047	const_iterator(p), const_iterator(table_.next_group(key, p)));
1048	}
1049
1050	// bucket interface
1051
1052	size_type bucket_count() const noexcept { return table_.bucket_count(); }
1053
1054	size_type max_bucket_count() const noexcept
1055	{
1056	return table_.max_bucket_count();
1057	}
1058
1059	size_type bucket_size(size_type) const;
1060
1061	size_type bucket(const key_type& k) const
1062	{
1063	return table_.hash_to_bucket(table_.hash(k));
1064	}
1065
1066	template <class Key>
1067	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1068	size_type>::type
1069	bucket(Key&& k) const
1070	{
1071	return table_.hash_to_bucket(table_.hash(std::forward<Key>(k)));
1072	}
1073
1074	local_iterator begin(size_type n)
1075	{
1076	return local_iterator(table_.begin(n));
1077	}
1078
1079	const_local_iterator begin(size_type n) const
1080	{
1081	return const_local_iterator(table_.begin(n));
1082	}
1083
1084	local_iterator end(size_type) { return local_iterator(); }
1085
1086	const_local_iterator end(size_type) const
1087	{
1088	return const_local_iterator();
1089	}
1090
1091	const_local_iterator cbegin(size_type n) const
1092	{
1093	return const_local_iterator(table_.begin(n));
1094	}
1095
1096	const_local_iterator cend(size_type) const
1097	{
1098	return const_local_iterator();
1099	}
1100
1101	// hash policy
1102
1103	float load_factor() const noexcept;
1104	float max_load_factor() const noexcept { return table_.mlf_; }
1105	void max_load_factor(float) noexcept;
1106	void rehash(size_type);
1107	void reserve(size_type);
1108
1109	#if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
1110	friend bool operator==
1111	<K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1112	friend bool operator!=
1113	<K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1114	#endif
1115	}; // class template unordered_multimap
1116
1117	template <class Archive, class K, class T, class H, class P, class A>
1118	void serialize(
1119	Archive& ar, unordered_multimap<K, T, H, P, A>& m, unsigned int version)
1120	{
1121	detail::serialize_fca_container(ar, m, version);
1122	}
1123
1124	#if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
1125
1126	template <class InputIterator,
1127	class Hash =
1128	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1129	class Pred =
1130	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1131	class Allocator = std::allocator<
1132	boost::unordered::detail::iter_to_alloc_t<InputIterator> >,
1133	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1134	class = std::enable_if_t<detail::is_hash_v<Hash> >,
1135	class = std::enable_if_t<detail::is_pred_v<Pred> >,
1136	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1137	unordered_multimap(InputIterator, InputIterator,
1138	std::size_t = boost::unordered::detail::default_bucket_count,
1139	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1140	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1141	boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred,
1142	Allocator>;
1143
1144	template <class Key, class T,
1145	class Hash = boost::hash<std::remove_const_t<Key> >,
1146	class Pred = std::equal_to<std::remove_const_t<Key> >,
1147	class Allocator = std::allocator<std::pair<const Key, T> >,
1148	class = std::enable_if_t<detail::is_hash_v<Hash> >,
1149	class = std::enable_if_t<detail::is_pred_v<Pred> >,
1150	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1151	unordered_multimap(std::initializer_list<std::pair<Key, T> >,
1152	std::size_t = boost::unordered::detail::default_bucket_count,
1153	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1154	-> unordered_multimap<std::remove_const_t<Key>, T, Hash, Pred, Allocator>;
1155
1156	template <class InputIterator, class Allocator,
1157	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1158	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1159	unordered_multimap(InputIterator, InputIterator, std::size_t, Allocator)
1160	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1161	boost::unordered::detail::iter_val_t<InputIterator>,
1162	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1163	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1164	Allocator>;
1165
1166	template <class InputIterator, class Allocator,
1167	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1168	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1169	unordered_multimap(InputIterator, InputIterator, Allocator)
1170	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1171	boost::unordered::detail::iter_val_t<InputIterator>,
1172	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1173	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1174	Allocator>;
1175
1176	template <class InputIterator, class Hash, class Allocator,
1177	class = std::enable_if_t<detail::is_hash_v<Hash> >,
1178	class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1179	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1180	unordered_multimap(
1181	InputIterator, InputIterator, std::size_t, Hash, Allocator)
1182	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1183	boost::unordered::detail::iter_val_t<InputIterator>, Hash,
1184	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1185	Allocator>;
1186
1187	template <class Key, class T, class Allocator,
1188	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1189	unordered_multimap(std::initializer_list<std::pair<Key, T> >, std::size_t,
1190	Allocator) -> unordered_multimap<std::remove_const_t<Key>, T,
1191	boost::hash<std::remove_const_t<Key> >,
1192	std::equal_to<std::remove_const_t<Key> >, Allocator>;
1193
1194	template <class Key, class T, class Allocator,
1195	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1196	unordered_multimap(std::initializer_list<std::pair<Key, T> >, Allocator)
1197	-> unordered_multimap<std::remove_const_t<Key>, T,
1198	boost::hash<std::remove_const_t<Key> >,
1199	std::equal_to<std::remove_const_t<Key> >, Allocator>;
1200
1201	template <class Key, class T, class Hash, class Allocator,
1202	class = std::enable_if_t<detail::is_hash_v<Hash> >,
1203	class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1204	unordered_multimap(std::initializer_list<std::pair<Key, T> >, std::size_t,
1205	Hash, Allocator) -> unordered_multimap<std::remove_const_t<Key>, T, Hash,
1206	std::equal_to<std::remove_const_t<Key> >, Allocator>;
1207
1208	#endif
1209
1210	////////////////////////////////////////////////////////////////////////////
1211
1212	template <class K, class T, class H, class P, class A>
1213	unordered_map<K, T, H, P, A>::unordered_map()
1214	{
1215	}
1216
1217	template <class K, class T, class H, class P, class A>
1218	unordered_map<K, T, H, P, A>::unordered_map(size_type n, const hasher& hf,
1219	const key_equal& eql, const allocator_type& a)
1220	: table_(n, hf, eql, a)
1221	{
1222	}
1223
1224	template <class K, class T, class H, class P, class A>
1225	template <class InputIt>
1226	unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1227	size_type n, const hasher& hf, const key_equal& eql,
1228	const allocator_type& a)
1229	: table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1230	{
1231	this->insert(f, l);
1232	}
1233
1234	template <class K, class T, class H, class P, class A>
1235	unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
1236	: table_(other.table_,
1237	unordered_map::value_allocator_traits::
1238	select_on_container_copy_construction(other.get_allocator()))
1239	{
1240	if (other.size()) {
1241	table_.copy_buckets(other.table_, std::true_type());
1242	}
1243	}
1244
1245	template <class K, class T, class H, class P, class A>
1246	unordered_map<K, T, H, P, A>::unordered_map(allocator_type const& a)
1247	: table_(boost::unordered::detail::default_bucket_count, hasher(),
1248	key_equal(), a)
1249	{
1250	}
1251
1252	template <class K, class T, class H, class P, class A>
1253	unordered_map<K, T, H, P, A>::unordered_map(
1254	unordered_map const& other, allocator_type const& a)
1255	: table_(other.table_, a)
1256	{
1257	if (other.table_.size_) {
1258	table_.copy_buckets(other.table_, std::true_type());
1259	}
1260	}
1261
1262	template <class K, class T, class H, class P, class A>
1263	unordered_map<K, T, H, P, A>::unordered_map(
1264	unordered_map&& other, allocator_type const& a)
1265	: table_(other.table_, a, boost::unordered::detail::move_tag())
1266	{
1267	table_.move_construct_buckets(other.table_);
1268	}
1269
1270	template <class K, class T, class H, class P, class A>
1271	unordered_map<K, T, H, P, A>::unordered_map(
1272	std::initializer_list<value_type> list, size_type n, const hasher& hf,
1273	const key_equal& eql, const allocator_type& a)
1274	: table_(
1275	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1276	hf, eql, a)
1277	{
1278	this->insert(list.begin(), list.end());
1279	}
1280
1281	template <class K, class T, class H, class P, class A>
1282	unordered_map<K, T, H, P, A>::unordered_map(
1283	size_type n, const allocator_type& a)
1284	: table_(n, hasher(), key_equal(), a)
1285	{
1286	}
1287
1288	template <class K, class T, class H, class P, class A>
1289	unordered_map<K, T, H, P, A>::unordered_map(
1290	size_type n, const hasher& hf, const allocator_type& a)
1291	: table_(n, hf, key_equal(), a)
1292	{
1293	}
1294
1295	template <class K, class T, class H, class P, class A>
1296	template <class InputIterator>
1297	unordered_map<K, T, H, P, A>::unordered_map(
1298	InputIterator f, InputIterator l, const allocator_type& a)
1299	: table_(boost::unordered::detail::initial_size(
1300	f, l, detail::default_bucket_count),
1301	hasher(), key_equal(), a)
1302	{
1303	this->insert(f, l);
1304	}
1305
1306	template <class K, class T, class H, class P, class A>
1307	template <class InputIt>
1308	unordered_map<K, T, H, P, A>::unordered_map(
1309	InputIt f, InputIt l, size_type n, const allocator_type& a)
1310	: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1311	key_equal(), a)
1312	{
1313	this->insert(f, l);
1314	}
1315
1316	template <class K, class T, class H, class P, class A>
1317	template <class InputIt>
1318	unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1319	size_type n, const hasher& hf, const allocator_type& a)
1320	: table_(
1321	boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1322	{
1323	this->insert(f, l);
1324	}
1325
1326	template <class K, class T, class H, class P, class A>
1327	unordered_map<K, T, H, P, A>::unordered_map(
1328	std::initializer_list<value_type> list, const allocator_type& a)
1329	: table_(boost::unordered::detail::initial_size(
1330	list.begin(), list.end(), detail::default_bucket_count),
1331	hasher(), key_equal(), a)
1332	{
1333	this->insert(list.begin(), list.end());
1334	}
1335
1336	template <class K, class T, class H, class P, class A>
1337	unordered_map<K, T, H, P, A>::unordered_map(
1338	std::initializer_list<value_type> list, size_type n,
1339	const allocator_type& a)
1340	: table_(
1341	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1342	hasher(), key_equal(), a)
1343	{
1344	this->insert(list.begin(), list.end());
1345	}
1346
1347	template <class K, class T, class H, class P, class A>
1348	unordered_map<K, T, H, P, A>::unordered_map(
1349	std::initializer_list<value_type> list, size_type n, const hasher& hf,
1350	const allocator_type& a)
1351	: table_(
1352	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1353	hf, key_equal(), a)
1354	{
1355	this->insert(list.begin(), list.end());
1356	}
1357
1358	template <class K, class T, class H, class P, class A>
1359	unordered_map<K, T, H, P, A>::~unordered_map() noexcept
1360	{
1361	}
1362
1363	template <class K, class T, class H, class P, class A>
1364	unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=(
1365	std::initializer_list<value_type> list)
1366	{
1367	this->clear();
1368	this->insert(list.begin(), list.end());
1369	return *this;
1370	}
1371
1372	// size and capacity
1373
1374	template <class K, class T, class H, class P, class A>
1375	std::size_t unordered_map<K, T, H, P, A>::max_size() const noexcept
1376	{
1377	using namespace std;
1378
1379	// size <= mlf_ * count
1380	return boost::unordered::detail::double_to_size(
1381	f: ceil(x: static_cast<double>(table_.mlf_) *
1382	static_cast<double>(table_.max_bucket_count()))) -
1383	1;
1384	}
1385
1386	// modifiers
1387
1388	template <class K, class T, class H, class P, class A>
1389	template <class InputIt>
1390	void unordered_map<K, T, H, P, A>::insert(InputIt first, InputIt last)
1391	{
1392	if (first != last) {
1393	table_.insert_range_unique(
1394	table::extractor::extract(*first), first, last);
1395	}
1396	}
1397
1398	template <class K, class T, class H, class P, class A>
1399	void unordered_map<K, T, H, P, A>::insert(
1400	std::initializer_list<value_type> list)
1401	{
1402	this->insert(list.begin(), list.end());
1403	}
1404
1405	template <class K, class T, class H, class P, class A>
1406	typename unordered_map<K, T, H, P, A>::iterator
1407	unordered_map<K, T, H, P, A>::erase(iterator position)
1408	{
1409	return table_.erase_node(position);
1410	}
1411
1412	template <class K, class T, class H, class P, class A>
1413	typename unordered_map<K, T, H, P, A>::iterator
1414	unordered_map<K, T, H, P, A>::erase(const_iterator position)
1415	{
1416	return table_.erase_node(position);
1417	}
1418
1419	template <class K, class T, class H, class P, class A>
1420	typename unordered_map<K, T, H, P, A>::size_type
1421	unordered_map<K, T, H, P, A>::erase(const key_type& k)
1422	{
1423	return table_.erase_key_unique_impl(k);
1424	}
1425
1426	template <class K, class T, class H, class P, class A>
1427	typename unordered_map<K, T, H, P, A>::iterator
1428	unordered_map<K, T, H, P, A>::erase(
1429	const_iterator first, const_iterator last)
1430	{
1431	return table_.erase_nodes_range(first, last);
1432	}
1433
1434	template <class K, class T, class H, class P, class A>
1435	void unordered_map<K, T, H, P, A>::swap(unordered_map& other)
1436	noexcept(value_allocator_traits::is_always_equal::value&&
1437	boost::unordered::detail::is_nothrow_swappable<H>::value&&
1438	boost::unordered::detail::is_nothrow_swappable<P>::value)
1439	{
1440	table_.swap(other.table_);
1441	}
1442
1443	template <class K, class T, class H, class P, class A>
1444	template <typename H2, typename P2>
1445	void unordered_map<K, T, H, P, A>::merge(
1446	boost::unordered_map<K, T, H2, P2, A>& source)
1447	{
1448	table_.merge_unique(source.table_);
1449	}
1450
1451	template <class K, class T, class H, class P, class A>
1452	template <typename H2, typename P2>
1453	void unordered_map<K, T, H, P, A>::merge(
1454	boost::unordered_map<K, T, H2, P2, A>&& source)
1455	{
1456	table_.merge_unique(source.table_);
1457	}
1458
1459	template <class K, class T, class H, class P, class A>
1460	template <typename H2, typename P2>
1461	void unordered_map<K, T, H, P, A>::merge(
1462	boost::unordered_multimap<K, T, H2, P2, A>& source)
1463	{
1464	table_.merge_unique(source.table_);
1465	}
1466
1467	template <class K, class T, class H, class P, class A>
1468	template <typename H2, typename P2>
1469	void unordered_map<K, T, H, P, A>::merge(
1470	boost::unordered_multimap<K, T, H2, P2, A>&& source)
1471	{
1472	table_.merge_unique(source.table_);
1473	}
1474
1475	// observers
1476
1477	template <class K, class T, class H, class P, class A>
1478	typename unordered_map<K, T, H, P, A>::hasher
1479	unordered_map<K, T, H, P, A>::hash_function() const
1480	{
1481	return table_.hash_function();
1482	}
1483
1484	template <class K, class T, class H, class P, class A>
1485	typename unordered_map<K, T, H, P, A>::key_equal
1486	unordered_map<K, T, H, P, A>::key_eq() const
1487	{
1488	return table_.key_eq();
1489	}
1490
1491	// lookup
1492
1493	template <class K, class T, class H, class P, class A>
1494	typename unordered_map<K, T, H, P, A>::iterator
1495	unordered_map<K, T, H, P, A>::find(const key_type& k)
1496	{
1497	return iterator(table_.find(k));
1498	}
1499
1500	template <class K, class T, class H, class P, class A>
1501	typename unordered_map<K, T, H, P, A>::const_iterator
1502	unordered_map<K, T, H, P, A>::find(const key_type& k) const
1503	{
1504	return const_iterator(table_.find(k));
1505	}
1506
1507	template <class K, class T, class H, class P, class A>
1508	template <class CompatibleKey, class CompatibleHash,
1509	class CompatiblePredicate>
1510	typename unordered_map<K, T, H, P, A>::iterator
1511	unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
1512	CompatibleHash const& hash, CompatiblePredicate const& eq)
1513	{
1514	return table_.transparent_find(k, hash, eq);
1515	}
1516
1517	template <class K, class T, class H, class P, class A>
1518	template <class CompatibleKey, class CompatibleHash,
1519	class CompatiblePredicate>
1520	typename unordered_map<K, T, H, P, A>::const_iterator
1521	unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
1522	CompatibleHash const& hash, CompatiblePredicate const& eq) const
1523	{
1524	return table_.transparent_find(k, hash, eq);
1525	}
1526
1527	template <class K, class T, class H, class P, class A>
1528	typename unordered_map<K, T, H, P, A>::size_type
1529	unordered_map<K, T, H, P, A>::count(const key_type& k) const
1530	{
1531	return table_.find_node(k) ? 1 : 0;
1532	}
1533
1534	template <class K, class T, class H, class P, class A>
1535	std::pair<typename unordered_map<K, T, H, P, A>::iterator,
1536	typename unordered_map<K, T, H, P, A>::iterator>
1537	unordered_map<K, T, H, P, A>::equal_range(const key_type& k)
1538	{
1539	iterator first = table_.find(k);
1540	iterator second = first;
1541	if (second != this->end()) {
1542	++second;
1543	}
1544	return std::make_pair(first, second);
1545	}
1546
1547	template <class K, class T, class H, class P, class A>
1548	std::pair<typename unordered_map<K, T, H, P, A>::const_iterator,
1549	typename unordered_map<K, T, H, P, A>::const_iterator>
1550	unordered_map<K, T, H, P, A>::equal_range(const key_type& k) const
1551	{
1552	iterator first = table_.find(k);
1553	iterator second = first;
1554	if (second != this->end()) {
1555	++second;
1556	}
1557	return std::make_pair(const_iterator(first), const_iterator(second));
1558	}
1559
1560	template <class K, class T, class H, class P, class A>
1561	typename unordered_map<K, T, H, P, A>::mapped_type&
1562	unordered_map<K, T, H, P, A>::operator[](const key_type& k)
1563	{
1564	return table_.try_emplace_unique(k).first->second;
1565	}
1566
1567	template <class K, class T, class H, class P, class A>
1568	typename unordered_map<K, T, H, P, A>::mapped_type&
1569	unordered_map<K, T, H, P, A>::operator[](key_type&& k)
1570	{
1571	return table_.try_emplace_unique(std::move(k)).first->second;
1572	}
1573
1574	template <class K, class T, class H, class P, class A>
1575	template <class Key>
1576	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1577	typename unordered_map<K, T, H, P, A>::mapped_type&>::type
1578	unordered_map<K, T, H, P, A>::operator[](Key&& k)
1579	{
1580	return table_.try_emplace_unique(std::forward<Key>(k)).first->second;
1581	}
1582
1583	template <class K, class T, class H, class P, class A>
1584	typename unordered_map<K, T, H, P, A>::mapped_type&
1585	unordered_map<K, T, H, P, A>::at(const key_type& k)
1586	{
1587	typedef typename table::node_pointer node_pointer;
1588
1589	if (table_.size_) {
1590	node_pointer p = table_.find_node(k);
1591	if (p)
1592	return p->value().second;
1593	}
1594
1595	boost::unordered::detail::throw_out_of_range(
1596	message: "Unable to find key in unordered_map.");
1597	}
1598
1599	template <class K, class T, class H, class P, class A>
1600	typename unordered_map<K, T, H, P, A>::mapped_type const&
1601	unordered_map<K, T, H, P, A>::at(const key_type& k) const
1602	{
1603	typedef typename table::node_pointer node_pointer;
1604
1605	if (table_.size_) {
1606	node_pointer p = table_.find_node(k);
1607	if (p)
1608	return p->value().second;
1609	}
1610
1611	boost::unordered::detail::throw_out_of_range(
1612	message: "Unable to find key in unordered_map.");
1613	}
1614
1615	template <class K, class T, class H, class P, class A>
1616	template <class Key>
1617	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1618	typename unordered_map<K, T, H, P, A>::mapped_type&>::type
1619	unordered_map<K, T, H, P, A>::at(Key&& k)
1620	{
1621	typedef typename table::node_pointer node_pointer;
1622
1623	if (table_.size_) {
1624	node_pointer p = table_.find_node(std::forward<Key>(k));
1625	if (p)
1626	return p->value().second;
1627	}
1628
1629	boost::unordered::detail::throw_out_of_range(
1630	message: "Unable to find key in unordered_map.");
1631	}
1632
1633	template <class K, class T, class H, class P, class A>
1634	template <class Key>
1635	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1636	typename unordered_map<K, T, H, P, A>::mapped_type const&>::type
1637	unordered_map<K, T, H, P, A>::at(Key&& k) const
1638	{
1639	typedef typename table::node_pointer node_pointer;
1640
1641	if (table_.size_) {
1642	node_pointer p = table_.find_node(std::forward<Key>(k));
1643	if (p)
1644	return p->value().second;
1645	}
1646
1647	boost::unordered::detail::throw_out_of_range(
1648	message: "Unable to find key in unordered_map.");
1649	}
1650
1651	template <class K, class T, class H, class P, class A>
1652	typename unordered_map<K, T, H, P, A>::size_type
1653	unordered_map<K, T, H, P, A>::bucket_size(size_type n) const
1654	{
1655	return table_.bucket_size(n);
1656	}
1657
1658	// hash policy
1659
1660	template <class K, class T, class H, class P, class A>
1661	float unordered_map<K, T, H, P, A>::load_factor() const noexcept
1662	{
1663	if (table_.size_ == 0) {
1664	return 0.0f;
1665	}
1666
1667	BOOST_ASSERT(table_.bucket_count() != 0);
1668	return static_cast<float>(table_.size_) /
1669	static_cast<float>(table_.bucket_count());
1670	}
1671
1672	template <class K, class T, class H, class P, class A>
1673	void unordered_map<K, T, H, P, A>::max_load_factor(float m) noexcept
1674	{
1675	table_.max_load_factor(m);
1676	}
1677
1678	template <class K, class T, class H, class P, class A>
1679	void unordered_map<K, T, H, P, A>::rehash(size_type n)
1680	{
1681	table_.rehash(n);
1682	}
1683
1684	template <class K, class T, class H, class P, class A>
1685	void unordered_map<K, T, H, P, A>::reserve(size_type n)
1686	{
1687	table_.reserve(n);
1688	}
1689
1690	template <class K, class T, class H, class P, class A>
1691	inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
1692	unordered_map<K, T, H, P, A> const& m2)
1693	{
1694	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1695	struct dummy
1696	{
1697	unordered_map<K, T, H, P, A> x;
1698	};
1699	#endif
1700	return m1.table_.equals_unique(m2.table_);
1701	}
1702
1703	template <class K, class T, class H, class P, class A>
1704	inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
1705	unordered_map<K, T, H, P, A> const& m2)
1706	{
1707	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1708	struct dummy
1709	{
1710	unordered_map<K, T, H, P, A> x;
1711	};
1712	#endif
1713	return !m1.table_.equals_unique(m2.table_);
1714	}
1715
1716	template <class K, class T, class H, class P, class A>
1717	inline void swap(unordered_map<K, T, H, P, A>& m1,
1718	unordered_map<K, T, H, P, A>& m2) noexcept(noexcept(m1.swap(m2)))
1719	{
1720	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
1721	struct dummy
1722	{
1723	unordered_map<K, T, H, P, A> x;
1724	};
1725	#endif
1726	m1.swap(m2);
1727	}
1728
1729	template <class K, class T, class H, class P, class A, class Predicate>
1730	typename unordered_map<K, T, H, P, A>::size_type erase_if(
1731	unordered_map<K, T, H, P, A>& c, Predicate pred)
1732	{
1733	return detail::erase_if(c, pred);
1734	}
1735
1736	////////////////////////////////////////////////////////////////////////////
1737
1738	template <class K, class T, class H, class P, class A>
1739	unordered_multimap<K, T, H, P, A>::unordered_multimap()
1740	{
1741	}
1742
1743	template <class K, class T, class H, class P, class A>
1744	unordered_multimap<K, T, H, P, A>::unordered_multimap(size_type n,
1745	const hasher& hf, const key_equal& eql, const allocator_type& a)
1746	: table_(n, hf, eql, a)
1747	{
1748	}
1749
1750	template <class K, class T, class H, class P, class A>
1751	template <class InputIt>
1752	unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
1753	size_type n, const hasher& hf, const key_equal& eql,
1754	const allocator_type& a)
1755	: table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1756	{
1757	this->insert(f, l);
1758	}
1759
1760	template <class K, class T, class H, class P, class A>
1761	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1762	unordered_multimap const& other)
1763	: table_(other.table_,
1764	unordered_multimap::value_allocator_traits::
1765	select_on_container_copy_construction(other.get_allocator()))
1766	{
1767	if (other.table_.size_) {
1768	table_.copy_buckets(other.table_, std::false_type());
1769	}
1770	}
1771
1772	template <class K, class T, class H, class P, class A>
1773	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1774	allocator_type const& a)
1775	: table_(boost::unordered::detail::default_bucket_count, hasher(),
1776	key_equal(), a)
1777	{
1778	}
1779
1780	template <class K, class T, class H, class P, class A>
1781	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1782	unordered_multimap const& other, allocator_type const& a)
1783	: table_(other.table_, a)
1784	{
1785	if (other.table_.size_) {
1786	table_.copy_buckets(other.table_, std::false_type());
1787	}
1788	}
1789
1790	template <class K, class T, class H, class P, class A>
1791	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1792	unordered_multimap&& other, allocator_type const& a)
1793	: table_(other.table_, a, boost::unordered::detail::move_tag())
1794	{
1795	table_.move_construct_buckets(other.table_);
1796	}
1797
1798	template <class K, class T, class H, class P, class A>
1799	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1800	std::initializer_list<value_type> list, size_type n, const hasher& hf,
1801	const key_equal& eql, const allocator_type& a)
1802	: table_(
1803	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1804	hf, eql, a)
1805	{
1806	this->insert(list.begin(), list.end());
1807	}
1808
1809	template <class K, class T, class H, class P, class A>
1810	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1811	size_type n, const allocator_type& a)
1812	: table_(n, hasher(), key_equal(), a)
1813	{
1814	}
1815
1816	template <class K, class T, class H, class P, class A>
1817	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1818	size_type n, const hasher& hf, const allocator_type& a)
1819	: table_(n, hf, key_equal(), a)
1820	{
1821	}
1822
1823	template <class K, class T, class H, class P, class A>
1824	template <class InputIterator>
1825	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1826	InputIterator f, InputIterator l, const allocator_type& a)
1827	: table_(boost::unordered::detail::initial_size(
1828	f, l, detail::default_bucket_count),
1829	hasher(), key_equal(), a)
1830	{
1831	this->insert(f, l);
1832	}
1833
1834	template <class K, class T, class H, class P, class A>
1835	template <class InputIt>
1836	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1837	InputIt f, InputIt l, size_type n, const allocator_type& a)
1838	: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1839	key_equal(), a)
1840	{
1841	this->insert(f, l);
1842	}
1843
1844	template <class K, class T, class H, class P, class A>
1845	template <class InputIt>
1846	unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
1847	size_type n, const hasher& hf, const allocator_type& a)
1848	: table_(
1849	boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1850	{
1851	this->insert(f, l);
1852	}
1853
1854	template <class K, class T, class H, class P, class A>
1855	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1856	std::initializer_list<value_type> list, const allocator_type& a)
1857	: table_(boost::unordered::detail::initial_size(
1858	list.begin(), list.end(), detail::default_bucket_count),
1859	hasher(), key_equal(), a)
1860	{
1861	this->insert(list.begin(), list.end());
1862	}
1863
1864	template <class K, class T, class H, class P, class A>
1865	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1866	std::initializer_list<value_type> list, size_type n,
1867	const allocator_type& a)
1868	: table_(
1869	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1870	hasher(), key_equal(), a)
1871	{
1872	this->insert(list.begin(), list.end());
1873	}
1874
1875	template <class K, class T, class H, class P, class A>
1876	unordered_multimap<K, T, H, P, A>::unordered_multimap(
1877	std::initializer_list<value_type> list, size_type n, const hasher& hf,
1878	const allocator_type& a)
1879	: table_(
1880	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1881	hf, key_equal(), a)
1882	{
1883	this->insert(list.begin(), list.end());
1884	}
1885
1886	template <class K, class T, class H, class P, class A>
1887	unordered_multimap<K, T, H, P, A>::~unordered_multimap() noexcept
1888	{
1889	}
1890
1891	template <class K, class T, class H, class P, class A>
1892	unordered_multimap<K, T, H, P, A>&
1893	unordered_multimap<K, T, H, P, A>::operator=(
1894	std::initializer_list<value_type> list)
1895	{
1896	this->clear();
1897	this->insert(list.begin(), list.end());
1898	return *this;
1899	}
1900
1901	// size and capacity
1902
1903	template <class K, class T, class H, class P, class A>
1904	std::size_t unordered_multimap<K, T, H, P, A>::max_size() const noexcept
1905	{
1906	using namespace std;
1907
1908	// size <= mlf_ * count
1909	return boost::unordered::detail::double_to_size(
1910	f: ceil(x: static_cast<double>(table_.mlf_) *
1911	static_cast<double>(table_.max_bucket_count()))) -
1912	1;
1913	}
1914
1915	// modifiers
1916
1917	template <class K, class T, class H, class P, class A>
1918	template <class InputIt>
1919	void unordered_multimap<K, T, H, P, A>::insert(InputIt first, InputIt last)
1920	{
1921	table_.insert_range_equiv(first, last);
1922	}
1923
1924	template <class K, class T, class H, class P, class A>
1925	void unordered_multimap<K, T, H, P, A>::insert(
1926	std::initializer_list<value_type> list)
1927	{
1928	this->insert(list.begin(), list.end());
1929	}
1930
1931	template <class K, class T, class H, class P, class A>
1932	typename unordered_multimap<K, T, H, P, A>::iterator
1933	unordered_multimap<K, T, H, P, A>::erase(iterator position)
1934	{
1935	BOOST_ASSERT(position != this->end());
1936	return table_.erase_node(position);
1937	}
1938
1939	template <class K, class T, class H, class P, class A>
1940	typename unordered_multimap<K, T, H, P, A>::iterator
1941	unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
1942	{
1943	BOOST_ASSERT(position != this->end());
1944	return table_.erase_node(position);
1945	}
1946
1947	template <class K, class T, class H, class P, class A>
1948	typename unordered_multimap<K, T, H, P, A>::size_type
1949	unordered_multimap<K, T, H, P, A>::erase(const key_type& k)
1950	{
1951	return table_.erase_key_equiv(k);
1952	}
1953
1954	template <class K, class T, class H, class P, class A>
1955	typename unordered_multimap<K, T, H, P, A>::iterator
1956	unordered_multimap<K, T, H, P, A>::erase(
1957	const_iterator first, const_iterator last)
1958	{
1959	return table_.erase_nodes_range(first, last);
1960	}
1961
1962	template <class K, class T, class H, class P, class A>
1963	void unordered_multimap<K, T, H, P, A>::swap(unordered_multimap& other)
1964	noexcept(value_allocator_traits::is_always_equal::value&&
1965	boost::unordered::detail::is_nothrow_swappable<H>::value&&
1966	boost::unordered::detail::is_nothrow_swappable<P>::value)
1967	{
1968	table_.swap(other.table_);
1969	}
1970
1971	// observers
1972
1973	template <class K, class T, class H, class P, class A>
1974	typename unordered_multimap<K, T, H, P, A>::hasher
1975	unordered_multimap<K, T, H, P, A>::hash_function() const
1976	{
1977	return table_.hash_function();
1978	}
1979
1980	template <class K, class T, class H, class P, class A>
1981	typename unordered_multimap<K, T, H, P, A>::key_equal
1982	unordered_multimap<K, T, H, P, A>::key_eq() const
1983	{
1984	return table_.key_eq();
1985	}
1986
1987	template <class K, class T, class H, class P, class A>
1988	template <typename H2, typename P2>
1989	void unordered_multimap<K, T, H, P, A>::merge(
1990	boost::unordered_multimap<K, T, H2, P2, A>& source)
1991	{
1992	while (!source.empty()) {
1993	insert(source.extract(source.begin()));
1994	}
1995	}
1996
1997	template <class K, class T, class H, class P, class A>
1998	template <typename H2, typename P2>
1999	void unordered_multimap<K, T, H, P, A>::merge(
2000	boost::unordered_multimap<K, T, H2, P2, A>&& source)
2001	{
2002	while (!source.empty()) {
2003	insert(source.extract(source.begin()));
2004	}
2005	}
2006
2007	template <class K, class T, class H, class P, class A>
2008	template <typename H2, typename P2>
2009	void unordered_multimap<K, T, H, P, A>::merge(
2010	boost::unordered_map<K, T, H2, P2, A>& source)
2011	{
2012	while (!source.empty()) {
2013	insert(source.extract(source.begin()));
2014	}
2015	}
2016
2017	template <class K, class T, class H, class P, class A>
2018	template <typename H2, typename P2>
2019	void unordered_multimap<K, T, H, P, A>::merge(
2020	boost::unordered_map<K, T, H2, P2, A>&& source)
2021	{
2022	while (!source.empty()) {
2023	insert(source.extract(source.begin()));
2024	}
2025	}
2026
2027	// lookup
2028
2029	template <class K, class T, class H, class P, class A>
2030	typename unordered_multimap<K, T, H, P, A>::iterator
2031	unordered_multimap<K, T, H, P, A>::find(const key_type& k)
2032	{
2033	return iterator(table_.find(k));
2034	}
2035
2036	template <class K, class T, class H, class P, class A>
2037	typename unordered_multimap<K, T, H, P, A>::const_iterator
2038	unordered_multimap<K, T, H, P, A>::find(const key_type& k) const
2039	{
2040	return const_iterator(table_.find(k));
2041	}
2042
2043	template <class K, class T, class H, class P, class A>
2044	template <class CompatibleKey, class CompatibleHash,
2045	class CompatiblePredicate>
2046	typename unordered_multimap<K, T, H, P, A>::iterator
2047	unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2048	CompatibleHash const& hash, CompatiblePredicate const& eq)
2049	{
2050	return table_.transparent_find(k, hash, eq);
2051	}
2052
2053	template <class K, class T, class H, class P, class A>
2054	template <class CompatibleKey, class CompatibleHash,
2055	class CompatiblePredicate>
2056	typename unordered_multimap<K, T, H, P, A>::const_iterator
2057	unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2058	CompatibleHash const& hash, CompatiblePredicate const& eq) const
2059	{
2060	return table_.transparent_find(k, hash, eq);
2061	}
2062
2063	template <class K, class T, class H, class P, class A>
2064	typename unordered_multimap<K, T, H, P, A>::size_type
2065	unordered_multimap<K, T, H, P, A>::count(const key_type& k) const
2066	{
2067	return table_.group_count(k);
2068	}
2069
2070	template <class K, class T, class H, class P, class A>
2071	std::pair<typename unordered_multimap<K, T, H, P, A>::iterator,
2072	typename unordered_multimap<K, T, H, P, A>::iterator>
2073	unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k)
2074	{
2075	iterator n = table_.find(k);
2076	return std::make_pair(n, (n == end() ? n : table_.next_group(k, n)));
2077	}
2078
2079	template <class K, class T, class H, class P, class A>
2080	std::pair<typename unordered_multimap<K, T, H, P, A>::const_iterator,
2081	typename unordered_multimap<K, T, H, P, A>::const_iterator>
2082	unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const
2083	{
2084	iterator n = table_.find(k);
2085	return std::make_pair(const_iterator(n),
2086	const_iterator(n == end() ? n : table_.next_group(k, n)));
2087	}
2088
2089	template <class K, class T, class H, class P, class A>
2090	typename unordered_multimap<K, T, H, P, A>::size_type
2091	unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const
2092	{
2093	return table_.bucket_size(n);
2094	}
2095
2096	// hash policy
2097
2098	template <class K, class T, class H, class P, class A>
2099	float unordered_multimap<K, T, H, P, A>::load_factor() const noexcept
2100	{
2101	if (table_.size_ == 0) {
2102	return 0.0f;
2103	}
2104
2105	BOOST_ASSERT(table_.bucket_count() != 0);
2106	return static_cast<float>(table_.size_) /
2107	static_cast<float>(table_.bucket_count());
2108	}
2109
2110	template <class K, class T, class H, class P, class A>
2111	void unordered_multimap<K, T, H, P, A>::max_load_factor(float m) noexcept
2112	{
2113	table_.max_load_factor(m);
2114	}
2115
2116	template <class K, class T, class H, class P, class A>
2117	void unordered_multimap<K, T, H, P, A>::rehash(size_type n)
2118	{
2119	table_.rehash(n);
2120	}
2121
2122	template <class K, class T, class H, class P, class A>
2123	void unordered_multimap<K, T, H, P, A>::reserve(size_type n)
2124	{
2125	table_.reserve(n);
2126	}
2127
2128	template <class K, class T, class H, class P, class A>
2129	inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
2130	unordered_multimap<K, T, H, P, A> const& m2)
2131	{
2132	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2133	struct dummy
2134	{
2135	unordered_multimap<K, T, H, P, A> x;
2136	};
2137	#endif
2138	return m1.table_.equals_equiv(m2.table_);
2139	}
2140
2141	template <class K, class T, class H, class P, class A>
2142	inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
2143	unordered_multimap<K, T, H, P, A> const& m2)
2144	{
2145	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2146	struct dummy
2147	{
2148	unordered_multimap<K, T, H, P, A> x;
2149	};
2150	#endif
2151	return !m1.table_.equals_equiv(m2.table_);
2152	}
2153
2154	template <class K, class T, class H, class P, class A>
2155	inline void swap(unordered_multimap<K, T, H, P, A>& m1,
2156	unordered_multimap<K, T, H, P, A>& m2) noexcept(noexcept(m1.swap(m2)))
2157	{
2158	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2159	struct dummy
2160	{
2161	unordered_multimap<K, T, H, P, A> x;
2162	};
2163	#endif
2164	m1.swap(m2);
2165	}
2166
2167	template <class K, class T, class H, class P, class A, class Predicate>
2168	typename unordered_multimap<K, T, H, P, A>::size_type erase_if(
2169	unordered_multimap<K, T, H, P, A>& c, Predicate pred)
2170	{
2171	return detail::erase_if(c, pred);
2172	}
2173
2174	template <typename N, class K, class T, class A> class node_handle_map
2175	{
2176	template <typename Types> friend struct ::boost::unordered::detail::table;
2177	template <class K2, class T2, class H2, class P2, class A2>
2178	friend class boost::unordered::unordered_map;
2179	template <class K2, class T2, class H2, class P2, class A2>
2180	friend class boost::unordered::unordered_multimap;
2181
2182	typedef typename boost::allocator_rebind<A, std::pair<K const, T> >::type
2183	value_allocator;
2184
2185	typedef N node;
2186	typedef typename boost::allocator_rebind<A, node>::type node_allocator;
2187
2188	typedef
2189	typename boost::allocator_pointer<node_allocator>::type node_pointer;
2190
2191	public:
2192	typedef K key_type;
2193	typedef T mapped_type;
2194	typedef A allocator_type;
2195
2196	private:
2197	node_pointer ptr_;
2198	boost::unordered::detail::optional<value_allocator> alloc_;
2199
2200	node_handle_map(node_pointer ptr, allocator_type const& a)
2201	: ptr_(ptr), alloc_(a)
2202	{
2203	}
2204
2205	public:
2206	constexpr node_handle_map() noexcept : ptr_(), alloc_() {}
2207	node_handle_map(node_handle_map const&) = delete;
2208	node_handle_map& operator=(node_handle_map const&) = delete;
2209
2210	~node_handle_map()
2211	{
2212	if (ptr_) {
2213	node_allocator node_alloc(*alloc_);
2214	boost::unordered::detail::node_tmp<node_allocator> tmp(
2215	ptr_, node_alloc);
2216	}
2217	}
2218
2219	node_handle_map(node_handle_map&& n) noexcept
2220	: ptr_(n.ptr_),
2221	alloc_(std::move(n.alloc_))
2222	{
2223	n.ptr_ = node_pointer();
2224	}
2225
2226	node_handle_map& operator=(node_handle_map&& n)
2227	{
2228	BOOST_ASSERT(!alloc_.has_value() ||
2229	boost::allocator_propagate_on_container_move_assignment<
2230	value_allocator>::type::value ||
2231	(n.alloc_.has_value() && alloc_ == n.alloc_));
2232
2233	if (ptr_) {
2234	node_allocator node_alloc(*alloc_);
2235	boost::unordered::detail::node_tmp<node_allocator> tmp(
2236	ptr_, node_alloc);
2237	ptr_ = node_pointer();
2238	}
2239
2240	if (!alloc_.has_value() ||
2241	boost::allocator_propagate_on_container_move_assignment<
2242	value_allocator>::type::value) {
2243	alloc_ = std::move(n.alloc_);
2244	}
2245	ptr_ = n.ptr_;
2246	n.ptr_ = node_pointer();
2247
2248	return *this;
2249	}
2250
2251	key_type& key() const
2252	{
2253	return const_cast<key_type&>(ptr_->value().first);
2254	}
2255
2256	mapped_type& mapped() const { return ptr_->value().second; }
2257
2258	allocator_type get_allocator() const { return *alloc_; }
2259
2260	explicit operator bool() const noexcept
2261	{
2262	return !this->operator!();
2263	}
2264
2265	bool operator!() const noexcept { return ptr_ ? 0 : 1; }
2266
2267	BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
2268	{
2269	return ptr_ ? 0 : 1;
2270	}
2271
2272	void swap(node_handle_map& n)
2273	noexcept(boost::allocator_propagate_on_container_swap<
2274	value_allocator>::type::value ||
2275	boost::allocator_is_always_equal<value_allocator>::type::value)
2276	{
2277
2278	BOOST_ASSERT(!alloc_.has_value() || !n.alloc_.has_value() ||
2279	boost::allocator_propagate_on_container_swap<
2280	value_allocator>::type::value ||
2281	alloc_ == n.alloc_);
2282	if (boost::allocator_propagate_on_container_swap<
2283	value_allocator>::type::value ||
2284	!alloc_.has_value() || !n.alloc_.has_value()) {
2285	boost::core::invoke_swap(alloc_, n.alloc_);
2286	}
2287	boost::core::invoke_swap(ptr_, n.ptr_);
2288	}
2289	};
2290
2291	template <class N, class K, class T, class A>
2292	void swap(node_handle_map<N, K, T, A>& x, node_handle_map<N, K, T, A>& y)
2293	noexcept(noexcept(x.swap(y)))
2294	{
2295	x.swap(y);
2296	}
2297
2298	template <class Iter, class NodeType> struct insert_return_type_map
2299	{
2300	public:
2301	Iter position;
2302	bool inserted;
2303	NodeType node;
2304
2305	insert_return_type_map() : position(), inserted(false), node() {}
2306	insert_return_type_map(insert_return_type_map const&) = delete;
2307	insert_return_type_map& operator=(insert_return_type_map const&) = delete;
2308
2309	insert_return_type_map(insert_return_type_map&& x) noexcept
2310	: position(x.position),
2311	inserted(x.inserted),
2312	node(std::move(x.node))
2313	{
2314	}
2315
2316	insert_return_type_map& operator=(insert_return_type_map&& x)
2317	{
2318	inserted = x.inserted;
2319	position = x.position;
2320	node = std::move(x.node);
2321	return *this;
2322	}
2323	};
2324
2325	template <class Iter, class NodeType>
2326	void swap(insert_return_type_map<Iter, NodeType>& x,
2327	insert_return_type_map<Iter, NodeType>& y)
2328	{
2329	boost::core::invoke_swap(x.node, y.node);
2330	boost::core::invoke_swap(x.inserted, y.inserted);
2331	boost::core::invoke_swap(x.position, y.position);
2332	}
2333	} // namespace unordered
2334
2335	namespace serialization {
2336	template <class K, class T, class H, class P, class A>
2337	struct version<boost::unordered_map<K, T, H, P, A> >
2338	{
2339	BOOST_STATIC_CONSTANT(int, value = 1);
2340	};
2341
2342	template <class K, class T, class H, class P, class A>
2343	struct version<boost::unordered_multimap<K, T, H, P, A> >
2344	{
2345	BOOST_STATIC_CONSTANT(int, value = 1);
2346	};
2347	} // namespace serialization
2348
2349	} // namespace boost
2350
2351	#if defined(BOOST_MSVC)
2352	#pragma warning(pop)
2353	#endif
2354
2355	#endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
2356