Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::inclusive_scan: inkluzywne sumy prefiksowe

std::inclusive_scan zapisuje dla każdej pozycji redukcję obejmującą bieżący element i zwraca koniec zakresu wynikowego.

Wersja: C++23

Składnia

template<class InputIt, class OutputIt>
constexpr OutputIt std::inclusive_scan(InputIt first, InputIt last, OutputIt result);

template<class InputIt, class OutputIt, class BinaryOp>
constexpr OutputIt std::inclusive_scan(InputIt first, InputIt last, OutputIt result, BinaryOp op);

template<class InputIt, class OutputIt, class BinaryOp, class T>
constexpr OutputIt std::inclusive_scan(InputIt first, InputIt last, OutputIt result, BinaryOp op, T init);

std::inclusive_scan(first,last,result) używa std::plus<>; przeciążenia przyjmują binary_op oraz opcjonalny init. Bez init pierwszy wynik pochodzi od pierwszego elementu, z init każdy prefiks zaczyna się od tej wartości. Zapis opisany jako result + K oznacza iterator przesunięty o K pozycji, nie wymaga operatora + od iteratora wyjściowego.

Dla 1,2,3,4 przykład zapisuje 1,3,6,10; zwrócony iterator jest końcem czteroelementowego wyniku, więc końcowe porównanie drukuje 1. Dozwolone jest result == first, co umożliwia skan w miejscu.

Operacja nie może modyfikować wejścia ani zakresu wynikowego poza przypisaniami algorytmu i nie może unieważniać iteratorów. Grupowanie uogólnionej sumy nie jest ustalone; dla operacji nieasocjacyjnej, np. zmiennoprzecinkowego dodawania, wynik może być niedeterministyczny. Przy standardowej execution policy nieprzechwycony wyjątek operacji elementu prowadzi do std::terminate, a brak pamięci tymczasowej potrzebnej wykonaniu równoległemu może rzucić std::bad_alloc; wariant bez policy propaguje wyjątek operacji.

Przykłady

#include <array>
#include <iostream>
#include <numeric>

int main() {
    const std::array<int, 4> input{1, 2, 3, 4};
    std::array<int, 4> output{};
    const auto end = std::inclusive_scan(input.begin(), input.end(), output.begin());

    for (int value : output) std::cout << value << ' ';
    std::cout << (end == output.end()) << '\n';
}

Wynik

1 3 6 10 1

std::inclusive_scan → 1 3 6 10 1

Źródła