Code @ C++

Как написать программу на C++ для Android.Часть 4: Без Java.

2012-01-16T05:00:00.000+04:00

Часть 1 | Часть 2 | Часть 3 | Часть 4

В этой части мы не будем писать на Java. Напишем программу под Android используя только C++. Это будет просто.
Читать дальше »

Remove trailing spaces

2011-12-26T11:22:00.000+04:00

Для того, что удалить пробелы в конце строк в файле можно воспользоваться стандартным диалогом Replace в Visual Studio:

В строку Find what нужно ввести :Zs#$, а Replace with оставить пустой. Не забудьте поставить галку Use Regular expressions. Далее можно нажать Replace All.

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

Первичное интервью или что вас ждет на собеседовании на вакансию программист С++

2011-12-20T00:29:00.000+04:00

Набралось информации о том, как проходит первичное интервью на вакансию C++ разработчика в тех или иных компаниях. Читать дальше »

Как написать программу на C++ для Android.Часть 3: Используем С++ класс и STL

2011-11-09T07:00:00.000+04:00

Часть 1 | Часть 2 | Часть 3 | Часть 4

В предыдущей части мы убедились, что из Java программы можно довольно просто вызывать C++ функции. В этой статье рассмотрим более сложный пример с C++ классами. На C++ будем считать статистику по картинке получаемой со встроенной видеокамеры устройства (насколько я знаю, все Android устройства имеют хотя бы одну видеокамеру).
Читать дальше »

Многопроцессорный HAL в Windows

2011-11-01T13:43:00.000+04:00

Работая с виртуалками постоянно забываю что-то настроить важное в VirtualBox и ставлю систему с дефолтными настройками, т.е. процессор в виртуальной машине имеет только одно ядро. Потом, даже если поставить больше ядер у процессора, Windows XP и Vista не увидят их, т.к. используют однопроцессорный HAL. Проблему можно решить с помощью утилиты devcon. В командной строке набираем:

devcon sethwid @ROOT\ACPI_HAL\0000 := +acpiapic_mp !acpiapic_up
devcon update c:\windows\inf\hal.inf acpiapic_mp

После перезагрузки Windows начинает видеть много ядер.

Наводнение в Тайланде

2011-10-31T14:31:00.000+04:00

Вчера SMART отрапортовал, что мой Seagate на 1.5 Gb стремительно умирает и нужно срочно забэкапить данные. «Не проблема», подумал я и пошел смотреть где купить новый HDD. Поискав аналог на 1.5—2 Gb я был сильно удивлен ценами на жесткие диски. Экземпляры, которые стоили около 4000 руб., стали стоить около 8000 руб. Поиск по новостям выявил, что скачущий валютный курс вовсе не причем. Оказалось, что 25% мировых производственных мощностей заблокированы наводнением в Тайланде, где расположены заводы основных производителей (пруфлинк).

Новости не очень радостные в том плане, что цены уже выросли и ещё в том, что и дальше будут расти. Для читателей эта новость означает, что 3-я часть цикла статей про Android задерживается до покупки нового HDD и восстановления системы. Надеюсь, что на это уйдет не больше недели.

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

Как написать программу на C++ для Android.Часть 2: Используем простейшую С++ функцию.

2011-10-20T07:00:00.006+04:00

Часть 1 | Часть 2 | Часть 3 | Часть 4

В предыдущей части я рассказал как настроить окружение для разработки программ на C++ под Android. В этой части попробуем создать простейший проект с примитивным C++ кодом.

Читать дальше »

Как написать программу на C++ для Android.Часть 1: настраиваем среду разработки.

2011-10-15T19:50:00.005+04:00

Часть 1 | Часть 2 | Часть 3 | Часть 4

Google Developers Day, который я анонсировал, завершился. Несмотря на то, что доклады оставляли желать лучшего (в отличии от прошлого года), на Android секции было столько народу, что приходилось сидеть в проходах. Это говорит о том, что существует немалый интерес к этой теме. Видео с докладами обещали выложить на YouTube.

Все это совпало с выходом Ubuntu 11.10, которую хотелось посмотреть. Итогом стала идея напистать несколько статей на тему разработки на C++ под Android. В этой части, надеюсь, не последней, я опишу как с нуля настроить окружение для разработки. Итак, устанавливаем Ubuntu 11.10:

Читать дальше »

Как купить новый стандарт C++

2011-10-11T18:27:00.000+04:00

