const real_value_traits & get_real_value_traits() const;
real_value_traits & get_real_value_traits() ;
-
iterator begin() ;
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.
-
const_iterator begin() const;
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.
-
const_iterator cbegin() const;
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.
-
iterator end() ;
Effects: Returns an iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
-
const_iterator end() const;
Effects: Returns a const_iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
-
const_iterator cend() const;
Effects: Returns a const_iterator pointing to the end of the unordered_set.
Complexity: Constant.
Throws: Nothing.
-
hasher hash_function() const;
Effects: Returns the hasher object used by the unordered_set.
Complexity: Constant.
Throws: If hasher copy-constructor throws.
-
key_equal key_eq() const;
Effects: Returns the key_equal object used by the unordered_set.
Complexity: Constant.
Throws: If key_equal copy-constructor throws.
-
bool empty() const;
Effects: Returns true is the container is empty.
Complexity: if constant-time size and cache_last options are disabled, average constant time (worst case, with empty() == true: O(this->bucket_count()). Otherwise constant.
Throws: Nothing.
-
size_type size() const;
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.
-
void swap(hashtable & other) ;
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.
-
template<typename Cloner, typename Disposer>
void clone_from(const hashtable & src, Cloner cloner, Disposer disposer) ;
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.
iterator insert_equal(reference value) ;
template<typename Iterator> void insert_equal(Iterator b, Iterator e) ;
-
std::pair< iterator, bool > insert_unique(reference value) ;
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.
-
template<typename Iterator> void insert_unique(Iterator b, Iterator e) ;
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.
Note: Does not affect the validity of iterators and references. No copy-constructors are called.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
iterator insert_unique_commit(reference value,
const insert_commit_data & commit_data) ;
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.
-
void erase(const_iterator i) ;
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.
-
void erase(const_iterator b, const_iterator e) ;
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.
-
size_type erase(const_reference value) ;
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.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
template<typename Disposer>
void erase_and_dispose(const_iterator i, Disposer disposer) ;
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.
-
template<typename Disposer>
void erase_and_dispose(const_iterator b, const_iterator e,
Disposer disposer) ;
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.
-
template<typename Disposer>
size_type erase_and_dispose(const_reference value, Disposer disposer) ;
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.
-
template<typename KeyType, typename KeyHasher, typename KeyValueEqual,
typename Disposer>
size_type erase_and_dispose(const KeyType & key, KeyHasher hash_func,
KeyValueEqual equal_func, Disposer disposer) ;
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.
-
void clear() ;
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.
-
template<typename Disposer> void clear_and_dispose(Disposer disposer) ;
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.
-
size_type count(const_reference value) const;
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.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
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.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
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.
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
std::pair< iterator, iterator > equal_range(const_reference value) ;
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.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
std::pair< const_iterator, const_iterator >
equal_range(const_reference value) const;
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.
-
template<typename KeyType, typename KeyHasher, typename 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. 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.
-
iterator iterator_to(reference value) ;
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.
-
const_iterator iterator_to(const_reference value) const;
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.
-
local_iterator local_iterator_to(reference value) ;
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.
-
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. 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.
-
size_type bucket_count() const;
Effects: Returns the number of buckets passed in the constructor or the last rehash function.
Complexity: Constant.
Throws: Nothing.
-
size_type bucket_size(size_type n) const;
Requires: n is in the range [0, this->bucket_count()).
Effects: Returns the number of elements in the nth bucket.
Complexity: Constant.
Throws: Nothing.
-
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.
Complexity: Constant.
Throws: If the hash functor throws.
Note: the return value is in the range [0, this->bucket_count()).
-
template<typename KeyType, typename 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. 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()).
-
bucket_ptr bucket_pointer() const;
Effects: Returns the bucket array pointer passed in the constructor or the last rehash function.
Complexity: Constant.
Throws: Nothing.
-
local_iterator begin(size_type n) ;
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.
-
const_local_iterator begin(size_type n) const;
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.
-
const_local_iterator cbegin(size_type n) const;
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.
-
local_iterator end(size_type n) ;
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.
-
const_local_iterator end(size_type n) const;
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.
-
const_local_iterator cend(size_type n) const;
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.
-
void rehash(const bucket_traits & new_bucket_traits) ;
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.