Circular Span

Table of Contents

Introduction
Tutorial
- Running Average
- Finite Impulse Response
Design Rationale
Reference

Note	Precondition namespace circular = trial::circular;

Introduction

The circular::span<T> template class is a span that turns continguous storage into a double-ended circular queue.

Span	The storage is not owned by the span. The owner of the storage is responsible for destroying the span before releasing the storage.
Circular	Inserting elements into the span will remove elements at the other end of the span when the span is full. If elements always are inserted at the same end, then we effectively have a moving window over the most recent elements.
Double-ended	Elements can be inserted either at the beginning or the end of the span. This enables fixed-sized first-in-first-out or last-in-first-out usages.
Queue	Elements can only be inserted and erased at the beginning or end of the span.

Tutorial

Running Average

This tutorial demonstrates a reasonably simple use of a circular span where values are continuously inserted, but only the most recent ones are remembered and used.

Suppose we receive a sequence of numerical values \(x[n]\) one by one over time \(n\), and we want to calculate the running average \(\bar{x}[n]\) of the N most recent values. This is easily done by maintaining a running sum \(M_1[n]\).

\[\begin{aligned} M_1[n] &= M_1[n-1] + x[n] - x[n-N] \\ \bar{x}[n] &= \frac{M_1[n]}{N} \end{aligned}\]

Our class should at least support the following interface for inserting new values and for returning the current mean.

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

    average() noexcept;

    // Insert new value
    void push(value_type value) noexcept;
    // Return current mean
    value_type mean() const noexcept;
};

When we insert a new value, the oldest value must be removed from our running sum, so we have to remember the N most recent values. We therefore want to reserve storage for N values, and have an efficient way of inserting new values and removing old values from this storage. We are going to use a circular span (circular::span<value_type, N> window) that uses an array (value_type storage[N]) as storage.

template <typename T, std::size_t N>
class average
{
    static_assert(N > 0, "N must be greater than zero");

public:
    using value_type = T;

    average() noexcept;

    void push(value_type input) noexcept;
    value_type mean() const noexcept;

private:
    value_type sum = {};
    value_type storage[N];
    circular::span<value_type, N> window;
};

We start by initializing the circular span to use the array as storage.

template <typename T, std::size_t N>
average::average()
    : window(storage) // Instruct span to use storage
{
}

Notice that the array is automatically filled with default-constructed elements. These will be overwritten one by one when inserting new values into the window.

When new values are inserted we first update the running sum. This is done by undoing the effect of the oldest value (window.front()) if the window is full. There is a pre-condition for span<T, N>::front() that it can only be called if the window is not empty; this is guaranteed by the call to window.full().

Afterwards we store the input value in the window (window.push_back(input)) such that we can undo its effect when it later leaves the window. As the push_back() function overwrites the oldest value at the front, it is important that we update the running sum before we store the input value.

template <typename T, std::size_t N>
void average::push(value_type input) noexcept
{
    // Update the current mean
    if (window.full())
    {
        sum += input - window.front();
    }
    else
    {
        sum += input;
    }
    // Remember the input value for later use
    window.push_back(input);
}

The current mean is the calculated as the running sum divided by the number of elements in the window.

template <typename T, std::size_t N>
T average::mean() const noexcept
{
    assert(!window.empty());

    return sum / window.size();
}

Finite Impulse Response

This tutorial demonstrates how to use algorithms on the circular span. All we need are well-behaved iterators. The circular span iterators allows you to traverse all elements from the front to the back, or vice versa with reverse iterators. The iterators automatically handle that the elements may wrap around the underlying storage.

The Finite Impulse Response filter is one of the basic digital filters in the signal processing repertoire. A filtered value \(y[n]\) at time \(n\) is calculated as a weighted sum of input values \(x[i]\).

\[y[n] = \sum_{i=0}^{N} w_i\, x[n - i]\]

In other words, the filtered value is the inner product of the weights and the input values.

We need two containers - one for the weights and one for the input values. The weights are given upon initialization, and the input values are accrued over time. We are only interested in the last N input values, so we use a circular span to store the input values.

