23 Containers library [containers]

23.3 Sequence containers [sequences]

23.3.9 Class template hive [hive]

23.3.9.1 Overview [hive.overview]

A hive is a type of sequence container that provides constant-time insertion and erasure operations.

Storage is automatically managed in multiple memory blocks, referred to as element blocks.

Insertion position is determined by the container, and insertion may re-use the memory locations of erased elements.

Element blocks which contain elements are referred to as active blocks, those which do not are referred to as reserved blocks.

Active blocks which become empty of elements are either deallocated or become reserved blocks.

Reserved blocks become active blocks when they are used to store elements.

A user can create additional reserved blocks by calling reserve.

Erasures use unspecified techniques of constant time complexity to identify the memory locations of erased elements, which are subsequently skipped during iteration, as opposed to relocating subsequent elements during erasure.

Active block capacities have an implementation-defined growth factor (which need not be integral), for example a new active block's capacity could be equal to the summed capacities of the pre-existing active blocks.

Limits can be placed on both the minimum and maximum element capacities of element blocks, both by users and implementations.

(5.1)
The minimum limit shall be no larger than the maximum limit.
(5.2)
When limits are not specified by a user during construction, the implementation's default limits are used.
(5.3)
The default limits of an implementation are not guaranteed to be the same as the minimum and maximum possible capacities for an implementation's element blocks.

[Note 1:
To allow latitude for both implementation-specific and user-directed optimization.
— end note]

The latter are defined as hard limits.

The maximum hard limit shall be no larger than std::allocator_traits<Allocator>::max_size().
(5.4)
If user-specified limits are not within hard limits, or if the specified minimum limit is greater than the specified maximum limit, the behavior is undefined.
(5.5)
An element block is said to be within the bounds of a pair of minimum/maximum limits when its capacity is greater-or-equal-to the minimum limit and less-than-or-equal-to the maximum limit.

A hive conforms to the requirements for containers ([container.reqmts]), with the exception of operators == and !=.

A hive also meets the requirements of a reversible container ([container.rev.reqmts]), of an allocator-aware container ([container.alloc.reqmts]), and some of the requirements of a sequence container ([sequence.reqmts]).

Descriptions are provided here only for operations on hive that are not described in that table or for operations where there is additional semantic information.

The iterators of hive meet the Cpp17BidirectionalIterator requirements but also model three_way_comparable<strong_ordering>.

