Александр Степанов

Александр Степанов - это создатель STL. Ни добавить, ни отнять. Последние годы он занимается в основном преподаванием и написанием книг.

Недавно я купил его последнюю книгу "Elements of Programming".



Довольно своеобразная книга. Много математики, приводимой как обоснование тех или иных приемов в программировании (язык, конечно, С++), из-за чего читается немного тяжело. Забавно, я читал многие его публикации до этого, и как-то заметил, что чем дальше, тем больше он использует формальную математику для описания программирования.

Еще интересный факт: в данной книге везде при использовании шаблонов используются концепты, хотя недавно было принято решение, что в C++0x их не будет из-за общей пока недоработанности идеи.

Но вернемся к другим публикациям Степанова.

Одни из мои любимых - Notes for the Programming course at Adobe и Science of C++ Programming.

Например, ставший классикой, его пример на тему итераторов:

if (!v.empty()) {
  sort(&*begin(), &*v.begin() + v.size());
}

когда спрашивается, почему в данном вполне рабочем примере обязательно нужна проверка v.empty() и почему нельзя второй аргумент нельзя записать как &*v.end()?

Но вот что лично мне понравилось, это способ реализации оператора присваивания для класса. Обычно, когда в классе есть конструктор копирования и оператор присваивания, стандартный прием - это сделать закрытую функцию типа clone() или copy(), которая умеет правильно копировать класс, если внутренняя его структура нетривиальна, и вызывать эту функцию из конструктора копирования и оператора присваивания, тем самым избегая дублирования кода.

Но Степанов говорит следующее: "...присваивание должно осуществляться вызовом деструктора и последующим конструктором". То есть надо просто сделать полноценный конструктор копирования, а оператор присваивание реализовать так:

T& T::operator=(const T& x) {
  if (this != &x) {
    this->T::~T();
    new (this) T(x);
  }
  return *this;
}

Получается, что старый объект сам себя разрушает, вызвав деструктор (но память под ним не освобождается), а затем оператором new с явным размещением (память под объект тут уже повторно не распределяется) объект создается снова через конструктор копирования.

В общем, данные pdf-ки - очень интересное чтиво. Причем, Степанов никогда не забывает об эффективности (ибо неграмотное использования возможностей шаблонов элементарно делает программу очень медленной и жадной до ресурсов), и, например, главы про техники перемещения, а не копирования объектов очень познавательны.

Параметры по умолчанию в С++ - это опасно

Значения формальных параметров по умолчанию в С++ - удобная штука. Удобная и опасная.

Вот книжный пример (default_values.cpp):

#include <iostream>

class X {
 public:
  virtual void f(int i = 0) {
    std::cout << "X::f(): " << i << std::endl;
  }
};

class Y: public X {
 public:
  void f(int i = 1) {
    std::cout << "Y::f(): " << i << std::endl;
  }
};

int main() {
  X* a = new Y;
  a->f();

  Y* b = new Y;
  b->f();

  return 0;
}

Что распечатает эта программа? Вот что:

Y::f(): 0
Y::f(): 1

В обоих случаях была вызвана функция Y::f(), но значение аргумента было разное.

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

Я намеренно опустил модификатор virtual в описании функции f() в классе Y. Но от этого она невиртуальной не стала. При сложной иерархии классов очень несложно не заметить, что изначально функция была виртуальной, и для собственного удобства подправить ей значение параметра по умолчанию для какого-то конкретного случая, тем самым привнеся очень неприятную ошибку (и тут уже надежда на зоркий глаз коллеги при code view или на статические анализаторы).

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

Посты по теме:

• Google запрещает параметры по умолчанию для своих разработчиков
• Статический анализ кода (Coverity, Klocwork)
• Ведение блога на Google Code

---

Как я уже писал ранее, все исходные тексты и статьи теперь дублируются на одноименном сайте, размещенном на Google Code.

Парадокс Монти-Холла

Есть такая интересная задача - парадокс Монти-Холла.

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