Уже много кто написал, что вышел долгожданный стандарт C++. Почему-то часто упоминается, что его можно купить за 18$. Это неправда. Новый стандарт ISO/IEC 14882:2011 можно купить на сайте ISO за 352 швейцарских франка (примерно 387 долларов США).

Что касается $18, которые везде упоминаются, то Саттер у себя в блоге написал, что ANSI опубликовала старый стандарт и продает его за эти деньги (на самом деле, можно убедиться, что сайте ANSI указана цена $30). Новый стандарт ANSI уже продает за $403.

Удачных покупок!

Windows 8 работает на процессорах ARM

2011-10-06T00:01:00.003+04:00

Windows 8 In Action on upcoming Tegra "Kal-El" Processor

Куда пойти осенью в Москве

2011-09-26T22:19:00.000+04:00

На этой неделе Microsoft приглашает на очередной Microsoft Innovation Day. Зарегистрироваться можно по ссылке. Надеюсь там услышать из первых рук небольшой into для Windows 8 и Visual Studio 11, которые уже доступны для скачивания на портале MSDN. Также интересно послушать про новинки в SQL Server 11 "Denali".

Google также организует традиционный Google Developer Day в Москве 10 октября. Регистрация кажется ещё идет. Тут рассчитываю услышать про TV от Google и как планируется двигать Android в сторону устройств с HD экранами.

XML Schema в SQL Server

2011-09-05T23:16:00.004+04:00

Я уже как-то писал про то, что в SQL можно читать элементы XML прямо из столбца с соответствующим типом. Для того, чтобы SQL сервер контролировал правильность этого поля, используется специальный язык описания правил — XML Schema. Рассмотрим простейший пример такой схемы (сегодня все примеры для Microsoft SQL Server 2008):

<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

    <xsd:complexType name="PointType">
     <xsd:attribute name="X" type="xsd:int" />
     <xsd:attribute name="Y" type="xsd:int" />
     <xsd:attribute name="Z" type="xsd:int" use="optional" />
    </xsd:complexType>

    <xsd:element name="Point" type="PointType" />
</xsd:schema>

Данная схема разрешает только XML следующих видов:

<Point X="100" Y="100" />
<!-- или -->
<Point X="100" Y="100" Z="500"/>

При этом аттрибуты X и Y являются обязательными, а Z — опциональным. Для аттрибутов допускается только тип int. В MS SQL Server создание подобной схемы будет выглядеть так:

CREATE XML SCHEMA COLLECTION test AS '
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

    <xsd:complexType name="PointType">
     <xsd:attribute name="X" type="xsd:int" />
     <xsd:attribute name="Y" type="xsd:int" />
     <xsd:attribute name="Z" type="xsd:int" use="optional" />
    </xsd:complexType>

    <xsd:element name="Point" type="PointType" />
</xsd:schema>
'
GO

Далее можно попробовать создать xml с данной схемой (ниже используется переменная для того, чтобы этот код можно было легко скопировать и попробовать, но тоже самое верно и для столбца в таблице):

-- объявляем переменную @xml с ранее созданной схемой test
DECLARE @xml xml(test)

-- заполняем тестовыми данными
SET @xml='<Point X="10" Y="10" />'

-- делаем выборку
SELECT @xml.value('(/Point/@X)[1]','int'), @xml.value('(/Point/@Y)[1]','int')

При попытке записать невалидные данные SQL Server выдаст ошибку:

-- пробуем задать невалидный XML
SET @xml='<WrongPoint X="10" Y="10" />'