namespace std { template<class T, class Allocator = allocator<T>> class hive { public: // types using value_type = T; using allocator_type = Allocator; using pointer = typename allocator_traits<Allocator>::pointer; using const_pointer = typename allocator_traits<Allocator>::const_pointer; using reference = value_type&; using const_reference = const value_type&; using size_type = implementation-defined; // see [container.requirements] using difference_type = implementation-defined; // see [container.requirements] using iterator = implementation-defined; // see [container.requirements] using const_iterator = implementation-defined; // see [container.requirements] using reverse_iterator = std::reverse_iterator<iterator>; // see [container.requirements] using const_reverse_iterator = std::reverse_iterator<const_iterator>; // see [container.requirements] // [hive.cons], construct/copy/destroy constexpr hive() noexcept(noexcept(Allocator())) : hive(Allocator()) {} constexpr explicit hive(const Allocator&) noexcept; constexpr explicit hive(hive_limits block_limits) : hive(block_limits, Allocator()) {} constexpr hive(hive_limits block_limits, const Allocator&); explicit hive(size_type n, const Allocator& = Allocator()); hive(size_type n, hive_limits block_limits, const Allocator& = Allocator()); hive(size_type n, const T& value, const Allocator& = Allocator()); hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator()); template<class InputIterator> hive(InputIterator first, InputIterator last, const Allocator& = Allocator()); template<class InputIterator> hive(InputIterator first, InputIterator last, hive_limits block_limits, const Allocator& = Allocator()); template<container-compatible-range<T> R> hive(from_range_t, R&& rg, const Allocator& = Allocator()); template<container-compatible-range<T> R> hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator()); hive(const hive& x); hive(hive&&) noexcept; hive(const hive& x, const type_identity_t<Allocator>& alloc); hive(hive&&, const type_identity_t<Allocator>& alloc); hive(initializer_list<T> il, const Allocator& = Allocator()); hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator()); ~hive(); hive& operator=(const hive& x); hive& operator=(hive&& x) noexcept(see below); hive& operator=(initializer_list<T>); template<class InputIterator> void assign(InputIterator first, InputIterator last); template<container-compatible-range<T> R> void assign_range(R&& rg); void assign(size_type n, const T& t); void assign(initializer_list<T>); allocator_type get_allocator() const noexcept; // iterators 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; // [hive.capacity], capacity bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; size_type capacity() const noexcept; void reserve(size_type n); void shrink_to_fit(); void trim_capacity() noexcept; void trim_capacity(size_type n) noexcept; constexpr hive_limits block_capacity_limits() const noexcept; static constexpr hive_limits block_capacity_default_limits() noexcept; static constexpr hive_limits block_capacity_hard_limits() noexcept; void reshape(hive_limits block_limits); // [hive.modifiers], modifiers template<class... Args> iterator emplace(Args&&... args); template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args); iterator insert(const T& x); iterator insert(T&& x); iterator insert(const_iterator hint, const T& x); iterator insert(const_iterator hint, T&& x); void insert(initializer_list<T> il); template<container-compatible-range<T> R> void insert_range(R&& rg); template<class InputIterator> void insert(InputIterator first, InputIterator last); void insert(size_type n, const T& x); iterator erase(const_iterator position); iterator erase(const_iterator first, const_iterator last); void swap(hive&) noexcept(see below); void clear() noexcept; // [hive.operations], hive operations void splice(hive& x); void splice(hive&& x); template<class BinaryPredicate = equal_to<T>> size_type unique(BinaryPredicate binary_pred = BinaryPredicate()); template<class Compare = less<T>> void sort(Compare comp = Compare()); iterator get_iterator(const_pointer p) noexcept; const_iterator get_iterator(const_pointer p) const noexcept; private: hive_limits current-limits = implementation-defined; // exposition only }; template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>> hive(InputIterator, InputIterator, Allocator = Allocator()) -> hive<iter-value-type<InputIterator>, Allocator>; template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>> hive(InputIterator, InputIterator, hive_limits, Allocator = Allocator()) -> hive<iter-value-type<InputIterator>, Allocator>; template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> hive(from_range_t, R&&, Allocator = Allocator()) -> hive<ranges::range_value_t<R>, Allocator>; template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> hive(from_range_t, R&&, hive_limits, Allocator = Allocator()) -> hive<ranges::range_value_t<R>, Allocator>; }

23.3.9.2 Constructors, copy, and assignment [hive.cons]

🔗

constexpr explicit hive(const Allocator&) noexcept;

Effects: Constructs an empty hive, using the specified allocator.

Complexity: Constant.

🔗

constexpr hive(hive_limits block_limits, const Allocator&);

Effects: Constructs an empty hive, using the specified allocator.

Initializes current-limits with block_limits.

Complexity: Constant.

🔗

explicit hive(size_type n, const Allocator& = Allocator());
hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());

Preconditions: T is Cpp17DefaultInsertable into hive.

Effects: Constructs a hive with n default-inserted elements, using the specified allocator.

If the second overload is called, also initializes current-limits with block_limits.

Complexity: Linear in n.

🔗

hive(size_type n, const T& value, const Allocator& = Allocator());
hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());

Preconditions: T is Cpp17CopyInsertable into hive.

Effects: Constructs a hive with n copies of value, using the specified allocator.

If the second overload is called, also initializes current-limits with block_limits.

Complexity: Linear in n.

🔗

template<class InputIterator>
  hive(InputIterator first, InputIterator last, const Allocator& = Allocator());
template<class InputIterator>
  hive(InputIterator first, InputIterator last, hive_limits block_limits,
       const Allocator& = Allocator());

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

If the second overload is called, also initializes current-limits with block_limits.

Complexity: Linear in distance(first, last).

🔗