Естественно, ведущий точно заранее знает где приз и заведомо открывает пустой ящик. Итак, вы изначально выбрали ящик, но потом ведущий открыл один из оставшихся и выяснилось, что он пустой. Перед вами выбор: оставить свой изначальный выбор неизменным или изменить его, выбрав третий ящик (тот, что остался после вашего первого выбора и после открытия ведущим пустого ящика). При какой стратегии вероятность выигрыша выше?

Самое прямолинейное решение, приходящее в голову: смена ящика ничего особенно не даст. Вы выбрали один ящик из трех - вероятность выиграть 1/3. После открытия одного ящика ведущим их осталось два, поэтому вероятность угадать где приз 50/50. Выбор вы уже сделали, и он и так является одним из текущих вариантов. Выходит, что нет особого смысла менять выбор.

Но эта задачка тем и интересна, что при столь тривиальной постановке ее правильное решение не совсем очевидно, хотя с точки зрения теории вероятности тут все прозрачно - теорему Байеса еще никто не отменял.

Правильный ответ - да, надо менять выбор, так как в этом случае вероятность угадать повышается с 1/3 до 2/3 (и даже не 1/2).

В Википедии приведено исчерпывающее объяснение.

Ну а чтобы уж окончательно развеять все сомнения, пришлось провести эксперимент.

montihall.cpp:

#include <iostream>
#include <set>
#include <cstdlib>
#include <cassert>
#include <ctime>

int all_doors[] = { 1, 2, 3 };

bool no_change_strategy() {
  // doors - это множество доступных дверей (1, 2, 3) для выбора игроком.
  std::set<int> doors(all_doors, all_doors + 3);

  // Выбираем истинную дверь (от 1 до 3).
  int real_door = (std::rand() % 3) + 1;

  // Выбираем первый и окончательный выбор игрока (от 1 до 3).
  int primary_choice_door = (std::rand() % 3) + 1;

  return real_door == primary_choice_door;
}

bool change_strategy() {
  // doors - это множество доступных дверей (1, 2, 3) для выбора двери,
  // открываемой ведущим после первого выбора игрока.
  std::set<int> doors(all_doors, all_doors + 3);

  // Выбираем истинную дверь (от 1 до 3).
  int real_door = (std::rand() % 3) + 1;

  // Выбираем первый выбор игрока (от 1 до 3)
  int primary_choice_door = (std::rand() % 3) + 1;

  // Исключаем из множества дверей истинную дверь и выбор игрока.
  doors.erase(real_door);
  doors.erase(primary_choice_door);
  // На всякий пожарный проверим целостность данных.
  assert(doors.size() == 1 || doors.size() == 2);

  // Из оставшихся элементов (их может быть 1 или 2 штуки) выбираем дверь,
  // которую откроет ведущий. reveal_door равно либо 1, либо 2.
  int reveal_door = (std::rand() % doors.size()) + 1;

  // i указывает на первый элемент в множестве (всего в нем 1 или 2 элемента).
  std::set<int>::const_iterator i = doors.begin();
  // Сдвигаем итератор на элемент, номер которого равен reveal_door.
  // Можно было бы написать "if (reveal_door == 2) ++i;", но цикл как-то
  // универсальнее.
  while (--reveal_door) ++i;
  reveal_door = *i;

  // 'doors2' - это множество доступных дверей (1, 2, 3) для игрока,
  // меняющего свой первоначальный выбор.
  std::set<int> doors2(all_doors, all_doors + 3);

  // Исключаем из множества дверей первый выбор игрока и
  // и дверь, открытую ведущим.
  doors2.erase(primary_choice_door);
  doors2.erase(reveal_door);
  // На всякий пожарный проверим целостность данных.
  assert(doors2.size() == 1);

  // В множестве оставшихся дверей будет только одна дверь, так как истинная 
  // дверь точно не равна двери, открытой ведущим, во второй выбор игрока
  // точно отличается от первоначального. Поэтому просто берем из этого 
  // множества первый элемент.
  int second_choice = *doors2.begin();

  return real_door == second_choice;
}