-- получаем ошибку
-- XML Validation: Declaration not found for element 'WrongPoint'. Location: /*:WrongPoint[1]

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

Ссылки:

Автоматический выбор типа

2011-08-15T22:56:00.006+04:00

В библиотеке Boost есть набор средств для выбора типов. Например, можно выбрать наименьший тип с не менее чем N бит:

typedef boost::int_t<N>::least my_int_t;

Или тип, который точно сможет уместить в себя все числа в диапазоне от 0 до V:

typedef boost::int_max_value_t<V>::last my_int_t;

Или ещё целый беззнаковый тип, который может работать с числами от 0 до V и, при этом, самый быстрый на данной платформе:

typedef boost::uint_value_t<V>::fast my_uint_t;

Полный список можно посмотреть в документации.

ЭЛВИС-НеоТек нанимает на работу

2011-08-12T18:30:00.002+04:00

Компания ЭЛВИС-НеоТек приглашает на работу разработчиков. Читать дальше »

ternary operator (?:)

2011-08-09T23:14:00.001+04:00

Интересный факт: тернарный оператор (?:) может стоять не только в правой части выражения, но и в левой. Пример:

    int a = 5; int b = 10;
    (a > b ? a : b) = 100; // большему из a и b присвоим 100
    cout << "a=" << a << " b=" << b << endl;

    // result will be: a=5 b=100

Безопасны ли безопасные функции в Windows?

2011-08-05T14:30:00.003+04:00

Visual C++ при компиляции ANSI функций работы со строками постоянно выдает предупреждение о том, что есть более безопасные версии и использовать нужно именно их. Однако, по набору параметров они могут вовсе не отличаться, что не позволяет заметить разницу на этапе компиляции. Например, имеем следующий код:

int main(int argc, char *argv[])
{
    const char* stLine = "s=Media Presentation\n";

    std::vector<char> param(1024);

    _snscanf( stLine, 20, "s=%[^\r\n]", &param[0] );

    return 0;
}

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

_snscanf_s( stLine, 20, "s=%[^\r\n]", &param[0] );

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

Если почитать документацию более внимательно, то находим следующее небольшое замечание:

The buffer size parameter is required with the type field characters c, C, s, S, and [. For more information, see scanf Type Field Characters.

Это означает, что теперь после каждого строкового параметра нужно передавать размер буфера, т. е. код должен выглядеть следующим образом:

_snscanf_s( stLine, 20, "s=%[^\r\n]", &param[0], param.size() );

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

Зачем в checked_delete столько кода?

2011-07-26T01:11:00.001+04:00

Если посмотреть на реализацию функции checked_delete в библиотеке Boost, то можно увидеть следующий код:

template<class T> inline void checked_delete(T * x)
{
    // intentionally complex - simplification causes regressions
    typedef char type_must_be_complete[ sizeof(T)? 1: -1 ];
    (void) sizeof(type_must_be_complete);
    delete x;
}

Для чего нужны такие сложности и почему упрощение приведет к регрессу? Дело вот в чем: чтобы корректно удалить объект, его тип должен быть полностью определен (complete type). Проверяется это в несколько этапов:

Вызов оператора sizeof для неопределенного типа приведет к ошибке компиляции.
На случай, если sizeof вернет 0 (в случает нестандартного расширения в компиляторе), создается массив с отрицательной длинной, что запрещено во всех компиляторах.
Вторая строка нужна для компилятора Metrowerks CodeWarrior, который не будет инстанцировать первый typedef, пока он не используется.
Преобразование результата sizeof к void нужно, чтобы избежать предупреждений во время компиляции.

Ссылки:

Разъяснения от автора checked_delete.

operator& (address-of)

2011-06-21T00:31:00.002+04:00

C++ позволяет переопределять в своих классах ряд операторов, и в их числе — оператор взятия адреса. Попробуем воспользоваться этой возможностью:

struct useless_type {};
class nonaddressable {
  useless_type operator&() const;
};

Пример класса, где переопределен operator& — это CComPtr.

Теперь, если попробовать взять адрес экземпляра класса nonaddressable, то получим ошибку:

nonaddressable* xpe = &x; /* error */

Ошибка может возникнуть по двум причинам: во-первых, в примере оператор взятия адреса приватный, во-вторых — он возвращает экземпляр useless_type, а вовсе не указатель на nonaddressable.

Для разрешения этой ситуации в C++ существует крайне кривой механизм. Можно написать следующий код:

nonaddressable* xp = 
  reinterpret_cast<nonaddressable*>( &reinterpret_cast<char&>( x ) );

Стандарт гарантирует, что это будет работать, но выглядит все равно ужасно. К счастью, в библиотеке Boost существует обертка над этим механизмом — функция boost::addressof, которая учитывает возможные const-volatile. Пользоваться просто:

nonaddressable* xp = boost::addressof(x);

Ошибка сети в Empathy

2011-06-16T23:36:00.001+04:00

С 10 июня Empathy, стандартный мессанджер в Ubuntu 11.04, начал выдавать сообщение Ошибка сети (или Network error в английской версии) при попытке подключения аккаунта ICQ. Странно, что поиск в Google выдает кучу решений, которые не работают в версии 11.04.

Проблема описана в баг-трэкере Empathy (ошибка №795932). Если то, что выдает поиск Google не помогает, то решается путем написания в консоли следующих команд:

user@home:~$ mc-tool list | grep icq

Выдается что-то типа haze/icq/_31102050910. То, что выдалось подставляем в следующие команды:

user@home:~$ mc-tool update haze/icq/_31102050910 string:encryption=no_encryption
user@home:~$ mc-tool update haze/icq/_31102050910 bool:use-clientlogin=0

Перезапускаем Empathy и все работает. Если нет, то отписываемся в баг-трэкере.

Partial template specialization for pointers to __stdcall functions

2011-05-23T23:54:00.001+04:00

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

template<typename F> class TFunction;

template<typename R, typename T0>
class TFunction<R(*)(T0)>
{
};

Здесь мы пытаемся специализировать шаблон TFunction для указателя на функцию одного аргумента. Далее имеем два указателя:

typedef bool (*my_function_f)(int);             // (1)
typedef bool (__stdcall *my_function_f2)(int);  // (2)

Для (1) специализация, которая написана выше вполне подходит, а вот для (2) — нет. По умолчанию, предполагается что функция использует соглашение вызова __cdecl. Если мы хотим передавать указатели на функции с соглашением вызова __stdcall, то необходимо для этого случая написать отдельную специализацию:

template<typename R, typename T0>
class TFunction<R(__stdcall *)(T0)>
{
};

Кажется, этого достаточно. Однако, при компиляции кода под x64 процессоры ключевое слово __stdcall, которое обозначает порядок вызова функций, игнорируется. Обычно это незаметно, но если вы пытаетесь написать частичную специализацию шаблона, то проявляются неприятные эффекты. А именно, две специализации, которые написаны выше, получаются абсолютно одинаковыми, что приводит к ошибке компиляции. Решением будет отключить компиляцию второй специализации, например, так:

#ifndef _M_X64
template<typename R, typename T0>
class TFunction<R(__stdcall *)(T0)>
{
};
#endif

Макрос _M_X64 предопределен для x64 процессоров.

Ссылки по теме:

Пап, что ты делаешь на работе

2011-05-18T08:52:00.004+04:00

Как объяснить маленькому ребенку (4-5 лет), что папа/мама на работе разрабатывают софт? У меня возникла только одна аналогия для этого возраста — папа пишет книжки на специальном волшебном языке для компьютеров... Ну да, компы их читают и делают то, что там написано. Волшебный язык, конечно, знают не все люди... Книжки бывают разные: в играх много картинок, а есть скучные книжки-программы — совсем без картинок. Кстати, при загрузке Ubuntu пишется сначала куча текста, а потом уже появляется красивый интерфейс (ага, комп дочитал до нужного места, в книжках тоже не сразу понятно где находятся герои), что подтверждает аллегорию.

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

А у вас возникала необходимость объяснить чем вы занимаетесь?

sum of pairs

2011-05-13T23:19:00.002+04:00

Вы когда нибудь пробовали получить сумму элементов контейнера, который хранит элементы типа std::pair? Если да, то вы заметили, что std::pair не определяет operator+. На помощь приходит новый стандарт, в котором пишем лямбда-функцию, или библиотека boost::lambda с которой получаем следующий прекрасный но сложноперевариваемый код:

#include <deque>

#include <boost/lambda/bind.hpp>
#include <boost/lambda/construct.hpp>

template<typename T>
void summarize()
{
    typedef std::pair<T, T> pt_t;
    std::deque<pt_t> xs;
    using namespace boost::lambda;

    // fill xs with stuff

    pt_t res = std::accumulate(
        xs.begin(), xs.end(), std::make_pair(T(),T()),
        bind( constructor<pt_t>(),
             bind( std::plus<T>(), bind(&pt_t::first,_1), bind(&pt_t::first,_2) ),
             bind( std::plus<T>(), bind(&pt_t::second,_1), bind(&pt_t::second,_2) )
             )
         );

}

Find sum of elements in the array

2011-04-23T00:17:00.005+04:00

Наткнулся на задачу, которую предлагают в Yandex на собеседовании:

Ниже приведены три варианта суммирования чисел с плавающей точкой (предполагается, что числа в массиве только положительные).
double sum1(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}
<...>

Остальные варианты пока нам не интересны, их можно посмотреть тут (кстати, в последнем варианте бесконечный цикл). Зачем тут лишняя сортировка ясно сразу — предполагается, что точности double не хватит для расчетов. Ведь если суммировать числа от больших к меньшим, то сумма быстро растёт, и, когда мы дойдём до маленьких чисел, они могут быть денормализованы с огромной ошибкой.

