Add Constexpr Modifiers to Functions in and Headers

Significant changes to P0202R2 are marked with blue.

Show deleted lines.

I. Introduction and Motivation

The Standard Library provides a great collection of algorithms, many of which currently lack constexpr support. Even a simple constexpr usage requires reimplementing a big bunch of the Standard Library. Consider the simple example:

#include 
#include 
 
int main() {
	// OK
	constexpr std::array a { 'H', 'e', 'l', 'l', 'o' };

	// Failures:
	// * std::find is not constexpr
	constexpr auto it = std::find(a.rbegin(), a.rend(), 'H');
}

This proposal concentrates on constexpr algorithms, deferring simple containers and iterators to a separate proposal.

A proof of concept implementation for some algorithms, is available at: rhalbersma and Boost.Algorithm.

II. Impact on the Standard

This proposal is a pure library extension. It proposes changes to existing headers and such that the changes do not break existing code and do not degrade performance. It does not require any changes in the core language in simple cases of non assembly optimized Standard Library, and it could be implemented in standard C++.

Depending on the Standard Library implementation this proposal may rely on P0031R0. P0031R0 was adopted. P0031R0 provides constexpr additions to std::advance, std::distance, std::move_iterator and other functions and classes. Those may be used by some implementations of header.

III. Design Decisions

A. must not have `constexpr` additions

Existing implementations of the functions in header usually rely on functions from . For example std::copy usually takes advantage of std::memmove for POD types. During the Jacksonville meeting it was decided not to modify the headers, leading to a decision to use compiler specific intrinsics instead of functions from header.

B. Assumption that it is possible to implement all the proposed changes without affecting language core, especially [expr.const]

There are many Standard Library implementations nowadays, including some proprietary. It is impossible to investigate all of them to be 100% sure that no performance degradation possible.

This proposal assumes that:

If algorithm uses compiler intrinsics, then those intrinsics could be made constexpr by compiler vendors.
If algorithm uses assembly optimization, then that assembly could be turned into constexpr compiler intrinsic.
If algorithm uses external functions, then those functions could be made inline and marked constexpr or could be replaced with intrinsics.
Modern compilers are good in code optimization, so a decently small amount of algorithms use assembly or intrinsics.

C. Analysis of existing implementations.

libstdc++ and libc++ implement differently. libc++ uses some functions from header, libstdc++ uses compiler specific intrinsics:

libstdc++	libc++	Some of the Algorithms
__builtin_memmove	std::memmove	copy, sort, partition, copy_backward
__builtin_memset	std::memset	fill, fill_n
__builtin_memcmp		equal, lexicographical_compare

GCC's intrinsic __builtin_memcmp is already usable in constant expressions; intrinsics __builtin_memmove, __builtin_memset could be probably easily tuned to be usable in constant expressions. libc++ will probably have to follow the GCC steps and use intrinsics for std::memmove, std::memset or just remove their usage and rely on compiler's optimizations.

Algorithms stable_partition, inplace_merge and stable_sort allocate memory, construct variables using placement new, use unique_ptr and do other things not acceptable in constexpr expressions. Making those algorithms constexpr seems to be a hard task that would require a lot of intrinsics. Those algorithms are not marked with constexpr in this wording.

Algorithms shuffle and sample rely upon uniform_int_distribution that has no constexpr functions. Those algorithms are not marked with constexpr in this wording.

libc++ uses goto in some algorithms, this must be pretty simple to fix without affecting performance.

D. Do not mark `ExecutionPolicy&&` overloads with `constexpr`.

It seems that N4687 accidentaly marks some of the ExecutionPolicy&& overloads with constexpr execution policy. This wording does not mark the ExecutionPolicy&& overloads with constexpr.

E. Do not mark functions that use `std::swap` with `constexpr`.

During the LWG discussion it was noted that Core Issue 1581 affects is_swappable and swap. This paper avoids marking with constexpr the swap function and all the algorithms that have ValueSwappable requirement(20.5.3.2) are also not marked.

Adding constexpr to algorithms that use swap, numeric algorithms, searchers, some of the functions in char_traits and functions that relay on constexpr algorithms (like std::arrays comparison operators) will be covered in separate papers.

IV. Proposed wording relative to N4594

