std::exclusive_scan
Von cppreference.com
| Definiert in der Header-Datei <numeric> |
||
| template< class InputIt, class OutputIt, class T > OutputIt exclusive_scan( InputIt first, InputIt last, |
(1) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > |
(2) | (seit C++17) |
| template< class InputIt, class OutputIt, class T, class BinaryOp > |
(3) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, |
(4) | (seit C++17) |
1) Entspricht exclusive_scan(first, last, d_first, init, std::plus<>().
3) Berechnet die exklusive Präfixsumme mittels op.
Für jede ganze Zahl i in
[0, std::distance(first, last)), werden nacheinander folgende Operationen ausgeführt:- Erzeugt eine Sequenz, die durch init gefolgt von den Elementen von
[first,iter)in Reihenfolge gebildet wird, wobei iter der nächste ite Iterator von first ist. - Berechnet die generalisierte nicht-kommutative Summe der Sequenz über op.
- Weist das Ergebnis *dest zu, wobei dest der nächste ite Iterator von d_first ist.
2,4) Dasselbe wie (1,3), aber ausgeführt gemäß policy.
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 nicht-kommutative 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).
- Wenn einer der folgenden Werte nicht in
Tkonvertierbar ist, ist das Programm schlecht geformt
- binary_op(init, *first)
- binary_op(init, init)
- binary_op(*first, *first)
- Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
-
Tist 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 Iteratorenpaar, das den Bereich der zu summierenden Elemente definiert |
| d_first | - | der Anfang des Zielbereichs; kann gleich first sein |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| init | - | der Anfangswert |
| op | - | binäres FunctionObject, das auf das Ergebnis der Dereferenzierung der Eingabeiteratoren, die Ergebnisse anderer op und init 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,4) 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 exklusiven Scan (Funktionstemplate) |
| (C++17) |
ähnlich wie std::partial_sum, schließt das i-te Eingabeelement in die i-te Summe ein (Funktionstemplate) |
