Document #: | P3179R5 [Latest] [Status] |
Date: | 2025-01-13 |
Project: | Programming Language C++ |
Audience: |
LEWG |
Reply-to: |
Ruslan Arutyunyan <ruslan.arutyunyan@intel.com> Alexey Kukanov <alexey.kukanov@intel.com> Bryce Adelstein Lelbach (he/him/his) <brycelelbach@gmail.com> |
random_access_iterator
or
random_access_range
constexpr
parallel range algorithms__cpp_lib_parallel_algorithm
macro
in [version.syn]all_of
in
[alg.all.of]any_of
in
[alg.any.of]none_of
in
[alg.none.of]contains
in
[alg.contains]for_each
in
[alg.foreach]find
in
[alg.find]find_last
in
[alg.find.last]find_end
in
[alg.find.end]find_first_of
in
[alg.find.first.of]adjacent_find
in
[alg.adjacent.find]count
in
[alg.count]mismatch
in
[alg.mismatch]equal
in
[alg.equal]search
in
[alg.search]starts_with
in
[alg.starts.with]ends_with
in
[alg.ends.with]copy
in
[alg.copy]move
in
[alg.move]swap_ranges
in
[alg.swap]transform
in
[alg.transform]replace
in
[alg.replace]fill
in
[alg.fill]generate
in
[alg.generate]remove
in
[alg.remove]unique
in
[alg.unique]reverse
in
[alg.reverse]rotate
in
[alg.rotate]shift
in
[alg.shift]sort
in
[sort]stable_sort
in
[stable.sort]partial_sort
in
[partial.sort]partial_sort_copy
in
[partial.sort.copy]is_sorted
in
[is.sorted]nth_element
in
[alg.nth.element]partitions
in
[alg.partitions]merge
in
[alg.merge]includes
in
[includes]set_union
in
[set.union]set_intersection
in
[set.intersection]set_difference
in
[set.difference]set_symmetric_difference
in
[set.symmetric.difference]is_heap
in
[is.heap]min
,
max
,
minmax
in
[alg.min.max]lexicographical_compare
in
[alg.lex.comparison]This paper proposes adding parallel algorithms that work together with the C++ Ranges library.
Standard parallel algorithms with execution policies which set semantic requirements to user-provided callable objects were a good start for supporting parallelism in the C++ standard.
The C++ Ranges library - ranges, views, etc. - is a powerful facility to produce lazily evaluated pipelines that can be processed by range-based algorithms. Together they provide a productive and expressive API with the room for extra optimizations.
Combining these two powerful features by adding support for execution policies to the range-based algorithms opens an opportunity to fuse several computations into one parallel algorithm call, thus reducing the overhead on parallelism. That is especially valuable for heterogeneous implementations of parallel algorithms, for which the range-based API helps reducing the number of kernels submitted to an accelerator.
Users are already using ranges and range adaptors by passing range iterators to the existing non-range parallel algorithms. [P2408R5] was adopted to enable this. This pattern is often featured when teaching C++ parallel algorithms and appears in many codebases.
iota
and
cartesian_product
are especially
common, as many compute workloads want to iterate over indices, not
objects, and many work with multidimensional data.
transform
is also common, as it
enables fusion of element-wise operations into a single parallel
algorithm call, which can avoid the need for temporary storage and is
more performant than two separate calls.
However, passing range iterators to non-range algorithms is unwieldy and verbose. It is surprising to users that they cannot simply pass the ranges to the parallel algorithms as they would for serial algorithms.
Before
|
After
|
---|---|
|
|
Before
|
After
|
---|---|
|
|
Earlier, [P2500R2] proposed to add the range-based C++ parallel algorithms together with its primary goal of extending algorithms with schedulers. We have decided to split those parts to separate papers, which could progress independently.
This paper proposes execution policy support for C++ range-based algorithms. In the nutshell, the proposal extends C++ range algorithms with overloads taking any standard or implementation defined C++ execution policy as a function parameter. These overloads are further referred to as parallel range algorithms.
The proposal is targeted to C++26.
Comparing to the C++20 serial range algorithms, we propose the following modifications:
for_each
and
for_each_n
return only an iterator
but not the function. See Algorithm return
types.random_access_{iterator,range}
.
See Requiring
random_access_iterator or random_access_range.In addition to data sequences being passed as either ranges or “iterator and sentinel” pairs, the following differences to the C++17 parallel algorithms are proposed:
for_each
returns an iterator,
not
void
.random_access_{iterator,range}
,
and not LegacyForwardIterator.std::ranges
.
See Extending the overload sets of
algorithm function objects.regular_invocable
where possible. See Requirements for
callable parameters.constexpr
support. See constexpr parallel range
algorithms.The proposed API will look like the following (using
transform
as an example):
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
<O> OutS,
random_access_iterator O, sized_sentinel_forclass Proj = identity>
copy_constructible F, requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
::unary_transform_result<I, O>
ranges::transform(Ep&& exec, I first, S last, O result, OutS result_last,
ranges= {});
F op, Proj proj
template<execution-policy Ep, ranges::random-access-sized-range R, ranges::random-access-sized-range OutR,
class Proj = identity>
copy_constructible F, requires indirectly_writable<ranges::iterator_t<OutR>, indirect_result_t<F&, projected<ranges::iterator_t<R>, Proj>>>
::unary_transform_result<ranges::borrowed_iterator_t<R>, ranges::borrowed_iterator_t<OutR>>
ranges::transform(Ep&& exec, R&& r, OutR&& result, F op, Proj proj = {}); ranges
The used exposition-only concepts are described below.
We believe that adding parallel range algorithms does not have the risk of conflict with anticipated scheduler-based algorithms, because an execution policy does not satisfy the requirements for a policy-aware scheduler [P2500R2], a sender [P3300R0], or really anything else from [P2300R10] that can be used to specify such algorithms.
At this point we do not, however, discuss how the appearance of schedulers may or should impact the execution rules for parallel algorithms specified in [algorithms.parallel.exec], and just assume that the same rules apply to the range algorithms with execution policies.
Parallel range algorithms should operate with the same set of
execution policies as the existing parallel algorithms, that is,
seq
,
unseq
,
par
, and
par_unseq
in the std::execution
namespace, as well as any implementation-defined execution policies.
The following exposition-only concept simplifies constraining the algorithms with proper execution policy types:
template<class Ep>
concept execution-policy = // exposition only
<remove_cvref_t<Ep>>; is_execution_policy_v
We do not propose the parallel range algorithms to be customizable for application-defined execution policies. We expect such custom policies to become unnecessary once the standard algorithms are capable of working with schedulers/senders/receivers.
We explored possible algorithm return types and came to conclusion that returning the same type as serial range algorithms is the preferred option to make the changes for enabling parallelism minimal.
auto res = std::ranges::sort(v);
becomes:
auto res = std::ranges::sort(std::execution::par, v);
However, std::ranges::for_each
and std::ranges::for_each_n
require special consideration because previous design decisions suggest
that there should be a difference between serial and parallel
versions.
The following table summarizes return value types for the existing variants of these two algorithms:
API
|
Return type
|
---|---|
std::for_each |
Function |
Parallel std::for_each |
void |
std::for_each_n |
Iterator |
Parallel std::for_each_n |
Iterator |
std::ranges::for_each |
for_each_result<ranges::borrowed_iterator_t<Range>, Function> |
std::ranges::for_each ,
I +
S overload |
for_each_result<Iterator, Function> |
std::ranges::for_each_n |
for_each_n_result<Iterator, Function> |
While the serial std::for_each
returns the obtained function object with all modifications it might
have accumulated, the return type for the parallel std::for_each
is
void
because, as stated in the standard, “parallelization often does not
permit efficient state accumulation”. For efficient parallelism an
implementation can make multiple copies of the function object, which
for that purpose is allowed to be copyable and not just movable like for
the serial for_each
. That implies
that users cannot rely on any state accumulation within that function
object, so it does not make sense (and might be even dangerous) to
return it.
In
std::ranges
,
the return type of for_each
and
for_each_n
is unified to return both
an iterator and the function object.
Based on the analysis above and the
feedback from SG9 we think that the most reasonable return type for
parallel variants of std::ranges::for_each
and std::ranges::for_each_n
should be:
API
|
Return type
|
---|---|
Parallel std::ranges::for_each |
ranges::borrowed_iterator_t<Range> |
Parallel std::ranges::for_each ,
I +
S overload |
Iterator |
Parallel std::ranges::for_each_n |
Iterator |
We believe the proposed functionality should have the same properties and general behavior as serial range algorithms, particularly regarding the name lookup.
With the adoption of [P3136R0], function templates in the
std::ranges
namespace have been respecified as algorithm function objects.
These objects are defined as sets of one or more overloaded function
templates, which names designate the objects.
The parallel range algorithms we propose will extend the overload sets for the respective algorithm function objects. The name lookup rules for such objects will apply automatically. It is covered by the wording proposed in [P3136R0]; additional changes are not needed.
From the implementation standpoint, adding parallel versions of the range algorithms to the overload set should not be a problem. Please see Possible implementation of a parallel range algorithm for more information.
random_access_iterator
or
random_access_range
C++17 parallel algorithms minimally require LegacyForwardIterator for data sequences, but in our opinion, it is not quite suitable for an efficient parallel implementation. Therefore for parallel range algorithms we propose to require random access ranges and iterators.
Using parallel algorithms with forward ranges will in most cases give little to no benefit, and may even reduce performance due to extra overheads. We believe that forward ranges and iterators are bad abstractions for parallel data processing, and allowing those could result in wrong expectations and unsatisfactory user experience with parallel algorithms.
Many parallel programming models that are well known and widely used in the industry, including OpenMP, OpenCL, CUDA, SYCL, oneTBB, define iteration or data spaces for their parallel constructs in ways that allow creating sufficient parallel work quickly and efficiently. A key property for this is the ability to split the work into smaller chunks. These programming models allow to control the amount of work per chunk and sometimes the ways chunks are created and/or scheduled. All these also support iteration spaces up to at least 3 dimensions.
Except for tbb::parallel_for_each
in oneTBB which can work with forward iterators, these parallel
programming models require random access iterators or some equivalent,
such as numeric indexes or pointers. This is natural, as referring to an
arbitrary point in the iteration space at constant time is the main and
by far simplest way to create parallel work. Forward iterators, on the
other hand, are notoriously bad for splitting a sequence that can only
be done in linear time. Moreover, if the output of an algorithm should
preserve the order of its input, which is typical for the C++
algorithms, it requires additional synchronization or/and additional
space with forward iterators and comes almost for granted with random
access ones.
These very programming models are often used as backends to implement
the C++ standard parallelism. Not surprisingly, most implementations
fall back to serial processing if data sequences have no random access.
Of the GNU libstdc++, LLVM libc++, and MSVC’s standard library, only the
latter attempts to process forward iterator based sequences in parallel,
for which it first needs to serially iterate over a whole sequence once
or even twice. oneAPI DPC++ library (oneDPL) supports forward iterators
only for a very few algorithms, only for
par
and only in the implementation
based on oneTBB.
According to the SG1/SG9 feedback we have got earlier, there seemingly are two main reasons why others do not want to restrict parallel algorithms by only random access ranges:
filter_view
, from being used with
parallel range algorithms.Given the other aspects of the proposed design, we believe some degree of inconsistency with C++17 parallel algorithms is inevitable and should not become a gating factor for important design decisions.
The question of supporting the standard views that do not provide
random access is very important. We think though that it should better
be addressed through proper abstractions and new concepts defining
iteration spaces, including multidimensional ones, suitable for parallel
algorithms. We intend to work on developing these (likely in another
paper), however it requires time and effort to make it right, and we
think trying to squeeze that into C++26 adds significant risks. For now,
random access ranges with known bounds (see Requiring ranges to be bounded) is
probably the best approximation that exists in the standard. Starting
from that and gradually enabling other types of iteration spaces in a
source-compatible manner seems to us better than blanket allowance of
any forward_range
.
We propose taking a range as the output for the overloads that take ranges for input. Similarly, we propose requiring a sentinel for the output where the input is passed as “iterator and sentinel”.
The benefits of this range-as-the-output approach, comparing to taking a single iterator for the output, are:
sized_range
and
sized_sentinel_for
concepts will be
applied to the output sequences in the same way as to the input
sequences.copy_if
(and similar
algorithms with filtering semantics), where the output sequence
might be shorter than the input one. Knowing the expected size of the
output may open opportunities for more efficient implementations.On the joint SG1 and SG9 discussion of [P3179R2] the audience expressed several concerns about the idea and requested to stay with iterators for the output until deeper investigation is made.
To address the concerns, we wrote a separate paper [P3490R0] with the detailed investigation of the topic, suggesting there a compromise solution with adding separate function template overloads for both iterator-as-the-output and range-as-the-output. See [P3490R0] for more details.
Eventually SG9 accepted our original proposal to use ranges for the output, without extra overloads for legacy convenience.
One of the requirements we want to put on the parallel range algorithms is to disallow unbounded input and output. The reasons for that are:
std::ranges::views::iota(0)
,
it may result in an endless loop. It’s hard to imagine usefulness of
that in the case of parallel execution. Requiring data sequences to be
bounded potentially prevents errors at run-time.If several provided ranges or sequences are bounded, an algorithm
should stop as soon as the end is reached for the shortest one. There
are already precedents in the standard that an algorithm takes two
sequences with potentially different input sizes and chooses the smaller
size as the number of iterations it is going to make, such as std::ranges::transform
and std::ranges::mismatch
.
For the record, std::transform
(including the overload with execution policy) doesn’t support different
input sizes, while std::mismatch
does.
In the case of two input ranges or sequences, for a few algorithms -
namely, mismatch
,
equal
, and
transform
- it could be sufficient
for just one range to be bounded and the other assumed to have at least
as many elements as the bounded one. This enables unbounded ranges such
as views::repeat
in
certain useful patterns, for example:
void normalize_parallel(range auto&& v) {
auto mx = reduce(execution::par, v, ranges::max{});
(execution::par, v, views::repeat(mx), v.begin(), divides);
transform}
However, SG9 decided to require
sized_range
for all inputs, with the
plan to relax these constraints for
transform
once there is a way to
statically detect infinite ranges like views::repeat
(as
opposed to finite unsized ranges, such as null terminated strings).
The exposition-only concept random-access-sized-range
combines the key requirements to the types of ranges to simplify the
signatures of parallel range algorithms:
template<class R>
concept random-access-sized-range = // exposition only
::random_access_range<R> && ranges::sized_range<R>; ranges
In [P3179R0] we proposed that parallel range
algorithms should require function objects for predicates, comparators,
etc. to have
const
-qualified
operator()
,
with the intent to provide compile-time diagnostics for mutable function
objects which might be unsafe for parallel execution. We have got
contradictory feedback from SG1 and SG9 on that topic: SG1 preferred to
keep the behavior consistent with C++17 parallel algorithms, while SG9
supported our design intent.
We did extra investigation and decided that requiring
const
-qualified
operator at compile-time is not strictly necessary because:
regular_invocable
(or
its derivatives), which already has the semantic requirement of not
modifying either the function object or its arguments. While not
enforced at compile-time, it seems good enough for our purpose because
it demands having the same function object state between invocations
(independently of
const
qualifier), and it is consistent with serial range algorithms.for_each
using a mutable operator()
is of less concern if the algorithm does not return the function object
(see more detailed analysis below). For
generate
, a non-mutable callable
appears to be of very limited use: in order to produce multiple values
while not taking any arguments, a generator should typically maintain
and update some state.The following example works fine for serial code. While it compiles
for parallel code, users should not assume that the semantics remains
intact. Since the parallel version of
for_each
requires function object to
be copyable, it is not guaranteed that all
for_each
iterations are processed by
the same function object. Practically speaking, users cannot rely on
accumulating any state modifications in a parallel
for_each
call.
struct callable
{
void operator()(int& x)
{
++x;
++i; // a data race if the callable is executed concurrently
}
int get_i() const {
return i;
}
private:
int i = 0;
};
callable c;
// serial for_each call
auto fun = std::for_each(v.begin(), v.end(), c);
// parallel for_each call
// The callable object cannot be read because parallel for_each version purposefully returns void
::for_each(std::execution::par, v.begin(), v.end(), c);
std
// for_each serial range version call
auto [_, fun] = std::ranges::for_each(v.begin(), v.end(), c);
We allow the same callable to be used in the proposed std::ranges::for_each
.
// callable is used from the previous code snippet
callable c;// The returned iterator is ignored
::ranges::for_each(std::execution::par, v.begin(), v.end(), c); std
Again, even though c
accumulates
state modifications, one cannot rely on that because an algorithm
implementation is allowed to make as many copies of
c
as it wants. Of course, this can
be overcome by using std::reference_wrapper
but that might lead to data races.
// callable is used from the previous code snippet
// Wrapping a callable object with std::reference_wrapper compiles, but might result in data races
callable c;::ranges::for_each(std::execution::par, v.begin(), v.end(), std::ref(c)); std
Our conclusion is that it’s user responsibility to provide such a callable that avoids data races, same as for C++17 parallel algorithms.
constexpr
parallel range algorithms[P2902R0] suggests allowing algorithms with execution policies to be used in constant expressions. We do not consider that as a primary design goal for our work, however we will happily align with that proposal in the future once it progresses towards adoption into the working draft.
One of the goals is to require a minimal amount of changes when switching from the existing API to parallel range algorithms. However, that simplicity should not create hidden issues negatively impacting the overall user experience. We believe that the proposal provides a good balance in that regard.
As an example, let’s look at using
for_each
to apply a lambda function
to all elements of a std::vector v
.
For the serial range-based
for_each
call:
::ranges::for_each(v, [](auto& x) { ++x; }); std
switching to the parallel version will look like:
::ranges::for_each(std::execution::par, v, [](auto& x) { ++x; }); std
In this simple case, the only change is an execution policy added as
the first function argument. It will also hold for the “iterator and
sentinel” overload of std::ranges::for_each
.
The C++17 parallel for_each
call:
::for_each(std::execution::par, v.begin(), v.end(), [](auto& x) { ++x; }); std
can be changed to one of the following:
// Using iterator and sentinel
::ranges::for_each(std::execution::par, v.begin(), v.end(), [](auto& x) { ++x; });
std
// Using vector as a range
::ranges::for_each(std::execution::par, v, [](auto& x) { ++x; }); std
So, here only changing the namespace is necessary, though users might
also change v.begin(), v.end()
to just v
.
However, for other algorithms more changes might be necessary.
Let’s consider the following example:
(policy, begin(data), end(data));
reverse(policy, begin(data), end(data), begin(result), [](auto i){ return i * i; });
transformauto res = find_if(policy, begin(result), end(result), pred);
It has three stages and eventually tries to answer the question if the input sequence contains an element after reversing and transforming it. The interesting considerations are:
any_of
stage is started, though it
is not required for correctness. If reverse and transformation would be
done on the fly, a good implementation of
any_of
might have skipped the
remaining work when pred
returns
true
, thus
providing more performance.Let’s make it better:
// With fancy iterators
auto res = find_if(policy,
(make_reverse_iterator(end(data)),
make_transform_iterator[](auto i){ return i * i; }),
(make_reverse_iterator(begin(data)),
make_transform_iterator[](auto i){ return i * i; }),
); pred
Now there is only one parallel algorithm call, and
any_of
can skip unneeded work.
However, this variation also has interesting considerations:
transform iterator
to pass the
transformation function, but the two
make_transform_iterator
expressions
use two different lambdas, and the iterator type for
any_of
cannot be deduced because the
types of transform_iterator
do not
match. One of the options to make it compile is to store a lambda in a
variable.Let’s improve the example further with the proposed API:
// With ranges
auto res = find_if(policy, data | views::reverse | views::transform([](auto i){ return i * i; }),
); pred
The example above lacks the drawbacks described for the previous variations:
Here we show a possible implementation of std::ranges::for_each
with the new overloads proposed in Modify
for_each in [alg.foreach]:
// A possible implementation of std::ranges::for_each
namespace ranges
{
namespace __detail
{
struct __for_each_fn
{
// ...
// Existing serial overloads
// ...
// The overload for unsequenced and parallel policies. Requires random_access_iterator
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity, indirectly_unary_invocable<projected<I, Proj>> Fun>
operator()(Ep&& exec, I first, S last, Fun f, Proj proj = {}) const
I {
// properly handle the execution policy;
// for the reference, a serial implementation is provided
for (; first != last; ++first)
{
::invoke(f, std::invoke(proj, *first));
std}
return first;
}
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Fun>
indirectly_unary_invocable::borrowed_iterator_t<R>
rangesoperator()(Ep&& exec, R&& r, Fun f, Proj proj = {}) const
{
return (*this)(std::forward<Ep>(exec), std::ranges::begin(r),
::ranges::end(r), f, proj);
std}
}; // struct for_each
} // namespace __detail
inline namespace __for_each_fn_namespace
{
inline constexpr __detail::__for_each_fn for_each;
} // __for_each_fn_namespace
} // namespace ranges
std::ranges
namespace
all_of
|
search{_n}
|
remove_copy
|
is_sorted
|
is_heap
|
any_of
|
copy{_n}
|
remove_copy_if
|
is_sorted_until
|
is_heap_until
|
none_of
|
copy_if
|
unique
|
nth_element
|
min_element
|
for_each{_n}
|
move
|
unique_copy
|
is_partitioned
|
max_element
|
find
|
swap_ranges
|
reverse
|
partition
|
minmax_element
|
find_if
|
transform
|
reverse_copy
|
stable_partition
|
lexicographical_compare
|
find_if_not
|
replace
|
rotate
|
partition_copy
|
uninitialized_default_construct{_n}
|
find_end
|
replace_if
|
rotate_copy |
merge
|
uninitialized_value_construct{_n}
|
find_first_of
|
replace_copy
|
shift_left
|
inplace_merge
|
uninitialized_copy{_n}
|
adjacent_find
|
replace_copy_if
|
shift_right
|
includes
|
uninitialized_move{_n}
|
count
|
fill{_n}
|
sort
|
set_union
|
uninitialized_fill{_n}
|
count_if
|
generate{_n}
|
stable_sort
|
set_intersection
|
destroy{_n}
|
mismatch
|
remove
|
partial_sort
|
set_difference
| |
equal
|
remove_if
|
partial_sort_copy
|
set_symmetric_difference
|
std::ranges
namespace onlyThe algorithms below are easy to add because they are either expressible via existing parallel algorithms or an analogue with very close semantics exists:
std::ranges
algorithms to add
|
std algorithms used as the guidance
|
---|---|
contains
|
find
|
contains_subrange
|
search
|
find_last
|
find
|
find_last_if
|
find_if
|
find_last_if_not
|
find_if_not
|
starts_with
|
mismatch
|
ends_with
|
equal
|
min
|
min_element
|
max
|
max_element
|
minmax
|
minmax_element
|
Below we list the algorithms where we faced design issue(s). We would like to add them later:
rotate_copy
ExecutionPolicy
Below we list the algorithms below without
ExecutionPolicy
in C++17 and where
ExecutionPolicy
parameter doesn’t
seem to add value:
push_heap
pop_heap
sort_heap
next_permutation
prev_permutation
lower_bound
upper_bound
equal_range
binary_search
partition_point
Below we list the algorithms below without
ExecutionPolicy
in C++17, where
ExecutionPolicy
parameter might make
sense but requires deeper investigation:
iota
make_heap
is_permutation
copy_backward
move_backward
sample
(RNG specific)shuffle
(RNG specific)Below we list
std::ranges
only algorithms where we don’t add the
ExecutionPolicy
parameter:
fold_left
fold_left_first
fold_right
fold_right_last
fold_left_with_iter
fold_left_first_with_iter
generate_random
(RNG specific,
ExecutionPolicy
parameter was
rejected during [P1068R11] review)We understand that some useful algorithms do not yet exist in
std::ranges
,
for example, most of generalized numeric operations [numeric.ops]. The goal
of this paper is however limited to adding overloads with
ExecutionPolicy
to the existing
algorithms in the
std::ranges
namespace. Any follow-up paper that adds <numeric>
algorithms to
std::ranges
should also consider adding dedicated overloads with
ExecutionPolicy
.
The oneAPI DPC++ Library (oneDPL) developer guide covers parallel range algorithms we’ve implemented so far. The oneAPI specification provides formal signatures of these algorithms. The implementation supports execution policies for CPUs (semantically aligned with the C++ standard) and for SYCL devices, and it works with a subset of the standard C++ views.
We use the range-as-the-output approach where applicable: in
transform
,
copy
,
copy_if
, and
merge
.
We don’t foresee any issues with implementability for the rest of the proposed parallel algorithms because all of them were already implemented in C++17 and new APIs that we propose are expressible via the existing ones.
Having known bugs and feedback from SG1 and SG9, the plan of work prior to the next committee F2F meeting in Austria, 2025 is the following:
partition_copy
and
set_
algorithms family (like
set_union
, etc.)<memory>
Parallel Algorithms exist in the <memory>
synopsis only. Should it be fixed?ranges
is used (or not
used) inconsistently, in our opinion. Need an advice.partial_sort_copy
range-as-an-output is called R2
. For
uninitialized_copy
and
uninitialized_move
it’s called
OS
. For the new wording we call is
OutR
. We should probably align. The
same is true for sentinel-for-output.ExecutionPolicy
function
parameter is named exec
everywhere,
except two places where the name is
policy
. Should it be fixed?starts_with
,
ends_with
misses dot at the end of
Returns. It should be fixed, right?find_last
doesn’t have T = projected_value
…
in the synopsis. It must be a bug.replace_copy_if
does not
have indent for the second row of function parameters.unique_copy
wording uses
N
but its never
defined.shift_left
doesn’t have extra
‘Returns’ word in Returns sectionnth_element
in Effects
says were sorted. Should it be was?inplace_merge
Remarks
is not consistent with the rest, doesn’t have the same link to [algorithm.stable].execution-policy Ep
? Like
that? Without Ep
? Without execution-policy
?sort
might have a potential bug
in complexity about projections application.partial_sort_copy
seems to have
incomplete wording.We need to understand better whether using some
views
with parallel algorithms might
result in data races. While some investigation was done by other authors
in [P3159R0], it’s mostly not about the data
races but about ability to parallelize processing of data represented by
various views.
We need to invest more time to understand the implications of sharing
a state between view
and
iterator
on the possibility of data
races. One example is
transform_view
, where iterators keep
pointers to the function object that is stored in the view itself.
Here are questions we want to answer (potentially not a complete list):
begin()/end()/size()
and possibly other operations with ranges be considered like element
access functions for the purpose of thread safety definition?__cpp_lib_parallel_algorithm
macro
in [version.syn]- #define __cpp_lib_parallel_algorithm 201603L // also in <algorithm>, <numeric>
+ #define __cpp_lib_parallel_algorithm 20XXXXL // also in <algorithm>, <numeric>, <memory>
template<class T>// freestanding
concept constant_range = see below; +
+ template<class R>
+ concept random-access-sized-range = see below // exposition only
7
The constant_range
concept specifies
the requirements of a range
type
whose elements are not modifiable.
template<class T>
concept constant_range =
<T> && constant-iterator<iterator_t<T>>; input_range
X
The exposition-only
random-access-sized-range
concept specifies the requirements of a
range
type that is sized and
allows random access to its elements.
[Note X: This concept constraints some parallel algorithm overloads; see [algorithms] — end note]
template<class R>
concept random-access-sized-range = // exposition only random_access_range<R> && sized_range<R>;
2
A parallel algorithm is a function template listed in this
documentClause with an execution policy
([execpol])
template parameter named
ExecutionPolicy
or
execution-policy Ep
.
3 Parallel algorithms access objects indirectly accessible via their arguments by invoking the following functions:
1
Unless otherwise specified, functioninvocable objects passed into
parallel algorithms as objects of type
Predicate
,
BinaryPredicate
,
Compare
,
UnaryOperation
,
BinaryOperation
,
BinaryOperation1
,
BinaryOperation2
,
BinaryDivideOp
, Proj
,
and the operators used by the analogous overloads to these parallel
algorithms that are formed by an invocation with the specified default
predicate or operation (where applicable) shall not directly or
indirectly modify objects via their arguments, nor shall they rely on
the identity of the provided objects.
1
Parallel algorithms have template parameters named
ExecutionPolicy
or
execution-policy Ep
([execpol]) which
describe the manner in which the execution of these algorithms may be
parallelized and the manner in which they apply the element access
functions.
2
During the execution of a parallel algorithm, if the invocation of an
element access function exits via an uncaught exception, the behavior is
determined by the execution
policy.ExecutionPolicy
1
Parallel algorithms are algorithm overloads. Each parallel algorithm
overload has an additional template type parameter named
ExecutionPolicy
or
execution-policy Ep
,
which is the first template parameter. Additionally, each parallel
algorithm overload has an additional function parameter of type ExecutionPolicy&&
or
Ep&&
,
which is the first function parameter.
[Note 1: Not all algorithms have parallel algorithm overloads. — end note]
2
Unless otherwise specified, the semantics of
algorithm overloads with
an execution policy are identical to their overloads
without.ExecutionPolicy
3
Unless otherwise specified, the complexity requirements of
algorithm overloads with
an execution policy are relaxed from the complexity
requirements of the overloads without as follows: …ExecutionPolicy
4
Parallel algorithms shall not participate in overload resolution unless
is_execution_policy_v<remove_cvref_t<ExecutionPolicy>>
is true
.
Parallel algorithms in the
std::ranges
namespace are constrained with the following exposition-only
concept:
template<class Ep>
concept execution-policy = // exposition only is_execution_policy_v<remove_cvref_t<Ep>>;
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool all_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool all_of(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ bool all_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ bool all_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool any_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool any_of(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ bool any_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ bool any_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool none_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool none_of(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ bool none_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ bool none_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr bool contains(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr bool contains(R&& r, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ class T = projected_value_t<I, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ bool contains(Ep&& exec, I first, S last, const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ bool contains(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<forward_iterator I1, sentinel_for<I1> S1,
forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool contains_subrange(R1&& r1, R2&& r2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ bool contains_subrange(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ bool contains_subrange(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {},
+ Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I, class F>
using for_each_result = in_fun_result<I, F>;
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun>
constexpr for_each_result<I, Fun>
for_each(I first, S last, Fun f, Proj proj = {});
template<input_range R, class Proj = identity,
indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
constexpr for_each_result<borrowed_iterator_t<R>, Fun>
for_each(R&& r, Fun f, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirectly_unary_invocable<projected<I, Proj>> Fun>
+ I for_each(Ep&& exec, I first, S last, Fun f, Proj proj = {});
+
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
+ borrowed_iterator_t<R>
+ for_each(Ep&& exec, R&& r, Fun f, Proj proj = {});
}
namespace ranges {
template<class I, class F>
using for_each_n_result = in_fun_result<I, F>;
template<input_iterator I, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun>
constexpr for_each_n_result<I, Fun>
for_each_n(I first, iter_difference_t<I> n, Fun f, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, class Proj = identity,
+ indirectly_unary_invocable<projected<I, Proj>> Fun>
+ I for_each_n(Ep&& exec, I first, iter_difference_t<I> n, Fun f, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr I find(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_iterator_t<R>
find(R&& r, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ class T = projected_value_t<I, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ I find(Ep&& exec, I first, S last, const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R,
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ borrowed_iterator_t<R> find(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_iterator_t<R>
find_if(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ I find_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ borrowed_iterator_t<R> find_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_iterator_t<R>
find_if_not(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ I find_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ borrowed_iterator_t<R> find_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> find_last(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class T, class Proj = identity>
requires
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R> find_last(R&& r, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ class T = projected_value_t<I, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ subrange<I> find_last(Ep&& exec, I first, S last, const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ borrowed_subrange_t<R> find_last(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> find_last_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_subrange_t<R> find_last_if(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ subrange<I> find_last_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ borrowed_subrange_t<R> find_last_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> find_last_if_not(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr borrowed_subrange_t<R> find_last_if_not(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ subrange<I> find_last_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ borrowed_subrange_t<R> find_last_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
find_end(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2,
+ sized_sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ subrange<I1> find_end(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ borrowed_subrange_t<R1> find_end(Ep&& exec, R1&& r1, R2&& r2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1 find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_iterator_t<R1>
find_first_of(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ I1 find_first_of(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ borrowed_iterator_t<R1> find_first_of(Ep&& exec, R1&& r1, R2&& r2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_binary_predicate<projected<I, Proj>,
projected<I, Proj>> Pred = ranges::equal_to>
constexpr I adjacent_find(I first, S last, Pred pred = {},
Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_binary_predicate<projected<iterator_t<R>, Proj>,
projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
constexpr borrowed_iterator_t<R>
adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_binary_predicate<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to>
+ I adjacent_find(Ep&& exec, I first, S last, Pred pred = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_binary_predicate<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred
+ = ranges::equal_to>
+ borrowed_iterator_t<R> adjacent_find(Ep&& exec, R&& r, Pred pred = {}, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr iter_difference_t<I>
count(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr range_difference_t<R>
count(R&& r, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ class T = projected_value_t<I, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ iter_difference_t<I> count(Ep&& exec, I first, S last, const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ range_difference_t<R> count(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr iter_difference_t<I>
count_if(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr range_difference_t<R>
count_if(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ iter_difference_t<I> count_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ range_difference_t<R> count_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<class I1, class I2>
using mismatch_result = in_in_result<I1, I2>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr mismatch_result<I1, I2>
mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
mismatch(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ mismatch_result<I1, I2>
+ mismatch(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+ mismatch(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool equal(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool equal(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ bool equal(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2, class Pred = ranges::equal_to,
+ class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ bool equal(Ep&& exec, R1&& r1, R2&& r2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
sentinel_for<I2> S2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
search(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ subrange<I1>
+ search(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ borrowed_subrange_t<R1>
+ search(Ep&& exec, R1&& r1, R2&& r2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirectly_comparable<I, const T*, Pred, Proj>
constexpr subrange<I>
search_n(I first, S last, iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {});
template<forward_range R, class Pred = ranges::equal_to,
class Proj = identity, class T = projected_value_t<I, Proj>>
requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
constexpr borrowed_subrange_t<R>
search_n(R&& r, range_difference_t<R> count,
const T& value, Pred pred = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Pred = ranges::equal_to, class Proj = identity,
+ class T = projected_value_t<I, Proj>>
+ requires indirectly_comparable<I, const T*, Pred, Proj>
+ subrange<I>
+ search_n(Ep&& exec, I first, S last, iter_difference_t<I> count,
+ const T& value, Pred pred = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Pred = ranges::equal_to,
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
+ borrowed_subrange_t<R>
+ search_n(Ep&& exec, R&& r, range_difference_t<R> count,
+ const T& value, Pred pred = {}, Proj proj = {});
}
namespace ranges {
// [alg.starts.with], starts with
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool starts_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool starts_with(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ bool starts_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ bool starts_with(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
// [alg.ends.with], ends with
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires (forward_iterator<I1> || sized_sentinel_for<S1, I1>) &&
(forward_iterator<I2> || sized_sentinel_for<S2, I2>) &&
indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool ends_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires (forward_range<R1> || sized_range<R1>) &&
(forward_range<R2> || sized_range<R2>) &&
indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool ends_with(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
+ bool ends_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
+ bool ends_with(Ep&& exec, R1&& r1, R2&& r2,
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I, class O>
using copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr copy_result<I, O>
copy(I first, S last, O result);
template<input_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr copy_result<borrowed_iterator_t<R>, O>
copy(R&& r, O result);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>
+ requires indirectly_copyable<I, O>
+ copy_result<I, O> copy(Ep&& exec, I first, S last, O result, OutS result_last);
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
+ copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ copy(Ep&& exec, R&& r, OutR&& result_r);
}
namespace ranges {
template<class I, class O>
using copy_n_result = in_out_result<I, O>;
template<input_iterator I, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr copy_n_result<I, O>
copy_n(I first, iter_difference_t<I> n, O result);
+ template<execution-policy Ep, random_access_iterator I, random_access_iterator O,
+ sized_sentinel_for<O> OutS>
+ requires indirectly_copyable<I, O>
+ copy_n_result<I, O>
+ copy_n(Ep&& exec, I first, iter_difference_t<I> n, O result, OutS result_last);
}
namespace ranges {
template<class I, class O>
using copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
constexpr copy_if_result<I, O>
copy_if(I first, S last, O result, Pred pred, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O>
constexpr copy_if_result<borrowed_iterator_t<R>, O>
copy_if(R&& r, O result, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_copyable<I, O>
+ copy_if_result<I, O>
+ copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
+ Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random_access_iterator OutR,
+ class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
+ copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
}
namespace ranges {
template<class I, class O>
using move_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_movable<I, O>
constexpr move_result<I, O>
move(I first, S last, O result);
template<input_range R, weakly_incrementable O>
requires indirectly_movable<iterator_t<R>, O>
constexpr move_result<borrowed_iterator_t<R>, O>
move(R&& r, O result);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>
+ requires indirectly_movable<I, O>
+ move_result<I, O> move(Ep&& exec, I first, S last, O result, OutS result_last);
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
+ requires indirectly_movable<iterator_t<R>, iterator_t<OutR>>
+ move_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ move(Ep&& exec, R&& r, OutR&& result_r);
}
namespace ranges {
template<class I1, class I2>
using swap_ranges_result = in_in_result<I1, I2>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
requires indirectly_swappable<I1, I2>
constexpr swap_ranges_result<I1, I2>
swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
template<input_range R1, input_range R2>
requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
constexpr swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
swap_ranges(R1&& r1, R2&& r2);
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2>
+ requires indirectly_swappable<I1, I2>
+ swap_ranges_result<I1, I2>
+ swap_ranges(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2);
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2>
+ requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
+ swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+ swap_ranges(Ep&& exec, R1&& r1, R2&& r2);
}
namespace ranges {
template<class I, class O>
using unary_transform_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
copy_constructible F, class Proj = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
constexpr unary_transform_result<I, O>
transform(I first1, S last1, O result, F op, Proj proj = {});
template<input_range R, weakly_incrementable O, copy_constructible F,
class Proj = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
constexpr unary_transform_result<borrowed_iterator_t<R>, O>
transform(R&& r, O result, F op, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS,
+ copy_constructible F, class Proj = identity>
+ requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
+ unary_transform_result<I, O>
+ transform(Ep&& exec, I first, S last, O result, OutS result_last,
+ F op, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ copy_constructible F, class Proj = identity>
+ requires indirectly_writable<iterator_t<OutR>, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
+ unary_transform_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ transform(Ep&& exec, R&& r, OutR&& result_r, F op, Proj proj = {});
template<class I1, class I2, class O>
using binary_transform_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, copy_constructible F, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>,
projected<I2, Proj2>>>
constexpr binary_transform_result<I1, I2, O>
transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
copy_constructible F, class Proj1 = identity, class Proj2 = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>>
constexpr binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
transform(R1&& r1, R2&& r2, O result,
F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS,
+ copy_constructible F, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>, projected<I2, Proj2>>>
+ binary_transform_result<I1, I2, O>
+ transform(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result,
+ OutS result_last, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, copy_constructible F, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_writable<iterator_t<OutR>,
+ indirect_result_t<F&, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>>>
+ binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
+ transform(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T1 = projected_value_t<I, Proj>, class T2 = T1>
requires indirectly_writable<I, const T2&> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
constexpr I
replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
template<input_range R, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
requires indirectly_writable<iterator_t<R>, const T2&> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T1*>
constexpr borrowed_iterator_t<R>
replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = T1>
+ requires indirectly_writable<I, const T2&> &&
+ indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
+ I replace(Ep&& exec, I first, S last,
+ const T1& old_value, const T2& new_value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
+ requires indirectly_writable<iterator_t<R>, const T2&> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
+ borrowed_iterator_t<R>
+ replace(Ep&& exec, R&& r,
+ const T1& old_value, const T2& new_value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_writable<I, const T&>
constexpr I replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {});
template<input_range R, class Proj = identity, class T = projected_value_t<I, Proj>,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_writable<iterator_t<R>, const T&>
constexpr borrowed_iterator_t<R>
replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
+ class T = projected_value_t<I, Proj>,
+ indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_writable<I, const T&>
+ I replace_if(Ep&& exec, I first, S last, Pred pred,
+ const T& new_value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T = projected_value_t<iterator_t<R>, Proj>,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_writable<iterator_t<R>, const T&>
+ borrowed_iterator_t<R>
+ replace_if(Ep&& exec, R&& r, Pred pred,
+ const T& new_value, Proj proj = {});
}
namespace ranges {
template<class I, class O>
using replace_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, class O,
class Proj = identity,
class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> &&
output_iterator<O, const T2&>
constexpr replace_copy_result<I, O>
replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
Proj proj = {});
template<input_range R, class O, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<iterator_t<R>, O> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T1*> &&
output_iterator<O, const T2&>
constexpr replace_copy_result<borrowed_iterator_t<R>, O>
replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>,
+ class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
+ requires indirectly_copyable<I, O> &&
+ indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> &&
+ indirectly_writable<O, const T2&>
+ replace_copy_result<I, O>
+ replace_copy(Ep&& exec, I first, S last, O result, OutS result_last,
+ const T1& old_value, const T2& new_value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ class Proj = identity, class T1 = projected_value_t<iterator_t<R>, Proj>,
+ class T2 = range_value_t<OutR>>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*> &&
+ indirectly_writable<iterator_t<OutR>, const T2&>
+ replace_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ replace_copy(Ep&& exec, R&& r, OutR&& result_r,
+ const T1& old_value, const T2& new_value, Proj proj = {});
template<class I, class O>
using replace_copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, class O, class T = iter_value_t<O>
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O> && output_iterator<O, const T&>
constexpr replace_copy_if_result<I, O>
replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
Proj proj = {});
template<input_range R, class O, class T = iter_value_t<O>, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O> && output_iterator<O, const T&>
constexpr replace_copy_if_result<borrowed_iterator_t<R>, O>
replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>, class T = iter_value_t<O>,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_copyable<I, O> && indirectly_writable<O, const T&>
+ replace_copy_if_result<I, O>
+ replace_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
+ Pred pred, const T& new_value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ class T = range_value_t<OutR>, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
+ indirectly_writable<iterator_t<OutR>, const T&>
+ replace_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ replace_copy_if(Ep&& exec, R&& r, OutR&& result_r,
+ Pred pred, const T& new_value, Proj proj = {});
}
namespace ranges {
template<class O, sentinel_for<O> S, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O fill(O first, S last, const T& value);
template<class R, class T = range_value_t<R>>
requires output_range<R, const T&>
constexpr borrowed_iterator_t<R> fill(R&& r, const T& value);
template<class O, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O fill_n(O first, iter_difference_t<O> n, const T& value);
+ template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S,
+ class T = iter_value_t<O>>
+ requires indirectly_writable<O, const T&>
+ O fill(Ep&& exec, O first, S last, const T& value);
+ template<execution-policy Ep, random-access-sized-range R, class T = range_value_t<R>>
+ requires indirectly_writable<iterator_t<R>, const T&>
+ borrowed_iterator_t<R> fill(Ep&& exec, R&& r, const T& value);
+ template<execution-policy Ep, random_access_iterator O, class T = iter_value_t<O>>
+ requires indirectly_writable<O, const T&>
+ O fill_n(Ep&& exec, O first, iter_difference_t<O> n, const T& value);
}
namespace ranges {
template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O generate(O first, S last, F gen);
template<class R, copy_constructible F>
requires invocable<F&> && output_range<R, invoke_result_t<F&>>
constexpr borrowed_iterator_t<R> generate(R&& r, F gen);
template<input_or_output_iterator O, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O generate_n(O first, iter_difference_t<O> n, F gen);+ template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S,
+ copy_constructible F>
+ requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
+ O generate(Ep&& exec, O first, S last, F gen);
+ template<execution-policy Ep, random-access-sized-range R, copy_constructible F>
+ requires invocable<F&> && indirectly_writable<iterator_t<R>, invoke_result_t<F&>>
+ borrowed_iterator_t<R> generate(Ep&& exec, R&& r, F gen);
+ template<execution-policy Ep, random_access_iterator O, copy_constructible F>
+ requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
+ O generate_n(Ep&& exec, O first, iter_difference_t<O> n, F gen);
}
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> remove(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires permutable<iterator_t<R>> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R>
remove(R&& r, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, class T = projected_value_t<I, Proj>>
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ subrange<I> remove(Ep&& exec, I first, S last, const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ class T = projected_value_t<iterator_t<R>, Proj>>
+ requires permutable<iterator_t<R>> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ borrowed_subrange_t<R> remove(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I> remove_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
remove_if(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ subrange<I> remove_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> remove_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<class I, class O>
using remove_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, class T = projected_value_t<I, Proj>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr remove_copy_result<I, O>
remove_copy(I first, S last, O result, const T& value, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_copyable<iterator_t<R>, O> &&
indirect_binary_predicate<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
constexpr remove_copy_result<borrowed_iterator_t<R>, O>
remove_copy(R&& r, O result, const T& value, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>,
+ class Proj = identity, class T = projected_value_t<I, Proj>>
+ requires indirectly_copyable<I, O> &&
+ indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ remove_copy_result<I, O>
+ remove_copy(Ep&& exec, I first, S last, O result, OutS result_last,
+ const T& value, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+ remove_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ remove_copy(Ep&& exec, R&& r, OutR&& result_r, const T& value, Proj proj = {});
template<class I, class O>
using remove_copy_if_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
constexpr remove_copy_if_result<I, O>
remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O>
constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_copyable<I, O>
+ remove_copy_if_result<I, O>
+ remove_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
+ Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
+ remove_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ remove_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
}
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
unique(R&& r, C comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
+ requires permutable<I>
+ subrange<I> unique(Ep&& exec, I first, S last, C comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> unique(Ep&& exec, R&& r, C comp = {}, Proj proj = {});
}
namespace ranges {
template<class I, class O>
using unique_copy_result = in_out_result<I, O>;
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
requires indirectly_copyable<I, O> &&
(forward_iterator<I> ||
(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
indirectly_copyable_storable<I, O>)
constexpr unique_copy_result<I, O>
unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});
template<input_range R, weakly_incrementable O, class Proj = identity,
indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires indirectly_copyable<iterator_t<R>, O> &&
(forward_iterator<iterator_t<R>> ||
(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
indirectly_copyable_storable<iterator_t<R>, O>)
constexpr unique_copy_result<borrowed_iterator_t<R>, O>
unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>, class Proj = identity,
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
+ requires indirectly_copyable<I, O>
+ unique_copy_result<I, O>
+ unique_copy(Ep&& exec, I first, S last, O result, OutS result_last,
+ C comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
+ class Proj = identity,
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
+ unique_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ unique_copy(Ep&& exec, R&& r, OutR&& result_r,
+ C comp = {}, Proj proj = {});
}
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I>
constexpr I reverse(I first, S last);
template<bidirectional_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_iterator_t<R> reverse(R&& r);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
+ requires permutable<I>
+ I reverse(Ep&& exec, I first, S last);
+ template<execution-policy Ep, random-access-sized-range R>
+ requires permutable<iterator_t<R>>
+ borrowed_iterator_t<R> reverse(Ep&& exec, R&& r);
}
namespace ranges {
template<class I, class O>
using reverse_copy_result = in_out_result<I, O>;
template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr reverse_copy_result<I, O>
reverse_copy(I first, S last, O result);
template<bidirectional_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr reverse_copy_result<borrowed_iterator_t<R>, O>
reverse_copy(R&& r, O result);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O, sized_sentinel_for<O> OutS>
+ requires indirectly_copyable<I, O>
+ reverse_copy_result<I, O>
+ reverse_copy(Ep&& exec, I first, S last, O result, OutS result_last);
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
+ reverse_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
+ reverse_copy(Ep&& exec, R&& r, OutR&& result_r);
}
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> rotate(I first, I middle, S last);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> rotate(R&& r, iterator_t<R> middle);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
+ requires permutable<I>
+ subrange<I> rotate(Ep&& exec, I first, I middle, S last);
+ template<execution-policy Ep, random-access-sized-range R>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> rotate(Ep&& exec, R&& r, iterator_t<R> middle);
}
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> shift_left(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> shift_left(R&& r, range_difference_t<R> n);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
+ requires permutable<I>
+ subrange<I> shift_left(Ep&& exec, I first, S last, iter_difference_t<I> n);
+ template<execution-policy Ep, random-access-sized-range R>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> shift_left(Ep&& exec, R&& r, range_difference_t<R> n);
}
namespace ranges {
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> shift_right(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> shift_right(R&& r, range_difference_t<R> n);
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
+ requires permutable<I>
+ subrange<I> shift_right(Ep&& exec, I first, S last, iter_difference_t<I> n);
+ template<execution-policy Ep, random-access-sized-range R>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> shift_right(Ep&& exec, R&& r, range_difference_t<R> n);
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
sort(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
sort(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Comp = ranges::less, class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R> sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
stable_sort(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Comp = ranges::less, class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R> stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
partial_sort(R&& r, iterator_t<R> middle, Comp comp = {},
Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Comp = ranges::less, class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R> partial_sort(Ep&& exec, R&& r, iterator_t<R> middle,
+ Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<class I, class O>
using partial_sort_copy_result = in_out_result<I, O>;
template<input_iterator I1, sentinel_for<I1> S1,
random_access_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
constexpr partial_sort_copy_result<I1, I2>
partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, random_access_range R2, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
sortable<iterator_t<R2>, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>
constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
+ indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+ partial_sort_copy_result<I1, I2>
+ partial_sort_copy(Ep&& exec, I1 first, S1 last, I2 result_first, S2 result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+ requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
+ sortable<iterator_t<R2>, Comp, Proj2> &&
+ indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
+ projected<iterator_t<R2>, Proj2>>
+ partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+ partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {},
+ Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr bool is_sorted(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr bool is_sorted(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ bool is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ bool is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ I is_sorted_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ borrowed_iterator_t<R> is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Comp = ranges::less, class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I nth_element(Ep&& exec, I first, I nth, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R> nth_element(Ep&& exec, R&& r, iterator_t<R> nth,
+ Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr bool is_partitioned(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool is_partitioned(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ bool is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ bool is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<permutable I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr subrange<I>
partition(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
partition(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ subrange<I> partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires permutable<I>
constexpr subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});
template<bidirectional_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires permutable<I>
+ subrange<I> stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires permutable<iterator_t<R>>
+ borrowed_subrange_t<R> stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
}
namespace ranges {
template<class I, class O1, class O2>
using partition_copy_result = in_out_out_result<I, O1, O2>;
template<input_iterator I, sentinel_for<I> S,
weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
constexpr partition_copy_result<I, O1, O2>
partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
Proj proj = {});
template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, O1> &&
indirectly_copyable<iterator_t<R>, O2>
constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>
partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ random_access_iterator O1, sized_sentinel_for<O1> OutS1,
+ random_access_iterator O2, sized_sentinel_for<O2> OutS2,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
+ partition_copy_result<I, O1, O2>
+ partition_copy(Ep&& exec, I first, S last, O1 out_true, OutS1 last_true,
+ O2 out_false, OutS2 last_false, Pred pred, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR1,
+ random-access-sized-range OutR2, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR1>> &&
+ indirectly_copyable<iterator_t<R>, iterator_t<OutR2>>
+ partition_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR1>, borrowed_iterator_t<OutR2>>
+ partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r,
+ Pred pred, Proj proj = {});
}
namespace ranges {
template<class I1, class I2, class O>
using merge_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr merge_result<I1, I2, O>
merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
merge(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ merge_result<I1, I2, O>
+ merge(Ep&& exec, I1 first1, S1 last1,
+ I2 first2, S2 last2, O result, OutS result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
+ merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
+ merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {},
Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Comp = ranges::less, class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R> inplace_merge(Ep&& exec, R&& r, iterator_t<R> middle,
+ Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
ranges::less>
constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Proj1 = identity, class Proj2 = identity,
+ indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
+ bool includes(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Proj1 = identity, class Proj2 = identity,
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+ bool includes(Ep&& exec, R1&& r1, R2&& r2,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I1, class I2, class O>
using set_union_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_union_result<I1, I2, O>
set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ set_union_result<I1, I2, O>
+ set_union(Ep&& exec, I1 first1, S1 last1,
+ I2 first2, S2 last2, O result, OutS result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
+ set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
+ set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I1, class I2, class O>
using set_intersection_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<I1, I2, O>
set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
set_intersection(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ set_intersection_result<I1, I2, O>
+ set_intersection(Ep&& exec, I1 first1, S1 last1,
+ I2 first2, S2 last2, O result, OutS result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
+ rages::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
+ set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I, class O>
using set_difference_result = in_out_result<I, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_difference_result<I1, O>
set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_difference_result<borrowed_iterator_t<R1>, O>
set_difference(R1&& r1, R2&& r2, O result,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ set_difference_result<I1, O>
+ set_difference(Ep&& exec, I1 first1, S1 last1,
+ I2 first2, S2 last2, O result, OutS result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
+ set_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<OutR>>
+ set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<class I1, class I2, class O>
using set_symmetric_difference_result = in_in_out_result<I1, I2, O>;
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_symmetric_difference_result<I1, I2, O>
set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = {}, Proj1 proj1 = {},
Proj2 proj2 = {});
template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
borrowed_iterator_t<R2>, O>
set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ set_symmetric_difference_result<I1, I2, O>
+ set_symmetric_difference(Ep&& exec, I1 first1, S1 last1,
+ I2 first2, S2 last2, O result, OutS result_last,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ random-access-sized-range OutR, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
+ set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
+ set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr bool is_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr bool is_heap(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ bool is_heap(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ bool is_heap(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ I is_heap_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ borrowed_iterator_t<R>
+ is_heap_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr T min(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R>
min(R&& r, Comp comp = {}, Proj proj = {});+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+ range_value_t<R>
+ min(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr T max(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R>
max(R&& r, Comp comp = {}, Proj proj = {});+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+ range_value_t<R>
+ max(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<class T>
using minmax_result = min_max_result<T>;
template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr minmax_result<const T&>
minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {});
template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr minmax_result<T>
minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {});
template<input_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr minmax_result<range_value_t<R>>
minmax(R&& r, Comp comp = {}, Proj proj = {});+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
+ minmax_result<range_value_t<R>>
+ minmax(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
min_element(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ I min_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ borrowed_iterator_t<R>
+ min_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr I max_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr borrowed_iterator_t<R>
max_element(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ I max_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ borrowed_iterator_t<R>
+ max_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<class I>
using minmax_element_result = min_max_result<I>;
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
constexpr minmax_element_result<I>
minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
constexpr minmax_element_result<borrowed_iterator_t<R>>
minmax_element(R&& r, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
+ class Proj = identity,
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+ minmax_element_result<I>
+ minmax_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
+ template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+ minmax_element_result<borrowed_iterator_t<R>>
+ minmax_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
}
namespace ranges {
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
ranges::less>
constexpr bool
lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool
lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
+ class Proj1 = identity, class Proj2 = identity,
+ indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
+ bool lexicographical_compare(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+ template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
+ class Proj1 = identity, class Proj2 = identity,
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+ bool lexicographical_compare(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {},
+ Proj1 proj1 = {}, Proj2 proj2 = {});
}
all_of
in [alg.all.of]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
bool ranges::all_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> bool ranges::all_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
pred(*i)
for the overloads in namespace
std
;invoke(pred, invoke(proj, *i))
for the overloads in namespace
ranges
.2
Returns:
false
if
E
is
false
for
some iterator i
in the range [first, last)
,
and true
otherwise.
3
Complexity: At most
last - first
applications of the predicate and any projection.
any_of
in [alg.any.of]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
bool ranges::any_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> bool ranges::any_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
pred(*i)
for the overloads in namespace
std
;invoke(pred, invoke(proj, *i))
for the overloads in namespace
ranges
.2
Returns:
true
if
E
is
true
for
some iterator i
in the range [first, last)
,
and false
otherwise.
3
Complexity: At most
last - first
applications of the predicate and any projection.
none_of
in [alg.none.of]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
bool ranges::none_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> bool ranges::none_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
pred(*i)
for the overloads in namespace
std
;invoke(pred, invoke(proj, *i))
for the overloads in namespace
ranges
.2
Returns:
false
if
E
is
true
for
some iterator i
in the range [first, last)
,
and true
otherwise.
3
Complexity: At most
last - first
applications of the predicate and any projection.
contains
in [alg.contains]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});
Returns: ranges::find(std::move(first), last, value, proj) != last.
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
bool ranges::contains(Ep&& exec, I first, S last, const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> bool ranges::contains(Ep&& exec, R&& r, const T& value, Proj proj = {});
Returns: ranges::find(std::forward<Ep>(exec), std::move(first), last, value, proj) != last.
template<forward_iterator I1, sentinel_for<I1> S1,
<I2> S2,
forward_iterator I2, sentinel_forclass Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool ranges::contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2,
= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Pred pred template<forward_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
Returns: first2 == last2 || !ranges::search(first1, last1, first2, last2, pred, proj1, proj2).empty().
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
bool ranges::contains_subrange(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
bool ranges::contains_subrange(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Returns: first2 == last2 || !ranges::search(std::forward<Ep>(exec), first1, last1, first2, last2, pred, proj1, proj2).empty().
for_each
in [alg.foreach]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Fun>
indirectly_unary_invocableconstexpr ranges::for_each_result<I, Fun>
::for_each(I first, S last, Fun f, Proj proj = {});
rangestemplate<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Fun>
indirectly_unary_invocableconstexpr ranges::for_each_result<borrowed_iterator_t<R>, Fun>
::for_each(R&& r, Fun f, Proj proj = {}); ranges
Effects: Calls invoke(f, invoke(proj, *i))
for every iterator i
in the range
[first, last)
,
starting from first
and proceeding
to last - 1
.
[Note X: If the result of invoke(proj, *i)
is a mutable reference, f
can apply
non-constant functions. — end note]
Returns: {last, std::move(f)}.
Complexity: Applies f
and proj
exactly
last - first
times.
Remarks: If f
returns a
result, the result is ignored.
[Note X: The overloads in namespace
ranges
require
Fun
to model
copy_constructible
. — end
note]
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun>
I ranges::for_each(Ep&& exec, I first, S last, Fun f, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
borrowed_iterator_t<R> ranges::for_each(Ep&& exec, R&& r, Fun f, Proj proj = {});
Effects: Calls
invoke(f, invoke(proj, *i))
for
every iterator i
in the range
[first, last)
.
[Note X: If the result of
invoke(proj, *i)
is a mutable
reference, f
can apply
non-constant functions. — end note]
Returns: last.
Complexity: Applies
f
and
proj
exactly
last - first
times.
Remarks: If f
returns a result, the result is ignored. Implementations do not have the
freedom granted under [algorithms.parallel.exec]
to make arbitrary copies of elements from the input sequence.
[Note X: The overloads in namespace
ranges
require
Fun
to model
copy_constructible
. — end
note]
[Note X: Does not return a copy of its
Fun
parameter, since
parallelization often does not permit efficient state accumulation. —
end note]
template<input_iterator I, class Proj = identity,
<projected<I, Proj>> Fun>
indirectly_unary_invocableconstexpr ranges::for_each_n_result<I, Fun>
::for_each_n(I first, iter_difference_t<I> n, Fun f, Proj proj = {}); ranges
Preconditions: n >= 0
is true
.
Effects: Calls invoke(f, invoke(proj, *i))
for every iterator i
in the range
[first, first + n)
in order.
[Note X: If the result of invoke(proj, *i)
is a mutable reference, f
can apply
non-constant functions. — end note]
Returns: {first + n, std::move(f)}
.
Remarks: If f
returns a
result, the result is ignored.
[Note X: The overload in namespace
ranges
requires
Fun
to model
copy_constructible
. — end
note]
template<execution-policy Ep, random_access_iterator I, class Proj = identity,
indirectly_unary_invocable<projected<I, Proj>> Fun> I ranges::for_each_n(Ep&& exec, I first, iter_difference_t<I> n, Fun f, Proj proj = {});
Preconditions:
n >= 0
is
true
.
Effects: Calls
invoke(f, invoke(proj, *i))
for
every iterator i
in the range
[first, first + n)
.
[Note X: If the result of
invoke(proj, *i)
is a mutable
reference, f
can apply
non-constant functions. — end note]
Returns:
first + n
.
Remarks: If f
returns a result, the result is ignored. Implementations do not have the
freedom granted under [algorithms.parallel.exec]
to make arbitrary copies of elements from the input sequence.
[Note X: The overload in namespace
ranges
requires
Fun
to model
copy_constructible
. — end
note]
[Note X: Does not return a copy of its
Fun
parameter, since
parallelization often does not permit efficient state accumulation. —
end note]
find
in [alg.find]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_iterator_t<R>
::find(R&& r, const T& value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
I ranges::find(Ep&& exec, I first, S last, const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> borrowed_iterator_t<R> ranges::find(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr borrowed_iterator_t<R>
::find_if(R&& r, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
I ranges::find_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> borrowed_iterator_t<R> ranges::find_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr borrowed_iterator_t<R>
::find_if_not(R&& r, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
I ranges::find_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> borrowed_iterator_t<R> ranges::find_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
*i == value
for find
;pred(*i) != false
for find_if
;pred(*i) == false
for find_if_not
;bool(invoke(proj, *i) == value)
for ranges::find;
bool(invoke(pred, invoke(proj, *i)))
for ranges::find_if
;bool(!invoke(pred, invoke(proj, *i)))
for ranges::find_if_not
.2
Returns: The first iterator
i
in the range [first, last)
for which E
is
true
.
Returns last
if no such iterator is
found.
3
Complexity: At most
last - first
applications of the corresponding predicate and any projection.
find_last
in [alg.find.last]template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> ranges::find_last(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R> ranges::find_last(R&& r, const T& value, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
subrange<I> ranges::find_last(Ep&& exec, I first, S last, const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> borrowed_subrange_t<R> ranges::find_last(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
subrange<I> ranges::find_last_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> borrowed_subrange_t<R> ranges::find_last_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr subrange<I> ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr borrowed_subrange_t<R> ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
subrange<I> ranges::find_last_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> borrowed_subrange_t<R> ranges::find_last_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
bool(invoke(proj, *i) == value)
for ranges::find_last
;bool(invoke(pred, invoke(proj, *i)))
for ranges::find_last_if
;bool(!invoke(pred, invoke(proj, *i)))
for ranges::find_last_if_not
.2
Returns: Let i
be the last
iterator in the range [first, last)
for which E
is
true
.
Returns {i, last}
,
or {last, last}
if no such iterator is found.
3
Complexity: At most
last - first
applications of the corresponding predicate and projection.
find_end
in [alg.find.end]template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
ranges= {}, Proj2 proj2 = {});
Proj1 proj1 template<forward_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
::find_end(R1&& r1, R2&& r2, Pred pred = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1, random_access_iterator I2,
sized_sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
subrange<I1> ranges::find_end(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
borrowed_subrange_t<R1> ranges::find_end(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1 Let:
(1.1)
pred
be
equal_to{}
for the overloads with no parameter
pred
;
(1.2)
E
be:
(1.3)
i
be
last1
if [first2, last2)
is empty, or if (last2 - first2) > (last1 - first1)
is true
, or
if there is no iterator in the range [first1, last1 - (last2 - first2))
such that for every non-negative integer n < (last2 - first2)
,
E
is
true
.
Otherwise i
is the last such
iterator in [first1, last1 - (last2 - first2))
.
2 Returns:
i
for the overloads in namespace
std
.{i, i + (i == last1 ? 0 : last2 - first2)}
for the overloads in namespace
ranges
.3
Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1)
applications of the corresponding predicate and any projections.
find_first_of
in [alg.find.first.of]template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
= {},
Pred pred = {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, forward_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_iterator_t<R1>
::find_first_of(R1&& r1, R2&& r2, Pred pred = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
I1 ranges::find_first_of(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
borrowed_iterator_t<R1> ranges::find_first_of(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let E
be:
*i == *j
for the overloads with no parameter
pred
;pred(*i, *j) != false
for the overloads with a parameter
pred
and no parameter
proj1
;bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))
for the overloads with parameters
pred
and
proj1
.2 Effects: Finds an element that matches one of a set of values.
3
Returns: The first iterator
i
in the range [first1, last1)
such that for some iterator j
in the
range [first2, last2)
E
holds. Returns
last1
if [first2, last2)
is empty or if no such iterator is found.
4
Complexity: At most (last1-first1) * (last2-first2)
applications of the corresponding predicate and any projections.
adjacent_find
in [alg.adjacent.find]template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>,
indirect_binary_predicate<I, Proj>> Pred = ranges::equal_to>
projectedconstexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>,
indirect_binary_predicate<iterator_t<R>, Proj>> Pred = ranges::equal_to>
projectedconstexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_binary_predicate<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to>
I ranges::adjacent_find(Ep&& exec, I first, S last, Pred pred = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_binary_predicate<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred
= ranges::equal_to> borrowed_iterator_t<R> ranges::adjacent_find(Ep&& exec, R&& r, Pred pred = {}, Proj proj = {});
1
Let E
be:
*i == *(i + 1)
for the overloads with no parameter
pred
;pred(*i, *(i + 1)) != false
for the overloads with a parameter
pred
and no parameter
proj
;bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))
for the overloads with both parameters
pred
and
proj
.2
Returns: The first iterator
i
such that both
i
and i + 1
are in the range [first, last)
for which E
holds. Returns
last
if no such iterator is
found.
3
Complexity: For the overloads with no execution policy,
exactly ExecutionPolicy
min((i - first) + 1, (last - first) - 1)
applications of the corresponding predicate, where
i
is
adjacent_find
’s return value. For
the overloads with an execution policy,
ExecutionPolicy
O(last - first)
applications of the corresponding predicate, and no. No more than twice as many
applications of any projection.
count
in [alg.count]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr iter_difference_t<I>
::count(I first, S last, const T& value, Proj proj = {});
rangestemplate<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr range_difference_t<R>
::count(R&& r, const T& value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
iter_difference_t<I> ranges::count(Ep&& exec, I first, S last, const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> range_difference_t<R> ranges::count(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr iter_difference_t<I>
::count_if(I first, S last, Pred pred, Proj proj = {});
rangestemplate<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr range_difference_t<R>
::count_if(R&& r, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
iter_difference_t<I> ranges::count_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> range_difference_t<R> ranges::count_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be:
*i == value
for the overloads with no parameter
pred
or
proj
;pred(*i) != false
for the overloads with a parameter
pred
but no parameter
proj
;invoke(proj, *i) == value
for the overloads with a parameter
proj
but no parameter
pred
;bool(invoke(pred, invoke(proj, *i)))
for the overloads with both parameters
proj
and
pred
.2
Effects: Returns the number of iterators
i
in the range [first, last)
for which E
holds.
3
Complexity: Exactly
last - first
applications of the corresponding predicate and any projection.
mismatch
in [alg.mismatch]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr ranges::mismatch_result<I1, I2>
::mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
ranges= {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, input_range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
::mismatch(R1&& r1, R2&& r2, Pred pred = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
ranges::mismatch_result<I1, I2>
ranges::mismatch(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::mismatch(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let last2
be first2 + (last1 - first1)
for the overloads with no parameter
last2
or
r2
.
2
Let E
be:
!(*(first1 + n) == *(first2 + n))
for the overloads with no parameter
pred
;pred(*(first1 + n), *(first2 + n)) == false
for the overloads with a parameter
pred
and no parameter
proj1
;!invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n)))
for the overloads with both parameters
pred
and
proj1
.3
Let N
be min(last1 - first1, last2 - first2)
.
4
Returns: { first1 + n, first2 + n }
,
where n
is the smallest integer in
[0, N)
such that E
holds, or
N
if no such integer
exists.
5
Complexity: At most
N
applications of the
corresponding predicate and any projections.
equal
in [alg.equal]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
= {},
Pred pred = {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, input_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
bool ranges::equal(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
bool ranges::equal(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1 Let:
(1.1)
last2
be first2 + (last1 - first1)
for the overloads with no parameter
last2
or
r2
;
(1.2)
pred
be
equal_to{}
for the overloads with no parameter
pred
;
(1.3)
E
be:
2
Returns: If last1 - first1 != last2 - first2
,
return
false
.
Otherwise return
true
if
E
holds for every iterator
i
in the range [first1, last1)
.
Otherwise, returns
false
.
3 Complexity: If
first1
,
last1
,
first2
, and
last2
meet the
Cpp17RandomAccessIterator requirements ([random.access.iterators])
and last1 - first1 != last2 - first2
for the overloads in namespace
std
;first1
,
last1
,
first2
, and
last2
pairwise model
sized_sentinel_for
([iterator.concept.sizedsentinel])
and last1 - first1 != last2 - first2
for the first overload in namespace
ranges
,R1
and
R2
each model
sized_range
and ranges::distance(r1) != ranges::distance(r2)
for the second overload in namespace
ranges
,then no applications of the corresponding predicate and each projection; otherwise,
ExecutionPolicy
min(last1 - first1, last2 - first2)
applications of the corresponding predicate and any projections.ExecutionPolicy
O(min(last1 - first1, last2 - first2))
applications of the corresponding predicate.search
in [alg.search]template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
<I2> S2, class Pred = ranges::equal_to,
sentinel_forclass Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
ranges= {}, Proj2 proj2 = {});
Proj1 proj1 template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr borrowed_subrange_t<R1>
::search(R1&& r1, R2&& r2, Pred pred = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
subrange<I1>
ranges::search(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
borrowed_subrange_t<R1>
ranges::search(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
3 Returns:
{i, i + (last2 - first2)}
,
where i
is the first iterator in the
range [first1, last1 - (last2 - first2))
such that for every non-negative integer
n
less than last2 - first2
the
condition bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
is
true
.{last1, last1}
if no such iterator exists.4
Complexity: At most (last1 - first1) * (last2 - first2)
applications of the corresponding predicate and projections.
template<forward_iterator I, sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirectly_comparable<I, const T*, Pred, Proj>
constexpr subrange<I>
::search_n(I first, S last, iter_difference_t<I> count,
rangesconst T& value, Pred pred = {}, Proj proj = {});
template<forward_range R, class Pred = ranges::equal_to,
class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
constexpr borrowed_subrange_t<R>
::search_n(R&& r, range_difference_t<R> count,
rangesconst T& value, Pred pred = {}, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Pred = ranges::equal_to, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirectly_comparable<I, const T*, Pred, Proj>
subrange<I>
ranges::search_n(Ep&& exec, I first, S last, iter_difference_t<I> count,
const T& value, Pred pred = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Pred = ranges::equal_to,
class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
borrowed_subrange_t<R>
ranges::search_n(Ep&& exec, R&& r, range_difference_t<R> count, const T& value, Pred pred = {}, Proj proj = {});
9
Returns: {i, i + count}
where i
is the first iterator in the
range [first, last - count)
such that for every non-negative integer
n
less than
count
, the following condition
holds: invoke(pred, invoke(proj, *(i + n)), value)
.
Returns {last, last}
if no such iterator is found.
10
Complexity: At most
last - first
applications of the corresponding predicate and projection.
starts_with
in [alg.starts.with]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr bool ranges::starts_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
= {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr bool ranges::starts_with(R1&& r1, R2&& r2, Pred pred = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
Returns: ranges::mismatch(std::move(first1), last1, std::move(first2), last2, pred, proj1, proj2).in2 == last2
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
bool ranges::starts_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2, class Pred = ranges::equal_to,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> bool ranges::starts_with(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Returns: ranges::mismatch(std::forward<Ep>(exec), std::move(first1), last1, std::move(first2), last2, pred, proj1, proj2).in2 == last2
ends_with
in [alg.ends.with]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires (forward_iterator<I1> || sized_sentinel_for<S1, I1>) &&
(forward_iterator<I2> || sized_sentinel_for<S2, I2>) &&
<I1, I2, Pred, Proj1, Proj2>
indirectly_comparableconstexpr bool ranges::ends_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
Let N1
be last1 - first1
and
N2
be last2 - first2
.
Returns:
false
if
N1 < N2
,
otherwise ranges::equal(std::move(first1) + (N1 - N2), last1, std::move(first2), last2, pred, proj1, proj2)
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
bool ranges::ends_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Let N1
be
last1 - first1
and
N2
be
last2 - first2
.
Returns: false
if
N1 < N2
, otherwise ranges::equal(std::forward<Ep>(exec), std::move(first1) + (N1 - N2), last1, std::move(first2), last2, pred, proj1, proj2)
template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,
class Proj2 = identity>
requires (forward_range<R1> || sized_range<R1>) &&
(forward_range<R2> || sized_range<R2>) &&
<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
indirectly_comparableconstexpr bool ranges::ends_with(R1&& r1, R2&& r2, Pred pred = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
Let N1
be ranges::distance(r1)
and N2
be ranges::distance(r2)
.
Returns:
false
if
N1 < N2
,
otherwise ranges::equal(views::drop(ranges::ref_view(r1), N1 - static_cast<decltype(N1)>(N2)), r2, pred, proj1, proj2)
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
bool ranges::ends_with(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Let N1
be
ranges::distance(r1)
and
N2
be
ranges::distance(r2)
.
Returns: false
if
N1 < N2
, otherwise ranges::equal(std::forward<Ep>, views::drop(ranges::ref_view(r1), N1 - static_cast<decltype(N1)>(N2)), r2, pred, proj1, proj2)
copy
in [alg.copy]template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
(ExecutionPolicy&& policy,
ForwardIterator2 copy
ForwardIterator1 first, ForwardIterator1 last,); ForwardIterator2 result
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>
requires indirectly_copyable<I, O>
ranges::copy_result<I, O> ranges::copy(Ep&& exec, I first, S last, O result, OutS result_last);
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
ranges::copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::copy(Ep&& exec, R&& r, OutR&& result_r);
x
Let result_last
be
result + (last - first)
for the
overloads with no parameter
result_last
or
result_r
.
x
Let N
be min(last - first, result_last - result)
.
6
Preconditions: The ranges [first,
and lastfirst + N)[result, result +
do not overlap.N)(last - first)
7
Effects: Copies elements in the range [first,
into the range lastfirst + N)[result, result +
.
For each non-negative integer N)(last - first)
n <
,
performs N(last - first)
*(result + n) = *(first + n)
.
8
Returns:result + (last - first)
.
9
Complexity: Exactly
assignments.(last - first)N
template<input_iterator I, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr ranges::copy_n_result<I, O>
::copy_n(I first, iter_difference_t<I> n, O result); ranges
template<execution-policy Ep, random_access_iterator I, random_access_iterator O,
sized_sentinel_for<O> OutS>
requires indirectly_copyable<I, O>
ranges::copy_n_result<I, O> ranges::copy_n(Ep&& exec, I first, iter_difference_t<I> n, O result, OutS result_last);
x
Let result_last
be
result + (last - first)
for the
overloads with no parameter
result_last
.
10 Let
N
be max(0,
.nmin(n, result_last - result)
)
11
Mandates: The type Size
is
convertible to an integral type ([conv.integral],
[class.conv]).
12
Effects: For each non-negative integer
i
<
N
, performs *(result + i) = *(first + i)
.
13 Returns:
result + N
for the overloads in namespace
std
.{first + N, result + N}
for the overloads in namespace
ranges
.14
Complexity: Exactly
N
assignments.
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicaterequires indirectly_copyable<I, O>
constexpr ranges::copy_if_result<I, O>
::copy_if(I first, S last, O result, Pred pred, Proj proj = {});
rangestemplate<input_range R, weakly_incrementable O, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires indirectly_copyable<iterator_t<R>, O>
constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O>
::copy_if(R&& r, O result, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
ranges::copy_if_result<I, O>
ranges::copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random_access_iterator OutR,
class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
ranges::copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
15 Let
E
be:
bool(pred(*i))
for the overloads
in namespace std
;bool(invoke(pred, invoke(proj, *i)))
for the overloads in namespace
ranges
,and N
be the number
of iterators i
in the range
[first, last)
for which the
condition E
holds.
x Let:
16
Preconditions: The ranges [first, last)
and [result, result +
do not overlap.N)(last - first)
[Note 1: For the overload with an
ExecutionPolicy
, there might be a
performance cost if iterator_traits<ForwardIterator1>::value_type
is not Cpp17MoveConstructible (Table 31). For the overloads with an
execution-policy
,
there might be a performance cost if
iter_value_t<I>
is not
move_constructible
.
— end note]
17
Effects: Copies all of theN
elements referred to by the iterator
i
in the range [first, last)
for which E
is
true
into the range
[result, result + N)
.
18 Returns:
result + N
for the overloads in namespace
std
.{lastj, result + N}
for the overloads in namespace
ranges
, where the iterator
j
points to a
position in the range
[first, last)
past
the last copied element if
result + N == result_last
,
and j == last
otherwise.19
Complexity: ExactlyAt most
last - first
applications of the corresponding predicate and any projection.
20 Remarks: Stable ([algorithm.stable]).
move
in [alg.move]template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
(ExecutionPolicy&& policy,
ForwardIterator2 move
ForwardIterator1 first, ForwardIterator1 last,); ForwardIterator2 result
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>
requires indirectly_movable<I, O>
ranges::move_result<I, O> ranges::move(Ep&& exec, I first, S last, O result, OutS result_last);
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
requires indirectly_movable<iterator_t<R>, iterator_t<OutR>>
ranges::move_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::move(Ep&& exec, R&& r, OutR&& result_r);
x
Let E
be:
std::move(*(first + n))
for the overload in namespace
std
;ranges::iter_move(first + n)
for the overloads in namespace
ranges
.x
Let result_last
be
result + (last - first)
for the
overloads with no parameter
result_last
or
result_r
.
6
Let N
be min(last - first
., result_last - result)
7
Preconditions: The ranges [first,
and lastfirst + N)[result, result + N)
do not overlap.
8
Effects: Moves elements in the range [first,
into the range lastfirst + N)[result, result + N)
.
For each non-negative integer n < N
,
performs *(result + n) =
.Estd::move(*(first + _n_))
9
Returns:result + N
.
10
Complexity: Exactly
N
assignments.
swap_ranges
in [alg.swap]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2>
requires indirectly_swappable<I1, I2>
constexpr ranges::swap_ranges_result<I1, I2>
::swap_ranges(I1 first1, S1 last1, I2 first2, S2 last2);
rangestemplate<input_range R1, input_range R2>
requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
constexpr ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
::swap_ranges(R1&& r1, R2&& r2); ranges
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2>
requires indirectly_swappable<I1, I2>
ranges::swap_ranges_result<I1, I2>
ranges::swap_ranges(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2);
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2>
requires indirectly_swappable<iterator_t<R1>, iterator_t<R2>>
ranges::swap_ranges_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::swap_ranges(Ep&& exec, R1&& r1, R2&& r2);
1 Let:
last2
be first2 + (last1 - first1)
for the overloads with no parameter named
last2
;M
be min(last1 - first1, last2 - first2)
.2
Preconditions: The two ranges [first1, last1)
and [first2, last2)
do not overlap. For the overloads in namespace
std
, *(first1 + n)
is swappable with ([swappable.requirements])
*(first2 + n)
.
3
Effects: For each non-negative integer n < M
performs:
swap(*(first1 + n), *(first2 + n))
for the overloads in namespace
std
;ranges::iter_swap(first1 + n, first2 + n)
for the overloads in namespace
ranges
.4 Returns:
last2
for the overloads in namespace
std
.{first1 + M, first2 + M}
for the overloads in namespace
ranges
.5
Complexity: Exactly
M
swaps.
transform
in [alg.transform]template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity>
copy_constructible F, requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
constexpr ranges::unary_transform_result<I, O>
::transform(I first1, S last1, O result, F op, Proj proj = {});
rangestemplate<input_range R, weakly_incrementable O, copy_constructible F,
class Proj = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
constexpr ranges::unary_transform_result<borrowed_iterator_t<R>, O>
::transform(R&& r, O result, F op, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS,
copy_constructible F, class Proj = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I, Proj>>>
ranges::unary_transform_result<I, O>
ranges::transform(Ep&& exec, I first, S last, O result, OutS result_last,
F op, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
copy_constructible F, class Proj = identity>
requires indirectly_writable<iterator_t<OutR>, indirect_result_t<F&, projected<iterator_t<R>, Proj>>>
ranges::unary_transform_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::transform(Ep&& exec, R&& r, OutR&& result_r, F op, Proj proj = {});
template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Proj1 = identity,
weakly_incrementable O, copy_constructible F, class Proj2 = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>,
<I2, Proj2>>>
projectedconstexpr ranges::binary_transform_result<I1, I2, O>
::transform(I1 first1, S1 last1, I2 first2, S2 last2, O result,
ranges= {}, Proj2 proj2 = {});
F binary_op, Proj1 proj1 template<input_range R1, input_range R2, weakly_incrementable O,
class Proj1 = identity, class Proj2 = identity>
copy_constructible F, requires indirectly_writable<O, indirect_result_t<F&, projected<iterator_t<R1>, Proj1>,
<iterator_t<R2>, Proj2>>>
projectedconstexpr ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
::transform(R1&& r1, R2&& r2, O result,
ranges= {}, Proj2 proj2 = {}); F binary_op, Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS,
copy_constructible F, class Proj1 = identity, class Proj2 = identity>
requires indirectly_writable<O, indirect_result_t<F&, projected<I1, Proj1>, projected<I2, Proj2>>>
ranges::binary_transform_result<I1, I2, O>
ranges::transform(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result,
OutS result_last, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2, random-access-sized-range OutR,
copy_constructible F, class Proj1 = identity, class Proj2 = identity>
requires indirectly_writable<iterator_t<OutR>,
indirect_result_t<F&, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>>>
ranges::binary_transform_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
ranges::transform(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {});
1 Let:
last2
be first2 + (last1 - first1)
for the overloads with parameter
first2
but no parameter
last2
;NM
be last1 - first1
for
unary transforms, or min(last1 - first1, last2 - first2)
for binary transforms;(1.3)
E
be
op(*(first1 + (i - result)))
for unary transforms defined in namespace
std
;binary_op(*(first1 + (i - result)), *(first2 + (i - result)))
for binary transforms defined in namespace
std
;invoke(op, invoke(proj, *(first1 + (i - result))))
for unary transforms defined in namespace
ranges
;invoke(binary_op, invoke(proj1, *(first1 + (i - result))), invoke(proj2, *(first2 + (i - result))))
for binary transforms defined in namespace
ranges
.2
Preconditions: op
and
binary_op
do not invalidate
iterators or subranges, nor modify elements in the ranges
3
Effects: Assigns through every iterator
i
in the range [result, result + N)
a new corresponding value equal to
E
.
4 Returns:
result + N
for the overloads defined in namespace
std
.{first1 + N, result + N}
for unary transforms defined in namespace
ranges
.{first1 + N, first2 + N, result + N}
for binary transforms defined in namespace
ranges
.5
Complexity: Exactly
N
applications of
op
or
binary_op
, and any projections.
This requirement also
applies to the overload with an
ExecutionPolicy
.
6
Remarks: result
may be
equal to first1
or
first2
.
replace
in [alg.replace]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T1 = projected_value_t<I, Proj>, class T2 = T1>
requires indirectly_writable<I, const T2&> &&
<ranges::equal_to, projected<I, Proj>, const T1*>
indirect_binary_predicateconstexpr I
::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
rangestemplate<input_range R, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
requires indirectly_writable<iterator_t<R>, const T2&> &&
<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
indirect_binary_predicateconstexpr borrowed_iterator_t<R>
::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T1 = projected_value_t<I, Proj>, class T2 = T1>
requires indirectly_writable<I, const T2&> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
I ranges::replace(Ep&& exec, I first, S last,
const T1& old_value, const T2& new_value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = T1>
requires indirectly_writable<iterator_t<R>, const T2&> &&
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
borrowed_iterator_t<R>
ranges::replace(Ep&& exec, R&& r, const T1& old_value, const T2& new_value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
<projected<I, Proj>> Pred>
indirect_unary_predicaterequires indirectly_writable<I, const T&>
constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {});
template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires indirectly_writable<iterator_t<R>, const T&>
constexpr borrowed_iterator_t<R>
::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>,
indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_writable<I, const T&>
I ranges::replace_if(Ep&& exec, I first, S last, Pred pred,
const T& new_value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_writable<iterator_t<R>, const T&>
borrowed_iterator_t<R>
ranges::replace_if(Ep&& exec, R&& r, Pred pred, const T& new_value, Proj proj = {});
1
Let E
be
bool(*i == old_value)
for replace
;bool(pred(*i))
for replace_if
;bool(invoke(proj, *i) == old_value)
for ranges::replace
;bool(invoke(pred, invoke(proj, *i)))
for ranges::replace_if
.2
Mandates: new_value
is
writable ([iterator.requirements.general])
to first
.
3
Effects: Substitutes elements referred by the iterator
i
in the range [first, last)
with new_value
, when
E
is
true
.
4
Returns: last
for the
overloads in namespace ranges
.
5
Complexity: Exactly
last - first
applications of the corresponding predicate and any projection.
template<input_iterator I, sentinel_for<I> S, class O,
class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<I, O> &&
<ranges::equal_to, projected<I, Proj>, const T1*> &&
indirect_binary_predicate<O, const T2&>
output_iteratorconstexpr ranges::replace_copy_result<I, O>
::replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
ranges= {});
Proj proj template<input_range R, class O, class Proj = identity,
class T1 = projected_value_t<iterator_t<R>, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<iterator_t<R>, O> &&
<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
indirect_binary_predicate&& output_iterator<O, const T2&>
constexpr ranges::replace_copy_result<borrowed_iterator_t<R>, O>
::replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
ranges= {}); Proj proj
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>,
class Proj = identity, class T1 = projected_value_t<I, Proj>, class T2 = iter_value_t<O>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*> &&
indirectly_writable<O, const T2&>
ranges::replace_copy_result<I, O>
ranges::replace_copy(Ep&& exec, I first, S last, O result, OutS result_last,
const T1& old_value, const T2& new_value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
class Proj = identity, class T1 = projected_value_t<iterator_t<R>, Proj>,
class T2 = range_value_t<OutR>>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*> &&
indirectly_writable<iterator_t<OutR>, const T2&>
ranges::replace_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
ranges::replace_copy(Ep&& exec, R&& r, OutR&& result_r, const T1& old_value, const T2& new_value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S,class O, class T = iter_value_t<O>,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O> && output_iterator<O, const T&>
constexpr ranges::replace_copy_if_result<I, O>
::replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
ranges= {});
Proj proj template<input_range R, class O, class T = iter_value_t<O>, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires indirectly_copyable<iterator_t<R>, O> && output_iterator<O, const T&>
constexpr ranges::replace_copy_if_result<borrowed_iterator_t<R>, O>
::replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
ranges= {}); Proj proj
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>, class T = iter_value_t<O>,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O> && indirectly_writable<O, const T&>
ranges::replace_copy_if_result<I, O>
ranges::replace_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
Pred pred, const T& new_value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
class T = range_value_t<OutR>, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
indirectly_writable<iterator_t<OutR>, const T&>
ranges::replace_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
ranges::replace_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, const T& new_value, Proj proj = {});
6
Let E
be
bool(*(first + (i - result)) == old_value)
for replace_copy
;bool(pred(*(first + (i - result))))
for replace_copy_if
;bool(invoke(proj, *(first + (i - result))) == old_value)
for ranges::replace_copy
;bool(invoke(pred, invoke(proj, *(first + (i - result)))))
for ranges::replace_copy_if
.x Let
7
Mandates: The results of the expressions
*first
and
new_value
are writable ([iterator.requirements.general])
to result
.
8
Preconditions: The ranges [first,
and lastfirst + N)[result, result +
do not overlap.N)(last - first)
9
Effects: Assigns through every iterator
i
in the range [result, result +
a new corresponding valueN)(last - first)
10 Returns:
result + (last - first)
N
for the overloads in namespace
std
.{last
first + N
, `result + (last - first)
N`}
for the overloads in namespace
ranges
.11
Complexity: Exactly last - first
N
applications of the corresponding predicate and any projection.
fill
in [alg.fill]template<class O, sentinel_for<O> S, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O ranges::fill(O first, S last, const T& value);
template<class R, class T = range_value_t<R>>
requires output_range<R, const T&>
constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);
template<class O, class T = iter_value_t<O>>
requires output_iterator<O, const T&>
constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);
template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S,
class T = iter_value_t<O>>
requires indirectly_writable<O, const T&>
O ranges::fill(Ep&& exec, O first, S last, const T& value);
template<execution-policy Ep, random-access-sized-range R, class T = range_value_t<R>>
requires indirectly_writable<iterator_t<R>, const T&>
borrowed_iterator_t<R> ranges::fill(Ep&& exec, R&& r, const T& value);
template<execution-policy Ep, random_access_iterator O, class T = iter_value_t<O>>
requires indirectly_writable<O, const T&> O ranges::fill_n(Ep&& exec, O first, iter_difference_t<O> n, const T& value);
1
Let N
be max(0, n)
for the fill_n
algorithms, and
last - first
for the fill
algorithms.
2
Mandates: The expression value is writable ([iterator.requirements.general])
to the output iterator. The type
Size
is convertible to an integral
type ([conv.integral],
[class.conv]).
3
Effects: Assigns value through all the iterators in the range
[first, first + N)
.
4
Returns: first + N
.
5
Complexity: Exactly
N
assignments.
generate
in [alg.generate]template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O ranges::generate(O first, S last, F gen);
template<class R, copy_constructible F>
requires invocable<F&> && output_range<R, invoke_result_t<F&>>
constexpr borrowed_iterator_t<R> ranges::generate(R&& r, F gen);
template<input_or_output_iterator O, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
constexpr O ranges::generate_n(O first, iter_difference_t<O> n, F gen);
template<execution-policy Ep, random_access_iterator O, sized_sentinel_for<O> S, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
O ranges::generate(Ep&& exec, O first, S last, F gen);
template<execution-policy Ep, random-access-sized-range R, copy_constructible F>
requires invocable<F&> && indirectly_writable<iterator_t<R>, invoke_result_t<F&>>
borrowed_iterator_t<R> ranges::generate(Ep&& exec, R&& r, F gen);
template<execution-policy Ep, random_access_iterator O, copy_constructible F>
requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>> O ranges::generate_n(Ep&& exec, O first, iter_difference_t<O> n, F gen);
1
Let N
be max(0, n)
for the generate_n
algorithms, and
last - first
for the generate
algorithms.
2
Mandates: Size
is
convertible to an integral type ([conv.integral],
[class.conv]).
3
Effects: Assigns the result of successive evaluations of
gen()
through each iterator in the range [first, first + N)
.
4
Returns: first + N
.
5
Complexity: Exactly
N
evaluations of
gen()
and
assignments.
remove
in [alg.remove]template<permutable I, sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
template<forward_range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires permutable<iterator_t<R>> &&
<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
indirect_binary_predicateconstexpr borrowed_subrange_t<R>
::remove(R&& r, const T& value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
class T = projected_value_t<I, Proj>>
requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
subrange<I> ranges::remove(Ep&& exec, I first, S last, const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires permutable<iterator_t<R>> &&
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> borrowed_subrange_t<R> ranges::remove(Ep&& exec, R&& r, const T& value, Proj proj = {});
template<permutable I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
::remove_if(R&& r, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_unary_predicate<projected<I, Proj>> Pred>
subrange<I> ranges::remove_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::remove_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let E
be
bool(*i == value)
for remove
;bool(pred(*i))
for remove_if
;bool(invoke(proj, *i) == value)
for ranges::remove
;bool(invoke(pred, invoke(proj, *i)))
for ranges::remove_if
.2
Preconditions: For the algorithms in namespace
std
, the type of
*first
meets
the Cpp17MoveAssignable requirements (Table 33).
3
Effects: Eliminates all the elements referred to by iterator
i
in the range [first, last)
for which E
holds.
4
Returns: Let j
be
the end of the resulting range. Returns:
5
Complexity: Exactly
last - first
applications of the corresponding predicate and any projection.
6 Remarks: Stable ([algorithm.stable]).
7
[Note 1: Each element in the range [ret, last)
,
where ret
is the returned value, has
a valid but unspecified state, because the algorithms can eliminate
elements by moving from elements that were originally in that range. —
end note]
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, class T = projected_value_t<I, Proj>>
requires indirectly_copyable<I, O> &&
<ranges::equal_to, projected<I, Proj>, const T*>
indirect_binary_predicateconstexpr ranges::remove_copy_result<I, O>
::remove_copy(I first, S last, O result, const T& value, Proj proj = {});
rangestemplate<input_range R, weakly_incrementable O, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_copyable<iterator_t<R>, O> &&
<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
indirect_binary_predicateconstexpr ranges::remove_copy_result<borrowed_iterator_t<R>, O>
::remove_copy(R&& r, O result, const T& value, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>,
class Proj = identity, class T = projected_value_t<I, Proj>>
requires indirectly_copyable<I, O> &&
indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
ranges::remove_copy_result<I, O>
ranges::remove_copy(Ep&& exec, I first, S last, O result, OutS result_last,
const T& value, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> &&
indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
ranges::remove_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::remove_copy(Ep&& exec, R&& r, OutR&& result_r, const T& value, Proj proj = {});
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
constexpr ranges::remove_copy_if_result<I, O>
::remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});
rangestemplate<input_range R, weakly_incrementable O, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires indirectly_copyable<iterator_t<R>, O>
constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O>
::remove_copy_if(R&& r, O result, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O>
ranges::remove_copy_if_result<I, O>
ranges::remove_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
ranges::remove_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::remove_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
8
Let E
be
bool(*i == value)
for remove_copy
;bool(pred(*i))
for remove_copy_if
;bool(invoke(proj, *i) == value)
for ranges::remove_copy
;bool(invoke(pred, invoke(proj, *i)))
for ranges::remove_copy_if
.9
Let N
be the number of
elements in [first, last)
for
which E
is
false
.
x Let
10
Mandates:
*first
is
writable ([iterator.requirements.general])
to result
.
11
Preconditions: The ranges [first, last)
and [result, result +
do not overlap.N)(last - first)
[Note 2: For the overloads with an
ExecutionPolicy
, there might be a
performance cost if iterator_traits<ForwardIterator1>::value_type
does not meet the Cpp17MoveConstructible (Table 31)
requirements. For the
overloads with an
execution-policy
,
there might be a performance cost if
iter_value_t<I>
is not
move_constructible
.
— end note]
12
Effects: Copies all theN
elements referred to by the iterator
i
in the range [first, last)
for which E
is
false
into the range
[result, result + N)
.
13 Returns:
result + N
,
for the algorithms in namespace
std
.{lastj, result + N}
,
for the algorithms in namespace
ranges
, where the iterator
j
points to a
position in the range
[first, last)
past
the last copied element if
result + N == result_last
,
and j == last
otherwise.14
Complexity: ExactlyAt most
last - first
applications of the corresponding predicate and any projection.
15 Remarks: Stable ([algorithm.stable]).
unique
in [alg.unique]template<permutable I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> C = ranges::equal_to>
indirect_equivalence_relationconstexpr subrange<I> ranges::unique(I first, S last, C comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
indirect_equivalence_relationrequires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
::unique(R&& r, C comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
requires permutable<I>
subrange<I> ranges::unique(Ep&& exec, I first, S last, C comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::unique(Ep&& exec, R&& r, C comp = {}, Proj proj = {});
1
Let pred
be
equal_to{}
for the overloads with no parameter
pred
, and let
E
be
bool(pred(*(i - 1), *i))
for the overloads in namespace
std
;bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))
for the overloads in namespace
ranges
.2
Preconditions: For the overloads in namespace
std
,
pred
is an equivalence relation and
the type of
*first
meets
the Cpp17MoveAssignable requirements (Table 33).
3
Effects: For a nonempty range, eliminates all but the first
element from every consecutive group of equivalent elements referred to
by the iterator i
in the range [first + 1, last)
for which E
is
true
.
4
Returns: Let j
be
the end of the resulting range. Returns:
5
Complexity: For nonempty ranges, exactly (last - first) - 1
applications of the corresponding predicate and no more than twice as
many applications of any projection.
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
<projected<I, Proj>> C = ranges::equal_to>
indirect_equivalence_relationrequires indirectly_copyable<I, O> &&
(forward_iterator<I> ||
(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
<I, O>)
indirectly_copyable_storableconstexpr ranges::unique_copy_result<I, O>
::unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});
rangestemplate<input_range R, weakly_incrementable O, class Proj = identity,
<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
indirect_equivalence_relationrequires indirectly_copyable<iterator_t<R>, O> &&
(forward_iterator<iterator_t<R>> ||
(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
<iterator_t<R>, O>)
indirectly_copyable_storableconstexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O>
::unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>, class Proj = identity,
indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
requires indirectly_copyable<I, O>
ranges::unique_copy_result<I, O>
ranges::unique_copy(Ep&& exec, I first, S last, O result, OutS result_last,
C comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR,
class Proj = identity,
indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
ranges::unique_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
ranges::unique_copy(Ep&& exec, R&& r, OutR&& result_r, C comp = {}, Proj proj = {});
6
Let pred
be
equal_to{}
for the overloads in namespace std
with no parameter pred
, and let
E
be
bool(pred(*i, *(i - 1)))
for the overloads in namespace
std
;bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))
for the overloads in namespace
ranges
.Let
7
Mandates:
*first
is
writable ([iterator.requirements.general])
to result
.
8 Preconditions:
(8.1) The
ranges [first, last)
and [result, result +
do not overlap.N)(last - first)
(8.2) For
the overloads in namespace std
:
(8.2.1) The comparison function is an equivalence relation.
(8.2.2)
For the overloads with no
ExecutionPolicy
, let
T
be the value type of
InputIterator
. If
InputIterator
models
forward_iterator
([iterator.concept.forward]),
then there are no additional requirements for
T
. Otherwise, if
OutputIterator
meets the
Cpp17ForwardIterator requirements and its value type is the
same as T
, then
T
meets the
Cpp17CopyAssignable (Table 34) requirements. Otherwise,
T
meets both the
Cpp17CopyConstructible (Table 32) and
Cpp17CopyAssignable requirements.
[Note 1: For
the overloads with an
ExecutionPolicy
,
there might be a performance cost if the value type of
ForwardIterator1
does not meet both the Cpp17CopyConstructible and
Cpp17CopyAssignable requirements. — end
note]
[Note 1: For
the overloads with an
ExecutionPolicy
,
there might be a performance cost if the value type of
ForwardIterator1
does not meet both the Cpp17CopyConstructible and
Cpp17CopyAssignable requirements. For the overloads with an
execution-policy
,
there might be a performance cost if
iter_value_t<I>
does not meet both the
copy_constructible
and
copy_assignable
. —
end note]
9
Effects: Copies only the first element from everyN
consecutive groups of equal elements referred to
by the iterator i
in the range [first, last)
for which E
holds into a range
[result, result + N)
.
10 Returns:
result + N
for the overloads in namespace
std
.{lastj, result + N}
for the overloads in namespace
ranges
, where the iterator
j
points to a
position in the range
[first, last)
past
the last copied element if
result + N == result_last
,
and j == last
otherwise.11
Complexity: ExactlyAt most last - first - 1
applications of the corresponding predicate and no more than twice as
many applications of any projection.
reverse
in [alg.reverse]template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I>
constexpr I ranges::reverse(I first, S last);
template<bidirectional_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
requires permutable<I>
I ranges::reverse(Ep&& exec, I first, S last);
template<execution-policy Ep, random-access-sized-range R>
requires permutable<iterator_t<R>> borrowed_iterator_t<R> ranges::reverse(Ep&& exec, R&& r);
1
Preconditions: For the overloads in namespace
std
,
BidirectionalIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements]).
2
Effects: For each non-negative integer i < (last - first) / 2
,
applies std::iter_swap
, or
ranges::iter_swap
for the overloads in namespace
ranges
, to all pairs of iterators
first + i
,
(last - i) - 1
.
3
Returns: last
for the
overloads in namespace ranges
.
4
Complexity: Exactly (last - first)/2
swaps.
template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
requires indirectly_copyable<I, O>
constexpr ranges::reverse_copy_result<I, O>
::reverse_copy(I first, S last, O result);
rangestemplate<bidirectional_range R, weakly_incrementable O>
requires indirectly_copyable<iterator_t<R>, O>
constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O>
::reverse_copy(R&& r, O result); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O, sized_sentinel_for<O> OutS>
requires indirectly_copyable<I, O>
ranges::reverse_copy_result<I, O>
ranges::reverse_copy(Ep&& exec, I first, S last, O result, OutS result_last);
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
ranges::reverse_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::reverse_copy(Ep&& exec, R&& r, OutR&& result_r);
x
Let result_last
be
result + (last - first)
for the
overloads with no parameter
result_last
or
result_r
.
5
Let N
be last - first
min(last - first, result_last - result)
.
x
Let NEW_FIRST
be
first + (last - first) - N
.
6
Preconditions: The ranges [
and firstNEW_FIRST, last)[result, result + N)
do not overlap.
7
Effects: Copies the range [
to the range firstNEW_FIRST, last)[result, result + N)
such that for every non-negative integer
i < N
the following assignment takes place: *(result + N - 1 - i) = *(
.firstNEW_FIRST + i)
8 Returns:
result + N
for the overloads in namespace
std
.{lastNEW_FIRST
, result + N}
for the overloads in namespace
ranges
.9
Complexity: Exactly
N
assignments.
rotate
in [alg.rotate]template<permutable I, sentinel_for<I> S>
constexpr subrange<I> ranges::rotate(I first, I middle, S last);
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
requires permutable<I> subrange<I> ranges::rotate(Ep&& exec, I first, I middle, S last);
1
Preconditions: [first, middle)
and [middle, last)
are valid ranges. For the overloads in namespace
std
,
ForwardIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements]),
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
2
Effects: For each non-negative integer i < (last - first)
,
places the element from the position
first + i
into position first + (i + (last - middle)) % (last - first)
.
[Note 1: This is a left rotate. — end note]
3 Returns:
first + (last - middle)
for the overloads in namespace
std
.{first + (last - middle), last}
for the overload in namespace
ranges
.4
Complexity: At most
last - first
swaps.
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> ranges::rotate(R&& r, iterator_t<R> middle);
Effects: Equivalent to: return ranges::rotate(ranges::begin(r), middle, ranges::end(r));
template<execution-policy Ep, random-access-sized-range R>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::rotate(Ep&& exec, R&& r, iterator_t<R> middle);
Effects: Equivalent to: return ranges::rotate(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::end(r));
shift
in [alg.shift]template<permutable I, sentinel_for<I> S>
constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n)
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
requires permutable<I>
subrange<I> ranges::shift_left(Ep&& exec, I first, S last, iter_difference_t<I> n);
template<execution-policy Ep, random-access-sized-range R>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::shift_left(Ep&& exec, R&& r, range_difference_t<R> n);
1
Preconditions: n >= 0
is true
. For
the overloads in namespace std
, the
type of
*first
meets
the Cpp17MoveAssignable requirements.
2
Effects: If n == 0
or n >= last - first
,
does nothing. Otherwise, moves the element from position first + n + i
into position
first + i
for each non-negative integer i < (last - first) - n
.
For the overloads without an execution policy, does so in
order starting from ExecutionPolicy
template parameteri = 0
and proceeding to i = (last - first) - n - 1
.
3
Returns: Let
NEW_LAST
be first + (last - first - n)
if n < last - first
,
otherwise first
.
NEW_LAST
for the overloads
in namespace std
.{first, NEW_LAST}
for the overloads in namespace
ranges
.4
Complexity: At most (last - first) - n
assignments.
template<permutable I, sentinel_for<I> S>
constexpr subrange<I> ranges::shift_right(I first, S last, iter_difference_t<I> n);
template<forward_range R>
requires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> ranges::shift_right(R&& r, range_difference_t<R> n);
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S>
requires permutable<I>
subrange<I> ranges::shift_right(Ep&& exec, I first, S last, iter_difference_t<I> n);
template<execution-policy Ep, random-access-sized-range R>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::shift_right(Ep&& exec, R&& r, range_difference_t<R> n);
5
Preconditions: n >= 0
is true
. For
the overloads in namespace std
, the
type of
*first
meets
the Cpp17MoveAssignable requirements, and
ForwardIterator
meets the
Cpp17BidirectionalIterator requirements ([bidirectional.iterators])
or the Cpp17ValueSwappable requirements.
6
Effects: If n == 0
or n >= last - first
,
does nothing. Otherwise, moves the element from position
first + i
into position first + n + i
for each non-negative integer i < (last - first) - n
.
Does so in order starting from i = (last - first) - n - 1
and proceeding to i = 0
if
std
without an ExecutionPolicy
template
parameter, ForwardIterator
meets the
Cpp17BidirectionalIterator requirements,ranges
without an
execution-policy
,
I
models
bidirectional_iterator
.7
Returns: Let
NEW_FIRST
be
first + n
if
n < last - first
,
otherwise last
.
NEW_FIRST
for the overloads
in namespace std
.{NEW_FIRST, last}
for the overloads in namespace
ranges
.8
Complexity: At most (last - first) - n
assignments or swaps.
sort
in [sort]template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
::sort(I first, S last, Comp comp = {}, Proj proj = {});
rangestemplate<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
::sort(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
I ranges::sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
1
Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: For the overloads in namespace
std
,
RandomAccessIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements])
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
3
Effects: Sorts the elements in the range [first, last)
with respect to comp
and
proj
.
4
Returns: last
for the
overloads in namespace ranges
.
5
Complexity: Let N
be
last - first
.
O(NlogN)
comparisons and projections.
stable_sort
in [stable.sort]template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
I ranges::stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
1
Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: For the overloads in namespace
std
,
RandomAccessIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements])
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
3
Effects: Sorts the elements in the range [first, last)
with respect to comp
and
proj
.
4
Returns: last
for the
overloads in namespace ranges
.
5
Complexity: Let N
be
last - first
.
If enough extra memory is available, Nlog(N)
comparisons. Otherwise, at most Nlog2(N)
comparisons. In either case, twice as many projections as the number of
comparisons.
6 Remarks: Stable ([algorithm.stable]).
partial_sort
in [partial.sort]template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj> I ranges::partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
1
Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: [first, middle)
and [middle, last)
are valid ranges. For the overloads in namespace
std
,
RandomAccessIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements])
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
3
Effects: Places the first middle - first
elements from the range [first, last)
as sorted with respect to comp
and
proj
into the range [first, middle)
.
The rest of the elements in the range [middle, last)
are placed in an unspecified order.
4
Returns: last
for the
overload in namespace ranges
.
5
Complexity: Approximately (last - first) * log(middle - first)
comparisons, and twice as many projections.
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {}); ranges
Effects: Equivalent to: return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
borrowed_iterator_t<R> ranges::partial_sort(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::partial_sort(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::end(r), comp, proj);
partial_sort_copy
in [partial.sort.copy]template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
indirect_strict_weak_orderconstexpr ranges::partial_sort_copy_result<I1, I2>
::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Comp comp template<input_range R1, random_access_range R2, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
<iterator_t<R2>, Comp, Proj2> &&
sortable<Comp, projected<iterator_t<R1>, Proj1>,
indirect_strict_weak_order<iterator_t<R2>, Proj2>>
projectedconstexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
ranges::partial_sort_copy_result<I1, I2>
ranges::partial_sort_copy(Ep&& exec, I1 first, S1 last, I2 result_first, S2 result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
sortable<iterator_t<R2>, Comp, Proj2> &&
indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>>
ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
ranges::partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let N
be min(last - first, result_last - result_first)
.
Let comp
be
less{}
, and
proj1
and
proj2
be
identity{}
for the overloads with no parameters by those names.
2
Mandates: For the overloads in namespace
std
, the expression
*first
is
writable ([iterator.requirements.general])
to result_first
.
3
Preconditions: For the overloads in namespace
std
,
RandomAccessIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements]),
the type of *result_first
meets the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
4
For iterators a1
and
b1
in [first, last)
,
and iterators x2
and
y2
in [result_first, result_last)
,
after evaluating the assignment *y2 = *b1
,
let E
be the value of
bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2)))
.
Then, after evaluating the assignment *x2 = *a1
,
E
is equal to
bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2)))
.
[Note 1: Writing a value from the input range into the
output range does not affect how it is ordered by
comp
and
proj1
or
proj2
. — end note]
5
Effects: Places the first
N
elements as sorted with
respect to comp
and
proj2
into the range [result_first, result_first + N)
.
6 Returns:
result_first + N
for the overloads in namespace
std
.{last, result_first + N}
for the overloads in namespace
ranges
.7
Complexity: Approximately (last - first) * logN
comparisons, and twice as many projections.
is_sorted
in [is.sorted]template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::is_sorted_until(first, last, comp, proj) == last;
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
bool ranges::is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> bool ranges::is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::is_sorted_until(std::forward<Ep>(exec), first, last, comp, proj) == last;
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr borrowed_iterator_t<R>
::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
I ranges::is_sorted_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> borrowed_iterator_t<R> ranges::is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
6 Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
7 Returns: The last iterator
i
in [first, last]
for which the range [first, i)
is sorted with respect to comp
and
proj
.
8 Complexity: Linear.
nth_element
in [alg.nth.element]template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj> I ranges::nth_element(Ep&& exec, I first, I nth, S last, Comp comp = {}, Proj proj = {});
1
Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: [first, nth)
and [nth, last)
are valid ranges. For the overloads in namespace
std
,
RandomAccessIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements]),
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
3
Effects: After nth_element
the element in the position pointed to by
nth
is the element that would be in
that position if the whole range were sorted with respect to
comp
and
proj
, unless
nth == last
.
Also for every iterator i
in the
range [first, nth)
and every iterator j
in the range
[nth, last)
it holds that: bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))
is
false
.
4
Returns: last
for the
overload in namespace ranges
.
5
Complexity: For the overloads with no execution policy,
linear on average. For the overloads with an ExecutionPolicy
execution policy,
ExecutionPolicy
O(N)
applications of the predicate, and O(NlogN)
swaps, where N = last - first
.
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {}); ranges
Effects: Equivalent to: return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
borrowed_iterator_t<R> ranges::nth_element(Ep&& exec, R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::nth_element(std::forward<Ep>(exec), ranges::begin(r), nth, ranges::end(r), comp, proj);
partitions
in [alg.partitions]template<input_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicateconstexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
bool ranges::is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> bool ranges::is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {});
1
Let proj
be
identity{}
for the overloads with no parameter named
proj
.
2
Returns:
true
if and
only if the elements e
of [first, last)
are partitioned with respect to the expression bool(invoke(pred, invoke(proj, e)))
.
3
Complexity: Linear. At most
last - first
applications of pred
and
proj
.
template<permutable I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicateconstexpr subrange<I>
::partition(I first, S last, Pred pred, Proj proj = {});
rangestemplate<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R>
::partition(R&& r, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
subrange<I> ranges::partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
4
Let proj
be
identity{}
for the overloads with no parameter named
proj
and let E(x)
be bool(invoke(pred, invoke(proj, x)))
.
5
Preconditions: For the overloads in namespace
std
,
ForwardIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements]).
6
Effects: Places all the elements
e
in [first, last)
that satisfy E(e)
before all the elements that do not.
7
Returns: Let i
be an
iterator such that E(*j)
is true
for
every iterator j
in [first, i)
and false
for every iterator j
in [i, last)
.
Returns:
8
Complexity: Let N = last - first
:
ExecutionPolicy
N
applications of
the predicate and projection. At most N / 2
swaps if the type of first
meets the
Cpp17BidirectionalIterator requirements for the overloads in
namespace std
or models
bidirectional_iterator
for the
overloads in namespace ranges
, and
at most N
swaps
otherwise.ExecutionPolicy
O(NlogN)
swaps and O(N)
applications of the predicate.template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Pred>
indirect_unary_predicaterequires permutable<I>
constexpr subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
template<bidirectional_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires permutable<iterator_t<R>>
constexpr borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires permutable<I>
subrange<I> ranges::stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
9
Let proj
be
identity{}
for the overloads with no parameter named
proj
and let E(x)
be bool(invoke(pred, invoke(proj, x)))
.
10
Preconditions: For the overloads in namespace
std
,
BidirectionalIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements])
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
11
Effects: Places all the elements
e
in [first, last)
that satisfy E(e)
before all the elements that do not. The relative order of the elements
in both groups is preserved.
12
Returns: Let i
be an
iterator such that for every iterator
j
in [first, i)
,
E(*j)
is true
, and
for every iterator j
in the range
[i, last)
,
E(*j)
is false
.
Returns:
i
for the overloads in namespace
std
.{i, last}
for the overloads in namespace
ranges
.13
Complexity: Let N = last - first
:
ExecutionPolicy
Nlog2N
swaps, but only O(N)
swaps if there is enough extra memory. Exactly
N
applications of the
predicate and projection.ExecutionPolicy
O(NlogN)
swaps and O(N)
applications of the predicate.template<input_iterator I, sentinel_for<I> S, weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
constexpr ranges::partition_copy_result<I, O1, O2>
::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
ranges= {});
Proj proj template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
class Proj = identity,
<projected<iterator_t<R>, Proj>> Pred>
indirect_unary_predicaterequires indirectly_copyable<iterator_t<R>, O1> &&
<iterator_t<R>, O2>
indirectly_copyableconstexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
random_access_iterator O1, sized_sentinel_for<O1> OutS1,
random_access_iterator O2, sized_sentinel_for<O2> OutS2,
class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
ranges::partition_copy_result<I, O1, O2>
ranges::partition_copy(Ep&& exec, I first, S last, O1 out_true, OutS1 last_true,
O2 out_false, OutS2 last_false, Pred pred, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, random-access-sized-range OutR1,
random-access-sized-range OutR2, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires indirectly_copyable<iterator_t<R>, iterator_t<OutR1>> &&
indirectly_copyable<iterator_t<R>, iterator_t<OutR2>>
ranges::partition_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR1>, borrowed_iterator_t<OutR2>>
ranges::partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r, Pred pred, Proj proj = {});
14 Let
proj
be
identity{}
for the overloads with no parameter named
proj
and let E(x)
be bool(invoke(pred, invoke(proj, x)))
.
15
Mandates: For the overloads in namespace
std
, the expression
*first
is
writable ([iterator.requirements.general])
to out_true
and
out_false
.
16 Preconditions: The input range and output ranges do not overlap.
[Note 1: For the overload with an
ExecutionPolicy
, there might be a
performance cost if first
’s value
type does not meet the Cpp17CopyConstructible requirements.
For the overloads with an
execution-policy
,
there might be a performance cost if
first
’s value type
does not meet the
copy_constructible
requirements. — end note.]
17
Effects: For each iterator
i
in [first, last)
,
copies *i
to
the output range beginning with
out_true
if E(*i)
is true
, or
to the output range beginning with
out_false
otherwise.
18
Returns: Let o1
be the end
of the output range beginning at
out_true
, and
o2
the end of the output range
beginning at out_false
. Returns
{o1, o2}
for the overloads in namespace
std
.{last, o1, o2}
for the overloads in namespace
ranges
.19
Complexity: Exactly
last - first
applications of pred
and
proj
.
merge
in [alg.merge]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less, class Proj1 = identity,
weakly_incrementable O, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr ranges::merge_result<I1, I2, O>
::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Comp comp template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
::merge(R1&& r1, R2&& r2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {}); Comp comp
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::merge_result<I1, I2, O>
ranges::merge(Ep&& exec, I1 first1, S1 last1,
I2 first2, S2 last2, O result, OutS result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
random-access-sized-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let N
be (last1 - first1) + (last2 - first2)
.
Let comp
be
less{}
,
proj1
be
identity{}
, and
proj2
be
identity{}
, for the overloads
with no parameters by those names.
x Let
M
be (last1 - first1) + (last2 - first2)
;comp
be
less{}
,
proj1
be
identity{}
, and
proj2
be
identity{}
, for the overloads
with no parameters by those names;result_last
be
result + M
for the
overloads with no parameter
result_last
or
result_r
;N
be
min(M, result_last - result)
;E
be bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))
;K
be the rightmost
position of an element e2
in
[first2, last2)
such that the
number of elements e1
in
[first1, last1)
for which
E
holds is less than or
equal to N - K
.2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively. The resulting
range does not overlap with either of the original ranges.
3
Effects: Copies
all the elements of the two ranges
Copies
[first1, last1)
and
[first2, last2)
into the range
[result, result_last)
,
where result_last
is
result + N
first1 + N - K
elements of the range
[first1, last1)
and
first2 + K
elements of the range
[first2, last2)
into the range [result,
result_lastresult + N
), where
.
If an element result_last
is
result + N
a
precedes
b
in an input range,
a
is copied into the output range
before b
. If
e1
is an element of [first1, last1)
and e2
of [first2, last2)
,
e2
is copied into the output range
before e1
if and only if bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))
E
is true
.
4 Returns:
result_last
for the overloads in
namespace std
.{last1, last2, result_last}
{first1 + N - K, first2 + K, result + N}
for the overloads in namespace
ranges
.5 Complexity:
ExecutionPolicy
N − 1
comparisons and applications of each projection.ExecutionPolicy
O(N)
comparisons and
applications of each projection.6 Remarks: Stable ([algorithm.stable]).
template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj> I ranges::inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
7
Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
8
Preconditions: [first, middle)
and [middle, last)
are valid ranges sorted with respect to
comp
and
proj
. For the overloads in namespace
std
,
BidirectionalIterator
meets the
Cpp17ValueSwappable requirements ([swappable.requirements])
and the type of
*first
meets
the Cpp17MoveConstructible (Table 31) and
Cpp17MoveAssignable (Table 33) requirements.
9
Effects: Merges two sorted consecutive ranges [first, middle)
and [middle, last)
,
putting the result of the merge into the range [first, last)
.
The resulting range is sorted with respect to
comp
and
proj
.
10
Returns: last
for the
overload in namespace ranges
.
11
Complexity: Let N = last - first
:
ExecutionPolicy
N − 1
comparisons.O(NlogN)
comparisons.In either case, twice as many projections as comparisons.
12 Remarks: Stable.
template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {}); ranges
Effects: Equivalent to: return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
template<execution-policy Ep, random-access-sized-range R, class Comp = ranges::less,
class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
borrowed_iterator_t<R> ranges::inplace_merge(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::inplace_merge(std::forward<Ep>(exec), ranges::begin(r), middle, ranges::end(r), comp, proj);
includes
in [includes]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
<projected<I1, Proj1>,
indirect_strict_weak_order<I2, Proj2>> Comp = ranges::less>
projectedconstexpr bool ranges::includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
= {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
<projected<iterator_t<R1>, Proj1>,
indirect_strict_weak_order<iterator_t<R2>, Proj2>> Comp = ranges::less>
projectedconstexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
bool ranges::includes(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
bool ranges::includes(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let comp
be
less{}
,
proj1
be
identity{}
,
and proj2
be
identity{}
,
for the overloads with no parameters by those names.
2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively.
3
Returns:
true
if and
only if [first2, last2)
is a subsequence of [first1, last1)
.
[Note 1: A sequence
S
is a subsequence of
another sequence T
if
S
can be obtained from
T
by removing some, all, or
none of T
’s elements and
keeping the remaining elements in the same order. — end
note]
4
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons and applications of each projection.
set_union
in [set.union]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less,
weakly_incrementable O, class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr ranges::set_union_result<I1, I2, O>
::set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
ranges= {}, Proj2 proj2 = {});
Proj1 proj1 template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::set_union_result<I1, I2, O>
ranges::set_union(Ep&& exec, I1 first1, S1 last1,
I2 first2, S2 last2, O result, OutS result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
random-access-sized-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
ranges::set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let comp
be
less{}
, and
proj1
and
proj2
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively. The resulting
range does not overlap with either of the original ranges.
3 Effects: Constructs a sorted union of the elements from the two ranges; that is, the set of elements that are present in one or both of the ranges.
4
Returns: Let result_last
be
the end of the constructed range. Returns
result_last
for the overloads in
namespace std
.{last1, last2, result_last}
for the overloads in namespace
ranges
.5
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons and applications of each projection.
6
Remarks: Stable ([algorithm.stable]).
If [first1, last1)
contains m
elements that
are equivalent to each other and [first2, last2)
contains n
elements that
are equivalent to them, then all
m
elements from the first
range are copied to the output range, in order, and then the final max(n − m, 0)
elements from the second range are copied to the output range, in
order.
set_intersection
in [set.intersection]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less,
weakly_incrementable O, class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr ranges::set_intersection_result<I1, I2, O>
::set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Comp comp template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
::set_intersection(R1&& r1, R2&& r2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {}); Comp comp
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::set_intersection_result<I1, I2, O>
ranges::set_intersection(Ep&& exec, I1 first1, S1 last1,
I2 first2, S2 last2, O result, OutS result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
random-access-sized-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
ranges::set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let comp
be
less{}
, and
proj1
and
proj2
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively. The resulting
range does not overlap with either of the original ranges.
3 Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.
4
Returns: Let result_last
be
the end of the constructed range. Returns
result_last
for the overloads in
namespace std
.{last1, last2, result_last}
for the overloads in namespace
ranges
.5
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons and applications of each projection.
6
Remarks: Stable ([algorithm.stable]).
If [first1, last1)
contains m
elements that
are equivalent to each other and [first2, last2)
contains n
elements that
are equivalent to them, the first min(m,n)
elements are copied from the first range to the output range, in
order.
set_difference
in [set.difference]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less,
weakly_incrementable O, class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr ranges::set_difference_result<I1, O>
::set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Comp comp template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
::set_difference(R1&& r1, R2&& r2, O result,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {}); Comp comp
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::set_difference_result<I1, O>
ranges::set_difference(Ep&& exec, I1 first1, S1 last1,
I2 first2, S2 last2, O result, OutS result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
random-access-sized-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::set_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<OutR>>
ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let comp
be
less{}
, and
proj1
and
proj2
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively. The resulting
range does not overlap with either of the original ranges.
3
Effects: Copies the elements of the range [first1, last1)
which are not present in the range [first2, last2)
to the range beginning at result
.
The elements in the constructed range are sorted.
4
Returns: Let result_last
be
the end of the constructed range. Returns
result_last
for the overloads in
namespace std
.{last1, result_last}
for the overloads in namespace
ranges
.5
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons and applications of each projection.
6
Remarks: If [first1, last1)
contains m
elements that
are equivalent to each other and [first2, last2)
contains n
elements that
are equivalent to them, the last max(m − n, 0)
elements from [first1, last1)
are copied to the output range, in order.
set_symmetric_difference
in [set.symmetric.difference]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Comp = ranges::less,
weakly_incrementable O, class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr ranges::set_symmetric_difference_result<I1, I2, O>
::set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
ranges= {}, Proj1 proj1 = {},
Comp comp = {});
Proj2 proj2 template<input_range R1, input_range R2, weakly_incrementable O,
class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
<R2>, O>
borrowed_iterator_t::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
ranges::set_symmetric_difference_result<I1, I2, O>
ranges::set_symmetric_difference(Ep&& exec, I1 first1, S1 last1,
I2 first2, S2 last2, O result, OutS result_last,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
random-access-sized-range OutR, class Comp = ranges::less,
class Proj1 = identity, class Proj2 = identity>
requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Let comp
be
less{}
, and
proj1
and
proj2
be
identity{}
for the overloads with no parameters by those names.
2
Preconditions: The ranges [first1, last1)
and [first2, last2)
are sorted with respect to comp
and
proj1
or
proj2
, respectively. The resulting
range does not overlap with either of the original ranges.
3
Effects: Copies the elements of the range [first1, last1)
that are not present in the range [first2, last2)
,
and the elements of the range [first2, last2)
that are not present in the range [first1, last1)
to the range beginning at result
.
The elements in the constructed range are sorted.
4
Returns: Let result_last
be
the end of the constructed range. Returns
result_last
for the
overloads in namespace std
.{last1, last2, result_last}
for the overloads in namespace
ranges
.5
Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
comparisons and applications of each projection.
6
Remarks: Stable ([algorithm.stable]).
If [first1, last1)
contains m
elements that
are equivalent to each other and [first2, last2)
contains n
elements that
are equivalent to them, then |m − n|
of those elements shall be copied to the output range: the last
m − n
of these
elements from [first1, last1)
if m > n
,
and the last n − m
of these elements from [first2, last2)
if m < n
.
In either case, the elements are copied in order.
is_heap
in [is.heap]template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr bool ranges::is_heap(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr bool ranges::is_heap(R&& r, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::is_heap_until(first, last, comp, proj) == last;
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
bool ranges::is_heap(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> bool ranges::is_heap(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
Effects: Equivalent to: return ranges::is_heap_until(std::forward<Ep>(exec), first, last, comp, proj) == last;
template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
template<random_access_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr borrowed_iterator_t<R>
::is_heap_until(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
I ranges::is_heap_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
borrowed_iterator_t<R> ranges::is_heap_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
6 Let comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
7 Returns: The last iterator
i
in [first, last]
for which the range [first, i)
is a heap with respect to comp
and
proj
.
8 Complexity: Linear.
min
,
max
,
minmax
in [alg.min.max]template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderrequires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R>
::min(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
range_value_t<R> ranges::min(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
5
Preconditions: ranges::distance(r) > 0
.
For the overloads in namespace std
,
T
meets the
Cpp17CopyConstructible requirements. For the first form,
T
meets the
Cpp17LessThanComparable requirements (Table 29).
6 Returns: The smallest value in the input range. Returns a copy of the leftmost element when several elements are equivalent to the smallest.
7
Complexity: Exactly ranges::distance(r) - 1
comparisons and twice as many applications of the projection, if
any.
8
Remarks: An invocation may explicitly specify an argument for
the template parameter T
of the
overloads in namespace std
.
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderrequires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr range_value_t<R>
::max(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
range_value_t<R> ranges::max(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
13
Preconditions: ranges::distance(r) > 0
.
For the overloads in namespace std
,
T
meets the
Cpp17CopyConstructible requirements. For the first form,
T
meets the
Cpp17LessThanComparable requirements (Table 29).
14 Returns: The largest value in the input range. Returns a copy of the leftmost element when several elements are equivalent to the largest.
15
Complexity: Exactly ranges::distance(r) - 1
comparisons and twice as many applications of the projection, if
any.
16
Remarks: An invocation may explicitly specify an argument for
the template parameter T
of the
overloads in namespace std
.
template<input_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderrequires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
constexpr ranges::minmax_result<range_value_t<R>>
::minmax(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
ranges::minmax_result<range_value_t<R>> ranges::minmax(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
21
Preconditions: ranges::distance(r) > 0
.
For the overloads in namespace std
,
T
meets the
Cpp17CopyConstructible requirements. For the first form, type
T
meets the
Cpp17LessThanComparable requirements (Table 29).
22
Returns: Let X
be the
return type. Returns X{x, y}
,
where x
is a copy of the leftmost
element with the smallest value and
y
a copy of the rightmost element
with the largest value in the input range.
23
Complexity: At most (3/2)ranges::distance(r)
applications of the corresponding predicate and twice as many
applications of the projection, if any.
24
Remarks: An invocation may explicitly specify an argument for
the template parameter T
of the
overloads in namespace std
.
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr borrowed_iterator_t<R>
::min_element(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
I ranges::min_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
borrowed_iterator_t<R> ranges::min_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
25 Let
comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
26
Returns: The first iterator
i
in the range [first, last)
such that for every iterator j
in
the range [first, last)
,
bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))
is false
.
Returns last
if first == last
.
27
Complexity: Exactly max(last - first - 1, 0)
comparisons and twice as many projections.
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {});
template<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr borrowed_iterator_t<R>
::max_element(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
I ranges::max_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
borrowed_iterator_t<R> ranges::max_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
28 Let
comp
be
less{}
and
proj
be
identity{}
for the overloads with no parameters by those names.
29
Returns: The first iterator
i
in the range [first, last)
such that for every iterator j
in
the range [first, last)
,
bool(invoke(comp, invoke(proj, *i), invoke(proj, *j)))
is false
.
Returns last
if first == last
.
30
Complexity: Exactly max(last - first - 1, 0)
comparisons and twice as many projections.
template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
<projected<I, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr ranges::minmax_element_result<I>
::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
rangestemplate<forward_range R, class Proj = identity,
<projected<iterator_t<R>, Proj>> Comp = ranges::less>
indirect_strict_weak_orderconstexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
::minmax_element(R&& r, Comp comp = {}, Proj proj = {}); ranges
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
class Proj = identity,
indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
ranges::minmax_element_result<I>
ranges::minmax_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
template<execution-policy Ep, random-access-sized-range R, class Proj = identity,
indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
ranges::minmax_element_result<borrowed_iterator_t<R>> ranges::minmax_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
31
Returns: {first, first}
if [first, last)
is empty, otherwise {m, M}
,
where m
is the first iterator in
[first, last)
such that no iterator in the range refers to a smaller element, and
where M
is the last
iterator209 in [first, last)
such that no iterator in the range refers to a larger element.
32
Complexity: Let N
be
last - first
.
At most
max(⌊
\(\frac{3}{2}\)(N − 1)⌋, 0)
comparisons and twice as many applications of the projection, if
any.
lexicographical_compare
in [alg.lex.comparison]template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
<projected<I1, Proj1>,
indirect_strict_weak_order<I2, Proj2>> Comp = ranges::less>
projectedconstexpr bool
::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
ranges= {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Comp comp template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
<projected<iterator_t<R1>, Proj1>,
indirect_strict_weak_order<iterator_t<R2>, Proj2>> Comp = ranges::less>
projectedconstexpr bool
::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
ranges= {}, Proj2 proj2 = {}); Proj1 proj1
template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
random_access_iterator I2, sized_sentinel_for<I2> S2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp = ranges::less>
bool ranges::lexicographical_compare(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
template<execution-policy Ep, random-access-sized-range R1, random-access-sized-range R2,
class Proj1 = identity, class Proj2 = identity,
indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
bool ranges::lexicographical_compare(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
Returns:
true
if and
only if the sequence of elements defined by the range [first1, last1)
is lexicographically less than the sequence of elements defined by the
range [first2, last2)
.
2
Complexity: At most 2 min(last1 - first1, last2 - first2)
applications of the corresponding comparison and each projection, if
any.
3 Remarks: If two sequences have the same number of elements and their corresponding elements (if any) are equivalent, then neither sequence is lexicographically less than the other. If one sequence is a proper prefix of the other, then the shorter sequence is lexicographically less than the longer sequence. Otherwise, the lexicographical comparison of the sequences yields the same result as the comparison of the first corresponding pair of elements that are not equivalent.
[ Example: ranges::lexicographical_compare(I1, S1, I2, S2, Comp, Proj1, Proj2)
can be implemented as:
for ( ; first1 != last1 && first2 != last2 ; ++first1, (void) ++first2) {
if (invoke(comp, invoke(proj1, *first1), invoke(proj2, *first2))) return true;
if (invoke(comp, invoke(proj2, *first2), invoke(proj1, *first1))) return false;
}
return first1 == last1 && first2 != last2;
5 [Note 1: An empty sequence is lexicographically less than any non-empty sequence, but not less than any empty sequence. — end note]
// [specialized.algorithms], specialized algorithms
// [special.mem.concepts], special memory conceptstemplate<class I>
concept nothrow-input-iterator = see below; // exposition only
template<class I>
concept nothrow-forward-iterator = see below; // exposition only
template<class I>
concept nothrow-bidirectional-iterator = see below; // exposition only
template<class I> concept nothrow-random-access-iterator = see below; // exposition only
template<class S, class I>
concept nothrow-sentinel-for = see below; // exposition only
template<class S, class I> concept nothrow-sized-sentinel-for = see below; // exposition only
template<class R>
concept nothrow-input-range = see below; // exposition only
template<class R>
concept nothrow-forward-range = see below; // exposition only
template<class I>
concept nothrow-bidirectional-range = see below; // exposition only
template<class I>
concept nothrow-random-access-range = see below; // exposition only
template<class I> concept nothrow-random-access-sized-range = see below; // exposition only
template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S>
requires default_initializable<iter_value_t<I>>
(I first, S last); // freestanding
I uninitialized_default_constructtemplate<nothrow-forward-range R>
requires default_initializable<range_value_t<R>>
<R> uninitialized_default_construct(R&& r); // freestanding
borrowed_iterator_t
template<nothrow-forward-iterator I>
requires default_initializable<iter_value_t<I>>
(I first, iter_difference_t<I> n); // freestanding I uninitialized_default_construct_n
template<execution-policy Ep, nothrow-random-access-iterator I, nothrow-sized-sentinel-for<I> S>
requires default_initializable<iter_value_t<I>>
I uninitialized_default_construct(Ep&& exec, I first, S last); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-sized-range R>
requires default_initializable<range_value_t<R>>
borrowed_iterator_t<R> uninitialized_default_construct(Ep&& exec, R&& r); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-iterator I>
requires default_initializable<iter_value_t<I>> I uninitialized_default_construct_n(Ep&& exec, I first, iter_difference_t<I> n); // see [algorithms.parallel.overloads]
template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S>
requires default_initializable<iter_value_t<I>>
(I first, S last); // freestanding
I uninitialized_value_constructtemplate<nothrow-forward-range R>
requires default_initializable<range_value_t<R>>
<R> uninitialized_value_construct(R&& r); // freestanding
borrowed_iterator_t
template<nothrow-forward-iterator I>
requires default_initializable<iter_value_t<I>>
(I first, iter_difference_t<I> n); // freestanding I uninitialized_value_construct_n
template<execution-policy Ep, nothrow-random-access-iterator I, nothrow-sized-sentinel-for<I> S>
requires default_initializable<iter_value_t<I>>
I uninitialized_value_construct(Ep&& exec, I first, S last); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-sized-range R>
requires default_initializable<range_value_t<R>>
borrowed_iterator_t<R> uninitialized_value_construct(Ep&& exec, R&& r); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-iterator I>
requires default_initializable<iter_value_t<I>> I uninitialized_value_construct_n(Ep&& exec, I first, iter_difference_t<I> n); // see [algorithms.parallel.overloads]
template<input_iterator I, sentinel_for<I> S1,
<O> S2>
nothrow-forward-iterator O, nothrow-sentinel-forrequires constructible_from<iter_value_t<O>, iter_reference_t<I>>
<I, O>
uninitialized_copy_result(I ifirst, S1 ilast, O ofirst, S2 olast); // freestanding
uninitialized_copytemplate<input_range IR, nothrow-forward-range OR>
requires constructible_from<range_value_t<OR>, range_reference_t<IR>>
<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
uninitialized_copy_result(IR&& in_range, OR&& out_range); // freestanding
uninitialized_copy
template<class I, class O>
using uninitialized_copy_n_result = in_out_result<I, O>; // freestanding
template<input_iterator I, nothrow-forward-iterator O, nothrow-sentinel-for<O> S>
requires constructible_from<iter_value_t<O>, iter_reference_t<I>>
<I, O>
uninitialized_copy_n_result(I ifirst, iter_difference_t<I> n, // freestanding
uninitialized_copy_n); O ofirst, S olast
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S1,
nothrow-random-access-iterator O, nothrow-sized-sentinel-for<O> S2>
requires constructible_from<iter_value_t<O>, iter_reference_t<I>>
uninitialized_copy_result<I, O>
uninitialized_copy(Ep&& exec, I ifirst, S1 ilast, O ofirst, S2 olast); // see [algorithms.parallel.overloads]
template<execution-policy Ep, random-access-sized-range IR, nothrow-random-access-sized-range OR>
requires constructible_from<range_value_t<OR>, range_reference_t<IR>>
uninitialized_copy_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
uninitialized_copy(Ep&& exec, IR&& in_range, OR&& out_range); // see [algorithms.parallel.overloads]
template<execution-policy Ep, random_access_iterator I, nothrow-random-access-iterator O,
nothrow-sized-sentinel-for<O> S>
requires constructible_from<iter_value_t<O>, iter_reference_t<I>>
uninitialized_copy_n_result<I, O>
uninitialized_copy_n(Ep&& exec, I ifirst, iter_difference_t<I> n, // see [algorithms.parallel.overloads] O ofirst, S olast);
template<input_iterator I, sentinel_for<I> S1,
<O> S2>
nothrow-forward-iterator O, nothrow-sentinel-forrequires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
<I, O>
uninitialized_move_result(I ifirst, S1 ilast, O ofirst, S2 olast); // freestanding
uninitialized_movetemplate<input_range IR, nothrow-forward-range OR>
requires constructible_from<range_value_t<OR>, range_rvalue_reference_t<IR>>
<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
uninitialized_move_result(IR&& in_range, OR&& out_range); // freestanding
uninitialized_move
template<input_iterator I,
<O> S>
nothrow-forward-iterator O, nothrow-sentinel-forrequires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
<I, O>
uninitialized_move_n_result(I ifirst, iter_difference_t<I> n, // freestanding
uninitialized_move_n); O ofirst, S olast
template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S1,
nothrow-random-access-iterator O, nothrow-sized-sentinel-for<O> S2>
requires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
uninitialized_move_result<I, O>
uninitialized_move(Ep&& exec, I ifirst, S1 ilast, O ofirst, S2 olast); // see [algorithms.parallel.overloads]
template<execution-policy Ep, random-access-sized-range IR, nothrow-random-access-sized-range OR>
requires constructible_from<range_value_t<OR>, range_rvalue_reference_t<IR>>
uninitialized_move_result<borrowed_iterator_t<IR>, borrowed_iterator_t<OR>>
uninitialized_move(Ep&& exec, IR&& in_range, OR&& out_range); // see [algorithms.parallel.overloads]
template<execution-policy Ep, random_access_iterator I,
nothrow-random-access-iterator O, nothrow-sized-sentinel-for<O> S>
requires constructible_from<iter_value_t<O>, iter_rvalue_reference_t<I>>
uninitialized_move_n_result<I, O>
uninitialized_move_n(Ep&& exec, I ifirst, iter_difference_t<I> n, // see [algorithms.parallel.overloads] O ofirst, S olast);
template<nothrow-forward-iterator I, nothrow-sentinel-for<I> S, class T>
requires constructible_from<iter_value_t<I>, const T&>
(I first, S last, const T& x); // freestanding
I uninitialized_filltemplate<nothrow-forward-range R, class T>
requires constructible_from<range_value_t<R>, const T&>
<R> uninitialized_fill(R&& r, const T& x); // freestanding
borrowed_iterator_t
template<nothrow-forward-iterator I, class T>
requires constructible_from<iter_value_t<I>, const T&>
(I first, iter_difference_t<I> n, const T& x); // freestanding I uninitialized_fill_n
template<execution-policy Ep, nothrow-random-access-iterator I, nothrow-sized-sentinel-for<I> S, class T>
requires constructible_from<iter_value_t<I>, const T&>
I uninitialized_fill(Ep&& exec, I first, S last, const T& x); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-sized-range R, class T>
requires constructible_from<range_value_t<R>, const T&>
borrowed_iterator_t<R> uninitialized_fill(Ep&& exec, R&& r, const T& x); // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-iterator I, class T>
requires constructible_from<iter_value_t<I>, const T&> I uninitialized_fill_n(Ep&& exec, I first, iter_difference_t<I> n, const T& x); // see [algorithms.parallel.overloads]
template<nothrow-input-iterator I, nothrow-sentinel-for<I> S>
requires destructible<iter_value_t<I>>
constexpr I destroy(I first, S last) noexcept; // freestanding
template<nothrow-input-range R>
requires destructible<range_value_t<R>>
constexpr borrowed_iterator_t<R> destroy(R&& r) noexcept; // freestanding
template<nothrow-input-iterator I>
requires destructible<iter_value_t<I>>
constexpr I destroy_n(I first, iter_difference_t<I> n) noexcept; // freestanding
template<execution-policy Ep, nothrow-random-access-iterator I, nothrow-sized-sentinel-for<I> S>
requires destructible<iter_value_t<I>>
I destroy(Ep&& exec, I first, S last) noexcept; // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-sized-range R>
requires destructible<range_value_t<R>>
borrowed_iterator_t<R> destroy(Ep&& exec, R&& r) noexcept; // see [algorithms.parallel.overloads]
template<execution-policy Ep, nothrow-random-access-iterator I>
requires destructible<iter_value_t<I>> I destroy_n(Ep&& exec, I first, iter_difference_t<I> n) noexcept; // see [algorithms.parallel.overloads]
template<class S, class I>
concept nothrow-sentinel-for = sentinel_for<S, I>; // exposition only
Types S
and
I
model
nothrow-sentinel-for
only
if no exceptions are thrown from copy construction, move construction,
copy assignment, move assignment, or comparisons between valid values of
type I
and
S
.
[Note X: This concept allows some
sentinel_for
([iterator.concept.sentinel]) operations to throw exceptions. — end
note]
template<class S, class I>
concept nothrow-sized-sentinel-for = // exposition only
nothrow-sentinel-for<S, I> && sized_sentinel_for<S, I>;
Types S
and
I
model
nothrow-sized-sentinel-for
only if no exceptions are thrown from the
-
operator for valid values of
type I
and
S
.
[Note X: This concept allows some
sized_sentinel_for
([iterator.concept.sizedsentinel]) operations to throw exceptions. —
end note]
template<class I>
concept nothrow-forward-iterator = // exposition only
<I> &&
nothrow-input-iterator<I> &&
forward_iterator<I, I>; nothrow-sentinel-for
[Note X: This concept allows some
forward_iterator
([iterator.concept.forward]) operations to throw exceptions. — end
note]
template<class R>
concept nothrow-forward-range = // exposition only
<R> &&
nothrow-input-range<iterator_t<R>>; nothrow-forward-iterator
template<class I>
concept nothrow-bidirectional-iterator = // exposition only
nothrow-forward-iterator<I> && bidirectional_iterator<I>;
A type I
models nothrow-bidirectional-iterator
only if no exceptions are thrown from decrementing valid iterators.
[Note X: This concept allows some
bidirectional_iterator
([iterator.concept.bidir]) operations to throw exceptions. — end
note]
template<class R>
concept nothrow-bidirectional-range = // exposition only
nothrow-forward-range<R> && nothrow-bidirectional-iterator<iterator_t<R>>;
template<class I>
concept nothrow-random-access-iterator = // exposition only
nothrow-bidirectional-iterator<I> &&
random_access_iterator<I> && nothrow-sized-sentinel-for<I, I>;
A type I
models nothrow-random-access-iterator
only if no exceptions are thrown from advancement with
+=
,
+
,
-=
, and
-
, comparisons, or applying the
[]
subscript operator to valid
iterators.
[Note X: This concept allows some
random_access_iterator
([iterator.concept.random.access]) operations to throw exceptions. —
end note]
template<class R>
concept nothrow-random-access-range = // exposition only
nothrow-bidirectional-range<R> &&
nothrow-random-access-iterator<iterator_t<R>>;
template<class R>
concept nothrow-random-access-sized-range = // exposition only nothrow-random-access-range<R> && sized_range<R>;
random-access-sized-range
as an exposition-only concept for wording simplificationExecutionPolicy
parameter, italicize execution-policy
concept in wordingresult_last
or similar
for the algorithms where range-as-the-output is a novelty
(copy
,
transform
, etc.), unless stated
otherwise in Issues to address or in Out-of-scopefill
and
generate
algorithms family to use
indirectly_writable
instead of
output_iterator
and
output_range
for design
consistencycopy_n
algorithm familyrotate_copy
from scope
due to design issues&&
instead of
||
)std::ranges
iterator
as an outputfor_each
to match the proposed designrange
as an output for
the algorithmsmismatch
and
equal
to require
sized_range
for both inputs
(“&&
instead of
||
”).
SF | F | N | A | SA |
---|---|---|---|---|
4 | 3 | 1 | 0 | 0 |
transform
to require
sized_range
for both inputs
(“&&
instead of
||
”), with
the plan to relax these constraints once we have a way to statically
detect infinite ranges.
SF | F | N | A | SA |
---|---|---|---|---|
3 | 3 | 0 | 1 | 1 |
SF | F | N | A | SA |
---|---|---|---|---|
4 | 4 | 0 | 0 | 0 |
Poll 4 Forward [P3179R3] with the changes in [P3490R0] (as updated above) to LEWG for inclusion in C++26 with these changes polled above.
SF | F | N | A | SA |
---|---|---|---|---|
4 | 5 | 0 | 0 | 0 |
Forward [P3179R3] to LEWG with the following notes:
begin
/end
only once, in serial code (we do not think any new words are
needed)mismatch
,
transform
and
equal
assume the unsized range is at
least as large as the sized one (UB / precondition) or require
&& sizedSF | F | N | A | SA |
---|---|---|---|---|
4 | 8 | 0 | 0 | 0 |
Poll: Continue work on [P3179R2] for IS’26 with these notes: 1. RandomAccess for inputs and outputs 2. Iterators for outputs 3. We believe the overloads are worth it
SF | F | N | A | SA |
---|---|---|---|---|
7 | 4 | 2 | 1 | 0 |
for_each
shouldn’t return the callable
SF | F | N | A | SA |
---|---|---|---|---|
2 | 4 | 2 | 0 | 0 |
Poll 2: Parallel
std::ranges
algos should return the same type as serial
std::ranges
algos
Unanimous consent. |
Poll 3: Parallel ranges algos should require
forward_range
, not
random_access_range
SF | F | N | A | SA |
---|---|---|---|---|
3 | 2 | 3 | 1 | 1 |
Poll 4: Range-based parallel algos should require const operator()
SF | F | N | A | SA |
---|---|---|---|---|
0 | 7 | 2 | 0 | 0 |
Thanks to Jonathan Muller for the wording review and providing useful feedback.