All the additions to the Standard are marked with underlined green.

A. Modifications to "Header synopsis" [algorithms.general]

Note for editor: All the functions in [algorithms.general] must be marked with constexpr, except functions shuffle, sample, stable_sort, stable_partition, inplace_merge, functions accepting ExecutionPolicy and algorithms that have ValueSwappable requirement(20.5.3.2):

swap_ranges
iter_swap
reverse
rotate
shuffle
sort
stable_sort
partial_sort
partial_sort_copy
nth_element
partition
stable_partition
inplace_merge
push_heap
pop_heap
make_heap
sort_heap
next_permutation
prev_permutation

#include 

namespace std {

// 28.5, non-modifying sequence operations:
// 28.5.1, all of
template 
constexpr bool all_of(InputIterator first, InputIterator last, Predicate pred);

template 
bool all_of(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Predicate pred);

// 28.5.2, any of
template 
constexpr bool any_of(InputIterator first, InputIterator last, Predicate pred);

template 
bool any_of(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Predicate pred);

// 28.5.3, none of
template 
constexpr bool none_of(InputIterator first, InputIterator last, Predicate pred);

template 
bool none_of(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Predicate pred);

// 28.5.4, for each
template 
constexpr Function for_each(InputIterator first, InputIterator last, Function f);

template 
void for_each(ExecutionPolicy&& exec,
    ForwardIterator first, ForwardIterator last, Function f);

template 
constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);

template 
ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n, Function f);

// 28.5.5, find
template
constexpr InputIterator find(InputIterator first, InputIterator last, const T& value);

template 
ForwardIterator find(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    const T& value);

template 
constexpr InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

template 
ForwardIterator find_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Predicate pred);

template 
constexpr InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred);

template 
ForwardIterator find_if_not(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Predicate pred);

// 28.5.6, find end
template
constexpr ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

template
constexpr ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template 
ForwardIterator1 find_end(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template 
ForwardIterator1 find_end(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);

// 28.5.7, find first
template
constexpr InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2);

template
constexpr InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);

template
ForwardIterator1 find_first_of(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template
ForwardIterator find_first_of(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);

// 28.5.8, adjacent find
template
constexpr ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template
constexpr ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

template
ForwardIterator adjacent_find(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first,
    ForwardIterator last);

template
ForwardIterator adjacent_find(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first,
    ForwardIterator last,
    BinaryPredicate pred);

// 28.5.9, count
template
constexpr typename iterator_traits::difference_type count(InputIterator first, InputIterator last, const T& value);

template
typename iterator_traits::difference_type count(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr typename iterator_traits::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);

template
typename iterator_traits::difference_type count_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Predicate pred);

// 28.5.10, mismatch
template
constexpr pair
    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template 
constexpr pair
    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);

template
constexpr pair
    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template 
constexpr pair
    mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred);

template 
pair 
mismatch(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2);

template 
pair 
mismatch(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, BinaryPredicate pred);

template 
pair 
mismatch(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template 
pair 
mismatch(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);

// 28.5.11, equal
template
constexpr bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template 
constexpr bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);

template
constexpr bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template 
constexpr bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred);

template
bool equal(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2);

template
bool equal(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, BinaryPredicate pred);

template
bool equal(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template
bool equal(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);

// 28.5.12, is permutation
template
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

template
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred);

template
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

template
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

// 28.5.13, search
template
constexpr ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

template
constexpr ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template
ForwardIterator1 search(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template
ForwardIterator1 search(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    BinaryPredicate pred);


template
constexpr ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);

template 
constexpr ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred);

template
ForwardIterator search_n(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Size count, const T& value);

template
ForwardIterator search_n(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Size count, const T& value,
    BinaryPredicate pred);

template 
constexpr ForwardIterator search(ForwardIterator first, ForwardIterator last,
    const Searcher &searcher);

// 28.6, modifying sequence operations:
// 28.6.1, copy:
template
constexpr OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

template
ForwardIterator2 copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result);

template
constexpr OutputIterator copy_n(InputIterator first, Size n, OutputIterator result);

template
ForwardIterator2 copy_n(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, Size n,
    ForwardIterator2 result);

template
constexpr OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

template
ForwardIterator2 copy_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result, Predicate pred);

