Тест по программированию на C++ от GeekBrains (средний уровень)

Недавно я завис на портале geekbrains.ru, раздумывая, не поступить ли мне на курс по C++ или по Unity. Решил для развлечения тесты порешать по моим любимым языкам C/C++/C#. Несколько базовых тестов успешно прошел, а дальше забуксовал. И решил проработать проблемные вопросы, а в качестве стимула написать заметку в блог. Итак, поехали. Я немножко переформатировал фрагменты кода, чтобы он лучше воспринимался глазами. Ответы и пояснения иногда привожу прямо в исходном коде тестов в виде комментариев.

1. Что будет выведено на экран в результате работы программы?

#include <iostream>
using namespace std;

class A
{
public:
    A() :
        x(0),
        y(0),
        z(0)
    { }

    A(int a, int b) :
        y(x + 2 * b), // 3rd
        z(y + 1),     // 2nd
        x(a)          // 1st
    {
        cout << z << endl;
    }

private:
    int x; // 1st
    int y; // 2nd
    int z; // 3rd
};

void main()
{
    A(1, 1);
}

Видно, что вызывается конструктор класса A с двумя параметрами. Вот только конструктор какой-то странный, я бы такой код никогда не написал. Поле y инициализируется значением x + 2 * b, но поле x еще не проинициализировано, значит результат такой инициализации будет неопределен. Так рассудил я, ответил «Результат неизвестен» и ошибся. Подвело меня то, что я привык, что поля класса инициализируются в списке инициализации конструктора в том же порядке, в котором они объявлены, а в данном случае авторы, очевидно, нарочно сделали по-другому. Дело в том, что в языке C++ поля инициализируются в том порядке, в котором они объявлены, независимо от порядка, в котором вы их инициализируете в списке инициализации в конструкторе. Поэтому правильные сначала инициализируется поле x, потом y, потом z. Если бы авторы теста не старались запутать нас специально, то они написали бы:

class A
{
...
    A(int a, int b) :
        x(a)
        y(x + 2 * b),
        z(y + 1),
    {
        cout << z << endl;
    }
...
};

Таким образом x = a = 1, y = x + 2 * b = 1 + 2 * 1 = 3, z = y + 1 = 4. Правильный ответ: на экран будет выведено число 4.

2. Что должно стоять вместо ***, чтобы в результате работы программы на экран были выведены символы «12»

#include <iostream>
using namespace std;

class A
{
public:
    virtual void f()
    {
        cout << 1;
    }
};

class B : public A
{
public:
    ***
};

void main()
{
    A* a = new A();
    A* b = new B();
    a->f();
    b->f();
}

Вариантов можно было выбрать несколько и я выбрал:

void f() { cout << 2; }         // правильно
virtual void f() { cout << 2; } // правильно
static void f() { cout << 2; }  // НЕправильно

А подвело меня то, что я не обратил внимание на то, что указатель b имеет тип A*, а не B*. Поэтому компилятор выберет функцию A::f(), а не B::f().

3. В каких строках программы содержатся ошибки?

#include <iostream>
using namespace std;

void main()
{
    const int x = 1;           // 1
    int& y = x;                // 2 ошибка: ссылка не константная, а ссылается на константную переменную
    int *const p = new int(1); // 3
    const int *q = &x;         // 4
    int &z = p;                // 5 ошибка в синтаксисе
}

Правильный ответ приведен тут же в коде: 2 и 5. Но я по ошибке добавил еще и 4, не заметив слова const, которое в данном случае делает указатель указателем на констанные данные. Вот как исправить ошибки в строках 2 и 5:

void main()
{
    const int x = 1;           // 1
    const int& y = x;          // 2 добавил слово const
    int *const p = new int(1); // 3
    const int *q = &x;         // 4
    int &z = *p;               // 5 добавил * перед p
}

4. Какие контейнеры отсутствуют в стандартной библиотеке C++?

  1. deque
  2. min_heap
  3. inverse_list
  4. unordered_set
  5. forward_vector

