# Space Optimized Circular Buffer

# circular_buffer_space_optimized<T, Alloc>

## Contents

Description
Synopsis
Rationale
Header Files
Modelled concepts
Specific Public Types
Constructors and Destructor
Specific Public Member Functions
See also
Acknowledgements

## Description

The `circular_buffer_space_optimized` container is an adaptor of the `circular_buffer`. The functionality of the `circular_buffer_space_optimized` is similar to the base `circular_buffer` except it does not allocate memory at once when created rather it allocates memory as needed. (The predictive memory allocation is similar to typical `std::vector` implementation.) Moreover the memory is automatically freed as the size of the container decreases.

Figure: | The memory allocation process of the space optimized circular buffer. The `min_capacity()` of the capacity controller represents the minimal guaranteed amount of allocated memory. The allocated memory will never drop under this value. The default value of the `min_capacity()` is set to `0`.

## Synopsis

Note that some of the links point to the original `circular_buffer` if the functionality is the same.

    namespace boost {

    template <class T, class Alloc>
    class circular_buffer_space_optimized
    {
    public:
       typedef typename Alloc::value_type value_type;
       typedef typename Alloc::pointer pointer;
       typedef typename Alloc::const_pointer const_pointer;
       typedef typename Alloc::reference reference;
       typedef typename Alloc::const_reference const_reference;
       typedef typename Alloc::size_type size_type;
       typedef typename Alloc::difference_type difference_type;
       typedef Alloc allocator_type;
       typedef implementation-defined const_iterator;
       typedef implementation-defined iterator;
       typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
       typedef boost::reverse_iterator<iterator> reverse_iterator;
       typedef std::pair<pointer, size_type> array_range;
       typedef std::pair<const_pointer, size_type> const_array_range;
       typedef implementation-defined capacity_type;

       explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type());
       explicit circular_buffer_space_optimized(capacity_type capacity_ctrl, const allocator_type& alloc = allocator_type());
       circular_buffer_space_optimized(capacity_type capacity_ctrl, const_reference item, const allocator_type& alloc = allocator_type());
       circular_buffer_space_optimized(capacity_type capacity_ctrl, size_type n, const_reference item, const allocator_type& alloc = allocator_type());
       circular_buffer_space_optimized(const circular_buffer_space_optimized<T, Alloc>& cb);
       template <class InputIterator>
          circular_buffer_space_optimized(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
       template <class InputIterator>
          circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
       ~circular_buffer_space_optimized();

       allocator_type get_allocator() const;
       allocator_type& get_allocator();
       iterator begin();
       iterator end();
       const_iterator begin() const;
       const_iterator end() const;
       reverse_iterator rbegin();
       reverse_iterator rend();
       const_reverse_iterator rbegin() const;
       const_reverse_iterator rend() const;
       reference operator[](size_type index);
       const_reference operator[](size_type index) const;
       reference at(size_type index);
       const_reference at(size_type index) const;
       reference front();
       reference back();
       const_reference front() const;
       const_reference back() const;
       array_range array_one();
       array_range array_two();
       const_array_range array_one() const;
       const_array_range array_two() const;
       pointer linearize();
       size_type size() const;
       size_type max_size() const;
       bool empty() const;
       bool full() const;
       size_type reserve() const;
       const capacity_type& capacity() const;
       void set_capacity(const capacity_type& capacity_ctrl);
       void resize(size_type new_size, const_reference item = value_type());
       void rset_capacity(const capacity_type& capacity_ctrl);
       void rresize(size_type new_size, const_reference item = value_type());
       circular_buffer_space_optimized<T, Alloc>& operator=(const circular_buffer_space_optimized<T, Alloc>& cb);
       void assign(size_type n, const_reference item);
       void assign(capacity_type capacity_ctrl, size_type n, const_reference item);
       template <class InputIterator>
          void assign(InputIterator first, InputIterator last);
       template <class InputIterator>
          void assign(capacity_type capacity_ctrl, InputIterator first, InputIterator last);
       void swap(circular_buffer_space_optimized<T, Alloc>& cb);
       void push_back(const_reference item = value_type());
       void push_front(const_reference item = value_type());
       void pop_back();
       void pop_front();
       iterator insert(iterator pos, const_reference item = value_type());
       void insert(iterator pos, size_type n, const_reference item);
       template <class InputIterator>
          void insert(iterator pos, InputIterator first, InputIterator last);
       iterator rinsert(iterator pos, const_reference item = value_type());
       void rinsert(iterator pos, size_type n, const_reference item);
       template <class InputIterator>
          void rinsert(iterator pos, InputIterator first, InputIterator last);
       iterator erase(iterator pos);
       iterator erase(iterator first, iterator last);
       iterator rerase(iterator pos);
       iterator rerase(iterator first, iterator last);
       void clear();
    };

    template <class T, class Alloc>
       bool operator==(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       bool operator<(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       bool operator!=(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       bool operator>(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       bool operator<=(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       bool operator>=(const circular_buffer_space_optimized<T, Alloc>& lhs, const circular_buffer_space_optimized<T, Alloc>& rhs);
    template <class T, class Alloc>
       void swap(circular_buffer_space_optimized<T, Alloc>& lhs, circular_buffer_space_optimized<T, Alloc>& rhs);

    } // namespace boost

## Rationale

The auto-resizing mode of the space optimized circular buffer can be useful in situations when the container can possibly store large number of elements but most of its lifetime the container stores just few of them. The usage of the `circular_buffer_space_optimized` will result in decreased memory consumption and can improve the CPU cache effectiveness.

## Header Files

The `circular_buffer_space_optimized` is defined in the file `boost/circular_buffer.hpp`. There is also a forward declaration for the `circular_buffer_space_optimized` in the header file `boost/circular_buffer_fwd.hpp`.

## Modelled concepts

Random Access Container, Front Insertion Sequence and Back Insertion Sequence.

## Specific Public Types

Following public types are specific to the `circular_buffer_space_optimized`. Description of the public types common with the `circular_buffer` can be found in the `circular_buffer`'s documentation.

Type | Description
--- | ---

`capacity_type`

Capacity controller of the space optimized circular buffer.

    class capacity_control {
       size_type m_capacity;
       size_type m_min_capacity;
    public:
       capacity_control(size_type capacity, size_type min_capacity = 0) : m_capacity(capacity), m_min_capacity(min_capacity) {};
       size_type capacity() const { return m_capacity; }
       size_type min_capacity() const { return m_min_capacity; }
       operator size_type() const { return m_capacity; }
    };

Precondition:
  `capacity >= min_capacity`

The `capacity()` represents the capacity of the `circular_buffer_space_optimized` and the `min_capacity()` determines the minimal allocated size of its internal buffer. The converting constructor of the `capacity_control` allows implicit conversion from `size_type`-like types which ensures compatibility of creating an instance of the `circular_buffer_space_optimized` with other STL containers. On the other hand the operator `size_type()` provides implicit conversion to the `size_type` which allows to treat the capacity of the `circular_buffer_space_optimized` the same way as in the `circular_buffer`.

## Constructors and Destructor

`explicit circular_buffer_space_optimized(const allocator_type& alloc = allocator_type());`
Create an empty space optimized circular buffer with a maximum capacity.

Effect:
  `capacity().capacity() == max_size() && capacity().min_capacity() == 0 && size() == 0`
  There is no memory allocated in the internal buffer.

Parameter(s):
  `alloc`
    The allocator.

Throws:
  Nothing.

Complexity:
  Constant.

`explicit circular_buffer_space_optimized(capacity_type capacity_ctrl, const allocator_type& alloc = allocator_type());`
Create an empty space optimized circular buffer with the specified capacity.

Effect:
  `capacity() == capacity_ctrl && size() == 0`
  The amount of allocated memory in the internal buffer is `capacity_ctrl.min_capacity()`.

Parameter(s):
  `capacity_ctrl`
    The capacity controller representing the maximum number of elements which can be stored in the `circular_buffer_space_optimized` and the minimal allocated size of the internal buffer.
  `alloc`
    The allocator.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).

Complexity:
  Constant.

`circular_buffer_space_optimized(capacity_type capacity_ctrl, const_reference item, const allocator_type& alloc = allocator_type());`
Create a full space optimized circular buffer with the specified capacity filled with `capacity_ctrl.capacity()` copies of `item`.

Effect:
  `capacity() == capacity_ctrl && full() && (*this)[0] == item && (*this)[1] == item && ... && (*this) [capacity_ctrl.capacity() - 1] == item`
  The amount of allocated memory in the internal buffer is `capacity_ctrl.capacity()`.

Parameter(s):
  `capacity_ctrl`
    The capacity controller representing the maximum number of elements which can be stored in the `circular_buffer_space_optimized` and the minimal allocated size of the internal buffer.
  `item`
    The element the created `circular_buffer_space_optimized` will be filled with.
  `alloc`
    The allocator.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Complexity:
  Linear (in the `capacity_ctrl.capacity()`).

`circular_buffer_space_optimized(capacity_type capacity_ctrl, size_type n, const_reference item, const allocator_type& alloc = allocator_type());`
Create a space optimized circular buffer with the specified capacity filled with `n` copies of `item`.

Precondition:
  `capacity_ctrl.capacity() >= n`

Effect:
  `capacity() == capacity_ctrl && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this)[n - 1] == item`
  The amount of allocated memory in the internal buffer is `max[n, capacity_ctrl.min_capacity()]`.

Parameter(s):
  `capacity_ctrl`
    The capacity controller representing the maximum number of elements which can be stored in the `circular_buffer_space_optimized` and the minimal allocated size of the internal buffer.
  `n`
    The number of elements the created `circular_buffer_space_optimized` will be filled with.
  `item`
    The element the created `circular_buffer_space_optimized` will be filled with.
  `alloc`
    The allocator.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Complexity:
  Linear (in the `n`).

`circular_buffer_space_optimized(const circular_buffer_space_optimized<T,Alloc>& cb);`
The copy constructor.

Creates a copy of the specified `circular_buffer_space_optimized`.

Effect:
  `*this == cb`
  The amount of allocated memory in the internal buffer is `cb.size()`.

Parameter(s):
  `cb`
    The `circular_buffer_space_optimized` to be copied.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Complexity:
  Linear (in the size of `cb`).

`template <class InputIterator>
circular_buffer_space_optimized(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());`
Create a full space optimized circular buffer filled with a copy of the range.

Precondition:
  Valid range `[first, last)`.
  `first` and `last` have to meet the requirements of InputIterator.

Effect:
  `capacity().capacity() == std::distance(first, last) && capacity().min_capacity() == 0 && full() && (*this)[0]== *first && (*this)[1] == *(first + 1) && ... && (*this)[std::distance(first, last) - 1] == *(last - 1)`
  The amount of allocated memory in the internal buffer is `std::distance(first, last)`.

Parameter(s):
  `first`
    The beginning of the range to be copied.
  `last`
    The end of the range to be copied.
  `alloc`
    The allocator.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Complexity:
  Linear (in the `std::distance(first, last)`).

`template <class InputIterator>
circular_buffer_space_optimized(capacity_type capacity_ctrl, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());`
Create a space optimized circular buffer with the specified capacity (and the minimal guaranteed amount of allocated memory) filled with a copy of the range.

Precondition:
  Valid range `[first, last)`.
  `first` and `last` have to meet the requirements of InputIterator.

Effect:
  `capacity() == capacity_ctrl && size() <= std::distance(first, last) && (*this)[0]== (last - capacity_ctrl.capacity()) && (*this)[1] == *(last - capacity_ctrl.capacity() + 1) && ... && (*this)[capacity_ctrl.capacity() - 1] == *(last - 1)`
  If the number of items to be copied from the range `[first, last)` is greater than the specified `capacity_ctrl.capacity()` then only elements from the range `[last - capacity_ctrl.capacity(), last)` will be copied.
  The amount of allocated memory in the internal buffer is `max[capacity_ctrl.min_capacity(), min[capacity_ctrl.capacity(), std::distance(first, last)]]`.

Parameter(s):
  `capacity_ctrl`
    The capacity controller representing the maximum number of elements which can be stored in the `circular_buffer_space_optimized` and the minimal allocated size of the internal buffer.
  `first`
    The beginning of the range to be copied.
  `last`
    The end of the range to be copied.
  `alloc`
    The allocator.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Complexity:
  Linear (in `std::distance(first, last)`; in `min[capacity_ctrl.capacity(), std::distance(first, last)]` if the `InputIterator` is a RandomAccessIterator).

`~circular_buffer_space_optimized();`
The destructor.

Destroys the `circular_buffer_space_optimized`.

Throws:
  Nothing.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (including iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `clear()`

## Specific Public Member Functions

Following public member functions of the `circular_buffer_space_optimized` have different behaviour from the base `circular_buffer`. Description of the public member functions with the same behaviour can be found in the `circular_buffer`'s documentation.

`bool full() const;`
Is the `circular_buffer_space_optimized` full?

Returns:
  `true` if the number of elements stored in the `circular_buffer_space_optimized` equals the capacity of the `circular_buffer_space_optimized`; `false` otherwise.

Throws:
  Nothing.

Exception Safety:
  No-throw.

Iterator Invalidation:
  Does not invalidate any iterators.

Complexity:
  Constant (in the size of the `circular_buffer_space_optimized`).

See Also:
  `empty()`

`size_type reserve() const;`
Get the maximum number of elements which can be inserted into the `circular_buffer_space_optimized` without overwriting any of already stored elements.

Returns:
  `capacity().capacity() - size()`

Throws:
  Nothing.

Exception Safety:
  No-throw.

Iterator Invalidation:
  Does not invalidate any iterators.

Complexity:
  Constant (in the size of the `circular_buffer_space_optimized`).

See Also:
  `capacity()`, `size()`, `max_size()`

`const capacity_type& capacity() const;`
Get the capacity of the `circular_buffer_space_optimized`.

Returns:
  The capacity controller representing the maximum number of elements which can be stored in the `circular_buffer_space_optimized` and the minimal allocated size of the internal buffer.

Throws:
  Nothing.

Exception Safety:
  No-throw.

Iterator Invalidation:
  Does not invalidate any iterators.

Complexity:
  Constant (in the size of the `circular_buffer_space_optimized`).

See Also:
  `reserve()`, `size()`, `max_size()`, `set_capacity(const capacity_type&)`

`void set_capacity(const capacity_type& capacity_ctrl);`
Change the capacity (and the minimal guaranteed amount of allocated memory) of the `circular_buffer_space_optimized`.

Effect:
  `capacity() == capacity_ctrl && size() <= capacity_ctrl.capacity()`
  If the current number of elements stored in the `circular_buffer_space_optimized` is greater than the desired new capacity then number of `[size() - capacity_ctrl.capacity()]` last elements will be removed and the new size will be equal to `capacity_ctrl.capacity()`.
  If the current number of elements stored in the `circular_buffer_space_optimized` is lower than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as necessary but it will never drop below `capacity_ctrl.min_capacity()`.

Parameter(s):
  `capacity_ctrl`
    The new capacity controller.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Strong.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `min[size(), capacity_ctrl.capacity()]`).

Note:
  To explicitly clear the extra allocated memory use the shrink-to-fit technique:
  `boost::circular_buffer_space_optimized<int> cb(1000);
  ...
  boost::circular_buffer_space_optimized<int>(cb).swap(cb);`
  For more information about the shrink-to-fit technique in STL see http://www.gotw.ca/gotw/054.htm.

See Also:
  `rset_capacity(const capacity_type&)`, `resize(size_type, const_reference)`

`void resize(size_type new_size, const_reference item = value_type());`
Change the size of the `circular_buffer_space_optimized`.

Effect:
  `size() == new_size && capacity().capacity() >= new_size`
  If the new size is greater than the current size, copies of `item` will be inserted at the back of the of the `circular_buffer_space_optimized` in order to achieve the desired size. In the case the resulting size exceeds the current capacity the capacity will be set to `new_size`.
  If the current number of elements stored in the `circular_buffer_space_optimized` is greater than the desired new size then number of `[size() - new_size]` last elements will be removed. (The capacity will remain unchanged.)
  The amount of allocated memory in the internal buffer may be accommodated as necessary.

Parameter(s):
  `new_size`
    The new size.
  `item`
    The element the `circular_buffer_space_optimized` will be filled with in order to gain the requested size. (See the Effect.)

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the new size of the `circular_buffer_space_optimized`).

See Also:
  `rresize(size_type, const_reference)`, `set_capacity(const capacity_type&)`

`void rset_capacity(const capacity_type& capacity_ctrl);`
Change the capacity (and the minimal guaranteed amount of allocated memory) of the `circular_buffer_space_optimized`.

Effect:
  `capacity() == capacity_ctrl && size() <= capacity_ctrl`
  If the current number of elements stored in the `circular_buffer_space_optimized` is greater than the desired new capacity then number of `[size() - capacity_ctrl.capacity()]` first elements will be removed and the new size will be equal to `capacity_ctrl.capacity()`.
  If the current number of elements stored in the `circular_buffer_space_optimized` is lower than the new capacity then the amount of allocated memory in the internal buffer may be accommodated as necessary but it will never drop below `capacity_ctrl.min_capacity()`.

Parameter(s):
  `capacity_ctrl`
    The new capacity controller.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Strong.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `min[size(), capacity_ctrl.capacity()]`).

See Also:
  `set_capacity(const capacity_type&)`, `rresize(size_type, const_reference)`

`void rresize(size_type new_size, const_reference item = value_type());`
Change the size of the `circular_buffer_space_optimized`.

Effect:
  `size() == new_size && capacity().capacity() >= new_size`
  If the new size is greater than the current size, copies of `item` will be inserted at the front of the of the `circular_buffer_space_optimized` in order to achieve the desired size. In the case the resulting size exceeds the current capacity the capacity will be set to `new_size`.
  If the current number of elements stored in the `circular_buffer_space_optimized` is greater than the desired new size then number of `[size() - new_size]` first elements will be removed. (The capacity will remain unchanged.)
  The amount of allocated memory in the internal buffer may be accommodated as necessary.

Parameter(s):
  `new_size`
    The new size.
  `item`
    The element the `circular_buffer_space_optimized` will be filled with in order to gain the requested size. (See the Effect.)

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the new size of the `circular_buffer_space_optimized`).

See Also:
  `resize(size_type, const_reference)`, `rset_capacity(const capacity_type&)`

`circular_buffer_space_optimized<T,Alloc>& operator=(const circular_buffer_space_optimized<T,Alloc>& cb);`
The assign operator.

Makes this `circular_buffer_space_optimized` to become a copy of the specified `circular_buffer_space_optimized`.

Effect:
  `*this == cb`
  The amount of allocated memory in the internal buffer is `cb.size()`.

Parameter(s):
  `cb`
    The `circular_buffer_space_optimized` to be copied.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Strong.

Iterator Invalidation:
  Invalidates all iterators pointing to this `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of `cb`).

See Also:
  `assign(size_type, const_reference)`, `assign(capacity_type, size_type, const_reference)`, `assign(InputIterator, InputIterator)`, `assign(capacity_type, InputIterator, InputIterator)`

`void assign(size_type n, const_reference item);`
Assign `n` items into the space optimized circular buffer.

The content of the `circular_buffer_space_optimized` will be removed and replaced with `n` copies of the `item`.

Effect:
  `capacity().capacity() == n && capacity().min_capacity() == 0 && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this) [n - 1] == item`
  The amount of allocated memory in the internal buffer is `n`.

Parameter(s):
  `n`
    The number of elements the `circular_buffer_space_optimized` will be filled with.
  `item`
    The element the `circular_buffer_space_optimized` will be filled with.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the `n`).

See Also:
  `operator=`, `assign(capacity_type, size_type, const_reference)`, `assign(InputIterator, InputIterator)`, `assign(capacity_type, InputIterator, InputIterator)`

`void assign(capacity_type capacity_ctrl, size_type n, const_reference item);`
Assign `n` items into the space optimized circular buffer specifying the capacity.

The capacity of the `circular_buffer_space_optimized` will be set to the specified value and the content of the `circular_buffer_space_optimized` will be removed and replaced with `n` copies of the `item`.

Precondition:
  `capacity_ctrl.capacity() >= n`

Effect:
  `capacity() == capacity_ctrl && size() == n && (*this)[0] == item && (*this)[1] == item && ... && (*this) [n - 1] == item`
  The amount of allocated memory will be `max[n, capacity_ctrl.min_capacity()]`.

Parameter(s):
  `capacity_ctrl`
    The new capacity controller.
  `n`
    The number of elements the `circular_buffer_space_optimized` will be filled with.
  `item`
    The element the `circular_buffer_space_optimized` will be filled with.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the `n`).

See Also:
  `operator=`, `assign(size_type, const_reference)`, `assign(InputIterator, InputIterator)`, `assign(capacity_type, InputIterator, InputIterator)`

`template <class InputIterator>
void assign(InputIterator first, InputIterator last);`
Assign a copy of the range into the space optimized circular buffer.

The content of the `circular_buffer_space_optimized` will be removed and replaced with copies of elements from the specified range.

Precondition:
  Valid range `[first, last)`.
  `first` and `last` have to meet the requirements of InputIterator.

Effect:
  `capacity().capacity() == std::distance(first, last) && capacity().min_capacity() == 0 && size() == std::distance(first, last) && (*this)[0]== *first && (*this)[1] == *(first + 1) && ... && (*this)[std::distance(first, last) - 1] == *(last - 1)`
  The amount of allocated memory in the internal buffer is `std::distance(first, last)`.

Parameter(s):
  `first`
    The beginning of the range to be copied.
  `last`
    The end of the range to be copied.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the `std::distance(first, last)`).

See Also:
  `operator=`, `assign(size_type, const_reference)`, `assign(capacity_type, size_type, const_reference)`, `assign(capacity_type, InputIterator, InputIterator)`

`template <class InputIterator>
void assign(capacity_type capacity_ctrl, InputIterator first, InputIterator last);`
Assign a copy of the range into the space optimized circular buffer specifying the capacity.

The capacity of the `circular_buffer_space_optimized` will be set to the specified value and the content of the `circular_buffer_space_optimized` will be removed and replaced with copies of elements from the specified range.

Precondition:
  Valid range `[first, last)`.
  `first` and `last` have to meet the requirements of InputIterator.

Effect:
  `capacity() == capacity_ctrl && size() <= std::distance(first, last) && (*this)[0]== *(last - capacity) && (*this)[1] == *(last - capacity + 1) && ... && (*this)[capacity - 1] == *(last - 1)`
  If the number of items to be copied from the range `[first, last)` is greater than the specified `capacity` then only elements from the range `[last - capacity, last)` will be copied.
  The amount of allocated memory in the internal buffer is `max[std::distance(first, last), capacity_ctrl.min_capacity()]`.

Parameter(s):
  `capacity_ctrl`
    The new capacity controller.
  `first`
    The beginning of the range to be copied.
  `last`
    The end of the range to be copied.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `std::distance(first, last)`; in `min[capacity_ctrl.capacity(), std::distance(first, last)]` if the `InputIterator` is a RandomAccessIterator).

See Also:
  `operator=`, `assign(size_type, const_reference)`, `assign(capacity_type, size_type, const_reference)`, `assign(InputIterator, InputIterator)`

`void swap(circular_buffer_space_optimized<T,Alloc>& cb);`
Swap the contents of two space optimized circular buffers.

Effect:
  `this` contains elements of `cb` and vice versa; the capacity and the amount of allocated memory in the internal buffer of `this` equal to the capacity and the amount of allocated memory of `cb` and vice versa.

Parameter(s):
  `cb`
    The `circular_buffer_space_optimized` whose content will be swapped.

Throws:
  Nothing.

Exception Safety:
  No-throw.

Iterator Invalidation:
  Invalidates all iterators of both `circular_buffer_space_optimized` containers. (On the other hand the iterators still point to the same elements but within another container. If you want to rely on this feature you have to turn the Debug Support off otherwise an assertion will report an error if such invalidated iterator is used.)

Complexity:
  Constant (in the size of the `circular_buffer_space_optimized`).

See Also:
  `swap(circular_buffer_space_optimized<T, Alloc>&, circular_buffer_space_optimized<T, Alloc>&)`

`void push_back(const_reference item = value_type());`
Insert a new element at the end of the space optimized circular buffer.

Effect:
  if `capacity().capacity() > 0` then `back() == item`
  If the `circular_buffer_space_optimized` is full, the first element will be removed. If the capacity is `0`, nothing will be inserted.
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `item`
    The element to be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `push_front(const_reference)`, `pop_back()`, `pop_front()`

`void push_front(const_reference item = value_type());`
Insert a new element at the beginning of the space optimized circular buffer.

Effect:
  if `capacity().capacity() > 0` then `front() == item`
  If the `circular_buffer_space_optimized` is full, the last element will be removed. If the capacity is `0`, nothing will be inserted.
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `item`
    The element to be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `push_back(const_reference)`, `pop_back()`, `pop_front()`

`void pop_back();`
Remove the last element from the space optimized circular buffer.

Precondition:
  `!empty()`

Effect:
  The last element is removed from the `circular_buffer_space_optimized`.
  The amount of allocated memory in the internal buffer may be predictively decreased.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `pop_front()`, `push_back(const_reference)`, `push_front(const_reference)`

`void pop_front();`
Remove the first element from the space optimized circular buffer.

Precondition:
  `!empty()`

Effect:
  The first element is removed from the `circular_buffer_space_optimized`.
  The amount of allocated memory in the internal buffer may be predictively decreased.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `pop_back()`, `push_back(const_reference)`, `push_front(const_reference)`

`iterator insert(iterator pos, const_reference item = value_type());`
Insert an element at the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.

Effect:
  The `item` will be inserted at the position `pos`.
  If the `circular_buffer_space_optimized` is full, the first element will be overwritten. If the `circular_buffer_space_optimized` is full and the `pos` points to `begin()`, then the `item` will not be inserted. If the capacity is `0`, nothing will be inserted.
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position where the `item` will be inserted.
  `item`
    The element to be inserted.

Returns:
  Iterator to the inserted element or `begin()` if the `item` is not inserted. (See the Effect.)

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `insert(iterator, size_type, value_type)`, `insert(iterator, InputIterator, InputIterator)`, `rinsert(iterator, value_type)`, `rinsert(iterator, size_type, value_type)`, `rinsert(iterator, InputIterator, InputIterator)`

`void insert(iterator pos, size_type n, const_reference item);`
Insert `n` copies of the `item` at the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.

Effect:
  The number of `min[n, (pos - begin()) + reserve()]` elements will be inserted at the position `pos`.
  The number of `min[pos - begin(), max[0, n - reserve()]]` elements will be overwritten at the beginning of the `circular_buffer_space_optimized`.
  (See Example for the explanation.)
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position where the `item`s will be inserted.
  `n`
    The number of `item`s the to be inserted.
  `item`
    The element whose copies will be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `min[capacity().capacity(), size() + n]`).

Example:
  Consider a `circular_buffer_space_optimized` with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.
  `|1|2|3|4| | |`
  `p ---^`
  After inserting 5 elements at the position `p`:
  `insert(p, (size_t)5, 0);`
  actually only 4 elements get inserted and elements `1` and `2` are overwritten. This is due to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like this:
  `|0|0|0|0|3|4|`
  For comparison if the capacity would not be preserved the internal buffer would then result in `|1|2|0|0|0|0|0|3|4|`.

See Also:
  `insert(iterator, value_type)`, `insert(iterator, InputIterator, InputIterator)`, `rinsert(iterator, value_type)`, `rinsert(iterator, size_type, value_type)`, `rinsert(iterator, InputIterator, InputIterator)`

`template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last);`
Insert the range `[first, last)` at the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.
  Valid range `[first, last)` where `first` and `last` meet the requirements of an InputIterator.

Effect:
  Elements from the range `[first + max[0, distance(first, last) - (pos - begin()) - reserve()], last)` will be inserted at the position `pos`.
  The number of `min[pos - begin(), max[0, distance(first, last) - reserve()]]` elements will be overwritten at the beginning of the `circular_buffer_space_optimized`.
  (See Example for the explanation.)
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position where the range will be inserted.
  `first`
    The beginning of the range to be inserted.
  `last`
    The end of the range to be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `[size() + std::distance(first, last)]`; in `min[capacity().capacity(), size() + std::distance(first, last)]` if the `InputIterator` is a RandomAccessIterator).

Example:
  Consider a `circular_buffer_space_optimized` with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.
  `|1|2|3|4| | |`
  `p ---^`
  After inserting a range of elements at the position `p`:
  `int array[] = { 5, 6, 7, 8, 9 };`
  `insert(p, array, array + 5);`
  actually only elements `6`, `7`, `8` and `9` from the specified range get inserted and elements `1` and `2` are overwritten. This is due to the fact the insert operation preserves the capacity. After insertion the internal buffer looks like this:
  `|6|7|8|9|3|4|`
  For comparison if the capacity would not be preserved the internal buffer would then result in `|1|2|5|6|7|8|9|3|4|`.

See Also:
  `insert(iterator, value_type)`, `insert(iterator, size_type, value_type)`, `rinsert(iterator, value_type)`, `rinsert(iterator, size_type, value_type)`, `rinsert(iterator, InputIterator, InputIterator)`

`iterator rinsert(iterator pos, const_reference item = value_type());`
Insert an element before the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.

Effect:
  The `item` will be inserted before the position `pos`.
  If the `circular_buffer_space_optimized` is full, the last element will be overwritten. If the `circular_buffer_space_optimized` is full and the `pos` points to `end()`, then the `item` will not be inserted. If the capacity is `0`, nothing will be inserted.
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position before which the `item` will be inserted.
  `item`
    The element to be inserted.

Returns:
  Iterator to the inserted element or `end()` if the `item` is not inserted. (See the Effect.)

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `rinsert(iterator, size_type, value_type)`, `rinsert(iterator, InputIterator, InputIterator)`, `insert(iterator, value_type)`, `insert(iterator, size_type, value_type)`, `insert(iterator, InputIterator, InputIterator)`

`void rinsert(iterator pos, size_type n, const_reference item);`
Insert `n` copies of the `item` before the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.

Effect:
  The number of `min[n, (end() - pos) + reserve()]` elements will be inserted before the position `pos`.
  The number of `min[end() - pos, max[0, n - reserve()]]` elements will be overwritten at the end of the `circular_buffer_space_optimized`.
  (See Example for the explanation.)
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position where the `item`s will be inserted.
  `n`
    The number of `item`s the to be inserted.
  `item`
    The element whose copies will be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `min[capacity().capacity(), size() + n]`).

Example:
  Consider a `circular_buffer_space_optimized` with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.
  `|1|2|3|4| | |`
  `p ---^`
  After inserting 5 elements before the position `p`:
  `rinsert(p, (size_t)5, 0);`
  actually only 4 elements get inserted and elements `3` and `4` are overwritten. This is due to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like this:
  `|1|2|0|0|0|0|`
  For comparison if the capacity would not be preserved the internal buffer would then result in `|1|2|0|0|0|0|0|3|4|`.

See Also:
  `rinsert(iterator, value_type)`, `rinsert(iterator, InputIterator, InputIterator)`, `insert(iterator, value_type)`, `insert(iterator, size_type, value_type)`, `insert(iterator, InputIterator, InputIterator)`

`template <class InputIterator>
void rinsert(iterator pos, InputIterator first, InputIterator last);`
Insert the range `[first, last)` before the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` or its end.
  Valid range `[first, last)` where `first` and `last` meet the requirements of an InputIterator.

