Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <algorithm>
7 : #include <cstddef>
8 : #include <iterator>
9 : #include <pup.h>
10 : #include <type_traits>
11 :
12 : #include "Utilities/PrintHelpers.hpp"
13 : #include "Utilities/Requires.hpp"
14 : #include "Utilities/StlBoilerplate.hpp"
15 :
16 : namespace static_deque_detail {
17 : // "The extent to which an implementation determines that a type
18 : // cannot be an input iterator is unspecified, except that as a
19 : // minimum integral types shall not qualify as input iterators."
20 : // -- N4659 26.2.1.17
21 : template <typename U>
22 : constexpr static bool is_input_iterator = not std::is_integral_v<U>;
23 : } // namespace static_deque_detail
24 :
25 : /// A class implementing the std::deque interface with static storage.
26 : ///
27 : /// Differences from std::deque:
28 : /// * The size of the container cannot be increased above \p Capacity.
29 : /// * Operations moving the entire container are \f$O(n)\f$ instead of
30 : /// \f$O(1)\f$ in the size and invalidate all references and
31 : /// iterators.
32 : /// * Erasing elements from the front of the queue invalidates all
33 : /// iterators (but not references).
34 : ///
35 : /// This last point is not a fundamental limitation, but could be
36 : /// corrected with a more complicated iterator implementation if the
37 : /// standard behavior is found to be useful.
38 : template <typename T, size_t Capacity>
39 1 : class StaticDeque
40 : : public stl_boilerplate::RandomAccessSequence<StaticDeque<T, Capacity>,
41 : T, true> {
42 : public:
43 : // Aliases needed in the class definition. The rest can just be
44 : // inherited.
45 0 : using size_type = typename StaticDeque::size_type;
46 0 : using difference_type = typename StaticDeque::difference_type;
47 0 : using iterator = typename StaticDeque::iterator;
48 0 : using const_iterator = typename StaticDeque::const_iterator;
49 :
50 0 : StaticDeque() = default;
51 0 : explicit StaticDeque(size_type count);
52 0 : StaticDeque(size_type n, const T& value);
53 : template <
54 : typename InputIterator,
55 : Requires<static_deque_detail::is_input_iterator<InputIterator>> = nullptr>
56 0 : StaticDeque(InputIterator first, InputIterator last);
57 0 : StaticDeque(const StaticDeque& other);
58 0 : StaticDeque(StaticDeque&& other);
59 0 : StaticDeque(std::initializer_list<T> init);
60 :
61 0 : ~StaticDeque();
62 :
63 0 : StaticDeque& operator=(const StaticDeque& other);
64 0 : StaticDeque& operator=(StaticDeque&& other);
65 0 : StaticDeque& operator=(std::initializer_list<T> init);
66 :
67 : template <
68 : typename InputIterator,
69 : Requires<static_deque_detail::is_input_iterator<InputIterator>> = nullptr>
70 0 : void assign(InputIterator first, InputIterator last);
71 0 : void assign(size_type count, const T& value);
72 0 : void assign(std::initializer_list<T> init);
73 :
74 0 : size_type size() const { return size_; }
75 0 : size_type max_size() const { return Capacity; }
76 0 : void resize(size_type count);
77 0 : void resize(size_type count, const T& value);
78 0 : void shrink_to_fit() {}
79 :
80 0 : T& operator[](size_type n) { return *entry_address(n); }
81 0 : const T& operator[](size_type n) const { return *entry_address(n); }
82 :
83 : template <typename... Args>
84 0 : T& emplace_front(Args&&... args);
85 : template <typename... Args>
86 0 : T& emplace_back(Args&&... args);
87 : template <typename... Args>
88 0 : iterator emplace(const_iterator position, Args&&... args);
89 :
90 0 : void push_front(const T& x) { emplace_front(x); }
91 0 : void push_front(T&& x) { emplace_front(std::move(x)); }
92 0 : void push_back(const T& x) { emplace_back(x); }
93 0 : void push_back(T&& x) { emplace_back(std::move(x)); }
94 :
95 0 : iterator insert(const_iterator position, const T& x);
96 0 : iterator insert(const_iterator position, T&& x);
97 0 : iterator insert(const_iterator position, size_type n, const T& x);
98 : template <
99 : typename InputIterator,
100 : Requires<static_deque_detail::is_input_iterator<InputIterator>> = nullptr>
101 0 : iterator insert(const_iterator position, InputIterator first,
102 : InputIterator last);
103 0 : iterator insert(const_iterator position, std::initializer_list<T> init);
104 :
105 0 : void pop_front();
106 0 : void pop_back();
107 :
108 0 : iterator erase(const_iterator position);
109 0 : iterator erase(const_iterator first, const_iterator last);
110 :
111 0 : void swap(StaticDeque& other);
112 0 : void clear();
113 :
114 0 : void pup(PUP::er& p);
115 :
116 : private:
117 : // Operations on the middle of the deque are supposed to shift as
118 : // few elements as possible.
119 0 : bool should_operate_on_back(const const_iterator& first,
120 : const const_iterator& last) const {
121 : return (this->end() - last) <= (first - this->begin());
122 : }
123 :
124 : // Index into the internal array of T of logical index n
125 0 : size_type internal_index(size_type n) const {
126 : auto index = start_position_ + n;
127 : if (index >= Capacity) {
128 : index -= Capacity;
129 : }
130 : ASSERT(index < static_cast<difference_type>(Capacity),
131 : "Calculated out-of-range index: " << index);
132 : return index;
133 : }
134 :
135 0 : const T* entry_address(size_type n) const {
136 : return reinterpret_cast<const T*>(data_) + internal_index(n);
137 : }
138 :
139 0 : T* entry_address(size_type n) {
140 : return reinterpret_cast<T*>(data_) + internal_index(n);
141 : }
142 :
143 : // This array contains the memory used to store the elements. It is
144 : // treated as an array of T, except that some elements may be
145 : // missing, i.e., be segments of memory not containing objects.
146 : // Elements are created using placement new and removed by calling
147 : // their destructors.
148 : //
149 : // Logically, the array is considered to be a periodic structure.
150 : // The existing elements are stored contiguously in the logical
151 : // structure, which may correspond to a contiguous portion of the
152 : // actual memory or a segment at the end and a segment at the
153 : // beginning. This segment can grow or shrink at either end,
154 : // allowing insertions and removals at the ends without needing to
155 : // move any other entries.
156 : //
157 : // The start_position_ variable stores the index of the start of the
158 : // portion of the array that is in use, in the range [0, Capacity).
159 : // Care must be taken to keep this value in range when the start of
160 : // the used memory crosses the end of the storage. The size_
161 : // variable stores the number of existing elements, which must be in
162 : // the range [0, Capacity]. (This could not be implemented using a
163 : // "one past the end" index instead of the size, because that index
164 : // is the same for size=0 and size=Capacity.)
165 0 : alignas(T) std::byte data_[sizeof(T) * Capacity];
166 0 : size_type start_position_{0};
167 0 : size_type size_{0};
168 : };
169 :
170 : template <typename T, size_t Capacity>
171 : StaticDeque<T, Capacity>::StaticDeque(const size_type count) {
172 : resize(count);
173 : }
174 :
175 : template <typename T, size_t Capacity>
176 : StaticDeque<T, Capacity>::StaticDeque(const size_type n, const T& value) {
177 : resize(n, value);
178 : }
179 :
180 : template <typename T, size_t Capacity>
181 : template <typename InputIterator,
182 : Requires<static_deque_detail::is_input_iterator<InputIterator>>>
183 : StaticDeque<T, Capacity>::StaticDeque(const InputIterator first,
184 : const InputIterator last) {
185 : assign(first, last);
186 : }
187 :
188 : template <typename T, size_t Capacity>
189 : StaticDeque<T, Capacity>::StaticDeque(const StaticDeque& other)
190 : : StaticDeque(other.begin(), other.end()) {}
191 :
192 : template <typename T, size_t Capacity>
193 : StaticDeque<T, Capacity>::StaticDeque(StaticDeque&& other)
194 : : StaticDeque(std::move_iterator(other.begin()),
195 : std::move_iterator(other.end())) {}
196 :
197 : template <typename T, size_t Capacity>
198 : StaticDeque<T, Capacity>::StaticDeque(const std::initializer_list<T> init)
199 : : StaticDeque(init.begin(), init.end()) {}
200 :
201 : template <typename T, size_t Capacity>
202 : StaticDeque<T, Capacity>::~StaticDeque() {
203 : clear();
204 : }
205 :
206 : template <typename T, size_t Capacity>
207 : auto StaticDeque<T, Capacity>::operator=(const StaticDeque& other)
208 : -> StaticDeque& {
209 : if (size() > other.size()) {
210 : resize(other.size());
211 : }
212 : size_t i = 0;
213 : for (; i < size(); ++i) {
214 : (*this)[i] = other[i];
215 : }
216 : for (; i < other.size(); ++i) {
217 : push_back(other[i]);
218 : }
219 : return *this;
220 : }
221 :
222 : template <typename T, size_t Capacity>
223 : auto StaticDeque<T, Capacity>::operator=(StaticDeque&& other) -> StaticDeque& {
224 : if (size() > other.size()) {
225 : resize(other.size());
226 : }
227 : size_t i = 0;
228 : for (; i < size(); ++i) {
229 : (*this)[i] = std::move(other[i]);
230 : }
231 : for (; i < other.size(); ++i) {
232 : push_back(std::move(other[i]));
233 : }
234 : return *this;
235 : }
236 :
237 : template <typename T, size_t Capacity>
238 : auto StaticDeque<T, Capacity>::operator=(const std::initializer_list<T> init)
239 : -> StaticDeque& {
240 : assign(init);
241 : return *this;
242 : }
243 :
244 : template <typename T, size_t Capacity>
245 : template <typename InputIterator,
246 : Requires<static_deque_detail::is_input_iterator<InputIterator>>>
247 : void StaticDeque<T, Capacity>::assign(InputIterator first,
248 : const InputIterator last) {
249 : // This could be slightly more efficient if this object is not
250 : // already empty by assigning to existing objects.
251 : clear();
252 : while (first != last) {
253 : push_back(*first++);
254 : }
255 : }
256 :
257 : template <typename T, size_t Capacity>
258 : void StaticDeque<T, Capacity>::assign(const size_type count, const T& value) {
259 : ASSERT(count <= max_size(), count << " exceeds max size " << max_size());
260 : // This could be slightly more efficient if this object is not
261 : // already empty by assigning to existing objects.
262 : clear();
263 : resize(count, value);
264 : }
265 :
266 : template <typename T, size_t Capacity>
267 : void StaticDeque<T, Capacity>::assign(const std::initializer_list<T> init) {
268 : assign(init.begin(), init.end());
269 : }
270 :
271 : template <typename T, size_t Capacity>
272 : void StaticDeque<T, Capacity>::resize(const size_type count) {
273 : ASSERT(count <= max_size(), count << " exceeds max size " << max_size());
274 : while (size() > count) {
275 : pop_back();
276 : }
277 : while (size() < count) {
278 : emplace_back();
279 : }
280 : }
281 :
282 : template <typename T, size_t Capacity>
283 : void StaticDeque<T, Capacity>::resize(const size_type count, const T& value) {
284 : ASSERT(count <= max_size(), count << " exceeds max size " << max_size());
285 : while (size() > count) {
286 : pop_back();
287 : }
288 : while (size() < count) {
289 : push_back(value);
290 : }
291 : }
292 :
293 : template <typename T, size_t Capacity>
294 : template <typename... Args>
295 : T& StaticDeque<T, Capacity>::emplace_front(Args&&... args) {
296 : ASSERT(size() < max_size(), "Container is full.");
297 : auto* const new_entry =
298 : new (entry_address(Capacity - 1)) T(std::forward<Args>(args)...);
299 : // This must be done last in case T's constructor throws an
300 : // exception.
301 : if (start_position_ == 0) {
302 : start_position_ = Capacity - 1;
303 : } else {
304 : --start_position_;
305 : }
306 : ++size_;
307 : return *new_entry;
308 : }
309 :
310 : template <typename T, size_t Capacity>
311 : template <typename... Args>
312 : T& StaticDeque<T, Capacity>::emplace_back(Args&&... args) {
313 : ASSERT(size() < max_size(), "Container is full.");
314 : auto* const new_entry =
315 : new (entry_address(size())) T(std::forward<Args>(args)...);
316 : // This must be done last in case T's constructor throws an
317 : // exception.
318 : ++size_;
319 : return *new_entry;
320 : }
321 :
322 : template <typename T, size_t Capacity>
323 : template <typename... Args>
324 0 : auto StaticDeque<T, Capacity>::emplace(const const_iterator position,
325 : Args&&... args) -> iterator {
326 : if (position == this->begin()) {
327 : emplace_front(std::forward<Args>(args)...);
328 : return this->begin();
329 : } else if (position == this->end()) {
330 : emplace_back(std::forward<Args>(args)...);
331 : return this->end() - 1;
332 : }
333 :
334 : const auto element_to_assign = position - this->begin();
335 : if (should_operate_on_back(position, position)) {
336 : emplace_back(std::move(this->back()));
337 : std::move_backward(this->begin() + element_to_assign, this->end() - 2,
338 : this->end() - 1);
339 : } else {
340 : emplace_front(std::move(this->front()));
341 : std::move(this->begin() + 2, this->begin() + element_to_assign + 1,
342 : this->begin() + 1);
343 : }
344 :
345 : const auto new_element = this->begin() + element_to_assign;
346 : // emplace in the middle does not construct in place. STL
347 : // containers also have this behavior.
348 : *new_element = T(std::forward<Args>(args)...);
349 : return new_element;
350 : }
351 :
352 : template <typename T, size_t Capacity>
353 : auto StaticDeque<T, Capacity>::insert(const const_iterator position, const T& x)
354 : -> iterator {
355 : return emplace(position, x);
356 : }
357 :
358 : template <typename T, size_t Capacity>
359 : auto StaticDeque<T, Capacity>::insert(const const_iterator position, T&& x)
360 : -> iterator {
361 : return emplace(position, std::move(x));
362 : }
363 :
364 : template <typename T, size_t Capacity>
365 : auto StaticDeque<T, Capacity>::insert(const const_iterator position,
366 : const size_type n, const T& x)
367 : -> iterator {
368 : // In theory we could insert these in place and save a bunch of
369 : // moves, but keeping track of when elements must be assigned
370 : // vs. constructed would be a pain, and this can't be that common an
371 : // operation.
372 : if (should_operate_on_back(position, position)) {
373 : // We are about to invalidate position.
374 : const auto insert_index = position - this->begin();
375 : const auto old_size = static_cast<difference_type>(size());
376 : for (size_type i = 0; i < n; ++i) {
377 : emplace_back(x);
378 : }
379 : const auto new_position = this->begin() + insert_index;
380 : const auto old_end = this->begin() + old_size;
381 : std::rotate(new_position, old_end, this->end());
382 : return new_position;
383 : } else {
384 : // We are about to invalidate position.
385 : const auto insert_index = position - this->begin();
386 : const auto insert_back_index = this->end() - position;
387 : const auto old_size = static_cast<difference_type>(size());
388 : for (size_type i = 0; i < n; ++i) {
389 : emplace_front(x);
390 : }
391 : const auto new_position = this->begin() + insert_index;
392 : const auto new_position_end = this->end() - insert_back_index;
393 : const auto old_begin = this->end() - old_size;
394 : std::rotate(this->begin(), old_begin, new_position_end);
395 : return new_position;
396 : }
397 : }
398 :
399 : template <typename T, size_t Capacity>
400 : template <typename InputIterator,
401 : Requires<static_deque_detail::is_input_iterator<InputIterator>>>
402 0 : auto StaticDeque<T, Capacity>::insert(const const_iterator position,
403 : InputIterator first,
404 : const InputIterator last) -> iterator {
405 : // The iterators could be single-pass, so we can't clear space and
406 : // then insert the new elements. We also can't do repeated single
407 : // insertions because that's too inefficient. Instead, we have to
408 : // create the new elements at the end and then rotate them into
409 : // place.
410 : if (should_operate_on_back(position, position)) {
411 : // We are about to invalidate position.
412 : const auto insert_index = position - this->begin();
413 : const auto old_size = static_cast<difference_type>(size());
414 : while (first != last) {
415 : emplace_back(*first++);
416 : }
417 : const auto new_position = this->begin() + insert_index;
418 : const auto old_end = this->begin() + old_size;
419 : std::rotate(new_position, old_end, this->end());
420 : return new_position;
421 : } else {
422 : // We are about to invalidate position.
423 : const auto insert_index = position - this->begin();
424 : const auto insert_back_index = this->end() - position;
425 : const auto old_size = static_cast<difference_type>(size());
426 : while (first != last) {
427 : emplace_front(*first++);
428 : }
429 : const auto new_position = this->begin() + insert_index;
430 : const auto new_position_end = this->end() - insert_back_index;
431 : const auto old_begin = this->end() - old_size;
432 : std::reverse(this->begin(), old_begin);
433 : std::rotate(this->begin(), old_begin, new_position_end);
434 : return new_position;
435 : }
436 : }
437 :
438 : template <typename T, size_t Capacity>
439 : auto StaticDeque<T, Capacity>::insert(const const_iterator position,
440 : const std::initializer_list<T> init)
441 : -> iterator {
442 : return insert(position, init.begin(), init.end());
443 : }
444 :
445 : template <typename T, size_t Capacity>
446 : void StaticDeque<T, Capacity>::pop_front() {
447 : ASSERT(not this->empty(), "Container is empty.");
448 : if (start_position_ == Capacity - 1) {
449 : start_position_ = 0;
450 : } else {
451 : ++start_position_;
452 : }
453 : --size_;
454 : // Calling the destructor is sufficient to remove the element.
455 : // There is no special "placement delete".
456 : entry_address(Capacity - 1)->~T();
457 : }
458 :
459 : template <typename T, size_t Capacity>
460 : void StaticDeque<T, Capacity>::pop_back() {
461 : ASSERT(not this->empty(), "Container is empty.");
462 : --size_;
463 : // Calling the destructor is sufficient to remove the element.
464 : // There is no special "placement delete".
465 : entry_address(size())->~T();
466 : }
467 :
468 : template <typename T, size_t Capacity>
469 : auto StaticDeque<T, Capacity>::erase(const const_iterator position)
470 : -> iterator {
471 : return erase(position, position + 1);
472 : }
473 :
474 : template <typename T, size_t Capacity>
475 : auto StaticDeque<T, Capacity>::erase(const const_iterator first,
476 : const const_iterator last) -> iterator {
477 : const auto result_offset = first - this->begin();
478 : auto num_to_remove = last - first;
479 : if (num_to_remove == 0) {
480 : return last - this->begin() + this->begin();
481 : }
482 : if (should_operate_on_back(first, last)) {
483 : std::move(last, this->cend(), first - this->begin() + this->begin());
484 : while (num_to_remove-- != 0) {
485 : pop_back();
486 : }
487 : } else {
488 : std::move_backward(this->cbegin(), first,
489 : last - this->begin() + this->begin());
490 : while (num_to_remove-- != 0) {
491 : pop_front();
492 : }
493 : }
494 : return this->begin() + result_offset;
495 : }
496 :
497 : template <typename T, size_t Capacity>
498 : void StaticDeque<T, Capacity>::swap(StaticDeque& other) {
499 : using std::swap;
500 : swap(*this, other);
501 : }
502 :
503 : template <typename T, size_t Capacity>
504 : void StaticDeque<T, Capacity>::clear() {
505 : while (not this->empty()) {
506 : pop_back();
507 : }
508 : }
509 :
510 : template <typename T, size_t Capacity>
511 : void StaticDeque<T, Capacity>::pup(PUP::er& p) {
512 : // If performance when serializing simple types becomes an issue, we
513 : // can just send the array of bytes and the other member variables,
514 : // which will probably perform better (unless, perhaps, the
515 : // container is nearly empty). That can't be done for types that
516 : // are not trivially copyable, which would still need to use
517 : // something like the current implementation.
518 : size_type sz = size();
519 : p | sz;
520 : resize(sz);
521 : for (auto& entry : *this) {
522 : p | entry;
523 : }
524 : }
525 :
526 : template <typename T, size_t Capacity>
527 0 : void swap(StaticDeque<T, Capacity>& x, StaticDeque<T, Capacity>& y) {
528 : const auto initial_size = x.size();
529 : if (initial_size > y.size()) {
530 : return swap(y, x);
531 : }
532 : for (size_t i = 0; i < initial_size; ++i) {
533 : using std::swap;
534 : swap(x[i], y[i]);
535 : }
536 : const auto to_move =
537 : y.begin() +
538 : static_cast<typename StaticDeque<T, Capacity>::difference_type>(
539 : initial_size);
540 : x.insert(x.end(), std::move_iterator(to_move), std::move_iterator(y.end()));
541 : y.erase(to_move, y.end());
542 : }
543 :
544 : template <typename T, size_t Capacity>
545 0 : std::ostream& operator<<(std::ostream& s,
546 : const StaticDeque<T, Capacity>& deque) {
547 : sequence_print_helper(s, deque.begin(), deque.end());
548 : return s;
549 : }
|
