1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2014
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
13 #ifndef BOOST_INTRUSIVE_UNORDERED_SET_HPP
14 #define BOOST_INTRUSIVE_UNORDERED_SET_HPP
20 #include <boost/intrusive/detail/config_begin.hpp>
21 #include <boost/intrusive/intrusive_fwd.hpp>
22 #include <boost/intrusive/hashtable.hpp>
23 #include <boost/move/utility_core.hpp>
24 #include <boost/static_assert.hpp>
29 //! The class template unordered_set is an intrusive container, that mimics most of
30 //! the interface of std::tr1::unordered_set as described in the C++ TR1.
32 //! unordered_set is a semi-intrusive container: each object to be stored in the
33 //! container must contain a proper hook, but the container also needs
34 //! additional auxiliary memory to work: unordered_set needs a pointer to an array
35 //! of type `bucket_type` to be passed in the constructor. This bucket array must
36 //! have at least the same lifetime as the container. This makes the use of
37 //! unordered_set more complicated than purely intrusive containers.
38 //! `bucket_type` is default-constructible, copyable and assignable
40 //! The template parameter \c T is the type to be managed by the container.
41 //! The user can specify additional options and if no options are provided
42 //! default options are used.
44 //! The container supports the following options:
45 //! \c base_hook<>/member_hook<>/value_traits<>,
46 //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
47 //! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
49 //! unordered_set only provides forward iterators but it provides 4 iterator types:
50 //! iterator and const_iterator to navigate through the whole container and
51 //! local_iterator and const_local_iterator to navigate through the values
52 //! stored in a single bucket. Local iterators are faster and smaller.
54 //! It's not recommended to use non constant-time size unordered_sets because several
55 //! key functions, like "empty()", become non-constant time functions. Non
56 //! constant-time size unordered_sets are mainly provided to support auto-unlink hooks.
58 //! unordered_set, unlike std::unordered_set, does not make automatic rehashings nor
59 //! offers functions related to a load factor. Rehashing can be explicitly requested
60 //! and the user must provide a new bucket array that will be used from that moment.
62 //! Since no automatic rehashing is done, iterators are never invalidated when
63 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
64 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
65 template<class T, class ...Options>
67 template<class ValueTraits, class Hash, class Equal, class SizeType, class BucketTraits, std::size_t BoolFlags>
69 class unordered_set_impl
70 : public hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags>
74 typedef hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags> table_type;
78 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set_impl)
80 typedef table_type implementation_defined;
84 typedef typename implementation_defined::value_type value_type;
85 typedef typename implementation_defined::value_traits value_traits;
86 typedef typename implementation_defined::bucket_traits bucket_traits;
87 typedef typename implementation_defined::pointer pointer;
88 typedef typename implementation_defined::const_pointer const_pointer;
89 typedef typename implementation_defined::reference reference;
90 typedef typename implementation_defined::const_reference const_reference;
91 typedef typename implementation_defined::difference_type difference_type;
92 typedef typename implementation_defined::size_type size_type;
93 typedef typename implementation_defined::key_type key_type;
94 typedef typename implementation_defined::key_equal key_equal;
95 typedef typename implementation_defined::hasher hasher;
96 typedef typename implementation_defined::bucket_type bucket_type;
97 typedef typename implementation_defined::bucket_ptr bucket_ptr;
98 typedef typename implementation_defined::iterator iterator;
99 typedef typename implementation_defined::const_iterator const_iterator;
100 typedef typename implementation_defined::insert_commit_data insert_commit_data;
101 typedef typename implementation_defined::local_iterator local_iterator;
102 typedef typename implementation_defined::const_local_iterator const_local_iterator;
103 typedef typename implementation_defined::node_traits node_traits;
104 typedef typename implementation_defined::node node;
105 typedef typename implementation_defined::node_ptr node_ptr;
106 typedef typename implementation_defined::const_node_ptr const_node_ptr;
107 typedef typename implementation_defined::node_algorithms node_algorithms;
111 //! <b>Requires</b>: buckets must not be being used by any other resource.
113 //! <b>Effects</b>: Constructs an empty unordered_set_impl, storing a reference
114 //! to the bucket array and copies of the hasher and equal functors.
116 //! <b>Complexity</b>: Constant.
118 //! <b>Throws</b>: If value_traits::node_traits::node
119 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
120 //! or the copy constructor or invocation of Hash or Equal throws.
122 //! <b>Notes</b>: buckets array must be disposed only after
123 //! *this is disposed.
124 explicit unordered_set_impl( const bucket_traits &b_traits
125 , const hasher & hash_func = hasher()
126 , const key_equal &equal_func = key_equal()
127 , const value_traits &v_traits = value_traits())
128 : table_type(b_traits, hash_func, equal_func, v_traits)
131 //! <b>Requires</b>: buckets must not be being used by any other resource
132 //! and Dereferencing iterator must yield an lvalue of type value_type.
134 //! <b>Effects</b>: Constructs an empty unordered_set and inserts elements from
137 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
138 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
140 //! <b>Throws</b>: If value_traits::node_traits::node
141 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
142 //! or the copy constructor or invocation of hasher or key_equal throws.
144 //! <b>Notes</b>: buckets array must be disposed only after
145 //! *this is disposed.
146 template<class Iterator>
147 unordered_set_impl( Iterator b
149 , const bucket_traits &b_traits
150 , const hasher & hash_func = hasher()
151 , const key_equal &equal_func = key_equal()
152 , const value_traits &v_traits = value_traits())
153 : table_type(b_traits, hash_func, equal_func, v_traits)
154 { table_type::insert_unique(b, e); }
156 //! <b>Effects</b>: to-do
158 unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x)
159 : table_type(::boost::move(static_cast<table_type&>(x)))
162 //! <b>Effects</b>: to-do
164 unordered_set_impl& operator=(BOOST_RV_REF(unordered_set_impl) x)
165 { return static_cast<unordered_set_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); }
167 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
168 //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set
169 //! are not deleted (i.e. no destructors are called).
171 //! <b>Complexity</b>: Linear to the number of elements in the unordered_set, if
172 //! it's a safe-mode or auto-unlink value. Otherwise constant.
174 //! <b>Throws</b>: Nothing.
175 ~unordered_set_impl()
178 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_set.
180 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
181 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
183 //! <b>Throws</b>: Nothing.
185 { return table_type::begin(); }
187 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
188 //! of the unordered_set.
190 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
191 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
193 //! <b>Throws</b>: Nothing.
194 const_iterator begin() const
195 { return table_type::begin(); }
197 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
198 //! of the unordered_set.
200 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
201 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
203 //! <b>Throws</b>: Nothing.
204 const_iterator cbegin() const
205 { return table_type::cbegin(); }
207 //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set.
209 //! <b>Complexity</b>: Constant.
211 //! <b>Throws</b>: Nothing.
213 { return table_type::end(); }
215 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
217 //! <b>Complexity</b>: Constant.
219 //! <b>Throws</b>: Nothing.
220 const_iterator end() const
221 { return table_type::end(); }
223 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
225 //! <b>Complexity</b>: Constant.
227 //! <b>Throws</b>: Nothing.
228 const_iterator cend() const
229 { return table_type::cend(); }
231 //! <b>Effects</b>: Returns the hasher object used by the unordered_set.
233 //! <b>Complexity</b>: Constant.
235 //! <b>Throws</b>: If hasher copy-constructor throws.
236 hasher hash_function() const
237 { return table_type::hash_function(); }
239 //! <b>Effects</b>: Returns the key_equal object used by the unordered_set.
241 //! <b>Complexity</b>: Constant.
243 //! <b>Throws</b>: If key_equal copy-constructor throws.
244 key_equal key_eq() const
245 { return table_type::key_eq(); }
247 //! <b>Effects</b>: Returns true if the container is empty.
249 //! <b>Complexity</b>: if constant-time size and cache_last options are disabled,
250 //! average constant time (worst case, with empty() == true: O(this->bucket_count()).
251 //! Otherwise constant.
253 //! <b>Throws</b>: Nothing.
255 { return table_type::empty(); }
257 //! <b>Effects</b>: Returns the number of elements stored in the unordered_set.
259 //! <b>Complexity</b>: Linear to elements contained in *this if
260 //! constant-time size option is disabled. Constant-time otherwise.
262 //! <b>Throws</b>: Nothing.
263 size_type size() const
264 { return table_type::size(); }
266 //! <b>Requires</b>: the hasher and the equality function unqualified swap
267 //! call should not throw.
269 //! <b>Effects</b>: Swaps the contents of two unordered_sets.
270 //! Swaps also the contained bucket array and equality and hasher functors.
272 //! <b>Complexity</b>: Constant.
274 //! <b>Throws</b>: If the swap() call for the comparison or hash functors
275 //! found using ADL throw. Basic guarantee.
276 void swap(unordered_set_impl& other)
277 { table_type::swap(other.table_); }
279 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
280 //! Cloner should yield to nodes that compare equal and produce the same
281 //! hash than the original node.
283 //! <b>Effects</b>: Erases all the elements from *this
284 //! calling Disposer::operator()(pointer), clones all the
285 //! elements from src calling Cloner::operator()(const_reference )
286 //! and inserts them on *this. The hash function and the equality
287 //! predicate are copied from the source.
289 //! If store_hash option is true, this method does not use the hash function.
291 //! If any operation throws, all cloned elements are unlinked and disposed
292 //! calling Disposer::operator()(pointer).
294 //! <b>Complexity</b>: Linear to erased plus inserted elements.
296 //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
297 //! throws. Basic guarantee.
298 template <class Cloner, class Disposer>
299 void clone_from(const unordered_set_impl &src, Cloner cloner, Disposer disposer)
300 { table_type::clone_from(src.table_, cloner, disposer); }
302 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
304 //! <b>Requires</b>: value must be an lvalue
306 //! <b>Effects</b>: Tries to inserts value into the unordered_set.
308 //! <b>Returns</b>: If the value
309 //! is not already present inserts it and returns a pair containing the
310 //! iterator to the new value and true. If there is an equivalent value
311 //! returns a pair containing an iterator to the already present value
314 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
316 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
318 //! <b>Note</b>: Does not affect the validity of iterators and references.
319 //! No copy-constructors are called.
320 std::pair<iterator, bool> insert(reference value)
321 { return table_type::insert_unique(value); }
323 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
324 //! of type value_type.
326 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
328 //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e).
329 //! Worst case O(N*this->size()).
331 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
333 //! <b>Note</b>: Does not affect the validity of iterators and references.
334 //! No copy-constructors are called.
335 template<class Iterator>
336 void insert(Iterator b, Iterator e)
337 { table_type::insert_unique(b, e); }
339 //! <b>Requires</b>: "hasher" must be a hash function that induces
340 //! the same hash values as the stored hasher. The difference is that
341 //! "hasher" hashes the given key instead of the value_type.
343 //! "key_value_equal" must be a equality function that induces
344 //! the same equality as key_equal. The difference is that
345 //! "key_value_equal" compares an arbitrary key with the contained values.
347 //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using
348 //! a user provided key instead of the value itself.
350 //! <b>Returns</b>: If there is an equivalent value
351 //! returns a pair containing an iterator to the already present value
352 //! and false. If the value can be inserted returns true in the returned
353 //! pair boolean and fills "commit_data" that is meant to be used with
354 //! the "insert_commit" function.
356 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
358 //! <b>Throws</b>: If hasher or key_value_equal throw. Strong guarantee.
360 //! <b>Notes</b>: This function is used to improve performance when constructing
361 //! a value_type is expensive: if there is an equivalent value
362 //! the constructed object must be discarded. Many times, the part of the
363 //! node that is used to impose the hash or the equality is much cheaper to
364 //! construct than the value_type and this function offers the possibility to
365 //! use that the part to check if the insertion will be successful.
367 //! If the check is successful, the user can construct the value_type and use
368 //! "insert_commit" to insert the object in constant-time.
370 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
371 //! objects are inserted or erased from the unordered_set.
373 //! After a successful rehashing insert_commit_data remains valid.
374 template<class KeyType, class KeyHasher, class KeyValueEqual>
375 std::pair<iterator, bool> insert_check
376 (const KeyType &key, KeyHasher hasher, KeyValueEqual key_value_equal, insert_commit_data &commit_data)
377 { return table_type::insert_unique_check(key, hasher, key_value_equal, commit_data); }
379 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
380 //! must have been obtained from a previous call to "insert_check".
381 //! No objects should have been inserted or erased from the unordered_set between
382 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
384 //! <b>Effects</b>: Inserts the value in the unordered_set using the information obtained
385 //! from the "commit_data" that a previous "insert_check" filled.
387 //! <b>Returns</b>: An iterator to the newly inserted object.
389 //! <b>Complexity</b>: Constant time.
391 //! <b>Throws</b>: Nothing.
393 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
394 //! previously executed to fill "commit_data". No value should be inserted or
395 //! erased between the "insert_check" and "insert_commit" calls.
397 //! After a successful rehashing insert_commit_data remains valid.
398 iterator insert_commit(reference value, const insert_commit_data &commit_data)
399 { return table_type::insert_unique_commit(value, commit_data); }
401 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
403 //! <b>Effects</b>: Erases the element pointed to by i.
405 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
407 //! <b>Throws</b>: Nothing.
409 //! <b>Note</b>: Invalidates the iterators (but not the references)
410 //! to the erased element. No destructors are called.
411 void erase(const_iterator i)
412 { table_type::erase(i); }
414 //! <b>Effects</b>: Erases the range pointed to by b end e.
416 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
417 //! worst case O(this->size()).
419 //! <b>Throws</b>: Nothing.
421 //! <b>Note</b>: Invalidates the iterators (but not the references)
422 //! to the erased elements. No destructors are called.
423 void erase(const_iterator b, const_iterator e)
424 { table_type::erase(b, e); }
426 //! <b>Effects</b>: Erases all the elements with the given value.
428 //! <b>Returns</b>: The number of erased elements.
430 //! <b>Complexity</b>: Average case O(this->count(value)).
431 //! Worst case O(this->size()).
433 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
435 //! <b>Note</b>: Invalidates the iterators (but not the references)
436 //! to the erased elements. No destructors are called.
437 size_type erase(const_reference value)
438 { return table_type::erase(value); }
440 //! <b>Requires</b>: "hasher" must be a hash function that induces
441 //! the same hash values as the stored hasher. The difference is that
442 //! "hasher" hashes the given key instead of the value_type.
444 //! "key_value_equal" must be a equality function that induces
445 //! the same equality as key_equal. The difference is that
446 //! "key_value_equal" compares an arbitrary key with the contained values.
448 //! <b>Effects</b>: Erases all the elements that have the same hash and
449 //! compare equal with the given key.
451 //! <b>Returns</b>: The number of erased elements.
453 //! <b>Complexity</b>: Average case O(this->count(value)).
454 //! Worst case O(this->size()).
456 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
458 //! <b>Note</b>: Invalidates the iterators (but not the references)
459 //! to the erased elements. No destructors are called.
460 template<class KeyType, class KeyHasher, class KeyValueEqual>
461 size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
462 { return table_type::erase(key, hash_func, equal_func); }
464 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
466 //! <b>Effects</b>: Erases the element pointed to by i.
467 //! Disposer::operator()(pointer) is called for the removed element.
469 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
471 //! <b>Throws</b>: Nothing.
473 //! <b>Note</b>: Invalidates the iterators
474 //! to the erased elements.
475 template<class Disposer>
476 void erase_and_dispose(const_iterator i, Disposer disposer
478 , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
481 { table_type::erase_and_dispose(i, disposer); }
483 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
485 //! <b>Effects</b>: Erases the range pointed to by b end e.
486 //! Disposer::operator()(pointer) is called for the removed elements.
488 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
489 //! worst case O(this->size()).
491 //! <b>Throws</b>: Nothing.
493 //! <b>Note</b>: Invalidates the iterators
494 //! to the erased elements.
495 template<class Disposer>
496 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
497 { table_type::erase_and_dispose(b, e, disposer); }
499 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
501 //! <b>Effects</b>: Erases all the elements with the given value.
502 //! Disposer::operator()(pointer) is called for the removed elements.
504 //! <b>Returns</b>: The number of erased elements.
506 //! <b>Complexity</b>: Average case O(this->count(value)).
507 //! Worst case O(this->size()).
509 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
511 //! <b>Note</b>: Invalidates the iterators (but not the references)
512 //! to the erased elements. No destructors are called.
513 template<class Disposer>
514 size_type erase_and_dispose(const_reference value, Disposer disposer)
515 { return table_type::erase_and_dispose(value, disposer); }
517 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
519 //! <b>Effects</b>: Erases all the elements with the given key.
520 //! according to the comparison functor "equal_func".
521 //! Disposer::operator()(pointer) is called for the removed elements.
523 //! <b>Returns</b>: The number of erased elements.
525 //! <b>Complexity</b>: Average case O(this->count(value)).
526 //! Worst case O(this->size()).
528 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
530 //! <b>Note</b>: Invalidates the iterators
531 //! to the erased elements.
532 template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
533 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
534 { return table_type::erase_and_dispose(key, hash_func, equal_func, disposer); }
536 //! <b>Effects</b>: Erases all of the elements.
538 //! <b>Complexity</b>: Linear to the number of elements on the container.
539 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
541 //! <b>Throws</b>: Nothing.
543 //! <b>Note</b>: Invalidates the iterators (but not the references)
544 //! to the erased elements. No destructors are called.
546 { return table_type::clear(); }
548 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
550 //! <b>Effects</b>: Erases all of the elements.
552 //! <b>Complexity</b>: Linear to the number of elements on the container.
553 //! Disposer::operator()(pointer) is called for the removed elements.
555 //! <b>Throws</b>: Nothing.
557 //! <b>Note</b>: Invalidates the iterators (but not the references)
558 //! to the erased elements. No destructors are called.
559 template<class Disposer>
560 void clear_and_dispose(Disposer disposer)
561 { return table_type::clear_and_dispose(disposer); }
563 //! <b>Effects</b>: Returns the number of contained elements with the given value
565 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
567 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
568 size_type count(const_reference value) const
569 { return table_type::find(value) != end(); }
571 //! <b>Requires</b>: "hash_func" must be a hash function that induces
572 //! the same hash values as the stored hasher. The difference is that
573 //! "hash_func" hashes the given key instead of the value_type.
575 //! "equal_func" must be a equality function that induces
576 //! the same equality as key_equal. The difference is that
577 //! "equal_func" compares an arbitrary key with the contained values.
579 //! <b>Effects</b>: Returns the number of contained elements with the given key
581 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
583 //! <b>Throws</b>: If hash_func or equal_func throw.
584 template<class KeyType, class KeyHasher, class KeyValueEqual>
585 size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
586 { return table_type::find(key, hash_func, equal_func) != end(); }
588 //! <b>Effects</b>: Finds an iterator to the first element is equal to
589 //! "value" or end() if that element does not exist.
591 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
593 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
594 iterator find(const_reference value)
595 { return table_type::find(value); }
597 //! <b>Requires</b>: "hash_func" must be a hash function that induces
598 //! the same hash values as the stored hasher. The difference is that
599 //! "hash_func" hashes the given key instead of the value_type.
601 //! "equal_func" must be a equality function that induces
602 //! the same equality as key_equal. The difference is that
603 //! "equal_func" compares an arbitrary key with the contained values.
605 //! <b>Effects</b>: Finds an iterator to the first element whose key is
606 //! "key" according to the given hasher and equality functor or end() if
607 //! that element does not exist.
609 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
611 //! <b>Throws</b>: If hash_func or equal_func throw.
613 //! <b>Note</b>: This function is used when constructing a value_type
614 //! is expensive and the value_type can be compared with a cheaper
615 //! key type. Usually this key is part of the value_type.
616 template<class KeyType, class KeyHasher, class KeyValueEqual>
617 iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
618 { return table_type::find(key, hash_func, equal_func); }
620 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
621 //! "key" or end() if that element does not exist.
623 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
625 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
626 const_iterator find(const_reference value) const
627 { return table_type::find(value); }
629 //! <b>Requires</b>: "hash_func" must be a hash function that induces
630 //! the same hash values as the stored hasher. The difference is that
631 //! "hash_func" hashes the given key instead of the value_type.
633 //! "equal_func" must be a equality function that induces
634 //! the same equality as key_equal. The difference is that
635 //! "equal_func" compares an arbitrary key with the contained values.
637 //! <b>Effects</b>: Finds an iterator to the first element whose key is
638 //! "key" according to the given hasher and equality functor or end() if
639 //! that element does not exist.
641 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
643 //! <b>Throws</b>: If hash_func or equal_func throw.
645 //! <b>Note</b>: This function is used when constructing a value_type
646 //! is expensive and the value_type can be compared with a cheaper
647 //! key type. Usually this key is part of the value_type.
648 template<class KeyType, class KeyHasher, class KeyValueEqual>
649 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
650 { return table_type::find(key, hash_func, equal_func); }
652 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
653 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
656 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
658 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
659 std::pair<iterator,iterator> equal_range(const_reference value)
660 { return table_type::equal_range(value); }
662 //! <b>Requires</b>: "hash_func" must be a hash function that induces
663 //! the same hash values as the stored hasher. The difference is that
664 //! "hash_func" hashes the given key instead of the value_type.
666 //! "equal_func" must be a equality function that induces
667 //! the same equality as key_equal. The difference is that
668 //! "equal_func" compares an arbitrary key with the contained values.
670 //! <b>Effects</b>: Returns a range containing all elements with equivalent
671 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
674 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, hash_func)).
675 //! Worst case O(this->size()).
677 //! <b>Throws</b>: If hash_func or the equal_func throw.
679 //! <b>Note</b>: This function is used when constructing a value_type
680 //! is expensive and the value_type can be compared with a cheaper
681 //! key type. Usually this key is part of the value_type.
682 template<class KeyType, class KeyHasher, class KeyValueEqual>
683 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
684 { return table_type::equal_range(key, hash_func, equal_func); }
686 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
687 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
690 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
692 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
693 std::pair<const_iterator, const_iterator>
694 equal_range(const_reference value) const
695 { return table_type::equal_range(value); }
697 //! <b>Requires</b>: "hash_func" must be a hash function that induces
698 //! the same hash values as the stored hasher. The difference is that
699 //! "hash_func" hashes the given key instead of the value_type.
701 //! "equal_func" must be a equality function that induces
702 //! the same equality as key_equal. The difference is that
703 //! "equal_func" compares an arbitrary key with the contained values.
705 //! <b>Effects</b>: Returns a range containing all elements with equivalent
706 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
709 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
710 //! Worst case O(this->size()).
712 //! <b>Throws</b>: If the hash_func or equal_func throw.
714 //! <b>Note</b>: This function is used when constructing a value_type
715 //! is expensive and the value_type can be compared with a cheaper
716 //! key type. Usually this key is part of the value_type.
717 template<class KeyType, class KeyHasher, class KeyValueEqual>
718 std::pair<const_iterator, const_iterator>
719 equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
720 { return table_type::equal_range(key, hash_func, equal_func); }
722 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
723 //! appropriate type. Otherwise the behavior is undefined.
725 //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_set
726 //! that points to the value
728 //! <b>Complexity</b>: Constant.
730 //! <b>Throws</b>: If the internal hash function throws.
731 iterator iterator_to(reference value)
732 { return table_type::iterator_to(value); }
734 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
735 //! appropriate type. Otherwise the behavior is undefined.
737 //! <b>Effects</b>: Returns: a valid const_iterator belonging to the
738 //! unordered_set that points to the value
740 //! <b>Complexity</b>: Constant.
742 //! <b>Throws</b>: If the internal hash function throws.
743 const_iterator iterator_to(const_reference value) const
744 { return table_type::iterator_to(value); }
746 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
747 //! appropriate type. Otherwise the behavior is undefined.
749 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
750 //! that points to the value
752 //! <b>Complexity</b>: Constant.
754 //! <b>Throws</b>: Nothing.
756 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
758 static local_iterator s_local_iterator_to(reference value)
759 { return table_type::s_local_iterator_to(value); }
761 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
762 //! appropriate type. Otherwise the behavior is undefined.
764 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
765 //! the unordered_set that points to the value
767 //! <b>Complexity</b>: Constant.
769 //! <b>Throws</b>: Nothing.
771 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
773 static const_local_iterator s_local_iterator_to(const_reference value)
774 { return table_type::s_local_iterator_to(value); }
776 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
777 //! appropriate type. Otherwise the behavior is undefined.
779 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
780 //! that points to the value
782 //! <b>Complexity</b>: Constant.
784 //! <b>Throws</b>: Nothing.
785 local_iterator local_iterator_to(reference value)
786 { return table_type::local_iterator_to(value); }
788 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
789 //! appropriate type. Otherwise the behavior is undefined.
791 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
792 //! the unordered_set that points to the value
794 //! <b>Complexity</b>: Constant.
796 //! <b>Throws</b>: Nothing.
797 const_local_iterator local_iterator_to(const_reference value) const
798 { return table_type::local_iterator_to(value); }
800 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
801 //! or the last rehash function.
803 //! <b>Complexity</b>: Constant.
805 //! <b>Throws</b>: Nothing.
806 size_type bucket_count() const
807 { return table_type::bucket_count(); }
809 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
811 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
813 //! <b>Complexity</b>: Constant.
815 //! <b>Throws</b>: Nothing.
816 size_type bucket_size(size_type n) const
817 { return table_type::bucket_size(n); }
819 //! <b>Effects</b>: Returns the index of the bucket in which elements
820 //! with keys equivalent to k would be found, if any such element existed.
822 //! <b>Complexity</b>: Constant.
824 //! <b>Throws</b>: If the hash functor throws.
826 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
827 size_type bucket(const value_type& k) const
828 { return table_type::bucket(k); }
830 //! <b>Requires</b>: "hash_func" must be a hash function that induces
831 //! the same hash values as the stored hasher. The difference is that
832 //! "hash_func" hashes the given key instead of the value_type.
834 //! <b>Effects</b>: Returns the index of the bucket in which elements
835 //! with keys equivalent to k would be found, if any such element existed.
837 //! <b>Complexity</b>: Constant.
839 //! <b>Throws</b>: If hash_func throws.
841 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
842 template<class KeyType, class KeyHasher>
843 size_type bucket(const KeyType& k, KeyHasher hash_func) const
844 { return table_type::bucket(k, hash_func); }
846 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
847 //! or the last rehash function.
849 //! <b>Complexity</b>: Constant.
851 //! <b>Throws</b>: Nothing.
852 bucket_ptr bucket_pointer() const
853 { return table_type::bucket_pointer(); }
855 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
857 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
858 //! of the sequence stored in the bucket n.
860 //! <b>Complexity</b>: Constant.
862 //! <b>Throws</b>: Nothing.
864 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
865 //! containing all of the elements in the nth bucket.
866 local_iterator begin(size_type n)
867 { return table_type::begin(n); }
869 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
871 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
872 //! of the sequence stored in the bucket n.
874 //! <b>Complexity</b>: Constant.
876 //! <b>Throws</b>: Nothing.
878 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
879 //! containing all of the elements in the nth bucket.
880 const_local_iterator begin(size_type n) const
881 { return table_type::begin(n); }
883 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
885 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
886 //! of the sequence stored in the bucket n.
888 //! <b>Complexity</b>: Constant.
890 //! <b>Throws</b>: Nothing.
892 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
893 //! containing all of the elements in the nth bucket.
894 const_local_iterator cbegin(size_type n) const
895 { return table_type::cbegin(n); }
897 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
899 //! <b>Effects</b>: Returns a local_iterator pointing to the end
900 //! of the sequence stored in the bucket n.
902 //! <b>Complexity</b>: Constant.
904 //! <b>Throws</b>: Nothing.
906 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
907 //! containing all of the elements in the nth bucket.
908 local_iterator end(size_type n)
909 { return table_type::end(n); }
911 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
913 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
914 //! of the sequence stored in the bucket n.
916 //! <b>Complexity</b>: Constant.
918 //! <b>Throws</b>: Nothing.
920 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
921 //! containing all of the elements in the nth bucket.
922 const_local_iterator end(size_type n) const
923 { return table_type::end(n); }
925 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
927 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
928 //! of the sequence stored in the bucket n.
930 //! <b>Complexity</b>: Constant.
932 //! <b>Throws</b>: Nothing.
934 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
935 //! containing all of the elements in the nth bucket.
936 const_local_iterator cend(size_type n) const
937 { return table_type::cend(n); }
939 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
940 //! or the same as the old bucket array. new_size is the length of the
941 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
942 //! n can be bigger or smaller than this->bucket_count().
944 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
945 //! the values from the old bucket and inserts then in the new one.
947 //! If store_hash option is true, this method does not use the hash function.
949 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
951 //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
952 void rehash(const bucket_traits &new_bucket_traits)
953 { table_type::rehash(new_bucket_traits); }
959 //! <b>Complexity</b>:
963 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
964 bool incremental_rehash(bool grow = true)
965 { return table_type::incremental_rehash(grow); }
967 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
968 bool incremental_rehash(const bucket_traits &new_bucket_traits)
969 { return table_type::incremental_rehash(new_bucket_traits); }
975 //! <b>Complexity</b>:
978 size_type split_count() const
979 { return table_type::split_count(); }
981 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
982 //! the container that is bigger than n. This suggestion can be used
983 //! to create bucket arrays with a size that will usually improve
984 //! container's performance. If such value does not exist, the
985 //! higher possible value is returned.
987 //! <b>Complexity</b>: Amortized constant time.
989 //! <b>Throws</b>: Nothing.
990 static size_type suggested_upper_bucket_count(size_type n)
991 { return table_type::suggested_upper_bucket_count(n); }
993 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
994 //! the container that is smaller than n. This suggestion can be used
995 //! to create bucket arrays with a size that will usually improve
996 //! container's performance. If such value does not exist, the
997 //! lower possible value is returned.
999 //! <b>Complexity</b>: Amortized constant time.
1001 //! <b>Throws</b>: Nothing.
1002 static size_type suggested_lower_bucket_count(size_type n)
1003 { return table_type::suggested_lower_bucket_count(n); }
1005 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1008 //! Helper metafunction to define an \c unordered_set that yields to the same type when the
1009 //! same options (either explicitly or implicitly) are used.
1010 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1011 template<class T, class ...Options>
1013 template<class T, class O1 = void, class O2 = void
1014 , class O3 = void, class O4 = void
1015 , class O5 = void, class O6 = void
1016 , class O7 = void, class O8 = void
1017 , class O9 = void, class O10= void
1020 struct make_unordered_set
1023 typedef typename pack_options
1024 < hashtable_defaults,
1025 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1026 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1030 >::type packed_options;
1032 typedef typename detail::get_value_traits
1033 <T, typename packed_options::proto_value_traits>::type value_traits;
1035 typedef typename make_bucket_traits
1036 <T, true, packed_options>::type bucket_traits;
1038 typedef unordered_set_impl
1040 , typename packed_options::hash
1041 , typename packed_options::equal
1042 , typename packed_options::size_type
1044 , (std::size_t(true)*hash_bool_flags::unique_keys_pos)
1045 | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
1046 | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
1047 | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
1048 | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
1049 | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
1050 > implementation_defined;
1053 typedef implementation_defined type;
1056 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1058 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1059 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
1061 template<class T, class ...Options>
1064 : public make_unordered_set<T,
1065 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1066 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1072 typedef typename make_unordered_set
1074 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1075 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1081 //Assert if passed value traits are compatible with the type
1082 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
1083 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set)
1086 typedef typename Base::value_traits value_traits;
1087 typedef typename Base::bucket_traits bucket_traits;
1088 typedef typename Base::iterator iterator;
1089 typedef typename Base::const_iterator const_iterator;
1090 typedef typename Base::bucket_ptr bucket_ptr;
1091 typedef typename Base::size_type size_type;
1092 typedef typename Base::hasher hasher;
1093 typedef typename Base::key_equal key_equal;
1095 explicit unordered_set ( const bucket_traits &b_traits
1096 , const hasher & hash_func = hasher()
1097 , const key_equal &equal_func = key_equal()
1098 , const value_traits &v_traits = value_traits())
1099 : Base(b_traits, hash_func, equal_func, v_traits)
1102 template<class Iterator>
1103 unordered_set ( Iterator b
1105 , const bucket_traits &b_traits
1106 , const hasher & hash_func = hasher()
1107 , const key_equal &equal_func = key_equal()
1108 , const value_traits &v_traits = value_traits())
1109 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
1112 unordered_set(BOOST_RV_REF(unordered_set) x)
1113 : Base(::boost::move(static_cast<Base&>(x)))
1116 unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
1117 { return static_cast<unordered_set&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
1123 //! The class template unordered_multiset is an intrusive container, that mimics most of
1124 //! the interface of std::tr1::unordered_multiset as described in the C++ TR1.
1126 //! unordered_multiset is a semi-intrusive container: each object to be stored in the
1127 //! container must contain a proper hook, but the container also needs
1128 //! additional auxiliary memory to work: unordered_multiset needs a pointer to an array
1129 //! of type `bucket_type` to be passed in the constructor. This bucket array must
1130 //! have at least the same lifetime as the container. This makes the use of
1131 //! unordered_multiset more complicated than purely intrusive containers.
1132 //! `bucket_type` is default-constructible, copyable and assignable
1134 //! The template parameter \c T is the type to be managed by the container.
1135 //! The user can specify additional options and if no options are provided
1136 //! default options are used.
1138 //! The container supports the following options:
1139 //! \c base_hook<>/member_hook<>/value_traits<>,
1140 //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
1141 //! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
1143 //! unordered_multiset only provides forward iterators but it provides 4 iterator types:
1144 //! iterator and const_iterator to navigate through the whole container and
1145 //! local_iterator and const_local_iterator to navigate through the values
1146 //! stored in a single bucket. Local iterators are faster and smaller.
1148 //! It's not recommended to use non constant-time size unordered_multisets because several
1149 //! key functions, like "empty()", become non-constant time functions. Non
1150 //! constant-time size unordered_multisets are mainly provided to support auto-unlink hooks.
1152 //! unordered_multiset, unlike std::unordered_set, does not make automatic rehashings nor
1153 //! offers functions related to a load factor. Rehashing can be explicitly requested
1154 //! and the user must provide a new bucket array that will be used from that moment.
1156 //! Since no automatic rehashing is done, iterators are never invalidated when
1157 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
1158 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1159 template<class T, class ...Options>
1161 template<class ValueTraits, class Hash, class Equal, class SizeType, class BucketTraits, std::size_t BoolFlags>
1163 class unordered_multiset_impl
1164 : public hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags>
1168 typedef hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags> table_type;
1172 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset_impl)
1174 typedef table_type implementation_defined;
1177 typedef typename implementation_defined::value_type value_type;
1178 typedef typename implementation_defined::value_traits value_traits;
1179 typedef typename implementation_defined::bucket_traits bucket_traits;
1180 typedef typename implementation_defined::pointer pointer;
1181 typedef typename implementation_defined::const_pointer const_pointer;
1182 typedef typename implementation_defined::reference reference;
1183 typedef typename implementation_defined::const_reference const_reference;
1184 typedef typename implementation_defined::difference_type difference_type;
1185 typedef typename implementation_defined::size_type size_type;
1186 typedef typename implementation_defined::key_type key_type;
1187 typedef typename implementation_defined::key_equal key_equal;
1188 typedef typename implementation_defined::hasher hasher;
1189 typedef typename implementation_defined::bucket_type bucket_type;
1190 typedef typename implementation_defined::bucket_ptr bucket_ptr;
1191 typedef typename implementation_defined::iterator iterator;
1192 typedef typename implementation_defined::const_iterator const_iterator;
1193 typedef typename implementation_defined::insert_commit_data insert_commit_data;
1194 typedef typename implementation_defined::local_iterator local_iterator;
1195 typedef typename implementation_defined::const_local_iterator const_local_iterator;
1196 typedef typename implementation_defined::node_traits node_traits;
1197 typedef typename implementation_defined::node node;
1198 typedef typename implementation_defined::node_ptr node_ptr;
1199 typedef typename implementation_defined::const_node_ptr const_node_ptr;
1200 typedef typename implementation_defined::node_algorithms node_algorithms;
1204 //! <b>Requires</b>: buckets must not be being used by any other resource.
1206 //! <b>Effects</b>: Constructs an empty unordered_multiset, storing a reference
1207 //! to the bucket array and copies of the hasher and equal functors.
1209 //! <b>Complexity</b>: Constant.
1211 //! <b>Throws</b>: If value_traits::node_traits::node
1212 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1213 //! or the copy constructor or invocation of Hash or Equal throws.
1215 //! <b>Notes</b>: buckets array must be disposed only after
1216 //! *this is disposed.
1217 explicit unordered_multiset_impl ( const bucket_traits &b_traits
1218 , const hasher & hash_func = hasher()
1219 , const key_equal &equal_func = key_equal()
1220 , const value_traits &v_traits = value_traits())
1221 : table_type(b_traits, hash_func, equal_func, v_traits)
1224 //! <b>Requires</b>: buckets must not be being used by any other resource
1225 //! and Dereferencing iterator must yield an lvalue of type value_type.
1227 //! <b>Effects</b>: Constructs an empty unordered_multiset and inserts elements from
1230 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
1231 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
1233 //! <b>Throws</b>: If value_traits::node_traits::node
1234 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1235 //! or the copy constructor or invocation of hasher or key_equal throws.
1237 //! <b>Notes</b>: buckets array must be disposed only after
1238 //! *this is disposed.
1239 template<class Iterator>
1240 unordered_multiset_impl ( Iterator b
1242 , const bucket_traits &b_traits
1243 , const hasher & hash_func = hasher()
1244 , const key_equal &equal_func = key_equal()
1245 , const value_traits &v_traits = value_traits())
1246 : table_type(b_traits, hash_func, equal_func, v_traits)
1247 { table_type::insert_equal(b, e); }
1249 //! <b>Effects</b>: to-do
1251 unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x)
1252 : table_type(::boost::move(static_cast<table_type&>(x)))
1255 //! <b>Effects</b>: to-do
1257 unordered_multiset_impl& operator=(BOOST_RV_REF(unordered_multiset_impl) x)
1258 { return static_cast<unordered_multiset_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); }
1260 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1262 //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_multiset
1263 //! are not deleted (i.e. no destructors are called).
1265 //! <b>Complexity</b>: Linear to the number of elements in the unordered_multiset, if
1266 //! it's a safe-mode or auto-unlink value. Otherwise constant.
1268 //! <b>Throws</b>: Nothing.
1269 ~unordered_multiset_impl()
1272 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_multiset.
1274 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1275 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1277 //! <b>Throws</b>: Nothing.
1279 { return table_type::begin(); }
1281 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
1282 //! of the unordered_multiset.
1284 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1285 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1287 //! <b>Throws</b>: Nothing.
1288 const_iterator begin() const
1289 { return table_type::begin(); }
1291 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
1292 //! of the unordered_multiset.
1294 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1295 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1297 //! <b>Throws</b>: Nothing.
1298 const_iterator cbegin() const
1299 { return table_type::cbegin(); }
1301 //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_multiset.
1303 //! <b>Complexity</b>: Constant.
1305 //! <b>Throws</b>: Nothing.
1307 { return table_type::end(); }
1309 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
1311 //! <b>Complexity</b>: Constant.
1313 //! <b>Throws</b>: Nothing.
1314 const_iterator end() const
1315 { return table_type::end(); }
1317 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
1319 //! <b>Complexity</b>: Constant.
1321 //! <b>Throws</b>: Nothing.
1322 const_iterator cend() const
1323 { return table_type::cend(); }
1325 //! <b>Effects</b>: Returns the hasher object used by the unordered_set.
1327 //! <b>Complexity</b>: Constant.
1329 //! <b>Throws</b>: If hasher copy-constructor throws.
1330 hasher hash_function() const
1331 { return table_type::hash_function(); }
1333 //! <b>Effects</b>: Returns the key_equal object used by the unordered_multiset.
1335 //! <b>Complexity</b>: Constant.
1337 //! <b>Throws</b>: If key_equal copy-constructor throws.
1338 key_equal key_eq() const
1339 { return table_type::key_eq(); }
1341 //! <b>Effects</b>: Returns true if the container is empty.
1343 //! <b>Complexity</b>: if constant-time size and cache_last options are disabled,
1344 //! average constant time (worst case, with empty() == true: O(this->bucket_count()).
1345 //! Otherwise constant.
1347 //! <b>Throws</b>: Nothing.
1349 { return table_type::empty(); }
1351 //! <b>Effects</b>: Returns the number of elements stored in the unordered_multiset.
1353 //! <b>Complexity</b>: Linear to elements contained in *this if
1354 //! constant-time size option is disabled. Constant-time otherwise.
1356 //! <b>Throws</b>: Nothing.
1357 size_type size() const
1358 { return table_type::size(); }
1360 //! <b>Requires</b>: the hasher and the equality function unqualified swap
1361 //! call should not throw.
1363 //! <b>Effects</b>: Swaps the contents of two unordered_multisets.
1364 //! Swaps also the contained bucket array and equality and hasher functors.
1367 //! <b>Complexity</b>: Constant.
1369 //! <b>Throws</b>: If the swap() call for the comparison or hash functors
1370 //! found using ADL throw. Basic guarantee.
1371 void swap(unordered_multiset_impl& other)
1372 { table_type::swap(other.table_); }
1374 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1375 //! Cloner should yield to nodes that compare equal and produce the same
1376 //! hash than the original node.
1378 //! <b>Effects</b>: Erases all the elements from *this
1379 //! calling Disposer::operator()(pointer), clones all the
1380 //! elements from src calling Cloner::operator()(const_reference )
1381 //! and inserts them on *this. The hash function and the equality
1382 //! predicate are copied from the source.
1384 //! If store_hash option is true, this method does not use the hash function.
1386 //! If any operation throws, all cloned elements are unlinked and disposed
1387 //! calling Disposer::operator()(pointer).
1389 //! <b>Complexity</b>: Linear to erased plus inserted elements.
1391 //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
1392 //! throws. Basic guarantee.
1393 template <class Cloner, class Disposer>
1394 void clone_from(const unordered_multiset_impl &src, Cloner cloner, Disposer disposer)
1395 { table_type::clone_from(src.table_, cloner, disposer); }
1397 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1399 //! <b>Requires</b>: value must be an lvalue
1401 //! <b>Effects</b>: Inserts value into the unordered_multiset.
1403 //! <b>Returns</b>: An iterator to the new inserted value.
1405 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1407 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
1409 //! <b>Note</b>: Does not affect the validity of iterators and references.
1410 //! No copy-constructors are called.
1411 iterator insert(reference value)
1412 { return table_type::insert_equal(value); }
1414 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
1415 //! of type value_type.
1417 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
1419 //! <b>Complexity</b>: Average case is O(N), where N is the
1420 //! size of the range.
1422 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1424 //! <b>Note</b>: Does not affect the validity of iterators and references.
1425 //! No copy-constructors are called.
1426 template<class Iterator>
1427 void insert(Iterator b, Iterator e)
1428 { table_type::insert_equal(b, e); }
1430 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1432 //! <b>Effects</b>: Erases the element pointed to by i.
1434 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1436 //! <b>Throws</b>: Nothing.
1438 //! <b>Note</b>: Invalidates the iterators (but not the references)
1439 //! to the erased element. No destructors are called.
1440 void erase(const_iterator i)
1441 { table_type::erase(i); }
1443 //! <b>Effects</b>: Erases the range pointed to by b end e.
1445 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
1446 //! worst case O(this->size()).
1448 //! <b>Throws</b>: Nothing.
1450 //! <b>Note</b>: Invalidates the iterators (but not the references)
1451 //! to the erased elements. No destructors are called.
1452 void erase(const_iterator b, const_iterator e)
1453 { table_type::erase(b, e); }
1455 //! <b>Effects</b>: Erases all the elements with the given value.
1457 //! <b>Returns</b>: The number of erased elements.
1459 //! <b>Complexity</b>: Average case O(this->count(value)).
1460 //! Worst case O(this->size()).
1462 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1464 //! <b>Note</b>: Invalidates the iterators (but not the references)
1465 //! to the erased elements. No destructors are called.
1466 size_type erase(const_reference value)
1467 { return table_type::erase(value); }
1469 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1470 //! the same hash values as the stored hasher. The difference is that
1471 //! "hash_func" hashes the given key instead of the value_type.
1473 //! "key_value_equal" must be a equality function that induces
1474 //! the same equality as key_equal. The difference is that
1475 //! "key_value_equal" compares an arbitrary key with the contained values.
1477 //! <b>Effects</b>: Erases all the elements that have the same hash and
1478 //! compare equal with the given key.
1480 //! <b>Returns</b>: The number of erased elements.
1482 //! <b>Complexity</b>: Average case O(this->count(value)).
1483 //! Worst case O(this->size()).
1485 //! <b>Throws</b>: If the hash_func or the equal_func functors throws.
1486 //! Basic guarantee.
1488 //! <b>Note</b>: Invalidates the iterators (but not the references)
1489 //! to the erased elements. No destructors are called.
1490 template<class KeyType, class KeyHasher, class KeyValueEqual>
1491 size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1492 { return table_type::erase(key, hash_func, equal_func); }
1494 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1496 //! <b>Effects</b>: Erases the element pointed to by i.
1497 //! Disposer::operator()(pointer) is called for the removed element.
1499 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1501 //! <b>Throws</b>: Nothing.
1503 //! <b>Note</b>: Invalidates the iterators
1504 //! to the erased elements.
1505 template<class Disposer>
1506 void erase_and_dispose(const_iterator i, Disposer disposer
1508 , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
1511 { table_type::erase_and_dispose(i, disposer); }
1513 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1514 template<class Disposer>
1515 void erase_and_dispose(const_iterator i, Disposer disposer)
1516 { this->erase_and_dispose(const_iterator(i), disposer); }
1519 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1521 //! <b>Effects</b>: Erases the range pointed to by b end e.
1522 //! Disposer::operator()(pointer) is called for the removed elements.
1524 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
1525 //! worst case O(this->size()).
1527 //! <b>Throws</b>: Nothing.
1529 //! <b>Note</b>: Invalidates the iterators
1530 //! to the erased elements.
1531 template<class Disposer>
1532 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
1533 { table_type::erase_and_dispose(b, e, disposer); }
1535 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1537 //! <b>Effects</b>: Erases all the elements with the given value.
1538 //! Disposer::operator()(pointer) is called for the removed elements.
1540 //! <b>Returns</b>: The number of erased elements.
1542 //! <b>Complexity</b>: Average case O(this->count(value)).
1543 //! Worst case O(this->size()).
1545 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1547 //! <b>Note</b>: Invalidates the iterators (but not the references)
1548 //! to the erased elements. No destructors are called.
1549 template<class Disposer>
1550 size_type erase_and_dispose(const_reference value, Disposer disposer)
1551 { return table_type::erase_and_dispose(value, disposer); }
1553 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1555 //! <b>Effects</b>: Erases all the elements with the given key.
1556 //! according to the comparison functor "equal_func".
1557 //! Disposer::operator()(pointer) is called for the removed elements.
1559 //! <b>Returns</b>: The number of erased elements.
1561 //! <b>Complexity</b>: Average case O(this->count(value)).
1562 //! Worst case O(this->size()).
1564 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
1566 //! <b>Note</b>: Invalidates the iterators
1567 //! to the erased elements.
1568 template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
1569 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
1570 { return table_type::erase_and_dispose(key, hash_func, equal_func, disposer); }
1572 //! <b>Effects</b>: Erases all the elements of the container.
1574 //! <b>Complexity</b>: Linear to the number of elements on the container.
1575 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1577 //! <b>Throws</b>: Nothing.
1579 //! <b>Note</b>: Invalidates the iterators (but not the references)
1580 //! to the erased elements. No destructors are called.
1582 { return table_type::clear(); }
1584 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1586 //! <b>Effects</b>: Erases all the elements of the container.
1588 //! <b>Complexity</b>: Linear to the number of elements on the container.
1589 //! Disposer::operator()(pointer) is called for the removed elements.
1591 //! <b>Throws</b>: Nothing.
1593 //! <b>Note</b>: Invalidates the iterators (but not the references)
1594 //! to the erased elements. No destructors are called.
1595 template<class Disposer>
1596 void clear_and_dispose(Disposer disposer)
1597 { return table_type::clear_and_dispose(disposer); }
1599 //! <b>Effects</b>: Returns the number of contained elements with the given key
1601 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1603 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1604 size_type count(const_reference value) const
1605 { return table_type::count(value); }
1607 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1608 //! the same hash values as the stored hasher. The difference is that
1609 //! "hash_func" hashes the given key instead of the value_type.
1611 //! "key_value_equal" must be a equality function that induces
1612 //! the same equality as key_equal. The difference is that
1613 //! "key_value_equal" compares an arbitrary key with the contained values.
1615 //! <b>Effects</b>: Returns the number of contained elements with the given key
1617 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1619 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1620 template<class KeyType, class KeyHasher, class KeyValueEqual>
1621 size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1622 { return table_type::count(key, hash_func, equal_func); }
1624 //! <b>Effects</b>: Finds an iterator to the first element whose value is
1625 //! "value" or end() if that element does not exist.
1627 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1629 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1630 iterator find(const_reference value)
1631 { return table_type::find(value); }
1633 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1634 //! the same hash values as the stored hasher. The difference is that
1635 //! "hash_func" hashes the given key instead of the value_type.
1637 //! "key_value_equal" must be a equality function that induces
1638 //! the same equality as key_equal. The difference is that
1639 //! "key_value_equal" compares an arbitrary key with the contained values.
1641 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1642 //! "key" according to the given hasher and equality functor or end() if
1643 //! that element does not exist.
1645 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1647 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1649 //! <b>Note</b>: This function is used when constructing a value_type
1650 //! is expensive and the value_type can be compared with a cheaper
1651 //! key type. Usually this key is part of the value_type.
1652 template<class KeyType, class KeyHasher, class KeyValueEqual>
1653 iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1654 { return table_type::find(key, hash_func, equal_func); }
1656 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1657 //! "key" or end() if that element does not exist.
1659 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1661 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1662 const_iterator find(const_reference value) const
1663 { return table_type::find(value); }
1665 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1666 //! the same hash values as the stored hasher. The difference is that
1667 //! "hash_func" hashes the given key instead of the value_type.
1669 //! "key_value_equal" must be a equality function that induces
1670 //! the same equality as key_equal. The difference is that
1671 //! "key_value_equal" compares an arbitrary key with the contained values.
1673 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1674 //! "key" according to the given hasher and equality functor or end() if
1675 //! that element does not exist.
1677 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1679 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1681 //! <b>Note</b>: This function is used when constructing a value_type
1682 //! is expensive and the value_type can be compared with a cheaper
1683 //! key type. Usually this key is part of the value_type.
1684 template<class KeyType, class KeyHasher, class KeyValueEqual>
1685 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1686 { return table_type::find(key, hash_func, equal_func); }
1688 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
1689 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
1692 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
1694 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1695 std::pair<iterator,iterator> equal_range(const_reference value)
1696 { return table_type::equal_range(value); }
1698 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1699 //! the same hash values as the stored hasher. The difference is that
1700 //! "hash_func" hashes the given key instead of the value_type.
1702 //! "key_value_equal" must be a equality function that induces
1703 //! the same equality as key_equal. The difference is that
1704 //! "key_value_equal" compares an arbitrary key with the contained values.
1706 //! <b>Effects</b>: Returns a range containing all elements with equivalent
1707 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
1710 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
1711 //! Worst case O(this->size()).
1713 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1715 //! <b>Note</b>: This function is used when constructing a value_type
1716 //! is expensive and the value_type can be compared with a cheaper
1717 //! key type. Usually this key is part of the value_type.
1718 template<class KeyType, class KeyHasher, class KeyValueEqual>
1719 std::pair<iterator,iterator> equal_range
1720 (const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1721 { return table_type::equal_range(key, hash_func, equal_func); }
1723 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
1724 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
1727 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
1729 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1730 std::pair<const_iterator, const_iterator>
1731 equal_range(const_reference value) const
1732 { return table_type::equal_range(value); }
1734 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1735 //! the same hash values as the stored hasher. The difference is that
1736 //! "hash_func" hashes the given key instead of the value_type.
1738 //! "key_value_equal" must be a equality function that induces
1739 //! the same equality as key_equal. The difference is that
1740 //! "key_value_equal" compares an arbitrary key with the contained values.
1742 //! <b>Effects</b>: Returns a range containing all elements with equivalent
1743 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
1746 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
1747 //! Worst case O(this->size()).
1749 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1751 //! <b>Note</b>: This function is used when constructing a value_type
1752 //! is expensive and the value_type can be compared with a cheaper
1753 //! key type. Usually this key is part of the value_type.
1754 template<class KeyType, class KeyHasher, class KeyValueEqual>
1755 std::pair<const_iterator, const_iterator>
1756 equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1757 { return table_type::equal_range(key, hash_func, equal_func); }
1759 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
1760 //! appropriate type. Otherwise the behavior is undefined.
1762 //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_multiset
1763 //! that points to the value
1765 //! <b>Complexity</b>: Constant.
1767 //! <b>Throws</b>: If the hash function throws.
1768 iterator iterator_to(reference value)
1769 { return table_type::iterator_to(value); }
1771 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
1772 //! appropriate type. Otherwise the behavior is undefined.
1774 //! <b>Effects</b>: Returns: a valid const_iterator belonging to the
1775 //! unordered_multiset that points to the value
1777 //! <b>Complexity</b>: Constant.
1779 //! <b>Throws</b>: If the hash function throws.
1780 const_iterator iterator_to(const_reference value) const
1781 { return table_type::iterator_to(value); }
1783 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1784 //! appropriate type. Otherwise the behavior is undefined.
1786 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
1787 //! that points to the value
1789 //! <b>Complexity</b>: Constant.
1791 //! <b>Throws</b>: Nothing.
1793 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1795 static local_iterator s_local_iterator_to(reference value)
1796 { return table_type::s_local_iterator_to(value); }
1798 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1799 //! appropriate type. Otherwise the behavior is undefined.
1801 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
1802 //! the unordered_set that points to the value
1804 //! <b>Complexity</b>: Constant.
1806 //! <b>Throws</b>: Nothing.
1808 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1810 static const_local_iterator s_local_iterator_to(const_reference value)
1811 { return table_type::s_local_iterator_to(value); }
1813 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1814 //! appropriate type. Otherwise the behavior is undefined.
1816 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
1817 //! that points to the value
1819 //! <b>Complexity</b>: Constant.
1821 //! <b>Throws</b>: Nothing.
1822 local_iterator local_iterator_to(reference value)
1823 { return table_type::local_iterator_to(value); }
1825 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1826 //! appropriate type. Otherwise the behavior is undefined.
1828 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
1829 //! the unordered_set that points to the value
1831 //! <b>Complexity</b>: Constant.
1833 //! <b>Throws</b>: Nothing.
1834 const_local_iterator local_iterator_to(const_reference value) const
1835 { return table_type::local_iterator_to(value); }
1837 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
1838 //! or the last rehash function.
1840 //! <b>Complexity</b>: Constant.
1842 //! <b>Throws</b>: Nothing.
1843 size_type bucket_count() const
1844 { return table_type::bucket_count(); }
1846 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1848 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
1850 //! <b>Complexity</b>: Constant.
1852 //! <b>Throws</b>: Nothing.
1853 size_type bucket_size(size_type n) const
1854 { return table_type::bucket_size(n); }
1856 //! <b>Effects</b>: Returns the index of the bucket in which elements
1857 //! with keys equivalent to k would be found, if any such element existed.
1859 //! <b>Complexity</b>: Constant.
1861 //! <b>Throws</b>: If the hash functor throws.
1863 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
1864 size_type bucket(const value_type& k) const
1865 { return table_type::bucket(k); }
1867 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1868 //! the same hash values as the stored hasher. The difference is that
1869 //! "hash_func" hashes the given key instead of the value_type.
1871 //! <b>Effects</b>: Returns the index of the bucket in which elements
1872 //! with keys equivalent to k would be found, if any such element existed.
1874 //! <b>Complexity</b>: Constant.
1876 //! <b>Throws</b>: If the hash functor throws.
1878 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
1879 template<class KeyType, class KeyHasher>
1880 size_type bucket(const KeyType& k, const KeyHasher &hash_func) const
1881 { return table_type::bucket(k, hash_func); }
1883 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
1884 //! or the last rehash function.
1886 //! <b>Complexity</b>: Constant.
1888 //! <b>Throws</b>: Nothing.
1889 bucket_ptr bucket_pointer() const
1890 { return table_type::bucket_pointer(); }
1892 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1894 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
1895 //! of the sequence stored in the bucket n.
1897 //! <b>Complexity</b>: Constant.
1899 //! <b>Throws</b>: Nothing.
1901 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1902 //! containing all of the elements in the nth bucket.
1903 local_iterator begin(size_type n)
1904 { return table_type::begin(n); }
1906 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1908 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
1909 //! of the sequence stored in the bucket n.
1911 //! <b>Complexity</b>: Constant.
1913 //! <b>Throws</b>: Nothing.
1915 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1916 //! containing all of the elements in the nth bucket.
1917 const_local_iterator begin(size_type n) const
1918 { return table_type::begin(n); }
1920 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1922 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
1923 //! of the sequence stored in the bucket n.
1925 //! <b>Complexity</b>: Constant.
1927 //! <b>Throws</b>: Nothing.
1929 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1930 //! containing all of the elements in the nth bucket.
1931 const_local_iterator cbegin(size_type n) const
1932 { return table_type::cbegin(n); }
1934 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1936 //! <b>Effects</b>: Returns a local_iterator pointing to the end
1937 //! of the sequence stored in the bucket n.
1939 //! <b>Complexity</b>: Constant.
1941 //! <b>Throws</b>: Nothing.
1943 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1944 //! containing all of the elements in the nth bucket.
1945 local_iterator end(size_type n)
1946 { return table_type::end(n); }
1948 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1950 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
1951 //! of the sequence stored in the bucket n.
1953 //! <b>Complexity</b>: Constant.
1955 //! <b>Throws</b>: Nothing.
1957 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1958 //! containing all of the elements in the nth bucket.
1959 const_local_iterator end(size_type n) const
1960 { return table_type::end(n); }
1962 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1964 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
1965 //! of the sequence stored in the bucket n.
1967 //! <b>Complexity</b>: Constant.
1969 //! <b>Throws</b>: Nothing.
1971 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1972 //! containing all of the elements in the nth bucket.
1973 const_local_iterator cend(size_type n) const
1974 { return table_type::cend(n); }
1976 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
1977 //! or the same as the old bucket array. new_size is the length of the
1978 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
1979 //! n can be bigger or smaller than this->bucket_count().
1981 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
1982 //! the values from the old bucket and inserts then in the new one.
1984 //! If store_hash option is true, this method does not use the hash function.
1986 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
1988 //! <b>Throws</b>: If the hasher functor throws.
1989 void rehash(const bucket_traits &new_bucket_traits)
1990 { table_type::rehash(new_bucket_traits); }
1992 //! <b>Requires</b>:
1996 //! <b>Complexity</b>:
2000 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
2001 bool incremental_rehash(bool grow = true)
2002 { return table_type::incremental_rehash(grow); }
2004 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
2005 bool incremental_rehash(const bucket_traits &new_bucket_traits)
2006 { return table_type::incremental_rehash(new_bucket_traits); }
2008 //! <b>Requires</b>:
2012 //! <b>Complexity</b>:
2015 size_type split_count() const
2016 { return table_type::split_count(); }
2018 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
2019 //! the container that is bigger than n. This suggestion can be used
2020 //! to create bucket arrays with a size that will usually improve
2021 //! container's performance. If such value does not exist, the
2022 //! higher possible value is returned.
2024 //! <b>Complexity</b>: Amortized constant time.
2026 //! <b>Throws</b>: Nothing.
2027 static size_type suggested_upper_bucket_count(size_type n)
2028 { return table_type::suggested_upper_bucket_count(n); }
2030 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
2031 //! the container that is smaller than n. This suggestion can be used
2032 //! to create bucket arrays with a size that will usually improve
2033 //! container's performance. If such value does not exist, the
2034 //! lower possible value is returned.
2036 //! <b>Complexity</b>: Amortized constant time.
2038 //! <b>Throws</b>: Nothing.
2039 static size_type suggested_lower_bucket_count(size_type n)
2040 { return table_type::suggested_lower_bucket_count(n); }
2042 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2045 //! Helper metafunction to define an \c unordered_multiset that yields to the same type when the
2046 //! same options (either explicitly or implicitly) are used.
2047 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2048 template<class T, class ...Options>
2050 template<class T, class O1 = void, class O2 = void
2051 , class O3 = void, class O4 = void
2052 , class O5 = void, class O6 = void
2053 , class O7 = void, class O8 = void
2054 , class O9 = void, class O10= void
2057 struct make_unordered_multiset
2060 typedef typename pack_options
2061 < hashtable_defaults,
2062 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2063 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2067 >::type packed_options;
2069 typedef typename detail::get_value_traits
2070 <T, typename packed_options::proto_value_traits>::type value_traits;
2072 typedef typename make_bucket_traits
2073 <T, true, packed_options>::type bucket_traits;
2075 typedef unordered_multiset_impl
2077 , typename packed_options::hash
2078 , typename packed_options::equal
2079 , typename packed_options::size_type
2081 , (std::size_t(false)*hash_bool_flags::unique_keys_pos)
2082 | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
2083 | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
2084 | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
2085 | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
2086 | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
2087 > implementation_defined;
2090 typedef implementation_defined type;
2093 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2095 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2096 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
2098 template<class T, class ...Options>
2100 class unordered_multiset
2101 : public make_unordered_multiset<T,
2102 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2103 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2109 typedef typename make_unordered_multiset
2111 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2112 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2117 //Assert if passed value traits are compatible with the type
2118 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
2119 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset)
2122 typedef typename Base::value_traits value_traits;
2123 typedef typename Base::bucket_traits bucket_traits;
2124 typedef typename Base::iterator iterator;
2125 typedef typename Base::const_iterator const_iterator;
2126 typedef typename Base::bucket_ptr bucket_ptr;
2127 typedef typename Base::size_type size_type;
2128 typedef typename Base::hasher hasher;
2129 typedef typename Base::key_equal key_equal;
2131 explicit unordered_multiset( const bucket_traits &b_traits
2132 , const hasher & hash_func = hasher()
2133 , const key_equal &equal_func = key_equal()
2134 , const value_traits &v_traits = value_traits())
2135 : Base(b_traits, hash_func, equal_func, v_traits)
2138 template<class Iterator>
2139 unordered_multiset( Iterator b
2141 , const bucket_traits &b_traits
2142 , const hasher & hash_func = hasher()
2143 , const key_equal &equal_func = key_equal()
2144 , const value_traits &v_traits = value_traits())
2145 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
2148 unordered_multiset(BOOST_RV_REF(unordered_multiset) x)
2149 : Base(::boost::move(static_cast<Base&>(x)))
2152 unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
2153 { return static_cast<unordered_multiset&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
2158 } //namespace intrusive
2161 #include <boost/intrusive/detail/config_end.hpp>
2163 #endif //BOOST_INTRUSIVE_UNORDERED_SET_HPP