The array_sequence Data Structure

array_sequence

An array_sequence<T> is a concrete implementation of the sequence ADT/concept that maintains a dynamically-sized array.

Creating array_sequences

tabulate Work Span 
auto tabulate(
  size_t n,      // the length of the sequence
  auto&& f       // the element function
)
 $\displaystyle\sum_{i=0}^{n-1} \mathcal{W}(f(i))$ $\displaystyle\max_{i=0}^{n-1} \mathcal{S}(f(i))$

tabulate takes a length n and a function f, and creates an array_sequence of length n such that the i-th element is f(i). The work and span bounds assume that invoking f takes constant time.

Often we will use a lambda as the function f. For example, to create a sequence S of length 1000 such that S[i] == i, i.e., the sequence [0,1,2,...,999], we could write 

auto S = par::tabulate(1000, [](int i) { return i; });

The type of S will be array_sequence<int>. Note that we did not have to specify the value type T explicitly, it was deduced from the return type of the lambda (int). If we want a different type, we can explicitly specify a return type for the lambda: 

auto S = par::tabulate(1000, [](int i) -> double { return i; });
to_sequence Work Span 
auto to_sequence(
  sequence auto&& S        // the sequence to convert
)
 $O(|S|)$ $O(1)$

to_sequence converts a value of any sequence type into an array_sequence. The cost bounds assume that each element of the sequence being converted can be materialized in constant time.

For example, we can convert a std::vector into an array_sequence by writing 

std::vector v{1,2,3};
auto a = par::to_sequence(v);