int main() {
  std::srand(std::time(0));
  int guess_on_change = 0;
  int guess_on_not_change = 0;
  int N = 100000;
  for (int i = 0; i < N; ++i) {
    if (change_strategy())
      guess_on_change = guess_on_change + 1;
    if (no_change_strategy())
      guess_on_not_change = guess_on_not_change + 1;
  }
  std::cout << "Вероятность выиграть при смене изначального выбора: "
    << guess_on_change * 1.0 / N << std::endl;
  std::cout << "Вероятность выиграть не меняя изначального выбора: "
    << guess_on_not_change * 1.0 / N << std::endl;
  return 0;
}

Компилируем и запускаем:

cl /EHsc /D_NDEBUG montihall.cpp && montihall

Результат подтверждает теорию:

Вероятность выиграть при смене изначального выбора: 0.67005
Вероятность выиграть не меняя изначального выбора: 0.33347

Лично я провел замечательные несколько часов, вспоминая всю эту тему условных вероятностей. А вы?

Ведение блога на Google Code

Лично я пока не дозрел до ведения блога на собственном сайте. Конечно, собственный сайт - это удобно. Все можно поменять и сделать как хочется. Но это и обязанность - настраивать, обновлять версии, присматривать и т.д. Все это реально, но пока не для меня. Я как-то больше радею за контент, нежели за оформление.

Теперь ближе к делу. Blogspot как механизм для ведения блога меня вполне устраивает. Единственное, чего не хватает - это возможности форматирования постов не в HTML или WYSIWYG редакторе, а на каком-нибудь диалекте Wiki. Мне много-то не надо, хотя бы базовые элементы.

Последнее время я как-то уж сблизился с Google Code. А там как раз есть Wiki для ведения документации. Вот и возникала мысль скрестить Blogspot и Google Code для ведения блога.

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

Я пришел вот к такой схеме. Для начала я завел одноименный проект на Google Code - Easy Coding.

Каждый пост пишется на Google Code в виде отдельной странички Wiki (лишний повод не писать двух-строчных одноразовых постов). Отлаживается верстка и общий внешний вид. Можно писать прямо в онлайне на страничке, но лично я изначально набиваю все в notepad++ и aspell. Благо разметка Wiki не требует ежеминутного закольцованного ерзанья типа исправил-посмотрел-как-выглядит, как в HTML.

Если надо повесить картинку, то она выкладывается в раздел Downloads, и ссылка на картинку ведет туда. Исходники тоже можно было бы заливать в этот раздел, есть есть способ лучше. Исходники удобнее держать в разделе Source. Там их можно удобно просматривать, скачивать, комментировать и т.д. И тут уже можно насладиться контролем версий для них (еще раз уточню - когда выкладываешь работающие исходники, это становится важно) - Subversion или Mercurial, кому что больше нравится. Кстати, раздел Wiki тоже под контролем версий.

Я использую Mercurial, так как распределенная модель позволяет работать долго локально, а потом одним махом отправить изменения на сервер. Получается, что Mercurial в данном случае - это как файловый клиент для обмена файлами с Google Code.

Итак, пост закончен и отлажен. Теперь его надо выложить на Blogspot.

Для этого я написал элементарный скрипт на php. Данный скрипт преобразует пост из формата .wiki в .html с ориентацией на особенности шаблонов и стилей конкретно Blogspot'а. Он, конечно, не идеален, но я решил так - я не буду делать универсального монстра, а буду править его по мере возникновения проблем или требования новых возможностей.

Так так теперь у меня всегда локально лежат посты в виде .wiki файлов, то если мне надо исправить пост - сначала я вношу изменения в .wiki, затем конвертирую .wiki снова в .html и выкладываю через онлайновый редактор Blogspot'а. Это позволяет всегда иметь посты в нормальной .wiki разметке и не думать, как их корежит онлайновый редактор Blogspot'а.

Соглашусь, многое из сказанного странно для владельцев собственных автономных блогов, но вот для клиентов Blogspot'а подобная методика весьма жизненна.

В качестве первого блина предыдущий пост про функторы был написан по этой методике. Пока я доволен.

Посты по теме:

• Кто быстрее: функтор или указатель на функцию
• Хостинг на Google Code: SerialCom

Кто быстрее: функтор или указатель на функцию

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

functor.cpp:

#include "gtest/gtest.h"

