-
iterator begin() ;
Effects: Returns an iterator pointing to the beginning of the unordered_multiset.
Complexity: Constant time if `cache_begin<>` is true. Amortized constant time with 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_multiset.
Complexity: Constant time if `cache_begin<>` is true. Amortized constant time with 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_multiset.
Complexity: Constant time if `cache_begin<>` is true. Amortized constant time with worst case (empty unordered_set) O(this->bucket_count())
Throws: Nothing.
-
iterator end() ;
Effects: Returns an iterator pointing to the end of the unordered_multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator end() const;
Effects: Returns a const_iterator pointing to the end of the unordered_multiset.
Complexity: Constant.
Throws: Nothing.
-
const_iterator cend() const;
Effects: Returns a const_iterator pointing to the end of the unordered_multiset.
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_multiset.
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_multiset.
Complexity: Linear to elements contained in *this if constant-time size option is enabled. Constant-time otherwise.
Throws: Nothing.
-
void swap(unordered_multiset & other) ;
Requires: the hasher and the equality function unqualified swap call should not throw.
Effects: Swaps the contents of two unordered_multisets. 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 unordered_multiset & 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.
-
iterator insert(reference value) ;
Requires: value must be an lvalue
Effects: Inserts value into the unordered_multiset.
Returns: An iterator to the new 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.
-
template<typename Iterator> void insert(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: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().
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.
-
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.
"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: 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 the hash_func or the equal_func functors throws. 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 the elements of the container.
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 the elements of the container.
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 key
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, 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.
"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: Returns the number of contained elements with the given key
Complexity: Average case O(1), worst case O(this->size()).
Throws: If the internal hasher or the equality functor throws.
-
iterator find(const_reference value) ;
Effects: Finds an iterator to the first element whose value is "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.
"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: 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 the internal hasher or the equality functor throws.
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.
"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: 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 the internal hasher or the equality functor throws.
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.
"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: 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 internal hasher or the equality functor throws.
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.
"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: 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 internal hasher or the equality functor throws.
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_multiset of appropriate type. Otherwise the behavior is undefined.
Effects: Returns: a valid iterator belonging to the unordered_multiset that points to the value
Complexity: Constant.
Throws: If the hash function throws.
-
const_iterator iterator_to(const_reference value) const;
Requires: value must be an lvalue and shall be in a unordered_multiset of appropriate type. Otherwise the behavior is undefined.
Effects: Returns: a valid const_iterator belonging to the unordered_multiset that points to the value
Complexity: Constant.
Throws: If the 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 value_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 the hash functor 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.