Skip to content

ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

License

Notifications You must be signed in to change notification settings

martinmoene/ring-span-lite

Repository files navigation

ring-span lite: A circular buffer view for C++98 and later

Language License Build Status Version download Conan Vcpkg Try it on wandbox Try it on godbolt online

Contents

Example usage

#include "nonstd/ring_span.hpp"
#include <iostream>
#include <numeric>

template< typename T, size_t N >
inline size_t dim( T (&arr)[N] ) { return N; }

template< typename T, class Popper>
inline std::ostream & operator<<( std::ostream & os, ::nonstd::ring_span<T, Popper> const & rs )
{
    os << "[ring_span: "; std::copy( rs.begin(), rs.end(), std::ostream_iterator<T>(os, ", ") ); return os << "]";
}

int main()
{
    double arr[]   = { 2.0 , 3.0, 5.0, };
    double coeff[] = { 0.25, 0.5, 0.25 };

    nonstd::ring_span<double> buffer( arr, arr + dim(arr), arr, dim(arr) );

    std::cout << buffer << "\n";

    // new sample:
    buffer.push_back( 7.0 );

    std::cout << buffer << "\n";

    double result = std::inner_product( buffer.begin(), buffer.end(), coeff, 0.0 );

    std::cout << "filter result: " << result << "\n";
}

Compile and run

prompt> g++ -std=c++98 -Wall -I../include -o 01-filter.exe 01-filter.cpp && 01-filter.exe
[ring_span: 2, 3, 5, ]
[ring_span: 3, 5, 7, ]
filter result: 5

Or to run with Buck:

prompt> buck run example/:01-filter 

In a nutshell

ring-span lite is a single-file header-only library to represent a circular buffer view on a container. The library aims to provide a C++yy-like ring_span for use with C++98 and later [1][2]. Its initial code is inspired on the reference implementation by Arthur O'Dwyer [3]. It is my intention to let the interface of this ring_span follow the unfolding standard one.

This library also includes header <ring.hpp> to provide a data-owning ring buffer.

Features and properties of ring-span lite are ease of installation (single header), freedom of dependencies other than the standard library.

Limitations of ring-span lite are ... .

License

ring-span lite is distributed under the Boost Software License.

Dependencies

ring-span lite has no other dependencies than the C++ standard library.

Installation

ring-span lite is a single-file header-only library. Put ring_span.hpp in the include folder directly into the project source tree or somewhere reachable from your project.

Synopsis

Contents

Types in namespace nonstd

Purpose p0059 Type Notes
Circular buffer view ✓/– template<
 class T
 , class Popper = default_popper<T>
 , bool CapacityIsPowerOf2 = false
>
class ring_span
See Note 1 below.
Ignore element template< class T >
class null_popper
 
Return element template< class T >
class default_popper
 
Return element, replace original template< class T >
class copy_popper
 

Note 1: CapacityIsPowerOf2 is an extension (nsrs_CONFIG_STRICT_P0059=0).With CapacityIsPowerOf2 being true, method normalize_() is optimized to use bitwise and instead of modulo division.

Interface of ring-span lite

Class ring_span

Kind p0059 Type / Method Note / Result
Various types type ring_span<T, Popper[, CapacityIsPowerOf2]>
  size_type  
Value types value_type  
  pointer  
  reference  
  const_reference  
Iterator types iterator  
  const_iterator  
  reverse_iterator  
  const_reverse_iterator  
Construction ring_span(
It begin, It end
, Popper popper = Popper() ) noexcept
create empty span of
distance(begin,end) capacity
  ring_span(
It begin, It end
, It first, size_type size
, Popper popper = Popper() ) noexcept
create partially filled span of
distance(begin,end) capacity,
size elements
  ring_span( ring_span && ) = default (>= C++11)
  ring_span& operator=( ring_span && ) = default (>= C++11)
  ring_span( ring_span const & ) implicitly deleted (>= C++11)
  ring_span & operator=( ring_span const & ); implicitly deleted (>= C++11)
  ring_span( ring_span const & ) declared private (< C++11)
  ring_span & operator=( ring_span const & ); declared private (< C++11)
