Sequence Algorithms

Subrange Views

These helper functions create views into an existing sequence. They do not copy elements; instead, they return lightweight objects that refer to the original sequence. Note that this means the original sequences must still be alive, or these views will be dangling, and using them would be undefined behavior.

subrange Work Span 
auto subrange(
  sequence auto&& S,
  std::size_t i,   // start index (inclusive)
  std::size_t j    // end index (exclusive)
)
 $O(1)$ $O(1)$

subrange returns a view of the elements of S with indices in the half-open range [i, j). 

par::array_sequence a{0, 1, 2, 3, 4, 5};
auto x = subrange(a, 1, 4); // x == {1, 2, 3}
subseq Work Span 
auto subseq(
  sequence auto&& S,
  std::size_t i,   // start index (inclusive)
  std::size_t k    // length
)
 $O(1)$ $O(1)$

subseq returns a view of k elements of S, starting at index i. This is equivalent to subrange(S, i, i + k). 

par::array_sequence a{0, 1, 2, 3, 4, 5};
auto x = subseq(a, 2, 3);  // x == {2, 3, 4}
split_mid Work Span 
auto split_mid(
  sequence auto&& S
)
 $O(1)$ $O(1)$

split_mid splits a sequence into two subranges consisting of the first |S|/2 elements and the remaining elements, and returns them as a pair. 

par::array_sequence a{0, 1, 2, 3, 4};
auto [L, R] = par::split_mid(a);  // L == {0, 1}, R == {2, 3, 4}

Aggregation

reduce Work Span 
auto reduce(
  sequence auto&& S,   // the input sequence
  auto identity,       // the identity (initial) value
  auto&& f             // the binary operation
)
 $O(|S|)$ $O(\log |S|)$

reduce combines all elements of a sequence into a single value using a binary operation f. The bounds assumes that invoking f takes constant time. The binary operation f should be associative and identity should act as an identity element for f.

For example, we can compute the sum of a sequence of integers by writing 

par::array_sequence a{1, 2, 3, 4};
auto s = par::reduce(a, 0, std::plus<>{});  // s == 10

As another example, we can compute the maximum element of a sequence 

par::array_sequence a{5, 1, 9, 3};
auto m = par::reduce(a, 0, par::max);  // m == 9
scan Work Span 
auto scan(
  sequence auto&& S,   // the input sequence
  auto identity,       // the identity (initial) value
  auto&& f             // the binary operation
)
 $O(|S|)$ $O(\log |S|)$

Returns: a pair (P, total), where P is the prefix-scan sequence and total is the reduction of the entire input.

scan computes the exclusive prefix scan of a sequence using a binary operation f. The result is a sequence P of the same length as S, where P[i] is the result of combining all elements of S before index i, starting from identity. The bounds assumes that invoking f takes constant time. The binary operation f should be associative and identity should act as an identity element for f. 

par::array_sequence a{1, 2, 3, 4};
auto [p, total] = par::scan(a, 0, std::plus<>{});   // p == {0, 1, 3, 6}, total = 10
scan_inclusive Work Span 
auto scan_inclusive(
  sequence auto&& S,   // the input sequence
  auto identity,       // the identity (initial) value
  auto&& f             // the binary operation
)
 $O(|S|)$ $O(\log |S|)$

scan_inclusive computes the inclusive prefix scan of a sequence using a binary operation f. The result is a sequence P of the same length as S, where P[i] includes the element S[i] in the prefix. The bounds assumes that invoking f takes constant time. The binary operation f should be associative and identity should act as an identity 

par::array_sequence a{1, 2, 3, 4};
auto p = par::scan_inclusive(a, 0, std::plus<>{});  // p == {1, 3, 6, 10}

Sequence Construction

append Work Span 
auto append(
  sequence auto&& S1,   // the first sequence
  sequence auto&& S2    // the second sequence
)
 $O(|S1| + |S2|)$ $O(\log(|S1| + |S2|))$

