Что скрывает O-нотация?

Для оценки времени работы алгоритмов принято использовать O-нотацию. Она задает верхнюю асимптотическую сложность алгоритма. То есть, она показывает как, при прочих равных, изменяется время работы алгоритма при изменении размера входных данных. Например, если некоторый алгоритм имеет сложность O(n*n), то при увеличении размера входных данных в 3 раза, время его работы увеличится примерно в 9 (3*3) раз.

Ее же используют для сравнения эффективности алгоритмов. Так, если первый алгоритм имеет сложность O(n*n), а второй — O(n), то последний значительно быстрее первого. При увеличении размера входных данных в 3 раза, время работы первого алгоритма увеличится примерно в 9 раз, а второго — в три раза. Почему примерно?

Продолжить чтение →

Текстовый редактор для Git в среде Windows

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

Вообще грамотное составление коммитов и комментариев к ним — отдельная тема, которую мы не будем здесь обсуждать. Я хотел прежде всего сосредоточиться на инструментарии. Точнее поделиться своим личным опытом поиска оного в среде Windows. Продолжить чтение →

Две проблемы использования Git в Windows

Все знают, что Git изначально появился в Linux и только потом его портировали в Windows. Это наложило определенный отпечаток на его работу в «не родной» для себя среде. Сегодня я опишу две проблемы, с которыми я столкнулся при использовании Git в среде Windows. Продолжить чтение →

Шпаргалка Windows API теперь доступна на Bitbucket

Вчера наконец-то разместил на Bitbucket (аналог GitHub) исходные файлы всех трёх томов своего проекта Шпаргалка Windows API. Зачем я это сделал? Причин несколько. Продолжить чтение →

Итераторы не защищают от переполнения

Итераторы были введены в С++ в качестве основного механизма доступа к элементам контейнера. Они должны обеспечивать унифицированный объектно-ориентированный доступ к элементам. Но насколько он безопасен? То есть, защищают ли итераторы от индексного переполнения? Давайте проверим. Продолжить чтение →

std::vector при нехватке памяти

Контейнер std::vector представляет собой динамический массив, автоматически увеличивающийся в размере по мере надобности. Он описан в любом приличном руководстве по С++. Там же описываются его методы, достоинства и недостатки по сравнению с другими контейнерами.

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

GCC требует открытого конструктора копирования для C++98

В одной из своих прошлых статей я рассказывал, что при возврате объектов GCC не использует конструктор копирования, сразу размещая объекты там, где они должны располагаться. Однако, в некоторых случаях GCC требует наличия открытого конструктора копирования. Продолжить чтение →

Wine неправильно обрабатывает исключения в 64-битных приложениях

Wine — популярная программа для запуска Windows приложений в среде Linux. Как оказалось в ней содержится серьезная ошибка, не позволяющая полноценно использовать 64-битные приложения. Продолжить чтение →

Не используйте std::move при возврате объектов

Конструкторы и операторы перемещения являются важным нововведением С++11. Про них много написано, и я не стану повторять основы. Вместо этого я хотел бы сосредоточиться на таком вопросе, как возвращение объектов. Нужно ли для этого использовать функцию std::move или нет? Продолжить чтение →

GLib не обеспечивает размер типа guint64

В одном из своих прошлых постов я рассказывал, как компилировать приложения, использующую библиотеку GTK. Однако, как оказалось, входящая в ее состав библиотека GLib имеет одну неприятную особенность. Продолжить чтение →