Iteration begin() noexcept iterator
  begin() noexcept const_iterator
  cbegin() noexcept const_iterator
  end() noexcept iterator
  end() noexcept const_iterator
  cend() noexcept const_iterator
Reverse iter. rbegin() noexcept reverse_iterator
  rbegin() noexcept const_reverse_iterator
  crbegin() noexcept const_reverse_iterator
  rend() noexcept reverse_iterator
  rend() noexcept const_reverse_iterator
  crend() noexcept const_reverse_iterator
Observation empty() noexcept true if empty
  full() noexcept true if full
  size() noexcept current number of elements
  capacity() noexcept maximum number of elements
Element access front() noexcept reference to element at front
  front() noexcept const_reference to element at front
  back() noexcept reference to back element at back
  back() noexcept const_reference to element at back
  operator[]( size_type idx ) noexcept reference to element at specified index
  operator[]( size_type idx ) noexcept const_reference to element at specified index
Elem.extraction pop_front() Popper::return_type (p0059: auto)
  pop_back() Popper::return_type
Elem.insertion push_back( value_type const & value ) noexcept(…) void; restrained (>= C++11)
  push_back( value_type const & value ) void; unrestrained (< C++11)
  push_back( value_type && value ) noexcept(…) void; restrained (>= C++11)
  emplace_back( Args &&... args ) noexcept(…) void; restrained (>= C++11)
  push_front( value_type const & value ) noexcept(…) void; restrained (>= C++11)
  push_front( value_type const & value ) void; unrestrained (< C++11)
  push_front( value_type && value ) noexcept(…) void; restrained (>= C++11)
  emplace_front( Args &&... args ) noexcept(…) void; restrained (>= C++11)
Swap swap( ring_span & rhs ) noexcept void;

Class ring_iterator

Kind p0059 Type / Method Note / Result
Various types type ring_span< T, Popper >
  difference_type  
Value types value_type  
  pointer  
  reference  
Category iterator_category  
Construction ring_iterator() = default (>= C++11)
  ring_iterator() (< C++11)
Conversion operator ring_iterator<…,true>() const noexcept const ring_iterator
Element access operator*() const noexcept reference
Increment operator++() noexcept ring_iterator<…> &
  operator++( int ) noexcept ring_iterator<…>
Decrement operator--() noexcept ring_iterator<…> &
  operator--( int ) noexcept ring_iterator<…>
Addition operator+=( int i ) noexcept ring_iterator<…> &
  operator-=( int i ) noexcept ring_iterator<…> &
Difference operator-( ring_iterator<…> const & rhs ) difference_type, Note 1
Comparison operator==( ring_iterator<…> const & rhs ) const noexcept bool, Note 1
  operator!=( ring_iterator<…> const & rhs ) const noexcept bool, Note 1
  operator<( ring_iterator<…> const & rhs ) const noexcept bool, Note 1
  operator<=( ring_iterator<…> const & rhs ) const noexcept bool, Note 1
  operator>( ring_iterator<…> const & rhs ) const noexcept bool, Note 1
  operator>=( ring_iterator<…> const & rhs ) const noexcept bool, Note 1

Note 1: accepts lhs and rhs of different const-ness.

Non-member functions for ring-span lite

Kind p0059 Function Note / Result
Swap –/✓ swap( ring_span<…> & lhs, ring_span<…> & rhs ) void
Iterator offset operator+( ring_iterator<…> it, int i ) noexcept ring_iterator<…>
  operator+( int i, ring_iterator<…> it ) noexcept ring_iterator<…>
  operator-( ring_iterator<…> it, int i ) noexcept ring_iterator<…>
  operator-( int i, ring_iterator<…> it ) noexcept ring_iterator<…>

Legenda: – not in proposal · ✓ in proposal · –/✓ not in proposal/in sg14 code

Class ring

Kind Type / Method Note / Result
Circular buffer template<
 class Container
 , bool CapacityIsPowerOf2 = false
>
class ring
See Note 1 below.
Various types size_type  
Value types value_type  
  reference  
  const_reference  
Iterator types iterator  
  const_iterator  
  reverse_iterator  
  const_reverse_iterator  
