Class template unordered_bucket

Class template unordered_bucket_manager

boost::intrusive::unordered_bucket_manager

Synopsis

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

template<typename Hashtable, typename Allocator = void> 
class unordered_bucket_manager {
public:
  // types
  typedef Hashtable                     hashtable_type;    
  typedef hashtable_type::bucket_type   bucket_type;       
  typedef hashtable_type::bucket_traits bucket_traits_type;
  typedef hashtable_type::size_type     size_type;         
  typedef implementation_defined        allocator_type;    

  // public member functions
  explicit unordered_bucket_manager(size_type = 0u, 
                                    const allocator_type & = allocator_type());
  unordered_bucket_manager(unordered_bucket_manager &&);
  unordered_bucket_manager & operator=(unordered_bucket_manager &&);
  ~unordered_bucket_manager();
  void swap(unordered_bucket_manager &);
  size_type bucket_count() const noexcept;
  bucket_traits_type traits() const noexcept;
  allocator_type get_allocator() const;
  float max_load_factor() const noexcept;
  void max_load_factor(float);
  float load_factor(const hashtable_type &) const noexcept;
  bool reserve(hashtable_type &, size_type);
  bool reserve_additional(hashtable_type &, size_type = 1u);
  bool rehash(hashtable_type &, size_type);
  bool shrink_to_fit(hashtable_type &);
};

Description

unordered_bucket_manager is a utility that owns and manages the dynamic bucket array required by Boost.Intrusive unordered associative containers (unordered_set, unordered_multiset and hashtable). It implements operations that require modifying the bucket array: increasing the bucket array to maintain the load factor before an insertion, shrink_to_fit, reserve, full-rehashing, etc.

The memory for the bucket array is obtained from an allocator held by the manager.

This class does not allocates the nodes (values) inserted in the container, these are created and managed by the user of the semi-intrusive container.

Template parameters:

Hashtable: the Boost.Intrusive unordered container type (an instantiation of unordered_set, unordered_multiset or hashtable) that must use its default bucket traits, i.e. the bucket_traits option must not be customized.
Allocator: void (the default) means that the bucket array is taken from the global operator new. Any other type is used as the allocator of the bucket array, and it shall be an allocator of buckets: Allocator::value_type shall be Hashtable::bucket_type and Allocator::pointer must be convertible to Hashtable::bucket_ptr.

Usage rules:

