Tag Archives: метафункция

Вычисление чисел Фибоначчи во время компиляции С++14

Шесть лет назад я привёл пример вычисления целочисленных констант в рамках стандарта C++03. Последний стандарт C++14 ввёл новый вид шаблона: шаблоны переменных. Данная конструкция не только позволяет писать то же самое намного более коротко, но и использовать практически произвольные типы данных.

Пример чисел Фибоначчи, вычисляемых во время компиляции в плавающей точке:

template <unsigned N>
const double fib = fib<N-1> + fib<N-2>;

template <>
const double fib<0> = 0.;

template <>
const double fib<1> = 1.;

Конечно, если константы требуется использовать как параметры шаблонов (для чего, собственно, они и вычисляются во время компиляции), то они должны быть целочисленными и, кроме того, использовать ключевое слово constexpr:

template <unsigned N>
constexpr unsigned long long fib = fib<N-1> + fib<N-2>;

template <>
constexpr unsigned long long fib<0> = 0;

template <>
constexpr unsigned long long fib<1> = 1;
Реклама

Обобщённая функция удаления элементов из контейнера

Введение

Стандартная библиотека C++ не предлагает общего интерфейса для удаления элементов из произвольного контейнера. Тем не менее, средства метапрограммирования и принцип SFINAE позволяют реализовать такой интерфейс (например, в виде функции-шаблона) поверх стандартных компонент и выполнять выбор подходящего для переданного контейнера метода на этапе компиляции. Наша функция будет удалять элементы контейнера, удовлетворяющие произвольному предикату, переданному в виде функтора. Обычно это линейная по числу элементов контейнера операция, в случае же ассоциативных контейнеров, реализованных в виде деревьев, она может быть линеарифмической.

Далее предполагаем следующую «шапку».

#include <algorithm>
#include <iterator>
#include <type_traits>
#include <utility>
using namespace std;

Реализации свободной функции для разных видов контейнеров

Контейнеры-списки реализуют желаемую функцию в виде функции-члена, которой и следует переадресовать вызов.

/// Удаляет элементы, для которых pred возвращает истину,
/// из связных списков (std::list, std::forward_list).
template <class List, class Pred> inline
void list_remove_if(List &l, Pred pred)
{
  l.remove_if(pred);
}

Прочие линейные контейнеры с изменяемым размером (вектор, дек) предполагают перемещение элементов в начало (затирая удаляемые) с сохранением относительного порядка и «отрезание хвоста» контейнера.

/// Удаляет элементы, для которых pred возвращает истину,
/// из линейных контейнеров (std::vector, std::deque).
template <class Vector, class Pred> inline
void vector_remove_if(Vector &v, Pred pred)
{
  v.erase(remove_if(begin(v), end(v), pred), end(v));
}

Ассоциативные контейнеры требуют прямого обхода с удалением конкретных элементов.

/// Удаляет элементы, для которых pred возвращает истину,
/// из ассоциативных контейнеров (разные варианты set и map).
/// В случае map предикат вычисляется для пары ключ-значение.
template <class Assoc, class Pred>
void assoc_remove_if(Assoc &a, Pred pred)
{
  for (auto it = begin(a), it_end = end(a); it != it_end; )
    if (pred(*it))
      it = a.erase(it);
    else
      ++it;
}

 
Автоматический выбор правильного варианта по виду контейнера

Автоматический выбор между представленными тремя вариантами можно организовать через банальную лобовую перегрузку функции remove_if для std::list, std::vector, std::set и т.д. Но мне не нравится этот вариант, так как он не способен автоматически «принять» нестандартные контейнеры, удовлетворяющие интерфейсу того или иного STL-контейнера — для каждого вида контейнера надо будет написать явную перегрузку.

Вместо этого мы можем заставить компилятор автоматически выбирать тот или иной вариант в зависимости от того, какие операции доступны для контейнера (сделать это позволяет SFINAE).

Вариант list_remove_if годится тогда, когда контейнер предоставляет метод remove_if (сам контейнер лучше знает как эффективно удалять из него элементы). Вариант vector_remove_if годится для контейнеров с методом удаления диапазона erase(iterator, iterator) и итератором произвольного доступа (формально достаточно итератора однонаправленного последовательного доступа («forward»), но тогда будут подходить и ассоциативные контейнеры). Наконец, вариант assoc_remove_if годится для всех контейнеров с методом iterator erase(iterator).

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

