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

Soit T le type valeur de decltype(first).

Soit binary_op l'opération binaire réelle :

• Si l'une des conditions suivantes est satisfaite, le programme est mal formé :

• Pour les surcharges (1,3) :

• T n'est pas constructible à partir de *first.
• acc n'est pas inscriptible dans d_first.
• Le résultat de binary_op(val, acc)(jusqu'à C++20)binary_op(val, std::move(acc))(depuis C++20) n'est pas inscriptible dans d_first.

• Pour les surcharges (2,4) :

• *first n'est pas inscriptible dans d_first.
• Le résultat de binary_op(*first, *first) n'est pas inscriptible dans d_first.

• Soit d_last l'itérateur à retourner, si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

• Pour les surcharges (2,4), [first, last) et [d_first, d_last) se chevauchent.
• binary_op modifie tout élément de [first, last) ou [d_first, d_last).
• binary_op invalide tout itérateur ou sous-plage dans [first, last] ou [d_first, d_last].

Paramètres

Valeur de retour

Itérateur pointant sur l'élément après le dernier élément écrit, ou d_first si [first, last) est vide.

Complexité

Soit \(\scriptsize N\)N comme std::distance(first, last) :

Exceptions

Les surcharges avec un paramètre template nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy est l'une des politiques standard, std::terminate est appelé. Pour tout autre ExecutionPolicy, le comportement est défini par l'implémentation.
• Si l'algorithme échoue à allouer de la mémoire, std::bad_alloc est levée.

Implémentation possible

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 a été introduit suite à la résolution de LWG issue 539. La raison d'utiliser acc plutôt que de calculer directement les différences est que la sémantique de ce dernier est confuse si les types suivants ne correspondent pas :

• le type valeur de InputIt
• le(s) type(s) inscriptible(s) de OutputIt
• les types des paramètres de operator- ou op
• le type de retour de operator- ou op

acc sert d'objet intermédiaire pour mettre en cache les valeurs des éléments itérés :

• son type est le type valeur de InputIt
• la valeur écrite dans d_first (qui est la valeur de retour de operator- ou op) lui est affectée
• sa valeur est passée à operator- ou 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>{});

Exemple

#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

Rapports de défauts

Les rapports de défauts suivants, modifiant le comportement, ont été appliqués rétroactivement aux normes C++ publiées précédemment.

Voir aussi