Я ответил правильно, только вот указал не те которые отсутствуют, а те которые присутствуют. Но вопрос все равно стоящий, поскольку я например всех контейнеров STL наизусть не помню, так как в своих поделках пользуюсь только тремя: vector, map и array. Отличная табличка с перечислением всех контейнеров и их функциональности есть на cppreference.com. Я только их перечислю:

  • array — массив фиксированного размера.
  • vector — контейнер с изменяемым размером
  • deque — double-ended queue (двустронняя очередь), позволяет вставлять эффективно вставлять и удалять элементы с начала и с конца.
  • forward_list — односвязный список, позволяет эффективно вставлять и удалять элементы.
  • list — двусвязный список, позволяет эффективно вставлять и удалять элементы.
  • set — множество уникальных объектов.
  • map — ассоциативный контейнер с уникальными ключами.
  • unordered_set — множество уникальных объектов.
  • unordered_map — ассоциативный контейнер с уникальными ключами.
  • stack — адаптер контейнера, предоставляет функциональность LIFO-устройства.
  • queue — адаптер контейнера, предоставляет функциональность FIFO-устройства.

5. Что из перечисленного ниже обязательно вызовет неопределенное поведение в C++?

  1. Обращение по несуществующему ключу в map через operator[]
  2. Разыменование нулевого указателя
  3. Использование виртуального наследования
  4. Выход за пределы типа
  5. Множественное наследование

Провожу эксперимент — разыменовываю нулевой указатель:

void main()
{
    int* p = nullptr;
    int a = *p;
}

Появляется сообщение «Access violation exception», и программа завершается. Вроде вполне себе определенное поведение, поэтому я этот пункт не отметил и ошибся. Дело в том, что в стандарте C++ написано, что разыменование нулевого указателя вызывает неопределенное поведение, т. е. поведение, которое не регламентируется стандартом. А сообщение об ошибке и завершение программы в моем случае — это заслуга операционной системы. Что такое «выход за пределы типа», я вообще не понял, возможно, имелся в виду «доступ к объекту при помощи указателя на тип отличный от типа объекта». Типичные примеры неопределенного поведения приведены на cppreference.com, а полную информацию см. в спецификации C++ на полторы тысячи страниц.

6. Что будет выведено на экран в результате работы программы?

template<class T = int>
class MyClass
{
public:
    void f() { cout << "D"; }
};

template<>
class MyClass<int>
{
public:
    void g() { cout << "S1"; }
};

template<>
class MyClass<double>
{
public:
    void h() { cout << "S2"; }
};

void main()
{
    MyClass<> a; // MyClass<int> a;
    a.f();       // Ошибка: MyClass<int> не имеет функции-члена с именем f

    MyClass<string> b;
    b.f();

    MyClass<double> c;
    c.h();
}

Я ответил «DDS2» и ошибся. На самом деле программа не скомпилируется — пояснения даны в коде. Шаблонный параметр класса MyClass имеет значение по-умолчанию — int, но в то же время для шаблонного параметра int существует специализация, а в этой специализации действительно нет функции-члена с именем f. Авторы теста опять сбили меня с понталыку, написав заведомо корявый код.

7. Что должно стоять вместо ***, чтобы программа успешно скомпилировалась?

class A
{
public:
    void f() {}
};

class B : public A
{ };

class C : public A
{
public:
    void f() {}
};

class D : public B, public C
{ };

void main()
{
    D d;
    ***
}

Это пример ромбовидного наследования. Как ни странно, я до сих пор никогда не пользовался даже множественным наследованием, не говоря уже о ромбовидном. Хитростей в C++ и так хватает, а множественное наследование подкидывает еще дополнительные. Например в приведенном коде класс D содержит две копии класса A, поэтому если написать вызов функции d.f(), возникнет неоднозначность, для какой копии класса A вызывать функцию. Поэтому надо явно сообщить компилятору эту информацию:

void main()
{
    D d;
    // d.f(); // Error: ambiguity
    d.A::f();
    d.B::f();
    d.C::f();
}

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

#include <iostream>
using namespace std;

class A
{
private:
    char x;
public:
    A(char x) : x(x) {}
    void f() { cout << x << endl; }
};

class B : public A
{
public:
    B() : A('B') {}
};

class C : public A
{
public:
    C() : A('C') {}
};

class D : public B, public C
{ };

class E : public C, public B
{ };

void main()
{
    D d;
    // d.f(); // Error: ambiguity
    d.A::f(); // "B"
    d.B::f(); // "B"
    d.C::f(); // "C"

    E e;
    // e.f(); // Error: ambiguity
    e.A::f(); // "C"
    e.B::f(); // "B"
    e.C::f(); // "C"

    cin.get();
}

Про множественное наследование можно почитать в [Bjarne Stroustrup. The C++ Programming Language. Fourth Edition. 21.3 Multiple Inheritance]. Что следует отметить: при «ромбовидном» наследовании в самом производном классе обязательно окажется несколько копий одного и того же базового класса, если только это не так называемое виртуальное наследование, при котором таких копий не возникает — см. [Stroustrup, 21.3.5 Virtual base classes]. На самом деле термин «ромбовидное наследование» относится как раз к виртуальному наследованию. Если наследование не виртуальное, то формально никакого ромба нет, но мне проще употреблять термин «ромбовидное наследование» и в этом случае тоже.

--- обычное наследование ---
class A {};
class B : public A {};
class C : public A {};
class D : public B, public C {};

A   A
|   |
B   C
 \ /
  D

--- виртуальное наследование ---
class A {};
class B : virtual public A {};
class C : virtual public A {};
class D : public B, public C {};

  A
 / \
B   C
 \ /
  D

8. Какие строчки программы приведут к ошибкам компиляции?

#include <iostream>
using namespace std;

template <typename T1, typename T2>
void f(T1 x, T2 y)
{
    cout << x << " " << y << endl;
}

class A
{
public:
    A(int x) : val(x) { }

private:
    int val;
};

void main()
{
    f<char>('1', "2");   // 1
    f<string>('1', "2"); // 2 Error: '1' is not a string
    f('1', "2");         // 3
    f<A, int>(1, 2);     // 4
    f(1.0, 2);           // 5
}

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

9. Что будет выведено на экран в результате работы программы?

#include <iostream>
using namespace std;

class A
{
public:
    virtual void f()
    {
        cout << "A";
    }
};

class B : public A
{
public:
    void f()
    {
        cout << "B";
    }
};

void main()
{
    B b;
    A& a = b;
    a.f();
}

Я давно программирую на C#, а в C# подобный код вывел бы «A», потому что в классе B в определении функции f нет слова override, поэтому функция B::f скрывает функцию A::f. Но в C++ все не так, функция B::f переопределяет функцию A::f, поэтому выведется «B». Однако и в C++ когда переопределяют функции хорошо бы добавлять для ясности слово override:

class B : public A
{
public:
    void f() override
    {
        cout << "B";
    }
};

10. Что будет выведено на экран в результате работы программы?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main()
{
    vector<int> v = { 52, 12, 32, 29, 37 };

    make_heap(v.begin(), v.end());    // 1
    /*
    max-heap:
              52
             /  \
           37    32
          /  \
        29    12

    vector after the heapification:
        52 37 32 29 12
    */


    int n = v.size();
    for (int i = 0; i < n; i++)
    {
        pop_heap(v.begin(), v.end());
        cout << v.back() << " ";
        v.pop_back();
    }
    // 52 37 32 29 12
}