Чтобы оценить о каком порядке ошибки идет речь посмотрим на следующий пример:

const double x = 0.01;
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    s = s + x;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;

На моей машине он выдает результат: 9.53674e-05

Итого, простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально $n$, и среднеквадратичную ошибку, которая растет как $\sqrt n$ на случайных данных.

Однако, хочется суммировать без ошибок и при этом делать это не за линейно-логарифмическое время $O(n\log n)$, а за линейное $O(n)$. Это нам позволяет алгоритм автора стандарта IEEE 754, Уильяма Мортона Кэхэна (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Предыдущий пример с учетом алгоритма Кэхэна:

const double x = 0.01;
double c = 0; // keep error here, initial error is zero
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    const double y = x - c;
    const double t = s + y;
    c = (t - s) - y; // Beware eagerly optimising compilers!
    s = t;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;

В итоге выдает 0.

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

Autocomplete

2011-04-11T23:17:00.002+04:00

На днях встал вопрос сделать функцию для подсказки завершения слов. Самый простой вариант — сравнивать введенную часть слова с первыми буквами слов из словаря и выдавать все слова, у которых совпадает начало. На маленьких словарях это работает, в целом, неплохо, но люди делают опечатки и хотелось бы предлагать исправленные варианты слов, т. е. нужно выдавать похожие слова. Про меру «похожести» последовательностей 0–1 ещё в 1965 году упомянул советский математик Владимир Иосифович Левенштейн, что позже дало имя расстоянию Левенштейна.

Расстояние Левенштейна — это минимальное количество операций вставки, замены и удаления одного символа, необходимых для превращения одной строки в другую.

Это уже почти то, что нужно, но в расстоянии Левенштейна перестановки не учитываются. На наше счастье товарищ Дамерау (Damerau) не только добавил к указанным операциями ещё одну — перестановку двух соседних символов, но и утверждал, что 80% ошибок при наборе текста дают как раз указанные четыре операции. Расстояние, которое учитывает эти операции назвали, как можно догадаться, расстоянием Дамерау–Левенштейна. Результаты этих работ теперь используются не только в бесполезных спеллчекерах, которые убивают грамотность, но и в исследованиях ДНК.

Мне же эти исследования пригодились для решения поставленной задачи. Ниже показана функция на C++, которая вычисляет расстояние Дамерау–Левенштейна:

int damerauLevenshteinDistance( const std::vector<char>& a, const std::vector<char>& b )
{
    const int a_size = static_cast<int>( a.size() );
    const int b_size = static_cast<int>( b.size() );
    const int INF = a_size + b_size;
    std::vector<std::vector<int> > H( a.size()+2, std::vector<int>( b.size()+2 ) );
    H[0][0] = INF;
    for ( int i = 0; i <= a_size; ++i ) { H[i+1][1] = i; H[i+1][0] = INF; }
    for ( int j = 0; j <= b_size; ++j ) { H[1][j+1] = j; H[0][j+1] = INF; }
    
    const int alphabet_size = std::numeric_limits<char>::max();
    std::vector<char> DA( alphabet_size );
    for ( int d = 0; d < alphabet_size; ++d ) DA[d] = 0;
    for ( int i = 1; i <= a_size; ++i ) {
        size_t DB = 0;
        for ( int j = 1; j <= b_size; ++j ) {
            const int i1 = DA[ b[j-1] ];
            const int j1 = DB;
            const int d = (a[i-1]==b[j-1]) ? 0 : 1;
            if ( d == 0 ) DB = j;
            H[i+1][j+1] = std::min( 
                std::min(H[i][j]+d, H[i+1][j]+1), 
                std::min(H[i][j+1]+1, H[i1][j1] + (i-i1-1) + 1 + (j-j1-1) ) );
        }
        DA[ a[i-1] ] = i;
    }
    return H[a.size()+1][b.size()+1];
}

Тема последних дней — поиск Муаммара Каддафи. Расчет расстояния от этого слова (Gadaffi) до всех слов английского словаря размером 329380 слов занимает порядка 2 секунд на моем домашнем Core2Duo 2.13GHz, т. е. функция работает довольно быстро.

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

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

Стоит отметить, что автозавершение слов — это встроенная функция Windows и разработчикам предлагаются интерфейсы IAutoComplete и IACList, пользоваться которыми, на первый взгляд, оказалось не очень удобно и они реализуют самый простой вариант автозавершения, что тоже не подходит.

Ссылки по теме:

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

2011-03-29T23:21:00.000+04:00

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