namespace impl
{
  /// Категория итератора для условного типа "не-итератора".
  struct Not_an_iterator_tag {};
  /// Специальный тип, означающий отсутствие типа,
  /// но позволяющий создавать объекты (в отличие от void).
  struct No_type_tag {};
  /// Условный тип "не-итератор", имитирует итератор с
  /// определёнными вложенными типами std::iterator_traits.
  struct False_iterator
    : iterator<Not_an_iterator_tag, No_type_tag> {};
 
  /// Метафункция. Извлекает тип итератора коллекции X 
  /// (использует для этого [std::]begin).
  /// Если begin(X) не определена, возвращает False_iterator.
  template <class X>
  class Collection_iterator
  {
    template <class Y>
    static False_iterator check(unsigned long, Y&&);
 
    template <class Y>
    static auto check(int, Y &&y) -> decltype(begin(y));
 
  public:
    using type = decltype(check(1, declval<X>()));
  };
 
  /// Проверяет, является ли X "коллекцией".
  /// Коллекция -- объект, для которого свободные функции
  /// begin и end возвращают итераторы с категорией,
  /// приводимой к forward_iterator_tag.
  /// Проверяется только [std::]begin.
  /// В качестве коллекции может выступать любой STL контейнер,
  /// объект std::basic_string или статический массив.
  template <class X>
  struct Is_collection
    : is_convertible<typename
        iterator_traits<typename Collection_iterator<X>::type>::iterator_category,
        forward_iterator_tag> {};
 
  ///////////////////////////////////////////////////////////////////////////// 
  /// Проверка, возможен ли вызов assoc_remove_if для объекта Cont.
  template <class Cont>
  class Assoc_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    template <class C>
    static auto check(int, C &&c) ->
      is_convertible<
        decltype(c.erase(begin(c))),
        decltype(begin(c))>;
 
    static const bool
      erase_defined = decltype(check(1, declval<Cont>()))::value,
      is_collection = Is_collection<Cont>::value;
 
  public:
    using type = integral_constant<bool, erase_defined && is_collection>;
    static const bool value = type::value;
  };
 
  /// Проверка, возможен ли вызов vector_remove_if для объекта Cont.
  template <class Cont>
  class Vector_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    template <class C>
    static auto check(int, C &&c) -> integral_constant<bool,
         is_convertible<typename
            iterator_traits<typename Collection_iterator<C>::type>::iterator_category,
            random_access_iterator_tag>::value
      && is_convertible<
            decltype(c.erase(begin(c), end(c))),
            decltype(begin(c))>::value>;
 
  public:
    using type = decltype(check(1, declval<Cont>()));
    static const bool value = type::value;
  };
 
  /// Проверка, возможен ли вызов list_remove_if.
  template <class Cont>
  class List_remove_if_possible
  {
    template <class C>
    static false_type check(unsigned long, C&&);
 
    // Универсальный предикат.
    struct Unipred
    {
      template <class T> 
      bool operator()(const T&) { return false; }
    };
 
    template <class C>
    static auto check(int, C &&c) ->
      decltype((void)c.remove_if(Unipred{}), true_type{});
 
  public:
    using type = decltype(check(1, declval<Cont>()));
    static const bool value = type::value;
  };
 
  ///////////////////////////////////////////////////////////////////////////// 
  // Статическая диспетчеризация вызова
  // Теги для статического выбора соответствующего варианта remove_if.
  struct Assoc_remove_if_tag {};
  struct Vector_remove_if_tag {};
  struct List_remove_if_tag {};
 
  /// Выбор подходящего тега remove_if для контейнера.
  template <class Cont>
  class Remove_if_tag
  {
    static const bool
      assoc_possible  = Assoc_remove_if_possible<Cont>::value,
      vector_possible = Vector_remove_if_possible<Cont>::value,
      list_possible   = List_remove_if_possible<Cont>::value;
 
    static_assert(assoc_possible || vector_possible || list_possible,
        "remove_if can not be called for this type");
 
  public:
    using type = conditional_t<list_possible, List_remove_if_tag,
                 conditional_t<vector_possible, Vector_remove_if_tag,
                 conditional_t<assoc_possible, Assoc_remove_if_tag,
                               void>>>;
  };

  // Перенаправление вызова remove_if на варианты для различных типов контейнеров.
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, Assoc_remove_if_tag)
  { assoc_remove_if(c, pred); }
 
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, Vector_remove_if_tag)
  { vector_remove_if(c, pred); }
 
  template <class Cont, class Pred> inline
  void remove_if(Cont &c, Pred pred, List_remove_if_tag)
  { list_remove_if(c, pred); }
}

/// Вызов разрешается статически в подходящий вариант в зависимости от типа контейнера.
template <class Cont, class Pred> inline
void remove_if(Cont &container, Pred pred)
{
  impl::remove_if(container, pred, typename impl::Remove_if_tag<Cont>::type{});
}