template <typename T, std::size_t N>
class impulse
{
    static_assert(std::is_arithmetic<T>::value, "T must be arithmetic");

public:
    using value_type = T;

    template <typename... Weights>
    impulse(Weights&&...);

    // Insert new input value
    void push(value_type);
    // Return filtered value
    value_type value() const;

private:
    // Storage for weights
    std::array<value_type, N> weights;
    // Storage for input values
    value_type storage[N];
    circular::span<value_type, N> window;
};

The weights a passed to the constructor, which also pairs the span to its storage.

template <typename T, std::size_t N>
template <typename... Weights>
impulse::impulse(Weights... weights)
    : weights(std::forward<Weights>(weights)...),
      window(storage) // Instruct span to use storage
{
}

Accruing input values is done by pushing them into the span. The order of the weights are customarily specified starting with the weight \(w_0\) that is multiplied to the most recent input value \(x[n]\), and so on. We therefore insert the input values at the front of the span, so that when we iterate from the beginning towards the end, we will visit the most recent input values first.

template <typename T, std::size_t N>
void impulse::push(value_type input)
{
    window.push_front(std::move(input));
}

Finally, calculating the filtered value is done using the inner product, which is were we need the iterators.

template <typename T, std::size_t N>
auto impulse::value() const -> value_type
{
    // Function is const, so const_iterators are used.
    return std::inner_product(window.begin(),
                              window.end(),
                              weights.begin(),
                              value_type{});
}

Other variations are possible. For instance, we could have pushed the input values at the end of the span, and then used reverse iterators in the algorithm.

Design Rationale

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

Extent

The extent is an optional template argument that specifies the capacity of the span at compile-time. The capacity is part of the span type and therefore does not have to be stored as a member variable.

If the Extent template argument is omitted, or specified as dynamic_extent, the capacity is determined when the span is constructed. The capacity does not change after construction, unless the span is recreated by assignment. For this case, the capacity is stored as a member variable.

The extent has been introduced for alignment with std::span<T, Extent>.

Lazy Destruction

The circular queue uses a lazy destruction policy when elements are removed from the queue. The removed elements are not destroyed immediately but linger in the underlying storage until they are overwritten by an insertion, or the underlying storage is destroyed.

When elements are removed by remove_front() or remove_back() they are left untouched in the underlying storage. Only the internal state of the span is modified.
When elements are popped by pop_front() or pop_back() they are left in a moved-from state in the underlying storage.

In both cases the removed elements in the underlying storage are left in an unspecified but valid state, which enables us to overwrite them later on.

The reason is that the storage is contiguous, so there have to be some unused elements in the storage. The removed elements are therefore left in their position in the storage, and only destroyed when when the position is needed by another insertion. The removed elements are not replaced by some default element for performance reasons.

Segments

Circular span supports subspans, but unlike std::span a subspans of a circular span is not another circular span. Creating a circular span must be done on contiguous storage. Although circular span operates on contiguous storage, the range from begin() until end() is not guaranteed to be contiguous as it may wrap around the underlying storage. Thus, a circular span cannot be constructed from another circular span.

Instead span<T>::segment and span<T>::const_segment are used to represent subspans. These types models the ContiguousRange and SizedRange requirements. This means that they have both begin() and end() returning ContiguousIterator and data() and size() to access the elements in the subspan.

The storage is not owned by the segment.

There are four member functions that returns a segment:

first_segment() returns a range of all contiguous elements starting from the front of the span,
last_segment returns a range of any left-over elements that have been wrapped around in the underlying storage,
first_unused_segment() returns a range of all unused contiguous elements starting from the end of the span, and
last_unused_segment() returns a range of any left-over elements that have been wrapped around in the underlying storage.

Notice that first_segment() will be non-empty if the span is non-empty, and first_unused_segment() will be non-empty is the span is non-full. The remaining segments will be empty if their associated segment can contain all elements.

This functionality is useful for use cases such as zero-copy network transmission of the circular span.

Reference

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

Defined in namespace trial::circular.

