Шрифт:
Интервал:
Закладка:
std::accumulate(it, end_it,
std::ostream_iterator<int>{std::cout, ", "},
filter(even)(
map(twice)(
copy_and_advance
)
));
std::cout << 'n';
}
10. Компиляция и запуск программы дадут следующий результат. Значения 1, 3 и 5 отбрасываются, поскольку являются нечетными, а 2, 4 и 6 выводятся на экран после их умножения на два.
$ echo "1 2 3 4 5 6" | ./transform_if
4, 8, 12,
Как это работает
Этот пример выглядит довольно сложным, поскольку мы активно использовали вложенные лямбда-выражения. Чтобы понять, как все работает, взглянем на внутреннее содержимое функции std::accumulate. Именно так она выглядит в обычной реализации, предлагаемой в библиотеке STL:
template <typename T, typename F>
T accumulate(InputIterator first, InputIterator last, T init, F f)
{
for (; first != last; ++first) {
init = f(init, *first);
}
return init;
}
Параметр функции f выполняет здесь остальную работу, а цикл собирает результаты в предоставленной пользователем переменной init. В обычном варианте использования диапазон итераторов может представлять собой вектор чисел, например 0, 1, 2, 3, 4, а переменная init будет иметь значение 0. Функция f является простой бинарной функцией, которая может определять сумму двух элементов с помощью оператора +.
В нашем примере цикл просто складывает все элементы и записывает результат в переменную init, это выглядит, например, так: init = (((0+1)+2)+3)+4. Подобная запись помогает понять, что std::accumulate представляет собой функцию свертки. Выполнение свертки для диапазона значений означает применение бинарной операции для переменной-аккумулятора и каждого элемента диапазона пошагово (результат каждой операции является значением-аккумулятором для последующей операции). Поскольку эта функция обобщена, с ее помощью можно решать разные задачи, например реализовать функцию std::transform_if! Функция f в таком случае будет называться функцией reduce (свертки).
Очень прямолинейная реализация функции transform_if будет выглядеть так:
template <typename InputIterator, typename OutputIterator,
typename P, typename Transform>
OutputIterator transform_if(InputIterator first, InputIterator last,
OutputIterator out,
P predicate, Transform trans)
{
for (; first != last; ++first) {
if (predicate(*first)) {
*out = trans(*first);
++out;
}
}
return out;
}
Данная реализация очень похожа на std::accumulate, если считать параметр out переменной init и каким-то образом заменить функцией f конструкцию if-construct и ее тело!
Мы на самом деле сделали это — создали данную конструкцию if-construct и ее тело с помощью объекта бинарной функции, предоставленного в качестве параметра функции std::accumulate:
auto copy_and_advance ([](auto it, auto input) {
*it = input;
return ++it;
});
Функция std::accumulate помещает переменную init в параметр бинарной функции it. Второй параметр — текущее значение из диапазона, получаемое в цикле. Мы предоставили итератор вывода как параметр init функции std::accumulate. Таким образом, функция std::accumulate не считает сумму, а перемещает элементы, по которым итерирует, в другой диапазон. Это значит следующее: мы повторно реализовали функцию std::copy, которая пока что не имеет предикатов и преобразований.
Фильтрацию с помощью предиката добавим путем обертывания функции copy_and_advance в другой объект функции, который пользуется функцией-предикатом:
template <typename T>
auto filter(T predicate)
{
return [=] (auto reduce_fn) {
return [=] (auto accum, auto input) {
if (predicate(input)) {
return reduce_fn(accum, input);
} else {
return accum;
}
};
};
}
Эта конструкция на первый взгляд выглядит сложной, но посмотрим на конструкцию if. Если функция-предикат вернет значение true, то параметры будут перенаправлены функции reduce_fn, в роли которой в нашем случае выступает функция copy_and_advance. Если же предикат вернет значение false, то переменная accum, выступающая в роли переменной init функции std::accumulate, будет возвращена без изменений. Так мы реализуем ту часть операции фильтрации, где пропускаем элемент. Конструкция if находится внутри лямбда-выражения, которое имеет такую же сигнатуру бинарной функции, что и функция copy_and_advance; это делает ее хорошей заменой.
Теперь мы можем отфильтровать элементы, но все еще не выполняем их преобразование. Это делается с помощью вспомогательной функции map:
template <typename T>
auto map(T fn)
{
return [=] (auto reduce_fn) {
return [=] (auto accum, auto input) {
return reduce_fn(accum, fn(input));
};
};
}
Теперь код выглядит гораздо проще. Он тоже содержит внутреннее лямбда-выражение, которое имеет такую же сигнатуру, как и функция copy_and_advance, поэтому способен заменить ее. Реализация просто направляет дальше входные значения, но притом преобразует правый параметр вызова бинарной функции с помощью функции fn.
Далее, когда мы воспользуемся этими вспомогательными функциями, напишем следующее выражение:
filter(even)(
map(twice)(
copy_and_advance
)
)
Вызов filter(even) захватывает предикат even и дает функцию, которая принимает бинарную функцию, чтобы обернуть ее в другую бинарную функцию, выполняющую фильтрацию. Функция map(twice) делает то же самое с функцией преобразования twice, но оборачивает бинарную функцию copy_and_advance в другую бинарную функцию, всегда преобразующую правый параметр.
Не выполнив оптимизацию, мы получим сложнейшую конструкцию, состоящую из вложенных функций, которые вызывают другие функции и при этом выполняют совсем немного работы. Однако компилятор может легко оптимизировать подобный код. Полученная бинарная функция так же проста, как и результат более прямолинейной реализации функции transform_if. Мы ничего не теряем с точки зрения производительности, приобретая компонуемость, свойственную функциям, поскольку смогли объединить предикат even и функцию преобразования