std:: adjacent_difference

Let T be the value type of decltype ( first ) .

Given binary_op as the actual binary operation:

• If any of the following conditions is satisfied, the program is ill-formed:

• For overloads (1,3) :

• T is not constructible from * first .
• acc is not writable to d_first .
• The result of binary_op ( val, acc ) (until C++20) binary_op ( val, std :: move ( acc ) ) (since C++20) is not writable to d_first .

• For overloads (2,4) :

• * first is not writable to d_first .
• The result of binary_op ( * first, * first ) is not writable to d_first .

• Given d_last as the iterator to be returned , if any of the following conditions is satisfied, the behavior is undefined:

• For overloads (2,4) , [ first , last ) and [ d_first , d_last ) overlaps.
• binary_op modifies any element of [ first , last ) or [ d_first , d_last ) .
• binary_op invalidates any iterator or subrange in [ first , last ] or [ d_first , d_last ] .

Parameters

Return value

Iterator to the element past the last element written, or d_first if [ first , last ) is empty.

Complexity

Given \(\scriptsize N\) N as std:: distance ( first, last ) :

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 other ExecutionPolicy , the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

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;
}

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;
}

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 - or op
• the return type of operator - or 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 of operator - or op ) is assigned to it
• its value is passed to operator - or 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>{});

Example

#include <array>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
void println(auto comment, const auto& sequence)
{
    std::cout << comment;
    for (const auto& n : sequence)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    // Default implementation - the difference between two adjacent items
    std::vector v{4, 6, 9, 13, 18, 19, 19, 15, 10};
    println("Initially, v = ", v);
    std::adjacent_difference(v.begin(), v.end(), v.begin());
    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<>{});
    println("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

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

See also