Reduce.md

Разбор задачи Reduce

Условие

Напишите аналог функции стандартной библиотеки std::reduce. Заголовок функции должен быть таким:

template<typename Iterator, typename T, typename BinaryOp>
T Reduce(Iterator first, Iterator last, T init, BinaryOp op);

Здесь:

• Iterator как минимум является forward-итератором;
• T - тип элементов в контейнере, на которые указывают итераторы типа Iterator;
• op - бинарная операция, которая принимает два аргумента типа T и возвращает элемент типа T. Гарантируется, что операция ассоциативная и коммутативная.

Возвращаемое значение функции Reduce может быть определенно рекурсивно следующим образом:

• если first == last, то Reduce(first, last, init, op) равно значению init;
• иначе Reduce(first, last, init, op) равно op(*first, Reduce(std::next(first), last, init, op)).

Из такого определения не следует, что задачу нужно решать рекурсивно.

---

Заметим, что примером операции op может быть обычное сложение или умножение чисел. В таком случае, если init равно 0 (или, соответственно, 1), мы после вызова функции получим сумму или произведение элементов.

Неверные решения

1. Использовать std::reduce. В любой другой ситуации это на самом деле единственное верное решение. Однако, в данной задаче мы явно просим написать свою реализацию и решение, использующее std::reduce, получает вердикт CE.

2. Использовать рекурсивное определение в качестве идеи для реализации. Каждый итератор может занимать минимум 8 байт. Аргумент op занимает 8 байт. Аргумент init может занимать 8 байт, если T является типом int64_t, например. В итоге, каждый уровень рекурсии добавляет избыточное потребление памяти в 32 байта. В сумме, 32*N байт избыточной памяти, что в действительности может быть сильно оптимизировано до O(1) дополнительной памяти. Такие решения получают вердикт ML.

3. Пройтись по массиву в обратном порядке и применить операцию с соседними элементами. Как минимум, проходиться по последовательности в обратном порядке без надобной причины не естественно. Также функция должна работать как минимум для forward-итераторов, что сказано в условии. В итоге попытка сделать декремент итератора приводит к вердикту CE.

4. Скорее не решение, а возможная ошибка - допустить выхода итератора за границы [first,last). Это ошибка и приводит к неопределенному поведению, что ловится санитайзером и что нельзя допускать. Такие решения получают RE.

Решение

Так как операция коммутативна и ассоциативна, то можно поменять порядок её применения и начать с первых элементов. Пройдёмся циклом и применим функцию op последовательно к соседним элементам:

template <typename Iterator, typename T, typename BinaryOp>
T Reduce(Iterator first, Iterator last, T init, BinaryOp op) {
    while (begin != end) {
        init = op(init, *begin);
        ++begin;
    }

    return init;
}