boost unordered_set find

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu , C++ Coding Standards

Class template unordered_set

boost::intrusive::unordered_set

Description

The class template unordered_set is an intrusive container, that mimics most of the interface of std::tr1::unordered_set as described in the C++ TR1.

unordered_set 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: unordered_set 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 unordered_set 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<> and cache_begin<> .

unordered_set 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 unordered_sets because several key functions, like "empty()", become non-constant time functions. Non constant-time size unordered_sets are mainly provided to support auto-unlink hooks.

unordered_set , unlike std::unordered_set, 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 rehasing.

unordered_set public construct/copy/destruct

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.

Requires : buckets must not be being used by any other resource and dereferencing iterator must yield an lvalue of type value_type.

Effects : Constructs an empty container and inserts elements from [b, e).

Complexity : If N is distance(b, e): Average case is O(N) (with a good hash function and with buckets_len >= N),worst case O(N^2).

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 hasher or key_equal throws.

Effects : Constructs a container moving resources from another container. Internal value traits, bucket traits, hasher and comparison are move constructed and nodes belonging to x are linked to *this.

Throws : If value_traits::node_traits::node's move constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the move constructor of value traits, bucket traits, hasher or comparison throws.

Effects : Equivalent to swap.

Effects : Detaches all elements from this. The objects in the unordered_set are not deleted (i.e. no destructors are called).

Complexity : Linear to the number of elements in the unordered_set , if it's a safe-mode or auto-unlink value. Otherwise constant.

Throws : Nothing.

unordered_set public member functions

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())

Effects : Returns a const_iterator pointing to the beginning of the unordered_set .

Effects : Returns an iterator pointing to the end of the unordered_set .

Effects : Returns a const_iterator pointing to the end of the unordered_set .

Effects : Returns the hasher object used by the unordered_set .

Throws : If hasher copy-constructor throws.

Effects : Returns the key_equal object used by the unordered_set .

Throws : If key_equal copy-constructor throws.

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.

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.

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.

Effects : Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(reference) and inserts them on *this. The hash function and the equality predicate are copied from the source.

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.

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 distance(b, e). Worst case O(N*this->size()).

Throws : If the internal hasher or the equality functor throws. Basic guarantee.

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.

Throws : If hasher or key_compare 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.

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.

Throws : If hash_func or equal_func throw. Strong guarantee.

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.

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.

Effects : Erases the element pointed to by i.

Note : Invalidates the iterators (but not the references) to the erased element. No destructors are called.

Effects : Erases the range pointed to by b end e.

Complexity : Average case O(distance(b, e)), worst case O(this->size()).

Note : Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

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()).

Effects : Erases all the elements that have the same hash and compare equal with the given key.

Throws : If hash_func or equal_func throw. Basic guarantee.

Requires : Disposer::operator()(pointer) shouldn't throw.

Effects : Erases the element pointed to by i. Disposer::operator()(pointer) is called for the removed element.

Note : Invalidates the iterators to the erased elements.

Effects : Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.

Effects : Erases all the elements with the given value. Disposer::operator()(pointer) is called for the removed elements.

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.

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.

Complexity : Linear to the number of elements on the container. Disposer::operator()(pointer) is called for the removed elements.

Effects : Returns the number of contained elements with the given value

Throws : If the internal hasher or the equality functor throws.

Effects : Returns the number of contained elements with the given key

Throws : If hash_func or equal throw.

Effects : Finds an iterator to the first element is equal to "value" or end() if that element does not exist.

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.

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.

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.

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.

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.

Throws : If the hasher or equal_func throw.

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

Throws : If the internal hash function throws.

Effects : Returns: a valid const_iterator belonging to the unordered_set that points to the value

Effects : Returns: a valid local_iterator belonging to the unordered_set that points to the value

Effects : Returns the number of buckets passed in the constructor or the last rehash function.

Requires : n is in the range [0, this->bucket_count()).

Effects : Returns the number of elements in the nth bucket.

Effects : Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed.

Throws : If the hash functor throws.

Note : the return value is in the range [0, this->bucket_count()).

Throws : If hash_func throws.

Effects : Returns the bucket array pointer passed in the constructor or the last rehash function.

Effects : Returns a local_iterator pointing to the beginning of the sequence stored in the bucket n.