One manager manages the buckets of exactly one container. Declare the manager before the container (so that it's constructed first and destroyed last) and construct the container from traits().
Insertions are done on the container. Before each one, call reserve_additional(c, n) (or reserve(c, capacity)) so the load factor invariant is maintained. For a batch of n elements, one reserve_additional(c, n) call grows the array at most once; a call per element grows it step by step.
The manager holds only the operations that need the bucket array or the load factor. Every other operation is done on the container itself: insertions (insert, insert_check/insert_commit), lookups (find, count, equal_range, iteration...) and erasures (erase, erase_and_dispose, clear, clear_and_dispose).
Erasures never touch the bucket array, as in the standard unordered containers: bucket_count() is unchanged (even when the container becomes empty), erasing invalidates only iterators and references to the erased elements, and a single erasure stays O(1) on average. To release buckets, call shrink_to_fit() (or rehash()) explicitly when convenient.
Any operation that reports a rehash (or may perform one) invalidates all iterators into the container. Pointers and references to the elements are never invalidated (nodes are relinked, not moved).
The container must be empty (or already destroyed) when the manager releases a bucket array it still uses, i.e. at manager destruction, move-assignment over it, or swap with an unrelated manager.

Example (values owned by the caller, as usual in Boost.Intrusive):

typedef boost::intrusive::unordered_set<MyType>              Uset;
typedef boost::intrusive::unordered_bucket_manager<Uset>     Manager;

Manager mgr;                    //allocates the initial bucket array
Uset    set(mgr.traits());      //container uses the managed buckets

MyType *p = new MyType(...);
mgr.reserve_additional(set);         //room for one more element
set.insert(*p);                      //insertions: on the container
Uset::iterator it = set.find(key);   //lookups go straight through
set.erase(key);                      //erasures too: no bucket work
mgr.shrink_to_fit(set);              //the only way to lose buckets
set.clear_and_dispose(Deleter());    //leave the buckets empty

`unordered_bucket_manager` public member functions

```
explicit unordered_bucket_manager(size_type bucket_count_hint = 0u, 
                                  const allocator_type & a = allocator_type());
```
Effects: Constructs the manager, allocating an initial bucket array of at least bucket_count_hint buckets (rounded up to a count the container accepts; when zero, the smallest such count is used). A copy of a is stored and used for every bucket allocation.

Throws: If the allocator throws.
```
unordered_bucket_manager(unordered_bucket_manager && x);
```
Effects: Move constructor. Ownership of the bucket array is transferred; the container associated with x (if any) keeps working and becomes associated with *this. The moved-from manager owns no buckets and shall only be destroyed, assigned to or swapped.

Throws: If the allocator's copy constructor throws.
```
unordered_bucket_manager & operator=(unordered_bucket_manager && x);
```
Requires: No container is using the bucket array currently owned by *this (buckets must be empty).

Effects: Destroys the owned array and takes ownership of x's array (see the move constructor).

Throws: If the allocator's copy assignment throws.
```
~unordered_bucket_manager();
```
Requires: No container is using the owned bucket array anymore: the associated container has been destroyed, or cleared (e.g. via clear_and_dispose), before the manager is destroyed.

Effects: Destroys the buckets and deallocates the array.
```
void swap(unordered_bucket_manager & x);
```
Effects: Swaps ownership of the bucket arrays, the allocators, and the maximum load factors. The containers associated with each manager become associated with the other one.

Throws: Nothing (assuming the allocator's swap doesn't throw).
```
size_type bucket_count() const noexcept;
```
Effects: Returns the length of the owned bucket array.

Throws: Nothing.
```
bucket_traits_type traits() const noexcept;
```
Effects: Returns a value-semantics bucket traits object (of the container's own bucket traits type) describing the currently owned array, suitable to construct the associated container.

Throws: Nothing.
```
allocator_type get_allocator() const;
```
Effects: Returns a copy of the stored allocator, converted back to the original Allocator type.
```
float max_load_factor() const noexcept;
```
Effects: Returns the current maximum load factor.
```
void max_load_factor(float mlf);
```
Requires: mlf > 0.0f

Effects: Sets the maximum load factor. Does not rehash: the bucket array is not resized immediately, and the new factor is applied by the next operation that changes the bucket count (reserve(), reserve_additional(), rehash(), shrink_to_fit()).

float load_factor(const hashtable_type & c) const noexcept;

Effects: Returns the current load factor of the container.

```
bool reserve(hashtable_type & c, size_type element_capacity);
```
Requires: c was constructed with this manager's buckets.

Effects: If the owned array is too small to hold element_capacity elements without exceeding the maximum load factor, allocates a bigger array and rehashes c into it (the array is never shrunk). Does nothing when the array is already big enough. Call it before inserting directly into the container: to make room for n more elements, ask for c.size() + n.

Returns: true if a rehash took place (all iterators into c are invalidated; pointers and references remain valid).

Throws: If the allocator throws, or if the container's hasher throws during rehashing (see rehash() notes below).
```
bool reserve_additional(hashtable_type & c, size_type extra_elements = 1u);
```
Requires: c was constructed with this manager's buckets.

Effects: Equivalent to reserve(c, c.size() + extra_elements): if the owned array is too small for extra_elements more elements at the maximum load factor, allocates a bigger array and rehashes c into it. Call it before inserting into the container.

Returns: true if a rehash took place (all iterators into c are invalidated; pointers and references remain valid).

Throws: If the allocator throws, or if the container's hasher throws during rehashing (see rehash() notes below).
```
bool rehash(hashtable_type & c, size_type bucket_count_hint);
```
Effects: Sets the bucket count to the suggested count nearest to max(bucket_count_hint, c.size()/max_load_factor()), growing or shrinking as needed. When that count differs from the current one, allocates a new array and rehashes c into it; otherwise does nothing.

Returns: true if a rehash took place (all iterators into c are invalidated; pointers and references remain valid).

Throws: If the allocator throws, or if the container's hasher throws during rehashing.

Note: If the container's hasher throws while relinking, Boost.Intrusive restores every element into the previous bucket array, this manager deallocates the new (empty) one and the exception is propagated, so the strong guarantee is provided as long as the hasher computes equal values for equal keys.
```
bool shrink_to_fit(hashtable_type & c);
```
Effects: Shrinks the bucket array to the smallest suggested count that respects the maximum load factor for the current size, which allocates that smaller array and rehashes c into it. Erasures never do this implicitly (see the class documentation), so this is the operation to call when releasing buckets is desired.

Returns: true if a rehash took place (all iterators into c are invalidated; pointers and references remain valid).

Throws: If the allocator throws, or if the container's hasher throws during rehashing.