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             : }