Construction ring() create empty ring,
C-array, std::array
  ring(size_type size) create empty ring of capacity size,
dynamic container
Iteration begin() noexcept iterator
  begin() noexcept const_iterator
  cbegin() noexcept const_iterator
  end() noexcept iterator
  end() noexcept const_iterator
  cend() noexcept const_iterator
Reverse iter. rbegin() noexcept reverse_iterator
  rbegin() noexcept const_reverse_iterator
  crbegin() noexcept const_reverse_iterator
  rend() noexcept reverse_iterator
  rend() noexcept const_reverse_iterator
  crend() noexcept const_reverse_iterator
Observation empty() noexcept true if empty
  full() noexcept true if full
  size() noexcept current number of elements
  capacity() noexcept maximum number of elements
Element access front() noexcept reference to element at front
  front() noexcept const_reference to element at front
  back() noexcept reference to back element at back
  back() noexcept const_reference to element at back
Element access front() noexcept reference to element at front
  front() noexcept const_reference to element at front
  back() noexcept reference to back element at back
  back() noexcept const_reference to element at back
  operator[]( size_type idx ) noexcept reference to element at specified index
  operator[]( size_type idx ) noexcept const_reference to element at specified index
Elem.extraction pop_front() Popper::return_type
  pop_back() Popper::return_type
Elem.insertion & push_back( value_type const & value ) noexcept(…) void; restrained (>= C++11)
  push_back( value_type const & value ) void; unrestrained (< C++11)
  push_back( value_type && value ) noexcept(…) void; restrained (>= C++11)
  emplace_back( Args &&... args ) noexcept(…) void; restrained (>= C++11)
  push_front( value_type const & value ) noexcept(…) void; restrained (>= C++11)
  push_front( value_type const & value ) void; unrestrained (< C++11)
  push_front( value_type && value ) noexcept(…) void; restrained (>= C++11)
  emplace_front( Args &&... args ) noexcept(…) void; restrained (>= C++11)
Swap swap( ring_span & rhs ) noexcept void;

Note 1: CapacityIsPowerOf2 is an extension (nsrs_CONFIG_STRICT_P0059=0).With CapacityIsPowerOf2 being true, method normalize_() is optimized to use bitwise and instead of modulo division. Class default_popper is used as popper.

Configuration macros

Tweak header

If the compiler supports __has_include(), ring-span lite supports the tweak header mechanism. Provide your tweak header as nonstd/ring_span.tweak.hpp in a folder in the include-search-path. In the tweak header, provide definitions as documented below, like #define nsrs_CPLUSPLUS 201103L.

Standard selection macro

-Dnsrs_CPLUSPLUS=199711L
Define this macro to override the auto-detection of the supported C++ standard, if your compiler does not set the __cpluplus macro correctly.

Select std::ring_span or nonstd::ring_span

At default, ring_span lite uses std::ring_span if it is available and lets you use it via namespace nonstd. You can however override this default and explicitly request to use std::ring_span or ring_span lite's nonstd::ring_span as nonstd::ring_span via the following macros.

-Dnsrs_CONFIG_SELECT_RING_SPAN=nsrs_RING_SPAN_DEFAULT
Define this to nsrs_RING_SPAN_STD to select std::ring_span as nonstd::ring_span. Define this to nsrs_RING_SPAN_NONSTD to select nonstd::ring_span as nonstd::ring_span. Default is undefined, which has the same effect as defining to nsrs_RING_SPAN_DEFAULT.

Disable extensions

-Dnsrs_CONFIG_STRICT_P0059=0
Define this to 1 to omit behaviour not present in proposal p0059. Default is undefined (same effect as 0).

Enable popper empty base class optimization

-Dnsrs_CONFIG_POPPER_EMPTY_BASE_CLASS=0
Poppers are often stateless. To prevent they take up space C++20 attribute [[no_unique_address]] is used when available. Another way to prevent up taking space is to make the popper a base class of class ring_span. This is what occurs with macro nsrs_CONFIG_POPPER_EMPTY_BASE_CLASS defined to 1. This is an extension to proposal p0059. Disabling extensions via macro nsrs_CONFIG_STRICT_P0059 also disables this extension. Default is undefined (same effect as 0).

