[hive.overview]

# 23 Containers library [[containers]](./#containers)

## 23.3 Sequence containers [[sequences]](sequences#hive.overview)

### 23.3.9 Class template hive [[hive]](hive#overview)

#### 23.3.9.1 Overview [hive.overview]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7915)

A hive is a type of sequence container
that provides constant-time insertion and erasure operations[.](#1.sentence-1)

Storage is automatically managed in multiple memory blocks,
referred to as [*element blocks*](#def:element_block "23.3.9.1 Overview [hive.overview]")[.](#1.sentence-2)

Insertion position is determined by the container, and insertion
may re-use the memory locations of erased elements[.](#1.sentence-3)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7923)

Element blocks which contain elements are referred to
as [*active blocks*](#def:block,active "23.3.9.1 Overview [hive.overview]"),
those which do not are referred to as [*reserved blocks*](#def:block,reserved "23.3.9.1 Overview [hive.overview]")[.](#2.sentence-1)

Active blocks which become empty of elements are
either deallocated or become reserved blocks[.](#2.sentence-2)

Reserved blocks become active blocks when they are used to store elements[.](#2.sentence-3)

A user can create additional reserved blocks by calling reserve[.](#2.sentence-4)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7932)

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[.](#3.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7938)

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[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7945)

Limits can be placed on
both the minimum and maximum element capacities of element blocks,
both by users and implementations[.](#5.sentence-1)

- [(5.1)](#5.1)

  The minimum limit shall be no larger than the maximum limit[.](#5.1.sentence-1)

- [(5.2)](#5.2)

  When limits are not specified by a user during construction,
the implementation's default limits are used[.](#5.2.sentence-1)

- [(5.3)](#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[.](#5.3.sentence-1)
  [*Note [1](#note-1)*:
  To allow latitude for
both implementation-specific and user-directed optimization[.](#5.3.sentence-2)
 — *end note*]
   The latter are defined as hard limits[.](#5.3.sentence-3)
  The maximum hard limit shall be no larger thanstd​::​allocator_traits<Allocator>​::​max_size()[.](#5.3.sentence-4)

- [(5.4)](#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.4.sentence-1)

- [(5.5)](#5.5)

  An element block is said to be [*within the bounds*](#def:element_block,bounds "23.3.9.1 Overview [hive.overview]") 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[.](#5.5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7977)

A hive conforms to
the requirements for containers ([[container.reqmts]](container.reqmts "23.2.2.2 Container requirements")),
with the exception of operators == and !=[.](#6.sentence-1)

A hive also meets the requirements
of a reversible container ([[container.rev.reqmts]](container.rev.reqmts "23.2.2.3 Reversible container requirements")),
of an allocator-aware container ([[container.alloc.reqmts]](container.alloc.reqmts "23.2.2.5 Allocator-aware containers")), and
some of the requirements of a sequence container ([[sequence.reqmts]](sequence.reqmts "23.2.4 Sequence containers"))[.](#6.sentence-2)

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[.](#6.sentence-3)

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L7989)

The iterators of hive meet
the *Cpp17BidirectionalIterator* requirements
but also model [three_way_comparable](cmp.concept#concept:three_way_comparable "17.12.4 Concept three_­way_­comparable [cmp.concept]")<strong_ordering>[.](#7.sentence-1)

namespace std {template<class T, class Allocator = allocator<T>>class [hive](#lib:hive "23.3.9.1 Overview [hive.overview]") {public:// typesusing 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]](container.requirements "23.2 Requirements")using difference_type = *implementation-defined*; // see [[container.requirements]](container.requirements "23.2 Requirements")using iterator = *implementation-defined*; // see [[container.requirements]](container.requirements "23.2 Requirements")using const_iterator = *implementation-defined*; // see [[container.requirements]](container.requirements "23.2 Requirements")using reverse_iterator = std::reverse_iterator<iterator>; // see [[container.requirements]](container.requirements "23.2 Requirements")using const_reverse_iterator = std::reverse_iterator<const_iterator>; // see [[container.requirements]](container.requirements "23.2 Requirements")// [[hive.cons]](hive.cons "23.3.9.2 Constructors, copy, and assignment"), construct/copy/destroyconstexpr 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*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<T> R> hive(from_range_t, R&& rg, const Allocator& = Allocator()); template<[*container-compatible-range*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<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*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<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]](hive.capacity "23.3.9.3 Capacity"), capacitybool 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]](hive.modifiers "23.3.9.4 Modifiers"), modifierstemplate<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*](container.intro.reqmts#concept:container-compatible-range "23.2.2.1 Introduction [container.intro.reqmts]")<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 "23.3.9.5 Operations"), hive operationsvoid 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](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") 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](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") 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>;}