О затенении перегрузок функций

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

Рассмотрим простенький код: определим оператор вывода вектора в поток.

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

ostream& operator<<(ostream &os, const vector<int> &v)
{
	for (auto x: v)
		os << x << ' ';
	return os;
}

int main()
{
	cout << vector<int>{ 1, 2, 3, 4 } << endl;
	return 0;
}

Он работает так, как и предполагается, никаких проблем нет. Range-for — удобная штука: до его появления обход контейнера с помощью итераторов выглядел страшненько. Вместо явного цикла можно было воспользоваться возможностями STL: алгоритмом copy и адаптером потока ostream_iterator.

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

ostream& operator<<(ostream &os, const vector<int> &v)
{
	ostream_iterator<int> oi(os, " ");
	copy(begin(v), end(v), oi);
	return os;
}

int main()
{
	cout << vector<int>{ 1, 2, 3, 4 } << endl;
	return 0;
}

Этот вариант работает точно так же, как и предыдущий. Всё в порядке.

Попробуем обобщить его, например, на вектор векторов…

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

ostream& operator<<(ostream &os, const vector<int> &v)
{
	ostream_iterator<int> oi(os, " ");
	copy(begin(v), end(v), oi);
	return os;
}

ostream& operator<<
	(ostream &os, const vector<vector<int>> &m)
{
	ostream_iterator<vector<int>> oi(os, "\n");
	copy(begin(m), end(m), oi);
	return os;
}

int main()
{
	using VI = vector<int>;
	vector<VI> m
	{
		VI{ 1, 2, 3, 4 },
		VI{ 5, 6, 7, 8 },
		VI{ 9, 0, 1, 2 },
	};
	
	cout << m << endl;
	return 0;
}

И вот она, ошибка… Этот код уже не компилируется. Как часто бывает в таких случаях, компилятор может высыпать ворох маловразумительных ошибок. Проблема в операторе <<. Точнее, в том факте, что в том же пространстве имён std, где определены ostream_iterator и vector, определён и набор стандартных перегрузок operator<<, который «затеняет» operator<< из глобального пространства имён.

Простейший способ избавиться от ошибки — поместить свою версию operator<< также в пространство имён std. Например, такой код уже благополучно компилируется и работает правильно:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

namespace std
{
	ostream& operator<<(ostream &os, const vector<int> &v)
	{
		ostream_iterator<int> oi(os, " ");
		copy(begin(v), end(v), oi);
		return os;
	}
}

ostream& operator<<
	(ostream &os, const vector<vector<int>> &m)
{
	ostream_iterator<vector<int>> oi(os, "\n");
	copy(begin(m), end(m), oi);
	return os;
}

int main()
{
	using VI = vector<int>;
	vector<VI> m
	{
		VI{ 1, 2, 3, 4 },
		VI{ 5, 6, 7, 8 },
		VI{ 9, 0, 1, 2 },
	};
	
	cout << m << endl;
	return 0;
}

Я намеренно не стал помещать второй operator<< внутрь namespace std, чтобы показать, что здесь проблема была с первым operator<<, который должен вызываться некоей функцией, определённой в std.

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

Следующий пример определяет рекурсивную версию operator<<, которую тоже приходится поместить в namespace std:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;

namespace std
{
	template <class T>
	ostream& operator<<(ostream &os, const vector<T> &m)
	{
		ostream_iterator<T> oi(os.put('{'), " ");
		copy(begin(m), end(m), oi);
		return os.put('}');
	}
}

int main()
{
	using VI = vector<int>;
	vector<VI> m
	{
		VI{ 1, 2, 3, 4 },
		VI{ 5, 6, 7, 8 },
		VI{ 9, 0, 1, 2 },
	};
	
	cout << m << endl;
	return 0;
}

Вообще, «по умолчанию» считается плохим тоном вносить собственные определения в пространство имён std (есть исключения, например, частные специализации hash).

Для операций с собственными типами, определёнными в собственном пространстве имён, возможно положиться на ADL, поместив перегрузки операторов в то же самое пространство имён. В вышеприведённых примерах использовался std::vector, а определение операций для стандартных классов приводит к опасности коллизии разных определений для одних и тех же шаблонных классов, появившихся в разных местах проекта. Лично мне бы хотелось иметь в C++ «strong typedef», тем более, что для него даже новых ключевых слов вводить не надо:

namespace my
{
	using Data = new vector<int>;
	// Теперь Data != vector<int> и
	// определён в пространстве имён my.
	ostream& operator<<(ostream &os, const Data &d);
}

