std::inclusive_scan
Von cppreference.com
| Definiert in der Header-Datei <numeric> |
||
template< class InputIt, class OutputIt > OutputIt inclusive_scan( InputIt first, InputIt last, |
(1) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > |
(2) | (seit C++17) |
template< class InputIt, class OutputIt, class BinaryOp > OutputIt inclusive_scan( InputIt first, InputIt last, |
(3) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryOp > |
(4) | (seit C++17) |
template< class InputIt, class OutputIt, class BinaryOp, class T > |
(5) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, |
(6) | (seit C++17) |
1) Entspricht inclusive_scan(first, last, d_first, std::plus<>().
3) Berechnet die inklusive Präfixsumme mit op.
Für jede ganze Zahl i in
[0, std::distance(first, last)), werden nacheinander folgende Operationen ausgeführt:- Erstellt eine Sequenz, die aus den Elementen von
[first,iter]in der Reihenfolge gebildet wird, wobei iter der nächste ite Iterator von first ist. - Berechnet die verallgemeinerte nichtkommutative Summe der Sequenz über op.
- Weist das Ergebnis *dest zu, wobei dest der nächste ite Iterator von d_first ist.
5) Gleiches wie (3), aber jede erstellte Sequenz wird aus init gefolgt von den Elementen von
[first, iter] in der Reihenfolge gebildet.2,4,6) Dasselbe wie (1,3,5), aber gemäß policy ausgeführt.
Diese Überladungen nehmen an der Auflösungsauflösung teil, nur wenn alle folgenden Bedingungen erfüllt sind
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true. |
(bis C++20) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true. |
(seit C++20) |
Die *verallgemeinerte, nichtkommutative Summe* einer Sequenz von Elementen über eine binäre Operation binary_op ist wie folgt definiert:
- Wenn die Sequenz nur ein Element enthält, ist die Summe der Wert des Elements.
- Andernfalls werden die folgenden Operationen der Reihe nach ausgeführt
- Wählt zwei beliebige benachbarte Elemente elem1 und elem2 aus der Sequenz aus.
- Berechnet binary_op(elem1, elem2) und ersetzt die beiden Elemente in der Sequenz durch das Ergebnis.
- Wiederholt die Schritte 1 und 2, bis nur noch ein Element in der Sequenz verbleibt.
Gegeben binary_op als die tatsächliche binäre Operation
- Das Ergebnis ist nicht deterministisch, wenn die binary_op nicht assoziativ ist (z. B. Gleitkommaaddition).
- Für Überladungen (1-4) ist das Programm schlecht geformt, wenn binary_op(*first, *first) nicht in den Werttyp von decltype(first) konvertierbar ist.
- Für Überladungen (5,6) ist das Programm schlecht geformt, wenn einer der folgenden Werte nicht in `T` konvertierbar ist:
- binary_op(init, *first)
- binary_op(init, init)
- binary_op(*first, *first)
- Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
- Für Überladungen (1-4) ist der Werttyp von decltype(first) nicht MoveConstructible.
- Für Überladungen (5,6) ist `T` nicht MoveConstructible.
- binary_op modifiziert kein Element von
[first,last). - binary_op macht keinen Iterator oder Teilbereich von
[first,last]ungültig.
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Paar von Iteratoren, das den Quell-Bereich der zu summierenden Elemente definiert |
| d_first | - | der Anfang des Ziel-Bereichs; kann gleich first sein |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| init | - | der Anfangswert |
| op | - | binäre Funktionsobjekt, das auf das Ergebnis der Dereferenzierung der Eingabeiteratoren, die Ergebnisse anderer op und init (falls vorhanden) angewendet wird |
| 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.
[bearbeiten] Komplexität
Gegeben N als std::distance(first, last)
3-6) O(N) Anwendungen von 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
ExecutionPolicyeine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andereExecutionPolicyist das Verhalten implementierungsabhängig. - Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.
[bearbeiten] Beispiel
Führen Sie diesen Code aus
#include <functional> #include <iostream> #include <iterator> #include <numeric> #include <vector> int main() { std::vector data{3, 1, 4, 1, 5, 9, 2, 6}; std::cout << "Exclusive sum: "; std::exclusive_scan(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "), 0); std::cout << "\nInclusive sum: "; std::inclusive_scan(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n\nExclusive product: "; std::exclusive_scan(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "), 1, std::multiplies<>{}); std::cout << "\nInclusive product: "; std::inclusive_scan(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "), std::multiplies<>{}); }
Ausgabe
Exclusive sum: 0 3 4 8 9 14 23 25 Inclusive sum: 3 4 8 9 14 23 25 31 Exclusive product: 1 3 3 12 12 60 540 1080 Inclusive product: 3 3 12 12 60 540 1080 6480
[bearbeiten] Siehe auch
| berechnet die Differenzen zwischen benachbarten Elementen in einer Reihe (Funktionstemplate) | |
| summiert oder faltet eine Reihe von Elementen (Funktionstemplate) | |
| berechnet die partielle Summe einer Elementreihe (Funktionstemplate) | |
| (C++17) |
wendet eine aufrufbare Funktion an und berechnet dann einen inklusiven Scan (Funktionstemplate) |
| (C++17) |
ähnlich wie std::partial_sum, schließt das i-te Eingabeelement von der i-ten Summe aus (Funktionstemplate) |
