 |
Boost
v1.57.0
doxygen for www.boost.org
|
|
|
Boost
v1.57.0
doxygen for www.boost.org
|
|
The class template hashtable is an intrusive hash table container, that is used to construct intrusive unordered_set and unordered_multiset containers. More...
#include <hashtable.hpp>
Public Types | |
| typedef ValueTraits | value_traits |
| typedef value_traits::pointer | pointer |
| typedef value_traits::const_pointer | const_pointer |
| typedef value_traits::value_type | value_type |
| typedef pointer_traits < pointer >::reference | reference |
| typedef pointer_traits < const_pointer >::reference | const_reference |
| typedef pointer_traits < pointer >::difference_type | difference_type |
| typedef SizeType | size_type |
| typedef value_type | key_type |
| typedef data_type::value_equal | key_equal |
| typedef data_type::value_equal | value_equal |
| typedef data_type::hasher | hasher |
| typedef detail::bucket_impl < slist_impl > | bucket_type |
| typedef pointer_traits < pointer >::template rebind_pointer< bucket_type > ::type | bucket_ptr |
| typedef pointer_traits < pointer >::template rebind_pointer< const bucket_type >::type | const_bucket_ptr |
| typedef pointer_traits < bucket_ptr >::reference | bucket_reference |
| typedef pointer_traits < bucket_ptr >::reference | const_bucket_reference |
| typedef slist_impl::iterator | siterator |
| typedef slist_impl::const_iterator | const_siterator |
| typedef hashtable_iterator < bucket_plus_vtraits_t, false > | iterator |
| typedef hashtable_iterator < bucket_plus_vtraits_t, true > | const_iterator |
| typedef value_traits::node_traits | node_traits |
| typedef node_traits::node | node |
| typedef pointer_traits < pointer >::template rebind_pointer< node >::type | node_ptr |
| typedef pointer_traits < pointer >::template rebind_pointer< const node > ::type | const_node_ptr |
| typedef pointer_traits < node_ptr >::reference | node_reference |
| typedef pointer_traits < const_node_ptr >::reference | const_node_reference |
| typedef slist_impl::node_algorithms | node_algorithms |
| typedef detail::insert_commit_data_impl | insert_commit_data |
| typedef detail::transform_iterator < typename slist_impl::iterator, downcast_node_to_value_t < value_traits, false > > | local_iterator |
| typedef detail::transform_iterator < typename slist_impl::iterator, downcast_node_to_value_t < value_traits, true > > | const_local_iterator |
Public Member Functions | |
| hashtable_impl (const bucket_traits &b_traits, const hasher &hash_func=hasher(), const key_equal &equal_func=key_equal(), const value_traits &v_traits=value_traits()) | |
| Requires: buckets must not be being used by any other resource. More... | |
| hashtable_impl (BOOST_RV_REF(hashtable_impl) x) | |
| Effects: to-do More... | |
| hashtable_impl & | operator= (BOOST_RV_REF(hashtable_impl) x) |
| Effects: to-do More... | |
| iterator | begin () |
| Effects: Returns an iterator pointing to the beginning of the unordered_set. More... | |
| const_iterator | begin () const |
| Effects: Returns a const_iterator pointing to the beginning of the unordered_set. More... | |
| const_iterator | cbegin () const |
| Effects: Returns a const_iterator pointing to the beginning of the unordered_set. More... | |
| iterator | end () |
| Effects: Returns an iterator pointing to the end of the unordered_set. More... | |
| const_iterator | end () const |
| Effects: Returns a const_iterator pointing to the end of the unordered_set. More... | |
| const_iterator | cend () const |
| Effects: Returns a const_iterator pointing to the end of the unordered_set. More... | |
| hasher | hash_function () const |
| Effects: Returns the hasher object used by the unordered_set. More... | |
| key_equal | key_eq () const |
| Effects: Returns the key_equal object used by the unordered_set. More... | |
| bool | empty () const |
| Effects: Returns true if the container is empty. More... | |
| size_type | size () const |
| Effects: Returns the number of elements stored in the unordered_set. More... | |
| void | swap (hashtable_impl &other) |
| Requires: the hasher and the equality function unqualified swap call should not throw. More... | |
| template<class Cloner , class Disposer > | |
| void | clone_from (const hashtable_impl &src, Cloner cloner, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw Cloner should yield to nodes that compare equal and produce the same hash than the original node. More... | |
| iterator | insert_equal (reference value) |
| Requires: value must be an lvalue More... | |
| template<class Iterator > | |
| void | insert_equal (Iterator b, Iterator e) |
| Requires: Dereferencing iterator must yield an lvalue of type value_type. More... | |
| std::pair< iterator, bool > | insert_unique (reference value) |
| Requires: value must be an lvalue More... | |
| template<class Iterator > | |
| void | insert_unique (Iterator b, Iterator e) |
| Requires: Dereferencing iterator must yield an lvalue of type value_type. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| std::pair< iterator, bool > | insert_unique_check (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func, insert_commit_data &commit_data) |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| iterator | insert_unique_commit (reference value, const insert_commit_data &commit_data) |
| Requires: value must be an lvalue of type value_type. More... | |
| void | erase (const_iterator i) |
| Effects: Erases the element pointed to by i. More... | |
| void | erase (const_iterator b, const_iterator e) |
| Effects: Erases the range pointed to by b end e. More... | |
| size_type | erase (const_reference value) |
| Effects: Erases all the elements with the given value. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| size_type | erase (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| template<class Disposer > | |
| void | erase_and_dispose (const_iterator i, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class Disposer > | |
| void | erase_and_dispose (const_iterator b, const_iterator e, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class Disposer > | |
| size_type | erase_and_dispose (const_reference value, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual , class Disposer > | |
| size_type | erase_and_dispose (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| void | clear () |
| Effects: Erases all of the elements. More... | |
| template<class Disposer > | |
| void | clear_and_dispose (Disposer disposer) |
| Requires: Disposer::operator()(pointer) shouldn't throw. More... | |
| size_type | count (const_reference value) const |
| Effects: Returns the number of contained elements with the given value More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| size_type | count (const KeyType &key, const KeyHasher &hash_func, const KeyValueEqual &equal_func) const |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| iterator | find (const_reference value) |
| Effects: Finds an iterator to the first element is equal to "value" or end() if that element does not exist. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| iterator | find (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| const_iterator | find (const_reference value) const |
| Effects: Finds a const_iterator to the first element whose key is "key" or end() if that element does not exist. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| const_iterator | find (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| std::pair< iterator, iterator > | equal_range (const_reference value) |
| Effects: Returns a range containing all elements with values equivalent to value. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| std::pair< iterator, iterator > | equal_range (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| std::pair< const_iterator, const_iterator > | equal_range (const_reference value) const |
| Effects: Returns a range containing all elements with values equivalent to value. More... | |
| template<class KeyType , class KeyHasher , class KeyValueEqual > | |
| std::pair< const_iterator, const_iterator > | equal_range (const KeyType &key, KeyHasher hash_func, KeyValueEqual equal_func) const |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| iterator | iterator_to (reference value) |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| const_iterator | iterator_to (const_reference value) const |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| local_iterator | local_iterator_to (reference value) |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| const_local_iterator | local_iterator_to (const_reference value) const |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| size_type | bucket_count () const |
| Effects: Returns the number of buckets passed in the constructor or the last rehash function. More... | |
| size_type | bucket_size (size_type n) const |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| size_type | bucket (const key_type &k) const |
| Effects: Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed. More... | |
| template<class KeyType , class KeyHasher > | |
| size_type | bucket (const KeyType &k, const KeyHasher &hash_func) const |
| Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher. More... | |
| bucket_ptr | bucket_pointer () const |
| Effects: Returns the bucket array pointer passed in the constructor or the last rehash function. More... | |
| local_iterator | begin (size_type n) |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| const_local_iterator | begin (size_type n) const |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| const_local_iterator | cbegin (size_type n) const |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| local_iterator | end (size_type n) |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| const_local_iterator | end (size_type n) const |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| const_local_iterator | cend (size_type n) const |
| Requires: n is in the range [0, this->bucket_count()). More... | |
| void | rehash (const bucket_traits &new_bucket_traits) |
| Requires: new_bucket_traits can hold a pointer to a new bucket array or the same as the old bucket array with a different length. More... | |
| bool | incremental_rehash (bool grow=true) |
| Requires: More... | |
| bool | incremental_rehash (const bucket_traits &new_bucket_traits) |
| Effects: If new_bucket_traits.bucket_count() is not this->bucket_count()/2 or this->bucket_count()*2, or this->split_bucket() != new_bucket_traits.bucket_count() returns false and does nothing. More... | |
| size_type | split_count () const |
| Requires: More... | |
Static Public Member Functions | |
| static local_iterator | s_local_iterator_to (reference value) |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| static const_local_iterator | s_local_iterator_to (const_reference value) |
| Requires: value must be an lvalue and shall be in a unordered_set of appropriate type. More... | |
| static size_type | suggested_upper_bucket_count (size_type n) |
| Effects: Returns the nearest new bucket count optimized for the container that is bigger or equal than n. More... | |
| static size_type | suggested_lower_bucket_count (size_type n) |
| Effects: Returns the nearest new bucket count optimized for the container that is smaller or equal than n. More... | |
Static Public Attributes | |
| static const bool | stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value |
| static const bool | store_hash = detail::store_hash_is_true<node_traits>::value |
| static const bool | unique_keys = 0 != (BoolFlags & hash_bool_flags::unique_keys_pos) |
| static const bool | constant_time_size = 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos) |
| static const bool | cache_begin = 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) |
| static const bool | compare_hash = 0 != (BoolFlags & hash_bool_flags::compare_hash_pos) |
| static const bool | incremental = 0 != (BoolFlags & hash_bool_flags::incremental_pos) |
| static const bool | power_2_buckets = incremental || (0 != (BoolFlags & hash_bool_flags::power_2_buckets_pos)) |
| static const bool | optimize_multikey = detail::optimize_multikey_is_true<node_traits>::value && !unique_keys |
The class template hashtable is an intrusive hash table container, that is used to construct intrusive unordered_set and unordered_multiset containers.
The no-throw guarantee holds only, if the VoidOrKeyEqual object and Hasher don't throw.
hashtable is a semi-intrusive container: each object to be stored in the container must contain a proper hook, but the container also needs additional auxiliary memory to work: hashtable needs a pointer to an array of type bucket_type to be passed in the constructor. This bucket array must have at least the same lifetime as the container. This makes the use of hashtable more complicated than purely intrusive containers. bucket_type is default-constructible, copyable and assignable
The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.
The container supports the following options: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<>, hash<> and equal<> bucket_traits<>, power_2_buckets<>, cache_begin<> and incremental<>.
hashtable only provides forward iterators but it provides 4 iterator types: iterator and const_iterator to navigate through the whole container and local_iterator and const_local_iterator to navigate through the values stored in a single bucket. Local iterators are faster and smaller.
It's not recommended to use non constant-time size hashtables because several key functions, like "empty()", become non-constant time functions. Non constant_time size hashtables are mainly provided to support auto-unlink hooks.
hashtables, does not make automatic rehashings nor offers functions related to a load factor. Rehashing can be explicitly requested and the user must provide a new bucket array that will be used from that moment.
Since no automatic rehashing is done, iterators are never invalidated when inserting or erasing elements. Iterators are only invalidated when rehashing.
| typedef pointer_traits<pointer>::template rebind_pointer< bucket_type >::type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::bucket_ptr |
| typedef pointer_traits<bucket_ptr>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::bucket_reference |
| typedef detail::bucket_impl<slist_impl> boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::bucket_type |
| typedef pointer_traits<pointer>::template rebind_pointer< const bucket_type >::type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_bucket_ptr |
| typedef pointer_traits<bucket_ptr>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_bucket_reference |
| typedef hashtable_iterator<bucket_plus_vtraits_t, true> boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_iterator |
| typedef detail::transform_iterator< typename slist_impl::iterator , downcast_node_to_value_t < value_traits , true> > boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_local_iterator |
| typedef pointer_traits<pointer>::template rebind_pointer< const node >::type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_node_ptr |
| typedef pointer_traits<const_node_ptr>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_node_reference |
| typedef value_traits::const_pointer boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_pointer |
| typedef pointer_traits<const_pointer>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_reference |
| typedef slist_impl::const_iterator boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::const_siterator |
| typedef pointer_traits<pointer>::difference_type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::difference_type |
| typedef data_type::hasher boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::hasher |
| typedef detail::insert_commit_data_impl boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::insert_commit_data |
| typedef hashtable_iterator<bucket_plus_vtraits_t, false> boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::iterator |
| typedef data_type::value_equal boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::key_equal |
| typedef value_type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::key_type |
| typedef detail::transform_iterator< typename slist_impl::iterator , downcast_node_to_value_t < value_traits , false> > boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::local_iterator |
| typedef node_traits::node boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::node |
| typedef slist_impl::node_algorithms boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::node_algorithms |
| typedef pointer_traits<pointer>::template rebind_pointer< node >::type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::node_ptr |
| typedef pointer_traits<node_ptr>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::node_reference |
| typedef value_traits::node_traits boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::node_traits |
| typedef value_traits::pointer boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::pointer |
| typedef pointer_traits<pointer>::reference boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::reference |
| typedef slist_impl::iterator boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::siterator |
| typedef SizeType boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::size_type |
| typedef data_type::value_equal boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::value_equal |
| typedef ValueTraits boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::value_traits |
| typedef value_traits::value_type boost::intrusive::hashtable_impl< ValueTraits, VoidOrKeyHash, VoidOrKeyEqual, SizeType, BucketTraits, BoolFlags >::value_type |
|
inlineexplicit |
Requires: buckets must not be being used by any other resource.
Effects: Constructs an empty unordered_set, storing a reference to the bucket array and copies of the key_hasher and equal_func functors.
Complexity: Constant.
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor or invocation of hash_func or equal_func throws.
Notes: buckets array must be disposed only after *this is disposed.
|
inline |
Effects: to-do
|
inline |
Effects: Returns an iterator pointing to the beginning of the unordered_set.
Complexity: Amortized constant time. Worst case (empty unordered_set): O(this->bucket_count())
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::begin(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::empty().
|
inline |
Effects: Returns a const_iterator pointing to the beginning of the unordered_set.
Complexity: Amortized constant time. Worst case (empty unordered_set): O(this->bucket_count())
Throws: Nothing.
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a local_iterator pointing to the beginning of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a const_local_iterator pointing to the beginning of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Effects: Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed.
Complexity: Constant.
Throws: If the hash functor throws.
Note: the return value is in the range [0, this->bucket_count()).
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::bucket().
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
Effects: Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed.
Complexity: Constant.
Throws: If hash_func throws.
Note: the return value is in the range [0, this->bucket_count()).
|
inline |
Effects: Returns the number of buckets passed in the constructor or the last rehash function.
Complexity: Constant.
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clear_and_dispose(), boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::erase_and_dispose().
|
inline |
Effects: Returns the bucket array pointer passed in the constructor or the last rehash function.
Complexity: Constant.
Throws: Nothing.
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns the number of elements in the nth bucket.
Complexity: Constant.
Throws: Nothing.
|
inline |
Effects: Returns a const_iterator pointing to the beginning of the unordered_set.
Complexity: Amortized constant time. Worst case (empty unordered_set): O(this->bucket_count())
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::begin(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from().
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a const_local_iterator pointing to the beginning of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Effects: Returns a const_iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::end().
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a const_local_iterator pointing to the end of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Effects: Erases all of the elements.
Complexity: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases all of the elements.
Complexity: Linear to the number of elements on the container. Disposer::operator()(pointer) is called for the removed elements.
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from().
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw Cloner should yield to nodes that compare equal and produce the same hash than the original node.
Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. The hash function and the equality predicate are copied from the source.
If store_hash option is true, this method does not use the hash function.
If any operation throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).
Complexity: Linear to erased plus inserted elements.
Throws: If cloner or hasher throw or hash or equality predicate copying throws. Basic guarantee.
|
inline |
Effects: Returns the number of contained elements with the given value
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::count().
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Returns the number of contained elements with the given key
Complexity: Average case O(1), worst case O(this->size()).
Throws: If hash_func or equal throw.
|
inline |
Effects: Returns true if the container is empty.
Complexity: if constant-time size and cache_begin options are disabled, average constant time (worst case, with empty() == true: O(this->bucket_count()). Otherwise constant.
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clear_and_dispose(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from().
|
inline |
Effects: Returns an iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::empty(), boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::end(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::erase_and_dispose().
|
inline |
Effects: Returns a const_iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a local_iterator pointing to the end of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns a const_local_iterator pointing to the end of the sequence stored in the bucket n.
Complexity: Constant.
Throws: Nothing.
Note: [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.
|
inline |
Effects: Returns a range containing all elements with values equivalent to value.
Returns std::make_pair(this->end(), this->end()) if no such elements exist.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::equal_range().
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Returns a range containing all elements with equivalent keys. Returns std::make_pair(this->end(), this->end()) if no such elements exist.
Complexity: Average case O(this->count(key, hash_func, equal_func)). Worst case O(this->size()).
Throws: If hash_func or the equal_func throw.
Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.
|
inline |
Effects: Returns a range containing all elements with values equivalent to value.
Returns std::make_pair(this->end(), this->end()) if no such elements exist.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Returns a range containing all elements with equivalent keys. Returns std::make_pair(this->end(), this->end()) if no such elements exist.
Complexity: Average case O(this->count(key, hash_func, equal_func)). Worst case O(this->size()).
Throws: If the hasher or equal_func throw.
Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.
|
inline |
Effects: Erases the element pointed to by i.
Complexity: Average case O(1), worst case O(this->size()).
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased element. No destructors are called.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::erase().
|
inline |
Effects: Erases the range pointed to by b end e.
Complexity: Average case O(std::distance(b, e)), worst case O(this->size()).
Throws: Nothing.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
|
inline |
Effects: Erases all the elements with the given value.
Returns: The number of erased elements.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws. Basic guarantee.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Erases all the elements that have the same hash and compare equal with the given key.
Returns: The number of erased elements.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If hash_func or equal_func throw. Basic guarantee.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the element pointed to by i. Disposer::operator()(pointer) is called for the removed element.
Complexity: Average case O(1), worst case O(this->size()).
Throws: Nothing.
Note: Invalidates the iterators to the erased elements.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::erase(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::erase_and_dispose().
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.
Complexity: Average case O(std::distance(b, e)), worst case O(this->size()).
Throws: Nothing.
Note: Invalidates the iterators to the erased elements.
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases all the elements with the given value. Disposer::operator()(pointer) is called for the removed elements.
Returns: The number of erased elements.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws. Basic guarantee.
Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.
|
inline |
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases all the elements with the given key. according to the comparison functor "equal_func". Disposer::operator()(pointer) is called for the removed elements.
Returns: The number of erased elements.
Complexity: Average case O(this->count(value)). Worst case O(this->size()).
Throws: If hash_func or equal_func throw. Basic guarantee.
Note: Invalidates the iterators to the erased elements.
|
inline |
Effects: Finds an iterator to the first element is equal to "value" or end() if that element does not exist.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::find().
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Finds an iterator to the first element whose key is "key" according to the given hash and equality functor or end() if that element does not exist.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If hash_func or equal_func throw.
Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.
|
inline |
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Finds an iterator to the first element whose key is "key" according to the given hasher and equality functor or end() if that element does not exist.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If hash_func or equal_func throw.
Note: This function is used when constructing a value_type is expensive and the value_type can be compared with a cheaper key type. Usually this key is part of the value_type.
|
inline |
Effects: Returns the hasher object used by the unordered_set.
Complexity: Constant.
Throws: If hasher copy-constructor throws.
|
inline |
Requires:
Effects:
Complexity:
Throws:
Note: this method is only available if incremental<true> option is activated.
|
inline |
Effects: If new_bucket_traits.bucket_count() is not this->bucket_count()/2 or this->bucket_count()*2, or this->split_bucket() != new_bucket_traits.bucket_count() returns false and does nothing.
Otherwise, copy assigns new_bucket_traits to the internal bucket_traits and transfers all the objects from old buckets to the new ones.
Complexity: Linear to size().
Throws: Nothing
Note: this method is only available if incremental<true> option is activated.
|
inline |
Requires: value must be an lvalue
Effects: Inserts the value into the unordered_set.
Returns: An iterator to the inserted value.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::clone_from(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::insert_equal().
|
inline |
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Equivalent to this->insert_equal(t) for each element in [b, e).
Complexity: Average case O(N), where N is std::distance(b, e). Worst case O(N*this->size()).
Throws: If the internal hasher or the equality functor throws. Basic guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
|
inline |
Requires: value must be an lvalue
Effects: Tries to inserts value into the unordered_set.
Returns: If the value is not already present inserts it and returns a pair containing the iterator to the new value and true. If there is an equivalent value returns a pair containing an iterator to the already present value and false.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws. Strong guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::insert_unique().
|
inline |
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Equivalent to this->insert_unique(t) for each element in [b, e).
Complexity: Average case O(N), where N is std::distance(b, e). Worst case O(N*this->size()).
Throws: If the internal hasher or the equality functor throws. Basic guarantee.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
|
inline |
Requires: "hash_func" must be a hash function that induces the same hash values as the stored hasher.
The difference is that "hash_func" hashes the given key instead of the value_type.
"equal_func" must be a equality function that induces the same equality as key_equal. The difference is that "equal_func" compares an arbitrary key with the contained values.
Effects: Checks if a value can be inserted in the unordered_set, using a user provided key instead of the value itself.
Returns: If there is an equivalent value returns a pair containing an iterator to the already present value and false. If the value can be inserted returns true in the returned pair boolean and fills "commit_data" that is meant to be used with the "insert_commit" function.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If hash_func or equal_func throw. Strong guarantee.
Notes: This function is used to improve performance when constructing a value_type is expensive: if there is an equivalent value the constructed object must be discarded. Many times, the part of the node that is used to impose the hash or the equality is much cheaper to construct than the value_type and this function offers the possibility to use that the part to check if the insertion will be successful.
If the check is successful, the user can construct the value_type and use "insert_commit" to insert the object in constant-time.
"commit_data" remains valid for a subsequent "insert_commit" only if no more objects are inserted or erased from the unordered_set.
After a successful rehashing insert_commit_data remains valid.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::insert_unique().
|
inline |
Requires: value must be an lvalue of type value_type.
commit_data must have been obtained from a previous call to "insert_check". No objects should have been inserted or erased from the unordered_set between the "insert_check" that filled "commit_data" and the call to "insert_commit".
Effects: Inserts the value in the unordered_set using the information obtained from the "commit_data" that a previous "insert_check" filled.
Returns: An iterator to the newly inserted object.
Complexity: Constant time.
Throws: Nothing.
Notes: This function has only sense if a "insert_check" has been previously executed to fill "commit_data". No value should be inserted or erased between the "insert_check" and "insert_commit" calls.
After a successful rehashing insert_commit_data remains valid.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::insert_unique().
|
inline |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: If the internal hash function throws.
|
inline |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid const_iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: If the internal hash function throws.
|
inline |
Effects: Returns the key_equal object used by the unordered_set.
Complexity: Constant.
Throws: If key_equal copy-constructor throws.
|
inline |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid local_iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: Nothing.
|
inline |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid const_local_iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: Nothing.
|
inline |
Effects: to-do
|
inline |
Requires: new_bucket_traits can hold a pointer to a new bucket array or the same as the old bucket array with a different length.
new_size is the length of the the array pointed by new_buckets. If new_bucket_traits.bucket_begin() == this->bucket_pointer() new_bucket_traits.bucket_count() can be bigger or smaller than this->bucket_count(). 'new_bucket_traits' copy constructor should not throw.
Effects: Updates the internal reference with the new bucket, erases the values from the old bucket and inserts then in the new one. Bucket traits hold by *this is assigned from new_bucket_traits. If the container is configured as incremental<>, the split bucket is set to the new bucket_count().
If store_hash option is true, this method does not use the hash function.
Complexity: Average case linear in this->size(), worst case quadratic.
Throws: If the hasher functor throws. Basic guarantee.
|
inlinestatic |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid local_iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: Nothing.
Note: This static function is available only if the value traits is stateless.
|
inlinestatic |
Requires: value must be an lvalue and shall be in a unordered_set of appropriate type.
Otherwise the behavior is undefined.
Effects: Returns: a valid const_local_iterator belonging to the unordered_set that points to the value
Complexity: Constant.
Throws: Nothing.
Note: This static function is available only if the value traits is stateless.
|
inline |
Effects: Returns the number of elements stored in the unordered_set.
Complexity: Linear to elements contained in *this if constant_time_size is false. Constant-time otherwise.
Throws: Nothing.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::empty().
|
inline |
Requires:
Effects:
Complexity:
Throws:
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::incremental_rehash().
|
inlinestatic |
Effects: Returns the nearest new bucket count optimized for the container that is smaller or equal than n.
This suggestion can be used to create bucket arrays with a size that will usually improve container's performance. If such value does not exist, the lowest possible value is returned.
Complexity: Amortized constant time.
Throws: Nothing.
|
inlinestatic |
Effects: Returns the nearest new bucket count optimized for the container that is bigger or equal than n.
This suggestion can be used to create bucket arrays with a size that will usually improve container's performance. If such value does not exist, the higher possible value is returned.
Complexity: Amortized constant time.
Throws: Nothing.
|
inline |
Requires: the hasher and the equality function unqualified swap call should not throw.
Effects: Swaps the contents of two unordered_sets. Swaps also the contained bucket array and equality and hasher functors.
Complexity: Constant.
Throws: If the swap() call for the comparison or hash functors found using ADL throw. Basic guarantee.
Referenced by boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::operator=(), and boost::intrusive::hashtable_impl< ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags >::swap().
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
|
static |
1.8.8