std::exclusive_scan

Определено в заголовочном файле `<numeric>`
template< class InputIt, class OutputIt, class T > OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init );	(1)	(начиная с C++17) (constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, T init );	(2)	(начиная с C++17)
template< class InputIt, class OutputIt, class T, class BinaryOp > OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init, BinaryOp op );	(3)	(начиная с C++17) (constexpr начиная с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp > ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, T init, BinaryOp op );	(4)	(начиная с C++17)

1) Эквивалентно exclusive_scan(first, last, d_first, init, std::plus<>().

3) Вычисляет эксклюзивную префиксную сумму с использованием op.

Для каждого целого числа i в [0, std::distance(first, last)) выполняются следующие операции в указанном порядке:

Создаётся последовательность, образованная из init, за которым следуют элементы [first, iter) в исходном порядке, где iter — следующий i_-й итератор first.
Вычисляется обобщённая некоммутативная сумма элементов последовательности с использованием op.
Результат присваивается *dest, где dest — следующий i_-й итератор d_first.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Обобщённая некоммутативная сумма последовательности элементов относительно бинарной операции binary_op определяется следующим образом:

Если последовательность содержит только один элемент, сумма равна значению этого элемента.
В противном случае выполняются следующие операции в указанном порядке:

Из последовательности выбираются любые два соседних элемента elem1 и elem2.
Вычисляется binary_op(elem1, elem2), а два элемента последовательности заменяются результатом.
Шаги 1 и 2 повторяются, пока в последовательности не останется один элемент.

Пусть binary_op — фактическая бинарная операция:

Результат не детерминирован, если binary_op не является ассоциативной (например, сложение чисел с плавающей точкой).
Если любое из следующих значений не преобразуется в T, программа некорректна:

binary_op(init, *first)
binary_op(init, init)
binary_op(*first, *first)

Если выполняется любое из следующих условий, поведение не определено:

T не удовлетворяет требованиям MoveConstructible.
binary_op изменяет любой элемент [first, last).
binary_op делает недействительным любой итератор или поддиапазон [first, last].

Параметры

first, last	-	пара итераторов, задающая диапазон суммируемых элементов
d_first	-	начало целевого диапазона; может быть равно `first`
policy	-	используемая политика выполнения
init	-	начальное значение
op	-	бинарный объект-функция, применяемый к результату разыменования входных итераторов, результатам других `op` и `init`
Требования к типам
-`InputIt` должен удовлетворять требованиям LegacyInputIterator.
-`OutputIt` должен удовлетворять требованиям LegacyOutputIterator.
-`ForwardIt1, ForwardIt2` должен удовлетворять требованиям LegacyForwardIterator.

Возвращаемое значение

Итератор на элемент, следующий за последним записанным элементом.

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1,2) \(\scriptsize O(N)\)O(N) применений std::plus<>().

3,4) \(\scriptsize O(N)\)O(N) применений op.

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, приводит к выбросу исключения, а ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Пример

#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<>{});
}

Вывод:

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

См. также

adjacent_difference	вычисляет разности между соседними элементами диапазона (шаблон функции)
accumulate	суммирует элементы диапазона или свёртывает их (шаблон функции)
partial_sum	вычисляет частичные суммы элементов диапазона (шаблон функции)
transform_exclusive_scan (C++17)	применяет вызываемый объект, затем вычисляет эксклюзивную префиксную сумму (шаблон функции)
inclusive_scan (C++17)	аналогичен `std::partial_sum`, но включает i^й входной элемент в i^ю сумму (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/exclusive_scan