Effect:
  Elements from the range `[first, last - max[0, distance(first, last) - (end() - pos) - reserve()])` will be inserted before the position `pos`.
  The number of `min[end() - pos, max[0, distance(first, last) - reserve()]]` elements will be overwritten at the end of the `circular_buffer`.
  (See Example for the explanation.)
  The amount of allocated memory in the internal buffer may be predictively increased.

Parameter(s):
  `pos`
    An iterator specifying the position where the range will be inserted.
  `first`
    The beginning of the range to be inserted.
  `last`
    The end of the range to be inserted.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::T(const T&)` throws.
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in `[size() + std::distance(first, last)]`; in `min[capacity().capacity(), size() + std::distance(first, last)]` if the `InputIterator` is a RandomAccessIterator).

Example:
  Consider a `circular_buffer_space_optimized` with the capacity of 6 and the size of 4. Its internal buffer may look like the one below.
  `|1|2|3|4| | |`
  `p ---^`
  After inserting a range of elements before the position `p`:
  `int array[] = { 5, 6, 7, 8, 9 };`
  `insert(p, array, array + 5);`
  actually only elements `5`, `6`, `7` and `8` from the specified range get inserted and elements `3` and `4` are overwritten. This is due to the fact the rinsert operation preserves the capacity. After insertion the internal buffer looks like this:
  `|1|2|5|6|7|8|`
  For comparison if the capacity would not be preserved the internal buffer would then result in `|1|2|5|6|7|8|9|3|4|`.

See Also:
  `rinsert(iterator, value_type)`, `rinsert(iterator, size_type, value_type)`, `insert(iterator, value_type)`, `insert(iterator, size_type, value_type)`, `insert(iterator, InputIterator, InputIterator)`

`iterator erase(iterator pos);`
Remove an element at the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` (but not an `end()`).

