Недавно я завис на портале geekbrains.ru, раздумывая, не поступить ли мне на курс по C++ или по Unity. Решил для развлечения тесты порешать по моим любимым языкам C/C++/C#. Несколько базовых тестов успешно прошел, а дальше забуксовал. И решил проработать проблемные вопросы, а в качестве стимула написать заметку в блог. Итак, поехали. Я немножко переформатировал фрагменты кода, чтобы он лучше воспринимался глазами. Ответы и пояснения иногда привожу прямо в исходном коде тестов в виде комментариев.
1. Что будет выведено на экран в результате работы программы?
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. Если бы авторы теста не старались запутать нас специально, то они написали бы:
{
...
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»
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();
}
Вариантов можно было выбрать несколько и я выбрал:
virtual void f() { cout << 2; } // правильно
static void f() { cout << 2; } // НЕправильно
А подвело меня то, что я не обратил внимание на то, что указатель b имеет тип A*, а не B*. Поэтому компилятор выберет функцию A::f(), а не B::f().
3. В каких строках программы содержатся ошибки?
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:
{
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++?
- deque
- min_heap
- inverse_list
- unordered_set
- 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++?
- Обращение по несуществующему ключу в map через operator[]
- Разыменование нулевого указателя
- Использование виртуального наследования
- Выход за пределы типа
- Множественное наследование
Провожу эксперимент — разыменовываю нулевой указатель:
{
int* p = nullptr;
int a = *p;
}
Появляется сообщение «Access violation exception», и программа завершается. Вроде вполне себе определенное поведение, поэтому я этот пункт не отметил и ошибся. Дело в том, что в стандарте C++ написано, что разыменование нулевого указателя вызывает неопределенное поведение, т. е. поведение, которое не регламентируется стандартом. А сообщение об ошибке и завершение программы в моем случае — это заслуга операционной системы. Что такое «выход за пределы типа», я вообще не понял, возможно, имелся в виду «доступ к объекту при помощи указателя на тип отличный от типа объекта». Типичные примеры неопределенного поведения приведены на cppreference.com, а полную информацию см. в спецификации C++ на полторы тысячи страниц.
6. Что будет выведено на экран в результате работы программы?
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. Что должно стоять вместо ***, чтобы программа успешно скомпилировалась?
{
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 вызывать функцию. Поэтому надо явно сообщить компилятору эту информацию:
{
D d;
// d.f(); // Error: ambiguity
d.A::f();
d.B::f();
d.C::f();
}
А вот вам такой забавный код, который показывает, что порядок, в котором вы указываете базовые классы при множественном наследовании, важен:
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
Класс, который наследуется виртуально называется виртуальным базовым классом.
Виртуальное наследование позволяет избежать дублирования данных при ромбовидном наследовании, но за это приходится платить «странностями» правил инициализации и присваивания классов, его использующих. В книжке Скотта Мейерса «Эффективное использование C++» есть раздел «Правило 40: Продумывайте подход к использованию множественного наследования». Совет Скотта Мейерса таков:
Не применяйте виртуальное наследование до тех пор, пока в нем не возникнет настоятельная необходимость — по-умолчанию используйте невиртуальное наследование. Если вы используете виртуальные базовые классы, старайтесь не размещать в них данные. Тогда можно забыть о странностях правил инициализации и присваивания таких классов.
Можно следовать тем же правилам вируального наследования, которые определены в языках Java и C#, которые допускают множественное наследование интерфейсов, но не множественное наследование классов.
8. Какие строчки программы приведут к ошибкам компиляции?
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. Что будет выведено на экран в результате работы программы?
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:
{
public:
void f() override
{
cout << "B";
}
};
10. Что будет выведено на экран в результате работы программы?
#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 <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. Какие строчки программы приведут к ошибкам компиляции?
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. Какие строчки программы приведут к ошибкам компиляции?
{
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 <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. Что будет выведено на экран в результате работы программы?
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.
Пока это всё. Буду обновлять данную заметку до тех пор пока не пройду тест 🙂