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