Мечты-мечты.

Реклама

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 строк полная версия влезет?

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

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

Conar 2: классы за борт!

Начало

Вторая «серия» планировалась через два дня после первой. Получилось — через две недели. Лень-матушка вперёд нас родилась…

Синтаксис вызова парсера

Предложенный ранее синтаксис для Parser несколько избыточен по части скобок :)

Новый синтаксис:

auto parser = parse(опция_1, опция_2, ...);
auto unparsed = parser(argc, argv);
cout << parser.help(...) << endl;

С помощью шаблона с переменным числом параметров данный синтаксис легко добавить к тому, что уже есть:

namespace impl
{
  /// A stub for parse with more parameters.
  inline void parse(Parser&) {}

  /// Add all options to the parser in one recursive call.
  template <class Opt1, class... Other> inline
  void parse(Parser &parser, Opt1 &&option_1,
               Other&&... other_options)
  {
    parser(forward<Opt1>(option_1));
    parse(parser, forward<Other>(other_options)...);
  }
}

/// Make a parser with all options in one call.
template <class... Options>
Parser parse(Options&&... options)
{
  Parser parser;
  impl::parse(parser, forward<Options>(options)...);
  return parser;
}

Представление опций

Объединение общего описания possible_keys и info (фактически, это DTO) с типозависимым поведением (handler) не есть хорошо. Можно было бы сделать из Option чисто абстрактный класс («интерфейс»), наследники которого определяли бы вызов обработчика (handler) и, вероятно, распознавание текста (собственно параметров) — пара виртуальных функций.

Но зачем парсеру знать эти подробности? Фактически, с точки зрения парсера всё поведение «опции» сконцентрировано в одном действии — распознавании текста. Какие там в процессе значения получаются, и как они затем обрабатываются, парсеру всё равно. Поэтому соблазнительно определить это одним замыканием (функциональным объектом), который «скармливается» парсеру. Надо только придумать интерфейс вызова…

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

Вариант ключа 1, ключ t, time

-t5, --time=5 — только одно значение может быть параметром — то, что идёт сразу за ключом или после знака =. Это часть («хвост») аргумента командной строки. Все прочие аргументы к делу не относятся.

Вариант ключа 2, ключ times

--times 10 start 20 finish — произвольное число параметров — аргументы командной строки за аргументом, содержащим ключ, и до конца или следующего аргумента, содержащего ключ.

Вариант ключа 1 можно рассматривать как частный случай варианта ключа 2. Для разбора в какой-то форме можно передавать массив строк. А возвращать, например, количество успешно распознанных строк. Но как сообщать другие ошибки: неверный формат, недостаточное количество параметров? В конце концов, этот вопрос можно отдать на откуп обработчику, а не решать его на уровне парсера.

Итого, получаем STL-подобный интерфейс:

template <class FwdIt>
FwdIt option_parse(FwdIt from, FwdIt to);
// iterator_traits<FwdIt>::value_type = string

Статическая проверка на соответствие сигнатуры вызова предполагаемого обработчика распознанных значений ключа может выполняться с помощью следующих определений (упакованы в namespace impl):

template <class FlagHandler>
using Is_flag_handler = std::is_convertible<
	FlagHandler, std::function<void()>>;

template <class ValueHandler, class T>
using Is_value_handler_for = std::is_convertible<
	ValueHandler, std::function<void(T)>>;

template <class SeqHandler, class T>
using Is_seq_handler_for = std::is_convertible<
	SeqHandler, std::function<void(T*, T*)>>;

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

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

Пример функциональной декомпозиции

Задача вроде тех, что решают студенты на нашем экзамене после первого семестра.

«Дана прямоугольная матрица. Найти в ней первую строку, не содержащую нулей, или определить, что таких строк нет.»

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

Решение в стиле C подразумевает прототип функции вроде (матрицу можно оформить по-разному, но предпочтём пока простейший вариант):

float* find_row_without_zero
  (float **a, size_t rows, size_t cols);

— вернуть указатель на соответствующую строку, либо nullptr, если такой нет.

Итак, студент видит слово «матрица», из чего делает вывод, что здесь явно двойной цикл, и пишет что-то такое:

float* find_row_without_zero
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
        // ???
      else
        // ???

Почему-то многим очень хочется поставить else-секцию с возвратом результата. Т.е. ошибочно подменить квантор «все» (не нули) на «существует». Под if в этом случае идёт break. Положим, стало ясно, что else здесь никак не нужен. Что же делать? Типичное неказистое решение имеет следующий вид:

// Bad structured programming (using a flag variable).
float* find_row_without_zero_1
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    bool found = true;
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
      {
        found = false;
        break;
      }
    }

    if (found)
      return a[i];
  }

  return nullptr;
}

В принципе, кто-то может решиться на использование goto, что даёт избавление от лишней переменной. Но это маловероятно: в примерах goto почти не встречается, а в книгах последних десятилетий его использование традиционно порицается.

// I'm not afraid of GOTO!
float* find_row_without_zero_2
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
      if (a[i][j] == 0)
        goto next_row;

    return a[i];
  next_row:;
  }

  return nullptr;
}

На самом деле, данная задача подразумевает применение функциональной декомпозиции (основного метода программирования, кстати). Достаточно понять, что решение по сути является композицией двух линейных поисков.

// Good structured programming:
// applying functional decomposition.
float* find_value
  (float *a, size_t size, float val)
{
  for (size_t i = 0; i < size; ++i)
    if (a[i] == val)
      return a + i;
  return nullptr;
}

float* find_row_without_zero_3
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (!find_value(a[i], cols, 0))
      return a[i];
  return nullptr;
}

Если предполагается использование STL (после первого семестра это ещё не предполагается), то явный цикл можно заменить на вызов std::find, так:

// Ah, std::find does the work in C++.
float* find_row_without_zero_4
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (std::find(a[i], a[i] + cols, 0.f) == a[i] + cols)
      return a[i];
  return nullptr;
}

или даже так (ещё std::find_if, шаблон по типу данных и значение по умолчанию вместо явного нуля):

// It's not beautiful, I guess...
template <class NT>
NT* find_row_without_zero_5
  (NT **a, size_t rows, size_t cols)
{
  const auto p = std::find_if(a, a + rows,
    [cols](NT *a)
    {
      return std::find(a, a + cols, NT{}) == a + cols;
    });
  return p == a + rows? nullptr: *p;
}

Последний вариант, впрочем, наверно, избыточно «навороченный».

Ну и наконец, можно поразвлекаться в функциональном стиле (требуется C++14), отказавшись от указателей и рассматривая матрицу как диапазон диапазонов. Будем возвращать итератор в стиле STL.

using std::forward;

template <class Item>
auto equals(Item &&item)
{
  return [it = forward<Item>(item)]
  (auto &&other)
  {
    return other == it;
  };
}

template <class Pred>
auto find(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::begin;
    using std::end;

    const auto e = end(rng);
    auto p = begin(rng);
    while (p != e && !pr(*p))
      ++p;

    return p;
  };
}

template <class Pred>
auto none(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::end;
    return find(pr)(rng) == end(rng);
  };
}

Вышеприведённые определения позволяют в итоге записать решение в виде композиции:

template <class Rng2>
auto find_row_without_zero_6(Rng2 &&rows)
{
  return find(none(equals(0)))(rows);
}

Забавно, что такая конструкция применима не только, например, к вектору векторов, но и к статическому двумерному массиву:

float m[3][4]
{
  { 1, 1, 1, 0 },
  { 0, 1, 1, 1 },
  { 1, 0, 1, 1 },
};

assert(find_row_without_zero_6(m) == std::end(m));

Conar: минипарсер параметров командной строки

Как известно, задача распознавания параметров командной строки давно и неоднократно решена. Примеры (список далеко не полон): Boost.Program_options (навороченная, и, увы, требует сборки), TCLAP, ezOptionParser, AnyOption, The Lean Mean C++ Option Parser. Обзора я делать не буду, напишу лишь, что ознакомление с данными библиотеками не отбило у меня желание сделать свою :)

Я хочу библиотеку: header-only (вообще полностью определённую в одном заголовочном файле), C++ (поддержка STL-контейнеров, анонимных функций), никакого (L)GPL (Boost-лицензия лучшая же), использование только Стандартной библиотеки C++ (пусть с элементами ещё не принятого C++17), действительно простая схема использования, не требующая писать каскады if-else или switch-case и явно использовать механизмы type-erasure (void*, any и т.п.). Производительность же не играет особого значения. Особая универсальность также мне не нужна.

Такая библиотека может быть достаточно маленькой для ad hoc программирования (без проектирования). Однако это не самое простое упражнение в программировании. Попробую описать её разработку (начата на момент написания этих строк) «в ходе процесса» в нескольких постах.

