Class template hub

boost::container::hub

Synopsis

// In header: <boost/container/hub.hpp>

template<typename T, typename Allocator = void> 
class hub {
public:
  // types
  typedef T                                                       value_type;            
  typedef Allocator                                               allocator_type;        
  typedef typename allocator_traits< Allocator >::pointer         pointer;               
  typedef typename allocator_traits< Allocator >::const_pointer   const_pointer;         
  typedef T &                                                     reference;             
  typedef const T &                                               const_reference;       
  typedef typename allocator_traits< Allocator >::size_type       size_type;             
  typedef typename allocator_traits< Allocator >::difference_type difference_type;       
  typedef unspecified                                             iterator;              
  typedef unspecified                                             const_iterator;        
  typedef std::reverse_iterator< iterator >                       reverse_iterator;      
  typedef std::reverse_iterator< const_iterator >                 const_reverse_iterator;

  // public member functions
  hub();
  explicit hub(const Allocator &) noexcept;
  explicit hub(size_type, const Allocator & = Allocator());
  hub(size_type, const T &, const Allocator & = Allocator());
  template<typename InputIterator, typename = unspecified> 
    hub(InputIterator, InputIterator, const Allocator & = Allocator());
  template<unspecified R> 
    hub(from_range_t, R &&, const Allocator & = Allocator());
  hub(const hub &);
  hub(const hub &, unspecified);
  hub(hub &&) noexcept;
  hub(hub &&, unspecified);
  hub(std::initializer_list< T >, const Allocator & = Allocator());
  ~hub();
  hub & operator=(const hub &);
  hub & operator=(hub &&);
  hub & operator=(std::initializer_list< T >);
  template<typename InputIterator, typename = unspecified> 
    void assign(InputIterator, InputIterator);
  template<unspecified R> void assign_range(R &&);
  void assign(size_type, const T &);
  void assign(std::initializer_list< T >);
  allocator_type get_allocator() const noexcept;
  iterator begin() noexcept;
  const_iterator begin() const noexcept;
  iterator end() noexcept;
  const_iterator end() const noexcept;
  reverse_iterator rbegin() noexcept;
  const_reverse_iterator rbegin() const noexcept;
  reverse_iterator rend() noexcept;
  const_reverse_iterator rend() const noexcept;
  const_iterator cbegin() const noexcept;
  const_iterator cend() const noexcept;
  const_reverse_iterator crbegin() const noexcept;
  const_reverse_iterator crend() const noexcept;
  bool empty() const noexcept;
  size_type size() const noexcept;
  size_type max_size() const noexcept;
  size_type capacity() const noexcept;
  void reserve(size_type);
  void shrink_to_fit();
  void trim_capacity() noexcept;
  void trim_capacity(size_type) noexcept;
  template<typename... Args> iterator emplace(Args &&...);
  template<typename... Args> iterator emplace_hint(const_iterator, Args &&...);
  iterator insert(const T &);
  iterator insert(const_iterator, const T &);
  iterator insert(T &&);
  iterator insert(const_iterator, T &&);
  void insert(std::initializer_list< T >);
  template<unspecified R> void insert_range(R &&);
  template<typename InputIterator, typename = unspecified> 
    void insert(InputIterator, InputIterator);
  void insert(size_type, const T &);
  iterator erase(const_iterator);
  void erase_void(const_iterator);
  iterator erase(const_iterator, const_iterator);
  void swap(hub &);
  void clear() noexcept;
  void splice(hub &);
  void splice(hub &&);
  template<typename BinaryPredicate = std::equal_to<T> > 
    size_type unique(BinaryPredicate = BinaryPredicate());
  template<typename Compare = std::less<T> > void sort(Compare = Compare());
  iterator get_iterator(const_pointer);
  const_iterator get_iterator(const_pointer) const;
};

Description

A hub is a container with constant-time insertion and erasure and element stability: pointers and iterators to an element remain valid until the element is erased. It is a nearly drop-in, more compact alternative to the C++26 std::hive.

Elements are stored in blocks of contiguous memory, each with a fixed capacity of 64 elements. The insertion position is chosen by the container, which may reuse the memory of previously erased elements. A block with at least one element is called active; an empty block kept internally for future reuse is called reserved. Reserved blocks are not used until all active blocks are full, and are only deallocated by shrink_to_fit, trim_capacity or on container destruction. New blocks are allocated only when every block is full or when the user issues a reserve operation.