Effect:
  The element at the position `pos` is removed.
  The amount of allocated memory in the internal buffer may be predictively decreased.

Parameter(s):
  `pos`
    An iterator pointing at the element to be removed.

Returns:
  Iterator to the first element remaining beyond the removed element or `end()` if no such element exists.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `erase(iterator, iterator)`, `rerase(iterator)`, `rerase(iterator, iterator)`, `clear()`

`iterator erase(iterator first, iterator last);`
Erase the range `[first, last)`.

Precondition:
  Valid range `[first, last)`.

Effect:
  The elements from the range `[first, last)` are removed. (If `first == last` nothing is removed.)
  The amount of allocated memory in the internal buffer may be predictively decreased.

Parameter(s):
  `first`
    The beginning of the range to be removed.
  `last`
    The end of the range to be removed.

Returns:
  Iterator to the first element remaining beyond the removed elements or `end()` if no such element exists.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `erase(iterator)`, `rerase(iterator)`, `rerase(iterator, iterator)`, `clear()`

`iterator rerase(iterator pos);`
Remove an element at the specified position.

Precondition:
  `pos` is a valid iterator pointing to the `circular_buffer_space_optimized` (but not an `end()`).
  The amount of allocated memory in the internal buffer may be predictively decreased.

Effect:
  The element at the position `pos` is removed.

