std::adjacent_difference

template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last,
                                        OutputIt d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last,
                                ForwardIt2 d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, 
                              OutputIt d_first, BinaryOperation op );

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, 
                                        OutputIt d_first,
                                        BinaryOperation op );

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, 
                                ForwardIt2 d_first, BinaryOperation op );

Если [first, last) не пусто, вычисляет разницу между вторым и первым элементом каждой смежной пары элементов и записывает разницу в диапазон, начинающийся в d_first + 1. Неизменная копия *first записывается в *d_first. Перегрузки (1,2) используют оператор- для вычисления разностей, перегрузки (3,4) используют заданную бинарную функцию op, применяя std::move к своим операндам справа(с C++11).

Эквивалентная операция для перегрузки (1), если [first, last) не пусто, использует накопитель acc для хранения значения, которое нужно вычесть:

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);
// ...

Эквивалентная операция для перегрузки (3), если [first, last) не пусто:

// 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);
...

Если op делает недействительными какие-либо итераторы (включая любые конечные итераторы) или изменяет любые элементы вовлечённых диапазонов, поведение не определено.

Для перегрузок (1,3), если std::iterator_traits<InputIt>::value_type не является копируемым(до C++11)перемещаемым(с C++11), поведение не определено.

Параметры

Возвращаемое значение

Итератор на элемент после последнего записанного элемента, или d_first если [first, last) пусто.

Сложность

Учитывая N как std::distance(first, last) - 1:

Исключение

Перегрузки с шаблоным параметром с именем ExecutionPolicy сообщают об ошибках следующим образом:

• Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy, поведение не определено.
• Если алгоритм не может выделить память, выбрасывается std::bad_alloc.

Возможная реализация

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

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

Примечания

acc была введена из-за разрешения LWG issue 539. Причина использования acc вместо непосредственного вычисления разностей заключается в том, что семантика последнего может быть неясной при несовпадении типов:

• тип значения InputIt
• тип(ы) записи OutputIt
• типы параметров оператора- или op
• тип возвращаемого значения оператора- или op

acc служит промежуточным объектом для кэширования значений итерируемых элементов:

• его тип — тип значения InputIt
• значение, записанное в d_first (которое является результатом оператора- или op) присваивается ему
• его значение передаётся в оператор- или 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>{});

Пример

#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

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

См. также