template
constexpr BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);

// 28.6.2, move
template
constexpr OutputIterator move(InputIterator first, InputIterator last, OutputIterator result);

template
ForwardIterator2 move(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result);

template
constexpr BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);

// 28.6.3, swap
template
constexpr ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

template
ForwardIterator2 swap_ranges(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2);

template
constexpr void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

// 28.6.4, transform
template
constexpr OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);

template
constexpr OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

template
ForwardIterator2 transform(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result, UnaryOperation op);

template
ForwardIterator transform(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator result,
    BinaryOperation binary_op);

// 28.6.5, replace
template
constexpr void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

template
void replace(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    const T& old_value, const T& new_value);

template
constexpr void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

template
void replace_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Predicate pred, const T& new_value);

template
constexpr OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

template
ForwardIterator2 replace_copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result,
    const T& old_value, const T& new_value);

template
constexpr OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

template
ForwardIterator2 replace_copy_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result,
    Predicate pred, const T& new_value);

// 28.6.6, fill
template
constexpr void fill(ForwardIterator first, ForwardIterator last, const T& value);

template
void fill(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr OutputIterator fill_n(OutputIterator first, Size n, const T& value);

template
ForwardIterator fill_n(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, Size n, const T& value);

// 28.6.7, generate
template
constexpr void generate(ForwardIterator first, ForwardIterator last, Generator gen);

template
void generate(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Generator gen);

template
constexpr OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

template
ForwardIterator generate_n(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, Size n, Generator gen);

// 28.6.8, remove
template
constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

template
ForwardIterator remove(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    const T& value);

template
constexpr ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

template
ForwardIterator remove_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Predicate pred);

template
constexpr OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

template
ForwardIterator2 remove_copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result, const T& value);

template
constexpr OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

template
ForwardIterator2 remove_copy_if(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result, Predicate pred);

// 28.6.9, unique
template
constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template
constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

template
ForwardIterator unique(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
ForwardIterator unique(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    BinaryPredicate pred);

template
constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);

template
constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);

template
ForwardIterator2 unique_copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result);

template
ForwardIterator2 unique_copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first, ForwardIterator1 last,
    ForwardIterator2 result, BinaryPredicate pred);

// 28.6.10, reverse
template
constexpr void reverse(BidirectionalIterator first, BidirectionalIterator last);

template
void reverse(ExecutionPolicy&& exec, // see 28.4.5
    BidirectionalIterator first, BidirectionalIterator last);

template
constexpr OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

template
ForwardIterator reverse_copy(ExecutionPolicy&& exec, // see 28.4.5
    BidirectionalIterator first,
    BidirectionalIterator last,
    ForwardIterator result);

// 28.6.11, rotate
template
constexpr ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

template
ForwardIterator rotate(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first,
    ForwardIterator middle,
    ForwardIterator last);

template
constexpr OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

template
ForwardIterator rotate_copy(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator middle,
    ForwardIterator last, ForwardIterator result);

// 28.6.12, sample
template
SampleIterator sample(PopulationIterator first, PopulationIterator last,
    SampleIterator out, Distance n,
    UniformRandomNumberGenerator&& g);

// 28.6.13, shuffle
template
void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g);


// 28.7.4, partitions
template 
constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);

template 
bool is_partitioned(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Predicate pred);

template
constexpr ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);

template
ForwardIterator partition(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first,
    ForwardIterator last,
    Predicate pred);

template
BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

template
BidirectionalIterator stable_partition(ExecutionPolicy&& exec, // see 28.4.5
    BidirectionalIterator first,
    BidirectionalIterator last,
    Predicate pred);

template 
constexpr pair
    partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);

template 
pair
partition_copy(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    ForwardIterator1 out_true, ForwardIterator2 out_false,
    Predicate pred);

template
constexpr ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

// 28.7, sorting and related operations
// 28.7.1, sorting
template
constexpr void sort(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
void sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last);

template
void sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last,
    Compare comp);

template
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
void stable_sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last);

template
void stable_sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last,
    Compare comp);

template
constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template
constexpr void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

template
void partial_sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last);

template
void partial_sort(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last, Compare comp);

template
constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

template
constexpr RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