template <
    typename T,
    std::size_t Extent = dynamic_extent
> class span;

The circular span template class is a circular view of some contiguous storage. The storage is not owned by the span. The owner must ensure that the span is destroyed before the storage is released.

The size is the current number of elements in the span.

The capacity is the maximum number of elements that can be inserted without overwriting old elements. The capacity cannot be changed.

The extent determines the capacity of the span. With dynamic_extent the capacity is derived from the input arguments at construction or assignment time. Otherwise the capacity is fixed to the specified Extent template argument. Dynamic extent is used by default.

Template arguments

`T`	Element type. Constraint: `T` must be a complete type.
`Extent`	The maximum number of elements in the span.

Member types

Member type	Definition
`element_type`	`T`
`value_type`	`std::remove_cv_t<T>`
`size_type`	`std::size_t`
`pointer`	`element_type*`
`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`	ContiugousRange and SizedRange with `value_type`
`const_segment`	ContiguousRange and SizedRange with `const value_type`

Member functions

Member function	Description
`constexpr span() noexcept`	Creates an empty span with zero capacity. No elements can be inserted into a zero-capacity span. The span must be recreated before use. Ensures: `capacity() == 0` Ensures: `size() == 0`
`constexpr span(const span& other) noexcept`	Creates a span by copying. Ensures: `capacity() == other.capacity()` Ensures: `size() == other.size()`
`constexpr span(span&& other) noexcept`	Creates span by moving. The state of the moved-from span is valid but unspecified. Ensures: `capacity() == other.capacity()` Ensures: `size() == other.size()`
`template <typename U, std::size_t N> explicit constexpr span(const span<U, N>& other) noexcept`	Creates a span by copying from convertible value type or compatible extent. Enables copying a mutable span into an immutable span, or copying a span with fixed extent into a span with dynamic extent. Constraint: `Extent == N` or `Extent == dynamic_extent` Constraint: `U` is convertible to `T` Ensures: `capacity() == other.capacity()` Ensures: `size() == other.size()`
`template <typename ContiguousIterator> constexpr span(ContiguousIterator begin, ContiguousIterator end) noexcept`	Creates a span from iterators. Expects: `Extent == std::distance(begin, end)` or `Extent == dynamic_extent` Ensures: `capacity() == std::distance(begin, end)` Ensures: `size() == std::distance(begin, end)`
`template <typename ContiguousIterator> constexpr span(ContiguousIterator begin, ContiguousIterator end, ContiguousIterator first, size_type length) noexcept`	Creates a span from iterators and initializes the span with the pre-existing `length` elements starting at `first`. Expects: `Extent == std::distance(begin, end)` or `Extent == dynamic_extent` Expects: `first` is within the range `[begin; end]` Expects: `length <= std::distance(first, end)` Ensures: `capacity() == std::distance(begin, end)` Ensures: `size() == length`
`template <std::size_t N> explicit constexpr span(value_type (&)[N]) noexcept`	Creates empty span from an array object with compatible extent. Constraint: `Extent == N` or `Extent == dynamic_extent` Ensures: `capacity() == N` Ensures: `size() == 0`
`constexpr⁠^[1] span& operator=(const span& other) noexcept`	Recreates span by copying. Ensures: `capacity() == other.capacity()` Ensures: `size() == other.size()`
`constexpr⁠^[1] span& operator=(span&&) noexcept`	Recreates span by moving. The state of the moved-from span is valid but unspecified. Ensures: `capacity() == other.capacity()` Ensures: `size() == other.size()`
`constexpr⁠^[1] span& operator=(std::initializer_list<value_type> input) noexcept(see Remarks)`	Replaces span with elements from initializer list. Capacity is unchanged. Constraint: `value_type` must be MoveAssignable. Ensures: `size() == std::min(input.size(), capacity())` Remarks: `noexcept` if `value_type` is nothrow MoveAssignable.
`constexpr bool empty() const noexcept`	Checks if span is empty.
`constexpr bool full() const noexcept`	Checks if span is full.
`constexpr size_type capacity() const noexcept`	Returns the maximum possible number of elements in the span.
`constexpr size_type size() const noexcept`	Returns the number of elements in the span.
`constexpr⁠^[1] reference front() noexcept`	Returns a reference to the first element in the span. Expects: `size() > 0`
`constexpr const_reference front() const noexcept`	Returns a constant reference to the first element in the span. Expects: `size() > 0`
`constexpr⁠^[1] reference back() noexcept`	Returns a reference to the last element in the span. Expects: `size() > 0`
`constexpr const_reference back() const noexcept`	Returns a constant reference to the last element in the span. Expects: `size() > 0`
`constexpr⁠^[1] reference operator[](size_type position) noexcept`	Returns a reference to the element at the given position in the span. Expects: `position < size()`
`constexpr const_reference operator[](size_type position) const noexcept`	Returns a reference to the element at the given position in the span. Expects: `position < size()`
`constexpr⁠^[1] void clear() noexcept`	Clears the span. The elements are not destroyed in the underlying storage. Ensures: `size() == 0`
`template <typename InputIterator> constexpr⁠^[1] void assign(InputIterator first, InputIterator last) noexcept(see Remarks)`	Replaces the span with elements from iterator range. Constraint: `value_type` must be CopyAssignable. 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 span with elements from initializer list. Constraint: `value_type` must be MoveAssignable. 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 span. If the span is full, then the element at the end of the span is silently erased to make room for new element. Constraint: `value_type` must be MoveAssignable. Expects: `capacity() > 0` 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 span. 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 span. If the span is full, then the element at the beginning of the span is silently erased to make room for new element. Constraint: `value_type` must be MoveAssignable. Expects: `capacity() > 0` 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 span. 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 span. 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 span. 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 span. 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 span is full, then the elements are taken from the end of the span. This effectively rotates the span without touching the elements in the underlying storage. Otherwise, the span 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 span. 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 span is full, then the elements are taken from the beginning of the span. This effectively rotates the span without touching the elements in the underlying storage. Otherwise, the span 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 span. 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 span. 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 rotate_front() noexcept(see Remarks)`	Moves elements such that the span starts at the beginning of the storage. Rotation does not alter the sequence of elements in the span. It only rearranges elements in the underlying storage such that first element in the span is located at the first position in the storage. This ensures that the elements are stored contiguously. Consequently the last segment will be empty. Rotation invalidates pointers and references, but does not invalidate iterators. Ensures: `std::distance(last_segment().begin(), last_segment.end()) == 0` Remarks: `noexcept` if `value_type` is nothrow Swappable.
`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 span.
`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 span.
`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 span.
`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 span.
`constexpr⁠^[1] segment first_segment() noexcept` `constexpr const_segment first_segment() const noexcept`	Returns the first contiguous segment of the span. The first segment covers the longest contiguous sequence of used elements in the underlying storage from the beginning of the span. An empty segment is returned if the span 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 span. The last segment covers the remaining used elements not covered by the first segment. Expects: `capacity() > 0`
`constexpr⁠^[1] segment first_unused_segment() noexcept` `constexpr const_segment first_unused_segment() const noexcept`	Returns the first contiguous unused segment of the span. The unused first segment covers the longest contiguous sequence of unused elements from the end of the span. An empty segment is returned if the span 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 span. The unused last segment covers the remaining unused elements in the underlying storage not covered by the unused first segment. Expects: `capacity() > 0`

Non-member constants

dynamic_extent

A constant of type std::size_t to specify a span with dynamic extent.

1. Not constexpr in C++11.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

span.adoc

span.adoc

Circular Span

Introduction

Tutorial

Running Average

Finite Impulse Response

Design Rationale

Extent

Lazy Destruction

Segments

Reference

Template arguments

Member types

Member functions

Non-member constants

Files

span.adoc

Latest commit

History

span.adoc

File metadata and controls

Circular Span

Introduction

Tutorial

Running Average

Finite Impulse Response

Design Rationale

Extent

Lazy Destruction

Segments

Reference

Template arguments

Member types

Member functions

Non-member constants