C++
Метапрограммирование

Вступление

замечания

Вычисление факториалов

Факториалы могут быть вычислены во время компиляции с использованием методов метапрограммирования шаблонов.

#include <iostream>

template<unsigned int n>
struct factorial
{
    enum
    {
        value = n * factorial<n - 1>::value
    };
};

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

int main()
{
    std::cout << factorial<7>::value << std::endl;    // prints "5040"
}

factorial - это структура, но в метапрограммировании шаблона он рассматривается как шаблонный метафунг. По соглашению метафайлы шаблонов оцениваются путем проверки определенного члена: ::type для метафайлов, которые приводят к типам, или ::value для метафайлов, которые генерируют значения.

В приведенном выше коде мы оцениваем factorial метафункт, создавая экземпляр шаблона с параметрами, которые мы хотим передать, и используя ::value чтобы получить результат оценки.

Сама метафония полагается на рекурсивно создающую тот же метафунгмент с меньшими значениями. factorial<0> представляет собой конечное условие. Метапрограммирование шаблонов имеет большинство ограничений функционального языка программирования , поэтому рекурсия является основной конструкцией «looping».

Поскольку метафайлы шаблонов выполняются во время компиляции, их результаты могут использоваться в контекстах, требующих значений времени компиляции. Например:

int my_array[factorial<5>::value];

Автоматические массивы должны иметь определенный размер времени компиляции. И результат metafunction - константа времени компиляции, поэтому ее можно использовать здесь.

Ограничение . Большинство компиляторов не позволят глубже рекурсии выйти за пределы. Например, компилятор g++ по умолчанию рекурсия ограничивает 256 уровней. В случае g++ программист может установить глубину рекурсии с помощью параметра -ftemplate-depth-X .

#include <iostream>
#include <type_traits>

template<long long n>
struct factorial :
  std::integral_constant<long long, n * factorial<n - 1>::value> {};

template<>
struct factorial<0> :
  std::integral_constant<long long, 1> {};

int main()
{
    std::cout << factorial<7>::value << std::endl;    // prints "5040"
}

#include <iostream>

constexpr long long factorial(long long n)
{
  return (n == 0) ? 1 : n * factorial(n - 1);
}

int main()
{
  char test[factorial(3)];
  std::cout << factorial(7) << '\n';
}

