Monthly Archives: Май 2014

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));
}

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