Итак, remove_if(контейнер, предикат) выбирает один из трёх способов удаления элементов, удовлетворяющих предикату, в зависимости от операций, предоставляемых контейнером. Приведённый код целиком и небольшой проверочный код: ideone, Bitbucket.

UPD. Увидел, что нечто подобное предлагалось для добавления в стандартную библиотеку. Пока оно представлено в виде расширения в пространстве имён experimental.

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

Расширение арсенала 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, т.е. имеем ситуацию или полностью заданный тип или произвольный тип, без возможности сопоставить параметры шаблона образцу.

C++11: SFINAE реализация is_callable

В стандарт C++11 из Boost попал набор шаблонов, позволяющих выполнять некоторые манипуляции с типами или проверять наличие поддержки типами тех или иных операций. Данный набор размещён в стандартном заголовочном файле type_traits. Почему-то в этот набор предопределённых метафункций не попала функция, позволяющая определить, возможно ли вызвать объект некоторого типа (указатель на функцию, ссылку на функцию или функтор) для заданного набора параметров. То есть, проверить поддержку им заданной сигнатуры. Впрочем, такую метафункцию (я назвал её «is_callable») в рамках C++11 реализовать довольно легко.

Основной элемент C++, позволяющий проверять доступность той или иной операции, называется SFINAE — «substitution failure is not an error» — ошибка при подстановке параметров шаблона в шаблоне функции не считается ошибкой компиляции, а просто исключает данный вариант из рассмотрения при вызове перегруженной функции. Классическим примером использования SFINAE является стандартный шаблон enable_if (также взятый из Boost), позволяющий «включать» или «выключать» определения функций в зависимости от выполнения условий времени компиляции.

С появлением ключевого слова decltype, позволяющего «извлечь» тип выражения, появился новый паттерн, задействующий SFINAE в духе enable_if:

template <class T>
decltype((void)(Expr(T)), RetExpr()) foo(T);

Данный вариант функции пропадёт из рассмотрения при вызове, если выражение Expr(T) нельзя скомпилировать для данного типа T. В противном случае, возвращаемый тип функции будет совпадать с типом значения выражения RetExpr(). Приведение к void позволяет гарантировать «нормальное» поведение оператора «запятая» (а то вдруг он перегружен).

Такую конструкцию обычно лучше оформлять с «хвостовым» определением возвращаемого типа. Заодно можно будет воспользоваться именами параметров функции в выражении внутри decltype.

template <class T>
auto foo(T t) ->
    decltype((void)(Expr(t)), RetExpr());

В общем-то, данный приём составляет основу определения метафункции is_callable, для представления которого я написал данный пост. Оно довольно простое.

#include <type_traits>
#include <utility>

template <class F>
struct Try_to_call
{
  template <class... Args>
  static std::false_type can_call(Args&&...);

  template <class... Args>
  static auto can_call(F& f, Args&&... args)
    -> decltype((void)f(std::forward<Args>(args)...),
                std::true_type{});
};

template <class F, class... Args>
using is_callable = decltype
  (
    Try_to_call<F>::can_call(*(F*)nullptr,
          std::forward<Args>(*(Args*)nullptr)...)
  );

Как правило, определяют функцию, дающую вариант «по умолчанию» и для того имеющую максимально обобщённый вид. Здесь это вариант can_call, возвращающий false_type, принимающий любой набор параметров. Вообще любой.

Также можно задействовать примитивные типы с неявным приведением. Например, «вариант по умолчанию» принимает дополнительный параметр типа unsigned, а «желаемый вариант» — параметр типа int. Тогда при передаче, например, числа 1, int — предпочтительнее при выборе перегруженного варианта, однако unsigned тоже сойдёт, так как определено неявное приведение типа int -> unsigned.

Теперь пример использования. При запуске должно вывести 1110. Проверено в MSVC2013 и gcc 4.9.2.

#include <iostream>

int main()
{
  using namespace std;
  auto sqr = [](double x) { return x * x; };
  cout << is_callable<decltype(sqr), int>::value
       << is_callable<int (*)(int), double>::value
       << is_callable<int (*)(int), int>::value
       << is_callable<int (*)(int), double, double>::value
       << endl;
  return 0;
}

Оператор [] для multimap

Наверное, не только у меня бывали моменты, когда отсутствие в std::multimap возможности оперировать блоками значений, отвечающих одному ключу, хотя бы в духе совместимости с std::map раздражало и казалось странным. В C++11 добавили хэш-таблицы, включая std::unordered_multimap — аналог std::multimap (сбалансированного дерева двоичного поиска), но расширение интерфейса в сторону работы с диапазонами не последовало. К сожалению, пример boost.range и языка D (см. также ссылки здесь) пока не находят отклика в Стандартной библиотеке C++.