Итак, с чего начать? Начнём с названия :) У меня это будет conar.hpp («console arguments»).

#ifndef CONAR_HPP_INCLUDED_N98K2U
#define CONAR_HPP_INCLUDED_N98K2U

namespace conar
{
  // ...
}

#endif//CONAR_HPP_INCLUDED_N98K2U

Далее весь код размещается внутри пространства имён conar. Необходимые #include подразумеваются и в тексте не упоминаются.

Ключ — имя опции (параметра командной строки). Опции может соответствовать несколько ключей. Если ключ состоит из одной буквы, то предполагается, что перед ним ставится один дефис («минус»). Если ключ состоит из нескольких букв (и, возможно, цифр), то перед ним ставится два дефиса (предполагаемое автоматическое дополнение пользовательских ключей). Если хочется иной формулировки, например, на дробь / как принято в Windows, то достаточно будет явно указать этот знак. Предполагается, что ключи чувствительны к регистру (в Windows принято иначе, да…). При поиске соответствия будем пытаться подобрать наиболее длинное возможное совпадение. Навскидку наивный алгоритм даёт в худшем случае время разбора O(N L log K + S), где N — количество параметров, L — длина наиболее длинного ключа, K — общее количество ключей, S — суммарное количество символов во всех параметрах.

Опция вида -abc интерпретируется как последовательность трёх опций -a -b -c, если не заданы явно ключи -abc или -ab. В последнем случае возможна попытка прочитать это как -ab c, успешность которой зависит от того, принимает ли -ab строку или символ.

Итак, базовый класс Option для различных классов опций. Нужно ли здесь вообще наследование с виртуальными функциями? Не уверен, посмотрим.

  /// Basic description of a command line option.
  struct Option
  {
    using Possible_keys = std::vector<std::string>;
    using Info = std::string;

    /// Keys corresponding to this option.
    Possible_keys possible_keys;
    /// Information about this option (for help).
    Info info;

    virtual ~Option() {}
    // This class may be extended later.
  };

Классы опций. Наследники класса Option. Объекты этих классов хранят обработчики (handler) распознанных параметров.

Флаг — опция без параметров, соответственно, обработчик имеет сигнатуру void().

  struct Flag_option: Option
  {
    using Handler = std::function<void()>;
    Handler handler;
  };

Значение — опция с одним параметром заданного типа T. Посему это шаблон. Обработчик имеет сигнатуру void(T) и будет вызываться для каждого удачно распознанного ключа с параметром.

Пример (-t, --time, T = int)

-t1 --time=2 -t 3 6 7 --time 4 8 9 даст четыре вызова обработчика с параметрами 1, 2, 3 и 4.

  template <class T>
  struct Value_option: Option
  {
    using Handler = std::function<void(T)>;
    Handler handler;
  };

Последовательность — опция, предполагающая передачу последовательности значений заданного типа (T) после ключа. Обработчик имеет сигнатуру void(T*, T*) и принимает диапазон массива с очередной успешно считанной последовательностью значений (их может быть несколько — для каждого упоминания ключа).

Пример (-i, --input, T = string)

-i "a b c" d e --input "next time" do this даст два вызова с массивами { «a b c», «d», «e» } и { «next time», «do», «this» }.

  template <class T>
  struct Seq_option: Option
  {
    using Handler = std::function<void(T*, T*)>;
    Handler handler;
  };

Парсер. Главный компонент библиотеки. Опции будем регистрировать, передавая объекты классов-наследников Option с помощью оператора (), который возвращает ссылку на объект парсера. Параметры функции main для распознавания (после регистрации всех опций) также передадим оператором (). Т.е. предполагается использование вроде

Parser{}(опция 1)(опция 2)(опция 3)(argc, argv);

результат вызова — список (вектор) нераспознанных параметров (в текстовой форме «как есть»).

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

Итак, заготовка Parser.

  class Parser
  {
  public:
    /// Construct a help message part that describes all the options known to the parser.
    std::string help(int key_column_width = 20, int line_width = 80, const char *line_sep = "\n") const
    {
      std::string result;
      // TODO
      return result;
    }

    /// Add an option description. Use functions flag and value for this.
    template <class Opt>
    Parser& operator()(Opt option)
    {
      static_assert(std::is_base_of<Option, Opt>::value);
      // TODO
      return *this;
    }

    /// A list of unparsed parameters.
    using Unparsed_parameters = std::vector<std::string>;

    /// Finally parse the command-line parameters given by an iterator range (of strings).
    template <class InIt>
    Unparsed_parameters operator()(InIt from, InIt to)
    {
      static_assert(std::is_convertible<
        typename std::iterator_traits<InIt>::iterator_category,
        std::input_iterator_tag>::value);

      Unparsed_parameters unparsed;
      // TODO
      return unparsed;
    }

    /// Parse arguments as they are passed to main, argv[0] is ignored.
    Unparsed_parameters operator()(int argc, char *argv[])
    {
      return (*this)(argv + 1, argv + argc);
    }
  };