append returns a new sequence consisting of the elements of S1 followed by the elements of S2. The value type of S2 must be the same as S1. 

par::array_sequence a{1, 2, 3};
par::array_sequence b{4, 5};
auto c = par::append(a, b);  // c == {1, 2, 3, 4, 5}
reverse Work Span 
auto reverse(
  sequence auto&& S    // the input sequence
)
 $O(|S|)$ $O(\log |S|)$

reverse returns a new sequence containing the elements of S in reverse order. 

par::array_sequence a{1, 2, 3, 4};
auto b = par::reverse(a);  // b == {4, 3, 2, 1}
flatten Work Span 
auto flatten(
  sequence auto&& S    // a sequence of sequences
)
 $O\!\left(\displaystyle\sum_{s \in S} \left(|s|+1\right)\right)$ $O(\log |S|)$

flatten takes a sequence whose elements are themselves sequences and concatenates all inner sequences into a single output sequence, preserving their order. 

par::array_sequence<par::array_sequence<int>> a{
  {1, 2},
  {3},
  {4, 5}
};

auto b = par::flatten(a);  // b == {1, 2, 3, 4, 5}
filter Work Span 
auto filter(
  sequence auto&& S,    // the input sequence
  auto&& p              // the predicate
)
 $\displaystyle\sum_{x \in S} \mathcal{W}(p(x))$ $O(\log |S|) + \displaystyle\max_{x \in S} \mathcal{S}(p(x))$

filter returns a new sequence containing exactly those elements of S for which p returns true, preserving their original order. The predicate p is applied once to each element of the sequence. 

par::array_sequence a{1, 2, 3, 4, 5};
auto b = par::filter(a, [](int x) { return x % 2 == 0; });  // b == {2, 4}
unique Work Span 
sequence auto unique(
  sequence auto&& S,   // the input sequence
  auto&& eq            // binary equality predicate (optional)
)
 $O(|S|)$ $O(\log |S|)$

unique returns a new sequence obtained by removing consecutive duplicate elements from S. Two adjacent elements are considered equal if eq returns true. If no equality predicate is provided, == is used.

The work and span bound assumes that eq can be invoked in constant time. 

par::array_sequence a{1, 1, 2, 2, 2, 3, 1};
auto b = par::unique(a);  // b == {1, 2, 3, 1}
par::array_sequence a{1, 4, 7, 2, 5, 3, 6};
auto c = par::unique(a, [](int x, int y) {
  return (x % 3) == (y % 3);
});  // c == {1, 2, 3}

Sorting and Collecting

merge Work Span 
auto merge(
  sequence auto&& S1,   // first sorted sequence
  sequence auto&& S2,   // second sorted sequence
  auto&& comp           // binary comparison function (optional)
)
 $O(|S1| + |S2|)$ $O(\log(|S1| + |S2|))$

merge combines two sorted sequences into a single sorted sequence. Both input sequences must already be sorted according to comp and have the same value type. If no comparison function is provided, < is used. The work and span bounds assume that invoking comp is constant time. 

par::array_sequence a{1, 3, 5};
par::array_sequence b{2, 4, 6};
auto c = par::merge(a, b);  // c == {1, 2, 3, 4, 5, 6}
sort Work Span 
auto sort(
  sequence auto&& S,   // the input sequence
  auto&& comp          // comparison function (optional)
)
 $O(|S| \log |S|)$ $O(\log^2 |S|)$

sort returns a new sequence containing the elements of S sorted according to the comparison function comp. If no comparison function is provided, < is used. The work and span bounds assume that invoking comp is constant time. 

par::array_sequence a{3, 1, 4, 1, 5};
auto b = par::sort(a);  // b == {1, 1, 3, 4, 5}
collect Work Span 
auto collect(
  sequence auto&& S,    // sequence of (key, value) pairs
  auto&& less           // key comparison function (optional)
)
 $O(|S| \log |S|)$ $O(\log^2 |S|)$

collect groups together values with equal keys. The input sequence is assumed to contain pairs of the form (key, value).

