1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
13 #ifndef BOOST_INTRUSIVE_IHASHSET_HPP
\r
14 #define BOOST_INTRUSIVE_IHASHSET_HPP
\r
16 #include "detail/config_begin.hpp"
\r
17 #include "detail/ihashtable.hpp"
\r
21 namespace intrusive {
\r
23 //! The class template iunordered_set is an intrusive container, that mimics most of
\r
24 //! the interface of std::tr1::unordered_set as described in the C++ TR1.
\r
26 //! iunordered_set is a pseudo-intrusive container: each object to be stored in the
\r
27 //! container must contain a proper hook, but the container also needs
\r
28 //! additional auxiliary memory to work: iunordered_set needs a pointer to an array
\r
29 //! of type `bucket_type` to be passed in the constructor. This bucket array must
\r
30 //! have at least the same lifetime as the container. This makes the use of
\r
31 //! iunordered_set more complicated than purely intrusive containers.
\r
32 //! `bucket_type` is default-constructible, copyable and assignable
\r
34 //! The template parameter ValueTraits is called "value traits". It stores
\r
35 //! information and operations about the type to be stored in the container.
\r
37 //! The template parameter Hash is a unary function object that take an argument
\r
38 //! of type ValueTraits::value_type and returns a value of type std::size_t.
\r
40 //! The template parameter Equal is a binary predicate that takes two arguments of
\r
41 //! type ValueTraits::value_type. Equal is an equivalence relation.
\r
43 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType
\r
44 //! will be embedded in the class, that will keep track of the number of stored objects.
\r
45 //! This will allow constant-time O(1) size() member, instead of default O(N) size.
\r
47 //! iunordered_set only provides forward iterators but it provides 4 iterator types:
\r
48 //! iterator and const_iterator to navigate through the whole container and
\r
49 //! local_iterator and const_local_iterator to navigate through the values
\r
50 //! stored in a single bucket. Local iterators are faster and smaller.
\r
52 //! It's not recommended to use non ConstantTimeSize iunordered_sets because several
\r
53 //! key functions, like "empty()", become non-constant time functions. Non
\r
54 //! ConstantTimeSize iunordered_sets are mainly provided to support auto-unlink hooks.
\r
56 //! iunordered_set, unlike std::unordered_set, does not make automatic rehashings nor
\r
57 //! offers functions related to a load factor. Rehashing can be explicitly requested
\r
58 //! and the user must provide a new bucket array that will be used from that moment.
\r
60 //! Since no automatic rehashing is done, iterators are never invalidated when
\r
61 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
\r
62 template< class ValueTraits
\r
63 , class Hash = boost::hash<typename ValueTraits::value_type>
\r
64 , class Equal = std::equal_to<typename ValueTraits::value_type>
\r
65 , bool ConstantTimeSize = true
\r
66 , class SizeType = std::size_t
\r
68 class iunordered_set
\r
71 typedef detail::ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType> table_type;
\r
75 iunordered_set (const iunordered_set&);
\r
79 iunordered_set &operator =(const iunordered_set&);
\r
81 typedef table_type implementation_defined;
\r
84 typedef typename ValueTraits::value_type value_type;
\r
85 typedef typename ValueTraits::pointer pointer;
\r
86 typedef typename ValueTraits::const_pointer const_pointer;
\r
87 typedef value_type& reference;
\r
88 typedef const value_type& const_reference;
\r
89 typedef SizeType size_type;
\r
90 typedef typename std::iterator_traits<pointer>::difference_type difference_type;
\r
91 typedef value_type key_type;
\r
92 typedef Equal key_equal;
\r
93 typedef Hash hasher;
\r
94 typedef typename implementation_defined::bucket_type bucket_type;
\r
95 typedef typename boost::pointer_to_other<pointer, bucket_type>::type bucket_ptr;
\r
96 typedef typename implementation_defined::iterator iterator;
\r
97 typedef typename implementation_defined::const_iterator const_iterator;
\r
98 typedef typename implementation_defined::insert_commit_data insert_commit_data;
\r
99 typedef typename implementation_defined::local_iterator local_iterator;
\r
100 typedef typename implementation_defined::const_local_iterator const_local_iterator;
\r
107 //! <b>Requires</b>: buckets must not be being used by any other resource.
\r
109 //! <b>Effects</b>: Constructs an empty iunordered_set, storing a reference
\r
110 //! to the bucket array and copies of the hasher and equal functors.
\r
112 //! <b>Complexity</b>: Constant.
\r
114 //! <b>Throws</b>: If value_traits::node_traits::node
\r
115 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
116 //! or the copy constructor or invocation of Hash or Equal throws.
\r
118 //! <b>Notes</b>: buckets array must be destroyed only after
\r
119 //! *this is destroyed.
\r
120 iunordered_set( bucket_ptr buckets
\r
121 , size_type buckets_len
\r
122 , const Hash & hasher = Hash()
\r
123 , const Equal &equal = Equal())
\r
124 : table_(buckets, buckets_len, hasher, equal)
\r
127 //! <b>Requires</b>: buckets must not be being used by any other resource
\r
128 //! and Dereferencing iterator must yield an lvalue of type value_type.
\r
130 //! <b>Effects</b>: Constructs an empty iunordered_set and inserts elements from
\r
133 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
\r
134 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
\r
136 //! <b>Throws</b>: If value_traits::node_traits::node
\r
137 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
138 //! or the copy constructor or invocation of Hash or Equal throws.
\r
140 //! <b>Notes</b>: buckets array must be destroyed only after
\r
141 //! *this is destroyed.
\r
142 template<class Iterator>
\r
143 iunordered_set( bucket_ptr buckets
\r
144 , size_type buckets_len
\r
147 , const Hash & hasher = Hash()
\r
148 , const Equal &equal = Equal())
\r
149 : table_(buckets, buckets_len, hasher, equal)
\r
150 { table_.insert_unique(b, e); }
\r
152 //! <b>Effects</b>: Detaches all elements from this. The objects in the iunordered_set
\r
153 //! are not deleted (i.e. no destructors are called).
\r
155 //! <b>Complexity</b>: Linear to the number of elements in the iunordered_set, if
\r
156 //! it's a safe-mode or auto-unlink value. Otherwise constant.
\r
158 //! <b>Throws</b>: Nothing.
\r
162 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the iunordered_set.
\r
164 //! <b>Complexity</b>: Amortized constant time.
\r
165 //! Worst case (empty iunordered_set): O(this->bucket_count())
\r
167 //! <b>Throws</b>: Nothing.
\r
169 { return table_.begin(); }
\r
171 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
\r
172 //! of the iunordered_set.
\r
174 //! <b>Complexity</b>: Amortized constant time.
\r
175 //! Worst case (empty iunordered_set): O(this->bucket_count())
\r
177 //! <b>Throws</b>: Nothing.
\r
178 const_iterator begin() const
\r
179 { return table_.begin(); }
\r
181 //! <b>Effects</b>: Returns an iterator pointing to the end of the iunordered_set.
\r
183 //! <b>Complexity</b>: Constant.
\r
185 //! <b>Throws</b>: Nothing.
\r
187 { return table_.end(); }
\r
189 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the iunordered_set.
\r
191 //! <b>Complexity</b>: Constant.
\r
193 //! <b>Throws</b>: Nothing.
\r
194 const_iterator end() const
\r
195 { return table_.end(); }
\r
197 //! <b>Effects</b>: Returns the hasher object used by the iunordered_set.
\r
199 //! <b>Complexity</b>: Constant.
\r
201 //! <b>Throws</b>: If hasher copy-constructor throws.
\r
202 hasher hash_function() const
\r
203 { return table_.hash_function(); }
\r
205 //! <b>Effects</b>: Returns the key_equal object used by the iunordered_set.
\r
207 //! <b>Complexity</b>: Constant.
\r
209 //! <b>Throws</b>: If key_equal copy-constructor throws.
\r
210 key_equal key_eq() const
\r
211 { return table_.key_eq(); }
\r
213 //! <b>Effects</b>: Returns true is the container is empty.
\r
215 //! <b>Complexity</b>: if ConstantTimeSize is false, average constant time
\r
216 //! (worst case, with empty() == true): O(this->bucket_count()).
\r
217 //! Otherwise constant.
\r
219 //! <b>Throws</b>: Nothing.
\r
221 { return table_.empty(); }
\r
223 //! <b>Effects</b>: Returns the number of elements stored in the iunordered_set.
\r
225 //! <b>Complexity</b>: Linear to elements contained in *this if
\r
226 //! ConstantTimeSize is false. Constant-time otherwise.
\r
228 //! <b>Throws</b>: Nothing.
\r
229 size_type size() const
\r
230 { return table_.size(); }
\r
232 //! <b>Requires</b>: the hasher and the equality function unqualified swap
\r
233 //! call should not throw.
\r
235 //! <b>Effects</b>: Swaps the contents of two iunordered_sets.
\r
236 //! Swaps also the contained bucket array and equality and hasher functors.
\r
238 //! <b>Complexity</b>: Constant.
\r
240 //! <b>Throws</b>: If the swap() call for the comparison or hash functors
\r
241 //! found using ADL throw. Basic guarantee.
\r
242 void swap(iunordered_set& other)
\r
243 { table_.swap(other.table_); }
\r
245 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
247 //! <b>Effects</b>: Erases all the elements from *this
\r
248 //! calling Destroyer::operator()(pointer), clones all the
\r
249 //! elements from src calling Cloner::operator()(const value_type &)
\r
250 //! and inserts them on *this.
\r
252 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
253 //! calling Destroyer::operator()(pointer).
\r
255 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
257 //! <b>Throws</b>: If cloner throws. Basic guarantee.
\r
258 template <class Cloner, class Destroyer>
\r
259 void clone_from(const iunordered_set &src, Cloner cloner, Destroyer destroyer)
\r
260 { table_.clone_from(src.table_, cloner, destroyer); }
\r
262 //! <b>Requires</b>: value must be an lvalue
\r
264 //! <b>Effects</b>: Tries to inserts value into the iunordered_set.
\r
266 //! <b>Returns</b>: If the value
\r
267 //! is not already present inserts it and returns a pair containing the
\r
268 //! iterator to the new value and true. If the value is already present
\r
269 //! returns a pair containing an iterator to the already present value
\r
272 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
274 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
\r
276 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
277 //! No copy-constructors are called.
\r
278 std::pair<iterator, bool> insert(value_type &value)
\r
279 { return table_.insert_unique(value); }
\r
281 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
282 //! the same hash values as the stored hasher. The difference is that
\r
283 //! "hasher" hashes the given key instead of the value_type.
\r
285 //! "key_value_equal" must be a equality function that induces
\r
286 //! the same equality as key_equal. The difference is that
\r
287 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
289 //! <b>Effects</b>: Checks if a value can be inserted in the iunordered_set, using
\r
290 //! a user provided key instead of the value itself.
\r
292 //! <b>Returns</b>: If an equivalent value is already present
\r
293 //! returns a pair containing an iterator to the already present value
\r
294 //! and false. If the value can be inserted returns true in the returned
\r
295 //! pair boolean and fills "commit_data" that is meant to be used with
\r
296 //! the "insert_commit" function.
\r
298 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
300 //! <b>Throws</b>: If hasher or key_value_equal throw. Strong guarantee.
\r
302 //! <b>Notes</b>: This function is used to improve performance when constructing
\r
303 //! a value_type is expensive: if an equivalent value is already present
\r
304 //! the constructed object must be discarded. Many times, the part of the
\r
305 //! node that is used to impose the hash or the equality is much cheaper to
\r
306 //! construct than the value_type and this function offers the possibility to
\r
307 //! use that the part to check if the insertion will be successful.
\r
309 //! If the check is successful, the user can construct the value_type and use
\r
310 //! "insert_commit" to insert the object in constant-time.
\r
312 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
\r
313 //! objects are inserted or erased from the iunordered_set.
\r
314 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
315 std::pair<iterator, bool> insert_check
\r
316 (const KeyType &key, KeyHasher hasher, KeyValueEqual key_value_equal, insert_commit_data &commit_data)
\r
317 { return table_.insert_unique_check(key, hasher, key_value_equal, commit_data); }
\r
319 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
\r
320 //! must have been obtained from a previous call to "insert_check".
\r
321 //! No objects should have been inserted or erased from the iunordered_set between
\r
322 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
\r
324 //! <b>Effects</b>: Inserts the value in the iunordered_set using the information obtained
\r
325 //! from the "commit_data" that a previous "insert_check" filled.
\r
327 //! <b>Returns</b>: An iterator to the newly inserted object.
\r
329 //! <b>Complexity</b>: Constant time.
\r
331 //! <b>Throws</b>: Nothing.
\r
333 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
\r
334 //! previously executed to fill "commit_data". No value should be inserted or
\r
335 //! erased between the "insert_check" and "insert_commit" calls.
\r
336 iterator insert_commit(value_type &value, const insert_commit_data &commit_data)
\r
337 { return table_.insert_unique_commit(value, commit_data); }
\r
339 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
340 //! of type value_type.
\r
342 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
\r
344 //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e).
\r
345 //! Worst case O(N*this->size()).
\r
347 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
349 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
350 //! No copy-constructors are called.
\r
351 template<class Iterator>
\r
352 void insert(Iterator b, Iterator e)
\r
353 { table_.insert_unique(b, e); }
\r
355 //! <b>Effects</b>: Erases the element pointed to by i.
\r
357 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
359 //! <b>Throws</b>: Nothing.
\r
361 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
362 //! to the erased element. No destructors are called.
\r
363 void erase(const_iterator i)
\r
364 { table_.erase(i); }
\r
366 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
368 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
\r
369 //! worst case O(this->size()).
\r
371 //! <b>Throws</b>: Nothing.
\r
373 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
374 //! to the erased elements. No destructors are called.
\r
375 void erase(const_iterator b, const_iterator e)
\r
376 { table_.erase(b, e); }
\r
378 //! <b>Effects</b>: Erases all the elements with the given value.
\r
380 //! <b>Returns</b>: The number of erased elements.
\r
382 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
383 //! Worst case O(this->size()).
\r
385 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
387 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
388 //! to the erased elements. No destructors are called.
\r
389 size_type erase(const value_type &value)
\r
390 { return table_.erase(value); }
\r
392 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
393 //! the same hash values as the stored hasher. The difference is that
\r
394 //! "hasher" hashes the given key instead of the value_type.
\r
396 //! "key_value_equal" must be a equality function that induces
\r
397 //! the same equality as key_equal. The difference is that
\r
398 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
400 //! <b>Effects</b>: Erases all the elements that have the same hash and
\r
401 //! compare equal with the given key.
\r
403 //! <b>Returns</b>: The number of erased elements.
\r
405 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
406 //! Worst case O(this->size()).
\r
408 //! <b>Throws</b>: If hasher or equal throw. Basic guarantee.
\r
410 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
411 //! to the erased elements. No destructors are called.
\r
412 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
413 size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
414 { return table_.erase(key, hasher, equal); }
\r
416 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
418 //! <b>Effects</b>: Erases the element pointed to by i.
\r
419 //! Destroyer::operator()(pointer) is called for the removed element.
\r
421 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
423 //! <b>Throws</b>: Nothing.
\r
425 //! <b>Note</b>: Invalidates the iterators
\r
426 //! to the erased elements.
\r
427 template<class Destroyer>
\r
428 iterator erase_and_destroy(const_iterator i, Destroyer destroyer)
\r
429 { return table_.erase_and_destroy(i, destroyer); }
\r
431 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
433 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
434 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
436 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
\r
437 //! worst case O(this->size()).
\r
439 //! <b>Throws</b>: Nothing.
\r
441 //! <b>Note</b>: Invalidates the iterators
\r
442 //! to the erased elements.
\r
443 template<class Destroyer>
\r
444 iterator erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)
\r
445 { return table_.erase_and_destroy(b, e, destroyer); }
\r
447 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
449 //! <b>Effects</b>: Erases all the elements with the given value.
\r
450 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
452 //! <b>Returns</b>: The number of erased elements.
\r
454 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
455 //! Worst case O(this->size()).
\r
457 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
459 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
460 //! to the erased elements. No destructors are called.
\r
461 template<class Destroyer>
\r
462 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
463 { return table_.erase_and_destroy(value, destroyer); }
\r
465 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
467 //! <b>Effects</b>: Erases all the elements with the given key.
\r
468 //! according to the comparison functor "equal".
\r
469 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
471 //! <b>Returns</b>: The number of erased elements.
\r
473 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
474 //! Worst case O(this->size()).
\r
476 //! <b>Throws</b>: If hasher or key_value_equal throw. Basic guarantee.
\r
478 //! <b>Note</b>: Invalidates the iterators
\r
479 //! to the erased elements.
\r
480 template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>
\r
481 size_type erase_and_destroy(const KeyType& key, KeyHasher hasher, KeyValueEqual equal, Destroyer destroyer)
\r
482 { return table_.erase_and_destroy(key, hasher, equal, destroyer); }
\r
484 //! <b>Effects</b>: Erases all of the elements.
\r
486 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
487 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
489 //! <b>Throws</b>: Nothing.
\r
491 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
492 //! to the erased elements. No destructors are called.
\r
494 { return table_.clear(); }
\r
496 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
498 //! <b>Effects</b>: Erases all of the elements.
\r
500 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
501 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
503 //! <b>Throws</b>: Nothing.
\r
505 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
506 //! to the erased elements. No destructors are called.
\r
507 template<class Destroyer>
\r
508 void clear_and_destroy(Destroyer destroyer)
\r
509 { return table_.clear_and_destroy(destroyer); }
\r
511 //! <b>Effects</b>: Returns the number of contained elements with the given value
\r
513 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
515 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
516 size_type count(const value_type &value) const
\r
517 { return table_.find(value) != end(); }
\r
519 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
520 //! the same hash values as the stored hasher. The difference is that
\r
521 //! "hasher" hashes the given key instead of the value_type.
\r
523 //! "key_value_equal" must be a equality function that induces
\r
524 //! the same equality as key_equal. The difference is that
\r
525 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
527 //! <b>Effects</b>: Returns the number of contained elements with the given key
\r
529 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
531 //! <b>Throws</b>: If hasher or equal throw.
\r
532 template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>
\r
533 size_type count(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
534 { return table_.find(key, hasher, equal) != end(); }
\r
536 //! <b>Effects</b>: Finds an iterator to the first element is equal to
\r
537 //! "value" or end() if that element does not exist.
\r
539 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
541 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
542 iterator find(const value_type &value)
\r
543 { return table_.find(value); }
\r
545 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
546 //! the same hash values as the stored hasher. The difference is that
\r
547 //! "hasher" hashes the given key instead of the value_type.
\r
549 //! "key_value_equal" must be a equality function that induces
\r
550 //! the same equality as key_equal. The difference is that
\r
551 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
553 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
554 //! "key" according to the given hasher and equality functor or end() if
\r
555 //! that element does not exist.
\r
557 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
559 //! <b>Throws</b>: If hasher or equal throw.
\r
561 //! <b>Note</b>: This function is used when constructing a value_type
\r
562 //! is expensive and the value_type can be compared with a cheaper
\r
563 //! key type. Usually this key is part of the value_type.
\r
564 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
565 iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
566 { return table_.find(key, hasher, equal); }
\r
568 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
569 //! "key" or end() if that element does not exist.
\r
571 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
573 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
574 const_iterator find(const value_type &value) const
\r
575 { return table_.find(value); }
\r
577 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
578 //! the same hash values as the stored hasher. The difference is that
\r
579 //! "hasher" hashes the given key instead of the value_type.
\r
581 //! "key_value_equal" must be a equality function that induces
\r
582 //! the same equality as key_equal. The difference is that
\r
583 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
585 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
586 //! "key" according to the given hasher and equality functor or end() if
\r
587 //! that element does not exist.
\r
589 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
591 //! <b>Throws</b>: If hasher or equal throw.
\r
593 //! <b>Note</b>: This function is used when constructing a value_type
\r
594 //! is expensive and the value_type can be compared with a cheaper
\r
595 //! key type. Usually this key is part of the value_type.
\r
596 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
597 const_iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
598 { return table_.find(key, equal); }
\r
600 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
\r
601 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
\r
602 //! elements exist.
\r
604 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
\r
606 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
607 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
608 { return table_.equal_range(value); }
\r
610 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
611 //! the same hash values as the stored hasher. The difference is that
\r
612 //! "hasher" hashes the given key instead of the value_type.
\r
614 //! "key_value_equal" must be a equality function that induces
\r
615 //! the same equality as key_equal. The difference is that
\r
616 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
618 //! <b>Effects</b>: Returns a range containing all elements with equivalent
\r
619 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
\r
620 //! elements exist.
\r
622 //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).
\r
624 //! <b>Throws</b>: If hasher or the equal throw.
\r
626 //! <b>Note</b>: This function is used when constructing a value_type
\r
627 //! is expensive and the value_type can be compared with a cheaper
\r
628 //! key type. Usually this key is part of the value_type.
\r
629 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
630 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
631 { return table_.equal_range(key, hasher, equal); }
\r
633 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
\r
634 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
\r
635 //! elements exist.
\r
637 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
\r
639 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
640 std::pair<const_iterator, const_iterator>
\r
641 equal_range(const value_type &value) const
\r
642 { return table_.equal_range(value); }
\r
644 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
645 //! the same hash values as the stored hasher. The difference is that
\r
646 //! "hasher" hashes the given key instead of the value_type.
\r
648 //! "key_value_equal" must be a equality function that induces
\r
649 //! the same equality as key_equal. The difference is that
\r
650 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
652 //! <b>Effects</b>: Returns a range containing all elements with equivalent
\r
653 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
\r
654 //! elements exist.
\r
656 //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).
\r
658 //! <b>Throws</b>: If the hasher or equal throw.
\r
660 //! <b>Note</b>: This function is used when constructing a value_type
\r
661 //! is expensive and the value_type can be compared with a cheaper
\r
662 //! key type. Usually this key is part of the value_type.
\r
663 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
664 std::pair<const_iterator, const_iterator>
\r
665 equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
666 { return table_.equal_range(key, equal); }
\r
668 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of
\r
669 //! appropriate type. Otherwise the behavior is undefined.
\r
671 //! <b>Effects</b>: Returns: a valid iterator i belonging to the iunordered_set
\r
672 //! that points to the value
\r
674 //! <b>Complexity</b>: Constant.
\r
676 //! <b>Throws</b>: If the internal hash function throws.
\r
677 iterator current(value_type &value)
\r
678 { return table_.current(value); }
\r
680 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of
\r
681 //! appropriate type. Otherwise the behavior is undefined.
\r
683 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
\r
684 //! iunordered_set that points to the value
\r
686 //! <b>Complexity</b>: Constant.
\r
688 //! <b>Throws</b>: If the internal hash function throws.
\r
689 const_iterator current(const value_type &value) const
\r
690 { return table_.current(value); }
\r
692 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of
\r
693 //! appropriate type. Otherwise the behavior is undefined.
\r
695 //! <b>Effects</b>: Returns: a valid local_iterator i belonging to the iunordered_set
\r
696 //! that points to the value
\r
698 //! <b>Complexity</b>: Constant.
\r
700 //! <b>Throws</b>: Nothing.
\r
701 static local_iterator current_local(value_type &value)
\r
702 { return table_type::current_local(value); }
\r
704 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of
\r
705 //! appropriate type. Otherwise the behavior is undefined.
\r
707 //! <b>Effects</b>: Returns: a valid const_local_iterator i belonging to
\r
708 //! the iunordered_set that points to the value
\r
710 //! <b>Complexity</b>: Constant.
\r
712 //! <b>Throws</b>: Nothing.
\r
713 static const_local_iterator current_local(const value_type &value)
\r
714 { return table_type::current_local(value); }
\r
716 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
\r
717 //! or the last rehash function.
\r
719 //! <b>Complexity</b>: Constant.
\r
721 //! <b>Throws</b>: Nothing.
\r
722 size_type bucket_count() const
\r
723 { return table_.bucket_count(); }
\r
725 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
727 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
\r
729 //! <b>Complexity</b>: Constant.
\r
731 //! <b>Throws</b>: Nothing.
\r
732 size_type bucket_size(size_type n)
\r
733 { return table_.bucket_size(n); }
\r
735 //! <b>Effects</b>: Returns the index of the bucket in which elements
\r
736 //! with keys equivalent to k would be found, if any such element existed.
\r
738 //! <b>Complexity</b>: Constant.
\r
740 //! <b>Throws</b>: If the hash functor throws.
\r
742 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
\r
743 size_type bucket(const key_type& k)
\r
744 { return table_.bucket(k); }
\r
746 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
747 //! the same hash values as the stored hasher. The difference is that
\r
748 //! "hasher" hashes the given key instead of the value_type.
\r
750 //! <b>Effects</b>: Returns the index of the bucket in which elements
\r
751 //! with keys equivalent to k would be found, if any such element existed.
\r
753 //! <b>Complexity</b>: Constant.
\r
755 //! <b>Throws</b>: If hasher throws.
\r
757 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
\r
758 template<class KeyType, class KeyHasher>
\r
759 size_type bucket(const KeyType& k, KeyHasher hasher)
\r
760 { return table_.bucket(k, hasher); }
\r
762 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
\r
763 //! or the last rehash function.
\r
765 //! <b>Complexity</b>: Constant.
\r
767 //! <b>Throws</b>: Nothing.
\r
768 bucket_ptr bucket_pointer() const
\r
769 { return table_.bucket_pointer(); }
\r
771 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
773 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
\r
774 //! of the sequence stored in the bucket n.
\r
776 //! <b>Complexity</b>: Constant.
\r
778 //! <b>Throws</b>: Nothing.
\r
780 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
781 //! containing all of the elements in the nth bucket.
\r
782 local_iterator begin(size_type n)
\r
783 { return table_.begin(n); }
\r
785 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
787 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
\r
788 //! of the sequence stored in the bucket n.
\r
790 //! <b>Complexity</b>: Constant.
\r
792 //! <b>Throws</b>: Nothing.
\r
794 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
795 //! containing all of the elements in the nth bucket.
\r
796 const_local_iterator begin(size_type n) const
\r
797 { return table_.begin(n); }
\r
799 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
801 //! <b>Effects</b>: Returns a local_iterator pointing to the end
\r
802 //! of the sequence stored in the bucket n.
\r
804 //! <b>Complexity</b>: Constant.
\r
806 //! <b>Throws</b>: Nothing.
\r
808 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
809 //! containing all of the elements in the nth bucket.
\r
810 local_iterator end(size_type n)
\r
811 { return table_.end(n); }
\r
813 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
815 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
\r
816 //! of the sequence stored in the bucket n.
\r
818 //! <b>Complexity</b>: Constant.
\r
820 //! <b>Throws</b>: Nothing.
\r
822 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
823 //! containing all of the elements in the nth bucket.
\r
824 const_local_iterator end(size_type n) const
\r
825 { return table_.end(n); }
\r
827 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
\r
828 //! or the same as the old bucket array. new_size is the length of the
\r
829 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
\r
830 //! n can be bigger or smaller than this->bucket_count().
\r
832 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
\r
833 //! the values from the old bucket and inserts then in the new one.
\r
835 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
\r
837 //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
\r
838 void rehash(bucket_ptr new_buckets, size_type new_size)
\r
839 { table_.rehash(new_buckets, new_size); }
\r
841 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
\r
842 //! the container that is bigger than n. This suggestion can be used
\r
843 //! to create bucket arrays with a size that will usually improve
\r
844 //! container's performance. If such value does not exist, the
\r
845 //! higher possible value is returned.
\r
847 //! <b>Complexity</b>: Amortized constant time.
\r
849 //! <b>Throws</b>: Nothing.
\r
850 static size_type suggested_upper_bucket_count(size_type n)
\r
851 { return table_type::suggested_upper_bucket_count(n); }
\r
853 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
\r
854 //! the container that is smaller than n. This suggestion can be used
\r
855 //! to create bucket arrays with a size that will usually improve
\r
856 //! container's performance. If such value does not exist, the
\r
857 //! lower possible value is returned.
\r
859 //! <b>Complexity</b>: Amortized constant time.
\r
861 //! <b>Throws</b>: Nothing.
\r
862 static size_type suggested_lower_bucket_count(size_type n)
\r
863 { return table_type::suggested_lower_bucket_count(n); }
\r
866 //! The class template iunordered_multiset is an intrusive container, that mimics most of
\r
867 //! the interface of std::tr1::unordered_multiset as described in the C++ TR1.
\r
869 //! iunordered_multiset is a pseudo-intrusive container: each object to be stored in the
\r
870 //! container must contain a proper hook, but the container also needs
\r
871 //! additional auxiliary memory to work: iunordered_multiset needs a pointer to an array
\r
872 //! of type `bucket_type` to be passed in the constructor. This bucket array must
\r
873 //! have at least the same lifetime as the container. This makes the use of
\r
874 //! iunordered_multiset more complicated than purely intrusive containers.
\r
875 //! `bucket_type` is default-constructible, copyable and assignable
\r
877 //! The template parameter ValueTraits is called "value traits". It stores
\r
878 //! information and operations about the type to be stored in the container.
\r
880 //! The template parameter Hash is a unary function object that take an argument
\r
881 //! of type ValueTraits::value_type and returns a value of type std::size_t.
\r
883 //! The template parameter Equal is a binary predicate that takes two arguments of
\r
884 //! type ValueTraits::value_type. Equal is an equivalence relation.
\r
886 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType
\r
887 //! will be embedded in the class, that will keep track of the number of stored objects.
\r
888 //! This will allow constant-time O(1) size() member, instead of default O(N) size.
\r
890 //! iunordered_multiset only provides forward iterators but it provides 4 iterator types:
\r
891 //! iterator and const_iterator to navigate through the whole container and
\r
892 //! local_iterator and const_local_iterator to navigate through the values
\r
893 //! stored in a single bucket. Local iterators are faster and smaller.
\r
895 //! It's not recommended to use non ConstantTimeSize iunordered_multisets because several
\r
896 //! key functions, like "empty()", become non-constant time functions. Non
\r
897 //! ConstantTimeSize iunordered_multisets are mainly provided to support auto-unlink hooks.
\r
899 //! iunordered_multiset, unlike std::unordered_set, does not make automatic rehashings nor
\r
900 //! offers functions related to a load factor. Rehashing can be explicitly requested
\r
901 //! and the user must provide a new bucket array that will be used from that moment.
\r
903 //! Since no automatic rehashing is done, iterators are never invalidated when
\r
904 //! inserting or erasing elements. Iterators are only invalidated when rehasing.
\r
905 template< class ValueTraits
\r
906 , class Hash = boost::hash<typename ValueTraits::value_type>
\r
907 , class Equal = std::equal_to<typename ValueTraits::value_type>
\r
908 , bool ConstantTimeSize = true
\r
909 , class SizeType = std::size_t
\r
911 class iunordered_multiset
\r
914 typedef detail::ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType> table_type;
\r
918 iunordered_multiset (const iunordered_multiset&);
\r
922 iunordered_multiset &operator =(const iunordered_multiset&);
\r
924 typedef table_type implementation_defined;
\r
927 typedef typename ValueTraits::value_type value_type;
\r
928 typedef typename ValueTraits::pointer pointer;
\r
929 typedef typename ValueTraits::const_pointer const_pointer;
\r
930 typedef value_type& reference;
\r
931 typedef const value_type& const_reference;
\r
932 typedef SizeType size_type;
\r
933 typedef typename std::iterator_traits<pointer>::difference_type difference_type;
\r
934 typedef value_type key_type;
\r
935 typedef Equal key_equal;
\r
936 typedef Hash hasher;
\r
937 typedef typename implementation_defined::bucket_type bucket_type;
\r
938 typedef typename boost::pointer_to_other<pointer, bucket_type>::type bucket_ptr;
\r
939 typedef typename implementation_defined::iterator iterator;
\r
940 typedef typename implementation_defined::const_iterator const_iterator;
\r
941 typedef typename implementation_defined::insert_commit_data insert_commit_data;
\r
942 typedef typename implementation_defined::local_iterator local_iterator;
\r
943 typedef typename implementation_defined::const_local_iterator const_local_iterator;
\r
950 //! <b>Requires</b>: buckets must not be being used by any other resource.
\r
952 //! <b>Effects</b>: Constructs an empty iunordered_multiset, storing a reference
\r
953 //! to the bucket array and copies of the hasher and equal functors.
\r
955 //! <b>Complexity</b>: Constant.
\r
957 //! <b>Throws</b>: If value_traits::node_traits::node
\r
958 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
959 //! or the copy constructor or invocation of Hash or Equal throws.
\r
961 //! <b>Notes</b>: buckets array must be destroyed only after
\r
962 //! *this is destroyed.
\r
963 iunordered_multiset ( bucket_ptr buckets
\r
964 , size_type buckets_len
\r
965 , const Hash & hasher = Hash()
\r
966 , const Equal &equal = Equal())
\r
967 : table_(buckets, buckets_len, hasher, equal)
\r
970 //! <b>Requires</b>: buckets must not be being used by any other resource
\r
971 //! and Dereferencing iterator must yield an lvalue of type value_type.
\r
973 //! <b>Effects</b>: Constructs an empty iunordered_multiset and inserts elements from
\r
976 //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)
\r
977 //! (with a good hash function and with buckets_len >= N),worst case O(N2).
\r
979 //! <b>Throws</b>: If value_traits::node_traits::node
\r
980 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
981 //! or the copy constructor or invocation of Hash or Equal throws.
\r
983 //! <b>Notes</b>: buckets array must be destroyed only after
\r
984 //! *this is destroyed.
\r
985 template<class Iterator>
\r
986 iunordered_multiset ( bucket_ptr buckets
\r
987 , size_type buckets_len
\r
990 , const Hash & hasher = Hash()
\r
991 , const Equal &equal = Equal())
\r
992 : table_(buckets, buckets_len, hasher, equal)
\r
993 { table_.insert_equal(b, e); }
\r
995 //! <b>Effects</b>: Detaches all elements from this. The objects in the iunordered_multiset
\r
996 //! are not deleted (i.e. no destructors are called).
\r
998 //! <b>Complexity</b>: Linear to the number of elements in the iunordered_multiset, if
\r
999 //! it's a safe-mode or auto-unlink value. Otherwise constant.
\r
1001 //! <b>Throws</b>: Nothing.
\r
1002 ~iunordered_multiset()
\r
1005 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the iunordered_multiset.
\r
1007 //! <b>Complexity</b>: Amortized constant time.
\r
1008 //! Worst case (empty iunordered_multiset): O(this->bucket_count())
\r
1010 //! <b>Throws</b>: Nothing.
\r
1012 { return table_.begin(); }
\r
1014 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
\r
1015 //! of the iunordered_multiset.
\r
1017 //! <b>Complexity</b>: Amortized constant time.
\r
1018 //! Worst case (empty iunordered_multiset): O(this->bucket_count())
\r
1020 //! <b>Throws</b>: Nothing.
\r
1021 const_iterator begin() const
\r
1022 { return table_.begin(); }
\r
1024 //! <b>Effects</b>: Returns an iterator pointing to the end of the iunordered_multiset.
\r
1026 //! <b>Complexity</b>: Constant.
\r
1028 //! <b>Throws</b>: Nothing.
\r
1030 { return table_.end(); }
\r
1032 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the iunordered_multiset.
\r
1034 //! <b>Complexity</b>: Constant.
\r
1036 //! <b>Throws</b>: Nothing.
\r
1037 const_iterator end() const
\r
1038 { return table_.end(); }
\r
1040 //! <b>Effects</b>: Returns the hasher object used by the iunordered_set.
\r
1042 //! <b>Complexity</b>: Constant.
\r
1044 //! <b>Throws</b>: If hasher copy-constructor throws.
\r
1045 hasher hash_function() const
\r
1046 { return table_.hash_function(); }
\r
1048 //! <b>Effects</b>: Returns the key_equal object used by the iunordered_multiset.
\r
1050 //! <b>Complexity</b>: Constant.
\r
1052 //! <b>Throws</b>: If key_equal copy-constructor throws.
\r
1053 key_equal key_eq() const
\r
1054 { return table_.key_eq(); }
\r
1056 //! <b>Effects</b>: Returns true is the container is empty.
\r
1058 //! <b>Complexity</b>: if ConstantTimeSize is false, average constant time
\r
1059 //! (worst case, with empty() == true): O(this->bucket_count()).
\r
1060 //! Otherwise constant.
\r
1062 //! <b>Throws</b>: Nothing.
\r
1063 bool empty() const
\r
1064 { return table_.empty(); }
\r
1066 //! <b>Effects</b>: Returns the number of elements stored in the iunordered_multiset.
\r
1068 //! <b>Complexity</b>: Linear to elements contained in *this if
\r
1069 //! ConstantTimeSize is false. Constant-time otherwise.
\r
1071 //! <b>Throws</b>: Nothing.
\r
1072 size_type size() const
\r
1073 { return table_.size(); }
\r
1075 //! <b>Requires</b>: the hasher and the equality function unqualified swap
\r
1076 //! call should not throw.
\r
1078 //! <b>Effects</b>: Swaps the contents of two iunordered_multisets.
\r
1079 //! Swaps also the contained bucket array and equality and hasher functors.
\r
1082 //! <b>Complexity</b>: Constant.
\r
1084 //! <b>Throws</b>: If the swap() call for the comparison or hash functors
\r
1085 //! found using ADL throw. Basic guarantee.
\r
1086 void swap(iunordered_multiset& other)
\r
1087 { table_.swap(other.table_); }
\r
1089 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1091 //! <b>Effects</b>: Erases all the elements from *this
\r
1092 //! calling Destroyer::operator()(pointer), clones all the
\r
1093 //! elements from src calling Cloner::operator()(const value_type &)
\r
1094 //! and inserts them on *this.
\r
1096 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
1097 //! calling Destroyer::operator()(pointer).
\r
1099 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
1101 //! <b>Throws</b>: If cloner throws.
\r
1102 template <class Cloner, class Destroyer>
\r
1103 void clone_from(const iunordered_multiset &src, Cloner cloner, Destroyer destroyer)
\r
1104 { table_.clone_from(src.table_, cloner, destroyer); }
\r
1106 //! <b>Requires</b>: value must be an lvalue
\r
1108 //! <b>Effects</b>: Inserts value into the iunordered_multiset.
\r
1110 //! <b>Returns</b>: An iterator to the new inserted value.
\r
1112 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1114 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
\r
1116 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
1117 //! No copy-constructors are called.
\r
1118 iterator insert(value_type &value)
\r
1119 { return table_.insert_equal(value); }
\r
1121 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
1122 //! of type value_type.
\r
1124 //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).
\r
1126 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
\r
1127 //! size of the range. However, it is linear in N if the range is already sorted
\r
1128 //! by value_comp().
\r
1130 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
1132 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
1133 //! No copy-constructors are called.
\r
1134 template<class Iterator>
\r
1135 void insert(Iterator b, Iterator e)
\r
1136 { table_.insert_equal(b, e); }
\r
1138 //! <b>Effects</b>: Erases the element pointed to by i.
\r
1140 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1142 //! <b>Throws</b>: Nothing.
\r
1144 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1145 //! to the erased element. No destructors are called.
\r
1146 void erase(const_iterator i)
\r
1147 { table_.erase(i); }
\r
1149 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
1151 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
\r
1152 //! worst case O(this->size()).
\r
1154 //! <b>Throws</b>: Nothing.
\r
1156 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1157 //! to the erased elements. No destructors are called.
\r
1158 void erase(const_iterator b, const_iterator e)
\r
1159 { table_.erase(b, e); }
\r
1161 //! <b>Effects</b>: Erases all the elements with the given value.
\r
1163 //! <b>Returns</b>: The number of erased elements.
\r
1165 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
1166 //! Worst case O(this->size()).
\r
1168 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
1170 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1171 //! to the erased elements. No destructors are called.
\r
1172 size_type erase(const value_type &value)
\r
1173 { return table_.erase(value); }
\r
1175 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1176 //! the same hash values as the stored hasher. The difference is that
\r
1177 //! "hasher" hashes the given key instead of the value_type.
\r
1179 //! "key_value_equal" must be a equality function that induces
\r
1180 //! the same equality as key_equal. The difference is that
\r
1181 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1183 //! <b>Effects</b>: Erases all the elements that have the same hash and
\r
1184 //! compare equal with the given key.
\r
1186 //! <b>Returns</b>: The number of erased elements.
\r
1188 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
1189 //! Worst case O(this->size()).
\r
1191 //! <b>Throws</b>: If the hasher or the equal functors throws. Basic guarantee.
\r
1193 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1194 //! to the erased elements. No destructors are called.
\r
1195 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
1196 size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
1197 { return table_.erase(key, hasher, equal); }
\r
1199 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1201 //! <b>Effects</b>: Erases the element pointed to by i.
\r
1202 //! Destroyer::operator()(pointer) is called for the removed element.
\r
1204 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1206 //! <b>Throws</b>: Nothing.
\r
1208 //! <b>Note</b>: Invalidates the iterators
\r
1209 //! to the erased elements.
\r
1210 template<class Destroyer>
\r
1211 void erase_and_destroy(const_iterator i, Destroyer destroyer)
\r
1212 { table_.erase_and_destroy(i, destroyer); }
\r
1214 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1216 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
1217 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1219 //! <b>Complexity</b>: Average case O(std::distance(b, e)),
\r
1220 //! worst case O(this->size()).
\r
1222 //! <b>Throws</b>: Nothing.
\r
1224 //! <b>Note</b>: Invalidates the iterators
\r
1225 //! to the erased elements.
\r
1226 template<class Destroyer>
\r
1227 void erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)
\r
1228 { table_.erase_and_destroy(b, e, destroyer); }
\r
1230 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1232 //! <b>Effects</b>: Erases all the elements with the given value.
\r
1233 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1235 //! <b>Returns</b>: The number of erased elements.
\r
1237 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
1238 //! Worst case O(this->size()).
\r
1240 //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
\r
1242 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1243 //! to the erased elements. No destructors are called.
\r
1244 template<class Destroyer>
\r
1245 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
1246 { return table_.erase_and_destroy(value, destroyer); }
\r
1248 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1250 //! <b>Effects</b>: Erases all the elements with the given key.
\r
1251 //! according to the comparison functor "equal".
\r
1252 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1254 //! <b>Returns</b>: The number of erased elements.
\r
1256 //! <b>Complexity</b>: Average case O(this->count(value)).
\r
1257 //! Worst case O(this->size()).
\r
1259 //! <b>Throws</b>: If hasher or equal throw. Basic guarantee.
\r
1261 //! <b>Note</b>: Invalidates the iterators
\r
1262 //! to the erased elements.
\r
1263 template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>
\r
1264 size_type erase_and_destroy(const KeyType& key, KeyHasher hasher, KeyValueEqual equal, Destroyer destroyer)
\r
1265 { return table_.erase_and_destroy(key, hasher, equal, destroyer); }
\r
1267 //! <b>Effects</b>: Erases all the elements of the container.
\r
1269 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
1270 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
1272 //! <b>Throws</b>: Nothing.
\r
1274 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1275 //! to the erased elements. No destructors are called.
\r
1277 { return table_.clear(); }
\r
1279 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1281 //! <b>Effects</b>: Erases all the elements of the container.
\r
1283 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
1284 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1286 //! <b>Throws</b>: Nothing.
\r
1288 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1289 //! to the erased elements. No destructors are called.
\r
1290 template<class Destroyer>
\r
1291 void clear_and_destroy(Destroyer destroyer)
\r
1292 { return table_.clear_and_destroy(destroyer); }
\r
1294 //! <b>Effects</b>: Returns the number of contained elements with the given key
\r
1296 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1298 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1299 size_type count(const value_type &value) const
\r
1300 { return table_.count(value); }
\r
1302 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1303 //! the same hash values as the stored hasher. The difference is that
\r
1304 //! "hasher" hashes the given key instead of the value_type.
\r
1306 //! "key_value_equal" must be a equality function that induces
\r
1307 //! the same equality as key_equal. The difference is that
\r
1308 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1310 //! <b>Effects</b>: Returns the number of contained elements with the given key
\r
1312 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1314 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1315 template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>
\r
1316 size_type count(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
1317 { return table_.count(key, hasher, equal); }
\r
1319 //! <b>Effects</b>: Finds an iterator to the first element whose value is
\r
1320 //! "value" or end() if that element does not exist.
\r
1322 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1324 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1325 iterator find(const value_type &value)
\r
1326 { return table_.find(value); }
\r
1328 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1329 //! the same hash values as the stored hasher. The difference is that
\r
1330 //! "hasher" hashes the given key instead of the value_type.
\r
1332 //! "key_value_equal" must be a equality function that induces
\r
1333 //! the same equality as key_equal. The difference is that
\r
1334 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1336 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
1337 //! "key" according to the given hasher and equality functor or end() if
\r
1338 //! that element does not exist.
\r
1340 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1342 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1344 //! <b>Note</b>: This function is used when constructing a value_type
\r
1345 //! is expensive and the value_type can be compared with a cheaper
\r
1346 //! key type. Usually this key is part of the value_type.
\r
1347 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
1348 iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
1349 { return table_.find(key, hasher, equal); }
\r
1351 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
1352 //! "key" or end() if that element does not exist.
\r
1354 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1356 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1357 const_iterator find(const value_type &value) const
\r
1358 { return table_.find(value); }
\r
1360 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1361 //! the same hash values as the stored hasher. The difference is that
\r
1362 //! "hasher" hashes the given key instead of the value_type.
\r
1364 //! "key_value_equal" must be a equality function that induces
\r
1365 //! the same equality as key_equal. The difference is that
\r
1366 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1368 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
1369 //! "key" according to the given hasher and equality functor or end() if
\r
1370 //! that element does not exist.
\r
1372 //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
\r
1374 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1376 //! <b>Note</b>: This function is used when constructing a value_type
\r
1377 //! is expensive and the value_type can be compared with a cheaper
\r
1378 //! key type. Usually this key is part of the value_type.
\r
1379 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
1380 const_iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
1381 { return table_.find(key, equal); }
\r
1383 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
\r
1384 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
\r
1385 //! elements exist.
\r
1387 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
\r
1389 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1390 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
1391 { return table_.equal_range(value); }
\r
1393 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1394 //! the same hash values as the stored hasher. The difference is that
\r
1395 //! "hasher" hashes the given key instead of the value_type.
\r
1397 //! "key_value_equal" must be a equality function that induces
\r
1398 //! the same equality as key_equal. The difference is that
\r
1399 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1401 //! <b>Effects</b>: Returns a range containing all elements with equivalent
\r
1402 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
\r
1403 //! elements exist.
\r
1405 //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).
\r
1407 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1409 //! <b>Note</b>: This function is used when constructing a value_type
\r
1410 //! is expensive and the value_type can be compared with a cheaper
\r
1411 //! key type. Usually this key is part of the value_type.
\r
1412 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
1413 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)
\r
1414 { return table_.equal_range(key, hasher, equal); }
\r
1416 //! <b>Effects</b>: Returns a range containing all elements with values equivalent
\r
1417 //! to value. Returns std::make_pair(this->end(), this->end()) if no such
\r
1418 //! elements exist.
\r
1420 //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
\r
1422 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1423 std::pair<const_iterator, const_iterator>
\r
1424 equal_range(const value_type &value) const
\r
1425 { return table_.equal_range(value); }
\r
1427 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1428 //! the same hash values as the stored hasher. The difference is that
\r
1429 //! "hasher" hashes the given key instead of the value_type.
\r
1431 //! "key_value_equal" must be a equality function that induces
\r
1432 //! the same equality as key_equal. The difference is that
\r
1433 //! "key_value_equal" compares an arbitrary key with the contained values.
\r
1435 //! <b>Effects</b>: Returns a range containing all elements with equivalent
\r
1436 //! keys. Returns std::make_pair(this->end(), this->end()) if no such
\r
1437 //! elements exist.
\r
1439 //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).
\r
1441 //! <b>Throws</b>: If the internal hasher or the equality functor throws.
\r
1443 //! <b>Note</b>: This function is used when constructing a value_type
\r
1444 //! is expensive and the value_type can be compared with a cheaper
\r
1445 //! key type. Usually this key is part of the value_type.
\r
1446 template<class KeyType, class KeyHasher, class KeyValueEqual>
\r
1447 std::pair<const_iterator, const_iterator>
\r
1448 equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const
\r
1449 { return table_.equal_range(key, equal); }
\r
1451 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of
\r
1452 //! appropriate type. Otherwise the behavior is undefined.
\r
1454 //! <b>Effects</b>: Returns: a valid iterator i belonging to the iunordered_multiset
\r
1455 //! that points to the value
\r
1457 //! <b>Complexity</b>: Constant.
\r
1459 //! <b>Throws</b>: If the hash function throws.
\r
1460 iterator current(value_type &value)
\r
1461 { return table_.current(value); }
\r
1463 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of
\r
1464 //! appropriate type. Otherwise the behavior is undefined.
\r
1466 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
\r
1467 //! iunordered_multiset that points to the value
\r
1469 //! <b>Complexity</b>: Constant.
\r
1471 //! <b>Throws</b>: If the hash function throws.
\r
1472 const_iterator current(const value_type &value) const
\r
1473 { return table_.current(value); }
\r
1475 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of
\r
1476 //! appropriate type. Otherwise the behavior is undefined.
\r
1478 //! <b>Effects</b>: Returns: a valid local_iterator i belonging to the iunordered_multiset
\r
1479 //! that points to the value
\r
1481 //! <b>Complexity</b>: Constant.
\r
1483 //! <b>Throws</b>: Nothing.
\r
1484 static local_iterator current_local(value_type &value)
\r
1485 { return table_type::current_local(value); }
\r
1487 //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of
\r
1488 //! appropriate type. Otherwise the behavior is undefined.
\r
1490 //! <b>Effects</b>: Returns: a valid const_local_iterator i belonging to
\r
1491 //! the iunordered_multiset that points to the value
\r
1493 //! <b>Complexity</b>: Constant.
\r
1495 //! <b>Throws</b>: Nothing.
\r
1496 static const_local_iterator current_local(const value_type &value)
\r
1497 { return table_type::current_local(value); }
\r
1499 //! <b>Effects</b>: Returns the number of buckets passed in the constructor
\r
1500 //! or the last rehash function.
\r
1502 //! <b>Complexity</b>: Constant.
\r
1504 //! <b>Throws</b>: Nothing.
\r
1505 size_type bucket_count() const
\r
1506 { return table_.bucket_count(); }
\r
1508 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
1510 //! <b>Effects</b>: Returns the number of elements in the nth bucket.
\r
1512 //! <b>Complexity</b>: Constant.
\r
1514 //! <b>Throws</b>: Nothing.
\r
1515 size_type bucket_size(size_type n)
\r
1516 { return table_.bucket_size(n); }
\r
1518 //! <b>Effects</b>: Returns the index of the bucket in which elements
\r
1519 //! with keys equivalent to k would be found, if any such element existed.
\r
1521 //! <b>Complexity</b>: Constant.
\r
1523 //! <b>Throws</b>: If the hash functor throws.
\r
1525 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
\r
1526 size_type bucket(const key_type& k)
\r
1527 { return table_.bucket(k); }
\r
1529 //! <b>Requires</b>: "hasher" must be a hash function that induces
\r
1530 //! the same hash values as the stored hasher. The difference is that
\r
1531 //! "hasher" hashes the given key instead of the value_type.
\r
1533 //! <b>Effects</b>: Returns the index of the bucket in which elements
\r
1534 //! with keys equivalent to k would be found, if any such element existed.
\r
1536 //! <b>Complexity</b>: Constant.
\r
1538 //! <b>Throws</b>: If the hash functor throws.
\r
1540 //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
\r
1541 template<class KeyType, class KeyHasher>
\r
1542 size_type bucket(const KeyType& k, const KeyHasher &hasher)
\r
1543 { return table_.bucket(k, hasher); }
\r
1545 //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
\r
1546 //! or the last rehash function.
\r
1548 //! <b>Complexity</b>: Constant.
\r
1550 //! <b>Throws</b>: Nothing.
\r
1551 bucket_ptr bucket_pointer() const
\r
1552 { return table_.bucket_pointer(); }
\r
1554 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
1556 //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
\r
1557 //! of the sequence stored in the bucket n.
\r
1559 //! <b>Complexity</b>: Constant.
\r
1561 //! <b>Throws</b>: Nothing.
\r
1563 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
1564 //! containing all of the elements in the nth bucket.
\r
1565 local_iterator begin(size_type n)
\r
1566 { return table_.begin(n); }
\r
1568 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
1570 //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
\r
1571 //! of the sequence stored in the bucket n.
\r
1573 //! <b>Complexity</b>: Constant.
\r
1575 //! <b>Throws</b>: Nothing.
\r
1577 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
1578 //! containing all of the elements in the nth bucket.
\r
1579 const_local_iterator begin(size_type n) const
\r
1580 { return table_.begin(n); }
\r
1582 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
1584 //! <b>Effects</b>: Returns a local_iterator pointing to the end
\r
1585 //! of the sequence stored in the bucket n.
\r
1587 //! <b>Complexity</b>: Constant.
\r
1589 //! <b>Throws</b>: Nothing.
\r
1591 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
1592 //! containing all of the elements in the nth bucket.
\r
1593 local_iterator end(size_type n)
\r
1594 { return table_.end(n); }
\r
1596 //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
\r
1598 //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
\r
1599 //! of the sequence stored in the bucket n.
\r
1601 //! <b>Complexity</b>: Constant.
\r
1603 //! <b>Throws</b>: Nothing.
\r
1605 //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
\r
1606 //! containing all of the elements in the nth bucket.
\r
1607 const_local_iterator end(size_type n) const
\r
1608 { return table_.end(n); }
\r
1610 //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
\r
1611 //! or the same as the old bucket array. new_size is the length of the
\r
1612 //! the array pointed by new_buckets. If new_buckets == this->bucket_pointer()
\r
1613 //! n can be bigger or smaller than this->bucket_count().
\r
1615 //! <b>Effects</b>: Updates the internal reference with the new bucket erases
\r
1616 //! the values from the old bucket and inserts then in the new one.
\r
1618 //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
\r
1620 //! <b>Throws</b>: If the hasher functor throws.
\r
1621 void rehash(bucket_ptr new_buckets, size_type new_size)
\r
1622 { table_.rehash(new_buckets, new_size); }
\r
1624 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
\r
1625 //! the container that is bigger than n. This suggestion can be used
\r
1626 //! to create bucket arrays with a size that will usually improve
\r
1627 //! container's performance. If such value does not exist, the
\r
1628 //! higher possible value is returned.
\r
1630 //! <b>Complexity</b>: Amortized constant time.
\r
1632 //! <b>Throws</b>: Nothing.
\r
1633 static size_type suggested_upper_bucket_count(size_type n)
\r
1634 { return table_type::suggested_upper_bucket_count(n); }
\r
1636 //! <b>Effects</b>: Returns the nearest new bucket count optimized for
\r
1637 //! the container that is smaller than n. This suggestion can be used
\r
1638 //! to create bucket arrays with a size that will usually improve
\r
1639 //! container's performance. If such value does not exist, the
\r
1640 //! lower possible value is returned.
\r
1642 //! <b>Complexity</b>: Amortized constant time.
\r
1644 //! <b>Throws</b>: Nothing.
\r
1645 static size_type suggested_lower_bucket_count(size_type n)
\r
1646 { return table_type::suggested_lower_bucket_count(n); }
\r
1649 } //namespace intrusive
\r
1650 } //namespace boost
\r
1652 #include "detail/config_end.hpp"
\r
1654 #endif //BOOST_INTRUSIVE_IHASHSET_HPP
\r