array.adoc

Circular Array

Table of Contents

• Introduction
• Tutorial
  • Running Average
• Design Rationale
  • std::array
• Reference
  • Template arguments
  • Member types
  • Member functions

Note	Precondition namespace circular = trial::circular;

Introduction

The circular::array<T, N> template class is a fixed-size double-ended circular queue.

The circular array has a fixed size, which means there can be at most N elements in the circular array, where N is determined at compile-time. Like std::array<T, N>, all N elements within the storage of the circular array are default constructed when the circular array is instantiated. Although all elements in the embedded array are constructed, the circular array will appear as empty. Inserting elements will overwrite the default constructed elements.

Tutorial

Running Average

In the circular span tutorial we ended up with a class definition for a running average containing both an array and a span.

template <typename T, std::size_t N>
class average
{
public:
    using value_type = T;

    // Member functions...

private:
    static_assert(N > 0, "N must be greater than zero");
    value_type sum = {};
    // Storage and window
    value_type storage[N];
    circular::span<value_type, N> window;
};

Combining a fixed-size storage with a circular span is exactly the purpose of the circular array, so we can replace the storage and span with circular::array<T, N>.

template <typename T, std::size_t N>
class average
{
public:
    using value_type = T;

    // Member functions...

private:
    static_assert(N > 0, "N must be greater than zero");
    value_type sum = {};
    // Window contains storage
    circular::array<value_type, N> window;
};

Design Rationale

This section describes the choices behind the design of the circular array.

The design rationale of circular::span<T, N> also applies, except the ability to use dynamic_extent.

std::array

The circular array, being a fixed-size container, is modeled after std::array<T, N>. The storage is located inside the circular array, which gives good locality and this cache performance, but move is linear time complexity.

There are some significant deviations.

• The circular array keeps track of the number of inserted elements. Although the underlying storage is filled with default constructed elements, they do not count as inserted elements. Inserted elements are those that have been assigned to the container, or that have been pushed to the front or the back.

• The circular array does not fulfill the ContiguousContainer requirements even though the storage is contiguous. This is because the circular array can wrap around the end of the storage, so it cannot fulfill the ContiguousIterator concept.

Reference

Defined in header <trial/circular/array.hpp>.

Defined in namespace trial::circular.

template <
    typename T,
    std::size_t N
> class array;

The circular array is a fixed-size circular queue.

The size is the current number of elements in the circular array.

The capacity is the maximum number of elements that can be inserted without overwriting old elements. The capacity is set to N at compile-time and cannot be changed at run-time.

The underlying storage will default construct N elements at construction-time. Inserting elements into the circular array will overwrite elements in the storage. Erasing elements from the circular array will leave the elements in the storage either untouched or in a moved-from state. The only guarantee given with regards to the elements in the storage is that they are in a valid state and therefore can either can be overwritten when new elements are inserted or destroyed when the circular array is destroyed.

Template arguments

T	Element type. Constraint: T must be a complete type. Constraint: T must be DefaultConstructible. Constraint: T must be Erasable.
N	The maximum number of elements in the span. Constraint: N cannot be dynamic_extent.

Member types

Member type	Definition
element_type	T
value_type	std::remove_cv_t<T>
size_type	std::size_t
reference	element_type&
const_reference	const element_type&
iterator	RandomAccessIterator with value_type
const_iterator	RandomAccessIterator with const value_type
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>
segment	ContiguousRange and SizedRange with value_type
const_segment	ContiguousRange and SizedRange with const value_type

Member functions

