Algorithms#

Lifting functions#

constexpr auto lf::lift = []<class F, class... Args>(auto, F &&func, Args &&...args)static ->task<std::invoke_result_t<F, Args...>>requires std::invocable<F, Args...>{co_return std::invoke(std::forward<F>(func), std::forward<Args>(args)...);}#

A higher-order function that lifts a function into an asynchronous function.

This is useful for when you want to fork a regular function:

auto work(int x) -> int;

Then later in some async context you can do:

{
  int a, b;

  co_await fork[a, lift](work, 42);
  co_await fork[b, lift](work, 007);

  co_await join;
}

Note

The lifted function will accept arguments by forwarding reference.

LF_LOFT(name)#

Lift an overload-set/template into a constrained lambda.

This is useful for passing overloaded/template names to higher order functions like lf::fork/lf::call.

LF_CLOFT(name, ...)#

Lift an overload-set/template into a constrained capturing lambda.

The variadic arguments are used as the lambda’s capture.

This is useful for passing overloaded/template names to higher order functions like lf::fork/lf::call.

Iteration with for_each#

constexpr impl::for_each_overload lf::for_each = {}#

A parallel implementation of std::ranges::for_each.

Effective call signature:

template <std::random_access_iterator I,
          std::sized_sentinel_for<I> S,
          typename Proj = std::identity,
          indirectly_unary_invocable<projected<I, Proj>> Fun
          >
void for_each(I head, S tail, std::iter_difference_t<I> n, Fun fun, Proj proj = {});

Overloads exist for a random-access range (instead of head and tail) and n can be omitted (which will set n = 1).

Exemplary usage:

co_await just[for_each](v, 10, [](auto &elem) {
  elem = 0;
});

This will set each element of v to 0 in parallel using a chunk size of 10.

If the function or projection handed to for_each are async functions, then they will be invoked asynchronously, this allows you to launch further tasks recursively.

Unlike std::ranges::for_each, this function will make an implementation defined number of copies of the function objects and may invoke these copies concurrently.

Transformations with map#

constexpr impl::map_overload lf::map = {}#

A parallel variation of std::transform.

Effective call signature:

template <std::random_access_iterator I,
          std::sized_sentinel_for<I> S,
          std::random_access_iterator O
          typename Proj = std::identity,
          indirectly_unary_invocable<projected<I, Proj>> Fun
          >
  requires std::indirectly_copyable<projected<I, Proj, Fun>, O>
void map(I head, S tail, O out, std::iter_difference_t<I> n, Fun fun, Proj proj = {});

Overloads exist for a random-access range (instead of head and tail) and n can be omitted (which will set n = 1).

Exemplary usage:

std::vector<int> out(v.size());

co_await just[map](v, out.begin(), 10, [](int const& elem) {
  return elem + 1;
});

This will set each element of out to one more than corresponding element in v using a chunk size of 10.

The input and output ranges must either be distinct (i.e. non-overlapping) or the same range (hence the transformation may be performed in-place).

If the function or projection handed to map are async functions, then they will be invoked asynchronously, this allows you to launch further tasks recursively.

Unlike std::transform, this function will make an implementation defined number of copies of the function objects and may invoke these copies concurrently.

Reductions with fold#

constexpr impl::fold_overload lf::fold = {}#

A parallel implementation of std::ranges::fold_left_first.

Effective call signature:

template <std::random_access_iterator I,
          std::sized_sentinel_for<I> S,
          typename Proj = std::identity,
          indirectly_foldable<projected<I, Proj>> Bop
          >
auto fold(I head, S tail, std::iter_difference_t<I> n, Bop bop, Proj proj = {}) -> indirect_fold_acc_t<Bop, I, Proj>;

Overloads exist for a random-access range (instead of head and tail) and n can be omitted (which will set n = 1).

Exemplary usage:

co_await just[fold](v, 10, std::plus<>{}, [](auto &elem) -> std::size_t {
  return elem % 2 == 0;
});

This counts the number of even elements in v in parallel, using a chunk size of 10.

If the binary operator or projection handed to fold are async functions, then they will be invoked asynchronously, this allows you to launch further tasks recursively.

Unlike the std::ranges::fold variations, this function will make an implementation defined number of copies of the function objects and may invoke these copies concurrently.

Generalized prefix sums with scan#

constexpr impl::scan_overload lf::scan = {}#

A parallel implementation of std::inclusive_scan that accepts generalized ranges and projections.

Effective call signature:

template <std::random_access_iterator I,
          std::sized_sentinel_for<I> S,
          std::random_access_iterator O,
          class Proj = std::identity,
          indirectly_scannable<O, projected<I, Proj>> Bop
          >
void scan(I beg, S end, O out, std::iter_difference_t<I> n, Bop bop, Proj proj = {});

Overloads exist for a random-access range (instead of head and tail), in place scans (omit the out iterator) and, the chunk size, n, can be omitted (which will set n = 1).

Exemplary usage:

co_await just[scan](in, out.begin(), std::plus<>{});

This computes the cumulative sum of the input and stores it in the output-range e.g. [1, 2, 2, 1] -> [1, 3, 5, 6].

The input and output ranges must either be distinct (i.e. non-overlapping) or the same range.

If the binary operator or projection handed to scan are async functions, then they will be invoked asynchronously, this allows you to launch further tasks recursively.

Unlike the std:: variations, this function will make an implementation defined number of copies of the function objects and may invoke these copies concurrently.