Tag Archives: C++14

Вычисление чисел Фибоначчи во время компиляции С++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;
Реклама

Conar 5: структура данных Parser

Начало

Предыдущая часть

Займёмся классом Parser.

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

Обработчик будем приводить к типу Handler, объявленному следующим образом:

using Parameters = std::vector<std::string>;
using PIt = Parameters::iterator;
using Handler = std::function<PIt(PIt, PIt)>;

Теперь определим собственно структуры данных, содержащиеся в объекте Parser. Mapper отображает ключи в индексы вектора Options.

using Option = std::tuple<Handler, Option_info>;
using Options = std::vector<Option>;
using Mapper = std::map<std::string, std::size_t>;
Options options;
Mapper mapper;

Напишем код, добавляющий опцию (тройку «обработчик, ключи, инфо«).

/// Add an option description.
/// Use functions flag, value and seq to make an option.
template <class Opt>
Parser& operator()(Opt option)
{
  using namespace std;
  static_assert(tuple_size<Opt>::value == 3);

  // Add the option to options.
  const auto index = options.size();
  options.emplace_back(move(get<0>(option)),
                       move(get<2>(option)));

  // Register keys of the option.
  for (auto &key: get<1>(option))
    mapper.emplace(key_prep(move(key)), index);

  return *this;
}

Функция key_prep добавляет знаки «-» в начало строки:

static std::string key_prep(std::string &&key)
{
  if (!key.empty() && std::isalnum(key[0]))
  {
    if (key.size() == 1)
      key.insert(0, 1, '-');
    else
      key.insert(0, "--");
  }

  return move(key);
}

Теперь можно заполнить тело функции help, которую можно использовать и в целях тестирования. Подумав, я решил убрать параметр «ширина строки», поскольку это не очень нужное усложнение. Реальную ширину строки консоли нельзя получить стандартными методами, а насильная вставка перевода строки может приводить к появлению избыточных пустых строк. Функция получилась длинная, но простая:

/// Construct a help message.
std::string help(
  std::size_t key_column_width = 20,
  const char *line_sep = "\n\n") const
{
  using namespace std;
  ostringstream write;
  write.setf(ios::left);

  // Option index -> first key (iterator).
  vector<Mapper::const_iterator> key_by_index(options.size());
  for (auto p = mapper.end(), b = mapper.begin();;)
  {
    --p;
    key_by_index.at(p->second) = p;
    if (p == b)
      break;
  }

  // Make the text.
  for (auto p = mapper.begin(), e = mapper.end(); p != e; ++p)
  {
    if (p->first.size() < key_column_width)
    {
      write.width(key_column_width);
      write << p->first;
    }
    else
    {
      write.width(0);
      write << p->first << '\n';
    }

    const auto pivot = key_by_index[p->second];
    if (pivot == p)
      write << get<1>(options[p->second]);
    else
      write << ("See " + pivot->first + ".");
    write << line_sep;
  }

  return write.str();
}

Самую сложную часть парсера — собственно разбор списка параметров — из-за недостатка времени в данный момент я оставил для следующей части.

Код данного варианта целиком.

Продолжение следует…

Conar 4: больше SFINAE

Начало

Предыдущая часть

Займёмся функциями, обеспечивающими чтение последовательностей. Первой такой функцией у меня будет не seq, а вариант value, который записывает каждое распознанное значение по итератору вывода.

template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    std::is_base_of<
      std::output_iterator_tag,
    typename std::iterator_traits<OutIt>::iterator_category>
      ::value, int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

Мелкая неприятность: пользователь должен явно указывать тип считываемых значений T. В принципе, можно сделать два варианта: аналогичный приведённому выше и выводящий тип значения с помощью iterator_traits::value_type. К сожалению, стандартные итераторы вывода, реализующие вставку в контейнеры, определяют value_type как void, делая тип элементов контейнера невыводимым для функции value. Кроме того, заметим, что forward_iterator_tag наследует от input_iterator_tag, но не от output_iterator_tag.

Введём простенькие вспомогательные определения.

/// Check if iterator It is compatible with category Cat.
template <class It, class Cat>
using Has_iterator_category =
  is_base_of<Cat,
    typename iterator_traits<It>::iterator_category>;

/// Check if iterator It is an output iterator.
template <class It>
using Is_output_iterator =
  Has_iterator_category<It,
    output_iterator_tag>;

/// Check if iterator It is a forward iterator.
template <class It>
using Is_forward_iterator =
  Has_iterator_category<It,
    forward_iterator_tag>;

