Monthly Archives: Август 2014

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

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

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

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

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

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

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

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

Начало программирования в D

Как известно, язык C был создан, чтобы сократить до минимума ассемблерную часть Unix. Язык C++ Строуструп создал, чтобы не писать на ассемблере, C и «различных современных языках высокого уровня». Было бы странно, если бы эта цепочка прервалась так скоро. Попыток заместить C было множество, но ни одна из них не удалась в полной мере. Последняя из подобных «неудач» — язык Go.

Впрочем, C++ тоже сформировал определённую нишу, и на неё тоже ведутся «посягательства». Вероятно, язык Java задумывали с тем, чтобы не писать ОО-программы на C++ (особую печаль у авторов, наверно, вызывала необходимость вручную удалять объекты, а также проблемы взаимодействия signed и unsigned значений). Что получилось, то получилось (имхо, получился новый COBOL). На сегодня у C++ есть конкуренты, гораздо более близкие к цели. Я имею в виду языки D и Rust. Что до Rust, то это проект действительно инновационный и многообещающий, но пока ещё недостаточно зрелый для серьёзного использования. А вот D, скорее, проект эволюционный, значительно более близкий C++ синтаксически и более зрелый.

D отказался от священной коровы C++ — совместимости с C. В этом вопросе D занимает следующую позицию: если код на C (или C++) компилируется как код на D, то и работает он, как предполагалось. Автор языка D Уолтер Брайт знаком с C++ «изнутри», так как был главным разработчиком компиляторов Zortech C++ (исторически первый компилятор C++ в машинный код, минуя промежуточный C), Symantic C++, Digital Mars C++ (уже в своей компании Digital Mars). Видимо, можно сказать, что D был создан, чтобы не программировать на C++.

Когда во времена до готовности C++11 я прочитал спецификацию D, то очень многие аспекты вызывали ощущение «вот этого-то мне так не хватало, когда я писал на C++» (это и нормальные модули и статические вычисления и автоматический вывод типов и более удобные встроенные массивы, контракты и доступность перемещения вместо копирования, юникод «из коробки»). C++11 несколько сгладил разрыв, но не все проблемы решены. Учитывая дальнейшее развитие C++ становится сложно сравнивать его с D. Главный плюс C++ — инфраструктура (компиляторы и библиотеки). У D есть ряд недостатков: большая зависимость от сборщика мусора (хотя формально им не обязательно пользоваться), сложная реализация RAII с выделением памяти на стеке (существенный минус, имхо). См. также обсуждение здесь.

Тем не менее, я решил попробовать. Поддержка проекта D Андреем Александреску, ставшим известным как автор книг по продвинутому C++, была одним из факторов, сподвигнувших меня начать экспериментировать с D. Итак, куплена книга Александреску «Язык программирования D» (в отличие от похожей по названию книги Строуструпа, стандартная библиотека D в этой книге отдельно не описывается, в примерах представлены только некоторые её элементы), можно начинать.

Есть три компилятора D (все — открытое ПО): референсный DMD от Уолтера Брайта, в котором реализована новейшая версия языка, компилятор GDC для инфраструктуры GCC, компилятор LDC на основе LLVM. Последний обещает выдавать наиболее оптимизированный код. Начинать проще с DMD, особенно в случае использования Windows: благо у него есть полноценные свежие сборки под Windows, включая поддержку целевой платформы x86-64. В качестве среды разработки можно использовать Visual Studio, если поставить Visual D. Отладка работает «из коробки». Для установки достаточно следовать инструкциям. Компилятор следует скачать и развернуть заранее (DMD фактически не обязательно «устанавливать», достаточно разархивировать и потом указать путь к нему). Каких-либо осложнений замечено не было.

Первую программу, которую я написал на D, я решил выложить в этом посте. Это, естественно, не HelloWorld. Это маленькая консольная утилита. Интерпретатор cmd.exe не имеет встроенных средств для замены заданных подстрок в файлах. Наверно, что-нибудь такое есть в powershell, я не изучал вопрос. Как-то так получилось, что я вообще не любитель всяких shell’ов.

Итак, пусть утилита получает замены в виде пар параметров (так что замен может быть сразу несколько), обрабатываемый файл читает из стандартного потока ввода, результат с заменами пишет в стандартный поток вывода.

Один из основных принципов работы с наборами значений в D — использование диапазонов (ranges), диапазоны заменяют пары итераторов C++ (см. презентацию Александреску Iterators Must Go! и статью On Iteration). Я воспользуюсь функцией byLine(), которая возвращает диапазон, позволяющий работать с потоком как с последовательностью строк. К каждой строке я буду применять замены. Кстати, стандартная функция replace требует подключения модуля std.array, одного std.string недостаточно. Вообще же, строка D — это массив неизменяемых символов. Итак, собственно код утилиты (к сожалению, на момент написания плагин форматирования исходного кода не имеет поддержки синтаксиса D).

// replace all substrings in a text file (by line)
// each pair of arguments constitutes a substitution "a" -> "b"
import std.stdio;
import std.string;
import std.array;

int main(string[] argv)
{
  immutable size_t args = (argv.length - 1) & ~1u;
  if (args == 0)
    stderr.write("No parameters means I send input to output as is.\n");

  // for each line in input
  foreach (line; stdin.byLine())
  {
    // for each pair of substitutions in parameters 
    for (size_t i = 0; i < args; i += 2)
      line = replace(line, argv[1 + i], argv[2 + i]);

    // output the result
    writeln(line);
  }

  return 0;
}