std:: reduce

From cppreference.net

Определено в заголовке `<numeric>`
template < class InputIt > typename std:: iterator_traits < InputIt > :: value_type reduce ( InputIt first, InputIt last ) ;	(1)	(начиная с C++17) (constexpr начиная с C++20)
template < class ExecutionPolicy, class ForwardIt > typename std:: iterator_traits < ForwardIt > :: value_type reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last ) ;	(2)	(начиная с C++17)
template < class InputIt, class T > T reduce ( InputIt first, InputIt last, T init ) ;	(3)	(начиная с C++17) (constexpr начиная с C++20)
template < class ExecutionPolicy, class ForwardIt, class T > T reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, T init ) ;	(4)	(начиная с C++17)
template < class InputIt, class T, class BinaryOp > T reduce ( InputIt first, InputIt last, T init, BinaryOp op ) ;	(5)	(начиная с C++17) (constexpr начиная с C++20)
template < class ExecutionPolicy, class ForwardIt, class T, class BinaryOp > T reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, T init, BinaryOp op ) ;	(6)	(начиная с C++17)

1) Эквивалентно reduce ( first, last, typename std:: iterator_traits < InputIt > :: value_type { } ) .

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

5) Сокращает диапазон

first

last

, возможно переставленный и агрегированный неопределённым образом, вместе с начальным значением init с помощью операции op .

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

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

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

Дано binary_op в качестве фактической бинарной операции:

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

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

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

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

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

Содержание

Параметры

first, last	-	пара итераторов, определяющих диапазон элементов, к которым применяется алгоритм
init	-	начальное значение обобщённой суммы
policy	-	политика выполнения, которая будет использоваться
op	-	бинарный FunctionObject , который будет применён в неопределённом порядке к результату разыменования входных итераторов, результатам других op и init .
Требования к типам
- `InputIt` должен удовлетворять требованиям LegacyInputIterator .
- `ForwardIt` должен удовлетворять требованиям LegacyForwardIterator .

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

1-4) Обобщенная сумма init и элементов диапазона

first

last

с использованием std:: plus <> ( ) .

5,6) Обобщённая сумма init и элементов диапазона

first

last

с использованием операции op .

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

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

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

Сложность

Дано $\scriptsize N$ $N$ как std:: distance ( first, last ) :

1-4)

O(N)

применений std:: plus <> ( ) .

5,6)

O(N)

применений op .

Исключения

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

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

Примечания

std::reduce ведёт себя как std::accumulate за исключением того, что элементы диапазона могут быть сгруппированы и переупорядочены произвольным образом.

Пример

Сравнение между std::reduce и std::accumulate :

Запустить этот код

#if PARALLEL
#include <execution>
#define SEQ std::execution::seq,
#define PAR std::execution::par,
#else
#define SEQ
#define PAR
#endif
#include <chrono>
#include <iomanip>
#include <iostream>
#include <locale>
#include <numeric>
#include <utility>
#include <vector>
int main()
{
    std::cout.imbue(std::locale("en_US.UTF-8"));
    std::cout << std::fixed << std::setprecision(1);
    auto eval = [](auto fun)
    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        const auto [name, result] = fun();
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::setw(28) << std::left << name << "сумма: "
                  << result << '\t' << "время: " << ms.count() << " мс\n";
    };
    {
        const std::vector<double> v(100'000'007, 0.1);
        eval([&v]{ return std::pair{"std::accumulate (double)",
            std::accumulate(v.cbegin(), v.cend(), 0.0)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, double)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, double)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
    {
        const std::vector<long> v(100'000'007, 1);
        eval([&v]{ return std::pair{"std::accumulate (long)",
            std::accumulate(v.cbegin(), v.cend(), 0l)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, long)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, long)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
}

Возможный вывод:

// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out
std::accumulate (double)    сумма: 10,000,000.7	время: 356.9 мс
std::reduce (seq, double)   сумма: 10,000,000.7	время: 140.1 мс
std::reduce (par, double)   сумма: 10,000,000.7	время: 140.1 мс
std::accumulate (long)      сумма: 100,000,007	время: 46.0 мс
std::reduce (seq, long)     сумма: 100,000,007	время: 67.3 мс
std::reduce (par, long)     сумма: 100,000,007	время: 63.3 мс
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    сумма: 10,000,000.7	время: 353.4 мс
std::reduce (seq, double)   сумма: 10,000,000.7	время: 140.7 мс
std::reduce (par, double)   сумма: 10,000,000.7	время: 24.7 мс
std::accumulate (long)      сумма: 100,000,007	время: 42.4 мс
std::reduce (seq, long)     сумма: 100,000,007	время: 52.0 мс
std::reduce (par, long)     сумма: 100,000,007	время: 23.1 мс

Смотрите также

accumulate	суммирует или сворачивает диапазон элементов (шаблон функции)
transform	применяет функцию к диапазону элементов, сохраняя результаты в целевом диапазоне (шаблон функции)
transform_reduce (C++17)	применяет вызываемый объект, затем выполняет неупорядоченную редукцию (шаблон функции)
ranges::fold_left (C++23)	выполняет левую свертку диапазона элементов (функциональный объект алгоритма)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std:: reduce

Содержание

Параметры

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

Сложность

Исключения

Примечания

Пример

Смотрите также