template<container-compatible-range<T> R>
  hive(from_range_t, R&& rg, const Allocator& = Allocator());
template<container-compatible-range<T> R>
  hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());

Effects: Constructs a hive object with the elements of the range rg, using the specified allocator.

If the second overload is called, also initializes current-limits with block_limits.

Complexity: Linear in ranges::distance(rg).

🔗

hive(const hive& x);
hive(const hive& x, const type_identity_t<Allocator>& alloc);

Preconditions: T is Cpp17CopyInsertable into hive.

Effects: Constructs a hive object with the elements of x.

If the second overload is called, uses alloc.

Initializes current-limits with x.current-limits.

Complexity: Linear in x.size().

🔗

hive(hive&& x);
hive(hive&& x, const type_identity_t<Allocator>& alloc);

Preconditions: For the second overload, when allocator_traits<alloc>::is_always_equal::value is false, T meets the Cpp17MoveInsertable requirements.

Effects: When the first overload is called, or the second overload is called and alloc == x.get_allocator() is true, current-limits is set to x.current-limits and each element block is moved from x into *this.

Pointers and references to the elements of x now refer to those same elements but as members of *this.

Iterators referring to the elements of x will continue to refer to their elements, but they now behave as iterators into *this.

If the second overload is called and alloc == x.get_allocator() is false, each element in x is moved into *this.

References, pointers and iterators referring to the elements of x, as well as the past-the-end iterator of x, are invalidated.

Postconditions: x.empty() is true.

Complexity: If the second overload is called and alloc == x.get_allocator() is false, linear in x.size().

Otherwise constant.

🔗

hive(initializer_list<T> il, const Allocator& = Allocator());
hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());

Preconditions: T is Cpp17CopyInsertable into hive.

Effects: Constructs a hive object with the elements of il, using the specified allocator.

If the second overload is called, also initializes current-limits with block_limits.

Complexity: Linear in il.size().

🔗

hive& operator=(const hive& x);

Preconditions: T is Cpp17CopyInsertable into hive and Cpp17CopyAssignable.

Effects: All elements in *this are either copy-assigned to, or destroyed.

All elements in x are copied into *this.

[Note 1:

current-limits is unchanged.

— end note]

Complexity: Linear in size() + x.size().

🔗

hive& operator=(hive&& x)
  noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
           allocator_traits<Allocator>::is_always_equal::value);

Preconditions: When (allocator_traits<Allocator>::propagate_on_container_move_assignment::value || allocator_traits<Allocator>::is_always_equal::value) is false, T is Cpp17MoveInsertable into hive and Cpp17MoveAssignable.

Effects: Each element in *this is either move-assigned to, or destroyed.