Я понятия не имел, что такое heap, поэтому полез в Википедию. Там я ничего не понял, но заглянул в список литературы и стал читать [Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн — Алгоритмы. Построение и анализ — 2013]. Очень интересная книжка, из нее я наконец узнал какие-то методы сортировки кроме метода пузырька. Чтобы понять, что такое heap (переводится в данном контексте как «пирамида», хотя в статьях в Википедии переводят как «куча»), нужно прочитать всё до Главы 6 — Пирамидальная сортировка включительно. Если в двух словах, то… heap — это структура данных «бинарное дерево», т. е. дерево, у каждого узла которого есть по два дочерних узла (или нет дочерних узлов вовсе). Причем каждый родительский узел связан с дочерними соотношением «больше или равно» (невозрастающее дерево) либо «меньше или равно» (неубывающее дерево). Оказывается, что любой контейнер из стандартной библиотеки C++ можно сделать таким деревом — для этого нужно просто выстроить элементы контейнера в определенном порядке, а именно по уровням дерева (словами объяснять — это непонятно, почитайте [Кормен и др., 6.1 — Пирамиды]). А зачем вообще нужна эта самая пирамида? Из книжки я понял, что она может быть нужна для двух вещей: 1) сортировка массива за время O(n*lg(n)), 2) реализация т. н. очереди с приоритетами.

Чтобы выстроить (упорядочить) элементы контейнера в соответствии со структурой heap, можно вызвать функцию make_heap. Функция выстраивает элементы в виде невозрастающего бинарного дерева. Первый элемент (корень дерева) всегда максимальный (52), на следующем уровне дерева расположены числа 37 и 32, еще ниже — 29 и 12 (см. комментарии в коде). Далее в цикле for: pop_heap перемещает первый элемент в конец контейнера, а остальные элементы снова heap’ифицирует. Следующая строка выводит на экран последний элемент контейнера, а функция pop_back его из контейнера удаляет. Таким образом на экран выведутся все элементы контейнера в порядке убывания.

11. Что будет выведено на экран в результате работы программы?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main()
{
    vector<int> v = { 0, 1, 2, 3, 4, 5, 6 };

    auto it = remove_if(
        v.begin(),
        v.end(),
        [](const int x) -> bool { return x % 5 != 0; });

    /*
           it
           |
       0 5 2 3 4 5 6
    */


    v.erase(it, v.end());

    // 0 5

    cout << v.size(); // 2

    cin.get();
}

Можно было бы подумать, что функция remove_if удаляет элементы из контейнера. На самом деле она этого делать не умеет, поскольку не является членом класса контейнера. Вместо этого она сдвигает все элементы, удовлетворяющие условию в правую часть контейнера, чтобы затем можно было их удалить вызовом специализированной функции — в данном случае vector::erase. Возвращает же функция remove_if итератор, который указывает на начало диапазона, который надо будет удалить. В приведенном примере удаляются все элементы, которые не делятся нацело на 5, и в результате в контейнере остается только два элемента — 2 и 5.

12. Какие строчки программы приведут к ошибкам компиляции?

#include <memory>
using namespace std;

class A {
public:
    A(int x) : val(x) { }
    int val;
};

void main()
{
    auto p1 = make_shared<A>(1); // 1
    auto p2 = make_shared(A, 1); // 2 Error: missing template arguments. Correct: make_shared<A>(1)
    A* a = new A(2);
    auto p3 = make_shared(a);    // 3 Error: missing template arguments. Correct: make_shared<A>(a)
    auto p4 = shared_ptr(a);     // 4 Error: missing template arguments. Correct: shared_ptr<A>(a)
    auto p5 = shared_ptr<A>(a);  // 5
}

Ответ — в комментариях в исходном коде.

13. Какие строчки программы приведут к ошибкам компиляции?

class A
{
public:
    void f() { }

protected:
    void g() { }

private:
    void h() {}
};

class B : public A
{
public:
    void method() {
        f(); // 1
        g(); // 2
        h(); // 3 Error: trying to access private member of base class
    }
};

class C : protected B
{
public:
    void method() {
        f(); // 4
        g(); // 5
        h(); // 6 Error: trying to access private member of base class
    }
};