Вот так, раз-два и готов файлик в сотню строк. Которые, впрочем, пока абсолютно бесполезны…

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

О реализации целочисленного аналога функции sqrt

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

При вычислении sqrt(x) в плавающей точке обычным методом является вычисление 1/sqrt(x) методом Ньютона и затем домножение на x (основная хитрость практической реализации данного метода заключается в способе выбора начального приближения). Эффективно применять этот метод, используя только целочисленные операции, вряд ли возможно, поэтому я решил посмотреть, насколько хорошо (по крайней мере, на конкретном процессоре) в этой задаче работает прямой лобовой метод — двоичный поиск.

Но даже двоичный поиск можно реализовать по-разному. И естественно хочется уметь сравнивать быстродействие разных вариантов в разных условиях.

Неожиданным открытием при первом простом тестировании стала зависимость скорости выполнения функции от её положения в asm-файле (для ассемблерных вариантов). Директива align перед циклами, напротив, не продемонстрировала устойчивого эффекта. Наиболее вероятным «виновником» в данном случае является предсказатель ветвлений и особенности его работы для конкретного CPU. Также может сказываться работа L1I и TLB (здесь, в частности, может удачно или неудачно подействовать директива align).

В случае «простого» тестирования вроде многократного вызова одной функции в цикле есть немалый шанс натолкнуться на проявление таких особенностей во всей их красе. Поэтому я решил поступить несколько хитрее: выполнить псевдослучайное перемешивание разных вызовов. В каждом прогоне — разное количество вызовов разных функций. Выполнив столько же прогонов, сколько у нас есть функций, получим вектор суммарных времён и матрицу количеств вызовов. Решив линейное уравнение, получим оценки времени вызова каждой функции. Можно сделать и больше прогонов и получить решение с помощью МНК (здесь не реализовано). В итоге я всё же не стал использовать аналитически обращаемую матрицу, а задействовал библиотеку uBLAS из состава Boost. См. также о влиянии фрагментации кучи на результаты тестирования.

Использовалась среда Microsoft Visual C++ 2015, компиляция под x86-64 с O2. Причёсывать код однолетней давности я уже поленился — там есть, что выкинуть, но если бы я этим занялся, то… В общем, год уже и так прошёл.

Замечание. В MSVC все исходники .c, .cpp, .asm должны иметь разные имена, так как при компиляции каждого из них порождается одноимённый .obj файл, которые сваливаются в одну общую папку и могут затирать друг друга с печальным результатом во время компоновки.

Итак, исследуемые варианты:

  1. cpp1, asm1 — цикл + ветвление;
  2. cpp2, asm2 — цикл + cmov;
  3. cpp3, asm3 — цикл + ветвление + ilog2 (целочисленный логарифм позволяет выбрать хорошее начальное приближение, для его реализации на x86 используется команда bsr или lzcnt);
  4. cpp4, asm4 — цикл + cmov + ilog2;
  5. asm5 — развёрнутый вариант asm3;
  6. asm6 — развёрнутый вариант asm4 (computed goto);
  7. fpu — использует команды SSE для вычисления isqrt (стандартный метод);
  8. null — ничего не делает, используется для оценки времени вызова.

Итак, результаты тестирования представлены на графике ниже. Числа получены следующим образом: в каждом прогоне использовалось 100’000 псевдослучайных чисел-аргументов, равномерно распределённых от нуля до числа, указанного по оси 0x (1k — 1024, 32k — 32’768, 1M — 220, 1G — 230), выполнялось 1100 повторений, из которых верхние и нижние 5% полученных оценок времён отбрасывались, а от оставшихся 1000 бралось арифметическое среднее. Всего выполнялось по 10 таких прогонов, из результатов которых для каждой функции выбиралось минимальное значение и затем вычиталось соответствующее минимальное значение функции null. В конце все результаты нормировались по функции fpu, так что по оси 0y графиков мы видим, во сколько раз все варианты медленнее вычисления isqrt на fpu.

