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