std::adjacent_difference() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class InputIt, class OutputIt >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );
// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOperation op );
// (1)
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );
// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOperation op );
// (1)
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );
// (2)
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );
If [first
; last
) is not empty, computes the differences between the second and the first of each adjacent pair of its elements and writes the differences to the range beginning at d_first + 1
.
An unmodified copy of *first
is written to *d_first
.
- (1, 3) Uses
operator-
to calculate the differences. - (2, 4) Use the given binary function
op
, all applyingstd::move
to their operands on the right hand side (od C++11).
Equivalent operation for overload (1), if [first
; last
) is not empty, uses the accumulator acc to store the value to be subtracted:
std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;
std::iterator_traits<InputIt>::value_type val1 = *(first + 1);
*(d_first + 1) = val1 - std::move(acc);
// or *(d_first + 1) = op(val1, std::move(acc)); for overload (2)
acc = std::move(val1);
std::iterator_traits<InputIt>::value_type val2 = *(first + 2);
*(d_first + 2) = val2 - std::move(acc);
acc = std::move(val2);
std::iterator_traits<InputIt>::value_type val3 = *(first + 3);
*(d_first + 3) = val3 - std::move(acc);
acc = std::move(val3);
// ...
Equivalent operation for overload (2), if [first
; last
) is not empty:
// performed first
*d_first = *first;
// performed after the initial assignment, might not be sequenced
*(d_first + 1) = *(first + 1) - *(first);
// or *(d_first + 1) = op(*(first + 1), *(first)); for overload (4)
*(d_first + 2) = *(first + 2) - *(first + 1);
*(d_first + 3) = *(first + 3) - *(first + 2);
...
If op
invalidates any iterator (including any of the end iterators) or modify any elements of the ranges involved, the behavior is undefined
For overloads (1 - 2), if std::iterator_traits<InputIt>::value_type
is not
CopyAssignable (do C++11)MoveAssignable (od C++11)
, the behavior is undefined
Parameters
first last | The range of elements. |
d_first | The beginning of the destination range. |
policy | The execution policy to use. See execution policy for details. |
op | Binary operation function object that will be applied. The signature of the function should be equivalent to the following:
|
Type requirements
InputIt must meet the requirements of LegacyInputIterator.
InputIt | LegacyInputIterator |
OutputIt | LegacyOutputIterator |
ForwardIt1 ForwardIt2 | LegacyOutputIterator |
T | CopyAssignable CopyConstructible |
-
For overloads (1 - 2), value type of
InputIt
must be constructible from*first
. -
acc
and the result of:- (1)
val - acc
(do C++11)val - std::move(acc) (od C++11) - (2)
op(val, acc)
(do C++11)op(val, std::move(acc)
(od C++11)
must be writable to
d_first
. - (1)
-
The result of
*first
and the result of:- (3)
*first - *first
- (4)
op(*first, *first)
must be writable to
d_first
. - (3)
Return value
Iterator to the element past the last element written, or d_first
if [first
; last
) is empty.
Complexity
Given N
as std::distance(first, last) - 1
:
- (1, 3) Exactly
N
applications ofoperator-
. - (2 ,4) Exactly
N
applications of the binary functionop
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
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++11
acc = std::move(val);
}
return ++d_first;
}
adjacent_difference(2)
template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // since C++20
OutputIt adjacent_difference(InputIt first, InputIt last, OutputIt d_first, BinaryOperation 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++11
acc = std::move(val);
}
return ++d_first;
}
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
operator-
orop
- The return type of
operator-
orop
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 ofoperator-
orop
) is assigned to it - Its value is passed to
operator-
orop
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>{});
Examples
#include <array>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
auto print = [](auto comment, auto const& sequence)
{
std::cout << comment;
for (const auto& n : sequence)
std::cout << n << ' ';
std::cout << '\n';
};
int main()
{
// Default implementation - the difference b/w two adjacent items
std::vector v {4, 6, 9, 13, 18, 19, 19, 15, 10};
print("Initially, v = ", v);
std::adjacent_difference(v.begin(), v.end(), v.begin());
print("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<>{});
print("Fibonacci, a = ", a);
}
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
Hover to see the original license.