Enable compilation errors

-Dnsrs_CONFIG_CONFIRMS_COMPILATION_ERRORS=0
Define this to 1 to include the tests with compile-time errors. Default is undefined (same effect as 0).

Reported to work with

The table below mentions the compiler versions ring-span lite is reported to work with.

OS Compiler Versions
Windows Clang/LLVM ?
  GCC 5.2.0, 6.3.0
  Visual C++
(Visual Studio)
8 (2005), 10 (2010), 11 (2012),
12 (2013), 14 (2015, 2017)
GNU/Linux Clang/LLVM 3.5.0
  GCC 4.8.4
OS X ? ?

Building the tests

To build the tests you need:

The lest test framework is included in the test folder.

Buck

To run the tests:

prompt> buck run test/

CMake

The following steps assume that the ring-span lite source code has been cloned into a directory named c:\ring-span-lite.

  1. Create a directory for the build outputs for a particular architecture.
    Here we use c:\ring-span-lite\build-win-x86-vc10.

     cd c:\ring-span-lite
     md build-win-x86-vc10
     cd build-win-x86-vc10
    
  2. Configure CMake to use the compiler of your choice (run cmake --help for a list).

     cmake -G "Visual Studio 10 2010" [see 3. below] ..
    
  3. Optional. You can control above configuration through the following options:

    • -DRING_SPAN_LITE_COLOURISE_TEST=ON: use colour for pass, fail, default off
  4. Build the test suite in the Debug configuration (alternatively use Release).

     cmake --build . --config Debug
    
  5. Run the test suite.

     ctest -V -C Debug
    

All tests should pass, indicating your platform is supported and you are ready to use ring-span lite. See the table with supported types and functions.

Other ring-span implementations

Notes and references

References

[1] p0059: A proposal to add a ring span to the standard library (latest, r4, r3, r2, r1, r0).
[2] WG21-SG14/SG14. Reference implementation of std::ring_span by Guy Davidson and Arthur O'Dwyer.
[3] Arthur O'Dwyer. Reference implementation of std::ring_span.
[4] Arthur O’Dwyer. Reference types with metadata cause problems. 30 May 2018.
[5] Phillip Johnston. Creating a Circular Buffer in C and C++. 17 May 2017.
[6] Jan Gaspar. Boost.Circular Buffer.

Appendix

Contents

A.1 Applets

Applets demonstrate a specific use case. They are available via tag [.applet].

> ring-span-main.t.exe -l .applet
ring_span: filter[.applet]

A.2 Compile-time information

The version of ring-span lite is available via tag [.version]. The following tags are available for information on the compiler and on the C++ standard library used: [.compiler], [.stdc++], [.stdlanguage] and [.stdlibrary].

A.3 Ring-span lite test specification

Note: test cases that assert are tagged with [.assert] and only run when [.assert] is included on the command line, like: test [.assert] partial-test-name.

click to expand

