std:: partial_sum

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

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

• Der Werttyp von InputIt ist nicht konstruierbar aus * first .
• acc ist nicht schreibbar nach d_first .
• Das Ergebnis von binary_op ( acc, * iter ) (bis C++20) binary_op ( std :: move ( acc ) , * iter ) (seit C++20) ist nicht implizit konvertierbar zum Werttyp von InputIt .

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

• binary_op modifiziert beliebige Elemente von [ first , last ) oder [ d_first , d_last ) .
• binary_op invalidiert beliebige Iteratoren oder Teilbereiche in [ first , last ] oder [ d_first , d_last ] .

1. ↑ Der tatsächlich zuzuweisende Wert ist das Ergebnis der Zuweisung im vorherigen Schritt. Wir nehmen an, dass das Zuweisungsergebnis hier acc ist.

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

Mögliche Implementierung

template<class InputIt, class OutputIt>
constexpr // seit C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
    while (++first != last)
    {
        sum = std::move(sum) + *first; // std::move seit C++20
        *++d_first = sum;
    }
    return ++d_first;
    // oder, seit C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

template<class InputIt, class OutputIt, class BinaryOp>
constexpr // seit C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOp op)
{
    if (first == last)
        return d_first;
    typename std::iterator_traits<InputIt>::value_type acc = *first;
    *d_first = acc;
    while (++first != last)
    {
        acc = op(std::move(acc), *first); // std::move seit C++20
        *++d_first = acc;
    }
    return ++d_first;
}

Hinweise

acc wurde aufgrund der Lösung von LWG Issue 539 eingeführt. Der Grund für die Verwendung von acc anstatt der direkten Aufsummierung der Ergebnisse (d.h. * ( d_first + 2 ) = ( * first + * ( first + 1 ) ) + * ( first + 2 ) ; ) liegt darin, dass die Semantik des Letzteren 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 Speichern und Bereitstellen der Werte für jeden Schritt der Berechnung:

• sein Typ ist der Werttyp von InputIt
• es wird geschrieben nach d_first
• sein Wert wird übergeben an operator + oder op
• es speichert den Rückgabewert von operator + oder op

enum not_int { x = 1, y = 2 };
char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];
// OK: verwendet operator+(char, char) und weist char-Werte dem int-Array zu
std::partial_sum(i_array, i_array + 4, o_array);
// Fehler: kann not_int-Werte nicht dem int-Array zuweisen
std::partial_sum(e_array, e_array + 4, o_array);
// OK: führt Konvertierungen bei Bedarf durch
// 1. erstellt "acc" vom Typ char (der Werttyp)
// 2. die char-Argumente werden für die long-Multiplikation verwendet (char -> long)
// 3. das long-Produkt wird "acc" zugewiesen (long -> char)
// 4. "acc" wird einem Element von "o_array" zugewiesen (char -> int)
// 5. zurück zu Schritt 2, um die verbleibenden Elemente im Eingabebereich zu verarbeiten
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

Beispiel

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
    std::cout << "Die ersten " << v.size() << " geraden Zahlen sind: ";
    // Ergebnis in den cout-Stream schreiben
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    // Ergebnis zurück in den Vektor v schreiben
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
    std::cout << "Die ersten " << v.size() << " Zweierpotenzen sind: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Die ersten 10 geraden Zahlen sind: 2 4 6 8 10 12 14 16 18 20 
Die ersten 10 Zweierpotenzen sind: 2 4 8 16 32 64 128 256 512 1024

Fehlerberichte

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

Siehe auch