std::adjacent_difference
From cppreference.com
| Defined in header <numeric>
|
||
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last,
OutputIt d_first );
|
(1) | (constexpr since C++20) |
template< class InputIt, class OutputIt, class BinaryOp >
OutputIt adjacent_difference( InputIt first, InputIt last,
OutputIt d_first, BinaryOp op );
|
(2) | (constexpr since C++20) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first );
|
(3) | (since C++17) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class BinaryOp >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 d_first, BinaryOp op );
|
(4) | (since C++17) |
Computes the differences of all pairs of adjacent elements in the source range [first, last), the results are stored in the destination range [d_first, d_last), where d_last is std::next(d_first, std::distance(first, last)).
- If the source range is empty, no difference will be computed.
- Otherwise,
std::distance(first, last)differences will be computed, where the first difference is*first.
Let
Tbe the value type ofdecltype(first), andsub_opbe the subtraction operation for calculating differences, it isoperator-(until C++20)an object of typestd::minus<>(since C++20) for overloads (1,3), oropfor overloads (2,4).
1,2) If the source range is not empty, performs the following operations in order:
- Initializes the accumulator
acc(of typeT) with the initial value*first. - Assigns
accto*d_first. - For each iterator
iterin[std::next(first),last)and the corresponding iteratord_iterin the destination range in order, performs the following operations in order:
a) Initializes a temporary accumulator
temp (of type T) with the initial value *iter. If any of the following conditions is satisfied, the program is ill-formed:
Tis not constructible with*first.- The type of
accor the result type ofsub_opis not writable tod_first.
|
If |
(since C++20) |
3,4) If the source range is not empty, performs the following operations in order:
- Assigns
*firstto*d_first. - For each iterator
iterin[std::next(first),last)and the corresponding iteratord_iterin the destination range, assigns the result ofsub_op(*iter, *std::prev(iter))to*d_iter.
If the type of
*first or the result type of sub_op is not writable to d_first, the program is ill-formed.If any of the following conditions is satisfied, the behavior is undefined:
sub_opmodifies any element of the source range or the destination range.sub_opinvalidates any iterator or subrange in[first,last]or[d_first,d_last].
Parameters
| first, last | - | the pair of iterators defining the source range |
| d_first | - | the beginning of the destination range |
| op | - | binary operation function object that will be applied. The signature of the function should be equivalent to the following:
The signature does not need to have |
| policy | - | the execution policy to use |
| Type requirements | ||
-InputIt must meet the requirements of LegacyInputIterator.
| ||
-OutputIt must meet the requirements of LegacyOutputIterator.
| ||
-ForwardIt1, ForwardIt2 must meet the requirements of LegacyForwardIterator.
| ||
Return value
The past-the-end iterator of the destination range (i.e. d_last).
Complexity
Given N as std::distance(first, last):
1,3) Exactly N-1 applications of
operator-(until C++20)the object of type std::minus<>(since C++20).2,4) Exactly N-1 applications of
op.Exceptions
3,4) During the execution process:
- If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
- If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).
Notes
acc was introduced because of the resolution of LWG issue 539. The reason of using acc rather than directly calculating the differences is because the semantic of the latter is confusing if the following types mismatch:
- the value type of
InputIt - the writable type(s) of
OutputIt - the types of the parameters of
sub_op - the return type of
sub_op
acc serves as the intermediate object to cache values of the iterated elements:
- Its type is the value type of
InputIt. - The value written to
d_first(which is the return value ofsub_op) is assigned to it. - Its value is passed to
sub_op.
char i_array[4] = {100, 100, 100, 100};
int o_array[4];
// OK: performs conversions when needed
// 1. creates “acc” of type char (the value type)
// 2. “acc” is assigned to the first element of “o_array”
// 3. the char arguments are used for long multiplication (char -> long)
// 4. the long product is assigned to the output range (long -> int)
// 5. the next value of “i_array” is assigned to “acc”
// 6. go back to step 3 to process the remaining elements in the input range
std::adjacent_difference(i_array, i_array + 4, o_array, std::multiplies<long>{});
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_parallel_algorithm |
201603L |
(C++17) | Parallel algorithms, overloads (3,4) |
Possible implementation
| adjacent_difference (1) |
|---|
template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first)
{
if (first == last)
return d_first;
typedef typename std::iterator_traits<InputIt>::value_type value_t;
value_t acc = *first;
*d_first = acc;
while (++first != last)
{
value_t val = *first;
*++d_first = val - std::move(acc); // std::move since C++20
acc = std::move(val);
}
return ++d_first;
}
|
| adjacent_difference (2) |
template<class InputIt, class OutputIt, class BinaryOp>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last,
OutputIt d_first, BinaryOp op)
{
if (first == last)
return d_first;
typedef typename std::iterator_traits<InputIt>::value_type value_t;
value_t acc = *first;
*d_first = acc;
while (++first != last)
{
value_t val = *first;
*++d_first = op(val, std::move(acc)); // std::move since C++20
acc = std::move(val);
}
return ++d_first;
}
|
Example
Run this code
#include <array>
#include <functional>
#include <iterator>
#include <numeric>
#include <print>
#include <vector>
int main()
{
// Default implementation - the difference between two adjacent items
std::vector v{4, 6, 9, 13, 18, 19, 19, 15, 10};
std::println("Initially, v = {}", v);
std::adjacent_difference(v.begin(), v.end(), v.begin());
std::println("Modified v = {}", v);
// Fibonacci
std::array<int, 10> a{1};
std::adjacent_difference(std::begin(a), std::prev(std::end(a)),
std::next(std::begin(a)), std::plus<>{});
std::println("Fibonacci, a = {}", a);
}
Output:
Initially, v = [4, 6, 9, 13, 18, 19, 19, 15, 10]
Modified v = [4, 2, 3, 4, 5, 1, 0, -4, -5]
Fibonacci, a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 242 | C++98 | sub_op could not have side effects
|
it cannot modify the ranges involved |
| LWG 539 | C++98 | the type requirements needed for the result evaluations and assignments to be valid were missing |
added |
| LWG 3058 | C++17 | for overloads (3,4), the result of each invocation of sub_op was assigned to a temporaryobject, and that object is assigned to the output range |
assign the results to the output range directly |