unordered_map.hpp source code [include/boost/unordered/unordered_map.hpp]

1
2	// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
3	// Copyright (C) 2005-2011 Daniel James.
4	// Copyright (C) 2022 Christian Mazakas
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/requires_cxx11.hpp>
19	#include <boost/core/explicit_operator_bool.hpp>
20	#include <boost/functional/hash.hpp>
21	#include <boost/move/move.hpp>
22	#include <boost/type_traits/is_constructible.hpp>
23	#include <boost/unordered/detail/map.hpp>
24	#include <boost/unordered/detail/type_traits.hpp>
25
26	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
27	#include <initializer_list>
28	#endif
29
30	#if defined(BOOST_MSVC)
31	#pragma warning(push)
32	// conditional expression is constant
33	#pragma warning(disable : 4127)
34	#if BOOST_MSVC >= 1400
35	// the inline specifier cannot be used when a friend declaration refers to a
36	// specialization of a function template
37	#pragma warning(disable : 4396)
38	#endif
39	#endif
40
41	namespace boost {
42	namespace unordered {
43	template <class K, class T, class H, class P, class A> class unordered_map
44	{
45	#if defined(BOOST_UNORDERED_USE_MOVE)
46	BOOST_COPYABLE_AND_MOVABLE(unordered_map)
47	#endif
48	template <typename, typename, typename, typename, typename>
49	friend class unordered_multimap;
50
51	public:
52	typedef K key_type;
53	typedef T mapped_type;
54	typedef std::pair<const K, T> value_type;
55	typedef typename boost::type_identity<H>::type hasher;
56	typedef typename boost::type_identity<P>::type key_equal;
57	typedef typename boost::type_identity<A>::type allocator_type;
58
59	private:
60	typedef boost::unordered::detail::map<A, K, T, H, P> types;
61	typedef typename types::value_allocator_traits value_allocator_traits;
62	typedef typename types::table table;
63
64	public:
65	typedef typename value_allocator_traits::pointer pointer;
66	typedef typename value_allocator_traits::const_pointer const_pointer;
67
68	typedef value_type& reference;
69	typedef value_type const& const_reference;
70
71	typedef std::size_t size_type;
72	typedef std::ptrdiff_t difference_type;
73
74	typedef typename table::iterator iterator;
75	typedef typename table::c_iterator const_iterator;
76	typedef typename table::l_iterator local_iterator;
77	typedef typename table::cl_iterator const_local_iterator;
78	typedef typename types::node_type node_type;
79	typedef typename types::insert_return_type insert_return_type;
80
81	private:
82	table table_;
83
84	public:
85	// constructors
86
87	unordered_map();
88
89	explicit unordered_map(size_type, const hasher& = hasher(),
90	const key_equal& = key_equal(),
91	const allocator_type& = allocator_type());
92
93	template <class InputIt>
94	unordered_map(InputIt, InputIt,
95	size_type = boost::unordered::detail::default_bucket_count,
96	const hasher& = hasher(), const key_equal& = key_equal(),
97	const allocator_type& = allocator_type());
98
99	unordered_map(unordered_map const&);
100
101	#if defined(BOOST_UNORDERED_USE_MOVE) \|\| \
102	!defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
103	unordered_map(BOOST_RV_REF(unordered_map) other)
104	BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
105	: table_(other.table_, boost::unordered::detail::move_tag ())
106	{
107	// The move is done in table_
108	}
109	#endif
110
111	explicit unordered_map(allocator_type const&);
112
113	unordered_map(unordered_map const&, allocator_type const&);
114
115	unordered_map(BOOST_RV_REF(unordered_map), allocator_type const&);
116
117	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
118	unordered_map(std::initializer_list<value_type>,
119	size_type = boost::unordered::detail::default_bucket_count,
120	const hasher& = hasher(), const key_equal& l = key_equal(),
121	const allocator_type& = allocator_type());
122	#endif
123
124	explicit unordered_map(size_type, const allocator_type&);
125
126	explicit unordered_map(size_type, const hasher&, const allocator_type&);
127
128	template <class InputIterator>
129	unordered_map(InputIterator, InputIterator, const allocator_type&);
130
131	template <class InputIt>
132	unordered_map(InputIt, InputIt, size_type, const allocator_type&);
133
134	template <class InputIt>
135	unordered_map(
136	InputIt, InputIt, size_type, const hasher&, const allocator_type&);
137
138	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
139	unordered_map(std::initializer_list<value_type>, const allocator_type&);
140
141	unordered_map(
142	std::initializer_list<value_type>, size_type, const allocator_type&);
143
144	unordered_map(std::initializer_list<value_type>, size_type, const hasher&,
145	const allocator_type&);
146	#endif
147
148	// Destructor
149
150	~unordered_map() BOOST_NOEXCEPT;
151
152	// Assign
153
154	#if defined(BOOST_UNORDERED_USE_MOVE)
155	unordered_map& operator=(BOOST_COPY_ASSIGN_REF(unordered_map) x)
156	{
157	table_.assign(x.table_, boost::unordered::detail::true_type());
158	return *this;
159	}
160
161	unordered_map& operator=(BOOST_RV_REF(unordered_map) x)
162	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
163	boost::is_nothrow_move_assignable<H>::value&&
164	boost::is_nothrow_move_assignable<P>::value)
165	{
166	table_.move_assign(x.table_, boost::unordered::detail::true_type());
167	return *this;
168	}
169	#else
170	unordered_map& operator=(unordered_map const& x)
171	{
172	table_.assign(x.table_, boost::unordered::detail::true_type());
173	return *this;
174	}
175
176	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
177	unordered_map& operator=(unordered_map&& x)
178	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
179	boost::is_nothrow_move_assignable<H>::value&&
180	boost::is_nothrow_move_assignable<P>::value)
181	{
182	table_.move_assign(x.table_, boost::unordered::detail::true_type());
183	return *this;
184	}
185	#endif
186	#endif
187
188	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
189	unordered_map& operator=(std::initializer_list<value_type>);
190	#endif
191
192	allocator_type get_allocator() const BOOST_NOEXCEPT
193	{
194	return table_.node_alloc();
195	}
196
197	// // iterators
198
199	iterator begin() BOOST_NOEXCEPT { return table_.begin(); }
200
201	const_iterator begin() const BOOST_NOEXCEPT
202	{
203	return const_iterator(table_.begin());
204	}
205
206	iterator end() BOOST_NOEXCEPT { return iterator(); }
207
208	const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
209
210	const_iterator cbegin() const BOOST_NOEXCEPT
211	{
212	return const_iterator(table_.begin());
213	}
214
215	const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
216
217	// size and capacity
218
219	BOOST_ATTRIBUTE_NODISCARD bool empty() const BOOST_NOEXCEPT
220	{
221	return table_.size_ == `0`;
222	}
223
224	size_type size() const BOOST_NOEXCEPT { return table_.size_; }
225
226	size_type max_size() const BOOST_NOEXCEPT;
227
228	// emplace
229
230	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
231
232	template <class... Args>
233	std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
234	{
235	return table_.emplace_unique(
236	table::extractor::extract(boost::forward<Args>(args)...),
237	boost::forward<Args>(args)...);
238	}
239
240	#else
241
242	#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
243
244	// 0 argument emplace requires special treatment in case
245	// the container is instantiated with a value type that
246	// doesn't have a default constructor.
247
248	std::pair<iterator, bool> emplace(
249	boost::unordered::detail::empty_emplace =
250	boost::unordered::detail::empty_emplace(),
251	value_type v = value_type())
252	{
253	return this->emplace(boost::move(v));
254	}
255
256	#endif
257
258	template <typename A0>
259	std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
260	{
261	return table_.emplace_unique(
262	table::extractor::extract(boost::forward<A0>(a0)),
263	boost::unordered::detail::create_emplace_args(
264	boost::forward<A0>(a0)));
265	}
266
267	template <typename A0, typename A1>
268	std::pair<iterator, bool> emplace(
269	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
270	{
271	return table_.emplace_unique(
272	table::extractor::extract(
273	boost::forward<A0>(a0), boost::forward<A1>(a1)),
274	boost::unordered::detail::create_emplace_args(
275	boost::forward<A0>(a0), boost::forward<A1>(a1)));
276	}
277
278	template <typename A0, typename A1, typename A2>
279	std::pair<iterator, bool> emplace(
280	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
281	{
282	return table_.emplace_unique(
283	table::extractor::extract(
284	boost::forward<A0>(a0), boost::forward<A1>(a1)),
285	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
286	boost::forward<A1>(a1), boost::forward<A2>(a2)));
287	}
288
289	#endif
290
291	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
292
293	template <class... Args>
294	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
295	{
296	return table_.emplace_hint_unique(hint,
297	table::extractor::extract(boost::forward<Args>(args)...),
298	boost::forward<Args>(args)...);
299	}
300
301	#else
302
303	#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
304
305	iterator emplace_hint(const_iterator hint,
306	boost::unordered::detail::empty_emplace =
307	boost::unordered::detail::empty_emplace(),
308	value_type v = value_type())
309	{
310	return this->emplace_hint(hint, boost::move(v));
311	}
312
313	#endif
314
315	template <typename A0>
316	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
317	{
318	return table_.emplace_hint_unique(hint,
319	table::extractor::extract(boost::forward<A0>(a0)),
320	boost::unordered::detail::create_emplace_args(
321	boost::forward<A0>(a0)));
322	}
323
324	template <typename A0, typename A1>
325	iterator emplace_hint(
326	const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
327	{
328	return table_.emplace_hint_unique(hint,
329	table::extractor::extract(
330	boost::forward<A0>(a0), boost::forward<A1>(a1)),
331	boost::unordered::detail::create_emplace_args(
332	boost::forward<A0>(a0), boost::forward<A1>(a1)));
333	}
334
335	template <typename A0, typename A1, typename A2>
336	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
337	BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
338	{
339	return table_.emplace_hint_unique(hint,
340	table::extractor::extract(
341	boost::forward<A0>(a0), boost::forward<A1>(a1)),
342	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
343	boost::forward<A1>(a1), boost::forward<A2>(a2)));
344	}
345
346	#endif
347
348	#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
349
350	#define BOOST_UNORDERED_EMPLACE(z, n, _) \
351	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
352	std::pair<iterator, bool> emplace( \
353	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
354	{ \
355	return table_.emplace_unique( \
356	table::extractor::extract( \
357	boost::forward<A0>(a0), boost::forward<A1>(a1)), \
358	boost::unordered::detail::create_emplace_args( \
359	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
360	} \
361	\
362	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
363	iterator emplace_hint( \
364	const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
365	{ \
366	return table_.emplace_hint_unique(hint, \
367	table::extractor::extract( \
368	boost::forward<A0>(a0), boost::forward<A1>(a1)), \
369	boost::unordered::detail::create_emplace_args( \
370	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
371	}
372
373	BOOST_UNORDERED_EMPLACE(`1`, `4`, _)
374	BOOST_UNORDERED_EMPLACE(`1`, `5`, _)
375	BOOST_UNORDERED_EMPLACE(`1`, `6`, _)
376	BOOST_UNORDERED_EMPLACE(`1`, `7`, _)
377	BOOST_UNORDERED_EMPLACE(`1`, `8`, _)
378	BOOST_UNORDERED_EMPLACE(`1`, `9`, _)
379	BOOST_PP_REPEAT_FROM_TO(`10`, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
380	BOOST_UNORDERED_EMPLACE, _)
381
382	#undef BOOST_UNORDERED_EMPLACE
383
384	#endif
385
386	std::pair<iterator, bool> insert(value_type const& x)
387	{
388	return this->emplace(x);
389	}
390
391	std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x)
392	{
393	return this->emplace(boost::move(x));
394	}
395
396	template <class P2>
397	typename boost::enable_if<
398	boost::is_constructible<value_type, BOOST_RV_REF(P2)>,
399	std::pair<iterator, bool> >::type insert(BOOST_RV_REF(P2) obj)
400	{
401	return this->emplace(boost::forward<P2>(obj));
402	}
403
404	iterator insert(const_iterator hint, value_type const& x)
405	{
406	return this->emplace_hint(hint, x);
407	}
408
409	iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
410	{
411	return this->emplace_hint(hint, boost::move(x));
412	}
413
414	template <class P2>
415	typename boost::enable_if<
416	boost::is_constructible<value_type, BOOST_RV_REF(P2)>, iterator>::type
417	insert(const_iterator hint, BOOST_RV_REF(P2) obj)
418	{
419	return this->emplace_hint(hint, boost::forward<P2>(obj));
420	}
421
422	template <class InputIt> void insert(InputIt, InputIt);
423
424	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
425	void insert(std::initializer_list<value_type>);
426	#endif
427
428	// extract
429
430	node_type extract(const_iterator position)
431	{
432	return node_type(
433	table_.extract_by_iterator_unique(position), table_.node_alloc());
434	}
435
436	node_type extract(const key_type& k)
437	{
438	return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
439	}
440
441	template <class Key>
442	typename boost::enable_if_c<
443	detail::transparent_non_iterable<Key, unordered_map>::value,
444	node_type>::type
445	extract(BOOST_FWD_REF(Key) k)
446	{
447	return node_type(table_.extract_by_key_impl(boost::forward<Key>(k)),
448	table_.node_alloc());
449	}
450
451	insert_return_type insert(BOOST_RV_REF(node_type) np)
452	{
453	insert_return_type result;
454	table_.move_insert_node_type_unique((node_type&)np, result);
455	return boost::move(result);
456	}
457
458	iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
459	{
460	return table_.move_insert_node_type_with_hint_unique(hint, np);
461	}
462
463	#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) \|\| \
464	(BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
465	private:
466	// Note: Use r-value node_type to insert.
467	insert_return_type insert(node_type&);
468	iterator insert(const_iterator, node_type& np);
469
470	public:
471	#endif
472
473	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
474
475	template <class... Args>
476	std::pair<iterator, bool> try_emplace(
477	key_type const& k, BOOST_FWD_REF(Args)... args)
478	{
479	return table_.try_emplace_unique(k, boost::forward<Args>(args)...);
480	}
481
482	template <class... Args>
483	std::pair<iterator, bool> try_emplace(
484	BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
485	{
486	return table_.try_emplace_unique(
487	boost::move(k), boost::forward<Args>(args)...);
488	}
489
490	template <class Key, class... Args>
491	typename boost::enable_if_c<
492	detail::transparent_non_iterable<Key, unordered_map>::value,
493	std::pair<iterator, bool> >::type
494	try_emplace(Key&& k, Args&&... args)
495	{
496	return table_.try_emplace_unique(
497	boost::forward<Key>(k), boost::forward<Args>(args)...);
498	}
499
500	template <class... Args>
501	iterator try_emplace(
502	const_iterator hint, key_type const& k, BOOST_FWD_REF(Args)... args)
503	{
504	return table_.try_emplace_hint_unique(
505	hint, k, boost::forward<Args>(args)...);
506	}
507
508	template <class... Args>
509	iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
510	BOOST_FWD_REF(Args)... args)
511	{
512	return table_.try_emplace_hint_unique(
513	hint, boost::move(k), boost::forward<Args>(args)...);
514	}
515
516	template <class Key, class... Args>
517	typename boost::enable_if_c<
518	detail::transparent_non_iterable<Key, unordered_map>::value,
519	iterator>::type
520	try_emplace(const_iterator hint, Key&& k, Args&&... args)
521	{
522	return table_.try_emplace_hint_unique(
523	hint, boost::forward<Key>(k), boost::forward<Args>(args)...);
524	}
525
526	#else
527
528	// In order to make this a template, this handles both:
529	// try_emplace(key const&)
530	// try_emplace(key&&)
531
532	template <typename Key>
533	std::pair<iterator, bool> try_emplace(BOOST_FWD_REF(Key) k)
534	{
535	return table_.try_emplace_unique(boost::forward<Key>(k));
536	}
537
538	// In order to make this a template, this handles both:
539	// try_emplace(const_iterator hint, key const&)
540	// try_emplace(const_iterator hint, key&&)
541
542	template <typename Key>
543	iterator try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k)
544	{
545	return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k));
546	}
547
548	// try_emplace(key const&, Args&&...)
549
550	template <typename A0>
551	std::pair<iterator, bool> try_emplace(
552	key_type const& k, BOOST_FWD_REF(A0) a0)
553	{
554	return table_.try_emplace_unique(
555	k, boost::unordered::detail::create_emplace_args(
556	boost::forward<A0>(a0)));
557	}
558
559	template <typename A0, typename A1>
560	std::pair<iterator, bool> try_emplace(
561	key_type const& k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
562	{
563	return table_.try_emplace_unique(
564	k, boost::unordered::detail::create_emplace_args(
565	boost::forward<A0>(a0), boost::forward<A1>(a1)));
566	}
567
568	template <typename A0, typename A1, typename A2>
569	std::pair<iterator, bool> try_emplace(key_type const& k,
570	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
571	{
572	return table_.try_emplace_unique(k,
573	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
574	boost::forward<A1>(a1), boost::forward<A2>(a2)));
575	}
576
577	// try_emplace(key&&, Args&&...)
578
579	template <typename A0>
580	std::pair<iterator, bool> try_emplace(
581	BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
582	{
583	return table_.try_emplace_unique(
584	boost::move(k), boost::unordered::detail::create_emplace_args(
585	boost::forward<A0>(a0)));
586	}
587
588	template <typename A0, typename A1>
589	std::pair<iterator, bool> try_emplace(
590	BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
591	{
592	return table_.try_emplace_unique(
593	boost::move(k), boost::unordered::detail::create_emplace_args(
594	boost::forward<A0>(a0), boost::forward<A1>(a1)));
595	}
596
597	template <typename A0, typename A1, typename A2>
598	std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k,
599	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
600	{
601	return table_.try_emplace_unique(boost::move(k),
602	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
603	boost::forward<A1>(a1), boost::forward<A2>(a2)));
604	}
605
606	// try_emplace(Key&&, Args&&...)
607
608	template <typename Key, typename A0>
609	typename boost::enable_if_c<
610	detail::transparent_non_iterable<Key, unordered_map>::value,
611	std::pair<iterator, bool> >::type
612	try_emplace(BOOST_FWD_REF(Key) k, BOOST_FWD_REF(A0) a0)
613	{
614	return table_.try_emplace_unique(
615	boost::forward<Key>(k), boost::unordered::detail::create_emplace_args(
616	boost::forward<A0>(a0)));
617	}
618
619	template <typename Key, typename A0, typename A1>
620	typename boost::enable_if_c<
621	detail::transparent_non_iterable<Key, unordered_map>::value,
622	std::pair<iterator, bool> >::type
623	try_emplace(
624	BOOST_FWD_REF(Key) k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
625	{
626	return table_.try_emplace_unique(boost::forward<Key>(k),
627	boost::unordered::detail::create_emplace_args(
628	boost::forward<A0>(a0), boost::forward<A1>(a1)));
629	}
630
631	template <typename Key, typename A0, typename A1, typename A2>
632	typename boost::enable_if_c<
633	detail::transparent_non_iterable<Key, unordered_map>::value,
634	std::pair<iterator, bool> >::type
635	try_emplace(BOOST_FWD_REF(Key) k, BOOST_FWD_REF(A0) a0,
636	BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
637	{
638	return table_.try_emplace_unique(boost::forward<Key>(k),
639	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
640	boost::forward<A1>(a1), boost::forward<A2>(a2)));
641	}
642
643	// try_emplace(const_iterator hint, key const&, Args&&...)
644
645	template <typename A0>
646	iterator try_emplace(
647	const_iterator hint, key_type const& k, BOOST_FWD_REF(A0) a0)
648	{
649	return table_.try_emplace_hint_unique(
650	hint, k, boost::unordered::detail::create_emplace_args(
651	boost::forward<A0>(a0)));
652	}
653
654	template <typename A0, typename A1>
655	iterator try_emplace(const_iterator hint, key_type const& k,
656	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
657	{
658	return table_.try_emplace_hint_unique(
659	hint, k, boost::unordered::detail::create_emplace_args(
660	boost::forward<A0>(a0), boost::forward<A1>(a1)));
661	}
662
663	template <typename A0, typename A1, typename A2>
664	iterator try_emplace(const_iterator hint, key_type const& k,
665	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
666	{
667	return table_.try_emplace_hint_unique(hint, k,
668	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
669	boost::forward<A1>(a1), boost::forward<A2>(a2)));
670	}
671
672	// try_emplace(const_iterator hint, key&&, Args&&...)
673
674	template <typename A0>
675	iterator try_emplace(
676	const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
677	{
678	return table_.try_emplace_hint_unique(
679	hint, boost::move(k), boost::unordered::detail::create_emplace_args(
680	boost::forward<A0>(a0)));
681	}
682
683	template <typename A0, typename A1>
684	iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
685	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
686	{
687	return table_.try_emplace_hint_unique(hint, boost::move(k),
688	boost::unordered::detail::create_emplace_args(
689	boost::forward<A0>(a0), boost::forward<A1>(a1)));
690	}
691
692	template <typename A0, typename A1, typename A2>
693	iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
694	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
695	{
696	return table_.try_emplace_hint_unique(hint, boost::move(k),
697	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
698	boost::forward<A1>(a1), boost::forward<A2>(a2)));
699	}
700
701	// try_emplace(const_iterator hint, Key&&, Args&&...)
702
703	template <typename Key, typename A0>
704	typename boost::enable_if_c<
705	detail::transparent_non_iterable<Key, unordered_map>::value,
706	iterator>::type
707	try_emplace(
708	const_iterator hint, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(A0) a0)
709	{
710	return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k),
711	boost::unordered::detail::create_emplace_args(
712	boost::forward<A0>(a0)));
713	}
714
715	template <typename Key, typename A0, typename A1>
716	typename boost::enable_if_c<
717	detail::transparent_non_iterable<Key, unordered_map>::value,
718	iterator>::type
719	try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k,
720	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
721	{
722	return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k),
723	boost::unordered::detail::create_emplace_args(
724	boost::forward<A0>(a0), boost::forward<A1>(a1)));
725	}
726
727	template <typename Key, typename A0, typename A1, typename A2>
728	typename boost::enable_if_c<
729	detail::transparent_non_iterable<Key, unordered_map>::value,
730	iterator>::type
731	try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k,
732	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
733	{
734	return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k),
735	boost::unordered::detail::create_emplace_args(boost::forward<A0>(a0),
736	boost::forward<A1>(a1), boost::forward<A2>(a2)));
737	}
738
739	#define BOOST_UNORDERED_TRY_EMPLACE(z, n, _) \
740	\
741	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
742	std::pair<iterator, bool> try_emplace( \
743	key_type const& k, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
744	{ \
745	return table_.try_emplace_unique( \
746	k, boost::unordered::detail::create_emplace_args( \
747	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
748	} \
749	\
750	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
751	std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, \
752	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
753	{ \
754	return table_.try_emplace_unique(boost::move(k), \
755	boost::unordered::detail::create_emplace_args( \
756	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
757	} \
758	\
759	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
760	iterator try_emplace(const_iterator hint, key_type const& k, \
761	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
762	{ \
763	return table_.try_emplace_hint_unique( \
764	hint, k, boost::unordered::detail::create_emplace_args( \
765	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
766	} \
767	\
768	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
769	iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, \
770	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
771	{ \
772	return table_.try_emplace_hint_unique(hint, boost::move(k), \
773	boost::unordered::detail::create_emplace_args( \
774	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
775	}
776
777	BOOST_UNORDERED_TRY_EMPLACE(`1`, `4`, _)
778	BOOST_UNORDERED_TRY_EMPLACE(`1`, `5`, _)
779	BOOST_UNORDERED_TRY_EMPLACE(`1`, `6`, _)
780	BOOST_UNORDERED_TRY_EMPLACE(`1`, `7`, _)
781	BOOST_UNORDERED_TRY_EMPLACE(`1`, `8`, _)
782	BOOST_UNORDERED_TRY_EMPLACE(`1`, `9`, _)
783	BOOST_PP_REPEAT_FROM_TO(`10`, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
784	BOOST_UNORDERED_TRY_EMPLACE, _)
785
786	#undef BOOST_UNORDERED_TRY_EMPLACE
787
788	#endif
789
790	template <class M>
791	std::pair<iterator, bool> insert_or_assign(
792	key_type const& k, BOOST_FWD_REF(M) obj)
793	{
794	return table_.insert_or_assign_unique(k, boost::forward<M>(obj));
795	}
796
797	template <class M>
798	std::pair<iterator, bool> insert_or_assign(
799	BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
800	{
801	return table_.insert_or_assign_unique(
802	boost::move(k), boost::forward<M>(obj));
803	}
804
805	template <class Key, class M>
806	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
807	std::pair<iterator, bool> >::type
808	insert_or_assign(BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj)
809	{
810	return table_.insert_or_assign_unique(
811	boost::forward<Key>(k), boost::forward<M>(obj));
812	}
813
814	template <class M>
815	iterator insert_or_assign(
816	const_iterator, key_type const& k, BOOST_FWD_REF(M) obj)
817	{
818	return table_.insert_or_assign_unique(k, boost::forward<M>(obj)).first;
819	}
820
821	template <class M>
822	iterator insert_or_assign(
823	const_iterator, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
824	{
825	return table_
826	.insert_or_assign_unique(boost::move(k), boost::forward<M>(obj))
827	.first;
828	}
829
830	template <class Key, class M>
831	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
832	iterator>::type
833	insert_or_assign(
834	const_iterator, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj)
835	{
836	return table_
837	.insert_or_assign_unique(
838	boost::forward<Key>(k), boost::forward<M>(obj))
839	.first;
840	}
841
842	iterator erase(iterator);
843	iterator erase(const_iterator);
844	size_type erase(const key_type&);
845	iterator erase(const_iterator, const_iterator);
846
847	template <class Key>
848	typename boost::enable_if_c<
849	detail::transparent_non_iterable<Key, unordered_map>::value,
850	size_type>::type
851	erase(BOOST_FWD_REF(Key) k)
852	{
853	return table_.erase_key_unique_impl(boost::forward<Key>(k));
854	}
855
856	BOOST_UNORDERED_DEPRECATED("Use erase instead")
857	void quick_erase(const_iterator it) { erase(it); }
858	BOOST_UNORDERED_DEPRECATED("Use erase instead")
859	void erase_return_void(const_iterator it) { erase(it); }
860
861	void swap(unordered_map&)
862	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
863	boost::is_nothrow_swappable<H>::value&&
864	boost::is_nothrow_swappable<P>::value);
865	void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
866
867	template <typename H2, typename P2>
868	void merge(boost::unordered_map<K, T, H2, P2, A>& source);
869
870	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
871	template <typename H2, typename P2>
872	void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
873	#endif
874
875	template <typename H2, typename P2>
876	void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
877
878	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
879	template <typename H2, typename P2>
880	void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
881	#endif
882
883	// observers
884
885	hasher hash_function() const;
886	key_equal key_eq() const;
887
888	// lookup
889
890	iterator find(const key_type&);
891	const_iterator find(const key_type&) const;
892
893	template <class Key>
894	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
895	iterator>::type
896	find(const Key& key)
897	{
898	return table_.find(key);
899	}
900
901	template <class Key>
902	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
903	const_iterator>::type
904	find(const Key& key) const
905	{
906	return const_iterator(table_.find(key));
907	}
908
909	template <class CompatibleKey, class CompatibleHash,
910	class CompatiblePredicate>
911	iterator find(CompatibleKey const&, CompatibleHash const&,
912	CompatiblePredicate const&);
913
914	template <class CompatibleKey, class CompatibleHash,
915	class CompatiblePredicate>
916	const_iterator find(CompatibleKey const&, CompatibleHash const&,
917	CompatiblePredicate const&) const;
918
919	bool contains(const key_type& k) const
920	{
921	return table_.find(k) != this->end();
922	}
923
924	template <class Key>
925	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
926	bool>::type
927	contains(const Key& k) const
928	{
929	return table_.find(k) != this->end();
930	}
931
932	size_type count(const key_type&) const;
933
934	template <class Key>
935	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
936	size_type>::type
937	count(const Key& k) const
938	{
939	return (table_.find(k) != this->end() ? `1` : `0`);
940	}
941
942	std::pair<iterator, iterator> equal_range(const key_type&);
943	std::pair<const_iterator, const_iterator> equal_range(
944	const key_type&) const;
945
946	template <class Key>
947	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
948	std::pair<iterator, iterator> >::type
949	equal_range(const Key& key)
950	{
951	iterator first = table_.find(key);
952	iterator last = first;
953	if (last != this->end()) {
954	++last;
955	}
956
957	return std::make_pair(first, last);
958	}
959
960	template <class Key>
961	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
962	std::pair<const_iterator, const_iterator> >::type
963	equal_range(const Key& key) const
964	{
965	iterator first = table_.find(key);
966	iterator last = first;
967	if (last != this->end()) {
968	++last;
969	}
970
971	return std::make_pair(first, last);
972	}
973
974	mapped_type& operator[](const key_type&);
975	mapped_type& operator[](BOOST_RV_REF(key_type));
976
977	template <class Key>
978	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
979	mapped_type&>::type
980	operator[](BOOST_FWD_REF(Key) k);
981
982	mapped_type& at(const key_type&);
983	mapped_type const& at(const key_type&) const;
984
985	template <class Key>
986	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
987	mapped_type&>::type at(BOOST_FWD_REF(Key) k);
988
989	template <class Key>
990	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
991	mapped_type const&>::type at(BOOST_FWD_REF(Key) k) const;
992
993	// bucket interface
994
995	size_type bucket_count() const BOOST_NOEXCEPT
996	{
997	return table_.bucket_count();
998	}
999
1000	size_type max_bucket_count() const BOOST_NOEXCEPT
1001	{
1002	return table_.max_bucket_count();
1003	}
1004
1005	size_type bucket_size(size_type) const;
1006
1007	size_type bucket(const key_type& k) const
1008	{
1009	return table_.hash_to_bucket(table_.hash(k));
1010	}
1011
1012	template <class Key>
1013	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1014	size_type>::type
1015	bucket(BOOST_FWD_REF(Key) k) const
1016	{
1017	return table_.hash_to_bucket(table_.hash(boost::forward<Key>(k)));
1018	}
1019
1020	local_iterator begin(size_type n)
1021	{
1022	return table_.begin(n);
1023	}
1024
1025	const_local_iterator begin(size_type n) const
1026	{
1027	return const_local_iterator(table_.begin(n));
1028	}
1029
1030	local_iterator end(size_type) { return local_iterator(); }
1031	const_local_iterator end(size_type) const
1032	{
1033	return const_local_iterator();
1034	}
1035
1036	const_local_iterator cbegin(size_type n) const
1037	{
1038	return const_local_iterator(table_.begin(n));
1039	}
1040
1041	const_local_iterator cend(size_type) const
1042	{
1043	return const_local_iterator();
1044	}
1045
1046	// hash policy
1047
1048	float load_factor() const BOOST_NOEXCEPT;
1049	float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
1050	void max_load_factor(float) BOOST_NOEXCEPT;
1051	void rehash(size_type);
1052	void reserve(size_type);
1053
1054	#if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
1055	friend bool operator==
1056	<K, T, H, P, A>(unordered_map const&, unordered_map const&);
1057	friend bool operator!=
1058	<K, T, H, P, A>(unordered_map const&, unordered_map const&);
1059	#endif
1060	}; // class template unordered_map
1061
1062	#if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
1063
1064	template <class InputIterator,
1065	class Hash =
1066	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1067	class Pred =
1068	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1069	class Allocator = std::allocator<
1070	boost::unordered::detail::iter_to_alloc_t<InputIterator> >,
1071	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1072	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1073	class = boost::enable_if_t<detail::is_pred_v<Pred> >,
1074	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1075	unordered_map(InputIterator, InputIterator,
1076	std::size_t = boost::unordered::detail::default_bucket_count,
1077	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1078	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
1079	boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred,
1080	Allocator>;
1081
1082	template <class Key, class T,
1083	class Hash = boost::hash<boost::remove_const_t<Key> >,
1084	class Pred = std::equal_to<boost::remove_const_t<Key> >,
1085	class Allocator = std::allocator<std::pair<const Key, T> >,
1086	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1087	class = boost::enable_if_t<detail::is_pred_v<Pred> >,
1088	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1089	unordered_map(std::initializer_list<std::pair<Key, T> >,
1090	std::size_t = boost::unordered::detail::default_bucket_count,
1091	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1092	-> unordered_map<boost::remove_const_t<Key>, T, Hash, Pred, Allocator>;
1093
1094	template <class InputIterator, class Allocator,
1095	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1096	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1097	unordered_map(InputIterator, InputIterator, std::size_t, Allocator)
1098	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
1099	boost::unordered::detail::iter_val_t<InputIterator>,
1100	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1101	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1102	Allocator>;
1103
1104	template <class InputIterator, class Allocator,
1105	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1106	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1107	unordered_map(InputIterator, InputIterator, Allocator)
1108	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
1109	boost::unordered::detail::iter_val_t<InputIterator>,
1110	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1111	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1112	Allocator>;
1113
1114	template <class InputIterator, class Hash, class Allocator,
1115	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1116	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1117	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1118	unordered_map(InputIterator, InputIterator, std::size_t, Hash, Allocator)
1119	-> unordered_map<boost::unordered::detail::iter_key_t<InputIterator>,
1120	boost::unordered::detail::iter_val_t<InputIterator>, Hash,
1121	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1122	Allocator>;
1123
1124	template <class Key, class T, class Allocator,
1125	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1126	unordered_map(std::initializer_list<std::pair<Key, T> >, std::size_t,
1127	Allocator) -> unordered_map<boost::remove_const_t<Key>, T,
1128	boost::hash<boost::remove_const_t<Key> >,
1129	std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1130
1131	template <class Key, class T, class Allocator,
1132	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1133	unordered_map(std::initializer_list<std::pair<Key, T> >, Allocator)
1134	-> unordered_map<boost::remove_const_t<Key>, T,
1135	boost::hash<boost::remove_const_t<Key> >,
1136	std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1137
1138	template <class Key, class T, class Hash, class Allocator,
1139	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1140	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1141	unordered_map(std::initializer_list<std::pair<Key, T> >, std::size_t, Hash,
1142	Allocator) -> unordered_map<boost::remove_const_t<Key>, T, Hash,
1143	std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1144
1145	#endif
1146
1147	template <class K, class T, class H, class P, class A>
1148	class unordered_multimap
1149	{
1150	#if defined(BOOST_UNORDERED_USE_MOVE)
1151	BOOST_COPYABLE_AND_MOVABLE(unordered_multimap)
1152	#endif
1153	template <typename, typename, typename, typename, typename>
1154	friend class unordered_map;
1155
1156	public:
1157	typedef K key_type;
1158	typedef T mapped_type;
1159	typedef std::pair<const K, T> value_type;
1160	typedef typename boost::type_identity<H>::type hasher;
1161	typedef typename boost::type_identity<P>::type key_equal;
1162	typedef typename boost::type_identity<A>::type allocator_type;
1163
1164	private:
1165	typedef boost::unordered::detail::map<A, K, T, H, P> types;
1166	typedef typename types::value_allocator_traits value_allocator_traits;
1167	typedef typename types::table table;
1168
1169	public:
1170	typedef typename value_allocator_traits::pointer pointer;
1171	typedef typename value_allocator_traits::const_pointer const_pointer;
1172
1173	typedef value_type& reference;
1174	typedef value_type const& const_reference;
1175
1176	typedef std::size_t size_type;
1177	typedef std::ptrdiff_t difference_type;
1178
1179	typedef typename table::iterator iterator;
1180	typedef typename table::c_iterator const_iterator;
1181	typedef typename table::l_iterator local_iterator;
1182	typedef typename table::cl_iterator const_local_iterator;
1183	typedef typename types::node_type node_type;
1184
1185	private:
1186	table table_;
1187
1188	public:
1189	// constructors
1190
1191	unordered_multimap();
1192
1193	explicit unordered_multimap(size_type, const hasher& = hasher(),
1194	const key_equal& = key_equal(),
1195	const allocator_type& = allocator_type());
1196
1197	template <class InputIt>
1198	unordered_multimap(InputIt, InputIt,
1199	size_type = boost::unordered::detail::default_bucket_count,
1200	const hasher& = hasher(), const key_equal& = key_equal(),
1201	const allocator_type& = allocator_type());
1202
1203	unordered_multimap(unordered_multimap const&);
1204
1205	#if defined(BOOST_UNORDERED_USE_MOVE) \|\| \
1206	!defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1207	unordered_multimap(BOOST_RV_REF(unordered_multimap) other)
1208	BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
1209	: table_(other.table_, boost::unordered::detail::move_tag ())
1210	{
1211	// The move is done in table_
1212	}
1213	#endif
1214
1215	explicit unordered_multimap(allocator_type const&);
1216
1217	unordered_multimap(unordered_multimap const&, allocator_type const&);
1218
1219	unordered_multimap(
1220	BOOST_RV_REF(unordered_multimap), allocator_type const&);
1221
1222	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1223	unordered_multimap(std::initializer_list<value_type>,
1224	size_type = boost::unordered::detail::default_bucket_count,
1225	const hasher& = hasher(), const key_equal& l = key_equal(),
1226	const allocator_type& = allocator_type());
1227	#endif
1228
1229	explicit unordered_multimap(size_type, const allocator_type&);
1230
1231	explicit unordered_multimap(
1232	size_type, const hasher&, const allocator_type&);
1233
1234	template <class InputIterator>
1235	unordered_multimap(InputIterator, InputIterator, const allocator_type&);
1236
1237	template <class InputIt>
1238	unordered_multimap(InputIt, InputIt, size_type, const allocator_type&);
1239
1240	template <class InputIt>
1241	unordered_multimap(
1242	InputIt, InputIt, size_type, const hasher&, const allocator_type&);
1243
1244	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1245	unordered_multimap(
1246	std::initializer_list<value_type>, const allocator_type&);
1247
1248	unordered_multimap(
1249	std::initializer_list<value_type>, size_type, const allocator_type&);
1250
1251	unordered_multimap(std::initializer_list<value_type>, size_type,
1252	const hasher&, const allocator_type&);
1253	#endif
1254
1255	// Destructor
1256
1257	~unordered_multimap() BOOST_NOEXCEPT;
1258
1259	// Assign
1260
1261	#if defined(BOOST_UNORDERED_USE_MOVE)
1262	unordered_multimap& operator=(BOOST_COPY_ASSIGN_REF(unordered_multimap) x)
1263	{
1264	table_.assign(x.table_, boost::unordered::detail::false_type());
1265	return *this;
1266	}
1267
1268	unordered_multimap& operator=(BOOST_RV_REF(unordered_multimap) x)
1269	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
1270	boost::is_nothrow_move_assignable<H>::value&&
1271	boost::is_nothrow_move_assignable<P>::value)
1272	{
1273	table_.move_assign(x.table_, boost::unordered::detail::false_type());
1274	return *this;
1275	}
1276	#else
1277	unordered_multimap& operator=(unordered_multimap const& x)
1278	{
1279	table_.assign(x.table_, boost::unordered::detail::false_type());
1280	return *this;
1281	}
1282
1283	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1284	unordered_multimap& operator=(unordered_multimap&& x)
1285	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
1286	boost::is_nothrow_move_assignable<H>::value&&
1287	boost::is_nothrow_move_assignable<P>::value)
1288	{
1289	table_.move_assign(x.table_, boost::unordered::detail::false_type());
1290	return *this;
1291	}
1292	#endif
1293	#endif
1294
1295	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1296	unordered_multimap& operator=(std::initializer_list<value_type>);
1297	#endif
1298
1299	allocator_type get_allocator() const BOOST_NOEXCEPT
1300	{
1301	return table_.node_alloc();
1302	}
1303
1304	// iterators
1305
1306	iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
1307
1308	const_iterator begin() const BOOST_NOEXCEPT
1309	{
1310	return const_iterator(table_.begin());
1311	}
1312
1313	iterator end() BOOST_NOEXCEPT { return iterator(); }
1314
1315	const_iterator end() const BOOST_NOEXCEPT { return const_iterator(); }
1316
1317	const_iterator cbegin() const BOOST_NOEXCEPT
1318	{
1319	return const_iterator(table_.begin());
1320	}
1321
1322	const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
1323
1324	// size and capacity
1325
1326	BOOST_ATTRIBUTE_NODISCARD bool empty() const BOOST_NOEXCEPT
1327	{
1328	return table_.size_ == `0`;
1329	}
1330
1331	size_type size() const BOOST_NOEXCEPT { return table_.size_; }
1332
1333	size_type max_size() const BOOST_NOEXCEPT;
1334
1335	// emplace
1336
1337	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1338
1339	template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args)
1340	{
1341	return iterator(table_.emplace_equiv(
1342	boost::unordered::detail::func::construct_node_from_args(
1343	table_.node_alloc(), boost::forward<Args>(args)...)));
1344	}
1345
1346	#else
1347
1348	#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1349
1350	// 0 argument emplace requires special treatment in case
1351	// the container is instantiated with a value type that
1352	// doesn't have a default constructor.
1353
1354	iterator emplace(boost::unordered::detail::empty_emplace =
1355	boost::unordered::detail::empty_emplace(),
1356	value_type v = value_type())
1357	{
1358	return this->emplace(boost::move(v));
1359	}
1360
1361	#endif
1362
1363	template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0)
1364	{
1365	return iterator(table_.emplace_equiv(
1366	boost::unordered::detail::func::construct_node_from_args(
1367	table_.node_alloc(), boost::unordered::detail::create_emplace_args(
1368	boost::forward<A0>(a0)))));
1369	}
1370
1371	template <typename A0, typename A1>
1372	iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
1373	{
1374	return iterator(table_.emplace_equiv(
1375	boost::unordered::detail::func::construct_node_from_args(
1376	table_.node_alloc(),
1377	boost::unordered::detail::create_emplace_args(
1378	boost::forward<A0>(a0), boost::forward<A1>(a1)))));
1379	}
1380
1381	template <typename A0, typename A1, typename A2>
1382	iterator emplace(
1383	BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1384	{
1385	return iterator(table_.emplace_equiv(
1386	boost::unordered::detail::func::construct_node_from_args(
1387	table_.node_alloc(),
1388	boost::unordered::detail::create_emplace_args(
1389	boost::forward<A0>(a0), boost::forward<A1>(a1),
1390	boost::forward<A2>(a2)))));
1391	}
1392
1393	#endif
1394
1395	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1396
1397	template <class... Args>
1398	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
1399	{
1400	return iterator(table_.emplace_hint_equiv(
1401	hint, boost::unordered::detail::func::construct_node_from_args(
1402	table_.node_alloc(), boost::forward<Args>(args)...)));
1403	}
1404
1405	#else
1406
1407	#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1408
1409	iterator emplace_hint(const_iterator hint,
1410	boost::unordered::detail::empty_emplace =
1411	boost::unordered::detail::empty_emplace(),
1412	value_type v = value_type())
1413	{
1414	return this->emplace_hint(hint, boost::move(v));
1415	}
1416
1417	#endif
1418
1419	template <typename A0>
1420	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
1421	{
1422	return iterator(table_.emplace_hint_equiv(hint,
1423	boost::unordered::detail::func::construct_node_from_args(
1424	table_.node_alloc(), boost::unordered::detail::create_emplace_args(
1425	boost::forward<A0>(a0)))));
1426	}
1427
1428	template <typename A0, typename A1>
1429	iterator emplace_hint(
1430	const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
1431	{
1432	return iterator(table_.emplace_hint_equiv(
1433	hint, boost::unordered::detail::func::construct_node_from_args(
1434	table_.node_alloc(),
1435	boost::unordered::detail::create_emplace_args(
1436	boost::forward<A0>(a0), boost::forward<A1>(a1)))));
1437	}
1438
1439	template <typename A0, typename A1, typename A2>
1440	iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
1441	BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1442	{
1443	return iterator(table_.emplace_hint_equiv(
1444	hint, boost::unordered::detail::func::construct_node_from_args(
1445	table_.node_alloc(),
1446	boost::unordered::detail::create_emplace_args(
1447	boost::forward<A0>(a0), boost::forward<A1>(a1),
1448	boost::forward<A2>(a2)))));
1449	}
1450
1451	#endif
1452
1453	#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1454
1455	#define BOOST_UNORDERED_EMPLACE(z, n, _) \
1456	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1457	iterator emplace(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
1458	{ \
1459	return iterator(table_.emplace_equiv( \
1460	boost::unordered::detail::func::construct_node_from_args( \
1461	table_.node_alloc(), \
1462	boost::unordered::detail::create_emplace_args( \
1463	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
1464	} \
1465	\
1466	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1467	iterator emplace_hint( \
1468	const_iterator hint, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
1469	{ \
1470	return iterator(table_.emplace_hint_equiv( \
1471	hint, boost::unordered::detail::func::construct_node_from_args( \
1472	table_.node_alloc(), \
1473	boost::unordered::detail::create_emplace_args( \
1474	BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
1475	}
1476
1477	BOOST_UNORDERED_EMPLACE(`1`, `4`, _)
1478	BOOST_UNORDERED_EMPLACE(`1`, `5`, _)
1479	BOOST_UNORDERED_EMPLACE(`1`, `6`, _)
1480	BOOST_UNORDERED_EMPLACE(`1`, `7`, _)
1481	BOOST_UNORDERED_EMPLACE(`1`, `8`, _)
1482	BOOST_UNORDERED_EMPLACE(`1`, `9`, _)
1483	BOOST_PP_REPEAT_FROM_TO(`10`, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
1484	BOOST_UNORDERED_EMPLACE, _)
1485
1486	#undef BOOST_UNORDERED_EMPLACE
1487
1488	#endif
1489
1490	iterator insert(value_type const& x) { return this->emplace(x); }
1491
1492	iterator insert(BOOST_RV_REF(value_type) x)
1493	{
1494	return this->emplace(boost::move(x));
1495	}
1496
1497	template <class P2>
1498	typename boost::enable_if<
1499	boost::is_constructible<value_type, BOOST_RV_REF(P2)>,
1500	iterator>::type insert(BOOST_RV_REF(P2) obj)
1501	{
1502	return this->emplace(boost::forward<P2>(obj));
1503	}
1504
1505	iterator insert(const_iterator hint, value_type const& x)
1506	{
1507	return this->emplace_hint(hint, x);
1508	}
1509
1510	iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
1511	{
1512	return this->emplace_hint(hint, boost::move(x));
1513	}
1514
1515	template <class P2>
1516	typename boost::enable_if<
1517	boost::is_constructible<value_type, BOOST_RV_REF(P2)>,
1518	iterator>::type
1519	insert(const_iterator hint, BOOST_RV_REF(P2) obj)
1520	{
1521	return this->emplace_hint(hint, boost::forward<P2>(obj));
1522	}
1523
1524	template <class InputIt> void insert(InputIt, InputIt);
1525
1526	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1527	void insert(std::initializer_list<value_type>);
1528	#endif
1529
1530	// extract
1531
1532	node_type extract(const_iterator position)
1533	{
1534	return node_type(
1535	table_.extract_by_iterator_equiv(position), table_.node_alloc());
1536	}
1537
1538	node_type extract(const key_type& k)
1539	{
1540	return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
1541	}
1542
1543	template <class Key>
1544	typename boost::enable_if_c<
1545	detail::transparent_non_iterable<Key, unordered_multimap>::value,
1546	node_type>::type
1547	extract(const Key& k)
1548	{
1549	return node_type(table_.extract_by_key_impl(k), table_.node_alloc());
1550	}
1551
1552	iterator insert(BOOST_RV_REF(node_type) np)
1553	{
1554	return table_.move_insert_node_type_equiv(np);
1555	}
1556
1557	iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
1558	{
1559	return table_.move_insert_node_type_with_hint_equiv(hint, np);
1560	}
1561
1562	#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) \|\| \
1563	(BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
1564	private:
1565	// Note: Use r-value node_type to insert.
1566	iterator insert(node_type&);
1567	iterator insert(const_iterator, node_type& np);
1568
1569	public:
1570	#endif
1571
1572	iterator erase(iterator);
1573	iterator erase(const_iterator);
1574	size_type erase(const key_type&);
1575	iterator erase(const_iterator, const_iterator);
1576
1577	template <class Key>
1578	typename boost::enable_if_c<
1579	detail::transparent_non_iterable<Key, unordered_multimap>::value,
1580	size_type>::type
1581	erase(BOOST_FWD_REF(Key) k)
1582	{
1583	return table_.erase_key_equiv_impl(boost::forward<Key>(k));
1584	}
1585
1586	BOOST_UNORDERED_DEPRECATED("Use erase instead")
1587	void quick_erase(const_iterator it) { erase(it); }
1588	BOOST_UNORDERED_DEPRECATED("Use erase instead")
1589	void erase_return_void(const_iterator it) { erase(it); }
1590
1591	void swap(unordered_multimap&)
1592	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
1593	boost::is_nothrow_swappable<H>::value&&
1594	boost::is_nothrow_swappable<P>::value);
1595	void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
1596
1597	template <typename H2, typename P2>
1598	void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
1599
1600	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1601	template <typename H2, typename P2>
1602	void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
1603	#endif
1604
1605	template <typename H2, typename P2>
1606	void merge(boost::unordered_map<K, T, H2, P2, A>& source);
1607
1608	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1609	template <typename H2, typename P2>
1610	void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
1611	#endif
1612
1613	// observers
1614
1615	hasher hash_function() const;
1616	key_equal key_eq() const;
1617
1618	// lookup
1619
1620	iterator find(const key_type&);
1621	const_iterator find(const key_type&) const;
1622
1623	template <class Key>
1624	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1625	iterator>::type
1626	find(const Key& key)
1627	{
1628	return table_.find(key);
1629	}
1630
1631	template <class Key>
1632	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1633	const_iterator>::type
1634	find(const Key& key) const
1635	{
1636	return const_iterator(table_.find(key));
1637	}
1638
1639	template <class CompatibleKey, class CompatibleHash,
1640	class CompatiblePredicate>
1641	iterator find(CompatibleKey const&, CompatibleHash const&,
1642	CompatiblePredicate const&);
1643
1644	template <class CompatibleKey, class CompatibleHash,
1645	class CompatiblePredicate>
1646	const_iterator find(CompatibleKey const&, CompatibleHash const&,
1647	CompatiblePredicate const&) const;
1648
1649	bool contains(key_type const& k) const
1650	{
1651	return table_.find(k) != this->end();
1652	}
1653
1654	template <class Key>
1655	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1656	bool>::type
1657	contains(const Key& k) const
1658	{
1659	return table_.find(k) != this->end();
1660	}
1661
1662	size_type count(const key_type&) const;
1663
1664	template <class Key>
1665	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1666	size_type>::type
1667	count(const Key& k) const
1668	{
1669	return table_.group_count(k);
1670	}
1671
1672	std::pair<iterator, iterator> equal_range(const key_type&);
1673	std::pair<const_iterator, const_iterator> equal_range(
1674	const key_type&) const;
1675
1676	template <class Key>
1677	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1678	std::pair<iterator, iterator> >::type
1679	equal_range(const Key& key)
1680	{
1681	iterator p = table_.find(key);
1682	return std::make_pair(p, table_.next_group(key, p));
1683	}
1684
1685	template <class Key>
1686	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1687	std::pair<const_iterator, const_iterator> >::type
1688	equal_range(const Key& key) const
1689	{
1690	iterator p = table_.find(key);
1691	return std::make_pair(
1692	const_iterator(p), const_iterator(table_.next_group(key, p)));
1693	}
1694
1695	// bucket interface
1696
1697	size_type bucket_count() const BOOST_NOEXCEPT
1698	{
1699	return table_.bucket_count();
1700	}
1701
1702	size_type max_bucket_count() const BOOST_NOEXCEPT
1703	{
1704	return table_.max_bucket_count();
1705	}
1706
1707	size_type bucket_size(size_type) const;
1708
1709	size_type bucket(const key_type& k) const
1710	{
1711	return table_.hash_to_bucket(table_.hash(k));
1712	}
1713
1714	template <class Key>
1715	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
1716	size_type>::type
1717	bucket(BOOST_FWD_REF(Key) k) const
1718	{
1719	return table_.hash_to_bucket(table_.hash(boost::forward<Key>(k)));
1720	}
1721
1722	local_iterator begin(size_type n)
1723	{
1724	return local_iterator(table_.begin(n));
1725	}
1726
1727	const_local_iterator begin(size_type n) const
1728	{
1729	return const_local_iterator(table_.begin(n));
1730	}
1731
1732	local_iterator end(size_type) { return local_iterator(); }
1733
1734	const_local_iterator end(size_type) const
1735	{
1736	return const_local_iterator();
1737	}
1738
1739	const_local_iterator cbegin(size_type n) const
1740	{
1741	return const_local_iterator(table_.begin(n));
1742	}
1743
1744	const_local_iterator cend(size_type) const
1745	{
1746	return const_local_iterator();
1747	}
1748
1749	// hash policy
1750
1751	float load_factor() const BOOST_NOEXCEPT;
1752	float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
1753	void max_load_factor(float) BOOST_NOEXCEPT;
1754	void rehash(size_type);
1755	void reserve(size_type);
1756
1757	#if !BOOST_WORKAROUND(BOOST_BORLANDC, < 0x0582)
1758	friend bool operator==
1759	<K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1760	friend bool operator!=
1761	<K, T, H, P, A>(unordered_multimap const&, unordered_multimap const&);
1762	#endif
1763	}; // class template unordered_multimap
1764
1765	#if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
1766
1767	template <class InputIterator,
1768	class Hash =
1769	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1770	class Pred =
1771	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1772	class Allocator = std::allocator<
1773	boost::unordered::detail::iter_to_alloc_t<InputIterator> >,
1774	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1775	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1776	class = boost::enable_if_t<detail::is_pred_v<Pred> >,
1777	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1778	unordered_multimap(InputIterator, InputIterator,
1779	std::size_t = boost::unordered::detail::default_bucket_count,
1780	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1781	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1782	boost::unordered::detail::iter_val_t<InputIterator>, Hash, Pred,
1783	Allocator>;
1784
1785	template <class Key, class T,
1786	class Hash = boost::hash<boost::remove_const_t<Key> >,
1787	class Pred = std::equal_to<boost::remove_const_t<Key> >,
1788	class Allocator = std::allocator<std::pair<const Key, T> >,
1789	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1790	class = boost::enable_if_t<detail::is_pred_v<Pred> >,
1791	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1792	unordered_multimap(std::initializer_list<std::pair<Key, T> >,
1793	std::size_t = boost::unordered::detail::default_bucket_count,
1794	Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1795	-> unordered_multimap<boost::remove_const_t<Key>, T, Hash, Pred,
1796	Allocator>;
1797
1798	template <class InputIterator, class Allocator,
1799	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1800	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1801	unordered_multimap(InputIterator, InputIterator, std::size_t, Allocator)
1802	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1803	boost::unordered::detail::iter_val_t<InputIterator>,
1804	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1805	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1806	Allocator>;
1807
1808	template <class InputIterator, class Allocator,
1809	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1810	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1811	unordered_multimap(InputIterator, InputIterator, Allocator)
1812	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1813	boost::unordered::detail::iter_val_t<InputIterator>,
1814	boost::hash<boost::unordered::detail::iter_key_t<InputIterator> >,
1815	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1816	Allocator>;
1817
1818	template <class InputIterator, class Hash, class Allocator,
1819	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1820	class = boost::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1821	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1822	unordered_multimap(
1823	InputIterator, InputIterator, std::size_t, Hash, Allocator)
1824	-> unordered_multimap<boost::unordered::detail::iter_key_t<InputIterator>,
1825	boost::unordered::detail::iter_val_t<InputIterator>, Hash,
1826	std::equal_to<boost::unordered::detail::iter_key_t<InputIterator> >,
1827	Allocator>;
1828
1829	template <class Key, class T, class Allocator,
1830	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1831	unordered_multimap(std::initializer_list<std::pair<Key, T> >, std::size_t,
1832	Allocator) -> unordered_multimap<boost::remove_const_t<Key>, T,
1833	boost::hash<boost::remove_const_t<Key> >,
1834	std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1835
1836	template <class Key, class T, class Allocator,
1837	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1838	unordered_multimap(std::initializer_list<std::pair<Key, T> >, Allocator)
1839	-> unordered_multimap<boost::remove_const_t<Key>, T,
1840	boost::hash<boost::remove_const_t<Key> >,
1841	std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1842
1843	template <class Key, class T, class Hash, class Allocator,
1844	class = boost::enable_if_t<detail::is_hash_v<Hash> >,
1845	class = boost::enable_if_t<detail::is_allocator_v<Allocator> > >
1846	unordered_multimap(std::initializer_list<std::pair<Key, T> >, std::size_t,
1847	Hash, Allocator) -> unordered_multimap<boost::remove_const_t<Key>, T,
1848	Hash, std::equal_to<boost::remove_const_t<Key> >, Allocator>;
1849
1850	#endif
1851
1852	////////////////////////////////////////////////////////////////////////////
1853
1854	template <class K, class T, class H, class P, class A>
1855	unordered_map<K, T, H, P, A>::unordered_map()
1856	{
1857	}
1858
1859	template <class K, class T, class H, class P, class A>
1860	unordered_map<K, T, H, P, A>::unordered_map(size_type n, const hasher& hf,
1861	const key_equal& eql, const allocator_type& a)
1862	: table_(n, hf, eql, a)
1863	{
1864	}
1865
1866	template <class K, class T, class H, class P, class A>
1867	template <class InputIt>
1868	unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1869	size_type n, const hasher& hf, const key_equal& eql,
1870	const allocator_type& a)
1871	: table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
1872	{
1873	this->insert(f, l);
1874	}
1875
1876	template <class K, class T, class H, class P, class A>
1877	unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
1878	: table_(other.table_,
1879	unordered_map::value_allocator_traits::
1880	select_on_container_copy_construction(other.get_allocator()))
1881	{
1882	if (other.size()) {
1883	table_.copy_buckets(
1884	other.table_, boost::unordered::detail::true_type());
1885	}
1886	}
1887
1888	template <class K, class T, class H, class P, class A>
1889	unordered_map<K, T, H, P, A>::unordered_map(allocator_type const& a)
1890	: table_(boost::unordered::detail::default_bucket_count, hasher(),
1891	key_equal(), a)
1892	{
1893	}
1894
1895	template <class K, class T, class H, class P, class A>
1896	unordered_map<K, T, H, P, A>::unordered_map(
1897	unordered_map const& other, allocator_type const& a)
1898	: table_(other.table_, a)
1899	{
1900	if (other.table_.size_) {
1901	table_.copy_buckets(
1902	other.table_, boost::unordered::detail::true_type());
1903	}
1904	}
1905
1906	template <class K, class T, class H, class P, class A>
1907	unordered_map<K, T, H, P, A>::unordered_map(
1908	BOOST_RV_REF(unordered_map) other, allocator_type const& a)
1909	: table_(other.table_, a, boost::unordered::detail::move_tag ())
1910	{
1911	table_.move_construct_buckets(other.table_);
1912	}
1913
1914	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1915
1916	template <class K, class T, class H, class P, class A>
1917	unordered_map<K, T, H, P, A>::unordered_map(
1918	std::initializer_list<value_type> list, size_type n, const hasher& hf,
1919	const key_equal& eql, const allocator_type& a)
1920	: table_(
1921	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1922	hf, eql, a)
1923	{
1924	this->insert(list.begin(), list.end());
1925	}
1926
1927	#endif
1928
1929	template <class K, class T, class H, class P, class A>
1930	unordered_map<K, T, H, P, A>::unordered_map(
1931	size_type n, const allocator_type& a)
1932	: table_(n, hasher(), key_equal(), a)
1933	{
1934	}
1935
1936	template <class K, class T, class H, class P, class A>
1937	unordered_map<K, T, H, P, A>::unordered_map(
1938	size_type n, const hasher& hf, const allocator_type& a)
1939	: table_(n, hf, key_equal(), a)
1940	{
1941	}
1942
1943	template <class K, class T, class H, class P, class A>
1944	template <class InputIterator>
1945	unordered_map<K, T, H, P, A>::unordered_map(
1946	InputIterator f, InputIterator l, const allocator_type& a)
1947	: table_(boost::unordered::detail::initial_size(
1948	f, l, detail::default_bucket_count),
1949	hasher(), key_equal(), a)
1950	{
1951	this->insert(f, l);
1952	}
1953
1954	template <class K, class T, class H, class P, class A>
1955	template <class InputIt>
1956	unordered_map<K, T, H, P, A>::unordered_map(
1957	InputIt f, InputIt l, size_type n, const allocator_type& a)
1958	: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
1959	key_equal(), a)
1960	{
1961	this->insert(f, l);
1962	}
1963
1964	template <class K, class T, class H, class P, class A>
1965	template <class InputIt>
1966	unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l,
1967	size_type n, const hasher& hf, const allocator_type& a)
1968	: table_(
1969	boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
1970	{
1971	this->insert(f, l);
1972	}
1973
1974	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1975
1976	template <class K, class T, class H, class P, class A>
1977	unordered_map<K, T, H, P, A>::unordered_map(
1978	std::initializer_list<value_type> list, const allocator_type& a)
1979	: table_(boost::unordered::detail::initial_size(
1980	list.begin(), list.end(), detail::default_bucket_count),
1981	hasher(), key_equal(), a)
1982	{
1983	this->insert(list.begin(), list.end());
1984	}
1985
1986	template <class K, class T, class H, class P, class A>
1987	unordered_map<K, T, H, P, A>::unordered_map(
1988	std::initializer_list<value_type> list, size_type n,
1989	const allocator_type& a)
1990	: table_(
1991	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
1992	hasher(), key_equal(), a)
1993	{
1994	this->insert(list.begin(), list.end());
1995	}
1996
1997	template <class K, class T, class H, class P, class A>
1998	unordered_map<K, T, H, P, A>::unordered_map(
1999	std::initializer_list<value_type> list, size_type n, const hasher& hf,
2000	const allocator_type& a)
2001	: table_(
2002	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
2003	hf, key_equal(), a)
2004	{
2005	this->insert(list.begin(), list.end());
2006	}
2007
2008	#endif
2009
2010	template <class K, class T, class H, class P, class A>
2011	unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT
2012	{
2013	}
2014
2015	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2016
2017	template <class K, class T, class H, class P, class A>
2018	unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=(
2019	std::initializer_list<value_type> list)
2020	{
2021	this->clear();
2022	this->insert(list.begin(), list.end());
2023	return *this;
2024	}
2025
2026	#endif
2027
2028	// size and capacity
2029
2030	template <class K, class T, class H, class P, class A>
2031	std::size_t unordered_map<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
2032	{
2033	using namespace std;
2034
2035	// size <= mlf_ count*
2036	return boost::unordered::detail::double_to_size(
2037	f: ceil(x: static_cast<double>(table_.mlf_) *
2038	static_cast<double>(table_.max_bucket_count()))) -
2039	`1`;
2040	}
2041
2042	// modifiers
2043
2044	template <class K, class T, class H, class P, class A>
2045	template <class InputIt>
2046	void unordered_map<K, T, H, P, A>::insert(InputIt first, InputIt last)
2047	{
2048	if (first != last) {
2049	table_.insert_range_unique(
2050	table::extractor::extract(*first), first, last);
2051	}
2052	}
2053
2054	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2055	template <class K, class T, class H, class P, class A>
2056	void unordered_map<K, T, H, P, A>::insert(
2057	std::initializer_list<value_type> list)
2058	{
2059	this->insert(list.begin(), list.end());
2060	}
2061	#endif
2062
2063	template <class K, class T, class H, class P, class A>
2064	typename unordered_map<K, T, H, P, A>::iterator
2065	unordered_map<K, T, H, P, A>::erase(iterator position)
2066	{
2067	return table_.erase_node(position);
2068	}
2069
2070	template <class K, class T, class H, class P, class A>
2071	typename unordered_map<K, T, H, P, A>::iterator
2072	unordered_map<K, T, H, P, A>::erase(const_iterator position)
2073	{
2074	return table_.erase_node(position);
2075	}
2076
2077	template <class K, class T, class H, class P, class A>
2078	typename unordered_map<K, T, H, P, A>::size_type
2079	unordered_map<K, T, H, P, A>::erase(const key_type& k)
2080	{
2081	return table_.erase_key_unique_impl(k);
2082	}
2083
2084	template <class K, class T, class H, class P, class A>
2085	typename unordered_map<K, T, H, P, A>::iterator
2086	unordered_map<K, T, H, P, A>::erase(
2087	const_iterator first, const_iterator last)
2088	{
2089	return table_.erase_nodes_range(first, last);
2090	}
2091
2092	template <class K, class T, class H, class P, class A>
2093	void unordered_map<K, T, H, P, A>::swap(unordered_map& other)
2094	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
2095	boost::is_nothrow_swappable<H>::value&&
2096	boost::is_nothrow_swappable<P>::value)
2097	{
2098	table_.swap(other.table_);
2099	}
2100
2101	template <class K, class T, class H, class P, class A>
2102	template <typename H2, typename P2>
2103	void unordered_map<K, T, H, P, A>::merge(
2104	boost::unordered_map<K, T, H2, P2, A>& source)
2105	{
2106	table_.merge_unique(source.table_);
2107	}
2108
2109	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2110	template <class K, class T, class H, class P, class A>
2111	template <typename H2, typename P2>
2112	void unordered_map<K, T, H, P, A>::merge(
2113	boost::unordered_map<K, T, H2, P2, A>&& source)
2114	{
2115	table_.merge_unique(source.table_);
2116	}
2117	#endif
2118
2119	template <class K, class T, class H, class P, class A>
2120	template <typename H2, typename P2>
2121	void unordered_map<K, T, H, P, A>::merge(
2122	boost::unordered_multimap<K, T, H2, P2, A>& source)
2123	{
2124	table_.merge_unique(source.table_);
2125	}
2126
2127	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2128	template <class K, class T, class H, class P, class A>
2129	template <typename H2, typename P2>
2130	void unordered_map<K, T, H, P, A>::merge(
2131	boost::unordered_multimap<K, T, H2, P2, A>&& source)
2132	{
2133	table_.merge_unique(source.table_);
2134	}
2135	#endif
2136
2137	// observers
2138
2139	template <class K, class T, class H, class P, class A>
2140	typename unordered_map<K, T, H, P, A>::hasher
2141	unordered_map<K, T, H, P, A>::hash_function() const
2142	{
2143	return table_.hash_function();
2144	}
2145
2146	template <class K, class T, class H, class P, class A>
2147	typename unordered_map<K, T, H, P, A>::key_equal
2148	unordered_map<K, T, H, P, A>::key_eq() const
2149	{
2150	return table_.key_eq();
2151	}
2152
2153	// lookup
2154
2155	template <class K, class T, class H, class P, class A>
2156	typename unordered_map<K, T, H, P, A>::iterator
2157	unordered_map<K, T, H, P, A>::find(const key_type& k)
2158	{
2159	return iterator(table_.find(k));
2160	}
2161
2162	template <class K, class T, class H, class P, class A>
2163	typename unordered_map<K, T, H, P, A>::const_iterator
2164	unordered_map<K, T, H, P, A>::find(const key_type& k) const
2165	{
2166	return const_iterator(table_.find(k));
2167	}
2168
2169	template <class K, class T, class H, class P, class A>
2170	template <class CompatibleKey, class CompatibleHash,
2171	class CompatiblePredicate>
2172	typename unordered_map<K, T, H, P, A>::iterator
2173	unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
2174	CompatibleHash const& hash, CompatiblePredicate const& eq)
2175	{
2176	return table_.transparent_find(k, hash, eq);
2177	}
2178
2179	template <class K, class T, class H, class P, class A>
2180	template <class CompatibleKey, class CompatibleHash,
2181	class CompatiblePredicate>
2182	typename unordered_map<K, T, H, P, A>::const_iterator
2183	unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
2184	CompatibleHash const& hash, CompatiblePredicate const& eq) const
2185	{
2186	return table_.transparent_find(k, hash, eq);
2187	}
2188
2189	template <class K, class T, class H, class P, class A>
2190	typename unordered_map<K, T, H, P, A>::size_type
2191	unordered_map<K, T, H, P, A>::count(const key_type& k) const
2192	{
2193	return table_.find_node(k) ? `1` : `0`;
2194	}
2195
2196	template <class K, class T, class H, class P, class A>
2197	std::pair<typename unordered_map<K, T, H, P, A>::iterator,
2198	typename unordered_map<K, T, H, P, A>::iterator>
2199	unordered_map<K, T, H, P, A>::equal_range(const key_type& k)
2200	{
2201	iterator first = table_.find(k);
2202	iterator second = first;
2203	if (second != this->end()) {
2204	++second;
2205	}
2206	return std::make_pair(first, second);
2207	}
2208
2209	template <class K, class T, class H, class P, class A>
2210	std::pair<typename unordered_map<K, T, H, P, A>::const_iterator,
2211	typename unordered_map<K, T, H, P, A>::const_iterator>
2212	unordered_map<K, T, H, P, A>::equal_range(const key_type& k) const
2213	{
2214	iterator first = table_.find(k);
2215	iterator second = first;
2216	if (second != this->end()) {
2217	++second;
2218	}
2219	return std::make_pair(const_iterator(first), const_iterator(second));
2220	}
2221
2222	template <class K, class T, class H, class P, class A>
2223	typename unordered_map<K, T, H, P, A>::mapped_type&
2224	unordered_map<K, T, H, P, A>::operator[](const key_type& k)
2225	{
2226	return table_.try_emplace_unique(k).first->second;
2227	}
2228
2229	template <class K, class T, class H, class P, class A>
2230	typename unordered_map<K, T, H, P, A>::mapped_type&
2231	unordered_map<K, T, H, P, A>::operator[](BOOST_RV_REF(key_type) k)
2232	{
2233	return table_.try_emplace_unique(boost::move(k)).first->second;
2234	}
2235
2236	template <class K, class T, class H, class P, class A>
2237	template <class Key>
2238	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
2239	typename unordered_map<K, T, H, P, A>::mapped_type&>::type
2240	unordered_map<K, T, H, P, A>::operator[](BOOST_FWD_REF(Key) k)
2241	{
2242	return table_.try_emplace_unique(boost::forward<Key>(k)).first->second;
2243	}
2244
2245	template <class K, class T, class H, class P, class A>
2246	typename unordered_map<K, T, H, P, A>::mapped_type&
2247	unordered_map<K, T, H, P, A>::at(const key_type& k)
2248	{
2249	typedef typename table::node_pointer node_pointer;
2250
2251	if (table_.size_) {
2252	node_pointer p = table_.find_node(k);
2253	if (p)
2254	return p->value().second;
2255	}
2256
2257	boost::throw_exception(
2258	e: std::out_of_range ("Unable to find key in unordered_map."));
2259	}
2260
2261	template <class K, class T, class H, class P, class A>
2262	typename unordered_map<K, T, H, P, A>::mapped_type const&
2263	unordered_map<K, T, H, P, A>::at(const key_type& k) const
2264	{
2265	typedef typename table::node_pointer node_pointer;
2266
2267	if (table_.size_) {
2268	node_pointer p = table_.find_node(k);
2269	if (p)
2270	return p->value().second;
2271	}
2272
2273	boost::throw_exception(
2274	e: std::out_of_range ("Unable to find key in unordered_map."));
2275	}
2276
2277	template <class K, class T, class H, class P, class A>
2278	template <class Key>
2279	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
2280	typename unordered_map<K, T, H, P, A>::mapped_type&>::type
2281	unordered_map<K, T, H, P, A>::at(BOOST_FWD_REF(Key) k)
2282	{
2283	typedef typename table::node_pointer node_pointer;
2284
2285	if (table_.size_) {
2286	node_pointer p = table_.find_node(boost::forward<Key>(k));
2287	if (p)
2288	return p->value().second;
2289	}
2290
2291	boost::throw_exception(
2292	e: std::out_of_range ("Unable to find key in unordered_map."));
2293	}
2294
2295	template <class K, class T, class H, class P, class A>
2296	template <class Key>
2297	typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
2298	typename unordered_map<K, T, H, P, A>::mapped_type const&>::type
2299	unordered_map<K, T, H, P, A>::at(BOOST_FWD_REF(Key) k) const
2300	{
2301	typedef typename table::node_pointer node_pointer;
2302
2303	if (table_.size_) {
2304	node_pointer p = table_.find_node(boost::forward<Key>(k));
2305	if (p)
2306	return p->value().second;
2307	}
2308
2309	boost::throw_exception(
2310	e: std::out_of_range ("Unable to find key in unordered_map."));
2311	}
2312
2313	template <class K, class T, class H, class P, class A>
2314	typename unordered_map<K, T, H, P, A>::size_type
2315	unordered_map<K, T, H, P, A>::bucket_size(size_type n) const
2316	{
2317	return table_.bucket_size(n);
2318	}
2319
2320	// hash policy
2321
2322	template <class K, class T, class H, class P, class A>
2323	float unordered_map<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
2324	{
2325	if (table_.size_ == `0`) {
2326	return `0.0f`;
2327	}
2328
2329	BOOST_ASSERT(table_.bucket_count() != `0`);
2330	return static_cast<float>(table_.size_) /
2331	static_cast<float>(table_.bucket_count());
2332	}
2333
2334	template <class K, class T, class H, class P, class A>
2335	void unordered_map<K, T, H, P, A>::max_load_factor(float m) BOOST_NOEXCEPT
2336	{
2337	table_.max_load_factor(m);
2338	}
2339
2340	template <class K, class T, class H, class P, class A>
2341	void unordered_map<K, T, H, P, A>::rehash(size_type n)
2342	{
2343	table_.rehash(n);
2344	}
2345
2346	template <class K, class T, class H, class P, class A>
2347	void unordered_map<K, T, H, P, A>::reserve(size_type n)
2348	{
2349	table_.reserve(n);
2350	}
2351
2352	template <class K, class T, class H, class P, class A>
2353	inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
2354	unordered_map<K, T, H, P, A> const& m2)
2355	{
2356	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2357	struct dummy
2358	{
2359	unordered_map<K, T, H, P, A> x;
2360	};
2361	#endif
2362	return m1.table_.equals_unique(m2.table_);
2363	}
2364
2365	template <class K, class T, class H, class P, class A>
2366	inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
2367	unordered_map<K, T, H, P, A> const& m2)
2368	{
2369	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2370	struct dummy
2371	{
2372	unordered_map<K, T, H, P, A> x;
2373	};
2374	#endif
2375	return !m1.table_.equals_unique(m2.table_);
2376	}
2377
2378	template <class K, class T, class H, class P, class A>
2379	inline void swap(
2380	unordered_map<K, T, H, P, A>& m1, unordered_map<K, T, H, P, A>& m2)
2381	BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
2382	{
2383	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2384	struct dummy
2385	{
2386	unordered_map<K, T, H, P, A> x;
2387	};
2388	#endif
2389	m1.swap(m2);
2390	}
2391
2392	template <class K, class T, class H, class P, class A, class Predicate>
2393	typename unordered_map<K, T, H, P, A>::size_type erase_if(
2394	unordered_map<K, T, H, P, A>& c, Predicate pred)
2395	{
2396	return detail::erase_if(c, pred);
2397	}
2398
2399	////////////////////////////////////////////////////////////////////////////
2400
2401	template <class K, class T, class H, class P, class A>
2402	unordered_multimap<K, T, H, P, A>::unordered_multimap()
2403	{
2404	}
2405
2406	template <class K, class T, class H, class P, class A>
2407	unordered_multimap<K, T, H, P, A>::unordered_multimap(size_type n,
2408	const hasher& hf, const key_equal& eql, const allocator_type& a)
2409	: table_(n, hf, eql, a)
2410	{
2411	}
2412
2413	template <class K, class T, class H, class P, class A>
2414	template <class InputIt>
2415	unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
2416	size_type n, const hasher& hf, const key_equal& eql,
2417	const allocator_type& a)
2418	: table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
2419	{
2420	this->insert(f, l);
2421	}
2422
2423	template <class K, class T, class H, class P, class A>
2424	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2425	unordered_multimap const& other)
2426	: table_(other.table_,
2427	unordered_multimap::value_allocator_traits::
2428	select_on_container_copy_construction(other.get_allocator()))
2429	{
2430	if (other.table_.size_) {
2431	table_.copy_buckets(
2432	other.table_, boost::unordered::detail::false_type());
2433	}
2434	}
2435
2436	template <class K, class T, class H, class P, class A>
2437	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2438	allocator_type const& a)
2439	: table_(boost::unordered::detail::default_bucket_count, hasher(),
2440	key_equal(), a)
2441	{
2442	}
2443
2444	template <class K, class T, class H, class P, class A>
2445	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2446	unordered_multimap const& other, allocator_type const& a)
2447	: table_(other.table_, a)
2448	{
2449	if (other.table_.size_) {
2450	table_.copy_buckets(
2451	other.table_, boost::unordered::detail::false_type());
2452	}
2453	}
2454
2455	template <class K, class T, class H, class P, class A>
2456	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2457	BOOST_RV_REF(unordered_multimap) other, allocator_type const& a)
2458	: table_(other.table_, a, boost::unordered::detail::move_tag ())
2459	{
2460	table_.move_construct_buckets(other.table_);
2461	}
2462
2463	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2464
2465	template <class K, class T, class H, class P, class A>
2466	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2467	std::initializer_list<value_type> list, size_type n, const hasher& hf,
2468	const key_equal& eql, const allocator_type& a)
2469	: table_(
2470	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
2471	hf, eql, a)
2472	{
2473	this->insert(list.begin(), list.end());
2474	}
2475
2476	#endif
2477
2478	template <class K, class T, class H, class P, class A>
2479	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2480	size_type n, const allocator_type& a)
2481	: table_(n, hasher(), key_equal(), a)
2482	{
2483	}
2484
2485	template <class K, class T, class H, class P, class A>
2486	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2487	size_type n, const hasher& hf, const allocator_type& a)
2488	: table_(n, hf, key_equal(), a)
2489	{
2490	}
2491
2492	template <class K, class T, class H, class P, class A>
2493	template <class InputIterator>
2494	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2495	InputIterator f, InputIterator l, const allocator_type& a)
2496	: table_(boost::unordered::detail::initial_size(
2497	f, l, detail::default_bucket_count),
2498	hasher(), key_equal(), a)
2499	{
2500	this->insert(f, l);
2501	}
2502
2503	template <class K, class T, class H, class P, class A>
2504	template <class InputIt>
2505	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2506	InputIt f, InputIt l, size_type n, const allocator_type& a)
2507	: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
2508	key_equal(), a)
2509	{
2510	this->insert(f, l);
2511	}
2512
2513	template <class K, class T, class H, class P, class A>
2514	template <class InputIt>
2515	unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
2516	size_type n, const hasher& hf, const allocator_type& a)
2517	: table_(
2518	boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
2519	{
2520	this->insert(f, l);
2521	}
2522
2523	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2524
2525	template <class K, class T, class H, class P, class A>
2526	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2527	std::initializer_list<value_type> list, const allocator_type& a)
2528	: table_(boost::unordered::detail::initial_size(
2529	list.begin(), list.end(), detail::default_bucket_count),
2530	hasher(), key_equal(), a)
2531	{
2532	this->insert(list.begin(), list.end());
2533	}
2534
2535	template <class K, class T, class H, class P, class A>
2536	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2537	std::initializer_list<value_type> list, size_type n,
2538	const allocator_type& a)
2539	: table_(
2540	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
2541	hasher(), key_equal(), a)
2542	{
2543	this->insert(list.begin(), list.end());
2544	}
2545
2546	template <class K, class T, class H, class P, class A>
2547	unordered_multimap<K, T, H, P, A>::unordered_multimap(
2548	std::initializer_list<value_type> list, size_type n, const hasher& hf,
2549	const allocator_type& a)
2550	: table_(
2551	boost::unordered::detail::initial_size(list.begin(), list.end(), n),
2552	hf, key_equal(), a)
2553	{
2554	this->insert(list.begin(), list.end());
2555	}
2556
2557	#endif
2558
2559	template <class K, class T, class H, class P, class A>
2560	unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT
2561	{
2562	}
2563
2564	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2565
2566	template <class K, class T, class H, class P, class A>
2567	unordered_multimap<K, T, H, P, A>& unordered_multimap<K, T, H, P, A>::
2568	operator=(std::initializer_list<value_type> list)
2569	{
2570	this->clear();
2571	this->insert(list.begin(), list.end());
2572	return *this;
2573	}
2574
2575	#endif
2576
2577	// size and capacity
2578
2579	template <class K, class T, class H, class P, class A>
2580	std::size_t
2581	unordered_multimap<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
2582	{
2583	using namespace std;
2584
2585	// size <= mlf_ count*
2586	return boost::unordered::detail::double_to_size(
2587	f: ceil(x: static_cast<double>(table_.mlf_) *
2588	static_cast<double>(table_.max_bucket_count()))) -
2589	`1`;
2590	}
2591
2592	// modifiers
2593
2594	template <class K, class T, class H, class P, class A>
2595	template <class InputIt>
2596	void unordered_multimap<K, T, H, P, A>::insert(InputIt first, InputIt last)
2597	{
2598	table_.insert_range_equiv(first, last);
2599	}
2600
2601	#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2602	template <class K, class T, class H, class P, class A>
2603	void unordered_multimap<K, T, H, P, A>::insert(
2604	std::initializer_list<value_type> list)
2605	{
2606	this->insert(list.begin(), list.end());
2607	}
2608	#endif
2609
2610	template <class K, class T, class H, class P, class A>
2611	typename unordered_multimap<K, T, H, P, A>::iterator
2612	unordered_multimap<K, T, H, P, A>::erase(iterator position)
2613	{
2614	BOOST_ASSERT(position != this->end());
2615	return table_.erase_node(position);
2616	}
2617
2618	template <class K, class T, class H, class P, class A>
2619	typename unordered_multimap<K, T, H, P, A>::iterator
2620	unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
2621	{
2622	BOOST_ASSERT(position != this->end());
2623	return table_.erase_node(position);
2624	}
2625
2626	template <class K, class T, class H, class P, class A>
2627	typename unordered_multimap<K, T, H, P, A>::size_type
2628	unordered_multimap<K, T, H, P, A>::erase(const key_type& k)
2629	{
2630	return table_.erase_key_equiv(k);
2631	}
2632
2633	template <class K, class T, class H, class P, class A>
2634	typename unordered_multimap<K, T, H, P, A>::iterator
2635	unordered_multimap<K, T, H, P, A>::erase(
2636	const_iterator first, const_iterator last)
2637	{
2638	return table_.erase_nodes_range(first, last);
2639	}
2640
2641	template <class K, class T, class H, class P, class A>
2642	void unordered_multimap<K, T, H, P, A>::swap(unordered_multimap& other)
2643	BOOST_NOEXCEPT_IF(value_allocator_traits::is_always_equal::value&&
2644	boost::is_nothrow_swappable<H>::value&&
2645	boost::is_nothrow_swappable<P>::value)
2646	{
2647	table_.swap(other.table_);
2648	}
2649
2650	// observers
2651
2652	template <class K, class T, class H, class P, class A>
2653	typename unordered_multimap<K, T, H, P, A>::hasher
2654	unordered_multimap<K, T, H, P, A>::hash_function() const
2655	{
2656	return table_.hash_function();
2657	}
2658
2659	template <class K, class T, class H, class P, class A>
2660	typename unordered_multimap<K, T, H, P, A>::key_equal
2661	unordered_multimap<K, T, H, P, A>::key_eq() const
2662	{
2663	return table_.key_eq();
2664	}
2665
2666	template <class K, class T, class H, class P, class A>
2667	template <typename H2, typename P2>
2668	void unordered_multimap<K, T, H, P, A>::merge(
2669	boost::unordered_multimap<K, T, H2, P2, A>& source)
2670	{
2671	while (!source.empty()) {
2672	insert(source.extract(source.begin()));
2673	}
2674	}
2675
2676	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2677	template <class K, class T, class H, class P, class A>
2678	template <typename H2, typename P2>
2679	void unordered_multimap<K, T, H, P, A>::merge(
2680	boost::unordered_multimap<K, T, H2, P2, A>&& source)
2681	{
2682	while (!source.empty()) {
2683	insert(source.extract(source.begin()));
2684	}
2685	}
2686	#endif
2687
2688	template <class K, class T, class H, class P, class A>
2689	template <typename H2, typename P2>
2690	void unordered_multimap<K, T, H, P, A>::merge(
2691	boost::unordered_map<K, T, H2, P2, A>& source)
2692	{
2693	while (!source.empty()) {
2694	insert(source.extract(source.begin()));
2695	}
2696	}
2697
2698	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2699	template <class K, class T, class H, class P, class A>
2700	template <typename H2, typename P2>
2701	void unordered_multimap<K, T, H, P, A>::merge(
2702	boost::unordered_map<K, T, H2, P2, A>&& source)
2703	{
2704	while (!source.empty()) {
2705	insert(source.extract(source.begin()));
2706	}
2707	}
2708	#endif
2709
2710	// lookup
2711
2712	template <class K, class T, class H, class P, class A>
2713	typename unordered_multimap<K, T, H, P, A>::iterator
2714	unordered_multimap<K, T, H, P, A>::find(const key_type& k)
2715	{
2716	return iterator(table_.find(k));
2717	}
2718
2719	template <class K, class T, class H, class P, class A>
2720	typename unordered_multimap<K, T, H, P, A>::const_iterator
2721	unordered_multimap<K, T, H, P, A>::find(const key_type& k) const
2722	{
2723	return const_iterator(table_.find(k));
2724	}
2725
2726	template <class K, class T, class H, class P, class A>
2727	template <class CompatibleKey, class CompatibleHash,
2728	class CompatiblePredicate>
2729	typename unordered_multimap<K, T, H, P, A>::iterator
2730	unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2731	CompatibleHash const& hash, CompatiblePredicate const& eq)
2732	{
2733	return table_.transparent_find(k, hash, eq);
2734	}
2735
2736	template <class K, class T, class H, class P, class A>
2737	template <class CompatibleKey, class CompatibleHash,
2738	class CompatiblePredicate>
2739	typename unordered_multimap<K, T, H, P, A>::const_iterator
2740	unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
2741	CompatibleHash const& hash, CompatiblePredicate const& eq) const
2742	{
2743	return const_iterator(
2744	table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
2745	}
2746
2747	template <class K, class T, class H, class P, class A>
2748	typename unordered_multimap<K, T, H, P, A>::size_type
2749	unordered_multimap<K, T, H, P, A>::count(const key_type& k) const
2750	{
2751	return table_.group_count(k);
2752	}
2753
2754	template <class K, class T, class H, class P, class A>
2755	std::pair<typename unordered_multimap<K, T, H, P, A>::iterator,
2756	typename unordered_multimap<K, T, H, P, A>::iterator>
2757	unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k)
2758	{
2759	iterator n = table_.find(k);
2760	return std::make_pair(n, (n == end() ? n : table_.next_group(k, n)));
2761	}
2762
2763	template <class K, class T, class H, class P, class A>
2764	std::pair<typename unordered_multimap<K, T, H, P, A>::const_iterator,
2765	typename unordered_multimap<K, T, H, P, A>::const_iterator>
2766	unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const
2767	{
2768	iterator n = table_.find(k);
2769	return std::make_pair(const_iterator(n),
2770	const_iterator(n == end() ? n : table_.next_group(k, n)));
2771	}
2772
2773	template <class K, class T, class H, class P, class A>
2774	typename unordered_multimap<K, T, H, P, A>::size_type
2775	unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const
2776	{
2777	return table_.bucket_size(n);
2778	}
2779
2780	// hash policy
2781
2782	template <class K, class T, class H, class P, class A>
2783	float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
2784	{
2785	if (table_.size_ == `0`) {
2786	return `0.0f`;
2787	}
2788
2789	BOOST_ASSERT(table_.bucket_count() != `0`);
2790	return static_cast<float>(table_.size_) /
2791	static_cast<float>(table_.bucket_count());
2792	}
2793
2794	template <class K, class T, class H, class P, class A>
2795	void unordered_multimap<K, T, H, P, A>::max_load_factor(
2796	float m) BOOST_NOEXCEPT
2797	{
2798	table_.max_load_factor(m);
2799	}
2800
2801	template <class K, class T, class H, class P, class A>
2802	void unordered_multimap<K, T, H, P, A>::rehash(size_type n)
2803	{
2804	table_.rehash(n);
2805	}
2806
2807	template <class K, class T, class H, class P, class A>
2808	void unordered_multimap<K, T, H, P, A>::reserve(size_type n)
2809	{
2810	table_.reserve(n);
2811	}
2812
2813	template <class K, class T, class H, class P, class A>
2814	inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
2815	unordered_multimap<K, T, H, P, A> const& m2)
2816	{
2817	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2818	struct dummy
2819	{
2820	unordered_multimap<K, T, H, P, A> x;
2821	};
2822	#endif
2823	return m1.table_.equals_equiv(m2.table_);
2824	}
2825
2826	template <class K, class T, class H, class P, class A>
2827	inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
2828	unordered_multimap<K, T, H, P, A> const& m2)
2829	{
2830	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2831	struct dummy
2832	{
2833	unordered_multimap<K, T, H, P, A> x;
2834	};
2835	#endif
2836	return !m1.table_.equals_equiv(m2.table_);
2837	}
2838
2839	template <class K, class T, class H, class P, class A>
2840	inline void swap(unordered_multimap<K, T, H, P, A>& m1,
2841	unordered_multimap<K, T, H, P, A>& m2)
2842	BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
2843	{
2844	#if BOOST_WORKAROUND(BOOST_CODEGEARC, BOOST_TESTED_AT(0x0613))
2845	struct dummy
2846	{
2847	unordered_multimap<K, T, H, P, A> x;
2848	};
2849	#endif
2850	m1.swap(m2);
2851	}
2852
2853	template <class K, class T, class H, class P, class A, class Predicate>
2854	typename unordered_multimap<K, T, H, P, A>::size_type erase_if(
2855	unordered_multimap<K, T, H, P, A>& c, Predicate pred)
2856	{
2857	return detail::erase_if(c, pred);
2858	}
2859
2860	template <typename N, class K, class T, class A> class node_handle_map
2861	{
2862	BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle_map)
2863
2864	template <typename Types> friend struct ::boost::unordered::detail::table;
2865	template <class K2, class T2, class H2, class P2, class A2>
2866	friend class boost::unordered::unordered_map;
2867	template <class K2, class T2, class H2, class P2, class A2>
2868	friend class boost::unordered::unordered_multimap;
2869
2870	typedef typename boost::allocator_rebind<A, std::pair<K const, T> >::type
2871	value_allocator;
2872
2873	typedef N node;
2874	typedef typename boost::allocator_rebind<A, node>::type node_allocator;
2875
2876	typedef
2877	typename boost::allocator_pointer<node_allocator>::type node_pointer;
2878
2879	public:
2880	typedef K key_type;
2881	typedef T mapped_type;
2882	typedef A allocator_type;
2883
2884	private:
2885	node_pointer ptr_;
2886	boost::unordered::detail::optional<value_allocator> alloc_;
2887
2888	node_handle_map(node_pointer ptr, allocator_type const& a)
2889	: ptr_(ptr), alloc_(a)
2890	{
2891	}
2892
2893	public:
2894	BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(), alloc_() {}
2895
2896	~node_handle_map()
2897	{
2898	if (ptr_) {
2899	node_allocator node_alloc(*alloc_);
2900	boost::unordered::detail::node_tmp<node_allocator> tmp(
2901	ptr_, node_alloc);
2902	}
2903	}
2904
2905	node_handle_map(BOOST_RV_REF(node_handle_map) n) BOOST_NOEXCEPT
2906	: ptr_(n.ptr_),
2907	alloc_(boost::move(n.alloc_))
2908	{
2909	n.ptr_ = node_pointer();
2910	}
2911
2912	node_handle_map& operator=(BOOST_RV_REF(node_handle_map) n)
2913	{
2914	BOOST_ASSERT(!alloc_.has_value() \|\|
2915	boost::allocator_propagate_on_container_move_assignment<
2916	value_allocator>::type::value \|\|
2917	(n.alloc_.has_value() && alloc_ == n.alloc_));
2918
2919	if (ptr_) {
2920	node_allocator node_alloc(*alloc_);
2921	boost::unordered::detail::node_tmp<node_allocator> tmp(
2922	ptr_, node_alloc);
2923	ptr_ = node_pointer();
2924	}
2925
2926	if (!alloc_.has_value() \|\|
2927	boost::allocator_propagate_on_container_move_assignment<
2928	value_allocator>::type::value) {
2929	alloc_ = boost::move(n.alloc_);
2930	}
2931	ptr_ = n.ptr_;
2932	n.ptr_ = node_pointer();
2933
2934	return *this;
2935	}
2936
2937	key_type& key() const
2938	{
2939	return const_cast<key_type&>(ptr_->value().first);
2940	}
2941
2942	mapped_type& mapped() const { return ptr_->value().second; }
2943
2944	allocator_type get_allocator() const { return *alloc_; }
2945
2946	BOOST_EXPLICIT_OPERATOR_BOOL_NOEXCEPT()
2947
2948	bool operator!() const BOOST_NOEXCEPT { return ptr_ ? `0` : `1`; }
2949
2950	BOOST_ATTRIBUTE_NODISCARD bool empty() const BOOST_NOEXCEPT
2951	{
2952	return ptr_ ? `0` : `1`;
2953	}
2954
2955	void swap(node_handle_map& n) BOOST_NOEXCEPT_IF(
2956	boost::allocator_propagate_on_container_swap<
2957	value_allocator>::type::value \|\|
2958	boost::allocator_is_always_equal<value_allocator>::type::value)
2959	{
2960
2961	BOOST_ASSERT(!alloc_.has_value() \|\| !n.alloc_.has_value() \|\|
2962	boost::allocator_propagate_on_container_swap<
2963	value_allocator>::type::value \|\|
2964	alloc_ == n.alloc_);
2965	if (boost::allocator_propagate_on_container_swap<
2966	value_allocator>::type::value \|\|
2967	!alloc_.has_value() \|\| !n.alloc_.has_value()) {
2968	boost::swap(alloc_, n.alloc_);
2969	}
2970	boost::swap(ptr_, n.ptr_);
2971	}
2972	};
2973
2974	template <class N, class K, class T, class A>
2975	void swap(node_handle_map<N, K, T, A>& x, node_handle_map<N, K, T, A>& y)
2976	BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(x.swap(y)))
2977	{
2978	x.swap(y);
2979	}
2980
2981	template <class Iter, class NodeType> struct insert_return_type_map
2982	{
2983	private:
2984	BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_map)
2985
2986	// typedef typename boost::allocator_rebind<A,
2987	// std::pair<K const, T> >::type value_allocator;
2988	// typedef N node_;
2989
2990	public:
2991	Iter position;
2992	bool inserted;
2993	NodeType node;
2994
2995	insert_return_type_map() : position(), inserted(false), node() {}
2996
2997	insert_return_type_map(BOOST_RV_REF(insert_return_type_map)
2998	x) BOOST_NOEXCEPT : position(x.position),
2999	inserted(x.inserted),
3000	node(boost::move(x.node))
3001	{
3002	}
3003
3004	insert_return_type_map& operator=(BOOST_RV_REF(insert_return_type_map) x)
3005	{
3006	inserted = x.inserted;
3007	position = x.position;
3008	node = boost::move(x.node);
3009	return *this;
3010	}
3011	};
3012
3013	template <class Iter, class NodeType>
3014	void swap(insert_return_type_map<Iter, NodeType>& x,
3015	insert_return_type_map<Iter, NodeType>& y)
3016	{
3017	boost::swap(x.node, y.node);
3018	boost::swap(x.inserted, y.inserted);
3019	boost::swap(x.position, y.position);
3020	}
3021	} // namespace unordered
3022	} // namespace boost
3023
3024	#if defined(BOOST_MSVC)
3025	#pragma warning(pop)
3026	#endif
3027
3028	#endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
3029

Browse the source code of include/boost/unordered/unordered_map.hpp