Несколько месяцев назад я написал расширение, добавляющее оператор [] и аналогичную функцию at() в произвольный класс, совместимый с std::multimap или std::unordered_multimap. Подмешивание функционала происходит с помощью наследования от базового контейнера, переданного параметром шаблона. Традиционно принято считать, что наследовать от стандартных контейнеров — плохо, так как они изначально для этого не предназначены (невиртуальные деструкторы). В данном случае этим стереотипом можно пренебречь, так как класс-наследник не добавляет никакого состояния к объекту базового класса и никак не влияет на его жизненный цикл. Добавляемая функциональность могла бы быть реализована внешними методами, если бы они были в C++ (есть в D).

Оператор [] возвращает прокси-объект «диапазон» MapRangeView, для которого определён ряд операций (например, присваивание, begin/end), позволяющие оперировать группой элементов multimap как контейнером с минимальным функционалом (например, обходить их с помощью for(:)). Впрочем, данный класс предоставляет также ряд высокоуровневых функций (синтаксический сахар). Но есть и свои мелкие неприятности:

map1["key1"] = map2["key2"]; // копирование прокси-объекта
// содержимое map1 и map2 не поменялось

Я решил не нагружать базовый оператор присваивания подменой содержимого контейнера. Вместо этого добавлен ещё один очень простой прокси-класс BasicRange, в который оборачивается наш диапазон, если требуется скопировать или переместить его элементы (для перемещения используется std::move_iterator).

map1["key1"] = map2["key2"].copying(); // копирование элементов
map1["key3"] = map2["key4"].moving();  // перемещение элементов
map2["key4"].erase(); // удаление того, что осталось после перемещения

У получившегося кода есть свои недостатки, но, что более важно, я пока не пользовался им всерьёз и не могу сказать, что уверен в отсутствии опасных ошибок. Исходники: определение классов диапазонов, контейнер-обёртка multimap, простенькие тесты.

C++: список типов

Данный пост посвящён созданию списков типов в C++11 и работе с ними.
Список — это линейная рекурсивная структура данных. Условно её можно представить как

type List = Nil | (type, List)

Здесь Nil — вспомогательный тип, означающий пустой список (или конец списка).

// выбор первой части пары
head x = x
head (h, t) = h

// выбор второй части пары
tail x = Nil
tail (h, t) = t

Теперь на C++.

struct Nil {};

template <class H, class T = Nil>
struct Cons {};

template <class L>
struct Head { using type = L; };

template <class H, class T>
struct Head<Cons<H, T>> { using type = H; };

template <class L>
struct Tail { using type = Nil; };

template <class H, class T>
struct Tail<Cons<H, T>> { using type = T; };

Cons (сокращение от construct) позволяет собирать пару типов в новый тип. Фактически, например, список [char, short, int, long] записывается как Cons<char, Cons<short, Cons<int, Cons<long, Nil>>>>. Это не слишком удобно. Добавим вспомогательные определения, позволяющие сократить запись.

// *T -- синоним выборки зависимого имени type
template <class L>
using HeadT = typename Head<L>::type;

template <class L>
using TailT = typename Tail<L>::type;

template <class... Types>
struct List {};

template <>
struct List<> { using type = Nil; };

template <class H, class... T>
struct List<H, T...> 
{ using type = Cons<H, typename List<T...>::type>; };

template <class... Types>
using ListT = typename List<Types...>::type;

Теперь тот же список типов, что был приведён выше, можно записать как ListT<char, short, int, long>.
Обработка списка распадается на обращение к голове и рекурсивную обработку хвоста. Напишем функцию, выводящую в консоль названия типов, зафиксированных в списке (я воспользуюсь частичной специализацией шаблонов функций, появившейся в C++11).

template <class List>
void print_typelist()
{
  std::cout << typeid(HeadT<List>).name() << ' ';
  print_typelist<TailT<List>>();
}

template <>
void print_typelist<Nil>() {}

Предположим, что есть метафункция f : type -> type и требуется получить список результатов применения данной функции к исходному списку (операция map). Как это реализовать?

map f Nil = Nil
map f (h, t) = (f h, map f t)

Чтобы оформить это на C++, необходимо решить, на какой вариант представления метафункций при этом ориентироваться. В данном случае, я выбрал вариант 2 как основной, применяемый Стандартной библиотекой.

template <template <class A> class F, class L>
struct Map
{ using type = typename F<L>::type; };

