std::adjacent_difference

Definiert in der Header-Datei `<numeric>`
template< class InputIt, class OutputIt > OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt2 adjacent_difference( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first );	(2)	(seit C++17)
template< class InputIt, class OutputIt, class BinaryOp > OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first, BinaryOp op );	(3)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOp > ForwardIt2 adjacent_difference( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, BinaryOp op );	(4)	(seit C++17)

Sei T der Werttyp von decltype(first).

1) Wenn [first, last) leer ist, tut dies nichts.

Andernfalls werden die folgenden Operationen in dieser Reihenfolge ausgeführt:

Erstellt einen Akkumulator acc vom Typ T und initialisiert ihn mit *first.
Weist acc *d_first zu.
Für jeden Iterator iter in [++first, last) in Reihenfolge werden die folgenden Operationen ausgeführt:

a) Erstellt ein Objekt val vom Typ T und initialisiert es mit *iter.

b) Berechnet val - acc(bis C++20)val - std::move(acc)(seit C++20).

c) Weist das Ergebnis *++d_first zu.

d) Kopiert(bis C++20)Verschiebt(seit C++20) weist von val nach acc.

2) Wenn [first, last) leer ist, tut dies nichts.

Andernfalls werden die folgenden Operationen in dieser Reihenfolge ausgeführt:

Weist *first *d_first zu.
Für jede Ganzzahl i in [1, std::distance(first, last)) werden die folgenden Operationen in Reihenfolge ausgeführt:

a) Berechnet curr - prev, wobei curr der nächste ite Iterator von first ist und prev der nächste i - 1te Iterator von first ist.

b) Weist das Ergebnis *dest zu, wobei dest der nächste ite Iterator von d_first ist.

3) Wie (1), berechnet aber op(val, acc)(bis C++20)op(val, std::move(acc))(seit C++20) anstelle von.

4) Wie (2), berechnet aber op(curr, prev) anstelle von.

Gegeben binary_op als die tatsächliche binäre Operation

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Programm ill-formed (wohlgeformt):

Für Überladungen (1,3)

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

Für Überladungen (2,4)

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

Gegeben d_last als der Iterator, der zurückgegeben werden soll, ist das Verhalten undefiniert, wenn eine der folgenden Bedingungen erfüllt ist:

Für Überladungen (1,3) ist T nicht MoveAssignable.

(seit C++20)

Für Überladungen (2,4) überlappen sich [first, last) und [d_first, d_last).
binary_op modifiziert keine Elemente von [first, last) oder [d_first, d_last).
binary_op macht keine Iteratoren oder Teilbereiche in [first, last] oder [d_first, d_last] ungültig.

[bearbeiten] Parameter

first, last	-	das Paar von Iteratoren, das den Bereich der Elemente definiert, die
d_first	-	der Anfang des Zielbereichs
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
op	-	ein binäres Operations-Funktionsobjekt, das angewendet wird. Die Signatur der Funktion sollte äquivalent zu folgender sein: Ret fun(const Type1 &a, const Type2 &b); Die Signatur muss nicht const & haben. Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ iterator_traits<InputIt>::value_type implizit in beide konvertiert werden kann. Der Typ Ret muss so beschaffen sein, dass ein Objekt vom Typ OutputIt dereferenziert und ein Wert vom Typ Ret zugewiesen werden kann.
Typanforderungen
- `InputIt` muss die Anforderungen von LegacyInputIterator erfüllen.
- `OutputIt` muss die Anforderungen an LegacyOutputIterator erfüllen.
- `ForwardIt1, ForwardIt2` müssen die Anforderungen an LegacyForwardIterator erfüllen.

[bearbeiten] Rückgabewert

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

[bearbeiten] Komplexität

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

1,2) Genau

N-1

Anwendungen von operator-.

3,4) Genau

N-1

Anwendungen der binären Funktion op.

[bearbeiten] Ausnahmen

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

Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

[bearbeiten] Mögliche Implementierung

adjacent_difference (1)

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

adjacent_difference (3)

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

[bearbeiten] Hinweise

acc wurde aufgrund der Auflösung von LWG-Problem 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
die beschreibbaren 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 Wert, der nach d_first geschrieben wird (was 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: 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>{});

[bearbeiten] Beispiel

Führen Sie diesen Code aus

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

Ausgabe

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

[bearbeiten] Fehlerberichte

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 242	C++98	op darf keine Nebenwirkungen haben	es darf nicht modifizieren die beteiligten Bereiche
LWG 539	C++98	die für das Ergebnis erforderlichen Typanforderungen Auswertungen und Zuweisungen gültig zu sein, fehlten	hinzugefügt
LWG 3058	C++17	für Überladungen (2,4), das Ergebnis jeder Invokation von operator- oder op wurde einem temporären Objekt zugewiesen und dieses Objekt wird in den Ausgabebereich geschrieben	die Ergebnisse zuweisen in den Ausgabebereich direkt

[bearbeiten] Siehe auch

partial_sum	berechnet die partielle Summe einer Elementreihe (Funktionstemplate) [bearbeiten]
accumulate	summiert oder faltet eine Reihe von Elementen (Funktionstemplate) [bearbeiten]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen