Самая маленькая программа на C/C++, которая вызывает segmentation fault

Самый маленький код, который после компиляции с помощью gcc вызывает segmentation fault:

main;

Компилируем:

$ gcc crash.c
crash.c:1: warning: data definition has no type or storage class

Запускаем:

$ ./a.out
Segmentation fault

Увидел не так давно на хабре, делюсь.

Вопросы программисту C/C++ на собеседовании с ответами

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

  • В какую сторону надо крутить руль, чтоб повернуть направо?
  • За что отвечает педаль сцепления/тормоза/газа?

Такое конечно случается далеко не всегда, но первые пару вопросов обычно такого рода («А какую надо давить педаль, чтоб автомобиль остановился?»). Публикую свои ответы на некоторые вопросы для программистов. Вдруг кому пригодится.. Возможно, здесь много ошибок и помарок — при составлении этого списка я не пользовался интернетом. Старался выдать, что знаю сам.

Как можно оптимизировать данный цикл?

void func(int *array, int len)
{
    for (int i = 0; i < len; i++)
    {
        array[i] = array[i] * array[i];
    }
}

Вот таким образом:

void func(int *array, int len)
{
    const int *end = array + len;
 
    while (array != end)
    {
        const int value = *array;
        *array++ = value * value;
    }
}

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

В чем отличие std::list<T> от std::vector<T>?

std::vector<T> — это обертка над обычным С/C++ массивом. Соответственно:

  • если std::vector<T> заполнен, то при добавлении нового элемента, массив удаляется целиком и создается заново с бОльшим размером
  • любой элемент массива можно получить моментально, потому что позиция элемента вычисляется банальным прибавлением индекса к первому элементу (array[i] = array + i)
  • удаление любого элемента из массива, кроме последнего, приведет к перемещению всех элементов справа от удаляемого на одну позицию влево (при соблюдении некоторых условий, можно воспользоваться хаком)
  • занимает неразрывный блок памяти

std::list<T> — это список элементов, которые связаны между собой указателями prev (предыдущий элемент) и next (следующий элемент). Внутри себя std::list<T> хранит указатель на первый элемент и последний (зависит от реализации). Исходя из этого:

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

В языке Java различия между ArrayList и LinkedList практически такие же.

Почему в C++ нужно использовать new вместо теплого лампового malloc()?

Потому что malloc() тупо выделяет блок памяти и возвращает этот блок программисту. А new выделяет память и вызывает конструктор объекта. Тоже самое относится к delete и free(). delete вызывает деструктор и освобождает память. free() просто освобождает память. Также есть размещающий new, который создает объект в уже выделенной вами памяти.

Кстати, изначально конструкторы и деструкторы классов в C++ назывались new и delete и выглядели вот так:

class SomeClass
{
    // Конструктор
    void new();
 
    // Деструктор
    void delete()
};

В чем отличие между new/delete и new[]/delete[]?

new выделяет память для одного элемента и вызывает конструктор для него, в то время как new[] выделяет память для массива элементов и вызывает конструктор для каждого из них. delete должен вызываться для объекта выделенного с помощью new, а delete[] для массива, выделенного с помощью new[]. От проблем соответствия new/delete вас могут избавить классы std::auto_ptr<T> (для одного элемента) и std::tr1::scoped_array<T> (для массива элементов). Которые сами вызывают правильный delete в деструкторе.

Для чего нужен тип std::auto_ptr<T>?

В стародавние времена вы должны были сами следить за тем, чтоб после каждого new был вызван свой delete. Это было жутко неудобно (программисты Си выкручиваются из этой ситуации вставляя goto):