template <template <class A> class F, class H, class T>
struct Map<F, Cons<H, T>>
{
  using type = Cons<typename F<H>::type,
                    typename Map<F, T>::type>;
};

template <template <class A> class F>
struct Map<F, Nil> { using type = Nil; };

Предположим, есть метафункция b(x, y), принимающая два параметра. Тогда можно поставить задачу о свёртке списка, т.е. вычисления выражения вида b(start, b(item1, b(item2, …, b(itemN-1, itemN)…))). В функциональных языках функцию, позволяющую выполнить такую свёртку списка для произвольных функции b и начального значения start, обычно называют foldr (правоассоциативная свёртка). Я буду использовать следующее определение на C++.

template <
  template <class A, class B> class F,
  class S, class L>
struct Fold
{
  using type = S;
  static const auto value = type::value;
};

template <
  template <class A, class B> class F,
  class S, class H, class T>
struct Fold<F, S, Cons<H, T>>
{
  using type = typename
    F<S, typename Fold<F, H, T>::type>::type;
  static const auto value = type::value;
};

Воспользуемся Fold для определения операций проверки выполнения некоторого предиката на каком-либо или на всех элементах списка.

template <bool B>
using Bool = std::integral_constant<bool, B>;

using False = Bool<false>;
using True = Bool<true>;

template <class A, class B>
struct Or: Bool<A::value || B::value> {};

template <class A, class B>
struct And: Bool<A::value && B::value> {};

template <class L>
using ExistsTrue = typename Fold<Or, False, L>::type;

template <class L>
using AllTrue = typename Fold<And, True, L>::type;

Например, мы хотим проверить, принадлежит ли некоторый тип заданному списку. Определим для этого метафункцию Belongs тип список:

template <
  template <class A, class B> class F,
  class A>  // карринг
struct Bind
{
  template <class B>
  using apply = typename F<A, B>::type;
};

template <class T, class L>
struct Belongs
  : ExistsTrue<typename 
      Map<Bind<std::is_same, T>::template apply, L>::type> {};

На данной основе не сложно определить и другие операции, обычно определяемые для списков (например, вычисление длины).

Исходный код

C++: возможная замена стандартным min & max

Стандартный заголовок algorithm предоставляет определения min, max и minmax (возвращает std::pair). Итак, как выглядит объявление, например, базового варианта std::max?

template <class T>
const T& max(const T& a, const T& b);

Недостатки этого объявления:

  • одинаковый тип a и b — наиболее раздражающий недостаток. Например, что-нибудь безобидное вроде max(vec.size(), 100) уже не компилируется, потому что 100 имеет тип int, а не size_t;
  • только два параметра, поэтому max(a, b, c) придётся оформить как max(a, max(b, c));
  • передача по const-ссылке:
    • для переменных a и b невозможно написать max(a, b) = c;
    • невозможна перемещающая семантика для rvalue: auto v = max(compute_vector1(), compute_vector2()) — всегда копирование;
    • иногда возникает проблема с порождением оптимального кода для значений простых типов.

Что до недостатка 2, то C++2011 предоставляет новые варианты, принимающие initializer_list:

template <class T>
T max(std::initializer_list<T> ilist);

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

Рассмотрим недостаток 1. Простое определение для двух разных типов вызывает затруднение в месте описания возвращаемого типа. C++2014 мог бы позволить написать просто

template <class U, class V> inline
auto max(U u, V v)
{ return u < v? v: u; }

В C++2011 придётся прибегнуть к decltype:

template <class U, class V> inline
auto max(U u, V v)
  -> decltype(u < v? v: u)
{ return u < v? v: u; }

или воспользоваться метафункцией std::common_type из type_traits (также доступна в варианте Boost для ряда старых компиляторов):

template <class U, class V> inline
typename std::common_type<U, V>::type
max(U u, V v)
{ return u < v? v: u; }

Попробуем обобщить данный код, используя универсальные ссылки (std::forward из memory):

template <class U, class V> inline
typename std::common_type<U, V>::type
max(U &&u, V &&v)
{
  return u < v? std::forward<V>(v): std::forward<U>(u);
}

К сожалению, код

int a = 1, b = 2;
max(a, b) = 3;

не компилируется, потому что common_type убирает ссылки (возвращаемый тип данного варианта max будет int, а не int&). Вероятно, простейший вариант исправить этот недостаток — реализовать объединение типов с помощью оператора ?: (сохраняющего ссылочные типы).

template <class U, class V> inline
auto max(U &&u, V &&v)
  -> decltype(u < v? std::forward<V>(v): std::forward<U>(u))
{
  return u < v? std::forward<V>(v): std::forward<U>(u);
}

