C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц Страница 40

выдает значения в консоль. Объект функции copy_and_advance работает с этим итератором вывода, присваивая ему целые числа, полученные от пользователя. По сути, данное действие выводит на экран присвоенные элементы. Но мы хотим видеть только четные числа, полученные от пользователя, и умножить их. Для этого оборачиваем функцию copy_and_advance в фильтр even, а затем — в преобразователь twice.

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 и функцию преобразования