bool func()
{
    Stream *stream = new Stream;
 
    if (0 != stream->open("some stream"))
    {
        delete stream;
        return false;
    }
 
    if (0 != stream->load())
    {
        delete stream;
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
    delete stream;
    return true;
}

После появление std::auto_ptr<T> стало возможным переписать функцию таким образом:

bool func()
{
    std::auto_ptr<Stream> stream(new Stream);
 
    if (0 != stream->open("some stream"))
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    if (0 != stream->load())
    {
        // Здесь "delete stream" вызывается автоматически
        return false;
    }
 
    // Выполняем полезную работу
    // Закончили полезную работу
 
    // Здесь "delete stream" вызывается автоматически
    return true;
}

И еще очень важный момент: std::auto_ptr<T> владеет объектом единолично. Вы не сможете шарить объект между двумя std::auto_ptr<T> (используйте в таких случаях std::shared_ptr<T>):

void func() 
{
    Object *object = new Object;
 
    std::auto_ptr<Object> ptr1(object); // object теперь живет внутри ptr1
    std::auto_ptr<Object> ptr2(ptr1); // ptr1 опустел, object внутри ptr2
 
    // здесь деструктор ptr2 удалит object
    // а здесь вызовется деструктор ptr1 впустую
}

И помните: std::auto_ptr<T> не подходит для массивов выделенных с помощью new[]. Для этих целей используйте std::tr1::scoped_array<T> или boost::scoped_array<T>.

Что такое RAII?

Это переводится как «Получение ресурса есть инициализация». Идея вкратце такая: в конструкторе открываем/блокируем ресурс, в деструкторе закрываем/освобождаем ресурс. Вот пример:

class FILEWrap
{
public:
    FILEWrap( const char *fileName )
        : f_(fopen(fileName, "rb"))
    {
    }
 
    ~FILEWrap()
    {
        if (f_)
        {
            fclose(f_);
        }
    }
 
private:
    FILE *f_;
};

Или более каноничный пример (блокирование мьютекса или критической секции):

class MutexLock
{
public:
    MutexLock(Mutex &mutex)
        : mutex_(mutex)
    {
        mutex.lock();
    }
 
    ~MutexLock()
    {
        mutex.unlock();
    }
 
private:
    Mutex &mutex_;
};

Зачем нужен виртуальный деструктор?

Попробуем обойтись без него:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Вывод:

construct A
construct B
destruct A

Как можно заметить деструктор B не вызвался. Сделаем деструктор класса A виртуальным и посмотрим что получится:

#include <stdio.h>
 
class A
{
public:
    A() 
    { 
        printf("construct A\n"); 
    }
 
    virtual ~A() 
    { 
        printf("destruct A\n"); 
    }
};
 
 
class B : public A
{
public:
    B() 
    { 
        printf("construct B\n"); 
    }
 
    ~B() 
    { 
        printf("destruct B\n"); 
    }
};
 
 
int main()
{
    B *b = new B;
    A *a = b;
    delete a;
}

Теперь все отлично:

construct A
construct B
destruct B
destruct A

В каком порядке инициализируются члены класса?

Члены класса создаются в порядке их объявления в классе. Уничтожаются они в обратном порядке. Давайте проверим:

#include <stdio.h>
 
class Printer
{
public:
    Printer( const char *n ) 
        : n_(n)
    {
        printf("+%s ", n_);
    }
 
    ~Printer() 
    {
        printf("-%s ", n_);
    }
 
private:
    const char *n_;
};
 
 
class A : public Printer
{   
public:
    A() 
        : Printer("A") 
    {
    }
};
 
 
class B : public Printer
{
public:
    B() 
        : Printer("B") 
    {
    }
};
 
 
class C : public Printer
{
public:
    C() 
        : Printer("C") 
    {
    }
};
 
 
class Test
{
private:
    A A_;
    B B_;
    C C_;
};
 
 
int main()
{
    Test test;
}

Запустим:

+A +B +C -C -B -A

Все правильно.

Порядок объявления очень важен, если один член класса во время инициализации использует данные другого члена. Кстати, компилятор gcc выдает warning (с флагом -Wall), если вы описали инициализацию членов класса в другом порядке. И это еще одна причина в пользу использования настройки компилятора «считать предупреждения ошибками» (в gcc это флаг -Werror).

Быстрый способ удаления элемента из массива типа std::vector (C/C++) или ArrayList (Java)

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

Вот простой код для демонстрации:

#include <vector>
#include <stdio.h>
 
template <class T>
void remove_item( std::vector<T> &v, int i )
{
    // Сохраняем последний элемент
    const T item = v.back();
    // Удаляем последний элемент из массива
    v.pop_back();
    // Вставляем сохраненный элемента вместо элемента с индексом i
    v[i] = item;
}
 
 
int main()
{
    std::vector<int> v;
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(14);
 
    printf("before:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
 
    remove_item(v, 1);
 
    printf("after:\n");
    for (int i = 0, count = v.size(); i < count; ++i)
    {
        printf("v[%d] = %d\n", i, v[i]);
    }
}

Вывод:

before:
v[0] = 10
v[1] = 11
v[2] = 12
v[3] = 13
v[4] = 14
after:
v[0] = 10
v[1] = 14
v[2] = 12
v[3] = 13

Обратите внимание, что в remove_item() происходит копирование последнего элемента. Так что если у вас что-то сложнее простых int, long, char или float, то этот код вам надо переписать.

Код для ArrayList (Java). Не проверял, но идея понятна:

public class ArrayListUtil {
    public static <T> void removeItem(ArrayList<T> v, int index) {
        T item = v.get(v.size() - 1);
        v.remove(v.size() - 1);
        v.set(index, item);
    }
 
    private ArrayListUtil {
    }
}

Советую вам использовать стандартные функции std::remove() и std::remove_if(), которые делают практически тоже самое и std::vector::erase(), подробнее можно ознакомиться по ссылке.

О библиотеке сжатия zlib

Сегодня я хочу рассказать о замечательной библиотеке zlib.

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

Впервые в жизни мне пришлось столкнуться с компрессией данных в игре «Петрович и все, все, все», которую мы делали в Trickster Games для Андрея Бильжо.

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

Петрович и инопланетянин

На этом скриншоте присутствуют: Петрович (два цвета), Инопланетянин aka «логотип Trickster Games» (2 цвета), фон (4 цвета). Каждое изображение может занимать от 256 килобайт до 4-х мегабайт (потому что DDS). Загрузка одного уровня, состоявшего из 50-200 таких изображений, занимала от 10 до 45 секунд. Разумеется, это нас в корне не устраивало.

После мозгового штурма на эту тему было найдено решение — использовать алгоритм RLE. Этот алгоритм позволяет очень эффективно сжимать длинную цепочку одинаковых бит, что наглядно показано в википедии: блок данных «AAAAAAAAAAAAAAABBBBBC» мы записываем вот так «15A5BC». Экономия, как говорится, налицо.

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

/* Сжимает данные из буфера src в dst.
 * src - входной буфер
 * srcSize - размер входного буфера в байтах
 * dst - выходной буфер
 * dstSize - перед вызовом должен быть установлен в размер буфера dst, 
 *     после вызова туда записывается реальное количество сжатых байт
 *
 * Функция возвращает true, если данные были сжаты успешно 
 * (это значит, что уровень сжатия меньше или равен единице)
 */
bool compressRLE( void *dst, int *dstSize, const void *src, int srcSize);
 
/* Расжимает данные из буфера src в dst.
 * src - входной буфер
 * srcSize - размер входного буфера в байтах
 * dst - выходной буфер
 * dstSize - перед вызовом должен быть установлен в размер буфера dst, 
 *     после вызова туда записывается реальное количество распакованных байт
 *
 * Функция возвращает true, если данные были расжаты успешно 
 */
bool uncompressRLE( void *dst, int *dstSize, const void *src, int dstSize);

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

..И тут мы плавно переходим к zlib.

Библиотека zlib используется практически везде, где есть CPU: мобильные телефоны, компьютеры, микроволновки, современные автомобили, телевизоры — список можно продолжать бесконечно. Кто знает, может она сейчас трудится на Марсе внутри ровера Curiosity, сжимая, передаваемые на Землю, данные.

Библиотека может сжимать блок данных или поток. Рассмотрим вкратце сжатие блока данных. Описание метода вот такое:

// Сжимает данные методом deflate из буфера src в dst
// dest - выходной буфер
// destLen - размер выходного буфера (после удачного сжатия 
//     сюда сохраняется размер сжатых данных)
// source - входной буфер
// sourceLen - размер входного буфера
// Возвращает Z_OK в случае удачи, записывает размер сжатых данных в destLen
ZEXTERN int ZEXPORT compress OF((Bytef *dest,   uLongf *destLen,
                                 const Bytef *source, uLong sourceLen));

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

#include <zlib.h>
#include <memory.h>
#include <stdio.h>
 
#define SRC_SIZE 512
#define DST_SIZE 512
 
int main()
{
    // Входной буфер размером SRC_SIZE
    unsigned char source[SRC_SIZE];
    // Тут мы будем хранить размер входного буфера 
    // (переменная просто для наглядности)
    const unsigned long sourceLen = SRC_SIZE;
    // Выходной буфер
    unsigned char dest[DST_SIZE];
    // Размер выходного буфера
    unsigned long destLen = DST_SIZE;
 
    // Будем сжимать буфер забитый нулями
    memset(source, 0, SRC_SIZE * sizeof(source[0]));
 
    if (Z_OK == compress(dest, &destLen, source, sourceLen))
    {
        // Все успешно
        printf("Compress ratio: %.2f\n", destLen/(float) sourceLen);
    }
    else
    {
        // Тут можете разобрать код ошибки и вывести более подробную информацию
        printf("Compress failed\n");
    }
 
    return 0;
}

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

Есть вопросы? Спрашивайте, не стесняйтесь.

P.S. Если вы дочитали досюда, рекомендую изучить libdeflate.

Тестовые задания для программистов. Издание исправленное и дополненное

Я просто оставлю это здесь.

[user@domain ~]# cc -Wall -Werror -pedantic Binary.c
BinaryPrint.c:6:5: error: C++ style comments are not allowed in ISO C90
BinaryPrint.c:6:5: error: (this will be reported only once per input file)
cc1: warnings being treated as errors
BinaryPrint.c: In function 'BinaryPrint':
BinaryPrint.c:13: warning: ISO C90 forbids mixed declarations and code

diff -r afee20b80dff BinaryPrint.c
--- a/BinaryPrint.c     Tue Feb 22 09:11:12 2011 +0300
+++ b/BinaryPrint.c     Tue Nov 15 18:51:10 2011 +0300
@@ -3,31 +3,31 @@
 
 void BinaryPrint( long n )
 {
-    // Частный случай - n равно нулю
+    unsigned long mask = 1 << (sizeof(n) * 8 - 1);
+
+    /* Пропускаем бесполезные нули слева */
+    int skipZero = 1;
+
+    /* Частный случай - n равно нулю */
     if (n == 0)
     {
         printf("0\n");
         return;
     }
 
-    unsigned long mask = 1 << (sizeof(n) * 8 - 1);
-
-    // Пропускаем бесполезные нули слева
-    int skipZero = 1;
-
     while (mask)
     {
-        // Определим текущий бит
+        /* Определим текущий бит */
         unsigned char c = (n & mask) ? 1 : 0;
 
-        // Отключим пропуск нулей в дальнейшем
+        /* Отключим пропуск нулей в дальнейшем */
         if (skipZero && c)
             skipZero = 0;
 
         if (!skipZero)
             printf("%d", c);
 
-        // Сдвинем маску на один бит вправо
+        /* Сдвинем маску на один бит вправо */
         mask >>= 1;
     }
     printf("\n");
[user@domain ~]# cc -Wall -Werror -pedantic RemoveDups.c
RemoveDups.c:8:5: error: C++ style comments are not allowed in ISO C90
RemoveDups.c:8:5: error: (this will be reported only once per input file)
cc1: warnings being treated as errors
RemoveDups.c: In function 'RemoveDups':
RemoveDups.c:16: warning: value computed is not used
RemoveDups.c:22: warning: value computed is not used
RemoveDups.c:24: warning: value computed is not used
diff -r afee20b80dff RemoveDups.c
--- a/RemoveDups.c      Tue Feb 22 09:11:12 2011 +0300
+++ b/RemoveDups.c      Tue Nov 15 18:56:00 2011 +0300
@@ -5,25 +5,25 @@
     const char * src = pStr;
     char * dst = pStr;
 
-    // Пока не дойдем до конца строки
+    /* Пока не дойдем до конца строки */
     while (*src)
     {
-        // Записываем в pStr текущий символ, если указатели разные
+        /* Записываем в pStr текущий символ, если указатели разные */
         if (dst != src)
             *dst = *src;
 
-        // Сдвигаем dst вправо
-        *dst++;
+        /* Сдвигаем dst вправо */
+        dst++;
 
-        // Пока не конец строки и следующий символ такой же
+        /* Пока не конец строки и следующий символ такой же */
         while ((*src + 1) && *(src + 1) == *src)
         {
-            // Сдвигаем указатель src вправо
-            *src++;
+            /* Сдвигаем указатель src вправо */
+            src++;
         }
-        *src++;
+        src++;
     }
-    // Запишем ноль в конец строки
+    /* Запишем ноль в конец строки */
     *dst = 0;
 }

Читайте также: «Вопросы программисту на собеседовании с ответами».

Блог Евгения Жирнова