Note : [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.

Effects : Returns a const_local_iterator pointing to the beginning of the sequence stored in the bucket n.

Effects : Returns a local_iterator pointing to the end of the sequence stored in the bucket n.

Effects : Returns a const_local_iterator pointing to the end of the sequence stored in the bucket n.

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 : If new_bucket_traits.bucket_begin() == this->bucket_pointer() is false, unlinks values from the old bucket and inserts then in the new one according to the hash value of values.

If new_bucket_traits.bucket_begin() == this->bucket_pointer() is true, the implementations avoids moving values as much as possible.

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. If false, the implementation tries to minimize calls to the hash function (e.g. once for equivalent values if optimize_multikey<true> is true).

If rehash is successful updates the internal bucket_traits with new_bucket_traits.

Complexity : Average case linear in this->size(), worst case quadratic.

Throws : If the hasher functor throws. Basic guarantee.

Note : This function is used when keys from inserted elements are changed (e.g. a language change when key is a string) but uniqueness and hash properties are preserved so a fast full rehash recovers invariants for *this without extracting and reinserting all elements again.

Requires : Calls produced to the hash function should not alter the value uniqueness properties of already inserted elements. If hasher(key1) == hasher(key2) was true when elements were inserted, it shall be true during calls produced in the execution of this function.

key_equal is not called inside this function so it is assumed that key_equal(value1, value2) should produce the same results as before for inserted elements.

Effects : Reprocesses all values hold by *this, recalculating their hash values and redistributing them though the buckets.

If store_hash option is true, this method uses the hash function and updates the stored hash value.

Complexity :

Note : this method is only available if incremental<true> option is activated.

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

Requires : incremental<> option must be set

Effects : returns the current split count

Complexity : Constant

unordered_set public static functions

Note : This static function is available only if the value traits is stateless.

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.

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.

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu , C++ Coding Standards

Class template unordered_set

boost::intrusive::unordered_set

Description

The class template unordered_set is an intrusive container, that mimics most of the interface of std::tr1::unordered_set as described in the C++ TR1.

unordered_set is a pseudo-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: unordered_set 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 unordered_set 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<> .

unordered_set 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 unordered_sets because several key functions, like "empty()", become non-constant time functions. Non constant-time size unordered_sets are mainly provided to support auto-unlink hooks.

unordered_set, unlike std::unordered_set, 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 rehasing.

unordered_set public construct/copy/destruct

Requires : buckets must not be being used by any other resource.

Effects : Constructs an empty unordered_set_impl, storing a reference to the bucket array and copies of the hasher and equal 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 or Equal throws.

Notes : buckets array must be disposed only after this is disposed.

Requires : buckets must not be being used by any other resource and Dereferencing iterator must yield an lvalue of type value_type.

Effects : Constructs an empty unordered_set and inserts elements from [b, e).

Complexity : If N is std::distance(b, e): Average case is O(N) (with a good hash function and with buckets_len >= N),worst case O(N2).

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 hasher or key_equal throws.

Effects : Detaches all elements from this. The objects in the unordered_set are not deleted (i.e. no destructors are called).

Complexity : Linear to the number of elements in the unordered_set, if it's a safe-mode or auto-unlink value. Otherwise constant.

Throws : Nothing.

unordered_set public member functions

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())

Effects : Returns a const_iterator pointing to the beginning of the unordered_set.

Effects : Returns an iterator pointing to the end of the unordered_set.

Effects : Returns a const_iterator pointing to the end of the unordered_set.

Effects : Returns the hasher object used by the unordered_set.

Throws : If hasher copy-constructor throws.

Effects : Returns the key_equal object used by the unordered_set.

Throws : If key_equal copy-constructor throws.

Effects : Returns true is the container is empty.

Complexity : if constant-time size option is disabled, average constant time (worst case, with empty() == true): O(this->bucket_count()). Otherwise constant.

Effects : Returns the number of elements stored in the unordered_set.

Complexity : Linear to elements contained in *this if constant-time size option is enabled. Constant-time otherwise.

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.

Throws : If the swap() call for the comparison or hash functors found using ADL throw. Basic guarantee.

Requires : Disposer::operator()(pointer) shouldn't throw.

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.

If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

Complexity : Linear to erased plus inserted elements.

Throws : If cloner throws. Basic guarantee.

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.

Requires : Dereferencing iterator must yield an lvalue of type value_type.