#include <algorithm>

typedef double Type;

Type* array;
const int N = 100000000;

inline bool less(Type a1, Type a2) {
  return a1 < a2;
}

class Less {
 public:
  inline bool operator()(Type a1, Type a2) {
    return a1 < a2;
  }
};

// Использование встроенной функции сравнения.
TEST(Callback, BuiltIn) {
  std::sort(array, array + N);
}

// Использование свободной функции сравнения по указателю.
TEST(Callback, Function) {
  std::sort(array, array + N, less);
}

// Использование функтора.
TEST(Callback, Functor) {
  std::sort(array, array + N, Less());
}

int main(int argc, char* argv[]) {
  // Создаем отсортированный массив.
  array = new Type[N];
  Type* p = array;
  for (int i = 0; i < N; ++i) *p++ = i;

  testing::InitGoogleTest(&argc, argv);
  // Принудительно печатаем время работы тестов.
  testing::GTEST_FLAG(print_time) = true;
  return RUN_ALL_TESTS();
}

Компилируем и запускаем (Visual Studio 2008):

cl /O2 /arch:SSE2 /EHsc /I. functor.cpp gtest\gtest-all.cc && functor

Результат:

[==========] Running 3 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 3 tests from Callback
[ RUN      ] Callback.BuiltIn
[       OK ] Callback.BuiltIn (9547 ms)
[ RUN      ] Callback.Function
[       OK ] Callback.Function (24391 ms)
[ RUN      ] Callback.Functor
[       OK ] Callback.Functor (9578 ms)
[----------] 3 tests from Callback (43547 ms total)

[----------] Global test environment tear-down
[==========] 3 tests from 1 test case ran. (43547 ms total)
[  PASSED  ] 3 tests.

Видно, что скорость функтора (9578 мс) практически равна встроенной функции (9547 мс) сравнения. А вот вызов свободной функции конкретно отстает (24391 мс), приблизительно в 2.5 раза.

Такое поведение можно объяснить тем, что в данном случае при вызове обычной функции компилятор не может оптимизировать такой вызов встраиванием (inlining). Вне зависимости от того, что функция объявлена выстраиваемой, так как ее вызов производится по указателю, компилятор не может сделать предположений о значении этого указателя на стадии исполнения, а значит провести оптимизацию.

При использовании же функтора компилятору доступна информация о семантике вызываемого кода, поэтому все типы оптимизации возможны. Отсюда и скорость, близкая к встроенной функции сравнения.

Как вариант, при замене типа с double на int и при условии, что опция /arch:SSE2 включена, тест с функтором работал даже быстрее встроенной функции.

Вывод

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

Все необходимые файлы для компиляции примеров из этого поста можно посмотреть и скачать на сайте проекта Easy Сoding в соответствующем разделе.

---

Данный пост является экспериментом по использованию Google Code в качестве хостинга для размещения исходных текстов примеров и самих статей.

Головная страница проекта - http://code.google.com/p/easy-coding/.

Каждый пост будет по необходимости размещаться в отдельном каталоге и отдельной страницей Wiki.

Дизассемблер как метод уменьшения размера обновлений

Интересующихся попытками сделать жизнь лучше, рекомендую к прочтению интересный документ от инженеров Google на тему минимизации размеров обновлений для браузера Chrome.

Google очень радеет за безопасность своих продуктов. Например, для браузера Chrome - это значит регулярные обновления. А кому охота каждый день качать по десять мегов, даже если там весьма критическое обновление. Поэтому разработчики Chrome делают все, чтобы сократить размер пересылаемых по сети данных.

Применение bsdiff частичное решает проблему, и уже не надо тупо слать архив целиком.

Но теперь к самому интересному. Что происходит, когда найден досадный баг и сделано исправление, например:

Было:

...
if (packet_size < 1024) ...
...

а стало:

...
if (packet_size > 10 && packet_size < 1024) ...
...

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

Что делать? А что, если в обновлении посылать модуль не в двоичном виде, а в виде исходного текста? Тогда изменение (diff) будет совсем небольшое.