Ответ приведен в исходном коде. Я в своем коде до сих пор никогда не пользовался защищенным (protected) и закрытым (private) наследованием, поэтому есть повод поговорить. В зависимости от типа наследования изменяется видимость членов базового класса в производном классе. Например, при публичном (public) наследовании публичные члены базового класса становятся публичными же членами производного класса. А при защищенном наследовании публичные члены базового класса становятся защищенными членами производного класса. В таблице ниже показано, как изменяется видимость членов базового класса в производном классе в зависимости от типа наследования.

Base class member access modifier Type of inheritance
public protected private
public public protected private
protected protected protected private
private inaccessible inaccessible inaccessible

14. Почему программа не скомпилируется?

#include <iostream>
#include <string>
#include <map>
using namespace std;

class A
{
public:
    A(int x, const string& a) : val(x), str(a) { }
    A(const A& a) = delete;
    int val;
    string str;
};

// Relational less than operator is needed for map<A, ...>
// bool operator<(const A& a, const A& b) { return a.val < b.val; }

void main()
{
    map<A, int> m;
    A a(3, "2");
    m[a] = 1; // Error(1): This instruction tries to add a new key to the map
              //           To add a key it needs to copy variable a.
              //           But the copy constructor is deleted.
              // Error(2): Relational less than operator isn't defined (see comment above)
    cout << m[a];
}

Ответ приведен в комментариях. Ошибок две: конструктор копирования класса A удален (deleted function), для объектов класса A не определен оператор «меньше». И то, и другое требуется для того, чтобы можно было использовать объекты класса A в качестве ключей контейнера map.

15. Что будет выведено на экран в результате работы программы?

#include <iostream>
using namespace std;

class A
{
public:
    A() { cout << "A"; }
    ~A() { cout << "~A"; }
};

class B : public A
{
public:
    B() { cout << "B"; }
    ~B() { cout << "~B"; }
};

class C : public A, public B
{
public:
    C() { cout << "C"; }
    ~C() { cout << "~C"; }
};

class D : public A, public B, public C
{
public:
    D() { cout << "D"; }
    ~D() { cout << "~D"; }
};

void main()
{
    D d; // AABAABCD~D~C~B~A~A~B~A~A
}

Ответ приведен в комментарии. Множественное наследование со множеством копий класса A. В каком порядке вызываются конструкторы классов поможет понять следующий рисунок:

иерархия        порядок вызова
наследования    конструкторов
         A               5
         |               |
   A  A  B         2  4  6
   |  | /          |  | /
A  B  C         1  3  7
 \ | /           \ | /
   D               8

Деструкторы же вызываются в порядке, обратном тому, в котором вызываются конструкторы.

16. Какие из перечисленных ниже типов умных указателей существуют в С++11 и удаляют объект, на который указывают, если отсутствуют другие указатели, указывающие на тот же объект?

Вот список умных указателей, которые предлагает стандартная библиотека С++ с краткими пояснениями.

  • unique_ptr — указатель, которые не допускает копирование себя, предполагается, что существует только один (уникальный) указатель на некоторый объект. Когда удаляется указатель unique_ptr, удаляется и объект на который он указывает.
  • shared_ptr — указатель, который допускает копирование себя и производит подсчет ссылок. Число ссылок увеличивается при копировании указателя и уменьшается при уничтожении указателя. Когда число ссылок на объект становится равным нулю, объект удаляется.
  • weak_ptr — указатель, который работает в связке с shared_ptr. Не участвует в подсчете ссылок и не удаляет объект при уничтожении указателя. Задача weak_ptr — дать программисту возможность получить временный shared_ptr-указатель на объект при помощи функции lock(). Вызов функции lock() может завершиться неудачей, если объект уже удален.

Таким образом, правильный ответ на вопрос теста — shared_ptr.

Пока это всё. Буду обновлять данную заметку до тех пор пока не пройду тест 🙂

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *