162 lines
12 KiB
Markdown
162 lines
12 KiB
Markdown
[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>;}
|