Boost C++ Libraries

explicit unordered_set(const bucket_traits & b_traits, 
                       const hasher & hash_func = hasher(), 
                       const key_equal & equal_func = key_equal(), 
                       const value_traits & v_traits = value_traits());

template<typename Iterator> 
  unordered_set(Iterator b, Iterator e, const bucket_traits & b_traits, 
                const hasher & hash_func = hasher(), 
                const key_equal & equal_func = key_equal(), 
                const value_traits & v_traits = value_traits());

unordered_set(unordered_set && x);

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.

Complexity: Constant.

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.

unordered_set & operator=(unordered_set && x);

Effects: Equivalent to swap.

~unordered_set();

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.

iterator begin() noexcept;

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 noexcept;

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 noexcept;

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

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

Complexity: Constant.

Throws: Nothing.

const_iterator end() const noexcept;

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

Complexity: Constant.

Throws: Nothing.

const_iterator cend() const noexcept;

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 noexcept;

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.

size_type size() const noexcept;

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(unordered_set & other);

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.

template<typename Cloner, typename Disposer> 
  void clone_from(const unordered_set & 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.

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.

template<typename Cloner, typename Disposer> 
  void clone_from(unordered_set && 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.

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.

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.

std::pair< iterator, bool > insert(reference value);

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_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.

Note: Does not affect the validity of iterators and references. No copy-constructors are called.

std::pair< iterator, bool > 
insert_check(const key_type & key, insert_commit_data & commit_data);

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  std::pair< iterator, bool > 
  insert_check(const KeyType & key, KeyHasher hash_func, 
               KeyEqual key_value_equal, insert_commit_data & commit_data);

iterator insert_commit(reference value, 
                       const insert_commit_data & commit_data) noexcept;

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.

iterator insert_fast_commit(reference value, 
                            const insert_commit_data & commit_data) noexcept;

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".

No rehashing shall be performed between insert_check and insert_fast_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.

Since this commit operation does not support rehashing between the check and the commit, it's faster than insert_commit.

void erase(const_iterator i);

void erase(const_iterator b, const_iterator e) noexcept;

size_type erase(const key_type & key);

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  size_type erase(const KeyType & key, KeyHasher hash_func, 
                  KeyEqual 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) noexcept;

template<typename Disposer> 
  void erase_and_dispose(const_iterator b, const_iterator e, 
                         Disposer disposer) noexcept;

template<typename Disposer> 
  size_type erase_and_dispose(const key_type & key, Disposer disposer);

template<typename KeyType, typename KeyHasher, typename KeyEqual, 
         typename Disposer> 
  size_type erase_and_dispose(const KeyType & key, KeyHasher hash_func, 
                              KeyEqual 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() noexcept;

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) noexcept;

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 key_type & key) const;

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  size_type count(const KeyType & key, KeyHasher hash_func, 
                  KeyEqual 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 key_type & key);

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  iterator find(const KeyType & key, KeyHasher hash_func, KeyEqual 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 key_type & key) const;

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  const_iterator 
  find(const KeyType & key, KeyHasher hash_func, KeyEqual 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 key_type & key);

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  std::pair< iterator, iterator > 
  equal_range(const KeyType & key, KeyHasher hash_func, KeyEqual 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 key_type & key) const;

template<typename KeyType, typename KeyHasher, typename KeyEqual> 
  std::pair< const_iterator, const_iterator > 
  equal_range(const KeyType & key, KeyHasher hash_func, KeyEqual 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) noexcept;

const_iterator iterator_to(const_reference value) const noexcept;

local_iterator local_iterator_to(reference value) noexcept;

const_local_iterator local_iterator_to(const_reference value) const noexcept;

size_type bucket_count() const noexcept;

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 noexcept;

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;

template<typename KeyType, typename KeyHasher> 
  size_type bucket(const KeyType & k, 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 noexcept;

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) noexcept;

const_local_iterator begin(size_type n) const noexcept;

const_local_iterator cbegin(size_type n) const noexcept;

local_iterator end(size_type n) noexcept;

const_local_iterator end(size_type n) const noexcept;

const_local_iterator cend(size_type n) const noexcept;

void rehash(const bucket_traits & new_bucket_traits);

void full_rehash();

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: Average case linear in this->size(), worst case quadratic.

Throws: If the hasher functor throws. Basic guarantee.

bool incremental_rehash(bool grow = true);

Requires:

Effects:

Complexity:

Throws:

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

bool incremental_rehash(const bucket_traits & new_bucket_traits);

size_type split_count() const noexcept;

Requires: incremental<> option must be set

Effects: returns the current split count

Complexity: Constant

Throws: Nothing

static local_iterator s_local_iterator_to(reference value) noexcept;

static const_local_iterator 
s_local_iterator_to(const_reference value) noexcept;

static size_type suggested_upper_bucket_count(size_type n) noexcept;

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.

static size_type suggested_lower_bucket_count(size_type n) noexcept;

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.