constexpr long long factorial(long long n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

constexpr long long factorial(int n)
{
  long long result = 1;
  for (int i = 1; i <= n; ++i) {
    result *= i;
  }
  return result;
}

#include <iostream>
#include <utility>

template <class T, T N, class I = std::make_integer_sequence<T, N>>
struct factorial;

template <class T, T N, T... Is>
struct factorial<T,N,std::index_sequence<T, Is...>> {
   static constexpr T value = (static_cast<T>(1) * ... * (Is + 1));
};

int main() {
   std::cout << factorial<int, 5>::value << std::endl;
}

Итерация по пакету параметров

Часто нам нужно выполнить операцию над каждым элементом в пакете параметров вариационного шаблона. Есть много способов сделать это, и решения легче читать и писать с C ++ 17. Предположим, мы просто хотим напечатать каждый элемент в пакете. Самое простое решение - рекурсия:

void print_all(std::ostream& os) {
    // base case
}

template <class T, class... Ts>
void print_all(std::ostream& os, T const& first, Ts const&... rest) {
    os << first;
    
    print_all(os, rest...);
}

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

template <class... Ts>
void print_all(std::ostream& os, Ts const&... args) {
    using expander = int[];
    (void)expander{0,
        (void(os << args), 0)...
    };
}

Для объяснения того, как это работает, см . Отличный ответ TC .

template <class... Ts>
void print_all(std::ostream& os, Ts const&... args) {
    ((os << args), ...);
}

template <class T, class... Ts>
void print_all(std::ostream& os, T const& first, Ts const&... rest) {
    os << first;

    if constexpr (sizeof...(rest) > 0) {        
        // this line will only be instantiated if there are further
        // arguments. if rest... is empty, there will be no call to
        // print_all(os). 
        print_all(os, rest...);
    }
}

Итерация с помощью std :: integer_sequence

Поскольку C ++ 14, стандарт предоставляет шаблон класса

template <class T, T... Ints>
class integer_sequence;

template <std::size_t... Ints>
using index_sequence = std::integer_sequence<std::size_t, Ints...>;

и генерирующий метафунд для него:

template <class T, T N>
using make_integer_sequence = std::integer_sequence<T, /* a sequence 0, 1, 2, ..., N-1 */ >;

template<std::size_t N>
using make_index_sequence = make_integer_sequence<std::size_t, N>;

Хотя это стандартно в C ++ 14, это можно реализовать с помощью инструментов C ++ 11.

Мы можем использовать этот инструмент для вызова функции с помощью std::tuple аргументов (стандартизован в C ++ 17 как std::apply ):

namespace detail {
    template <class F, class Tuple, std::size_t... Is>
    decltype(auto) apply_impl(F&& f, Tuple&& tpl, std::index_sequence<Is...> ) {
        return std::forward<F>(f)(std::get<Is>(std::forward<Tuple>(tpl))...);
    }
}

template <class F, class Tuple>
decltype(auto) apply(F&& f, Tuple&& tpl) {
    return detail::apply_impl(std::forward<F>(f),
        std::forward<Tuple>(tpl),
        std::make_index_sequence<std::tuple_size<std::decay_t<Tuple>>::value>{});
}


// this will print 3
int f(int, char, double);

auto some_args = std::make_tuple(42, 'x', 3.14);
int r = apply(f, some_args); // calls f(42, 'x', 3.14)

Отправка тегов

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

namespace details {
    template <class RAIter, class Distance>
    void advance(RAIter& it, Distance n, std::random_access_iterator_tag) {
        it += n;
    }

    template <class BidirIter, class Distance>
    void advance(BidirIter& it, Distance n, std::bidirectional_iterator_tag) {
        if (n > 0) {
            while (n--) ++it;
        }
        else {
            while (n++) --it;
        }
    }

    template <class InputIter, class Distance>
    void advance(InputIter& it, Distance n, std::input_iterator_tag) {
        while (n--) {
            ++it;
        }
    }    
}

template <class Iter, class Distance>
void advance(Iter& it, Distance n) {
    details::advance(it, n, 
            typename std::iterator_traits<Iter>::iterator_category{} );
}

Параметры std::XY_iterator_tag перегруженных details::advance - неиспользуемые параметры функции. Фактическая реализация не имеет значения (на самом деле она полностью пуста). Их единственная цель - разрешить компилятору выбирать перегрузку, на основе которой вызывается класс класса details::advance .

В этом примере advance использует iterator_traits<T>::iterator_category который возвращает один из классов iterator_tag , в зависимости от реального типа Iter . Построенный по умолчанию объект типа iterator_category<Iter>::type затем позволяет компилятору выбрать одну из разных перегрузок details::advance . (Этот параметр функции, скорее всего, будет полностью оптимизирован, так как это построенный по умолчанию объект пустой struct и никогда не используется).

Отправка тегов может дать вам код, который намного легче читать, чем эквиваленты, используя SFINAE и enable_if .

Примечание: в то время как C ++ 17, if constexpr может упростить реализацию advance в частности, он не подходит для открытых реализаций, в отличие от диспетчеризации тегов.

Определить, действительно ли выражение

Можно определить, можно ли вызвать оператор или функцию для типа. Чтобы проверить, имеет ли класс перегрузку std::hash , можно сделать следующее:

#include <functional> // for std::hash
#include <type_traits> // for std::false_type and std::true_type
#include <utility> // for std::declval

template<class, class = void>
struct has_hash
    : std::false_type
{};

template<class T>
struct has_hash<T, decltype(std::hash<T>()(std::declval<T>()), void())>
    : std::true_type
{};

#include <functional> // for std::hash
#include <type_traits> // for std::false_type, std::true_type, std::void_t
#include <utility> // for std::declval

template<class, class = std::void_t<> >
struct has_hash
    : std::false_type
{};

template<class T>
struct has_hash<T, std::void_t< decltype(std::hash<T>()(std::declval<T>())) > >
    : std::true_type
{};

template< class... > using void_t = void;

Для определения того, является ли оператор, например operator< , синтаксисом, почти то же самое:

template<class, class = void>
struct has_less_than
    : std::false_type
{};

template<class T>
struct has_less_than<T, decltype(std::declval<T>() < std::declval<T>(), void())>
    : std::true_type
{};

Они могут использоваться для использования std::unordered_map<T> если T имеет перегрузку для std::hash , но в противном случае попытается использовать std::map<T> :

template <class K, class V>
using hash_invariant_map = std::conditional_t<
    has_hash<K>::value,
    std::unordered_map<K, V>,
    std::map<K,V>>;    

Вычисление мощности с C ++ 11 (и выше)

С C ++ 11 и выше вычисления во время компиляции могут быть намного проще. Например, вычисление мощности заданного числа во время компиляции будет следующим:

template <typename T>
constexpr T calculatePower(T value, unsigned power) {
    return power == 0 ? 1 : value * calculatePower(value, power-1);
}

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

Примечание. В C ++ 11 функция constexpr должна составлять только один оператор return.

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

Например

void useExample() {
    constexpr int compileTimeCalculated = calculatePower(3, 3); // computes at compile time,
                               // as both arguments are known at compilation time
                               // and used for a constant expression.
    int value;
    std::cin >> value;
    int runtimeCalculated = calculatePower(value, 3);  // runtime calculated,
                                    // because value is known only at runtime.
}

#include <iostream>
#include <utility>

template <class T, T V, T N, class I = std::make_integer_sequence<T, N>>
struct power;

template <class T, T V, T N, T... Is>
struct power<T, V, N, std::integer_sequence<T, Is...>> {
   static constexpr T value = (static_cast<T>(1) * ... * (V * static_cast<bool>(Is + 1)));
};

int main() {
   std::cout << power<int, 4, 2>::value << std::endl;
}

Ручное различие типов при задании любого типа T

При реализации SFINAE с использованием std::enable_if часто бывает полезно иметь доступ к вспомогательным шаблонам, который определяет, соответствует ли данный тип T набору критериев.

Чтобы помочь нам в этом, стандарт уже предоставляет два типа аналоговых std::true_type true и false которые являются std::true_type и std::false_type .

В следующем примере показано, как определить, является ли тип T указателем или нет, шаблон is_pointer имитирует поведение стандартного помощника std::is_pointer :

template <typename T>
struct is_pointer_: std::false_type {};

template <typename T>
struct is_pointer_<T*>: std::true_type {};

template <typename T>
struct is_pointer: is_pointer_<typename std::remove_cv<T>::type> { }

В приведенном выше коде есть три шага (иногда вам нужно только два):

1. Первое объявление is_pointer_ является случаем по умолчанию и наследуется от std::false_type . Случай по умолчанию должен всегда наследоваться от std::false_type поскольку он аналогичен « false состоянию».

2. Второе объявление специализируется на шаблоне is_pointer_ для указателя T* не заботясь о том, что такое T Эта версия наследуется от std::true_type .

3. Третья декларация (реальная) просто удаляет ненужную информацию из T (в этом случае мы удаляем const и volatile квалификаторы), а затем отступаем к одной из двух предыдущих деклараций.

Поскольку is_pointer<T> является классом, для доступа к его значению необходимо:

• Use ::value , например is_pointer<int>::value - value - статический член класса типа bool унаследованный от std::true_type или std::false_type ;
• Построить объект этого типа, например is_pointer<int>{} - Это работает, потому что std::is_pointer наследует свой конструктор по умолчанию из std::true_type или std::false_type (которые имеют конструкторы constexpr ) и оба std::true_type и std::false_type имеют constexpr преобразования constexpr для bool .

Это хорошая привычка предоставлять «вспомогательные шаблоны помощников», которые позволяют вам напрямую получать доступ к значению:

template <typename T>
constexpr bool is_pointer_v = is_pointer<T>::value;

template< class T > constexpr bool is_pointer_v = is_pointer<T>::value;
template< class T > constexpr bool is_reference_v = is_reference<T>::value;

Если-то-иначе

template<typename T>
struct ValueOrPointer
{
    typename std::conditional<(sizeof(T) > sizeof(void*)), T*, T>::type vop;
};

Generic Min / Max с переменным аргументом count

template <typename T1, typename T2>
auto min(const T1 &a, const T2 &b) 
-> typename std::common_type<const T1&, const T2&>::type
{
    return a < b ? a : b;
}

template <typename T1, typename T2, typename ... Args>
auto min(const T1 &a, const T2 &b, const Args& ... args)
-> typename std::common_type<const T1&, const T2&, const Args& ...>::type
{
    return min(min(a, b), args...);
}

auto minimum = min(4, 5.8f, 3, 1.8, 3, 1.1, 9);