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