Member function	Description
constexpr array() noexcept	Creates an empty circular array. The N elements of the underlying storage are default constructed. Ensures: capacity() == N Ensures: size() == 0
constexpr array(const array<T, N>& other) noexcept(see Remarks)	Creates a circular array by copying. Constraint: T must be CopyConstructible. Ensures: capacity() == other.capacity() Ensures: size() == other.size() Remarks: noexcept if value_type is nothrow CopyConstructible.
constexpr array(array<T, N>&& other) noexcept(see Remarks)	Creates a circular array by moving. Constraint: T must be MoveConstructible. Ensures: capacity() == other.capacity() Ensures: size() == other.size() Remarks: noexcept if value_type is nothrow MoveConstructible.
template <typename…​ Args> constexpr array(value_type, Args&&…​) noexcept(see Remarks)	Creates a circular array with elements from input. This constructor emulates aggregate initialization. Ensures: capacity() == N Ensures: size() == std::min(input.size(), N) Remarks: noexcept if value_type is nothrow MoveAssignable.
constexpr⁠[1] array& operator=(const array<T, N>& other) noexcept(see Remarks)	Recreates circular array by copying. Constraint: T must be CopyAssignable. Ensures: capacity() == other.capacity() Ensures: size() == other.size() Remarks: noexcept if value_type is nothrow CopyAssignable.
constexpr⁠[1] array& operator=(array&& other) noexcept(see Remarks)	Recreates circular array by moving. All elements are inserted, but if input.size() > N then only the last N input elements will remain in the circular array. Ensures: capacity() == other.capacity() Ensures: size() == other.size() Remarks: noexcept if value_type is nothrow MoveAssignable.
constexpr⁠[1] array& operator=(std::initializer_list<value_type> input) noexcept(see Remarks)	Recreates circular array with elements from initializer list. All elements are inserted, but if input.size() > N then only the last N input elements will remain in the circular array. Ensures: capacity() == N Ensures: size() == std::min(input.size(), N) Remarks: noexcept if value_type is nothrow MoveAssignable.
constexpr bool empty() const noexcept	Checks if circular array is empty. Empty means that size() == 0.
constexpr bool full() const noexcept	Checks if circular array is full. Full means that size() == capacity().
constexpr size_type capacity() const noexcept	Returns the maximum possible number of elements in the circular array.
constexpr size_type size() const noexcept	Returns the number of elements in the circular array.
constexpr size_type max_size() const noexcept	Returns the maximum possible number of elements in the circular array.
constexpr⁠[1] reference front() noexcept	Returns a reference to the first element in the circular array. Expects: size() > 0
constexpr const_reference front() const noexcept	Returns a constant reference to the first element in the circular array. Expects: size() > 0
constexpr⁠[1] reference back() noexcept	Returns a reference to the last element in the circular array. Expects: size() > 0
constexpr const_reference back() const noexcept	Returns a constant reference to the last element in the circular array. Expects: size() > 0
constexpr⁠[1] void clear() noexcept	Clears the circular array. The elements in the underlying storage are not destroyed. Ensures: capacity() == N Ensures: size() == 0
template <typename InputIterator> constexpr⁠[1] void assign(InputIterator first, InputIterator last) noexcept(see Remarks)	Replaces the circular array with elements from iterator range. Ensures: size() == std::min(std::distance(first, last), capacity()) Remarks: noexcept if value_type is nothrow CopyAssignable.
constexpr⁠[1] void assign(std::initializer_list<value_type> input) noexcept(see Remarks)	Replaces the circular array with elements from initializer list. Ensures: size() == std::min(input.size(), capacity()) Remarks: noexcept if value_type is nothrow MoveAssignable.
constexpr⁠[1] void push_front(value_type) noexcept(see Remarks)	Inserts an element at the beginning of the circular array. If the circular array is full, then the element at the end of the circular array is silently erased to make room for the new element. Expects: capacity() > 0 Ensures: size() <= capacity() Remarks: noexcept if value_type is nothrow MoveAssignable.
template <typename InputIterator> constexpr⁠[1] void push_front(InputIterator first, InputIterator last) noexcept(see Remarks)	Inserts elements from iterator range at the beginning of the circular array. Constraint: value_type must be CopyAssignable. Expects: capacity() > 0 Remarks: noexcept if value_type is nothrow CopyAssignable.
constexpr⁠[1] void push_back(value_type) noexcept(see Remarks)	Inserts an element at the end of the circular array. If the circular array is full, then the element at the beginning of the circular array is silently erased to make room for the new element. Expects: capacity() > 0 Ensures: size() <= capacity() Remarks: noexcept if value_type is nothrow MoveAssignable.
template <typename InputIterator> constexpr⁠[1] void push_back(InputIterator first, InputIterator last) noexcept(see Remarks)	Inserts elements from iterator range at the end of the circular array. Constraint: value_type must be CopyAssignable. Expects: capacity() > 0 Remarks: noexcept if value_type is nothrow CopyAssignable.
constexpr⁠[1] value_type pop_front() noexcept(see Remarks)	Removes and returns an element from the beginning of the circular array. The removed element in the underlying storage is left in a moved-from state. If the return value is unused, then remove_front() is a more efficient method for removing the front element. Expects: size() > 0 Remarks: noexcept if value_type is nothrow MoveConstructible.
constexpr⁠[1] value_type pop_back() noexcept(see Remarks)	Removes and returns an element from the end of the circular array. The removed element in the underlying storage is left in a moved-from state. If the return value is unused, then remove_back() is a more efficient method for removing the back element. Expects: size() > 0 Remarks: noexcept if value_type is nothrow MoveConstructible.
constexpr⁠[1] void expand_front() noexcept constexpr⁠[1] void expand_front(size_type count) noexcept	Inserts the given number of unspecified elements at the beginning of the circular array. The default value of count is 1 if omitted. Makes room for count elements at the front. The inserted elements are in an unspecified but valid state. If the circular array is full, then the elements are taken from the end of the circular array. This effectively rotates the circular array without touching the elements in the underlying storage. Otherwise, the circular array is enlarged. Expects: capacity() > 0 Expects: count <= capacity() Ensures: size() >= count
constexpr⁠[1] void expand_back() noexcept constexpr⁠[1] void expand_back(size_type count) noexcept	Inserts the given number of unspecified elements at the end of the circular array. The default value of count is 1 if omitted. Makes room for count elements at the back. The inserted elements are in an unspecified but valid state. If the circular array is full, then the elements are taken from the beginning of the circular array. This effectively rotates the circular array without touching the elements in the underlying storage. Otherwise, the circular array is enlarged. Expects: capacity() > 0 Expects: count <= capacity() Ensures: size() >= count
constexpr⁠[1] void remove_front() noexcept constexpr⁠[1] void remove_front(size_type count) noexcept	Removes the given number of elements from the beginning of the circular array. The default value of count is 1 if omitted. The removed elements are not destroyed in the underlying storage. Expects: size() > 0 Expects: count <= size() Ensures: capacity() - size() >= count
constexpr⁠[1] void remove_back() noexcept constexpr⁠[1] void remove_back(size_type count) noexcept	Removes the given number of elements from the end of the circular array. The default value of count is 1 if omitted. The removed elements are not destroyed in the underlying storage. Expects: size() > 0 Expects: count <= size() Ensures: capacity() - size() >= count
constexpr⁠[1] iterator begin() noexcept constexpr const_iterator begin() const noexcept constexpr const_iterator cbegin() const noexcept	Returns an interator to the beginning of the circular array.
constexpr⁠[1] iterator end() noexcept constexpr const_iterator end() const noexcept constexpr const_iterator cend() const noexcept	Returns an interator to the end of the circular array.
constexpr⁠[1] reverse_iterator rbegin() noexcept constexpr const_reverse_iterator rbegin() const noexcept constexpr const_reverse_iterator crbegin() const noexcept	Returns a reverse interator to the beginning of the circular array.
constexpr⁠[1] reverse_iterator rend() noexcept constexpr const_reverse_iterator rend() const noexcept constexpr const_reverse_iterator crend() const noexcept	Returns a reverse interator to the end of the circular array.
constexpr⁠[1] segment first_segment() noexcept +constexpr const_segment first_segment() const noexcept	Returns the first contiguous segment of the circular array. The first segment covers the longest contiguous sequence of used elements in the underlying storage from the beginning of the circular array. An empty segment is returned if the circular array is empty. An empty segment has data() == nullptr and size() == 0. Expects: capacity() > 0 Ensures: std::distance(first_segment().begin(), first_segment().end()) > 0 unless empty()
constexpr⁠[1] segment last_segment() noexcept +constexpr const_segment last_segment() const noexcept	Returns the last contiguous segment of the circular array. The last segment covers the remaining used elements not covered by the first segment. Expects: capacity() > 0
constexpr⁠[1] reference operator[](size_type position) noexcept	Returns a reference to the element at the given position in the circular array. Expects: position < size()
constexpr const_reference operator[](size_type positon) const noexcept	Returns a reference to the element at the given position in the circular array. Expects: position < size()
constexpr⁠[1] segment first_unused_segment() noexcept constexpr const_segment first_unused_segment() const noexcept	Returns the first contiguous unused segment of the circular array. The unused first segment covers the longest contiguous sequence of unused elements from the end of the circular array. An empty segment is returned if the circular array is full. An empty segment has data() == nullptr and size() == 0. Expects: capacity() > 0 Ensures: std::distance(last_unused_segment().begin(), last_unused_segment().end()) > 0 unless full()
constexpr⁠[1] segment last_unused_segment() noexcept constexpr const_segment last_unused_segment() const noexcept	Returns the last contiguous unused segment of the circular array. The unused last segment covers the remaining unused elements in the underlying storage not covered by the unused first segment. Expects: capacity() > 0

---

1. Not constexpr in C++11.