Line data    Source code

       1           0 : // Distributed under the MIT License.
       2             : // See LICENSE.txt for details.
       3             : 
       4             : #pragma once
       5             : 
       6             : #include <cstddef>
       7             : #include <limits>
       8             : 
       9             : #include "DataStructures/StaticDeque.hpp"
      10             : 
      11             : // This class is tested in Test_StaticDeque.cpp
      12             : 
      13             : /// A class implementing the std::deque interface using a circular
      14             : /// buffer to avoid allocations when the size does not exceed a
      15             : /// previous allocated capacity.
      16             : ///
      17             : /// The class is optimized for a small number of elements with many
      18             : /// balanced insertions and removals.  As such, the capacity is not
      19             : /// increased beyond the size required when inserting elements in
      20             : /// order to save memory in the steady-state.
      21             : ///
      22             : /// Differences from std::deque:
      23             : /// * Insertions (including during construction) are O(n) if the
      24             : ///   previous capacity is exceeded and invalidate all references and
      25             : ///   iterators.  Some cases where multiple insertions happen in the
      26             : ///   same method are optimized to perform only one reallocation.
      27             : /// * Erasing elements from the front of the queue invalidates all
      28             : ///   iterators (but not references).
      29             : ///
      30             : /// This last point is not a fundamental limitation, but could be
      31             : /// corrected with a more complicated iterator implementation if the
      32             : /// standard behavior is found to be useful.
      33             : ///
      34             : /// \note This class does not behave like a standard circular buffer,
      35             : /// in that insertion operations never overwrite existing elements.
      36             : /// The circularness is only a reference to the implementation using
      37             : /// circular internal storage to avoid allocations.
      38             : template <typename T>
      39           1 : class CircularDeque
      40             :     : public StaticDeque<T, std::numeric_limits<size_t>::max()> {
      41             :   using StaticDeque<T, std::numeric_limits<size_t>::max()>::StaticDeque;
      42             : };