Обобщим это определение на произвольное число параметров.

template <class U, class V, class ...Tail> inline
auto max(U &&u, V &&v, Tail&&... tail)
  -> decltype(max(std::forward<U>(u),
       max(std::forward<V>(v), std::forward<Tail>(tail)...)))
{
  return max(std::forward<U>(u),
         max(std::forward<V>(v), std::forward<Tail>(tail)...));
}

К сожалению, этот код не компилируется (при попытке вычислить max(1, 2, 3, 4), например) компилятором g++ (хотя компилируется msvc2013). Проблема в рекурсивной зависимости вывода типа — при вычислении max от 4 аргументов вариант для 3-х ещё не сгенерирован. Поэтому желательно отделить вычисление возвращаемого типа в метафункцию.

При использовании имён max/min вместе с объектами стандартных классов возможна «кража функций» (function hijacking) механизмом ADL (а то и срабатывание макросов max и min), поэтому я буду использовать (пусть и непривычные) имена maxi и mini, заведомо не конфликтующие со стандартными определениями. Итак, на примере минимума:

template <class...>
struct commonref_type {};

template <class U>
struct commonref_type<U>
{
  using type = U;
};

template <class U, class V>
struct commonref_type<U, V>
{
private:
  static U make_u();
  static V make_v();
  static bool dummy_condition();

public:
  using type = decltype(dummy_condition()? make_u() : make_v());
};

template <class U, class Head, class ...Tail>
struct commonref_type<U, Head, Tail...>
{
  using type = typename
    commonref_type<U, typename
    commonref_type<Head, Tail...>::type>::type;
};


template <class U, class V> inline
typename commonref_type<U, V>::type
mini(U &&u, V &&v)
{
  return v < u? std::forward<V>(v) : std::forward<U>(u);
}

template <class U, class V, class ...Tail> inline
typename commonref_type<U, V, Tail...>::type
mini(U &&u, V &&v, Tail&&... tail)
{
  return mini(std::forward<U>(u),
         mini(std::forward<V>(v), std::forward<Tail>(tail)...));
}

Формат, позволяющий передать произвольное количество разнотипных параметров, закрывает возможность с помощью механизма перегрузки функций добавить варианты, принимающие произвольный компаратор (такие есть у стандартных min и max). Но ничто не мешает дать другие имена, например, minc и maxc (от comparator). В отличие от стандартных вариантов, здесь будем передавать компаратор первым параметром.

template <class Comp, class U, class V> inline
typename commonref_type<U, V>::type
minc(Comp &&comp, U &&u, V &&v)
{
  return comp(v, u)? std::forward<V>(v) : std::forward<U>(u);
}

template <class Comp, class U, class V, class ...Tail> inline
typename commonref_type<U, V, Tail...>::type
minc(Comp &&comp, U &&u, V &&v, Tail&&... tail)
{
  return minc(comp, std::forward<U>(u),
         minc(comp, std::forward<V>(v), std::forward<Tail>(tail)...));
}

Последнее, с чем осталось разобраться — реализация «одновременного» поиска минимума и максимума. Следуя стандартному определению, будем возвращать пару (результат min, результат max) [std::tuple].

template <class ...Types>
struct minmax_result
{
  using part = typename commonref_type<Types...>::type;
  using type = std::tuple<part, part>;
};

Корректная реализация функций одновременного выбора минимума и максимума требует большого внимания к деталям. Моя версия:

template <class U, class V> inline
typename minmax_result<U, V>::type
minmaxi(U &&u, V &&v)
{
  using RT = typename minmax_result<U, V>::type;
  return v < u?
    RT(std::forward<V>(v), std::forward<U>(u))
  : RT(std::forward<U>(u), std::forward<V>(v));
}

template <class U, class V, class ...Tail> inline
typename minmax_result<U, V, Tail...>::type
minmaxi(U &&u, V &&v, Tail&&... tail)
{
  using RT = typename minmax_result<U, V, Tail...>::type;
  using R = typename commonref_type<V, Tail...>::type;
  auto tail_result =
    minmaxi(std::forward<V>(v), std::forward<Tail>(tail)...);
  auto &p0 = std::get<0>(tail_result),
       &p1 = std::get<1>(tail_result);
  return u < p1?
        (p0 < u?
             RT(std::forward<R>(p0), std::forward<R>(p1))
           : RT(std::forward<U>(u),  std::forward<R>(p1)))
           : RT(std::forward<R>(p0), std::forward<U>(u));
}

Текущий вариант реализации целиком.

