Вопросы программисту 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).