/// Check if iterator It declares void as its value type.
template <class It>
using Has_void_value =
  is_same<void,
    typename iterator_traits<It>::value_type>;

Теперь два варианта value, пишущих через итераторы можно определить следующим образом:

/// Construct a value option, which writes values through an iterator.
/// Explicitly typed variant when the type is not derivable from OutIt.
template <class T, class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

/// Construct a value option, which writes values through an iterator.
template <class OutIt> inline
auto value(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    (impl::Is_output_iterator<OutIt>::value ||
     impl::Is_forward_iterator<OutIt>::value) &&
    !impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  using T = typename std::iterator_traits<OutIt>::value_type;
  return value_parser<T>(
    [dest](T val) mutable { *dest++ = std::move(val); },
    move(keys), move(info));
}

Тестирование этих определений вскрыло небольшое упущение: value_parser также должна создавать mutable-замыкание, если мы хотим упаковать в него своё mutable-замыкание, что требуется, в свою очередь, из-за необходимости передвигать итератор на каждом вызове и сохранять его изменённую версию между вызовами. Соответственно, я также добавил mutable в flag_parser и seq_parser.

Теперь можно перейти к seq.

Вариант seq, заполняющий условно бесконечную последовательность по итератору, написать не составит большого труда. Полная аналогия с вариантами value, указанными выше. Как и в случае с value, предполагается, что «места хватит» (интересно, сколько параметров командной строки можно скормить в распространённых ОС/интерпретаторах?).

Приведу одну из них. Вторая абсолютно аналогична.

template <class T, class OutIt> inline
auto seq(OutIt dest,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_output_iterator<OutIt>::value &&
    impl::Has_void_value<OutIt>::value,
    int> = 0)
{
  using std::move;
  return seq_parser<T>(
    [dest](T *from, T *to) mutable
    {
      while (from != to)
        *dest++ = std::move(*from++);
    },
    move(keys), move(info));
}

Для удобства пользователя можно добавить ещё три варианта seq, которые принимают непосредственно контейнеры, извлекают тип элементов через вложенное объявление value_type и выбирают способ вставки (push_back, insert или push) в зависимости от того, какой подходит. Для различения между push_back и insert (линейными и ассоциативными контейнерами) нам в качестве заготовки пригодится SFINAE-костыль Is_incrementable. Последний вариант seq подразумевает вставку в адаптер вроде std::stack с помощью вызова push.

/// Check if container C supports push_back(T&&).
template <class C, class T>
struct Supports_push_back
{
  template <class Y>
  static true_type check(decltype((void)(
    declval<Y>().push_back(declval<T>())
  ), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C&>(1));
  static constexpr bool value = type::value;
};

Два других детектора (Supports_insert и Supports_push) полностью аналогичны (да, макрос сюда так и просится). Вспомогательные определения для краткости записи сигнатур функций seq:

template <class C>
using Use_push_back =
  Supports_push_back<C, typename C::value_type>;

template <class C>
using Use_insert = bool_constant<
  Supports_insert<C, typename C::value_type>::value &&
  !Use_push_back<C>::value>;

template <class C>
using Use_push = bool_constant<
  Supports_push<C, typename C::value_type>::value &&
  !Use_push_back<C>::value &&
  !Use_insert<C>::value>;

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

/// Construct a seq option,
/// which appends a "push_back" container.
template <class Container> inline
auto seq(Container &cont,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Use_push_back<Container>::value,
    int> = 0)
{
  using std::move;
  using T = typename Container::value_type;
  return seq_parser<T>(
    [&cont](T *from, T *to) mutable
    {
      while (from != to)
        cont.push_back(std::move(*from++));
    },
    move(keys), move(info));
}

Ещё два варианта seq полностью аналогичны.

Код данного варианта целиком.

Продолжение следует.

Conar 3: перегрузка функций и SFINAE

Часть 1

Часть 2

Написанный к данному моменту код всё ещё ничего не делает. Попробуем сделать функции-«упаковщики», создающие опции на основе заданных обработчиков и значений Possible_keys и Option_info. Роль DTO будет выполнять std::tuple<Обработчик, Possible_keys, Option_info>. Всего предполагается три семейства функций, отвечающих трём видам опций (ранее трём классам): flag, value и seq.

Предполагается, что данные функции будут перегружены. Для «выключения» ненужных шаблонов, вызывающих проблемы с неединственностью возможного варианта вызова перегруженной функции, C++11 и новее предлагает std::enable_if. Однако здесь нам неудобно ставить enable_if «впереди» (в возвращаемом типе), т.к. функции возвращают кортеж, включающий член анонимного типа. Впрочем, enable_if всегда можно поставить последним параметром.

Базовые функции имеют следующий вид:

/// Create a flag option with a custom handler.
template <class FlagHandler> inline
auto flag(FlagHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_flag_handler<FlagHandler>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      f();
      return from;
    },
    move(keys), move(info));
}