Метафункции C++

Общее определение: функции, вычисляемые во время компиляции, в том числе, позволяющие вычислять типы.

Механизм шаблонов C++ является чистым функциональным языком (с громоздким синтаксисом), выражения на котором вычисляются во время компиляции, поэтому основной метод реализации метафункций опирается на механизм шаблонов и (частичной) специализации. В C++2011 появился второй метод: на основе constexpr, здесь он не рассматривается.

Я буду выписывать «определения» в псевдокоде, напоминающем Haskell, а затем приводить аналог на C++.

Связывание имени с константой

let x = y
// x -- новое имя для значения y
// применительно к типам в C++
// C++1998
typedef y x;

// C++2011
using x = y;
Вариант 1

Пусть f принимает тип и возвращает тип.

Определение

f :: type -> type
f x = ...
template <class x> class f { ... };

Применение

f x  // или
f(x) // или
(f x)
f<x> // C++

Функции высших порядков

f :: (type -> type) -> type
f x = ...
template <template <class> x> class f { ... };

Достоинство: краткость синтаксиса применения.

Недостатки:

  • нельзя сопоставить уже существующие типы (например, нельзя выразить определение f int = float);
  • неудобно использовать функции высших порядков.
Вариант 2

Прообраз введён стандартной библиотекой C++, использующей зависимые имена в шаблонах (например, в std::unary_function, классах характеристик std::char_traits, std::iterator_traits, контейнерах).
Популяризован библиотеками Boost.MPL, Boost.TypeTraits (последняя вошла в стандарт C++2011).

Определение

f :: type -> type
f x = expr
template <class x> struct f
{
  typedef expr type;
};

Применение

f x // f(x)
typename f<x>::type // C++

Достоинства:

  • можно привязать любой тип;
  • можно задать мультифункцию (несколько зависимых имён);
  • можно вычислять не только типы, но и значения (традиционно используется вложенное имя value):
factorial :: unsigned -> unsigned
factorial n = n * factorial (n - 1)
factorial 0 = 1
template <unsigned n> struct factorial
{
  enum { value = n * factorial<n - 1>::value };
};

template <> struct factorial<0> { enum { value = 1u }; };

Другой классический пример такого рода: числа Фибоначчи.

  • можно задавать через наследование (используется std::conditional из type_traits):
uint :: unsigned -> type
uint bits = if bits < 9  then uint8_t  else
            if bits < 17 then uint16_t else
            if bits < 33 then uint32_t else
            uint64_t ;
template <unsigned bits> struct uint
  : conditional<(bits < 9),  uint8_t,  typename
    conditional<(bits < 17), uint16_t, typename
    conditional<(bits < 33), uint32_t,
    uint64_t >::type>::type> {};

Недостатки:

  • длинный синтаксис применения (причём typename требуется в контексте определения шаблона при использовании имён, зависящих от параметров шаблона, но запрещено в противном случае);
  • неудобно передавать в функции высшего порядка.

Замечание
С++2011 позволяет сократить синтаксис применения с помощью template-using объявления:

template <unsigned bits> using uint_t = typename uint<bits>::type;
uint_t<19> counter; // OK

Данный подход применяется в type_traits C++2014.

Замыкания и карринг

mul a b = a * b
mul5 = mul 5
thirty = mul5 6

Карринг в C++ напрямую не поддерживается. Его можно имитировать, разделив параметры шаблона.

template <int a>
struct mul
{
  template <int b>
  struct curried { enum { value = a * b }; };
};

using mul5 = mul<5>;
const auto thirty = mul5::curried<6>::value;

Обработка списков (C++2011 variadic templates)

len :: [type] -> int
len x:xs = 1 + len xs
len [] = 0
template <class ...xs>
struct len {};

template <class x, class ...xs>
struct len<x, xs...> { enum { value = 1 + len<xs...>::value }; };

template <>
struct len<> { enum { value = 0 }; };

Использование одновременно значений и типов в качестве параметров может быть затруднено отсутствием перегрузки метафункций. Поэтому для целочисленных типов в type_traits введена обёртка integral_constant (увы, писать выражения с помощью обычных арифметических и логических операций становится невозможно). Определим factorial на её основе (вариант с «хвостовой» рекурсией).

factorial n f = factorial (n - 1) (n * f)
factorial 0 f = f
template <uint64_t n>
using Uint = integral_constant<uint64_t, n>;

using Zero = Uint<0>;
using One = Uint<1>;

template <class N, class M>
struct Sub
  : Uint<N::value - M::value> {};

template <class N, class M>
struct Mul
  : Uint<N::value * M::value> {};