Effects : Equivalent to this->insert(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.

Requires : "hasher" must be a hash function that induces the same hash values as the stored hasher. The difference is that "hasher" hashes the given key instead of the value_type.

"key_value_equal" must be a equality function that induces the same equality as key_equal. The difference is that "key_value_equal" 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.

Throws : If hasher or key_value_equal 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.

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.

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.

Effects : Erases the element pointed to by i.

Note : Invalidates the iterators (but not the references) to the erased element. No destructors are called.

Effects : Erases the range pointed to by b end e.

Complexity : Average case O(std::distance(b, e)), worst case O(this->size()).

Note : Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

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()).

Effects : Erases all the elements that have the same hash and compare equal with the given key.

Throws : If hash_func or equal_func throw. Basic guarantee.

Effects : Erases the element pointed to by i. Disposer::operator()(pointer) is called for the removed element.

Note : Invalidates the iterators to the erased elements.

Effects : Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.

Effects : Erases all the elements with the given value. Disposer::operator()(pointer) is called for the removed elements.

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.

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.

Complexity : Linear to the number of elements on the container. Disposer::operator()(pointer) is called for the removed elements.

Effects : Returns the number of contained elements with the given value

Throws : If the internal hasher or the equality functor throws.

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

Throws : If hash_func or equal_func throw.

Effects : Finds an iterator to the first element is equal to "value" or end() if that element does not exist.

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.

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.

Effects : Finds a const_iterator to the first element whose key is "key" or end() if that element does not exist.

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.

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, hash_func)). Worst case O(this->size()).

Throws : If hash_func or the equal_func throw.

Complexity : Average case O(this->count(key, hash_func, equal_func)). Worst case O(this->size()).

Throws : If the hash_func or equal_func throw.

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

Throws : If the internal hash function throws.

Effects : Returns: a valid const_iterator belonging to the unordered_set that points to the value

Effects : Returns: a valid local_iterator belonging to the unordered_set that points to the value

Effects : Returns: a valid const_local_iterator belonging to the unordered_set that points to the value

Effects : Returns the number of buckets passed in the constructor or the last rehash function.

Requires : n is in the range [0, this->bucket_count()).

Effects : Returns the number of elements in the nth bucket.

Effects : Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such element existed.

Throws : If the hash functor throws.

Note : the return value is in the range [0, this->bucket_count()).

Throws : If hash_func throws.

Effects : Returns the bucket array pointer passed in the constructor or the last rehash function.

Effects : Returns a local_iterator pointing to the beginning of the sequence stored in the bucket n.

Note : [this->begin(n), this->end(n)) is a valid range containing all of the elements in the nth bucket.

Effects : Returns a const_local_iterator pointing to the beginning of the sequence stored in the bucket n.

Effects : Returns a local_iterator pointing to the end of the sequence stored in the bucket n.

Effects : Returns a const_local_iterator pointing to the end of the sequence stored in the bucket n.

Requires : new_buckets must be a pointer to a new bucket array or the same as the old bucket array. new_size is the length of the the array pointed by new_buckets. If new_buckets == this->bucket_pointer() n can be bigger or smaller than this->bucket_count().

Effects : Updates the internal reference with the new bucket erases the values from the old bucket and inserts then in the new one.

Complexity : Average case linear in this->size(), worst case quadratic.

Throws : If the hasher functor throws. Basic guarantee.

unordered_set public static functions

Note : This static function is available only if the value traits is stateless.

Effects : Returns the nearest new bucket count optimized for the container that is bigger 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.

Effects : Returns the nearest new bucket count optimized for the container that is smaller 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 lower possible value is returned.

Chapter 15. Boost.Unordered

Boost.Unordered provides the classes boost::unordered_set , boost::unordered_multiset , boost::unordered_map , and boost::unordered_multimap . These classes are identical to the hash containers that were added to the standard library with C++11. Thus, you can ignore the containers from Boost.Unordered if you work with a development environment supporting C++11.

boost::unordered_set can be replaced with std::unordered_set in Example 15.1 . boost::unordered_set doesn’t differ from std::unordered_set .

Example 15.2 uses boost::unordered_map to store the names and the number of legs for several animals. Once again, boost::unordered_map could be replaced with std::unordered_map .

In Example 15.3 elements of type animal are stored in a container of type boost::unordered_set . Because the hash function of boost::unordered_set doesn’t know the class animal , hash values can’t be automatically calculated for elements of this type. That’s why a hash function must be defined – otherwise the example can’t be compiled.