Процессор, на котором производился тест — AMD K10. Итак, мы видим, что «бодаться» с FPU на «больших» процессорах (пусть даже старых) бессмысленно. Пиррова победа в режиме 1k у asm4/cpp4. Применение ilog2 в комбинации с cmov даёт весьма неплохой эффект, который может оказаться ещё выше на простых процессорах без хорошего предсказателя переходов. А вот разворачивание цикла здесь не помогает (впрочем, опять же на «простом» процессоре ситуация может быть другой).

Простые годы

18 век

1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789

19 век

1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889

20 век

1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999

21 век

2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099

Пример наложения текста, формируемого средствами LaTeX, поверх изображения

Довольно типичной является ситуация, когда требуется вставить в текст на LaTeX изображение в векторном формате, содержащее надписи, причём эти надписи содержат формулы, и очень желательно обеспечить одинаковость шрифта в надписях в изображении со шрифтом в основном тексте. Добиться этого только средствами редактора изображений затруднительно. Обычным методом в таких случаях является использование текстовых меток («тегов») в изображении, которые, например, с помощью пакета psfrag подменяются текстом, сформированным LaTeX, уже во время компиляции tex-файла.

Однако в некоторых ситуациях psfrag не подходит. Одной из проблем с psfrag, рассчитанным на eps/dvi, является сложная схема работы с компиляцией в pdf, в процессе исполнения которой могут возникать непреодолимые ошибки. Заменить psfrag можно разными средствами. В данном посте я хочу продемонстрировать простейшее такое средство — команду \put.

Пусть есть следующее изображение (в формате pdf).

Пример векторного изображения

Пример векторного изображения

Замечание. Изображение, использованное здесь в качестве примера, было создано в векторном редакторе Inkscape. Данный редактор позволяет экспортировать изображение командами теха или генерировать вспомогательный тех-файл, использующий команду \put для вставки текстовых боксов поверх изображения, которые затем можно поправить по своему усмотрению. Однако, я не могу сказать, что это значимо упрощает работу по сравнению с «ручным методом», изложенным ниже, так как размеры текстовых надписей всё равно в итоге будут другими, а значит, всё равно придётся подгонять координаты. При этом генерируемый Inkscape’ом исходник теха содержит кучу вспомогательного кода со всякими там \makeatletter и \providecommand, что может быть непозволительной роскошью, например, при подготовке статьи в журнал.

Итак, всё что требуется — это пакет graphicx и окружение picture. Следующий пример LaTeX-кода

\documentclass[11pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}

\usepackage{graphicx} %

\usepackage{amssymb}
\usepackage[english,russian]{babel}

\begin{document}
\selectlanguage{russian}

\author{Кувшинов~Д.~Р.}
\title{Пример наложения текста, формируемого средствами
 \LaTeX, поверх изображения}

\maketitle

Какой-то текст над картинкой. Просто, чтобы занять место.
Ну должен же здесь быть какой-нибудь текст?
Хотя бы на пару строчек?

\bigskip

\begin{figure}[h]
\begin{center}
\begin{picture}(320,192)(0,0)
 \put(16,16){
  \includegraphics[width=288\unitlength]{image}}
    
 \put(53,106){
  \makebox(0,0)[lb]{$u$}}
 \put(125,109){
  \makebox(0,0)[lb]{$f$}}
 \put(106,186){
  \makebox(0,0)[lb]{$f$}}
 \put(107,56){
  \makebox(0,0)[lb]{$f$}}
 \put(226,102){
  \makebox(0,0)[lb]{$f(t,x,u)$}}
 \put(0,45){
  \makebox(0,0)[lb]{$\mathbb B^r(u; \delta(\rho))$}}
 \put(106,3){
  \makebox(0,0)[lb]{$\mathbb B^n(f(t, x, u); \rho)$}}
 \put(316,189){
  \makebox(0,0)[lb]{$\mathbb R^n$}}
 \put(224,6){
  \makebox(0,0)[lb]{$f(t, x, \mathbb B^r(u; \delta(\rho)))$}}
 \put(0,189){
  \makebox(0,0)[lb]{$\mathbb R^r$}}
\end{picture}
\end{center}
\caption{Отображение $f$.}\label{pict:P1}
\end{figure}

Ну и немного текста под картинкой. Никакого \verb!\bigskip!
или \verb!\vspace! здесь уже не требуется.

\end{document}

даёт

Результат наложения текста на картинку

Результат наложения текста на картинку