template <class N, class F = One>
struct factorial
  : factorial<Sub<N, One>, Mul<F, N>> {};

template <class F>
struct factorial<Zero, F>
  : F {};

Увы, приведённый код не компилируется. Дело в том, что подстановка шаблонов выполняется немедленно, ленивые вычисления для типов не используются, поэтому компилятор не способен «дойти» до template < class F > struct factorial. Следующий вариант также не будет компилироваться:

template <class N, class F = One>
struct factorial
{
  using base = factorial<Sub<N, One>, Mul<F, N>>;
  using type = typename base::type;
  enum { value = base::value };
};

Впрочем, обойти эту проблему можно, сразу включив условие в определение:

template <class N, class F = One>
struct factorial
  : conditional<N::value != 0,
      factorial<Sub<N, One>, Mul<N, F>>,
      F>::type {};
Вариант 3

Отделение имени от параметров шаблона с помощью вложенных определений. Первый известный мне подобный пример — стандартные аллокаторы C++1998 (rebind). Также применяется в Boost.MPL.

Определение

f x = expr
struct f
{
  template <class T> struct apply { typedef expr type };
};

Применение

f x
typename f::template apply<x>::type

Достоинства:

  • все из варианта 2;
  • удобно передавать в функции высшего порядка (универсальность: достаточно оперировать именами метафункций, являющимися обычными типами, а не шаблонами), в частности, такую метафункцию можно передать саму себе в качестве параметра;

Недостаток: ещё более длинный синтаксис применения (для прямого применения возможно сокращение с помощью template-using, что, впрочем, не спасает при описании выражений внутри метафункций).

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

Вычисление чисел Фибоначчи во время компиляции

Не думаю, что кого-нибудь из программистов на C/C++, кроме, может быть, самых начинающих, затруднит написать функцию, вычисляющую по заданному целому числу n число Фибоначчи с номером n, используя O(n) цикл вместо O(n^2) рекурсии (получаемой переписыванием определения числа Фибоначчи на языке программирования).

В данный момент моя цель состоит не в демонстрации эффективного вычисления чисел Фибоначчи (их можно считать по аналитической формуле, кроме того, есть коллекция реализаций), а в демонстрации реализации линейного алгоритма на шаблонах C++ (похожий пример на Scheme).

Надеюсь, мой пример будет полезен изучающим обобщённое программирование на C++. Итак, заставим компилятор вычислить числа Фибоначчи «по определению».

// Fibonacci numbers via templates by definition

template <unsigned N> struct Fib
{
  static const unsigned value =
    Fib<N - 1>::value + Fib<N - 2>::value;
};

template <> struct Fib <0>
{
  static const unsigned value = 0;
};

template <> struct Fib <1>
{
  static const unsigned value = 1;
};

Теперь, например, Fib<10>::value == 55, что и требовалось. Естественно, параметр шаблона должен быть известен на момент компиляции. Линейный алгоритм использует предыдущее число, поэтому введём дополнительную константу prev. Далее, мы можем избавиться от упоминания Fib<N-2>, сохранив только Fib<N-1>.

// linear calculation of n-th Fibonacci number on templates
template <unsigned N>
struct Fib: protected Fib<N - 1>
{
protected:
  static const unsigned prev = 
    Fib<N - 1>::value;
public:
  static const unsigned value = 
    Fib<N - 1>::prev + prev;  
};

template <> struct Fib <0>
{
protected:
  static const unsigned prev = 0;
public:
  static const unsigned value = 0;
};

template <> struct Fib <1>
{
protected:
  static const unsigned prev = 0;
public:
  static const unsigned value = 1;
};

Замечание 1. Использовать protected, конечно, необязательно (тем более в таком простом случае), это было сделано в целях разделения «интерфейса» (value) и «реализации».

Замечание 2. На самом деле первый вариант квадратичным не является, т.к. инстанцирование (подстановка формальных параметров шаблона) Fib<N> для разных N происходит только однажды. Например, вычислим Fib<6>::value.

Fib<6>::value = Fib<5>::value + Fib<4>::value
Fib<5>::value = Fib<4>::value + Fib<3>::value
Fib<4>::value = Fib<3>::value + Fib<2>::value
Fib<3>::value = Fib<2>::value + 1 // Fib<1>::value
Fib<2>::value = 1 + 0 // Fib<0>::value
=> Fib<2>::value = 1
=> Fib<3>::value = 2
=> Fib<4>::value = 3
=> Fib<5>::value = 5
=> Fib<6>::value = 8

Аналогичный (однократному инстанцированию) приём можно использовать в run-time вычислениях (w:memoization, пример на C++11).