When (allocator_traits<Allocator>::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is true, current-limits is set to x.current-limits and each element block is moved from x into *this.

Pointers and references to the elements of x now refer to those same elements but as members of *this.

Iterators referring to the elements of x will continue to refer to their elements, but they now behave as iterators into *this, not into x.

When (allocator_traits<Allocator>::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is false, each element in x is moved into *this.

References, pointers and iterators referring to the elements of x, as well as the past-the-end iterator of x, are invalidated.

Postconditions: x.empty() is true.

Complexity: Linear in size().

If (allocator_traits<Allocator>::propagate_on_container_move_assignment::value || get_allocator() == x.get_allocator()) is false, also linear in x.size().

23.3.9.3 Capacity [hive.capacity]

🔗

size_type capacity() const noexcept;

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() is true, there are no effects.

Otherwise increases capacity() by allocating reserved blocks.

Postconditions: capacity() >= n is true.

Throws: length_error if n > max_size(), as well as any exceptions thrown by the allocator.

Complexity: It does not change the size of the sequence and takes at most linear time in the number of reserved blocks allocated.

Remarks: All references, pointers, and iterators referring to elements in *this, as well as the past-the-end iterator, remain valid.

🔗

void shrink_to_fit();

Preconditions: T is Cpp17MoveInsertable into hive.

Effects: shrink_to_fit is a non-binding request to reduce capacity() to be closer to size().

[Note 1:

The request is non-binding to allow latitude for implementation-specific optimizations.

— end note]

It does not increase capacity(), but may reduce capacity().

It may reallocate elements.

If capacity() is already equal to size(), there are no effects.

If an exception is thrown during allocation of a new element block, capacity() may be reduced and reallocation may occur.

Otherwise if an exception is thrown, the effects are unspecified.

Complexity: If reallocation happens, linear in the size of the sequence.

Remarks: If reallocation happens, the order of the elements in *this may change and all references, pointers, and iterators referring to the elements in *this, as well as the past-the-end iterator, are invalidated.

🔗

void trim_capacity() noexcept;
void trim_capacity(size_type n) noexcept;

Effects: For the first overload, all reserved blocks are deallocated, and capacity() is reduced accordingly.

For the second overload, capacity() is reduced to no less than n.

Complexity: Linear in the number of reserved blocks deallocated.

Remarks: All references, pointers, and iterators referring to elements in *this, as well as the past-the-end iterator, remain valid.

🔗

constexpr hive_limits block_capacity_limits() const noexcept;

Returns: current-limits.

Complexity: Constant.

🔗

static constexpr hive_limits block_capacity_default_limits() noexcept;

Returns: A hive_limits struct with the min and max members set to the implementation's default limits.

Complexity: Constant.

🔗

static constexpr hive_limits block_capacity_hard_limits() noexcept;

Returns: A hive_limits struct with the min and max members set to the implementation's hard limits.

Complexity: Constant.

🔗

void reshape(hive_limits block_limits);

Preconditions: T is Cpp17MoveInsertable into hive.

Effects: For any active blocks not within the bounds of block_limits, the elements within those active blocks are reallocated to new or existing element blocks which are within the bounds.

Any element blocks not within the bounds of block_limits are deallocated.

If an exception is thrown during allocation of a new element block, capacity() may be reduced, reallocation may occur, and current-limits may be assigned a value other than block_limits.

Otherwise block_limits is assigned to current-limits.

If any other exception is thrown the effects are unspecified.

Postconditions: size() is unchanged.

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

If reallocation happens, also linear in the number of elements reallocated.

Remarks: This operation may change capacity().

If reallocation happens, the order of the elements in *this may change.

Reallocation invalidates all references, pointers, and iterators referring to the elements in *this, as well as the past-the-end iterator.

[Note 2:

If no reallocation happens, they remain valid.

— end note]

23.3.9.4 Modifiers [hive.modifiers]

🔗

template<class... Args> iterator emplace(Args&&... args);
template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args);

Preconditions: T is Cpp17EmplaceConstructible into hive from args.

Effects: Inserts an object of type T constructed with std::forward<Args>(args)....

The hint parameter is ignored.

If an exception is thrown, there are no effects.

[Note 1:

args can directly or indirectly refer to a value in *this.

— end note]

Returns: An iterator that points to the new element.

Complexity: Constant.

Exactly one object of type T is constructed.

Remarks: Invalidates the past-the-end iterator.

🔗

iterator insert(const T& x);
iterator insert(const_iterator hint, const T& x);
iterator insert(T&& x);
iterator insert(const_iterator hint, T&& x);

Effects: Equivalent to: return emplace(std::forward<decltype(x)>(x));

[Note 2:

The hint parameter is ignored.

— end note]

🔗

void insert(initializer_list<T> rg);
template<container-compatible-range<T> R>
  void insert_range(R&& rg);

Preconditions: T is Cpp17EmplaceInsertable into hive from *ranges::begin(rg).

rg and *this do not overlap.

Effects: Inserts copies of elements in rg.

Each iterator in the range rg is dereferenced exactly once.

Complexity: Linear in the number of elements inserted.

Exactly one object of type T is constructed for each element inserted.

Remarks: If an element is inserted, invalidates the past-the-end iterator.

🔗

void insert(size_type n, const T& x);

Preconditions: T is Cpp17CopyInsertable into hive.

Effects: Inserts n copies of x.

Complexity: Linear in n.

Exactly one object of type T is constructed for each element inserted.

Remarks: If an element is inserted, invalidates the past-the-end iterator.

🔗

template<class InputIterator>
  void insert(InputIterator first, InputIterator last);

Effects: Equivalent to insert_range(ranges::subrange(first, last)).

🔗

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

Complexity: Linear in the number of elements erased.

Additionally, if any active blocks become empty of elements as a result of the function call, at worst linear in the number of element blocks.

Remarks: Invalidates references, pointers and iterators referring to the erased elements.

An erase operation that erases the last element in *this also invalidates the past-the-end iterator.

🔗

void swap(hive& x)
  noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
           allocator_traits<Allocator>::is_always_equal::value);