The name of the hash function to define is hash_value() . It must expect as its sole parameter an object of the type the hash value should be calculated for. The type of the return value of hash_value() must be std::size_t .

The function hash_value() is automatically called when the hash value has to be calculated for an object. This function is defined for various types in the Boost libraries, including std::string . For user-defined types like animal , it must be defined by the developer.

Usually, the definition of hash_value() is rather simple: Hash values are created by accessing the member variables of an object one after another. This is done with the function boost::hash_combine() , which is provided by Boost.Hash and defined in boost/functional/hash.hpp . You don’t have to include this header file if you use Boost.Unordered because all containers from this library access Boost.Hash to calculate hash values.

In addition to defining hash_value() , you need to make sure two objects can be compared using == . That’s why the operator operator== is overloaded for animal in Example 15.3 .

The hash containers from the C++11 standard library use a hash function from the header file functional . The hash containers from Boost.Unordered expect the hash function hash_value() . Whether you use Boost.Hash within hash_value() doesn’t matter. Boost.Hash makes sense because functions like boost::hash_combine() make it easier to calculate hash values from multiple member variables step by step. However, this is only an implementation detail of hash_value() . Apart from the different hash functions used, the hash containers from Boost.Unordered and the standard library are basically equivalent.

• <cassert> (assert.h)
• <cctype> (ctype.h)
• <cerrno> (errno.h)
• C++11 <cfenv> (fenv.h)
• <cfloat> (float.h)
• C++11 <cinttypes> (inttypes.h)
• <ciso646> (iso646.h)
• <climits> (limits.h)
• <clocale> (locale.h)
• <cmath> (math.h)
• <csetjmp> (setjmp.h)
• <csignal> (signal.h)
• <cstdarg> (stdarg.h)
• C++11 <cstdbool> (stdbool.h)
• <cstddef> (stddef.h)
• C++11 <cstdint> (stdint.h)
• <cstdio> (stdio.h)
• <cstdlib> (stdlib.h)
• <cstring> (string.h)
• C++11 <ctgmath> (tgmath.h)
• <ctime> (time.h)
• C++11 <cuchar> (uchar.h)
• <cwchar> (wchar.h)
• <cwctype> (wctype.h)

Containers:

• C++11 <array>
• <deque>
• C++11 <forward_list>
• <list>
• <map>
• <queue>
• <set>
• <stack>
• C++11 <unordered_map>
• C++11 <unordered_set>
• <vector>

Input/Output:

• <fstream>
• <iomanip>
• <ios>
• <iosfwd>
• <iostream>
• <istream>
• <ostream>
• <sstream>
• <streambuf>

Multi-threading:

• C++11 <atomic>
• C++11 <condition_variable>
• C++11 <future>
• C++11 <mutex>
• C++11 <thread>
• <algorithm>
• <bitset>
• C++11 <chrono>
• C++11 <codecvt>
• <complex>
• <exception>
• <functional>
• C++11 <initializer_list>
• <iterator>
• <limits>
• <locale>
• <memory>
• <new>
• <numeric>
• C++11 <random>
• C++11 <ratio>
• C++11 <regex>
• <stdexcept>
• <string>
• C++11 <system_error>
• C++11 <tuple>
• C++11 <type_traits>
• C++11 <typeindex>
• <typeinfo>
• <utility>
• <valarray>
• <unordered_set>
• C++11 unordered_multiset
• C++11 unordered_set
• unordered_set
• C++11 unordered_set::~unordered_set
• C++11 unordered_set::unordered_set

member functions

• C++11 unordered_set::begin
• C++11 unordered_set::bucket
• C++11 unordered_set::bucket_count
• C++11 unordered_set::bucket_size
• C++11 unordered_set::cbegin
• C++11 unordered_set::cend
• C++11 unordered_set::clear
• C++11 unordered_set::count
• C++11 unordered_set::emplace
• C++11 unordered_set::emplace_hint
• C++11 unordered_set::empty
• C++11 unordered_set::end
• C++11 unordered_set::equal_range
• C++11 unordered_set::erase
• C++11 unordered_set::find
• C++11 unordered_set::get_allocator
• C++11 unordered_set::hash_function
• C++11 unordered_set::insert
• C++11 unordered_set::key_eq
• C++11 unordered_set::load_factor
• C++11 unordered_set::max_bucket_count
• C++11 unordered_set::max_load_factor
• C++11 unordered_set::max_size
• C++11 unordered_set::operator=
• C++11 unordered_set::rehash
• C++11 unordered_set::reserve
• C++11 unordered_set::size
• C++11 unordered_set::swap

