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