ring_span: Allows to construct an empty span from an iterator pair
ring_span: Allows to construct an empty span from an iterator pair - capacity is power of 2
ring_span: Allows to construct a partially filled span from an iterator pair and iterator, size
ring_span: Allows to construct a partially filled span from an iterator pair and iterator, size - capacity is power of 2
ring_span: Disallows to copy-construct from a ring_span (compile-time)
ring_span: Disallows to copy-assign from a ring_span (compile-time)
ring_span: Allows to move-construct from a ring_span (C++11)
ring_span: Allows to move-assign from a ring_span (C++11)
ring_span: Allows to obtain the capacity of a span
ring_span: Allows to obtain the number of elements in a span (size)
ring_span: Allows to check for an empty span
ring_span: Allows to check for a full span
ring_span: Allows to observe the element at the specified index [extension]
ring_span: Allows to observe the element at the front
ring_span: Allows to observe the element at the back
ring_span: Allows to obtain and remove the element at the front
ring_span: Allows to obtain and remove the element at the back [extension]
ring_span: Allows to copy-insert an element at the front [extension]
ring_span: Allows to move-insert an element at the front (C++11) [extension]
ring_span: Allows to emplace an element at the front (C++11) [extension]
ring_span: Allows to copy-insert an element at the back
ring_span: Allows to move-insert an element at the back (C++11)
ring_span: Allows to emplace an element at the back (C++11)
ring_span: Adding an element to an empty span makes it non-empty (front) [extension]
ring_span: Adding an element to an empty span makes it non-empty (back)
ring_span: Adding an element to an empty span doesn't change its capacity (front) [extension]
ring_span: Adding an element to an empty span doesn't change its capacity (back)
ring_span: Adding an element to a full span leaves it full (front) [extension]
ring_span: Adding an element to a full span leaves it full (back)
ring_span: Adding an element to a full span doesn't change its capacity (front) [extension]
ring_span: Adding an element to a full span doesn't change its capacity (back)
ring_span: Removing an element from a span with one element makes it empty (front)
ring_span: Removing an element from a span with one element makes it empty (back) [extension]
ring_span: Removing an element from a span with one element doesn't change its capacity (front)
ring_span: Removing an element from a span with one element doesn't change its capacity (back) [extension]
ring_span: Removing an element from a full span makes it not full (front)
ring_span: Removing an element from a full span makes it not full (back) [extension]
ring_span: Removing an element from a full span doesn't change its capacity (front)
ring_span: Removing an element from a full span doesn't change its capacity (back) [extension]
ring_span: Allows to swap spans (member)
ring_span: Allows to swap spans (non-member)
ring_span: Allows to appear in range-for (C++11)
ring_span: Allows iteration (non-const)
ring_span: Allows iteration (const)
ring_span: Allows iteration (mixed const-non-const)
ring_span: Allows reverse iteration (non-const) [extension]
ring_span: Allows reverse iteration (const) [extension]
ring_span: Allows reverse iteration (mixed const-non-const) [extension]
ring_span: A span with capacity zero is both empty and full
ring_span: A full span is a delay-line of capacity elements (back-front)
ring_span: A full span is a delay-line of capacity elements (front-back) [extension]
ring_span: A non-full span is a stack of capacity elements (back) [extension]
ring_span: A non-full span is a stack of capacity elements (front) [extension]
ring_span: A non-full span behaves like an harmonica (back-front)
ring_span: A non-full span behaves like an harmonica (front-back) [extension]
ring_iterator: Allows conversion to const ring_iterator [extension]
ring_iterator: Allows to dereference iterator (operator*())
ring_iterator: Allows to dereference iterator (operator->())
ring_iterator: Allows to index from iterator (operator[](size_t))
ring_iterator: Allows to increment iterator (prefix)
ring_iterator: Allows to increment iterator (postfix)
ring_iterator: Allows to decrement iterator (prefix)
ring_iterator: Allows to decrement iterator (postfix)
ring_iterator: Allows to advance iterator (+=) [extension]
ring_iterator: Allows to advance iterator (-=) [extension]
ring_iterator: Allows to offset iterator (+) [extension]
ring_iterator: Allows to offset iterator (-) [extension]
ring_iterator: Allows to obtain difference of iterators [extension]
ring_iterator: Allows to compare iterators (==)
ring_iterator: Allows to compare iterators (!=)
ring_iterator: Allows to compare iterators (<)
ring_iterator: Allows to compare iterators (<=)
ring_iterator: Allows to compare iterators (>)
ring_iterator: Allows to compare iterators (>=)
ring_iterator: Allows to compare iterators (mixed const-non-const)
null_popper: A null popper returns void
null_popper: A null popper leaves the original element unchanged
default_popper: A default popper returns the element
default_popper: A default popper moves the element (C++11)
default_popper: A default popper leaves the original element unchanged
copy_popper: A copy popper returns the element
copy_popper: A copy popper replaces the original element
ring: Allows to create data owning ring from container
ring: Allows to create data owning ring from container - capacity is power of 2
ring: Allows to create data owning ring from std::array (C++11)
ring: Allows to create data owning ring from C-array
tweak header: reads tweak header if supported [tweak]