1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2009
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
16 #include <boost/intrusive/detail/config_begin.hpp>
17 #include <boost/intrusive/intrusive_fwd.hpp>
18 #include <boost/intrusive/hashtable.hpp>
19 #include <boost/move/move.hpp>
26 //! The class template unordered_set is an intrusive container, that mimics most of
27 //! the interface of std::tr1::unordered_set as described in the C++ TR1.
29 //! unordered_set is a semi-intrusive container: each object to be stored in the
30 //! container must contain a proper hook, but the container also needs
31 //! additional auxiliary memory to work: unordered_set needs a pointer to an array
32 //! of type `bucket_type` to be passed in the constructor. This bucket array must
33 //! have at least the same lifetime as the container. This makes the use of
34 //! unordered_set more complicated than purely intrusive containers.
35 //! `bucket_type` is default-constructible, copyable and assignable
37 //! The template parameter \c T is the type to be managed by the container.
38 //! The user can specify additional options and if no options are provided
39 //! default options are used.
41 //! The container supports the following options:
42 //! \c base_hook<>/member_hook<>/value_traits<>,
43 //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
44 //! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
46 //! unordered_set only provides forward iterators but it provides 4 iterator types:
47 //! iterator and const_iterator to navigate through the whole container and
48 //! local_iterator and const_local_iterator to navigate through the values
49 //! stored in a single bucket. Local iterators are faster and smaller.
51 //! It's not recommended to use non constant-time size unordered_sets because several
52 //! key functions, like "empty()", become non-constant time functions. Non
53 //! constant-time size unordered_sets are mainly provided to support auto-unlink hooks.
55 //! unordered_set, unlike std::unordered_set, does not make automatic rehashings nor
56 //! offers functions related to a load factor. Rehashing can be explicitly requested
57 //! and the user must provide a new bucket array that will be used from that moment.
59 //! Since no automatic rehashing is done, iterators are never invalidated when
60 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
61 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
62 template<class T, class ...Options>
64 template<class Config>
66 class unordered_set_impl
70 typedef hashtable_impl<Config> table_type;
74 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set_impl)
76 typedef table_type implementation_defined;
80 typedef typename implementation_defined::value_type value_type;
81 typedef typename implementation_defined::value_traits value_traits;
82 typedef typename implementation_defined::bucket_traits bucket_traits;
83 typedef typename implementation_defined::pointer pointer;
84 typedef typename implementation_defined::const_pointer const_pointer;
85 typedef typename implementation_defined::reference reference;
86 typedef typename implementation_defined::const_reference const_reference;
87 typedef typename implementation_defined::difference_type difference_type;
88 typedef typename implementation_defined::size_type size_type;
89 typedef typename implementation_defined::key_type key_type;
90 typedef typename implementation_defined::key_equal key_equal;
91 typedef typename implementation_defined::hasher hasher;
92 typedef typename implementation_defined::bucket_type bucket_type;
93 typedef typename implementation_defined::bucket_ptr bucket_ptr;
94 typedef typename implementation_defined::iterator iterator;
95 typedef typename implementation_defined::const_iterator const_iterator;
96 typedef typename implementation_defined::insert_commit_data insert_commit_data;
97 typedef typename implementation_defined::local_iterator local_iterator;
98 typedef typename implementation_defined::const_local_iterator const_local_iterator;
99 typedef typename implementation_defined::node_traits node_traits;
100 typedef typename implementation_defined::node node;
101 typedef typename implementation_defined::node_ptr node_ptr;
102 typedef typename implementation_defined::const_node_ptr const_node_ptr;
103 typedef typename implementation_defined::node_algorithms node_algorithms;
112 //! <b>Requires</b>: buckets must not be being used by any other resource.
114 //! <b>Effects</b>: Constructs an empty unordered_set_impl, storing a reference
115 //! to the bucket array and copies of the hasher and equal functors.
117 //! <b>Complexity</b>: Constant.
119 //! <b>Throws</b>: If value_traits::node_traits::node
120 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
121 //! or the copy constructor or invocation of Hash or Equal throws.
123 //! <b>Notes</b>: buckets array must be disposed only after
124 //! *this is disposed.
125 unordered_set_impl( const bucket_traits &b_traits
126 , const hasher & hash_func = hasher()
127 , const key_equal &equal_func = key_equal()
128 , const value_traits &v_traits = value_traits())
129 : table_(b_traits, hash_func, equal_func, v_traits)
132 //! <b>Requires</b>: buckets must not be being used by any other resource
133 //! and Dereferencing iterator must yield an lvalue of type value_type.
135 //! <b>Effects</b>: Constructs an empty unordered_set and inserts elements from
138 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
139 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
141 //! <b>Throws</b>: If value_traits::node_traits::node
142 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
143 //! or the copy constructor or invocation of hasher or key_equal throws.
145 //! <b>Notes</b>: buckets array must be disposed only after
146 //! *this is disposed.
147 template<class Iterator>
148 unordered_set_impl( Iterator b
150 , const bucket_traits &b_traits
151 , const hasher & hash_func = hasher()
152 , const key_equal &equal_func = key_equal()
153 , const value_traits &v_traits = value_traits())
154 : table_(b_traits, hash_func, equal_func, v_traits)
155 { table_.insert_unique(b, e); }
157 //! <b>Effects</b>: to-do
159 unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x)
160 : table_(::boost::move(x.table_))
163 //! <b>Effects</b>: to-do
165 unordered_set_impl& operator=(BOOST_RV_REF(unordered_set_impl) x)
166 { table_ = ::boost::move(x.table_); return *this; }
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_.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_.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_.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_.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_.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_.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_.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_.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_.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_.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_.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_.clone_from(src.table_, cloner, disposer); }
302 //! <b>Requires</b>: value must be an lvalue
304 //! <b>Effects</b>: Tries to inserts value into the unordered_set.
306 //! <b>Returns</b>: If the value
307 //! is not already present inserts it and returns a pair containing the
308 //! iterator to the new value and true. If there is an equivalent value
309 //! returns a pair containing an iterator to the already present value
312 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
314 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
316 //! <b>Note</b>: Does not affect the validity of iterators and references.
317 //! No copy-constructors are called.
318 std::pair<iterator, bool> insert(reference value)
319 { return table_.insert_unique(value); }
321 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
322 //! of type value_type.
324 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
326 //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e).
327 //! Worst case O(N*this->size()).
329 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
331 //! <b>Note</b>: Does not affect the validity of iterators and references.
332 //! No copy-constructors are called.
333 template<class Iterator>
334 void insert(Iterator b, Iterator e)
335 { table_.insert_unique(b, e); }
337 //! <b>Requires</b>: "hasher" must be a hash function that induces
338 //! the same hash values as the stored hasher. The difference is that
339 //! "hasher" hashes the given key instead of the value_type.
341 //! "key_value_equal" must be a equality function that induces
342 //! the same equality as key_equal. The difference is that
343 //! "key_value_equal" compares an arbitrary key with the contained values.
345 //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using
346 //! a user provided key instead of the value itself.
348 //! <b>Returns</b>: If there is an equivalent value
349 //! returns a pair containing an iterator to the already present value
350 //! and false. If the value can be inserted returns true in the returned
351 //! pair boolean and fills "commit_data" that is meant to be used with
352 //! the "insert_commit" function.
354 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
356 //! <b>Throws</b>: If hasher or key_value_equal throw. Strong guarantee.
358 //! <b>Notes</b>: This function is used to improve performance when constructing
359 //! a value_type is expensive: if there is an equivalent value
360 //! the constructed object must be discarded. Many times, the part of the
361 //! node that is used to impose the hash or the equality is much cheaper to
362 //! construct than the value_type and this function offers the possibility to
363 //! use that the part to check if the insertion will be successful.
365 //! If the check is successful, the user can construct the value_type and use
366 //! "insert_commit" to insert the object in constant-time.
368 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
369 //! objects are inserted or erased from the unordered_set.
371 //! After a successful rehashing insert_commit_data remains valid.
372 template<class KeyType, class KeyHasher, class KeyValueEqual>
373 std::pair<iterator, bool> insert_check
374 (const KeyType &key, KeyHasher hasher, KeyValueEqual key_value_equal, insert_commit_data &commit_data)
375 { return table_.insert_unique_check(key, hasher, key_value_equal, commit_data); }
377 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
378 //! must have been obtained from a previous call to "insert_check".
379 //! No objects should have been inserted or erased from the unordered_set between
380 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
382 //! <b>Effects</b>: Inserts the value in the unordered_set using the information obtained
383 //! from the "commit_data" that a previous "insert_check" filled.
385 //! <b>Returns</b>: An iterator to the newly inserted object.
387 //! <b>Complexity</b>: Constant time.
389 //! <b>Throws</b>: Nothing.
391 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
392 //! previously executed to fill "commit_data". No value should be inserted or
393 //! erased between the "insert_check" and "insert_commit" calls.
395 //! After a successful rehashing insert_commit_data remains valid.
396 iterator insert_commit(reference value, const insert_commit_data &commit_data)
397 { return table_.insert_unique_commit(value, commit_data); }
399 //! <b>Effects</b>: Erases the element pointed to by i.
401 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
403 //! <b>Throws</b>: Nothing.
405 //! <b>Note</b>: Invalidates the iterators (but not the references)
406 //! to the erased element. No destructors are called.
407 void erase(const_iterator i)
410 //! <b>Effects</b>: Erases the range pointed to by b end e.
412 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
413 //! worst case O(this->size()).
415 //! <b>Throws</b>: Nothing.
417 //! <b>Note</b>: Invalidates the iterators (but not the references)
418 //! to the erased elements. No destructors are called.
419 void erase(const_iterator b, const_iterator e)
420 { table_.erase(b, e); }
422 //! <b>Effects</b>: Erases all the elements with the given value.
424 //! <b>Returns</b>: The number of erased elements.
426 //! <b>Complexity</b>: Average case O(this->count(value)).
427 //! Worst case O(this->size()).
429 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
431 //! <b>Note</b>: Invalidates the iterators (but not the references)
432 //! to the erased elements. No destructors are called.
433 size_type erase(const_reference value)
434 { return table_.erase(value); }
436 //! <b>Requires</b>: "hasher" must be a hash function that induces
437 //! the same hash values as the stored hasher. The difference is that
438 //! "hasher" hashes the given key instead of the value_type.
440 //! "key_value_equal" must be a equality function that induces
441 //! the same equality as key_equal. The difference is that
442 //! "key_value_equal" compares an arbitrary key with the contained values.
444 //! <b>Effects</b>: Erases all the elements that have the same hash and
445 //! compare equal with the given key.
447 //! <b>Returns</b>: The number of erased elements.
449 //! <b>Complexity</b>: Average case O(this->count(value)).
450 //! Worst case O(this->size()).
452 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
454 //! <b>Note</b>: Invalidates the iterators (but not the references)
455 //! to the erased elements. No destructors are called.
456 template<class KeyType, class KeyHasher, class KeyValueEqual>
457 size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
458 { return table_.erase(key, hash_func, equal_func); }
460 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
462 //! <b>Effects</b>: Erases the element pointed to by i.
463 //! Disposer::operator()(pointer) is called for the removed element.
465 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
467 //! <b>Throws</b>: Nothing.
469 //! <b>Note</b>: Invalidates the iterators
470 //! to the erased elements.
471 template<class Disposer>
472 void erase_and_dispose(const_iterator i, Disposer disposer
474 , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
477 { table_.erase_and_dispose(i, disposer); }
479 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
481 //! <b>Effects</b>: Erases the range pointed to by b end e.
482 //! Disposer::operator()(pointer) is called for the removed elements.
484 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
485 //! worst case O(this->size()).
487 //! <b>Throws</b>: Nothing.
489 //! <b>Note</b>: Invalidates the iterators
490 //! to the erased elements.
491 template<class Disposer>
492 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
493 { table_.erase_and_dispose(b, e, disposer); }
495 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
497 //! <b>Effects</b>: Erases all the elements with the given value.
498 //! Disposer::operator()(pointer) is called for the removed elements.
500 //! <b>Returns</b>: The number of erased elements.
502 //! <b>Complexity</b>: Average case O(this->count(value)).
503 //! Worst case O(this->size()).
505 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
507 //! <b>Note</b>: Invalidates the iterators (but not the references)
508 //! to the erased elements. No destructors are called.
509 template<class Disposer>
510 size_type erase_and_dispose(const_reference value, Disposer disposer)
511 { return table_.erase_and_dispose(value, disposer); }
513 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
515 //! <b>Effects</b>: Erases all the elements with the given key.
516 //! according to the comparison functor "equal_func".
517 //! Disposer::operator()(pointer) is called for the removed elements.
519 //! <b>Returns</b>: The number of erased elements.
521 //! <b>Complexity</b>: Average case O(this->count(value)).
522 //! Worst case O(this->size()).
524 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
526 //! <b>Note</b>: Invalidates the iterators
527 //! to the erased elements.
528 template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
529 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
530 { return table_.erase_and_dispose(key, hash_func, equal_func, disposer); }
532 //! <b>Effects</b>: Erases all of the elements.
534 //! <b>Complexity</b>: Linear to the number of elements on the container.
535 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
537 //! <b>Throws</b>: Nothing.
539 //! <b>Note</b>: Invalidates the iterators (but not the references)
540 //! to the erased elements. No destructors are called.
542 { return table_.clear(); }
544 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
546 //! <b>Effects</b>: Erases all of the elements.
548 //! <b>Complexity</b>: Linear to the number of elements on the container.
549 //! Disposer::operator()(pointer) is called for the removed elements.
551 //! <b>Throws</b>: Nothing.
553 //! <b>Note</b>: Invalidates the iterators (but not the references)
554 //! to the erased elements. No destructors are called.
555 template<class Disposer>
556 void clear_and_dispose(Disposer disposer)
557 { return table_.clear_and_dispose(disposer); }
559 //! <b>Effects</b>: Returns the number of contained elements with the given value
561 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
563 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
564 size_type count(const_reference value) const
565 { return table_.find(value) != end(); }
567 //! <b>Requires</b>: "hash_func" must be a hash function that induces
568 //! the same hash values as the stored hasher. The difference is that
569 //! "hash_func" hashes the given key instead of the value_type.
571 //! "equal_func" must be a equality function that induces
572 //! the same equality as key_equal. The difference is that
573 //! "equal_func" compares an arbitrary key with the contained values.
575 //! <b>Effects</b>: Returns the number of contained elements with the given key
577 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
579 //! <b>Throws</b>: If hash_func or equal_func throw.
580 template<class KeyType, class KeyHasher, class KeyValueEqual>
581 size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
582 { return table_.find(key, hash_func, equal_func) != end(); }
584 //! <b>Effects</b>: Finds an iterator to the first element is equal to
585 //! "value" or end() if that element does not exist.
587 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
589 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
590 iterator find(const_reference value)
591 { return table_.find(value); }
593 //! <b>Requires</b>: "hash_func" must be a hash function that induces
594 //! the same hash values as the stored hasher. The difference is that
595 //! "hash_func" hashes the given key instead of the value_type.
597 //! "equal_func" must be a equality function that induces
598 //! the same equality as key_equal. The difference is that
599 //! "equal_func" compares an arbitrary key with the contained values.
601 //! <b>Effects</b>: Finds an iterator to the first element whose key is
602 //! "key" according to the given hasher and equality functor or end() if
603 //! that element does not exist.
605 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
607 //! <b>Throws</b>: If hash_func or equal_func throw.
609 //! <b>Note</b>: This function is used when constructing a value_type
610 //! is expensive and the value_type can be compared with a cheaper
611 //! key type. Usually this key is part of the value_type.
612 template<class KeyType, class KeyHasher, class KeyValueEqual>
613 iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
614 { return table_.find(key, hash_func, equal_func); }
616 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
617 //! "key" or end() if that element does not exist.
619 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
621 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
622 const_iterator find(const_reference value) const
623 { return table_.find(value); }
625 //! <b>Requires</b>: "hash_func" must be a hash function that induces
626 //! the same hash values as the stored hasher. The difference is that
627 //! "hash_func" hashes the given key instead of the value_type.
629 //! "equal_func" must be a equality function that induces
630 //! the same equality as key_equal. The difference is that
631 //! "equal_func" compares an arbitrary key with the contained values.
633 //! <b>Effects</b>: Finds an iterator to the first element whose key is
634 //! "key" according to the given hasher and equality functor or end() if
635 //! that element does not exist.
637 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
639 //! <b>Throws</b>: If hash_func or equal_func throw.
641 //! <b>Note</b>: This function is used when constructing a value_type
642 //! is expensive and the value_type can be compared with a cheaper
643 //! key type. Usually this key is part of the value_type.
644 template<class KeyType, class KeyHasher, class KeyValueEqual>
645 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
646 { return table_.find(key, hash_func, equal_func); }
648 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
649 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
652 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
654 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
655 std::pair<iterator,iterator> equal_range(const_reference value)
656 { return table_.equal_range(value); }
658 //! <b>Requires</b>: "hash_func" must be a hash function that induces
659 //! the same hash values as the stored hasher. The difference is that
660 //! "hash_func" hashes the given key instead of the value_type.
662 //! "equal_func" must be a equality function that induces
663 //! the same equality as key_equal. The difference is that
664 //! "equal_func" compares an arbitrary key with the contained values.
666 //! <b>Effects</b>: Returns a range containing all elements with equivalent
667 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
670 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, hash_func)).
671 //! Worst case O(this->size()).
673 //! <b>Throws</b>: If hash_func or the equal_func throw.
675 //! <b>Note</b>: This function is used when constructing a value_type
676 //! is expensive and the value_type can be compared with a cheaper
677 //! key type. Usually this key is part of the value_type.
678 template<class KeyType, class KeyHasher, class KeyValueEqual>
679 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
680 { return table_.equal_range(key, hash_func, equal_func); }
682 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
683 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
686 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
688 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
689 std::pair<const_iterator, const_iterator>
690 equal_range(const_reference value) const
691 { return table_.equal_range(value); }
693 //! <b>Requires</b>: "hash_func" must be a hash function that induces
694 //! the same hash values as the stored hasher. The difference is that
695 //! "hash_func" hashes the given key instead of the value_type.
697 //! "equal_func" must be a equality function that induces
698 //! the same equality as key_equal. The difference is that
699 //! "equal_func" compares an arbitrary key with the contained values.
701 //! <b>Effects</b>: Returns a range containing all elements with equivalent
702 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
705 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
706 //! Worst case O(this->size()).
708 //! <b>Throws</b>: If the hash_func or equal_func throw.
710 //! <b>Note</b>: This function is used when constructing a value_type
711 //! is expensive and the value_type can be compared with a cheaper
712 //! key type. Usually this key is part of the value_type.
713 template<class KeyType, class KeyHasher, class KeyValueEqual>
714 std::pair<const_iterator, const_iterator>
715 equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
716 { return table_.equal_range(key, hash_func, equal_func); }
718 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
719 //! appropriate type. Otherwise the behavior is undefined.
721 //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_set
722 //! that points to the value
724 //! <b>Complexity</b>: Constant.
726 //! <b>Throws</b>: If the internal hash function throws.
727 iterator iterator_to(reference value)
728 { return table_.iterator_to(value); }
730 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
731 //! appropriate type. Otherwise the behavior is undefined.
733 //! <b>Effects</b>: Returns: a valid const_iterator belonging to the
734 //! unordered_set that points to the value
736 //! <b>Complexity</b>: Constant.
738 //! <b>Throws</b>: If the internal hash function throws.
739 const_iterator iterator_to(const_reference value) const
740 { return table_.iterator_to(value); }
742 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
743 //! appropriate type. Otherwise the behavior is undefined.
745 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
746 //! that points to the value
748 //! <b>Complexity</b>: Constant.
750 //! <b>Throws</b>: Nothing.
752 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
754 static local_iterator s_local_iterator_to(reference value)
755 { return table_type::s_local_iterator_to(value); }
757 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
758 //! appropriate type. Otherwise the behavior is undefined.
760 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
761 //! the unordered_set that points to the value
763 //! <b>Complexity</b>: Constant.
765 //! <b>Throws</b>: Nothing.
767 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
769 static const_local_iterator s_local_iterator_to(const_reference value)
770 { return table_type::s_local_iterator_to(value); }
772 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
773 //! appropriate type. Otherwise the behavior is undefined.
775 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
776 //! that points to the value
778 //! <b>Complexity</b>: Constant.
780 //! <b>Throws</b>: Nothing.
781 local_iterator local_iterator_to(reference value)
782 { return table_.local_iterator_to(value); }
784 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
785 //! appropriate type. Otherwise the behavior is undefined.
787 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
788 //! the unordered_set that points to the value
790 //! <b>Complexity</b>: Constant.
792 //! <b>Throws</b>: Nothing.
793 const_local_iterator local_iterator_to(const_reference value) const
794 { return table_.local_iterator_to(value); }
796 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
797 //! or the last rehash function.
799 //! <b>Complexity</b>: Constant.
801 //! <b>Throws</b>: Nothing.
802 size_type bucket_count() const
803 { return table_.bucket_count(); }
805 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
807 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
809 //! <b>Complexity</b>: Constant.
811 //! <b>Throws</b>: Nothing.
812 size_type bucket_size(size_type n) const
813 { return table_.bucket_size(n); }
815 //! <b>Effects</b>: Returns the index of the bucket in which elements
816 //! with keys equivalent to k would be found, if any such element existed.
818 //! <b>Complexity</b>: Constant.
820 //! <b>Throws</b>: If the hash functor throws.
822 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
823 size_type bucket(const value_type& k) const
824 { return table_.bucket(k); }
826 //! <b>Requires</b>: "hash_func" must be a hash function that induces
827 //! the same hash values as the stored hasher. The difference is that
828 //! "hash_func" hashes the given key instead of the value_type.
830 //! <b>Effects</b>: Returns the index of the bucket in which elements
831 //! with keys equivalent to k would be found, if any such element existed.
833 //! <b>Complexity</b>: Constant.
835 //! <b>Throws</b>: If hash_func throws.
837 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
838 template<class KeyType, class KeyHasher>
839 size_type bucket(const KeyType& k, KeyHasher hash_func) const
840 { return table_.bucket(k, hash_func); }
842 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
843 //! or the last rehash function.
845 //! <b>Complexity</b>: Constant.
847 //! <b>Throws</b>: Nothing.
848 bucket_ptr bucket_pointer() const
849 { return table_.bucket_pointer(); }
851 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
853 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
854 //! of the sequence stored in the bucket n.
856 //! <b>Complexity</b>: Constant.
858 //! <b>Throws</b>: Nothing.
860 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
861 //! containing all of the elements in the nth bucket.
862 local_iterator begin(size_type n)
863 { return table_.begin(n); }
865 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
867 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
868 //! of the sequence stored in the bucket n.
870 //! <b>Complexity</b>: Constant.
872 //! <b>Throws</b>: Nothing.
874 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
875 //! containing all of the elements in the nth bucket.
876 const_local_iterator begin(size_type n) const
877 { return table_.begin(n); }
879 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
881 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
882 //! of the sequence stored in the bucket n.
884 //! <b>Complexity</b>: Constant.
886 //! <b>Throws</b>: Nothing.
888 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
889 //! containing all of the elements in the nth bucket.
890 const_local_iterator cbegin(size_type n) const
891 { return table_.cbegin(n); }
893 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
895 //! <b>Effects</b>: Returns a local_iterator pointing to the end
896 //! of the sequence stored in the bucket n.
898 //! <b>Complexity</b>: Constant.
900 //! <b>Throws</b>: Nothing.
902 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
903 //! containing all of the elements in the nth bucket.
904 local_iterator end(size_type n)
905 { return table_.end(n); }
907 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
909 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
910 //! of the sequence stored in the bucket n.
912 //! <b>Complexity</b>: Constant.
914 //! <b>Throws</b>: Nothing.
916 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
917 //! containing all of the elements in the nth bucket.
918 const_local_iterator end(size_type n) const
919 { return table_.end(n); }
921 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
923 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
924 //! of the sequence stored in the bucket n.
926 //! <b>Complexity</b>: Constant.
928 //! <b>Throws</b>: Nothing.
930 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
931 //! containing all of the elements in the nth bucket.
932 const_local_iterator cend(size_type n) const
933 { return table_.cend(n); }
935 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
936 //! or the same as the old bucket array. new_size is the length of the
937 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
938 //! n can be bigger or smaller than this->bucket_count().
940 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
941 //! the values from the old bucket and inserts then in the new one.
943 //! If store_hash option is true, this method does not use the hash function.
945 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
947 //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
948 void rehash(const bucket_traits &new_bucket_traits)
949 { table_.rehash(new_bucket_traits); }
955 //! <b>Complexity</b>:
959 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
960 bool incremental_rehash(bool grow = true)
961 { return table_.incremental_rehash(grow); }
963 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
964 bool incremental_rehash(const bucket_traits &new_bucket_traits)
965 { return table_.incremental_rehash(new_bucket_traits); }
971 //! <b>Complexity</b>:
974 size_type split_count() const
975 { return table_.split_count(); }
977 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
978 //! the container that is bigger than n. This suggestion can be used
979 //! to create bucket arrays with a size that will usually improve
980 //! container's performance. If such value does not exist, the
981 //! higher possible value is returned.
983 //! <b>Complexity</b>: Amortized constant time.
985 //! <b>Throws</b>: Nothing.
986 static size_type suggested_upper_bucket_count(size_type n)
987 { return table_type::suggested_upper_bucket_count(n); }
989 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
990 //! the container that is smaller than n. This suggestion can be used
991 //! to create bucket arrays with a size that will usually improve
992 //! container's performance. If such value does not exist, the
993 //! lower possible value is returned.
995 //! <b>Complexity</b>: Amortized constant time.
997 //! <b>Throws</b>: Nothing.
998 static size_type suggested_lower_bucket_count(size_type n)
999 { return table_type::suggested_lower_bucket_count(n); }
1002 //! Helper metafunction to define an \c unordered_set that yields to the same type when the
1003 //! same options (either explicitly or implicitly) are used.
1004 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1005 template<class T, class ...Options>
1007 template<class T, class O1 = none, class O2 = none
1008 , class O3 = none, class O4 = none
1009 , class O5 = none, class O6 = none
1010 , class O7 = none, class O8 = none
1011 , class O9 = none, class O10= none
1014 struct make_unordered_set
1017 typedef unordered_set_impl
1018 < typename make_hashtable_opt
1020 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1021 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1026 > implementation_defined;
1028 typedef implementation_defined type;
1031 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1033 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1034 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
1036 template<class T, class ...Options>
1039 : public make_unordered_set<T,
1040 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1041 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1047 typedef typename make_unordered_set
1049 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1050 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
1056 //Assert if passed value traits are compatible with the type
1057 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
1058 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_set)
1061 typedef typename Base::value_traits value_traits;
1062 typedef typename Base::bucket_traits bucket_traits;
1063 typedef typename Base::iterator iterator;
1064 typedef typename Base::const_iterator const_iterator;
1065 typedef typename Base::bucket_ptr bucket_ptr;
1066 typedef typename Base::size_type size_type;
1067 typedef typename Base::hasher hasher;
1068 typedef typename Base::key_equal key_equal;
1070 unordered_set ( const bucket_traits &b_traits
1071 , const hasher & hash_func = hasher()
1072 , const key_equal &equal_func = key_equal()
1073 , const value_traits &v_traits = value_traits())
1074 : Base(b_traits, hash_func, equal_func, v_traits)
1077 template<class Iterator>
1078 unordered_set ( Iterator b
1080 , const bucket_traits &b_traits
1081 , const hasher & hash_func = hasher()
1082 , const key_equal &equal_func = key_equal()
1083 , const value_traits &v_traits = value_traits())
1084 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
1087 unordered_set(BOOST_RV_REF(unordered_set) x)
1088 : Base(::boost::move(static_cast<Base&>(x)))
1091 unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
1092 { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
1098 //! The class template unordered_multiset is an intrusive container, that mimics most of
1099 //! the interface of std::tr1::unordered_multiset as described in the C++ TR1.
1101 //! unordered_multiset is a semi-intrusive container: each object to be stored in the
1102 //! container must contain a proper hook, but the container also needs
1103 //! additional auxiliary memory to work: unordered_multiset needs a pointer to an array
1104 //! of type `bucket_type` to be passed in the constructor. This bucket array must
1105 //! have at least the same lifetime as the container. This makes the use of
1106 //! unordered_multiset more complicated than purely intrusive containers.
1107 //! `bucket_type` is default-constructible, copyable and assignable
1109 //! The template parameter \c T is the type to be managed by the container.
1110 //! The user can specify additional options and if no options are provided
1111 //! default options are used.
1113 //! The container supports the following options:
1114 //! \c base_hook<>/member_hook<>/value_traits<>,
1115 //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
1116 //! \c bucket_traits<>, \c power_2_buckets<> and \c cache_begin<>.
1118 //! unordered_multiset only provides forward iterators but it provides 4 iterator types:
1119 //! iterator and const_iterator to navigate through the whole container and
1120 //! local_iterator and const_local_iterator to navigate through the values
1121 //! stored in a single bucket. Local iterators are faster and smaller.
1123 //! It's not recommended to use non constant-time size unordered_multisets because several
1124 //! key functions, like "empty()", become non-constant time functions. Non
1125 //! constant-time size unordered_multisets are mainly provided to support auto-unlink hooks.
1127 //! unordered_multiset, unlike std::unordered_set, does not make automatic rehashings nor
1128 //! offers functions related to a load factor. Rehashing can be explicitly requested
1129 //! and the user must provide a new bucket array that will be used from that moment.
1131 //! Since no automatic rehashing is done, iterators are never invalidated when
1132 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
1133 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1134 template<class T, class ...Options>
1136 template<class Config>
1138 class unordered_multiset_impl
1142 typedef hashtable_impl<Config> table_type;
1146 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset_impl)
1148 typedef table_type implementation_defined;
1151 typedef typename implementation_defined::value_type value_type;
1152 typedef typename implementation_defined::value_traits value_traits;
1153 typedef typename implementation_defined::bucket_traits bucket_traits;
1154 typedef typename implementation_defined::pointer pointer;
1155 typedef typename implementation_defined::const_pointer const_pointer;
1156 typedef typename implementation_defined::reference reference;
1157 typedef typename implementation_defined::const_reference const_reference;
1158 typedef typename implementation_defined::difference_type difference_type;
1159 typedef typename implementation_defined::size_type size_type;
1160 typedef typename implementation_defined::key_type key_type;
1161 typedef typename implementation_defined::key_equal key_equal;
1162 typedef typename implementation_defined::hasher hasher;
1163 typedef typename implementation_defined::bucket_type bucket_type;
1164 typedef typename implementation_defined::bucket_ptr bucket_ptr;
1165 typedef typename implementation_defined::iterator iterator;
1166 typedef typename implementation_defined::const_iterator const_iterator;
1167 typedef typename implementation_defined::insert_commit_data insert_commit_data;
1168 typedef typename implementation_defined::local_iterator local_iterator;
1169 typedef typename implementation_defined::const_local_iterator const_local_iterator;
1170 typedef typename implementation_defined::node_traits node_traits;
1171 typedef typename implementation_defined::node node;
1172 typedef typename implementation_defined::node_ptr node_ptr;
1173 typedef typename implementation_defined::const_node_ptr const_node_ptr;
1174 typedef typename implementation_defined::node_algorithms node_algorithms;
1183 //! <b>Requires</b>: buckets must not be being used by any other resource.
1185 //! <b>Effects</b>: Constructs an empty unordered_multiset, storing a reference
1186 //! to the bucket array and copies of the hasher and equal functors.
1188 //! <b>Complexity</b>: Constant.
1190 //! <b>Throws</b>: If value_traits::node_traits::node
1191 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1192 //! or the copy constructor or invocation of Hash or Equal throws.
1194 //! <b>Notes</b>: buckets array must be disposed only after
1195 //! *this is disposed.
1196 unordered_multiset_impl ( const bucket_traits &b_traits
1197 , const hasher & hash_func = hasher()
1198 , const key_equal &equal_func = key_equal()
1199 , const value_traits &v_traits = value_traits())
1200 : table_(b_traits, hash_func, equal_func, v_traits)
1203 //! <b>Requires</b>: buckets must not be being used by any other resource
1204 //! and Dereferencing iterator must yield an lvalue of type value_type.
1206 //! <b>Effects</b>: Constructs an empty unordered_multiset and inserts elements from
1209 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
1210 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
1212 //! <b>Throws</b>: If value_traits::node_traits::node
1213 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1214 //! or the copy constructor or invocation of hasher or key_equal throws.
1216 //! <b>Notes</b>: buckets array must be disposed only after
1217 //! *this is disposed.
1218 template<class Iterator>
1219 unordered_multiset_impl ( Iterator b
1221 , const bucket_traits &b_traits
1222 , const hasher & hash_func = hasher()
1223 , const key_equal &equal_func = key_equal()
1224 , const value_traits &v_traits = value_traits())
1225 : table_(b_traits, hash_func, equal_func, v_traits)
1226 { table_.insert_equal(b, e); }
1228 //! <b>Effects</b>: to-do
1230 unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x)
1231 : table_(::boost::move(x.table_))
1234 //! <b>Effects</b>: to-do
1236 unordered_multiset_impl& operator=(BOOST_RV_REF(unordered_multiset_impl) x)
1237 { table_ = ::boost::move(x.table_); return *this; }
1239 //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_multiset
1240 //! are not deleted (i.e. no destructors are called).
1242 //! <b>Complexity</b>: Linear to the number of elements in the unordered_multiset, if
1243 //! it's a safe-mode or auto-unlink value. Otherwise constant.
1245 //! <b>Throws</b>: Nothing.
1246 ~unordered_multiset_impl()
1249 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_multiset.
1251 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1252 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1254 //! <b>Throws</b>: Nothing.
1256 { return table_.begin(); }
1258 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
1259 //! of the unordered_multiset.
1261 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1262 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1264 //! <b>Throws</b>: Nothing.
1265 const_iterator begin() const
1266 { return table_.begin(); }
1268 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
1269 //! of the unordered_multiset.
1271 //! <b>Complexity</b>: Constant time if `cache_begin<>` is true. Amortized
1272 //! constant time with worst case (empty unordered_set) O(this->bucket_count())
1274 //! <b>Throws</b>: Nothing.
1275 const_iterator cbegin() const
1276 { return table_.cbegin(); }
1278 //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_multiset.
1280 //! <b>Complexity</b>: Constant.
1282 //! <b>Throws</b>: Nothing.
1284 { return table_.end(); }
1286 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
1288 //! <b>Complexity</b>: Constant.
1290 //! <b>Throws</b>: Nothing.
1291 const_iterator end() const
1292 { return table_.end(); }
1294 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
1296 //! <b>Complexity</b>: Constant.
1298 //! <b>Throws</b>: Nothing.
1299 const_iterator cend() const
1300 { return table_.cend(); }
1302 //! <b>Effects</b>: Returns the hasher object used by the unordered_set.
1304 //! <b>Complexity</b>: Constant.
1306 //! <b>Throws</b>: If hasher copy-constructor throws.
1307 hasher hash_function() const
1308 { return table_.hash_function(); }
1310 //! <b>Effects</b>: Returns the key_equal object used by the unordered_multiset.
1312 //! <b>Complexity</b>: Constant.
1314 //! <b>Throws</b>: If key_equal copy-constructor throws.
1315 key_equal key_eq() const
1316 { return table_.key_eq(); }
1318 //! <b>Effects</b>: Returns true if the container is empty.
1320 //! <b>Complexity</b>: if constant-time size and cache_last options are disabled,
1321 //! average constant time (worst case, with empty() == true: O(this->bucket_count()).
1322 //! Otherwise constant.
1324 //! <b>Throws</b>: Nothing.
1326 { return table_.empty(); }
1328 //! <b>Effects</b>: Returns the number of elements stored in the unordered_multiset.
1330 //! <b>Complexity</b>: Linear to elements contained in *this if
1331 //! constant-time size option is disabled. Constant-time otherwise.
1333 //! <b>Throws</b>: Nothing.
1334 size_type size() const
1335 { return table_.size(); }
1337 //! <b>Requires</b>: the hasher and the equality function unqualified swap
1338 //! call should not throw.
1340 //! <b>Effects</b>: Swaps the contents of two unordered_multisets.
1341 //! Swaps also the contained bucket array and equality and hasher functors.
1344 //! <b>Complexity</b>: Constant.
1346 //! <b>Throws</b>: If the swap() call for the comparison or hash functors
1347 //! found using ADL throw. Basic guarantee.
1348 void swap(unordered_multiset_impl& other)
1349 { table_.swap(other.table_); }
1351 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1352 //! Cloner should yield to nodes that compare equal and produce the same
1353 //! hash than the original node.
1355 //! <b>Effects</b>: Erases all the elements from *this
1356 //! calling Disposer::operator()(pointer), clones all the
1357 //! elements from src calling Cloner::operator()(const_reference )
1358 //! and inserts them on *this. The hash function and the equality
1359 //! predicate are copied from the source.
1361 //! If store_hash option is true, this method does not use the hash function.
1363 //! If any operation throws, all cloned elements are unlinked and disposed
1364 //! calling Disposer::operator()(pointer).
1366 //! <b>Complexity</b>: Linear to erased plus inserted elements.
1368 //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
1369 //! throws. Basic guarantee.
1370 template <class Cloner, class Disposer>
1371 void clone_from(const unordered_multiset_impl &src, Cloner cloner, Disposer disposer)
1372 { table_.clone_from(src.table_, cloner, disposer); }
1374 //! <b>Requires</b>: value must be an lvalue
1376 //! <b>Effects</b>: Inserts value into the unordered_multiset.
1378 //! <b>Returns</b>: An iterator to the new inserted value.
1380 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1382 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
1384 //! <b>Note</b>: Does not affect the validity of iterators and references.
1385 //! No copy-constructors are called.
1386 iterator insert(reference value)
1387 { return table_.insert_equal(value); }
1389 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
1390 //! of type value_type.
1392 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
1394 //! <b>Complexity</b>: Average case is O(N), where N is the
1395 //! size of the range.
1397 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1399 //! <b>Note</b>: Does not affect the validity of iterators and references.
1400 //! No copy-constructors are called.
1401 template<class Iterator>
1402 void insert(Iterator b, Iterator e)
1403 { table_.insert_equal(b, e); }
1405 //! <b>Effects</b>: Erases the element pointed to by i.
1407 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1409 //! <b>Throws</b>: Nothing.
1411 //! <b>Note</b>: Invalidates the iterators (but not the references)
1412 //! to the erased element. No destructors are called.
1413 void erase(const_iterator i)
1414 { table_.erase(i); }
1416 //! <b>Effects</b>: Erases the range pointed to by b end e.
1418 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
1419 //! worst case O(this->size()).
1421 //! <b>Throws</b>: Nothing.
1423 //! <b>Note</b>: Invalidates the iterators (but not the references)
1424 //! to the erased elements. No destructors are called.
1425 void erase(const_iterator b, const_iterator e)
1426 { table_.erase(b, e); }
1428 //! <b>Effects</b>: Erases all the elements with the given value.
1430 //! <b>Returns</b>: The number of erased elements.
1432 //! <b>Complexity</b>: Average case O(this->count(value)).
1433 //! Worst case O(this->size()).
1435 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1437 //! <b>Note</b>: Invalidates the iterators (but not the references)
1438 //! to the erased elements. No destructors are called.
1439 size_type erase(const_reference value)
1440 { return table_.erase(value); }
1442 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1443 //! the same hash values as the stored hasher. The difference is that
1444 //! "hash_func" hashes the given key instead of the value_type.
1446 //! "key_value_equal" must be a equality function that induces
1447 //! the same equality as key_equal. The difference is that
1448 //! "key_value_equal" compares an arbitrary key with the contained values.
1450 //! <b>Effects</b>: Erases all the elements that have the same hash and
1451 //! compare equal with the given key.
1453 //! <b>Returns</b>: The number of erased elements.
1455 //! <b>Complexity</b>: Average case O(this->count(value)).
1456 //! Worst case O(this->size()).
1458 //! <b>Throws</b>: If the hash_func or the equal_func functors throws.
1459 //! Basic guarantee.
1461 //! <b>Note</b>: Invalidates the iterators (but not the references)
1462 //! to the erased elements. No destructors are called.
1463 template<class KeyType, class KeyHasher, class KeyValueEqual>
1464 size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1465 { return table_.erase(key, hash_func, equal_func); }
1467 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1469 //! <b>Effects</b>: Erases the element pointed to by i.
1470 //! Disposer::operator()(pointer) is called for the removed element.
1472 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1474 //! <b>Throws</b>: Nothing.
1476 //! <b>Note</b>: Invalidates the iterators
1477 //! to the erased elements.
1478 template<class Disposer>
1479 void erase_and_dispose(const_iterator i, Disposer disposer
1481 , typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
1484 { table_.erase_and_dispose(i, disposer); }
1486 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1487 template<class Disposer>
1488 void erase_and_dispose(const_iterator i, Disposer disposer)
1489 { this->erase_and_dispose(const_iterator(i), disposer); }
1492 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1494 //! <b>Effects</b>: Erases the range pointed to by b end e.
1495 //! Disposer::operator()(pointer) is called for the removed elements.
1497 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
1498 //! worst case O(this->size()).
1500 //! <b>Throws</b>: Nothing.
1502 //! <b>Note</b>: Invalidates the iterators
1503 //! to the erased elements.
1504 template<class Disposer>
1505 void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
1506 { table_.erase_and_dispose(b, e, disposer); }
1508 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1510 //! <b>Effects</b>: Erases all the elements with the given value.
1511 //! Disposer::operator()(pointer) is called for the removed elements.
1513 //! <b>Returns</b>: The number of erased elements.
1515 //! <b>Complexity</b>: Average case O(this->count(value)).
1516 //! Worst case O(this->size()).
1518 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
1520 //! <b>Note</b>: Invalidates the iterators (but not the references)
1521 //! to the erased elements. No destructors are called.
1522 template<class Disposer>
1523 size_type erase_and_dispose(const_reference value, Disposer disposer)
1524 { return table_.erase_and_dispose(value, disposer); }
1526 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1528 //! <b>Effects</b>: Erases all the elements with the given key.
1529 //! according to the comparison functor "equal_func".
1530 //! Disposer::operator()(pointer) is called for the removed elements.
1532 //! <b>Returns</b>: The number of erased elements.
1534 //! <b>Complexity</b>: Average case O(this->count(value)).
1535 //! Worst case O(this->size()).
1537 //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
1539 //! <b>Note</b>: Invalidates the iterators
1540 //! to the erased elements.
1541 template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
1542 size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
1543 { return table_.erase_and_dispose(key, hash_func, equal_func, disposer); }
1545 //! <b>Effects</b>: Erases all the elements of the container.
1547 //! <b>Complexity</b>: Linear to the number of elements on the container.
1548 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1550 //! <b>Throws</b>: Nothing.
1552 //! <b>Note</b>: Invalidates the iterators (but not the references)
1553 //! to the erased elements. No destructors are called.
1555 { return table_.clear(); }
1557 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1559 //! <b>Effects</b>: Erases all the elements of the container.
1561 //! <b>Complexity</b>: Linear to the number of elements on the container.
1562 //! Disposer::operator()(pointer) is called for the removed elements.
1564 //! <b>Throws</b>: Nothing.
1566 //! <b>Note</b>: Invalidates the iterators (but not the references)
1567 //! to the erased elements. No destructors are called.
1568 template<class Disposer>
1569 void clear_and_dispose(Disposer disposer)
1570 { return table_.clear_and_dispose(disposer); }
1572 //! <b>Effects</b>: Returns the number of contained elements with the given key
1574 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1576 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1577 size_type count(const_reference value) const
1578 { return table_.count(value); }
1580 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1581 //! the same hash values as the stored hasher. The difference is that
1582 //! "hash_func" hashes the given key instead of the value_type.
1584 //! "key_value_equal" must be a equality function that induces
1585 //! the same equality as key_equal. The difference is that
1586 //! "key_value_equal" compares an arbitrary key with the contained values.
1588 //! <b>Effects</b>: Returns the number of contained elements with the given key
1590 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1592 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1593 template<class KeyType, class KeyHasher, class KeyValueEqual>
1594 size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1595 { return table_.count(key, hash_func, equal_func); }
1597 //! <b>Effects</b>: Finds an iterator to the first element whose value is
1598 //! "value" or end() if that element does not exist.
1600 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1602 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1603 iterator find(const_reference value)
1604 { return table_.find(value); }
1606 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1607 //! the same hash values as the stored hasher. The difference is that
1608 //! "hash_func" hashes the given key instead of the value_type.
1610 //! "key_value_equal" must be a equality function that induces
1611 //! the same equality as key_equal. The difference is that
1612 //! "key_value_equal" compares an arbitrary key with the contained values.
1614 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1615 //! "key" according to the given hasher and equality functor or end() if
1616 //! that element does not exist.
1618 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1620 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1622 //! <b>Note</b>: This function is used when constructing a value_type
1623 //! is expensive and the value_type can be compared with a cheaper
1624 //! key type. Usually this key is part of the value_type.
1625 template<class KeyType, class KeyHasher, class KeyValueEqual>
1626 iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1627 { return table_.find(key, hash_func, equal_func); }
1629 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
1630 //! "key" or end() if that element does not exist.
1632 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1634 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1635 const_iterator find(const_reference value) const
1636 { return table_.find(value); }
1638 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1639 //! the same hash values as the stored hasher. The difference is that
1640 //! "hash_func" hashes the given key instead of the value_type.
1642 //! "key_value_equal" must be a equality function that induces
1643 //! the same equality as key_equal. The difference is that
1644 //! "key_value_equal" compares an arbitrary key with the contained values.
1646 //! <b>Effects</b>: Finds an iterator to the first element whose key is
1647 //! "key" according to the given hasher and equality functor or end() if
1648 //! that element does not exist.
1650 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
1652 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1654 //! <b>Note</b>: This function is used when constructing a value_type
1655 //! is expensive and the value_type can be compared with a cheaper
1656 //! key type. Usually this key is part of the value_type.
1657 template<class KeyType, class KeyHasher, class KeyValueEqual>
1658 const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1659 { return table_.find(key, hash_func, equal_func); }
1661 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
1662 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
1665 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
1667 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1668 std::pair<iterator,iterator> equal_range(const_reference value)
1669 { return table_.equal_range(value); }
1671 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1672 //! the same hash values as the stored hasher. The difference is that
1673 //! "hash_func" hashes the given key instead of the value_type.
1675 //! "key_value_equal" must be a equality function that induces
1676 //! the same equality as key_equal. The difference is that
1677 //! "key_value_equal" compares an arbitrary key with the contained values.
1679 //! <b>Effects</b>: Returns a range containing all elements with equivalent
1680 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
1683 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
1684 //! Worst case O(this->size()).
1686 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1688 //! <b>Note</b>: This function is used when constructing a value_type
1689 //! is expensive and the value_type can be compared with a cheaper
1690 //! key type. Usually this key is part of the value_type.
1691 template<class KeyType, class KeyHasher, class KeyValueEqual>
1692 std::pair<iterator,iterator> equal_range
1693 (const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
1694 { return table_.equal_range(key, hash_func, equal_func); }
1696 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
1697 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
1700 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
1702 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1703 std::pair<const_iterator, const_iterator>
1704 equal_range(const_reference value) const
1705 { return table_.equal_range(value); }
1707 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1708 //! the same hash values as the stored hasher. The difference is that
1709 //! "hash_func" hashes the given key instead of the value_type.
1711 //! "key_value_equal" must be a equality function that induces
1712 //! the same equality as key_equal. The difference is that
1713 //! "key_value_equal" compares an arbitrary key with the contained values.
1715 //! <b>Effects</b>: Returns a range containing all elements with equivalent
1716 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
1719 //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
1720 //! Worst case O(this->size()).
1722 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
1724 //! <b>Note</b>: This function is used when constructing a value_type
1725 //! is expensive and the value_type can be compared with a cheaper
1726 //! key type. Usually this key is part of the value_type.
1727 template<class KeyType, class KeyHasher, class KeyValueEqual>
1728 std::pair<const_iterator, const_iterator>
1729 equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
1730 { return table_.equal_range(key, hash_func, equal_func); }
1732 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
1733 //! appropriate type. Otherwise the behavior is undefined.
1735 //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_multiset
1736 //! that points to the value
1738 //! <b>Complexity</b>: Constant.
1740 //! <b>Throws</b>: If the hash function throws.
1741 iterator iterator_to(reference value)
1742 { return table_.iterator_to(value); }
1744 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
1745 //! appropriate type. Otherwise the behavior is undefined.
1747 //! <b>Effects</b>: Returns: a valid const_iterator belonging to the
1748 //! unordered_multiset that points to the value
1750 //! <b>Complexity</b>: Constant.
1752 //! <b>Throws</b>: If the hash function throws.
1753 const_iterator iterator_to(const_reference value) const
1754 { return table_.iterator_to(value); }
1756 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1757 //! appropriate type. Otherwise the behavior is undefined.
1759 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
1760 //! that points to the value
1762 //! <b>Complexity</b>: Constant.
1764 //! <b>Throws</b>: Nothing.
1766 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1768 static local_iterator s_local_iterator_to(reference value)
1769 { return table_type::s_local_iterator_to(value); }
1771 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1772 //! appropriate type. Otherwise the behavior is undefined.
1774 //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
1775 //! the unordered_set that points to the value
1777 //! <b>Complexity</b>: Constant.
1779 //! <b>Throws</b>: Nothing.
1781 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1783 static const_local_iterator s_local_iterator_to(const_reference value)
1784 { return table_type::s_local_iterator_to(value); }
1786 //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
1787 //! appropriate type. Otherwise the behavior is undefined.
1789 //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
1790 //! that points to the value
1792 //! <b>Complexity</b>: Constant.
1794 //! <b>Throws</b>: Nothing.
1795 local_iterator local_iterator_to(reference value)
1796 { return table_.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.
1807 const_local_iterator local_iterator_to(const_reference value) const
1808 { return table_.local_iterator_to(value); }
1810 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
1811 //! or the last rehash function.
1813 //! <b>Complexity</b>: Constant.
1815 //! <b>Throws</b>: Nothing.
1816 size_type bucket_count() const
1817 { return table_.bucket_count(); }
1819 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1821 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
1823 //! <b>Complexity</b>: Constant.
1825 //! <b>Throws</b>: Nothing.
1826 size_type bucket_size(size_type n) const
1827 { return table_.bucket_size(n); }
1829 //! <b>Effects</b>: Returns the index of the bucket in which elements
1830 //! with keys equivalent to k would be found, if any such element existed.
1832 //! <b>Complexity</b>: Constant.
1834 //! <b>Throws</b>: If the hash functor throws.
1836 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
1837 size_type bucket(const value_type& k) const
1838 { return table_.bucket(k); }
1840 //! <b>Requires</b>: "hash_func" must be a hash function that induces
1841 //! the same hash values as the stored hasher. The difference is that
1842 //! "hash_func" hashes the given key instead of the value_type.
1844 //! <b>Effects</b>: Returns the index of the bucket in which elements
1845 //! with keys equivalent to k would be found, if any such element existed.
1847 //! <b>Complexity</b>: Constant.
1849 //! <b>Throws</b>: If the hash functor throws.
1851 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
1852 template<class KeyType, class KeyHasher>
1853 size_type bucket(const KeyType& k, const KeyHasher &hash_func) const
1854 { return table_.bucket(k, hash_func); }
1856 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
1857 //! or the last rehash function.
1859 //! <b>Complexity</b>: Constant.
1861 //! <b>Throws</b>: Nothing.
1862 bucket_ptr bucket_pointer() const
1863 { return table_.bucket_pointer(); }
1865 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1867 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
1868 //! of the sequence stored in the bucket n.
1870 //! <b>Complexity</b>: Constant.
1872 //! <b>Throws</b>: Nothing.
1874 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1875 //! containing all of the elements in the nth bucket.
1876 local_iterator begin(size_type n)
1877 { return table_.begin(n); }
1879 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1881 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
1882 //! of the sequence stored in the bucket n.
1884 //! <b>Complexity</b>: Constant.
1886 //! <b>Throws</b>: Nothing.
1888 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1889 //! containing all of the elements in the nth bucket.
1890 const_local_iterator begin(size_type n) const
1891 { return table_.begin(n); }
1893 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1895 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
1896 //! of the sequence stored in the bucket n.
1898 //! <b>Complexity</b>: Constant.
1900 //! <b>Throws</b>: Nothing.
1902 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1903 //! containing all of the elements in the nth bucket.
1904 const_local_iterator cbegin(size_type n) const
1905 { return table_.cbegin(n); }
1907 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1909 //! <b>Effects</b>: Returns a local_iterator pointing to the end
1910 //! of the sequence stored in the bucket n.
1912 //! <b>Complexity</b>: Constant.
1914 //! <b>Throws</b>: Nothing.
1916 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1917 //! containing all of the elements in the nth bucket.
1918 local_iterator end(size_type n)
1919 { return table_.end(n); }
1921 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1923 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
1924 //! of the sequence stored in the bucket n.
1926 //! <b>Complexity</b>: Constant.
1928 //! <b>Throws</b>: Nothing.
1930 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1931 //! containing all of the elements in the nth bucket.
1932 const_local_iterator end(size_type n) const
1933 { return table_.end(n); }
1935 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
1937 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
1938 //! of the sequence stored in the bucket n.
1940 //! <b>Complexity</b>: Constant.
1942 //! <b>Throws</b>: Nothing.
1944 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
1945 //! containing all of the elements in the nth bucket.
1946 const_local_iterator cend(size_type n) const
1947 { return table_.cend(n); }
1949 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
1950 //! or the same as the old bucket array. new_size is the length of the
1951 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
1952 //! n can be bigger or smaller than this->bucket_count().
1954 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
1955 //! the values from the old bucket and inserts then in the new one.
1957 //! If store_hash option is true, this method does not use the hash function.
1959 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
1961 //! <b>Throws</b>: If the hasher functor throws.
1962 void rehash(const bucket_traits &new_bucket_traits)
1963 { table_.rehash(new_bucket_traits); }
1965 //! <b>Requires</b>:
1969 //! <b>Complexity</b>:
1973 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
1974 bool incremental_rehash(bool grow = true)
1975 { return table_.incremental_rehash(grow); }
1977 //! <b>Note</b>: this method is only available if incremental<true> option is activated.
1978 bool incremental_rehash(const bucket_traits &new_bucket_traits)
1979 { return table_.incremental_rehash(new_bucket_traits); }
1981 //! <b>Requires</b>:
1985 //! <b>Complexity</b>:
1988 size_type split_count() const
1989 { return table_.split_count(); }
1991 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
1992 //! the container that is bigger than n. This suggestion can be used
1993 //! to create bucket arrays with a size that will usually improve
1994 //! container's performance. If such value does not exist, the
1995 //! higher possible value is returned.
1997 //! <b>Complexity</b>: Amortized constant time.
1999 //! <b>Throws</b>: Nothing.
2000 static size_type suggested_upper_bucket_count(size_type n)
2001 { return table_type::suggested_upper_bucket_count(n); }
2003 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
2004 //! the container that is smaller than n. This suggestion can be used
2005 //! to create bucket arrays with a size that will usually improve
2006 //! container's performance. If such value does not exist, the
2007 //! lower possible value is returned.
2009 //! <b>Complexity</b>: Amortized constant time.
2011 //! <b>Throws</b>: Nothing.
2012 static size_type suggested_lower_bucket_count(size_type n)
2013 { return table_type::suggested_lower_bucket_count(n); }
2016 //! Helper metafunction to define an \c unordered_multiset that yields to the same type when the
2017 //! same options (either explicitly or implicitly) are used.
2018 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2019 template<class T, class ...Options>
2021 template<class T, class O1 = none, class O2 = none
2022 , class O3 = none, class O4 = none
2023 , class O5 = none, class O6 = none
2024 , class O7 = none, class O8 = none
2025 , class O9 = none, class O10= none
2028 struct make_unordered_multiset
2031 typedef unordered_multiset_impl
2032 < typename make_hashtable_opt
2034 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2035 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2040 > implementation_defined;
2042 typedef implementation_defined type;
2045 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2047 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2048 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
2050 template<class T, class ...Options>
2052 class unordered_multiset
2053 : public make_unordered_multiset<T,
2054 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2055 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2061 typedef typename make_unordered_multiset
2063 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2064 O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
2069 //Assert if passed value traits are compatible with the type
2070 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value));
2071 BOOST_MOVABLE_BUT_NOT_COPYABLE(unordered_multiset)
2074 typedef typename Base::value_traits value_traits;
2075 typedef typename Base::bucket_traits bucket_traits;
2076 typedef typename Base::iterator iterator;
2077 typedef typename Base::const_iterator const_iterator;
2078 typedef typename Base::bucket_ptr bucket_ptr;
2079 typedef typename Base::size_type size_type;
2080 typedef typename Base::hasher hasher;
2081 typedef typename Base::key_equal key_equal;
2083 unordered_multiset( const bucket_traits &b_traits
2084 , const hasher & hash_func = hasher()
2085 , const key_equal &equal_func = key_equal()
2086 , const value_traits &v_traits = value_traits())
2087 : Base(b_traits, hash_func, equal_func, v_traits)
2090 template<class Iterator>
2091 unordered_multiset( Iterator b
2093 , const bucket_traits &b_traits
2094 , const hasher & hash_func = hasher()
2095 , const key_equal &equal_func = key_equal()
2096 , const value_traits &v_traits = value_traits())
2097 : Base(b, e, b_traits, hash_func, equal_func, v_traits)
2100 unordered_multiset(BOOST_RV_REF(unordered_multiset) x)
2101 : Base(::boost::move(static_cast<Base&>(x)))
2104 unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
2105 { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
2110 } //namespace intrusive
2113 #include <boost/intrusive/detail/config_end.hpp>
2115 #endif //BOOST_INTRUSIVE_UNORDERED_SET_HPP