Monthly Archives: Февраль 2015

Перегрузка замыканий

Расширение арсенала C++ анонимными функциями и замыканиями в стандарте 2011 года сделало существенно более удобным использование алгоритмов STL и подобных им функций-шаблонов.

Пример. Удалить из вектора v все числа вне диапазона [-a, a].

v.erase(remove_if(v.begin(), v.end(),
    [a](double x) { return a < abs(x); }), v.end());

В случае C++14 не обязательно указывать конкретный принимаемый тип, что позволяет обобщить некоторые случаи. Например, в духе карринга

template <class Pred>
inline auto erase_remove_if(Pred pred)
{
  return [pred](auto &v)
  {
    v.erase(remove_if(begin(v), end(v), pred), end(v));
  };
}

// удалить из v все значения вне [-a, a]
erase_remove_if([a](auto x) { return a < abs(x); })(v);

С формальной точки зрения, замыкания (даже в варианте C++14) являются не расширением возможностей C++03, а своего рода «синтаксическим сахаром». Код, приведённый выше, можно переписать как

// C++03 version
template <class T>
class Outside_symsegment
{
  T a;
public:
  
  explicit Outside_symsegment(const T &a)
      : a(a) {}

  template <class X> // *
  bool operator()(const X &x) const
  {
    return a < abs(x);
  }
};

template <class T>
inline Outside_symsegment<T>
  make_outside_symsegment(const T &a)
{
  return Outside_symsegment<T>(a);
}

template <class Pred>
class Erase_remove_if
{
  Pred pred;
public:
  explicit Erase_remove_if(const Pred &pred)
      : pred(pred) {}

  template <class T>
  void operator()(T &v) const
  {
    v.erase(remove_if(v.begin(), v.end(), pred), v.end());
  }
};

template <class Pred>
inline Erase_remove_if<Pred>
  erase_remove_if(Pred pred)
{
  return Erase_remove_if<Pred>(pred);
}

// удалить из v все значения вне [-a, a]
erase_remove_if(make_outside_symsegment(a))(v);

* Замечание. Вариант для C++14 предоставляет возможность автоматического вывода возвращаемых типов (в лямбда-выражении можно не указывать возвращаемый тип), что во многих случаях можно имитировать средствами C++03, но здесь рассматриваться не будет. С другой стороны, можно использовать ещё одно нововведение C++11: decltype.

Таким образом, лямбда-выражение может создавать новый тип функтора с функцией-шаблоном operator(). Одним из возможных применений функторов является реализация паттерна «Посетитель» (Visitor) с использованием статической диспетчеризации для обработки разнотипных объектов.

Пример. В задаче сериализации структур данных можно предложить разные форматы, одновременно поддерживающие структуры «массив» и «множество» (набор уникальных элементов).

template <class Ostream>
class Writer
{
  Ostream &os;
  template <class... Any>
  void print(Any&&... any)
  {
    // это "трюк", дающий небольшое удобство:
    // возможность писать в print подряд набор значений;
    int _[] = { ((*this)(forward<Any>(any)), 0)... };
    // ну и маленькая демонстрация variadic templates :)
  }

  template <class Name, class Lit, class Cont>
  void prints
  (
    const Name &name,
    const Cont &cont, 
    Lit open,
    Lit delim,
    Lit close
  )
  {
    print(name, open);
    auto p = begin(cont), e = end(cont);
    if (p != e)
    {
      print(*p);
      while (++p != e)
        print(delim, *p);
    }
    print(close);    
  }
  
public:
  explicit Writer(Ostream &os)
      : os(os) {}

  // общий вариант, полагается на оператор <<
  template <class Any>
  void operator()(const Any &x)
  {
    os << x;
  }

  // вариант для строк, берёт содержимое в кавычки
  template <class Char, class Traits, class Alloc>
  void operator()(const basic_string<Char, Traits, Alloc> &s)
  {
    os << quoted(s);
  }

  template <class Name, class Item, class Alloc>
  void operator()(const Name &name, const vector<Item, Alloc> &v)
  {
    prints(name, v, ": [", ", ", "]");
  }

  template <class Name, class Item, class Comp, class Alloc>
  void operator()(const Name &name, const set<Item, Comp, Alloc> &s)
  {
    prints(name, s, ": {", ", ", "}");
  }
  
  // можно продолжить для других контейнеров
};

template <class Ostream>
inline auto make_writer(Ostream &os)
{
  return Writer<Ostream>(os);
}

(результат работы данного кода на ideone.com)

Можно ли сделать конструкцию, позволяющую создавать подобные перегруженные функторы на месте использования, например, из замыканий? Как нетрудно догадаться, ответ на этот вопрос положительный.

Для этого я воспользуюсь достаточно простой идеей: каждый перегруженный метод представлен либо самостоятельным функтором — объектом уникального класса, либо указателем (или ссылкой) на функцию. Собрать их все в один функтор можно с помощью наследования либо от того же класса, объектом которого является функтор, либо от класса-обёртки указателя на функцию.

Для этого определим метафункцию Functor_caller, позволяющую получить нужный базовый класс.

template <class F>
struct Functor_caller
{
  using type = F;
};

template <class R, class... Args>
struct Functor_caller<R (*)(Args...)>
{
  struct type
  {
    using ftype = R (*)(Args...);
    const ftype ptr;
    type(ftype ptr): ptr(ptr) {}

    R operator()(Args... args) const
    {
      return ptr(forward<Args>(args)...);
    }
  };
};

Для комбинирования пары классов в один производный класс через наследование определим вспомогательный шаблон Compose

template <class Base1, class Base2>
struct Compose : Base1, Base2
{
  template <class Init1, class Init2>
  Compose(Init1&& init1, Init2&& init2)
    : Base1(forward<Init1>(init1)),
      Base2(forward<Init2>(init2))
      {}

  Compose(Compose<Base1, Base2>&&) = default;
  using Base1::operator();
  using Base2::operator();
};

Теперь, наконец, можно определить функцию make_switch, создающую комбинированный функтор из набора функторов

template <class Functor>
inline auto make_switch(Functor&& functor)
{
  return typename Functor_caller<decay_t<Functor>>::
    type(forward<Functor>(functor));
}

template <class Functor, class... Tail>
inline auto make_switch(Functor&& functor, Tail&&... tail)
{
  auto head_object = make_switch(forward<Functor>(functor));
  auto tail_object = make_switch(forward<Tail>(tail)...);

  using head_type = decay_t<decltype(head_object)>;
  using tail_type = decay_t<decltype(tail_object)>;

  return Compose<head_type, tail_type>
    (move(head_object), move(tail_object));
}

(код целиком вместе с простеньким тестом)

Данная функция использует рекурсию времени компиляции — достаточно естественный приём при работе с шаблонами с переменным числом параметров. Шаблон decay_t введён стандартом C++14.

К сожалению, такое решение задачи о перегрузки замыканий (и в общем комбинирования произвольных функторов) далеко не безупречно.

Во-первых, созданный составной объект хранит во время исполнения все переданные make_switch указатели/ссылки на функции, даже если эти функции заданы во время компиляции (как в примере по ссылке выше), и вместо «прошитого» вызова совершает вызов по указателю, что в некоторых случаях чревато заметными дополнительными расходами процессорного времени.

Во-вторых, это решение не предоставляет возможность легко реализовать аналог рассмотренного выше класса Writer на основе замыканий, так как их возможности создания шаблонов operator() ограничены словом auto, не позволяющим «на месте» отделить произвольный vector от произвольного set, т.е. имеем ситуацию или полностью заданный тип или произвольный тип, без возможности сопоставить параметры шаблона образцу.