23 Containers library [containers]

23.3 Sequence containers [sequences]

23.3.9 Class template hive [hive]

23.3.9.1 Overview [hive.overview]

1
#
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 ([hive.modifiers]) position is determined by the container, and insertion may re-use the memory locations of erased elements.
[Note 1: 
Construction and assignment are not considered to involve insertion operations.
— end note]
2
#
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.
3
#
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.
4
#
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.
5
#
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 2: 
    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 passed to a hive constructor or reshape are not within hard limits, or if the specified minimum limit is greater than the specified maximum limit, the behavior is erroneous and the effects are implementation-defined.
    [Note 3: 
    This condition can be checked using is_within_hard_limits.
    — end note]
  • (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.
6
#
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.
7
#
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 = allocator_traits<Allocator>::pointer; using const_pointer = 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; static constexpr bool is_within_hard_limits(hive_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>; }