template
RandomAccessIterator partial_sort_copy(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    RandomAccessIterator result_first,
    RandomAccessIterator result_last);

template
RandomAccessIterator partial_sort_copy(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    RandomAccessIterator result_first,
    RandomAccessIterator result_last,
    Compare comp);

template
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);

template
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

template
bool is_sorted(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
bool is_sorted(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Compare comp);

template
constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);

template
constexpr ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);

template
ForwardIterator is_sorted_until(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
ForwardIterator is_sorted_until(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Compare comp);

// 28.7.2, Nth element
template
constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template
constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

template
void nth_element(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator nth,
    RandomAccessIterator last);

template
void nth_element(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator nth,
    RandomAccessIterator last, Compare comp);

// 28.7.3, binary search
template
constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template
constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template
constexpr pair
    equal_range(ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr pair
    equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template
constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

template
constexpr bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

// 28.7.5, merge
template
constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template
constexpr OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template
ForwardIterator merge(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result);

template
ForwardIterator merge(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result, Compare comp);

template
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

template
void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

template
void inplace_merge(ExecutionPolicy&& exec, // see 28.4.5
    BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last);

template
void inplace_merge(ExecutionPolicy&& exec, // see 28.4.5
    BidirectionalIterator first,
    BidirectionalIterator middle,
    BidirectionalIterator last, Compare comp);

// 28.7.6, set operations
template
constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template
constexpr bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

template
bool includes(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);
template
bool includes(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2, Compare comp);

template
constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template
constexpr OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template
ForwardIterator set_union(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result);

template
ForwardIterator set_union(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result, Compare comp);

template
constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template
constexpr OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template
ForwardIterator set_intersection(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result);

template
OutputIterator set_intersection(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result, Compare comp);

template
constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template
constexpr OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template
ForwardIterator set_difference(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result);

template
ForwardIterator set_difference(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result, Compare comp);

template
constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template
constexpr OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template
ForwardIterator set_symmetric_difference(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result);

template
ForwardIterator set_symmetric_difference(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    ForwardIterator result, Compare comp);

// 28.7.7, heap operations
template
constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
bool is_heap(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last);

template
bool is_heap(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
constexpr RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);

template
constexpr RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last);

template
RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, // see 28.4.5
    RandomAccessIterator first, RandomAccessIterator last,
    Compare comp);

// 28.7.8, minimum and maximum
template constexpr const T& min(const T& a, const T& b);

template
constexpr const T& min(const T& a, const T& b, Compare comp);

template
constexpr T min(initializer_list t);

template
constexpr T min(initializer_list t, Compare comp);

template constexpr const T& max(const T& a, const T& b);

template
constexpr const T& max(const T& a, const T& b, Compare comp);

template
constexpr T max(initializer_list t);

template
constexpr T max(initializer_list t, Compare comp);

template constexpr pair minmax(const T& a, const T& b);

template
constexpr pair minmax(const T& a, const T& b, Compare comp);

template
constexpr pair minmax(initializer_list t);

template
constexpr pair minmax(initializer_list t, Compare comp);

template
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last)

template
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

template
constexpr ForwardIterator min_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
constexpr ForwardIterator min_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Compare comp);

template
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last)

template
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

template
constexpr ForwardIterator max_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
constexpr ForwardIterator max_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last,
    Compare comp);

template
constexpr pair
    minmax_element(ForwardIterator first, ForwardIterator last);

template
constexpr pair
    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);

template
constexpr pair minmax_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last);

template
constexpr pair minmax_element(ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator first, ForwardIterator last, Compare comp);

// 28.7.9, bounded value
template
constexpr const T& clamp(const T& v, const T& lo, const T& hi);

template
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);

// 28.7.10, lexicographical comparison
template
constexpr bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template
constexpr bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

template
bool lexicographical_compare(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2);

template
bool lexicographical_compare(
    ExecutionPolicy&& exec, // see 28.4.5
    ForwardIterator1 first1, ForwardIterator1 last1,
    ForwardIterator2 first2, ForwardIterator2 last2,
    Compare comp);

// 28.7.11, permutations
template
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

template
constexpr bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template
constexpr bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

}

B. Modifications to remaining parts of "28 Algorithms library" [algorithms] (all sections except "Header synopsis" and "28.8 C library algorithms" [alg.c.library])

