std::transform_exclusive_scan

Определено в заголовочном файле <numeric>

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

template< class InputIt, class OutputIt, class T, 
          class BinaryOp, class UnaryOp >
OutputIt transform_exclusive_scan
    ( InputIt first, InputIt last, OutputIt d_first, T init,
      BinaryOp binary_op, UnaryOp unary_op );

(1)

(начиная с C++17)
(constexpr начиная с C++20)

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class T,
          class BinaryOp, class UnaryOp >
ForwardIt2 transform_exclusive_scan
    ( ExecutionPolicy&& policy,
      ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, T init,
      BinaryOp binary_op, UnaryOp unary_op );

(2)

(начиная с C++17)

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

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

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

2) То же, что и (1), но выполняется согласно 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 не является ассоциативной (например, сложение чисел с плавающей точкой).

Если какое-либо из следующих значений не преобразуется в T, программа некорректна:

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

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

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

Параметры

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

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

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

Сложность

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

1,2) \(\scriptsize O(N)\)O(N) применений unary_op и binary_op соответственно.

Исключения

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

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

Примечания

unary_op никогда не применяется к init.

Пример

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main()
{
    std::vector data{3, 1, 4, 1, 5, 9, 2, 6};

    auto times_10 = [](int x) { return x * 10; };

    std::cout << "10 times exclusive sum: ";
    std::transform_exclusive_scan(data.begin(), data.end(),
                                  std::ostream_iterator<int>(std::cout, " "),
                                  0, std::plus<int>{}, times_10);
    std::cout << "\n10 times inclusive sum: ";
    std::transform_inclusive_scan(data.begin(), data.end(),
                                  std::ostream_iterator<int>(std::cout, " "),
                                  std::plus<int>{}, times_10);
    std::cout << '\n';
}

Вывод:

10 times exclusive sum: 0 30 40 80 90 140 230 250 
10 times inclusive sum: 30 40 80 90 140 230 250 310

См. также

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

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