std:: adjacent_difference

Sei T der Werttyp von decltype ( first ) .

Gegeben binary_op als die tatsächliche binäre Operation:

• Wenn eine der folgenden Bedingungen erfüllt ist, ist das Programm fehlerhaft:

• Für Überladungen (1,3) :

• T ist nicht konstruierbar aus * first .
• acc ist nicht schreibbar nach d_first .
• Das Ergebnis von binary_op ( val, acc ) (bis C++20) binary_op ( val, std :: move ( acc ) ) (seit C++20) ist nicht schreibbar nach d_first .

• Für Überladungen (2,4) :

• * first ist nicht schreibbar nach d_first .
• Das Ergebnis von binary_op ( * first, * first ) ist nicht schreibbar nach d_first .

• Gegeben sei d_last als der zurückzugebende Iterator, falls eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

• Für Überladungen (2,4) überlappen sich [ first , last ) und [ d_first , d_last ) .
• binary_op modifiziert irgendein Element von [ first , last ) oder [ d_first , d_last ) .
• binary_op macht irgendeinen Iterator oder Teilbereich in [ first , last ] oder [ d_first , d_last ] ungültig.

Parameter

Rückgabewert

Iterator auf das Element nach dem letzten geschriebenen Element, oder d_first falls [ first , last ) leer ist.

Komplexität

Gegeben \(\scriptsize N\) N als std:: distance ( first, last ) :

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

• Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
• Wenn der Algorithmus keinen Speicher allokieren kann, wird std::bad_alloc geworfen.

Mögliche Implementierung

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

Hinweise

acc wurde aufgrund der Lösung von LWG Issue 539 eingeführt. Der Grund für die Verwendung von acc anstelle der direkten Berechnung der Differenzen liegt darin, dass die Semantik letzterer verwirrend ist, wenn die folgenden Typen nicht übereinstimmen:

• der Werttyp von InputIt
• der schreibbare Typ (oder die schreibbaren Typen) von OutputIt
• die Typen der Parameter von operator - oder op
• der Rückgabetyp von operator - oder op

acc dient als Zwischenobjekt zum Zwischenspeichern von Werten der iterierten Elemente:

• sein Typ ist der Werttyp von InputIt
• der an d_first geschriebene Wert (welcher der Rückgabewert von operator - oder op ist) wird ihm zugewiesen
• sein Wert wird an operator - oder op übergeben

char i_array[4] = {100, 100, 100, 100};
int  o_array[4];
// OK: führt Konvertierungen bei Bedarf durch
// 1. erstellt "acc" vom Typ char (der Werttyp)
// 2. "acc" wird dem ersten Element von "o_array" zugewiesen
// 3. die char-Argumente werden für die long-Multiplikation verwendet (char -> long)
// 4. das long-Produkt wird dem Ausgabebereich zugewiesen (long -> int)
// 5. der nächste Wert von "i_array" wird "acc" zugewiesen
// 6. zurück zu Schritt 3, um die verbleibenden Elemente im Eingabebereich zu verarbeiten
std::adjacent_difference(i_array, i_array + 4, o_array, std::multiplies<long>{});

Beispiel

#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()
{
    // Standardimplementierung - die Differenz zwischen zwei benachbarten Elementen
    std::vector v{4, 6, 9, 13, 18, 19, 19, 15, 10};
    println("Anfänglich, v = ", v);
    std::adjacent_difference(v.begin(), v.end(), v.begin());
    println("Modifiziertes 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

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

Siehe auch