Note for editor: All the functions marked with constexpr in previous paragraph of this document must be accordingly marked with constexpr in detailed algorithm description. For shortness only modifications to "28.5.1 All of" [alg.all_of] are shown in this paper.

28.5.1 All of [alg.all_of]

template 
constexpr bool all_of(InputIterator first, InputIterator last, Predicate pred);

template 
bool all_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
    Predicate pred);

Returns: true if [first,last) is empty or if pred(*i) is true for every iterator i in the range
    [first,last), and false otherwise.

Complexity: At most last - first applications of the predicate.

C. Modifications to "23.2 Utility components" [utility]

// 23.2.3, swap:
template
constexpr void swap(T& a, T& b) noexcept(see below );

template 
constexpr void swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b)));

// 23.2.4, exchange:
template 
constexpr T exchange(T& obj, U&& new_val);

D. Modifications to "23.2.3 swap" [utility.swap]

template constexpr void swap(T& a, T& b) noexcept(see below );

Remark: This function shall not participate in overload resolution unless is_move_constructible_v
is true and is_move_assignable_v is true. The expression inside noexcept is equivalent to:
    is_nothrow_move_constructible_v && is_nothrow_move_assignable_v

Requires: Type T shall be MoveConstructible (Table 20) and MoveAssignable (Table 22).
Effects: Exchanges values stored in two locations.

template
constexpr void swap(T (&a)[N], T (&b)[N]) noexcept(is_nothrow_swappable_v);

Remarks: This function shall not participate in overload resolution unless is_swappable_v is true.

Requires: a[i] shall be swappable with (20.5.3.2) b[i] for all i in the range [0,N).
Effects: As if by swap_ranges(a, a + N, b).

D. Modifications to "23.2.4 exchange" [utility.exchange]

template  constexpr T exchange(T& obj, U&& new_val);

Effects: Equivalent to:
    T old_val = std::move(obj);
    obj = std::forward(new_val);
    return old_val;

F. Feature-testing macro

For the purposes of SG10, we recommend the feature-testing macro name __cpp_lib_constexpr_algorithms.

V. Revision History

Revision 3:

Do not add constexpr to functions that use swap.

Revision 2:

Do not add constexpr to the ExecutionPolicy overloads.
Updated wording to use N4687.

Revision 1:

Dropped all the modifications for the header.
Dropped constexpr for stable_sort, stable_partition, inplace_merge, shuffle and sample.
Updated wording to use N4582.
Applied constexpr to the ExecutionPolicy overloads and algorithms added since N4567.

Oulu voting:

Should some part of this target C++17?
SF F N A SA
3  3 3 3 1 

Should the non-parallel parts be forwarded for C++Next?
SF F N A SA
6  7 0 0 0

Revision 0:

Initial proposal

Jacksonville voting:

Approve of adding constexpr to the algorithms?
SF F N A SA
9  4 3 0 0

Approve of adding constexpr to algorithms that need some compiler intrinsics, pending some compiler vendors approving?
SF F N A SA
2  8 5 1 0

Resolution: needs_updated_proposal

VI. References

[N4687] Working Draft, Standard for Programming Language C++. Available online at www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4687.pdf

[P0031R0] A Proposal to Add Constexpr Modifiers to reverse_iterator, move_iterator, array and Range Access. Available online at www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0031r0.html

[rhalbersma ] Proof of concept for some functions. Available online at https://bitbucket.org/rhalbersma/xstd/src/42553df6107623c71163f104b6f3cc550c245b4b/include/xstd/algorithm.hpp and https://bitbucket.org/rhalbersma/xstd/src/42553df6107623c71163f104b6f3cc550c245b4b/include/xstd/utility.hpp

[Boost.Algorithm] Constexpr modifiers for Boost Algorithm library. Available online at https://github.com/boostorg/algorithm/pull/13

[Discussion] A call to discuss asm in constexpr and constexpr . Available online at https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/9sTJWsOpptE

[P0202R0] Add Constexpr Modifiers to Functions in and Headers. Available online at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0202r0.html

VII. Acknowledgements

Walter E. Brown provided numerous comments, corrections, and suggestions for this proposal.