Parameter(s):
  `pos`
    An iterator pointing at the element to be removed.

Returns:
  Iterator to the first element remaining in front of the removed element or `begin()` if no such element exists.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

Note:
  Basically there is no difference between `erase(iterator)` and this method. It is implemented only for consistency with the base `circular_buffer`.

See Also:
  `erase(iterator)`, `erase(iterator, iterator)`, `rerase(iterator, iterator)`, `clear()`

`iterator rerase(iterator first, iterator last);`
Erase the range `[first, last)`.

Precondition:
  Valid range `[first, last)`.

Effect:
  The elements from the range `[first, last)` are removed. (If `first == last` nothing is removed.)
  The amount of allocated memory in the internal buffer may be predictively decreased.

Parameter(s):
  `first`
    The beginning of the range to be removed.
  `last`
    The end of the range to be removed.

Returns:
  Iterator to the first element remaining in front of the removed elements or `begin()` if no such element exists.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).
  Whatever `T::operator = (const T&)` throws.

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

Note:
  Basically there is no difference between `erase(iterator, iterator)` and this method. It is implemented only for consistency with the base `circular_buffer`.

See Also:
  `erase(iterator)`, `erase(iterator, iterator)`, `rerase(iterator)`, `clear()`

`void clear();`
Remove all stored elements from the space optimized circular buffer.

Effect:
  `size() == 0`
  The amount of allocated memory in the internal buffer may be predictively decreased.

Throws:
  An allocation error if memory is exhausted (`std::bad_alloc` if the standard allocator is used).

Exception Safety:
  Basic.

Iterator Invalidation:
  Invalidates all iterators pointing to the `circular_buffer_space_optimized` (except iterators equal to `end()`).

Complexity:
  Linear (in the size of the `circular_buffer_space_optimized`).

See Also:
  `~circular_buffer_space_optimized()`, `erase(iterator)`, `erase(iterator, iterator)`, `rerase(iterator)`, `rerase(iterator, iterator)`

## See also

`boost::circular_buffer, std::vector`

## Acknowledgements

The idea of the space optimized circular buffer has been introduced by Pavel Vozenilek.