std::adjacent_difference

template< class InputIt, class OutputIt >
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 BinaryOp >
OutputIt adjacent_difference( InputIt first, InputIt last, 
                              OutputIt d_first, BinaryOp op );

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

Sea T el tipo de valor de decltype(first).

Dado binary_op como la operación binaria real:

• Si se satisface alguna de las siguientes condiciones, el programa está mal formado:

• Para las sobrecargas (1,3):

• T no es construible desde *first.
• acc no es escribible a d_first.
• El resultado de binary_op(val, acc)(hasta C++20)binary_op(val, std::move(acc))(desde C++20) no es escribible a d_first.

• Para las sobrecargas (2,4):

• *first no es escribible a d_first.
• El resultado de binary_op(*first, *first) no es escribible a d_first.

• Dado d_last como el iterador a devolver, si se satisface alguna de las siguientes condiciones, el comportamiento no está definido:

• Para las sobrecargas (2,4), [first, last) y [d_first, d_last) se superponen.
• binary_op modifica cualquier elemento de [first, last) o [d_first, d_last).
• binary_op invalida cualquier iterador o subrango en [first, last] o [d_first, d_last].

Parámetros

Valor de retorno

Iterador al elemento después del último escrito, o d_first si [first, last) está vacío.

Complejidad

Dado \(\scriptsize N\)N como std::distance(first, last):

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy informan errores de la siguiente manera:

• Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es una de las políticas estándar, se llama a std::terminate. Para cualquier otro ExecutionPolicy, el comportamiento está definido por la implementación.
• Si el algoritmo falla al asignar memoria, se lanza std::bad_alloc.

Posible implementación

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

Notas

acc fue introducido porque de la resolución de LWG issue 539. La razón de usar acc en lugar de calcular directamente las diferencias es porque la semántica de esto último es confusa si los siguientes tipos no coinciden:

• el tipo de valor de InputIt
• los tipos escribibles de OutputIt
• los tipos de los parámetros de operator- o op
• el tipo de retorno de operator- o op

acc sirve como el objeto intermedio para almacenar en caché valores de los elementos iterados:

• su tipo es el tipo de valor de InputIt
• el valor escrito a d_first (que es el valor de retorno de operator- o op) se asigna a él
• su valor se pasa a operator- o 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>{});

Ejemplo

#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

Informes de defectos

Los siguientes informes de defectos que cambian el comportamiento se aplicaron retroactivamente a estándares C++ previamente publicados.

Véase también