The output is a sequence of pairs (key, values), where each values is a sequence containing all values associated with that key.

If no comparison function is provided, operator< is used to compare keys. 

par::array_sequence a{
  std::pair{1, 'a'},
  std::pair{2, 'b'},
  std::pair{1, 'c'},
  std::pair{2, 'd'}
};

auto c = par::collect(a);  // c == {(1, {'a','c'}), (2, {'b','d'})}

Element Transformations

map Work Span 
auto map(
  sequence auto&& S,   // the input sequence
  auto&& f             // the transformation function
)
 $\displaystyle\sum_{x \in S} \mathcal{W}(f(x))$ $\displaystyle\max_{x \in S} \mathcal{S}(f(x))$

map applies a function f independently to each element of a sequence and returns the resulting sequence, preserving the original order. The type of the resulting sequence is the return type of f. 

par::array_sequence a{1, 2, 3, 4};
auto b = par::map(a, [](int x) { return x * x; });  // b == {1, 4, 9, 16}
zip_with Work Span 
auto zip_with(
  auto&& f,            // the combining function
  sequence auto&&... S // the input sequences
)
 $\displaystyle\sum_{i=0}^{|S|-1} \mathcal{W}\!\left(f(S_1[i], \ldots, S_k[i])\right)$ $\displaystyle\max_{i=0}^{|S|-1} \mathcal{S}\!\left(f(S_1[i], \ldots, S_k[i])\right)$

zip_with applies a function f elementwise to multiple sequences. The i-th element of the output is f(S1[i], S2[i], ...). The length of the output sequence is the minimum length of the input sequences. 

par::array_sequence a{1, 2, 3};
par::array_sequence b{4, 5, 6};

auto c = par::zip_with([](int x, int y) {
  return x + y;
}, a, b);  // c == {5, 7, 9}

Lazy Views

zip Work Span 
auto zip(
  sequence auto&&... S    // the input sequences
)
 $O(1)$ $O(1)$

zip returns a view that groups together elements from multiple sequences. The i-th element of the result is a tuple containing the i-th elements of each input sequence.

The length of the zipped view is the minimum length of the input sequences. Elements of the view refer to elements of the original sequences rather than making copies. This means that the original sequences must outlive the zip view. 

par::array_sequence a{1, 2, 3};
par::array_sequence b{4, 5, 6};
auto z = par::zip(a, b);  // z = {(1,4), (2,5), (3,6)}

Side-Effecting/Impure Operations

Warning: These operations are intended to be used by impure/side-effecting code. They should therefore only be used as a last resort when absolutely necessary since they deviate from our preferred, safe style of avoiding shared mutation in parallel code. We will generally tell you when to consider using these operations.
for_each Work Span 
void for_each(
  sequence auto&& S,   // the input sequence
  auto&& f             // function to apply to each input
)
 $\displaystyle\sum_{x \in S} \mathcal{W}(f(x))$ $\displaystyle\max_{x \in S} \mathcal{S}(f(x))$

for_each applies a function f to each element of a sequence, executing the calls in parallel. Unlike map, the function f is expected to have side effects, therefore no result is returned. 

par::array_sequence a{1, 2, 3, 4};
par::for_each(a, [](int& x) {
  x *= 2;
});  // a == {2, 4, 6, 8}
apply_each Work Span 
void apply_each(
  sequence auto&& S,   // the input sequence
  auto&& f             // function to apply to each input
)
 $\displaystyle\sum_{x \in S} \mathcal{W}(f(x))$ $\displaystyle\max_{x \in S} \mathcal{S}(f(x))$

apply_each is similar to for_each, but assumes that the elements of the sequence are tuple-like types. Each tuple is unpacked and passed as arguments to the function f. 

par::array_sequence a{
  std::pair{1, 2},
  std::pair{3, 4}
};

par::apply_each(a, [](int x, int y) {
  std::cout << (x + y) << "\n";
});
// prints:
// 3
// 7