hub<T, Allocator> is a model of Container, ReversibleContainer, AllocatorAwareContainer and SequenceContainer, with the following exceptions: operators == and != are not provided, and positional insertion of the form insert(position,\ ...) or emplace(position,\ ...) is not provided or ignores the position argument. Its iterators model LegacyBidirectionalIterator.

Exception safety: Except when explicitly noted, all non-const member functions (and free functions taking hub by non-const reference) provide the basic exception guarantee, whereas all const member functions (and free functions taking hub by const reference) provide the strong guarantee.

Template Parameters

```
typename T
```
The cv-unqualified object type of the elements stored in the hub.
```
typename Allocator = void
```
An allocator whose value type is T. If void (the default), boost::container::new_allocator<T> is used.

`hub` public member functions

```
hub();
```
Effects: Constructs an empty hub, using Allocator() as the allocator.

Requires: Allocator is DefaultConstructible.

Complexity: Constant.
```
explicit hub(const Allocator & al_) noexcept;
```
Effects: Constructs an empty hub, using the specified allocator.

Complexity: Constant.
```
explicit hub(size_type n, const Allocator & al_ = Allocator());
```
Effects: Constructs a hub with n default-inserted elements, using the specified allocator.

Requires: T is DefaultInsertable into the hub.

Complexity: Linear in n.
```
hub(size_type n, const T & x, const Allocator & al_ = Allocator());
```
Effects: Constructs a hub with n copies of value, using the specified allocator.

Requires: T is CopyInsertable into the hub.

Complexity: Linear in n.

template<typename InputIterator, typename = unspecified> 
  hub(InputIterator first, InputIterator last, 
      const Allocator & al_ = Allocator());

Effects: Constructs a hub equal to the range [first, last), using the specified allocator.

Complexity: Linear in std::distance(first, last).

```
template<unspecified R> 
  hub(from_range_t, R && rg, const Allocator & al_ = Allocator());
```
Effects: Constructs a hub equal to the range rg, using the specified allocator.

Complexity: Linear in std::ranges::distance(rg).
```
hub(const hub & x);
```
Effects: Constructs a hub equal to x. The second overload uses the given allocator.

Requires: T is CopyInsertable into the hub.

Complexity: Linear in x.size().
```
hub(const hub & x, unspecified al_);
```
Effects: Constructs a hub equal to x, using the given allocator.

Requires: T is CopyInsertable into the hub.

Complexity: Linear in x.size().
```
hub(hub && x) noexcept;
```
Effects: Move constructor. Element blocks are moved from x into *this; pointers, references and iterators to elements of x remain valid but now refer to *this.

Postcondition: x.empty() is true.

Complexity: Constant.
```
hub(hub && x, unspecified al_);
```
Effects: Allocator-extended move constructor. If alloc equals x.get_allocator() the element blocks are moved (iterators/pointers to x remain valid as members of *this); otherwise each element is moved into *this and references, pointers and iterators to x are invalidated.

Requires: T is MoveInsertable when the allocators may be unequal.

Postcondition: x.empty() is true.

Complexity: Constant, or linear in x.size() if elements are moved one by one.
```
hub(std::initializer_list< T > il, const Allocator & al_ = Allocator());
```
Effects: Constructs a hub equal to il, using the specified allocator.

Requires: T is CopyInsertable into the hub.

Complexity: Linear in il.size().
```
~hub();
```
Effects: Destroys all elements and deallocates all blocks.

Complexity: Linear in size() plus the number of blocks.
```
hub & operator=(const hub & x);
```
Effects: Copy assignment. Existing elements are copy-assigned or destroyed and the elements of x are copied into *this, keeping their relative order.

Requires: T is CopyInsertable into the hub and CopyAssignable.

Complexity: Linear in size() + x.size().
```
hub & operator=(hub && x);
```
Effects: Move assignment. Existing elements are move-assigned or destroyed. If the allocator propagates on move assignment or both allocators are equal, element blocks are moved from x (iterators/pointers to x remain valid as members of *this); otherwise each element of x is moved into *this and references, pointers and iterators to x are invalidated.

Requires: T is MoveInsertable and MoveAssignable when elements are moved one by one.

Postcondition: x.empty() is true.

Complexity: Linear in size(), plus linear in x.size() when elements are moved one by one.
```
hub & operator=(std::initializer_list< T > il);
```
Effects: Replaces the contents of *this with a copy of il.