non-member overloads

• C++11 operators (unordered_set)
• C++11 swap (unordered_set)

std:: unordered_set ::find

Return value, iterator validity.

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Boost.org unordered module

boostorg/unordered

Folders and files, repository files navigation, boost.unordered.

Boost.Unordered offers a catalog of hash containers with different standards compliance levels, performances and intented usage scenarios:

boost::unordered_set boost::unordered_map boost::unordered_multiset boost::unordered_multimap

boost::unordered_flat_set boost::unordered_flat_map

boost::unordered_node_set boost::unordered_node_map

boost::concurrent_flat_set boost::concurrent_flat_map

Learn about Boost.Unordered

• Online documentation
• Some benchmarks
• Advancing the state of the art for std::unordered_map implementations
• Inside boost::unordered_flat_map
• Inside boost::concurrent_flat_map
• Bulk visitation in boost::concurrent_flat_map

Get the library

Boost.Unordered can be installed in a number of ways:

• Download Boost and you're ready to go (this is a header-only library requiring no building).
• Using Conan 2: In case you don't have it yet, add an entry for Boost in your conanfile.txt (the example requires at least Boost 1.83):
• Using vcpkg: Execute the command
• Using CMake: Boost CMake support infrastructure allows you to use CMake directly to download, build and consume all of Boost or some specific libraries.
• Join the #boost-unordered discussion group at cpplang.slack.com ( ask for an invite if you’re not a member of this workspace yet)
• Ask in the Boost Users mailing list (add the [unordered] tag at the beginning of the subject line)
• File an issue
• Pull requests against develop branch are most welcome. Note that by submitting patches you agree to license your modifications under the Boost Software License, Version 1.0 .

Contributors 20

• C++ Data Types
• C++ Input/Output
• C++ Pointers
• C++ Interview Questions
• C++ Programs
• C++ Cheatsheet
• C++ Projects
• C++ Exception Handling
• C++ Memory Management
• Unordered Sets in C++ Standard Template Library
• Different Ways to Initialize an unordered_set in C++

Commonly Used Methods

• unordered_set begin() function in C++ STL
• unordered_set end() in C++ STL
• unordered_set size() function in C++ STL
• unordered_set empty() function in C++ STL
• unordered_set insert() function in C++ STL
• unordered_set emplace() function in C++ STL

unordered_set find() function in C++ STL

• unordered_set count() function in C++ STL
• unordered_set erase() function in C++ STL
• unordered_set swap() in C++ STL
• unordered_set bucket() function in C++ STL

Other Member Methods

• unordered_set reserve() function in C++ STL
• unordered_set max_size() in C++ STL
• unordered_set max_bucket_count() function in C++ STL
• unordered_set max_load_factor() in C++ STL
• unordered_set load_factor() function in C++ STL
• unordered_set bucket_size() in C++ STL
• unordered_set bucket_count() function in C++ STL
• unordered_set hash_function() in C++ STL
• unordered_set emplace_hint() function in C++ STL
• unordered_set equal_range in C++ STL
• unordered_set operators in C++ STL
• unordered set of Vectors in C++ with Examples
• unordered set of Pairs in C++ with Examples
• How to create an unordered_set of user defined class or struct in C++?
• set vs unordered_set in C++ STL

The unordered_set::find() function is a built-in function in C++ STL which is used to search for an element in the container. It returns an iterator to the element, if found else, it returns an iterator pointing to unordered_set::end(). 

Parameter : This function accepts a mandatory parameter key which specifies the element to be searched for. 

Return Value : It returns an iterator to the element if found, else returns an iterator pointing to the end of unordered_set.

Below programs illustrate the unordered_set::find() function: 

Program 1 : 

Time Complexity: O(1)

Auxiliary Space: O(n)

Program 2 : 

Please Login to comment...

Similar reads.

• CPP-Functions
• cpp-unordered_set
• cpp-unordered_set-functions

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu , C++ Coding Standards

boost/intrusive/unordered_set.hpp

Revised $Date$

Copyright Beman Dawes, David Abrahams, 1998-2005.

Copyright Rene Rivera 2004-2008.

Distributed under the Boost Software License, Version 1.0 .

OSI Certified