P1645R0
constexpr for <numeric> algorithms

Draft Proposal,

This version:
https://elbeno.github.io/isocpp/constexpr-numeric/constexpr-numeric.html
Author:
Ben Deane (ben at elbeno dot com)
Audience:
LEWG, LWG
Project:
ISO/IEC JTC1/SC22/WG21 14882: Programming Language — C++

Abstract

We have made many algorithms constexpr for C++20, but we seem to have overlooked the algorithms in <numeric>.

1. Motivation

We have added constexpr to many parts of the standard library for C++20.

Notably, [P0879] Constexpr for swap and swap-related functions added constexpr to all functions in <algorithm> except shuffle, sample, stable_sort, stable_partition, inplace_merge, and functions accepting an ExecutionPolicy.

I believe LEWG’s design intent is that the non-allocating, non-parallel algorithms be constexpr. However, there are algorithms in <numeric> that have been overlooked.

2. Assumptions

[P0879] made the following assumptions:

This proposal could make the same assumptions about implementation; however with the advent of std::is_constant_evaluated for distinguishing compile-time and runtime code, perhaps these assumptions are no longer necessary.

3. Algorithms in <numeric> that were apparently overlooked

This proposal is to add constexpr to the following function templates in <numeric>, excepting the function templates that accept an ExecutionPolicy.

4. Feature testing macro

I propose the feature-testing macro __cpp_lib_constexpr_numeric_algorithms to identify the presence of these constexpr forms.

5. Proposed wording relative to N4810

Exactly as one would expect: add constexpr to the function templates listed above where they do not accept an ExecutionPolicy.

template<class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template<class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
template<class InputIterator>
  constexpr typename iterator_traits::value_type
    reduce(InputIterator first, InputIterator last);
template<class InputIterator, class T>
  constexpr T reduce(InputIterator first, InputIterator last, T init);
template<class InputIterator, class T, class BinaryOperation>
  constexpr T reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
template<class InputIterator1, class InputIterator2, class T>
  constexpr T inner_product(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, T init);
template<class InputIterator1, class InputIterator2, class T,
         class BinaryOperation1, class BinaryOperation2>
  constexpr T inner_product(InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, T init,
                            BinaryOperation1 binary_op1,
                            BinaryOperation2 binary_op2);
template<class InputIterator1, class InputIterator2, class T>
  constexpr T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2,
                               T init);
template<class InputIterator1, class InputIterator2, class T,
         class BinaryOperation1, class BinaryOperation2>
  constexpr T transform_reduce(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2,
                               T init,
                               BinaryOperation1 binary_op1,
                               BinaryOperation2 binary_op2);
template<class InputIterator, class T,
         class BinaryOperation, class UnaryOperation>
  constexpr T transform_reduce(InputIterator first, InputIterator last,
                               T init,
                               BinaryOperation binary_op, UnaryOperation unary_op);
template<class InputIterator, class OutputIterator>
  constexpr OutputIterator partial_sum(InputIterator first,
                                       InputIterator last,
                                       OutputIterator result);
template<class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator partial_sum(InputIterator first,
                                       InputIterator last,
                                       OutputIterator result,
                                       BinaryOperation binary_op);
template<class InputIterator, class OutputIterator, class T>
  constexpr OutputIterator exclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          T init);
template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
  constexpr OutputIterator exclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          T init, BinaryOperation binary_op);
template<class InputIterator, class OutputIterator>
  constexpr OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result);
template<class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          BinaryOperation binary_op);
template<class InputIterator, class OutputIterator, class BinaryOperation, class T>
  constexpr OutputIterator inclusive_scan(InputIterator first, InputIterator last,
                                          OutputIterator result,
                                          BinaryOperation binary_op, T init);
template<class InputIterator, class OutputIterator, class T,
         class BinaryOperation, class UnaryOperation>
  constexpr OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last,
                                                    OutputIterator result,
                                                    T init,
                                                    BinaryOperation binary_op,
                                                    UnaryOperation unary_op);
template<class InputIterator, class OutputIterator,
         class BinaryOperation, class UnaryOperation>
  constexpr OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
                                                    OutputIterator result,
                                                    BinaryOperation binary_op,
                                                    UnaryOperation unary_op);
template<class InputIterator, class OutputIterator,
         class BinaryOperation, class UnaryOperation, class T>
  constexpr OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last,
                                                    OutputIterator result,
                                                    BinaryOperation binary_op,
                                                    UnaryOperation unary_op,
                                                    T init);
template<class InputIterator, class OutputIterator>
  constexpr OutputIterator adjacent_difference(InputIterator first,
                                               InputIterator last,
                                               OutputIterator result);
template<class InputIterator, class OutputIterator, class BinaryOperation>
  constexpr OutputIterator adjacent_difference(InputIterator first,
                                               InputIterator last,
                                               OutputIterator result,
                                               BinaryOperation binary_op);
template<class ForwardIterator, class T>
  constexpr void iota(ForwardIterator first, ForwardIterator last, T value);

The feature-testing macro should also be updated.

__cpp_lib_constexpr_numeric_algorithms [TBD] <numeric>

6. Thanks

Thanks to Jan Wilmans, Joe Loser and Casey Carter.

References

Informative References

[P0879]
Antony Polukhin. Constexpr for swap and swap related functions. 2017-12-29. URL: https://wg21.link/P0879