Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::exclusive_scan: prefixos sem o elemento atual

std::exclusive_scan escreve em cada posição uma redução do valor inicial e dos elementos anteriores, excluindo o elemento dessa posição.

Versão: C++23

Sintaxe

template<class InputIterator, class OutputIterator, class T, class BinaryOperation>
constexpr OutputIterator exclusive_scan(
    InputIterator first, InputIterator last, OutputIterator result,
    T init, BinaryOperation binary_op);

std::exclusive_scan(first, last, result, init, binary_op) de <numeric> escreve N resultados e devolve o iterador de saída avançado N posições. Com entrada não vazia, o primeiro resultado é init e a posição K só inclui elementos anteriores a K; sem operador usa std::plus<>.

Para {3, 1, 4} com init = 10, o exemplo produz {10, 13, 14}. A notação posicional da norma não exige operator+ aos iteradores sequenciais: bastam iteradores de entrada/saída adequados e espaço para N resultados.

T tem de ser construível por movimento, as chamadas exigidas a binary_op têm de produzir valores convertíveis em T e a operação não pode modificar intervalos nem invalidar iteradores. result pode ser igual a first; não dependas de outra sobreposição. O agrupamento pode variar, pelo que uma operação não associativa pode ser não determinística. Na sobrecarga mostrada sem política, uma exceção de binary_op propaga-se normalmente. Com uma política de execução padrão, uma exceção não capturada de uma operação sobre elementos chama std::terminate; a impossibilidade de alocar memória temporária durante a execução paralela pode lançar std::bad_alloc.

Exemplos

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

int main() {
    const std::array input{3, 1, 4};
    std::array<int, 3> output{};
    std::exclusive_scan(input.begin(), input.end(), output.begin(), 10);
    std::cout << output[0] << ' ' << output[1] << ' ' << output[2] << '\n';
}

Resultado

10 13 14

std::exclusive_scan → 10 13 14

Fontes