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

PrevUpHomeNext

Class template unordered_multiset

boost::intrusive::unordered_multiset

Synopsis

// In header: <boost/intrusive/unordered_set.hpp>

template<typename T, class ... Options> 
class unordered_multiset {
public:
  // types
  typedef implementation_defined::value_type           value_type;          
  typedef implementation_defined::key_type             key_type;            
  typedef implementation_defined::value_traits         value_traits;        
  typedef implementation_defined::bucket_traits        bucket_traits;       
  typedef implementation_defined::pointer              pointer;             
  typedef implementation_defined::const_pointer        const_pointer;       
  typedef implementation_defined::reference            reference;           
  typedef implementation_defined::const_reference      const_reference;     
  typedef implementation_defined::difference_type      difference_type;     
  typedef implementation_defined::size_type            size_type;           
  typedef implementation_defined::key_equal            key_equal;           
  typedef implementation_defined::hasher               hasher;              
  typedef implementation_defined::bucket_type          bucket_type;         
  typedef implementation_defined::bucket_ptr           bucket_ptr;          
  typedef implementation_defined::iterator             iterator;            
  typedef implementation_defined::const_iterator       const_iterator;      
  typedef implementation_defined::insert_commit_data   insert_commit_data;  
  typedef implementation_defined::local_iterator       local_iterator;      
  typedef implementation_defined::const_local_iterator const_local_iterator;
  typedef implementation_defined::node_traits          node_traits;         
  typedef implementation_defined::node                 node;                
  typedef implementation_defined::node_ptr             node_ptr;            
  typedef implementation_defined::const_node_ptr       const_node_ptr;      

  // public member functions
  explicit unordered_multiset(const bucket_traits &, 
                              const hasher & = hasher(), 
                              const key_equal & = key_equal(), 
                              const value_traits & = value_traits());
  template<typename Iterator> 
    unordered_multiset(Iterator, Iterator, const bucket_traits &, 
                       const hasher & = hasher(), 
                       const key_equal & = key_equal(), 
                       const value_traits & = value_traits());
  unordered_multiset(unordered_multiset &&);
  unordered_multiset & operator=(unordered_multiset &&);
  ~unordered_multiset();
  iterator begin() noexcept;
  const_iterator begin() const noexcept;
  const_iterator cbegin() const noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  const_iterator cend() const noexcept;
  hasher hash_function() const;
  key_equal key_eq() const;
  bool empty() const noexcept;
  size_type size() const noexcept;
  void swap(unordered_multiset &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const unordered_multiset &, Cloner, Disposer);
  template<typename Cloner, typename Disposer> 
    void clone_from(unordered_multiset &&, Cloner, Disposer);
  iterator insert(reference);
  template<typename Iterator> void insert(Iterator, Iterator);
  void erase(const_iterator);
  void erase(const_iterator, const_iterator) noexcept;
  size_type erase(const key_type &);
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    size_type erase(const KeyType &, KeyHasher, KeyEqual);
  template<typename Disposer> 
    void erase_and_dispose(const_iterator, Disposer) noexcept;
  template<typename Disposer> 
    void erase_and_dispose(const_iterator, const_iterator, Disposer) noexcept;
  template<typename Disposer> 
    size_type erase_and_dispose(const key_type &, Disposer);
  template<typename KeyType, typename KeyHasher, typename KeyEqual, 
           typename Disposer> 
    size_type erase_and_dispose(const KeyType &, KeyHasher, KeyEqual, 
                                Disposer);
  void clear() noexcept;
  template<typename Disposer> void clear_and_dispose(Disposer) noexcept;
  size_type count(const key_type &) const;
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    size_type count(const KeyType &, KeyHasher, KeyEqual) const;
  iterator find(const key_type &);
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    iterator find(const KeyType &, KeyHasher, KeyEqual);
  const_iterator find(const key_type &) const;
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    const_iterator find(const KeyType &, KeyHasher, KeyEqual) const;
  std::pair< iterator, iterator > equal_range(const key_type &);
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    std::pair< iterator, iterator > 
    equal_range(const KeyType &, KeyHasher, KeyEqual);
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) const;
  template<typename KeyType, typename KeyHasher, typename KeyEqual> 
    std::pair< const_iterator, const_iterator > 
    equal_range(const KeyType &, KeyHasher, KeyEqual) const;
  iterator iterator_to(reference) noexcept;
  const_iterator iterator_to(const_reference) const noexcept;
  local_iterator local_iterator_to(reference) noexcept;
  const_local_iterator local_iterator_to(const_reference) const noexcept;
  size_type bucket_count() const noexcept;
  size_type bucket_size(size_type) const noexcept;
  size_type bucket(const key_type &) const;
  template<typename KeyType, typename KeyHasher> 
    size_type bucket(const KeyType &, KeyHasher) const;
  bucket_ptr bucket_pointer() const noexcept;
  local_iterator begin(size_type) noexcept;
  const_local_iterator begin(size_type) const noexcept;
  const_local_iterator cbegin(size_type) const noexcept;
  local_iterator end(size_type) noexcept;
  const_local_iterator end(size_type) const noexcept;
  const_local_iterator cend(size_type) const noexcept;
  void rehash(const bucket_traits &);
  void full_rehash();
  bool incremental_rehash(bool = true);
  bool incremental_rehash(const bucket_traits &);
  size_type split_count() const noexcept;

  // public static functions
  static local_iterator s_local_iterator_to(reference) noexcept;
  static const_local_iterator s_local_iterator_to(const_reference) noexcept;
  static size_type suggested_upper_bucket_count(size_type) noexcept;
  static size_type suggested_lower_bucket_count(size_type) noexcept;
};