Complexity: Linear in size() + il.size().
```
template<typename InputIterator, typename = unspecified> 
  void assign(InputIterator first, InputIterator last);
```
Effects: Replaces the contents of *this with a copy of the range [first, last).

Complexity: Linear in size() + std::distance(first, last).
```
template<unspecified R> void assign_range(R && rg);
```
Effects: Replaces the contents of *this with a copy of the elements in the range rg.

Complexity: Linear in size() + std::ranges::distance(rg).
```
void assign(size_type n, const T & x);
```
Effects: Replaces the contents of *this with n copies of x.

Complexity: Linear in size() + n.
```
void assign(std::initializer_list< T > il);
```
Effects: Replaces the contents of *this with a copy of il.

Complexity: Linear in size() + il.size().
```
allocator_type get_allocator() const noexcept;
```
Effects: Returns a copy of the allocator associated with *this.

Complexity: Constant.
```
iterator begin() noexcept;
```
Effects: Returns an iterator to the first element, or end() if empty. The const overloads return a const_iterator. Complexity: Constant.
```
const_iterator begin() const noexcept;
```
```
iterator end() noexcept;
```
Effects: Returns the past-the-end iterator. The end iterator is stable: it is not invalidated by insertion or erasure. The const overloads return a const_iterator. Complexity: Constant.
```
const_iterator end() const noexcept;
```
```
reverse_iterator rbegin() noexcept;
```
Effects: Reverse and const iterator accessors, with the usual semantics. Complexity: Constant.

const_reverse_iterator rbegin() const noexcept;

```
reverse_iterator rend() noexcept;
```

const_reverse_iterator rend() const noexcept;

```
const_iterator cbegin() const noexcept;
```
```
const_iterator cend() const noexcept;
```

const_reverse_iterator crbegin() const noexcept;

const_reverse_iterator crend() const noexcept;

```
bool empty() const noexcept;
```
Effects: Returns true if the hub contains no elements.

Complexity: Constant.
```
size_type size() const noexcept;
```
Effects: Returns the number of elements in the hub.

Complexity: Constant.
```
size_type max_size() const noexcept;
```
Effects: Returns the largest possible size of the hub.

Complexity: Constant.
```
size_type capacity() const noexcept;
```
Effects: Returns the total number of elements that *this can hold without requiring allocation of more element blocks.

Complexity: Constant.
```
void reserve(size_type n);
```
Effects: If n <= capacity() there are no effects; otherwise increases capacity() by allocating reserved blocks.

Postcondition: capacity() >= n.

Throws: if n > max_size(), plus any exception thrown by the allocator.

Complexity: Linear in the number of reserved blocks allocated.

Note: All references, pointers and iterators (including the past-the-end iterator) remain valid.
```
void shrink_to_fit();
```
Effects: Reallocates elements if needed so that the number of active blocks is minimized and deallocates the ensuing reserved blocks. If capacity() already equals size() there are no effects. If T throws during reallocation, the effects are unspecified.

Requires: T is MoveInsertable into the hub.

Complexity: Linear in size() if reallocation happens, plus linear in the number of reserved blocks.

Note: If reallocation happens, the order of the elements may change and all references, pointers and iterators to elements are invalidated.
```
void trim_capacity() noexcept;
```
Effects: Deallocates all reserved blocks, reducing capacity() accordingly.

Complexity: Linear in the number of reserved blocks deallocated.

Note: All references, pointers and iterators (including the past-the-end iterator) remain valid.
```
void trim_capacity(size_type n) noexcept;
```
Effects: If n >= capacity() there are no effects; otherwise reduces capacity() to no less than n by deallocating reserved blocks.

Complexity: Linear in the number of reserved blocks deallocated.

Note: All references, pointers and iterators (including the past-the-end iterator) remain valid.
```
template<typename... Args> iterator emplace(Args &&... args);
```
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... at a position chosen by the container. If an exception is thrown there are no effects. args may directly or indirectly refer to a value in *this.

Requires: T is EmplaceConstructible into the hub from args.

Returns: An iterator pointing to the new element.

Complexity: Constant. Exactly one object of type T is constructed.
```
template<typename... Args> 
  iterator emplace_hint(const_iterator, Args &&... args);
```
Effects: Equivalent to emplace(std::forward<Args>(args)...); the hint is ignored.

Returns: An iterator pointing to the new element.

