Delayed Sequence

Usage: #include <parlay/delayed_sequence.h>

template<
  typename T,
  typename V,
  typename F
> class delayed_sequence;

A delayed sequence is a lazy functional sequence that generates its elements on demand, rather than storing them in memory. A delayed sequence is a random-access range, i.e. it supports random-access iterators. The easiest way to construct a delayed sequence is to use the delayed_tabulate function (see core algorithms), since this avoids the need to explicitly specify the template parameters.

// A sequence consisting of the first 1000 odd integers
auto seq = parlay::delayed_tabulate(1000, [](size_t i) {
  return 2*i + 1;
});

By default, the reference type of a delayed sequence (the type obtained by dereferencing one of its iterators) is the return type of F, or, formally, std::invoke_result_t<const F&, size_t>. The value type of the sequence defaults to std::remove_cv_t<std::remove_reference_t<reference>>. These types can be customized by providing up to two optional arguments to delayed_tabulate.

Reference

Template parameters

Note that, counterintuitively, T is not necessarily a reference-qualified type, but rather, it refers to the type returned by dereferencing the iterator. For a delayed sequence, this could be a prvalue (temporary) type since elements are generated on demand. The value type V should be a type with value semantics that can be used to make a copy of an element of type T.

The function type F must be invokable as a const reference. That is, its operator() should be const qualified. This is true by default for lambdas. In other words, don’t use mutable lambdas in a delayed sequence.

Constructors

delayed_sequence(size_t n, F f)
delayed_sequence(size_t first, size_t last, F f)

Constructs a delayed sequence that generates elements from the given function f. Given n, the sequence consists of the elements f(0), ..., f(n-1). Otherwise, given first and last, the sequence consists of the elements f(first), ... f(last-1).

delayed_sequence(const delayed_sequence&)
delayed_sequence(delayed_sequence&&) noexcept
delayed_sequence& operator=(const delayed_sequence&)
delayed_sequence& operator=(delayed_sequence&&) noexcept

The move constructor is viable provided that the underlying function object is movable. The copy constructor should always be viable since F is required to be copyable.

Member types

Type Definition
value_type V
reference T
const_reference std::add_const_t<T>
iterator A constant random access iterator
const_iterator iterator
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator reverse_iterator
difference_type std::ptrdiff_t
size_type std::size_t

Member functions

Iterators

Function Description
iterator begin() const Iterator to the beginning of the sequence
iterator end() const Iterator to the end of the sequence
const_iterator cbegin() const Constant iterator to the beginning of the sequence
const_iterator cend() const Constant iterator to the end of the sequence
reverse_iterator rbegin() const Reverse iterator to the end of the sequence
reverse_iterator rend() const Reverse iterator to the beginning of the sequence
const_reverse_iterator crbegin() const Constant reverse iterator to the end of the sequence
const_reverse_iterator crend() const Constant reverse iterator to the beginning of the sequence

Element access

Function Description
T operator[](size_t i) const Generate the i’th element of the sequence
T front() const Generate the first element of the sequence
T back() const Generate the last element of the sequence

Size

Function Description
size_type size() const Return the length of the sequence
bool empty() const Return true if the sequence is empty

Miscelaneous

Function Description
void swap(delayed_sequence& other) Swap this delayed sequence with another of the same type