Ring View

Robert Ramey

Introduction

Given a collection of elements in storage, RingView provides functions to append and extract elements to/from that storage in the same order.

Tutorial

//  Example 1
//
//  Created by Robert Ramey on 8/2/17.
//  Copyright © 2017 Robert Ramey. All rights reserved.

#include <iostream>
#include <iterator>

#include "ring_view.hpp"

int main() {
    // given an array 42 characters long
    char storage[42];

    // create a ring view which uses the whole storage buffer
    ring_view<char *> rv{std::begin(storage), std::end(storage)};

    try{
        // append some characters
        for(char c : "hello world\n"){
            rv.push(c);
        }
        // extract them in first in/ first out sequence
        while(! rv.empty())
            // and display one by one
            std::cout << rv.pop();
    }
    // catch case where too many characters are pushed
    catch(std::overflow_error e){
        std::cout << "overflow error:" << e.what();
    }
    // catch case where more characters are popped than pushed
    catch(std::underflow_error e){
        std::cout << "underflow error:" << e.what();
    }
    std::cout << std::endl;
    return 0;
}

which produces the following output

hello world

Notes

The ring_view is an adaptor in some ways similar to std::queue. Both types create FIFO queues. The difference is that while std::queue manages it's own an std::Sequence container to hold queue elements, ring_view uses previously reserved storage which is referred to via a pair of iterators to specify the beginning and end of the storage. Not having to manage it's own storage and leveraging already existing storage can make ring_view more efficient and easier to use than std::queue.

But since both are FIFO queues, it's natural to expect that the API for a ring_view would be similar to that of std::queue, and indeed it is.

Rationale

1.

P0059R1 Has a much richer and more complete API. Why is the API of ring_view so much smaller.

This is not a standards proposal. It is the simplest component which can perform do what is needed. The API is by that of std::queue. It's so similar in fact, that one could think of it as an alternative implementation of std::queue which uses existing storage rather than allocating it's own. As one gains experience with using ring_view, he might be tempted to enhance it with additional operations. Indeed this is easy and attractive to do. But for now, there doesn't seem much point in making this any more elaborate than it currently is.

Types

This library consists of one type: ring_view

ring_view<I>

Description

A ring_view is an adaptor which provides functions for first in / first out access to existing storage.

Template Parameters

ParameterType RequirementsDescription
IForward Iterator

The type of the iterators used to specify the existing storage

Model of

CopyConstructible, CopyAssignable, MoveConstructible, MoveAssignable, Destructible

The above are implemented by the C++ compiler as default implementations. See Rule of Zero.

Notation

SymbolDescription
IA type that is a model of the ForwardIterator
i, jAn instance of type I
rand instance of type ring_view
Ttype of element in queue from std::iterator_traits<I>::value_type
tand instance of type ring_view::value_type
argslist of arguments to forward to the constructor of element of type ring_view::value_type

Associated Types

The existing storage is some sort of collection, array or sequence accessible by a ForwardIterator . This existing storage - or portion thereof can be made accessible as a queue using this ring_view class.

TypeDescription
std::iterator_traits<I>::value_typeThe type of object stored in the ring_view. This type must model requirements of the Assignable concept.

Inherited Valid Expressions

ring_view models the Assignable and Swappable concept. That is, it supports all valid expressions of that concept.

ring_view does not have a base class. Hence, it does not inherit any functionality from such base class.

New Valid Expressions

In addition to the expressions defined in the Assignable and Swappable concepts, the following expressions must be valid.

ExpressionType RequirementsReturn TypeSemantics
ring_view<I>(i,j)Forward IteratorDefine a queue in storage defined by the pair of iterators i and j. Iterators i and j must be such that j must be reachable by incrementing j some finite number of times. Typically this
ring_view::value_type some typeType of the underlying element in the storage and in the queue.
r.push(t)
const value_type &
value_type &&
voidappend the element v to the end of the queue. If capacity of the queue is exceeded, will throw std::overflow_error.
r.pop() value_type &&extract the element at the head of the queue. If queue is empty, will throw std::underflow_error.
r.front() const value_type &retrieve reference to the element at head of queue.
r.back() const value_type &retrieve reference to the element at tail of queue.
r.empty() boolreturn true of here are no elements in the queue, false otherwise.

Header

#include <ring_view.hpp>

Notes

The ring_view leverages heavily on the interface of the std::queue adaptor. The essential difference is that std::queue maintains it's own storage while ring_view uses existing storage. The std::queue is a Sequence container for which restricts operations on elements to pop_front and push_back. It really has no special value other than that it's name is suggestive of the way it is intended to be used.

But ring_view is NOT a a container so it doesn't model the STL Sequence concept as std::queue does. It never allocates, moves, deletes, or erases elements. push and pop operations are implemented just by incrementing pointers which is a very efficient operation. The only penalty for this efficiency gain is that one must specify the maximum number of elements in the queue when the ring_view is constructed.

stl::queue required that the underlying container support operations push_back() and pop_front() which are used by the implementation of stl::queue. ring_view makes no presumptions about the underlying storage that it uses. It can and will often be used on simple raw array.

Functions

This library defines no free functions.

References

  1. P0059R1 A proposal to add a ring span to the standard library

  2. std::queue standard library component queue