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