Конечно, посылать нормальный исходный текст и компилировать его на стороне клиента пока несколько затруднительно. Не у всех установлена Visual Studio.

Инженеры Google придумали технологию Courgette. Суть ее в том, что посылаются изменения на уровне не оригинального исходного текста, а на уровне ассемблера. Для формирования обновления скомпилированный исполняемый файл дизассемблируется. Тоже самое делается для предыдущей версии файла. Затем производится поиск изменений в текстовом виде (например, тем же стандартным diff'ом). И этот текстовый файл и является, собственно, обновлением. Затем он пересылается пользователю. На стороне пользователя текущий исполняемый файл тоже дизассемблируется, изменяется на основе принятого файла изменений (diff'а) и снова ассемблируется.

Старая схема с bsdiff'ом работала так:

  сервер:
    изменения = bsdiff(оригинал, обновление)
    передать изменения

  клиент:
    принять изменения
    обновление = bspatch(оригинал, изменения)

Теперь это работает так:

  сервер:
    ассемблер_оригинал = дизассемблировать(оригинал)
    ассемблер_обновление = дизассемблировать(обновление)
    ассемблер_обновление_кор = коррекция(ассемблер_обновление, ассемблер_оригинал)
    ассемблер_изменения = bsdiff(ассемблер_оригинал, ассемблер_обновление_кор)
    передать ассемблер_изменения

  клиент:
    принять ассемблер_изменения
    ассемблер_оригинал = дизассемблировать(оригинал)
    ассемблер_обновление_кор = bspatch(ассемблер_оригинал, ассемблер_изменения)
    обновление = ассемблировать(ассемблер_обновление_кор)

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

А вот и результаты на примере единичного обновления Chrome'а:

Метод	Размер обновления
Полное обновление	10,385,920
Обновление bsdiff'ом	704,512
Courgette метод	78,848

Неплохо, да?

Вот такой вот хитрый план у разработчиков Chrome. Обещают рассказать особенности реализации, как только все будет готово.

Данный пост является вольным переводом статьи, ссылка на которую дана в начале. Уж больно меня зацепила эта тема.

Руководство для начинающих по Google Test

Выложил на Google Code свой перевод руководства для начинающих по Google Test.

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

На отдельной странице будет общий список ресурсов о Google Test на русском языке. Очень пришелся кстати мой недавний пост о новшествах версии 1.3.0.

В планах перевод остальных документов.

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

Я последнее время увлекся различными механизмами верстки при помощитекстовых языков разметки. И я не про HTML. Я говорю о таких вещах, как простые Wiki-диалекты, и заканчивая целым миром верстки под названием TeX. Периодически покуриваю на ночь документацию с http://www.ccas.ru/voron/latex.html. Начал я с совершенно дивного коротенького справочника, где сухо и сжато перечислены базовые элементы языка верстки LaTeX c примерами.

Например, моя любимая задача линейного программирования:



будет записываться так:

\[
\max_{n\in R}\sum_{j=1}^n
c_jx_j
;\; 
\sum_{j=1}^n a_{ij}x_j\leqslant b_i, (i=1,\;2,\;\ldots,\;m)
\]

Если вы хотите в онлайне проиграться с набором формул в LaTeX, то рекомендую заглянуть сюда. Там, правда, не поддерживаются русские буквы в теле LaTeX команд, но для экспериментов это не проблема.

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

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

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

Вобщем, набивая перевод документации по Google Test, я просто отдыхал душой и попискивал от удовольствия, так как все происходило в Wiki-разметке в разделе документации проекта на Google Code.

Мечта - очень хотелось бы, чтобы когда-нидудь Blogspot реализовал бы альтернативный ввод постов с использованием Wiki-разметки, а не HTML. Хотя бы также, как это работает на Google Code. Ну а если еще и контроль версий будет, тогда вообще бесконечное счастье наступит.

Так если разобраться, единственная причина, почему нельзя вести блог прямо на Google Code в разделе Wiki - там нет трансляции постов в виде временной ленты. Если бы можно было в теле постов Блогспота на лету импортировать тест из документов Wiki c Google Code, то можно было бы удобно писать посты с применением Wiki-разметки и контролем версий, а отображать их в блоге.

