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

• For overloads (2,4), [first, last) and [ d_first ,  d_last )
• 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)

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
• 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

• 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
• 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