Description

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

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

unordered_multiset, 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_multiset public member functions

  1. explicit unordered_multiset(const bucket_traits & b_traits, 
                                const hasher & hash_func = hasher(), 
                                const key_equal & equal_func = key_equal(), 
                                const value_traits & v_traits = value_traits());
  2. template<typename Iterator> 
      unordered_multiset(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());
  3. unordered_multiset(unordered_multiset && x);

    Effects: to-do

  4. unordered_multiset & operator=(unordered_multiset && x);

    Effects: to-do

  5. ~unordered_multiset();

    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.

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

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

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

  9. iterator end() noexcept;

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

    Complexity: Constant.

    Throws: Nothing.

  10. const_iterator end() const noexcept;

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

    Complexity: Constant.

    Throws: Nothing.

  11. const_iterator cend() const noexcept;

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

    Complexity: Constant.

    Throws: Nothing.

  12. hasher hash_function() const;

    Effects: Returns the hasher object used by the unordered_set.

    Complexity: Constant.

    Throws: If hasher copy-constructor throws.

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

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

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

  16. void swap(unordered_multiset & 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.

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

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

  19. iterator insert(reference value);
  20. 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_equal(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.

  21. void erase(const_iterator i);
  22. void erase(const_iterator b, const_iterator e) noexcept;
  23. size_type erase(const key_type & key);
  24. 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.

  25. template<typename Disposer> 
      void erase_and_dispose(const_iterator i, Disposer disposer) noexcept;
  26. template<typename Disposer> 
      void erase_and_dispose(const_iterator b, const_iterator e, 
                             Disposer disposer) noexcept;
  27. template<typename Disposer> 
      size_type erase_and_dispose(const key_type & key, Disposer disposer);
  28. 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.

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

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

  31. size_type count(const key_type & key) const;
  32. 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.

  33. iterator find(const key_type & key);
  34. 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.

  35. const_iterator find(const key_type & key) const;
  36. 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.

  37. std::pair< iterator, iterator > equal_range(const key_type & key);
  38. 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.

  39. std::pair< const_iterator, const_iterator > 
    equal_range(const key_type & key) const;
  40. 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.

  41. iterator iterator_to(reference value) noexcept;
  42. const_iterator iterator_to(const_reference value) const noexcept;
  43. local_iterator local_iterator_to(reference value) noexcept;
  44. const_local_iterator local_iterator_to(const_reference value) const noexcept;
  45. 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.

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

  47. size_type bucket(const key_type & k) const;
  48. 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()).

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

  50. local_iterator begin(size_type n) noexcept;
  51. const_local_iterator begin(size_type n) const noexcept;
  52. const_local_iterator cbegin(size_type n) const noexcept;
  53. local_iterator end(size_type n) noexcept;
  54. const_local_iterator end(size_type n) const noexcept;
  55. const_local_iterator cend(size_type n) const noexcept;
  56. void rehash(const bucket_traits & new_bucket_traits);
  57. 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.

  58. bool incremental_rehash(bool grow = true);

    Requires:

    Effects:

    Complexity:

    Throws:

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

  59. bool incremental_rehash(const bucket_traits & new_bucket_traits);
  60. size_type split_count() const noexcept;

    Requires: incremental<> option must be set

    Effects: returns the current split count

    Complexity: Constant

    Throws: Nothing

unordered_multiset public static functions

  1. static local_iterator s_local_iterator_to(reference value) noexcept;
  2. static const_local_iterator 
    s_local_iterator_to(const_reference value) noexcept;
  3. 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.

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


PrevUpHomeNext