Я, например, редко пишу в блог посты на 2-3 строчки. Обычно это крополивая работа по набивке, верстке, подгонке картинок, общего вида и т.д. И каждый пост это по сути законченный документ, к которому иногда возвращаешься, что-то исправляешь, добавляешь и т.д. И тут все прелести удобной итеративной работы с текстом выходят на первый план.


Посты по теме:

• Обзор новшеств Google Test 1.3.0

Google C++ coding stantard прямо в Visual Studio

Многие читали стандарт кодирования на С++ от Google.

Для себя я его давно использую, а на работе удалось продавить его фрагменты в наш внутренний стандарт.

В качестве приятного бонуса Google раздает задорную утилитку cpplint, для быстрой проверки исходника на С++ на соответствие правилам и для генерации отчета, понимаемого средой разработки (например, Visual Studio). Написана она на Питоне, так что для ее использования его надо установить.

Я прикрутил cpplint себе в Студию, чтобы можно было проверять исходники прямо в редакторе.

cpplint имеет несколько десятков checker'ов, их можно опционально отключать. Я отключил только три:

• Проверку на использование #include без указания относительного пути, например #include "one.h" вместо #include "path/to/lib/one.h". Правило очень разумное, так как исключает перехлест заголовочных файлов с одинаковыми именами в разных подсистемах, но у меня уж больно много, где надо менять.
• Проверку на формирование имени защитного #define'а в начале заголовочного файла. У меня свое правило именования, и оно меня устраивает.
• Проверку на неиспользование потоков в STL. Я потоки использую, поэтому отключил.

Итак, получился скрипт cpplint.cmd:

C:\Python25\python.exe %~d0%~p0cpplint.py ^
  --filter=-build/include,-build/header_guard,-readability/streams ^
  --output=vs7 %1 %2 %3 %4 %5 %6 %7 %8 %9

Можно его из командной строки вызывать, но из Студии интереснее.

Итак, Menu->Tools->External Tool..., жмем Add и далее как на картинке (пути подправить по вкусу):



Теперь, прямо в редакторе жмем ALT-T,C,ENTER и снизу окне результатов получаем отчет. Кликая на его строки можно скакать по исходнику.

Лично я считаю, что порядок в исходниках напрямую связан с порядком в голове его автора.

Google Chrome OS

Удивительное дело, как Google умудряется без предварительного шапкозакидательства в стиле Microsoft делать удивительно грандиозные вещи: Chrome, Android, Native Client, а теперь еще и Google Chrome OS.

Обычно я не комментирую новости, но тут не мог стерпеть.

Static assert

А какой у вас используется assert времени компиляции, если не использовать boost/static_assert.hpp?

У меня вот такой:

template <bool> struct STATIC_ASSERTION_FAILURE;
template <> struct STATIC_ASSERTION_FAILURE<true> {};
#define STATIC_CHECK(x) sizeof(STATIC_ASSERTION_FAILURE< (bool)(x) >)

Работает приемлемо сносно:

int main() {
  STATIC_CHECK(sizeof(int) < sizeof(char));
  return 0;
}

Фундаментальные алгоритмы

После того, как я жестко облажался с самопальной сортировкой, причем облажался дважды: первый раз, когда думал, что порву по скорости STL'ный std::sort(), а второй - когда не понял, что все эти "ухищрения", как я думал, по ускорению QuickSort'а, реализованные в STL'е Visual Studio, есть ни что иное, как просто давно придуманный IntroSort.

В общем, я взял в руки:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка.



и начал освежать (а местами просто узнавать с нуля) когда-то читанное в студенчестве.

Втянулся.

Заказал вторую книгу:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах



Последние несколько лет я всегда делал основной упор на новые языки, операционные системы, организацию процесса разработки, работу над качеством и т.д. Получилось, что база как-то слегка подкосилась.

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

Обертка генератора парсеров грамматик Lemon для C++

Выложил на Google Code прототип библиотеки для удобного использования генератора LALR парсеров грамматик Lemon на С++.

Проект называется lemonbind.

