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