Effects: Exchanges the contents, capacity(), and current-limits of *this with that of x.

Complexity: Constant.

23.3.9.5 Operations [hive.operations]

In this subclause, arguments for a template parameter named Predicate or BinaryPredicate shall meet the corresponding requirements in [algorithms.requirements].

The semantics of i + n and i - n, where i is an iterator into the hive and n is an integer, are the same as those of next(i, n) and prev(i, n), respectively.

For sort, the definitions and requirements in [alg.sorting] apply.

🔗

void splice(hive& x);
void splice(hive&& x);

Preconditions: get_allocator() == x.get_allocator() is true.

Effects: If addressof(x) == this is true, the behavior is erroneous and there are no effects.

Otherwise, inserts the contents of x into *this and x becomes empty.

Pointers and references to the moved elements of x now refer to those same elements but as members of *this.

Iterators referring to the moved elements continue to refer to their elements, but they now behave as iterators into *this, not into x.

Throws: length_error if any of x's active blocks are not within the bounds of current-limits.

Complexity: Linear in the sum of all element blocks in x plus all element blocks in *this.

Remarks: Reserved blocks in x are not transferred into *this.

If addressof(x) == this is false, invalidates the past-the-end iterator for both x and *this.

🔗

template<class BinaryPredicate = equal_to<T>>
  size_type unique(BinaryPredicate binary_pred = BinaryPredicate());

Preconditions: binary_pred is an equivalence relation.

Effects: Erases all but the first element from every consecutive group of equivalent elements.

That is, for a nonempty hive, erases all elements referred to by the iterator i in the range [begin() + 1, end()) for which binary_pred(*i, *(i - 1)) is true.

Returns: The number of elements erased.

Throws: Nothing unless an exception is thrown by the predicate.

Complexity: If empty() is false, exactly size() - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

Remarks: Invalidates references, pointers, and iterators referring to the erased elements.

If the last element in *this is erased, also invalidates the past-the-end iterator.

🔗

template<class Compare = less<T>>
  void sort(Compare comp = Compare());

Preconditions: T is Cpp17MoveInsertable into hive, Cpp17MoveAssignable, and Cpp17Swappable.

Effects: Sorts *this according to the comp function object.

If an exception is thrown, the order of the elements in *this is unspecified.

Complexity:

O (N log N)

comparisons, where N is size().

Remarks: May allocate.

References, pointers, and iterators referring to elements in *this, as well as the past-the-end iterator, may be invalidated.

[Note 1:

Not required to be stable[algorithm.stable].

— end note]

🔗

iterator get_iterator(const_pointer p) noexcept;
const_iterator get_iterator(const_pointer p) const noexcept;

Preconditions: p points to an element in *this.

Returns: An iterator or const_iterator pointing to the same element as p.

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

23.3.9.6 Erasure [hive.erasure]

🔗

template<class T, class Allocator, class U>
  typename hive<T, Allocator>::size_type
    erase(hive<T, Allocator>& c, const U& value);

Effects: Equivalent to: return erase_if(c, [&](auto& elem) { return elem == value; });

🔗

template<class T, class Allocator, class Predicate>
  typename hive<T, Allocator>::size_type
    erase_if(hive<T, Allocator>& c, Predicate pred);

Effects: Equivalent to: auto original_size = c.size(); for (auto i = c.begin(), last = c.end(); i != last; ) { if (pred(*i)) { i = c.erase(i); } else { ++i; } } return original_size - c.size();