std::partial_sum
Von cppreference.com
| Definiert in der Header-Datei <numeric> |
||
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, |
(1) | (constexpr seit C++20) |
template< class InputIt, class OutputIt, class BinaryOp > OutputIt partial_sum( InputIt first, InputIt last, |
(2) | (constexpr seit C++20) |
1) Wenn
[first, last) leer ist, tut die Funktion nichts. Andernfalls führt sie die folgenden Operationen in dieser Reihenfolge aus:
- Erstellt einen Akkumulator acc vom Werttyp von
InputItund initialisiert ihn mit *first. - Weist acc *d_first zu.
- Für jede ganze Zahl i im Bereich
[1,std::distance(first, last))werden die folgenden Operationen in dieser Reihenfolge ausgeführt:
a) Berechnet acc + *iter(bis C++20)std::move(acc) + *iter(seit C++20), wobei iter der nächste ite Iterator von first ist.
b) Weist das Ergebnis acc zu.
2) Gleich wie (1), berechnet jedoch op(acc, *iter)(bis C++20)op(std::move(acc), *iter)(seit C++20) anstelle von acc + *iter.
Gegeben binary_op als die tatsächliche binäre Operation
- Wenn eine der folgenden Bedingungen erfüllt ist, ist das Programm ill-formed (wohlgeformt):
- Der Werttyp von
InputItist nicht aus *first konstruierbar. - acc ist nicht beschreibbar 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 in den Werttyp von
InputItkonvertierbar.
- Der Werttyp von
- Gegeben d_last als der zurückgegebene Iterator, ist das Verhalten undefiniert, wenn eine der folgenden Bedingungen erfüllt ist:
- binary_op modifiziert ein Element in
[first,last)oder[d_first,d_last). - binary_op macht einen Iterator oder ein Teilbereich in
[first,last]oder[d_first,d_last]ungültig.
- binary_op modifiziert ein Element in
- ↑ Der tatsächlich zuzuweisende Wert ist das Ergebnis der Zuweisung im vorherigen Schritt. Wir gehen hier davon aus, dass das Zuweisungsergebnis acc ist.
Inhalt |
[edit] Parameter
| first, last | - | das Iteratorenpaar, das den Bereich der zu summierenden Elemente definiert |
| d_first | - | der Anfang des Zielbereichs; kann gleich first sein |
| 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. |
| Typanforderungen | ||
-InputIt muss die Anforderungen von LegacyInputIterator erfüllen. | ||
-OutputIt muss die Anforderungen an LegacyOutputIterator erfüllen. | ||
[edit] Rückgabewert
Iterator auf das Element nach dem letzten geschriebenen Element, oder d_first, wenn [first, last) leer ist.
[edit] Komplexität
Gegeben sei N als std::distance(first, last).
1) Genau N-1 Anwendungen von operator+.
2) Genau N-1 Anwendungen der binären Funktion op.
[edit] Mögliche Implementierung
| partial_sum (1) |
|---|
template<class InputIt, class OutputIt> constexpr // since 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 since C++20 *++d_first = sum; } return ++d_first; // or, since C++14: // return std::partial_sum(first, last, d_first, std::plus<>()); } |
| partial_sum (2) |
template<class InputIt, class OutputIt, class BinaryOp> constexpr // since 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 since C++20 *++d_first = acc; } return ++d_first; } |
[edit] Hinweise
acc wurde aufgrund der Auflösung von LWG issue 539 eingeführt. Der Grund für die Verwendung von acc anstelle der direkten Aufsummierung der Ergebnisse (d.h. *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);) liegt daran, dass die Semantik des letzteren bei folgenden Typunterschieden verwirrend ist:
- 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 zur Speicherung und Bereitstellung der Werte für jeden Berechnungsschritt.
- sein Typ ist der Werttyp von
InputIt - er wird nach d_first geschrieben
- sein Wert wird an operator+ oder op übergeben
- er 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: uses operator+(char, char) and assigns char values to int array std::partial_sum(i_array, i_array + 4, o_array); // Error: cannot assign not_int values to int array std::partial_sum(e_array, e_array + 4, o_array); // OK: performs conversions when needed // 1. creates “acc” of type char (the value type) // 2. the char arguments are used for long multiplication (char -> long) // 3. the long product is assigned to “acc” (long -> char) // 4. “acc” is assigned to an element of “o_array” (char -> int) // 5. go back to step 2 to process the remaining elements in the input range std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});
[edit] Beispiel
Führen Sie diesen Code aus
#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 << "The first " << v.size() << " even numbers are: "; // write the result to the cout stream std::partial_sum(v.cbegin(), v.cend(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // write the result back to the vector v std::partial_sum(v.cbegin(), v.cend(), v.begin(), std::multiplies<int>()); std::cout << "The first " << v.size() << " powers of 2 are: "; for (int n : v) std::cout << n << ' '; std::cout << '\n'; }
Ausgabe
The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024
[edit] 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 | kann die beteiligten Bereiche nicht modifizieren |
| LWG 539 | C++98 | die erforderlichen Tybanforderungen für das Ergebnis Auswertungen und Zuweisungen zum gültig machen fehlten |
hinzugefügt |
[edit] Siehe auch
| berechnet die Differenzen zwischen benachbarten Elementen in einer Reihe (Funktionstemplate) | |
| summiert oder faltet eine Reihe von Elementen (Funktionstemplate) | |
| (C++17) |
ähnlich wie std::partial_sum, schließt das i-te Eingabeelement in die i-te Summe ein (Funktionstemplate) |
| (C++17) |
ähnlich wie std::partial_sum, schließt das i-te Eingabeelement von der i-ten Summe aus (Funktionstemplate) |