Lemon - это создающий исходник на C/C++ генератор, похожий на yacc или bison, для реализации заданой грамматики. Lemon был создан автором SQLite для разбора SQL'я.

Есть у Lemon несколько радикальных отличий от собратьев. В отличие от yacc/bison Lemon не использует обратные вызовы, то есть не парсер вызывает нас, когда готов принять очередной токен, а мы вызываем парсер, когда готовы скормить ему очередной токен. Также Lemon безопасен в потоковом плане и реентабелен. Именно эти отличия позволяют неплохо завернуть его в обертку C++ со всеми вытекающими радостями. Также Lemon использует более простую нотацию по именованию параметров в продукциях грамматики, значительно снижающую вероятность опечататься.

Lemon представляет собой всего для файла: lemon.c и lempar.c. Первый - это, собственно, генератор грамматик. Компилируется практически любым компилятором C/C++. Второй - шаблон, который использует генератор для создания целевого файла-парсера на языке С. Сгенерированный парсер также прекрасно компилируется любым компилятором C/C++.

Конечно, Lemon'у нужен лексический анализатор. Я использовал flex. Его тоже пришлось обернуть в С++.

Возникает вопрос - а для чего этот велосипед, когда есть ANTLR, Boost Spirit и прочие навороченные инструменты. Ответ как всегда прост - простота и скорость. Парадоксальная ситуация - подход с генерацией исходника, реализующего требуемую грамматику, был придуман много лет назад и воплощен в виде старичков типа lex/yacc/bison, а до сих пор используется за неимением простых и быстрых альтернатив, работающих на сложных грамматиках и на больших объемах анализируемого текста.

Собственно, моя мини библиотека на данный момент имеет три основных класса: Token, Tokenizer (обертка flex) и Parser (обертка Lemon). Набор тестов демонстрирует, как работать с этими классами. Тест Parser.NestedSelect разбирает вложенный SELECT тривиального диалекта SQL и строит дерево разбора.

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

P.S. Нашел дружественный проект по адаптированию Lemon'а для генерации парсеров не только на C и C++, но и на D.

P.P.S. Настоятельно рекомендую по теме вот эту книгу в заслуженной форме большего кирпича.

Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман
Компиляторы. Принципы, технологии и инструментарий



Осилил пока разделы про лексический и семантический анализ. Чисто из любопытства робко заглядывал в главы про генерацию кода и его оптимизацию. Там настоящая жесть.

Скрипты для архивации проектов под Windows

Архивировать папку с проектом очень удобно и полезно. Для себя я давно выбрал следующий формат имен архивов: имя проекта + дата и время с точностью до секунды, например:

easy-coding-2009.07.06-10.27.12.rar

Долгое время я использовал вот такой скрипт backup.cmd:

rem Берем имя родительского каталога без полного пути.
for %%I in (.) do set CWD=%%~nI
rem Архивируем.
winrar a -v -r -s -ag-YYYY.MM.DD-HH.MM.SS -x*.rar -x*.7z %CWD%

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

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

В этоге родился скрипт backup-7z.cmd:

@echo off
setlocal
set line=%DATE%
rem Проходимся по строке вида DD/MM/YYYY и
rem превращаем ее в YYYY.MM.DD.
:parse_date
for /F "delims=/ tokens=1,*" %%a in ("%line%") do (
  set line=%%b
  set now=%%a.%now%
)
if "%line%" neq "" goto parse_date
rem Отрезаем хвостовую точку от даты.
set now=%now:~0,10%
rem Добавляем время. Оно уже в формате HH:MM:SS.ms. Отрезаем доли секунды.
set now=%now%-%TIME:~0,8%
rem Заменяем двоеточие на точку
set now=%now::=.%
rem Берем имя родительского каталога без полного пути.
for %%I in (.) do set CWD=%%~nI
rem Архивируем.
7z a -mx9 -r -x!*.rar -x!*.7z %CWD%-%now%.7z
endlocal

Это скрипт делает все как и раньше, но только для 7z.

Конечно, под UNIX'ом есть море путей сделать подобное, да и в Windows можно Cygwin использовать, но я всегда сначала пытаюсь сделать native решение, если это возможно.