Complexity: Constant.
```
iterator insert(const T & x);
```
Effects: Inserts a copy of x (or moves x) at a position chosen by the container; overloads taking a hint ignore it. Equivalent to emplace(std::forward<decltype(x)>(x)).

Returns: An iterator pointing to the new element.

Complexity: Constant.

iterator insert(const_iterator, const T & x);

```
iterator insert(T && x);
```

iterator insert(const_iterator, T && x);

```
void insert(std::initializer_list< T > il);
```
Effects: Inserts copies of the elements in il. Equivalent to insert(il.begin(), il.end()).

Complexity: Linear in il.size().
```
template<unspecified R> void insert_range(R && rg);
```
Effects: Inserts copies of the elements in rg. Each iterator in rg is dereferenced exactly once.

Requires: T is EmplaceConstructible into the hub from *ranges::begin(rg) and rg does not overlap *this.

Complexity: Linear in the number of elements inserted; one object of type T is constructed per element.
```
template<typename InputIterator, typename = unspecified> 
  void insert(InputIterator first, InputIterator last);
```
Effects: Inserts copies of the elements in [first, last). Each iterator in the range is dereferenced exactly once.

Requires: T is EmplaceConstructible into the hub from *first and [first, last) does not overlap *this.

Complexity: Linear in the number of elements inserted; one object of type T is constructed per element.
```
void insert(size_type n, const T & x);
```
Effects: Inserts n copies of x.

Requires: T is CopyInsertable into the hub.

Complexity: Linear in n; one object of type T is constructed per element.
```
iterator erase(const_iterator pos);
```
Effects: Erases the element pointed to by pos.

Returns: An iterator pointing to the element that followed the erased one.

Complexity: Constant.

Note: Invalidates references, pointers and iterators referring to the erased element.
```
void erase_void(const_iterator pos);
```
Effects: Erases the element pointed to by pos. Equivalent to erase(pos) but returns nothing.

Complexity: Constant.

Note: Potentially faster than erase(pos) as no return iterator needs to be computed. Invalidates references, pointers and iterators referring to the erased element.
```
iterator erase(const_iterator first, const_iterator last);
```
Effects: Erases the elements in the range [first, last).

Returns: An iterator pointing to the element that followed the last erased element.

Complexity: Linear in the number of elements erased.

Note: Invalidates references, pointers and iterators referring to the erased elements.
```
void swap(hub & x);
```
Effects: Exchanges the contents and capacity() of *this with those of x.

Complexity: Constant.
```
void clear() noexcept;
```
Effects: Erases all elements. Reserved blocks are kept.

Complexity: Linear in size().
```
void splice(hub & x);
```
Effects: Inserts the contents of x into *this, leaving x empty. Pointers and references to the moved elements of x now refer to *this; iterators continue to refer to their elements but behave as iterators into *this. Reserved blocks of x are not transferred.

Requires: get_allocator() == x.get_allocator() and std::addressof(x) != this.

Complexity: Linear in the number of blocks of x plus the number of blocks of *this.
```
void splice(hub && x);
```
Effects: Equivalent to splice(x).
```
template<typename BinaryPredicate = std::equal_to<T> > 
  size_type unique(BinaryPredicate pred = BinaryPredicate());
```
Effects: Erases all but the first element from every consecutive group of equivalent elements, i.e. erases each element i in [begin() + 1, end()) for which pred(*i, *(i - 1)) is true.

Requires: pred is an equivalence relation.

Returns: The number of elements erased.

Throws: Nothing unless pred throws.

Complexity: Exactly size() - 1 applications of pred for a non-empty hub, otherwise none.

Note: Invalidates references, pointers and iterators referring to the erased elements.
```
template<typename Compare = std::less<T> > void sort(Compare comp = Compare());
```
Effects: Sorts *this according to comp. If comp or any operation on T throws, *this is left in a valid but unspecified state; if an exception is thrown while allocating internal memory there are no effects.

Requires: T is MoveInsertable into the hub, MoveConstructible, MoveAssignable and Swappable.

Complexity: O(N*log(N)) comparisons, where N is size().

Note: May allocate. References, pointers and iterators to elements may be invalidated. The sort is not stable.
```
iterator get_iterator(const_pointer p);
```
Effects: Returns an iterator (or const_iterator) referring to the same element as p.

Requires: p points to an element in *this.

Throws: Nothing.

Complexity: Linear in the number of active blocks in *this.

const_iterator get_iterator(const_pointer p) const;