From Jason Turner

[hive.overview]

C++23 → Trunk 9.5 KB 197 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpjsdk1em4/{from.md → to.md} +194 -0
tmp/tmpjsdk1em4/{from.md → to.md} RENAMED
@@ -0,0 +1,194 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ #### Overview <a id="hive.overview">[[hive.overview]]</a>
2
+
3
+ A `hive` is a type of sequence container that provides constant-time
4
+ insertion and erasure operations. Storage is automatically managed in
5
+ multiple memory blocks, referred to as *element blocks*. Insertion
6
+ position is determined by the container, and insertion may re-use the
7
+ memory locations of erased elements.
8
+
9
+ Element blocks which contain elements are referred to as *active
10
+ blocks*, those which do not are referred to as *reserved blocks*. Active
11
+ blocks which become empty of elements are either deallocated or become
12
+ reserved blocks. Reserved blocks become active blocks when they are used
13
+ to store elements. A user can create additional reserved blocks by
14
+ calling `reserve`.
15
+
16
+ Erasures use unspecified techniques of constant time complexity to
17
+ identify the memory locations of erased elements, which are subsequently
18
+ skipped during iteration, as opposed to relocating subsequent elements
19
+ during erasure.
20
+
21
+ Active block capacities have an *implementation-defined* growth factor
22
+ (which need not be integral), for example a new active block’s capacity
23
+ could be equal to the summed capacities of the pre-existing active
24
+ blocks.
25
+
26
+ Limits can be placed on both the minimum and maximum element capacities
27
+ of element blocks, both by users and implementations.
28
+
29
+ - The minimum limit shall be no larger than the maximum limit.
30
+ - When limits are not specified by a user during construction, the
31
+ implementation’s default limits are used.
32
+ - The default limits of an implementation are not guaranteed to be the
33
+ same as the minimum and maximum possible capacities for an
34
+ implementation’s element blocks. \[*Note 1*: To allow latitude for
35
+ both implementation-specific and user-directed
36
+ optimization. — *end note*] The latter are defined as hard limits.
37
+ The maximum hard limit shall be no larger than
38
+ `std::allocator_traits<Allocator>::max_size()`.
39
+ - If user-specified limits are not within hard limits, or if the
40
+ specified minimum limit is greater than the specified maximum limit,
41
+ the behavior is undefined.
42
+ - An element block is said to be *within the bounds* of a pair of
43
+ minimum/maximum limits when its capacity is greater-or-equal-to the
44
+ minimum limit and less-than-or-equal-to the maximum limit.
45
+
46
+ A `hive` conforms to the requirements for containers
47
+ [[container.reqmts]], with the exception of operators `==` and `!=`. A
48
+ `hive` also meets the requirements of a reversible container
49
+ [[container.rev.reqmts]], of an allocator-aware container
50
+ [[container.alloc.reqmts]], and some of the requirements of a sequence
51
+ container [[sequence.reqmts]]. Descriptions are provided here only for
52
+ operations on `hive` that are not described in that table or for
53
+ operations where there is additional semantic information.
54
+
55
+ The iterators of `hive` meet the *Cpp17BidirectionalIterator*
56
+ requirements but also model `three_way_comparable<strong_ordering>`.
57
+
58
+ ``` cpp
59
+ namespace std {
60
+ template<class T, class Allocator = allocator<T>>
61
+ class hive {
62
+ public:
63
+ // types
64
+ using value_type = T;
65
+ using allocator_type = Allocator;
66
+ using pointer = allocator_traits<Allocator>::pointer;
67
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
68
+ using reference = value_type&;
69
+ using const_reference = const value_type&;
70
+ using size_type = implementation-defined; // see [container.requirements]
71
+ using difference_type = implementation-defined; // see [container.requirements]
72
+ using iterator = implementation-defined; // see [container.requirements]
73
+ using const_iterator = implementation-defined; // see [container.requirements]
74
+ using reverse_iterator = std::reverse_iterator<iterator>; // see [container.requirements]
75
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>; // see [container.requirements]
76
+
77
+ // [hive.cons], construct/copy/destroy
78
+ constexpr hive() noexcept(noexcept(Allocator())) : hive(Allocator()) {}
79
+ constexpr explicit hive(const Allocator&) noexcept;
80
+ constexpr explicit hive(hive_limits block_limits) : hive(block_limits, Allocator()) {}
81
+ constexpr hive(hive_limits block_limits, const Allocator&);
82
+ explicit hive(size_type n, const Allocator& = Allocator());
83
+ hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());
84
+ hive(size_type n, const T& value, const Allocator& = Allocator());
85
+ hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());
86
+ template<class InputIterator>
87
+ hive(InputIterator first, InputIterator last, const Allocator& = Allocator());
88
+ template<class InputIterator>
89
+ hive(InputIterator first, InputIterator last, hive_limits block_limits,
90
+ const Allocator& = Allocator());
91
+ template<container-compatible-range<T> R>
92
+ hive(from_range_t, R&& rg, const Allocator& = Allocator());
93
+ template<container-compatible-range<T> R>
94
+ hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());
95
+ hive(const hive& x);
96
+ hive(hive&&) noexcept;
97
+ hive(const hive& x, const type_identity_t<Allocator>& alloc);
98
+ hive(hive&&, const type_identity_t<Allocator>& alloc);
99
+ hive(initializer_list<T> il, const Allocator& = Allocator());
100
+ hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());
101
+ ~hive();
102
+
103
+ hive& operator=(const hive& x);
104
+ hive& operator=(hive&& x) noexcept(see below);
105
+ hive& operator=(initializer_list<T>);
106
+ template<class InputIterator>
107
+ void assign(InputIterator first, InputIterator last);
108
+ template<container-compatible-range<T> R>
109
+ void assign_range(R&& rg);
110
+ void assign(size_type n, const T& t);
111
+ void assign(initializer_list<T>);
112
+ allocator_type get_allocator() const noexcept;
113
+
114
+ // iterators
115
+ iterator begin() noexcept;
116
+ const_iterator begin() const noexcept;
117
+ iterator end() noexcept;
118
+ const_iterator end() const noexcept;
119
+ reverse_iterator rbegin() noexcept;
120
+ const_reverse_iterator rbegin() const noexcept;
121
+ reverse_iterator rend() noexcept;
122
+ const_reverse_iterator rend() const noexcept;
123
+ const_iterator cbegin() const noexcept;
124
+ const_iterator cend() const noexcept;
125
+ const_reverse_iterator crbegin() const noexcept;
126
+ const_reverse_iterator crend() const noexcept;
127
+
128
+ // [hive.capacity], capacity
129
+ bool empty() const noexcept;
130
+ size_type size() const noexcept;
131
+ size_type max_size() const noexcept;
132
+ size_type capacity() const noexcept;
133
+ void reserve(size_type n);
134
+ void shrink_to_fit();
135
+ void trim_capacity() noexcept;
136
+ void trim_capacity(size_type n) noexcept;
137
+ constexpr hive_limits block_capacity_limits() const noexcept;
138
+ static constexpr hive_limits block_capacity_default_limits() noexcept;
139
+ static constexpr hive_limits block_capacity_hard_limits() noexcept;
140
+ void reshape(hive_limits block_limits);
141
+
142
+ // [hive.modifiers], modifiers
143
+ template<class... Args> iterator emplace(Args&&... args);
144
+ template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args);
145
+ iterator insert(const T& x);
146
+ iterator insert(T&& x);
147
+ iterator insert(const_iterator hint, const T& x);
148
+ iterator insert(const_iterator hint, T&& x);
149
+ void insert(initializer_list<T> il);
150
+ template<container-compatible-range<T> R>
151
+ void insert_range(R&& rg);
152
+ template<class InputIterator>
153
+ void insert(InputIterator first, InputIterator last);
154
+ void insert(size_type n, const T& x);
155
+
156
+ iterator erase(const_iterator position);
157
+ iterator erase(const_iterator first, const_iterator last);
158
+ void swap(hive&) noexcept(see below);
159
+ void clear() noexcept;
160
+
161
+ // [hive.operations], hive operations
162
+ void splice(hive& x);
163
+ void splice(hive&& x);
164
+ template<class BinaryPredicate = equal_to<T>>
165
+ size_type unique(BinaryPredicate binary_pred = BinaryPredicate());
166
+
167
+ template<class Compare = less<T>>
168
+ void sort(Compare comp = Compare());
169
+
170
+ iterator get_iterator(const_pointer p) noexcept;
171
+ const_iterator get_iterator(const_pointer p) const noexcept;
172
+
173
+ private:
174
+ hive_limits current-limits = implementation-defined; // exposition only
175
+ };
176
+
177
+ template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
178
+ hive(InputIterator, InputIterator, Allocator = Allocator())
179
+ -> hive<iter-value-type<InputIterator>, Allocator>;
180
+
181
+ template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
182
+ hive(InputIterator, InputIterator, hive_limits, Allocator = Allocator())
183
+ -> hive<iter-value-type<InputIterator>, Allocator>;
184
+
185
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
186
+ hive(from_range_t, R&&, Allocator = Allocator())
187
+ -> hive<ranges::range_value_t<R>, Allocator>;
188
+
189
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
190
+ hive(from_range_t, R&&, hive_limits, Allocator = Allocator())
191
+ -> hive<ranges::range_value_t<R>, Allocator>;
192
+ }
193
+ ```
194
+