/// Create a value option with a custom handler.
template <class T, class ValueHandler> inline
auto value(ValueHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
impl::Is_value_handler_for<ValueHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      if (from == to)
        return from;

      std::istringstream reader(*from);
      T val {};
      if (reader >> val)
      {
        f(std::move(val));
        ++from;
      }

      return from;
    },
    move(keys), move(info));
}

/// Create a value sequence option with a custom handler.
template <class T, class SeqHandler> inline
auto seq(SeqHandler handler,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_seq_handler_for<SeqHandler, T>::value, int> = 0)
{
  using std::move;
  return std::make_tuple(
    [f = move(handler)](auto from, auto to)
    {
      std::vector<T> values;
      for (std::istringstream reader; from != to; ++from)
      {
        reader.str(*from);
        T val {};
        if (!(reader >> val))
          break;

        values.emplace_back(std::move(val));
        reader.clear();
      }

      f(values.data(), values.data() + values.size());
      return from;
    },
    move(keys), move(info));
}

Теперь определим их перегруженные варианты для конкретных простых случаев.

Простейший случай — установка булевской переменной в соответствии с присутствием заданного флага в опциях.

/// Construct a flag option, which sets a Boolean variable.
inline auto flag(bool &flag_var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return flag(
    [&flag_var]() { flag_var = true; },
    move(keys), move(info));
}

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

template <class C>
struct Is_incrementable
{
  template <class Y>
  static true_type check(decltype(
    (void)(++declval<add_lvalue_reference_t<Y>>()), 1));

  template <class Y>
  static false_type check(unsigned);

  using type = decltype(check<C>(1));
  static constexpr bool value = type::value;
};

Собственно, код-«детектор» это ++declval<add_lvalue_reference_t<Y>>(), всё остальное — «boilerplate code». std::declval<Y> по умолчанию возвращает rvalue-ссылку, для которой ++ не определён, поэтому здесь следует предварительно сформировать «обычную» (lvalue) ссылку.

/// Construct a flag option, which increments a variable.
template <class C> inline
auto flag(C &counter,
  Possible_keys keys, Option_info info = {},
  std::enable_if_t<
    impl::Is_incrementable<C>::value &&
    !impl::Is_flag_handler<C>::value, int> = 0)
{
  return flag(
    [&counter]() { ++counter; },
    move(keys), move(info));
}

С Concepts этих корявеньких enable_if бы не было, да и прочие SFINAE-обороты можно было бы привести к менее костыльному виду. Но Concepts всё никак не принимают в стандарт…

Теперь займёмся value.
Запись прочитанного значения в заданную переменную могла бы иметь примерно такой вид:

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  return value<T>(/* что-то */);
}

Но данная сигнатура недостаточно хорошо «отличима» от сигнатуры базовой версии функции value… Я вижу три варианта решения проблемы: а) заставить пользователя указывать тип считываемого значения явно и проверять приводимость к T; б) ввести специальную функцию var, порождающую объект-обёртку переменной; в) проверять «читабельность» значений T из потока ввода (написать SFINAE-детектор аналогичный Is_incrementable и воспользоваться enable_if).

Вариант (б) менее интуитивен и вообще не очень мне нравится. Вариант (в) технически менее изящен, но более удобен для пользователя — не надо указывать тип явно.

Наконец, можно просто дать особые имена базовым функциям flag, value и seq, удалив их из набора перегруженных «удобных» функций прямого использования. Именно так я и поступлю. Теперь базовые версии flag, value и seq носят имена flag_parser, value_parser и seq_parser.

/// Construct a value option, which sets a variable.
template <class T> inline
auto value(T &var,
  Possible_keys keys, Option_info info = {})
{
  using std::move;
  return value_parser<T>(
    [&var](T val) { var = std::move(val); },
    move(keys), move(info));
}

В принципе, сейчас уже можно написать простенькие тесты на введённые выше «удобные» функции. Тесты добавлены в namespace test заголовочного файла conar.hpp. Тесты возвращают 0 в случае успеха. Объём кода тихонечко перевалил за 300 строчек. Интересно, в 1000 строк полная версия влезет?

Код данного варианта целиком.

Продолжение следует.

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

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