Годовой курс по C++

Язык, если это не C++, выучить можно.
- с лекции по функциональному программированию

- из паблика inter oves locum praesta, 19.02.2016

    В 2016-17 учебном году мне довелось прочитать углубленный курс по программированию на C++ для первокурсников ФИВТ МФТИ продвинутого потока.

    Здесь я привожу получившуюся программу курса за первый семестр и за второй, а также списки контрольных вопросов, которые давались студентам на зачетах в конце семестров. Считаю, что всем, кто (думает, что) знает C++ или только учится этому величайшему языку богов, будет интересно сопоставить свои знания с данной программой и проверить себя, ответив на приведенные вопросы. Я не привожу условия практических заданий, поскольку, во-первых, это еще куча простыней текста, во-вторых, эти задания, быть может, еще предстоит когда-то переиспользовать.

    Названия Intermediate и Upper-Intermediate мной даны, конечно же, субъективно и условно. "Почему не Advanced?" - спросите вы. Потому что здесь полностью отсутствует тема многопоточности, а также вещи, которые были привнесены в язык надвигающимся стандартом C++17. Вероятно, этому стоило бы посвятить третий семестр.

Первый семестр (C++ Intermediate)

Программа курса

  1. Общие сведения о языке С++, его авторе, существующих версиях языка, компиляторах. Функция main и ее особенности. Директива #include. Синтаксис объявления переменных, функций. Разница между объявлением и определением. Область видимости переменных, правила сокрытия имен, обращение к глобальной области видимости из локальной.
  2. Выражения и операторы. Правила вычисления выражений. Понятие lvalue и rvalue. Различные операторы присваивания и схема их работы. Операторы инкремента и декремента, отличие префиксного инкремента от постфиксного. Побитовые операторы. Логические операторы, особенности их вычисления. Тернарный оператор. Оператор запятая, схема его работы. Пространства имен, оператор “двойное двоеточие”.
  3. Фундаментальные типы, их размеры. Оператор sizeof. Литералы, константы для различных типов. Правила неявного преобразования типов. Преобразование типов в стиле Си, его принцип работы и недостатки. Перечисления (enum). Перегрузка функций. Правила разрешения перегрузки. Функции с необязательными аргументами. Функции с неуказанным числом аргументов. Ключевое слово inline.
  4. Указатели. Статические массивы. Сходства и различия между указателями и массивами. Разыменование указателей, операция взятия адреса. Арифметические операции с указателями. Преобразование указателей друг к другу, тип void*. Указатели на функции. Константы, ключевое слово const. Ссылки. Отличия ссылок от указателей. Необходимость инициализации констант и ссылок. Передача аргументов по значению, по указателю и по ссылке. Константные указатели и указатели на константу. Константные ссылки. Проблема переполнения стека. Динамическая память. Операторы new и new[]. Операторы delete и delete[], схема их работы, принцип использования. Проблема утечек памяти.
  5. Классы. Отличия классов от структур. Модификаторы доступа. Поля и методы, понятие инкапсуляции. Конструкторы. Конструктор по умолчанию. Перегрузка конструкторов. Конструктор копирования, его сигнатура и схема реализации. Оператор присваивания, его сигнатура и схема реализации. Пример, когда необходим нетривиальный конструктор копирования и оператор присваивания. Способы запрета конструкторов или присваивания. Правила генерации компилятором конструкторов. Деструкторы. Ключевое слово this и пример, когда оно нужно. Списки инициализации и пример, когда они необходимы. Явные конструкторы, ключевое слово explicit, пример. Статические поля и методы, пример. Локальные статические переменные. Константные и неконстантные методы. Ключевое слово mutable, пример. Дружественные методы и классы, пример.
  6. Перегрузка операторов. Какие операторы нельзя перегружать. Чего можно и чего нельзя добиться перегрузкой операторов. Синтаксис перегрузки арифметических операторов. Перегрузка префиксного и постфиксного инкремента. Перегрузка оператора "квадратные скобки", ее особенности. Перегрузка оператора "круглые скобки", пример использования. Перегрузка операторов приведения типа, ее особенности и недостатки, пример. Особенности перегрузки логических операторов и оператора "запятая".
  7. Понятие наследования. Синтаксис наследования, правила сокрытия имен при наследовании. Схема использования объектов производного класса в местах, где требуются объекты базового класса. Понятие о срезке при копировании. Порядок выполнения конструкторов и деструкторов при наследовании, вызов конструктора родителя из конструктора потомка. Виды наследования: публичное, приватное, защищенное. Пример использования приватного наследования. Множественное наследование. Проблема неоднозначности вызова метода из базовых классов и ее решение. Проблема ромбовидного наследования и ее решение. Виртуальное наследование, его особенности.
  8. Виртуальные функции, их применение. Понятие полиморфизма. Разница в поведении виртуальных и невиртуальных функций при наследовании. Чисто виртуальные функции. Понятие абстрактного класса, особенность абстрактных классов. Виртуальные деструкторы, чисто виртуальные деструкторы, их назначение. Проблема с вызовами виртуальных функций в конструкторах.
  9. Понятие шаблонов. Виды полиморфизма: статический и динамический. Шаблонные классы, синтаксис их определения. Специализация шаблонов, синтаксис определения, пример. Параметры шаблонов, не являющиеся типами, пример. Шаблонные функции, синтаксис объявления и использования. Проблема поиска имен при наследовании шаблонов, ее решение. Вложенные типы, ключевое слово typename и пример, когда оно необходимо.
  10. Приведение типов: static_cast, dynamic_cast, разница между ними, примеры применения. Приведение типов const_cast, пример применения. Приведение типов reinterpret_cast, пример применения. Ключевое слово typeid, динамическая проверка типа, вывод имени типа, пример.
  11. Понятие итераторов. Классификация итераторов: input, output, однонаправленные, двунаправленные, произвольного доступа. Операции, поддерживаемые итераторами. Структура std::iterator и ее смысл. Класс std::iterator_traits, его назначение, отличия от std::iterator и пример использования. Классы итераторных тегов. Пример функции, по-разному ведущей себя в зависимости от типа переданного итератора, реализация такого примера через шаблоны. Функции std::advance и std::distance, схема их реализации. Константные и неконстантные итераторы. Класс std::reverse_iterator, его примерная реализация. Функция base. Классы итераторов для вставок (insert_iterator), их схема реализации и использования. Функции std::inserter, std::front_inserter и std::back_inserter, схема их реализации и пример использования.
  12. Понятие исключений, общая идея, аргументы за и против применения исключений. Оператор throw и конструкция try...catch, схема ее работы. Правила генерации и перехвата исключений, производные исключения. Проброс и повторная генерация исключений, перехват любых исключений. Особенности передачи исключений по указателю, по ссылке и по значению. Спецификации исключений в стиле С++03, их преимущества и недостатки. Неожиданные исключения, функция unexpected. Функции terminate и set_terminate. Особенности исключений в конструкторах и деструкторах, функция uncaught_exception. Примеры стандартных исключений и операторов или методов STL, которые их генерируют. Отличия между исключениями и ошибками времени выполнения.
  13. Понятие контейнера. Последовательные контейнеры. Контейнер std::vector, схема его реализации. Схема работы и асимптотика методов push_back, pop_back, insert, erase. Методы size, capacity, resize, reserve, shrink_to_fit. Методы для обращения по индексу, для обращения к первому и последнему элементам. Метод swap, его схема реализации. Контейнер vector<bool> и его отличия от обычного vector. Контейнер std::deque, схема его реализации, асимптотика работы методов. Отличия deque от vector с точки зрения интерфейса. Контейнеры std::list и std::forward_list, схема их реализации, асимптотика работы методов. Отличия list от deque и vector с точки зрения интерфейса. Методы, специфичные для list: sort, merge, splice, remove, unique, reverse, схема их реализации. Отличия list от forward_list. Понятие адаптеров над контейнерами. Схема реализации std::stack, std::queue, std::priority_queue, асимптотика работы методов, требования к используемому контейнеру.
  14. Ассоциативные контейнеры. Класс std::map, его идея, его назначение и схема реализации. Асимптотика и принцип работы методов [], find, count, insert, erase. Класс std::pair и его связь с map. Функция make_pair. Класс std::set, его отличия от std::map. Классы std::multimap и std::multiset, их отличия от std:map и std::set. Класс std::unordered_map, его идея, схема реализации, асимптотика работы методов, отличия от std::map.
  15. Понятие функтора в С++. Принцип работы функторов. Стандартные функторы, схема их реализации, заголовочный файл <functional>. Понятие компаратора, примеры компараторов, стандартные компараторы, их реализация. Стандартные алгоритмы из заголовочного файла <algorithm>, их действие и асимптотика работы. Стандартные алгоритмы из заголовочного файла <numeric>, их действие.
  16. Стандартные строки. Шаблонный класс basic_string, его методы, отличия от vector. Класс string. Класс char_traits, его специализации, его назначение.
  17. Концепция потоков ввода-вывода. Иерархия классов стандартных потоков. Класс ios_base. Флаги потоков. Методы precision и width. Синхронизация с stdio. Классы basic_ios и ios. Состояние потоков, проверка и изменение состояния. Метод tie. Классы basic_istream, basic_iostream, basic_ostream. Классы ostream, istream, iostream, их определения. Манипуляторы потоков, схема их работы. Примеры манипуляторов. Манипуляторы с параметрами, заголовочный файл <iomanip>. Файловые потоки и строковые потоки. Буфера потоков, классы basic_streambuf и streambuf. Итераторы потоков: istream_iterator и ostream_iterator, их схема реализации.

Вопросы для контроля за первый семестр
Вариант 1

  1. Объясните значение термина "инкапсуляция".
  2. Объясните значение ключевого слова mutable. Приведите пример применения.
  3. Объясните значение терминов lvalue и rvalue в С++03.
  4. Что означает слово static применительно к методу класса?
  5. Чему будут равны значения переменных после вычисления выражения и чему равно значение выражения:
    ++x = (y = 3 ? 2 : 1,5);
  6. Что такое undefined behaviour в С++? Приведите пример.
  7. Что такое перегрузка функций? Приведите пример.
  8. Напишите код для выполнения следующих действий: выделить в куче массив из 1000 переменных типа int, проинициализировать нулями, затем удалить.
  9. Рассмотрим следующую программу:
    #include <vector>

    int main() { std::vector<int> v(10); delete[] &v[0]; }

    Скомпилируется ли она? Если да, то что произойдет при ее запуске? В каждом случае объясните ответ.
  10. Что такое const_cast? Приведите пример его использования.
  11. Перечислите основные отличия между указателями (T*) и ссылками (T&) в С++.
  12. Перечислите отличия между классом и структурой в С++.
  13. Что такое списки инициализации в конструкторах? Приведите пример ситуации, когда их необходимо использовать.
  14. Что такое срезка при копировании? Приведите пример ситуации, когда она возникает.
  15. Пусть имеется класс:
    class NotSoPleasant {

        size_t size; // количество элементов в array   

        int* array; // динамически выделяемый массив

        NotSoPleasant(size_t size): size(size) { array = new int[size]; }

        // ...

    };

    Напишите код конструктора копирования и оператора присваивания для данного класса.
  16. Пусть имеется класс BigInteger, у которого определен оператор += от int. Напишите код для определения префиксного и постфиксного инкремента у этого класса.
  17. В чем опасность перегрузки оператора двойной амперсанд?
  18. Для чего употребляется ключевое слово typeid? Приведите пример.
  19. Что такое виртуальное наследование? Для чего оно используется?
  20. Для чего необходим виртуальный деструктор? Приведите пример ситуации, когда отсутствие виртуального деструктора приводит к проблемам.
  21. Что такое абстрактный класс в С++? В чем особенность абстрактных классов?
  22. Приведите пример, когда необходимо использовать ключевое слово typename.
  23. Напишите шаблонный класс Greater<T>, аналог std::greater<T>.
  24. Что такое специализация шаблонов? Приведите пример специализированных шаблонов из стандартной библиотеки.
  25. Какие шаблонные параметры имеет класс std::reverse_iterator? Объясните вкратце, что представляет из себя реализация этого класса.
  26. Зачем нужна функция std::back_inserter? Приведите пример ее использования.
  27. Зачем нужен класс std::iterator_traits? Приведите пример его использования.
  28. Какие способы обращения по индексу к std::vector вы знаете, в чем разница между ними?
  29. Какие методы std::deque отсутствуют у std::vector? Каково их действие?
  30. Что такое адаптеры над контейнерами? Перечислите адаптеры над контейнерами, которые вы знаете. Над какими контейнерами они реализованы?
  31. Назовите хотя бы три метода std::list и std::forward_list, которые отсутствуют в других контейнерах. Поясните, какую асимптотическую сложность они имеют и что делают.
  32. Перечислите все известные вам способы проверить, есть ли в данном std::map запись с данным ключом.
  33. Назовите методы std::map, которые отсутствуют в std::multimap. Каково их действие и временная сложность.
  34. Рассмотрим функцию:
    void modify_set(std::set<int>& set) {
    for (std::set<int>::iterator iter = set.begin(); iter != set.end(); ++iter)
        *iter *= *iter;
    }

    Какую проблему в ней вы видите?
  35. Какие операции должен поддерживать тип данных, чтобы его можно было использовать в качестве ключа в std::map?
  36. Какие шаблонные параметры есть у класса std::unordered_map? Назовите хотя бы четыре из пяти, объясните их смысл.
  37. Каково действие алгоритма std::stable_partition? Какие параметры он принимает, какова его асимптотическая сложность?
  38. Каково действие алгоритма std::generate? Какие параметры он принимает?
  39. Что такое спецификации исключений? Приведите пример.
  40. Рассмотрим две строчки кода:
    catch (std::exception& ex) { throw; }
    catch (std::exception& ex) { throw ex; }
    В чем разница между ними? Когда эта разница проявляется?
  41. Что содержится в определении класса std::char_traits? Зачем нужен этот класс?
  42. Объясните действие метода tie класса std::basic_ios. Приведите пример, когда его нужно использовать.
  43. Что такое манипуляторы потоков? Приведите пример их использования.

Вариант 2

  1. Объясните значение термина полиморфизм. Какие виды полиморфизма есть в С++, как они реализуются?
  2. Объясните значение ключевого слова friend. Приведите пример применения.
  3. Объясните значение ключевого слова this. Приведите пример ситуации, когда необходимо использовать это слово.
  4. Что означает слово static применительно к локальной переменной?
  5. Объясните значение ключевого слова explicit. Приведите пример применения.
  6. Пусть имеется C-style массив arr из неизвестного числа элементов типа T. Присвойте переменной size значение, равное количеству элементов в этом массиве.
  7. Чему будут равны значения переменных после вычисления выражения и чему равно значение выражения:
    ((a = 5) ? (b = 3) : (a = 2)) = 7, 1;
  8. В чем отличие static_cast от C-style cast?
  9. Какая проблема есть в следующей строке кода?
    char* pc = 0, & rc = *pc;
  10. Рассмотрим следующую программу:
    #include <vector>

    int main() { std::vector<int> v(10); delete[] &v[0]; }

    Скомпилируется ли она? Если да, то что произойдет при ее запуске? В каждом случае объясните ответ.
  11. Перечислите контексты, в которых может употребляться ключевое слово const, и объясните значение этого слова в каждом случае.
  12. Напишите код для выполнения следующих действий: выделить в куче массив из 1000 переменных типа int, проинициализировать нулями, затем удалить.
  13. Напишите шаблонную функцию reverse, которая принимает на вход два итератора и разворачивает в обратном порядке диапазон значений между ними.
  14. Пусть объявлен класс:
    template<class T> class MyClass;

    Напишите код для запрета копирования и присваивания объектов этого класса друг другу.
  15. Пусть имеется класс:
    class FixedVector {

        std::array<int, N> coords; // N – глобальная константа

        // ...

    };

    Реализуйте для данного класса операторы + и +=, осуществляющие покоординатное сложение векторов.
  16. Какие операторы не поддаются перегрузке в С++? Назовите хотя бы 5 штук.
  17. Почему префиксный инкремент предпочтительнее постфиксного, если возвращаемое значение не используется в выражении?
  18. Для чего нужен dynamic_cast? Приведите пример ситуации, когда его целесообразно использовать.
  19. Что такое виртуальные функции? Для чего они необходимы, в чем их отличие от обычных функций?
  20. Для чего может быть нужен чисто виртуальный деструктор?
  21. В чем заключается “проблема ромбовидного наследования”? С помощью чего решается эта проблема?
  22. Назовите различия между публичным, приватным и защищенным наследованием. Для чего может быть нужно приватное наследование?
  23. Что такое компаратор? Какие вы знаете стандартные компараторы? Приведите пример использования.
  24. Напишите класс Multiplies<T1,T2>, аналогичный классу std::multiplies<T1,T2>.
  25. Перечислите виды итераторов, которые вам известны. Объясните разницу между ними.
  26. Что представляет из себя структура std::iterator? Что она содержит?
  27. Путь Iter является типом итератора. Почему запись std::iterator_traits<Iter>::value_type предпочтительнее, чем Iter::value_type?
  28. Какие шаблонные параметры имеет класс std::insert_iterator? Объясните вкратце, что представляет из себя реализация этого класса.
  29. Объясните разницу между методами std::vector::size() и std::vector::capacity().
  30. Какие методы std::vector отсутствуют у std::deque? Объясните их действие.
  31. Какие операции должен поддерживать тип T, чтобы его можно было использовать в контейнерах std::vector, std::deque?
  32. В чем заключаются отличия std::vector<bool> от std::vector над любым другим типом?
  33. Какие шаблонные параметры имеет класс std::priority_queue? Что представляет из себя реализация этого класса?
  34. Какие методы std::map отсутствуют в std::set? Объясните их действие и асимптотику работы.
  35. Напишите шаблонную функцию, которая по данному std::multiset возвращает число различных значений, хранящихся в нем.
  36. Рассмотрим функцию:
    int countSomeValues(const std::unordered_map<int,int>& map) {
       int ans = 0;
       for (int i = 10; i < 100; ++i)
           if (map[i] == 2)
               ++ans;
       return ans;
    }

    Какую проблему вы видите в ней?
  37. Какой тип имеет разыменованный итератор над std::map<T1, T2>? Как по этому итератору обратиться к ключу и к значению данной записи?
  38. Каково действие алгоритма std::nth_element? Какие параметры он принимает, какова его асимптотическая сложность?
  39. Каково действие алгоритма std::for_each? Какие параметры он принимает?
  40. Для чего нужна функция std::accumulate? Какие параметры она принимает? В каком заголовочном файле она объявлена?
  41. Объясните действие функции std::uncaught_exception. Приведите пример ее использования.
  42. Назовите хотя бы 3 примера стандартных функций С++ (или операторов, или методов классов), которые могут генерировать исключения. Назовите эти исключения.
  43. Объясните действие метода sync_with_stdio класса std::ios_base. Приведите пример, когда его нужно использовать.


Второй семестр (C++ Upper Intermediate)

Программа курса




1.      Введение в С++11 и еще некоторые тонкости  (2 лекции)

1.1.   Объединения (union). Отличия от классов и структур.

1.2.   Пространства имен. Поиск имен, зависящий от аргумента (идиома ADL). [DMC 3.2]

1.3.   Обобщенные typedef’ы в С++11. Примеры из STL. [EMC 3.3]

1.4.   Проблема вызова конструктора из конструктора. Делегирующие конструкторы в С++11. [статья на alenacpp]

1.5.   Определение пользовательских литералов в С++11. [статья на Хабрахабре]

1.6.   POD-типы. Ослабление требований к POD-типам в С++11.

1.7.   Enum-классы в С++11. Отличия от обычных enum’ов. [EMC 3.4]

1.8.   Выравнивания, оператор alignof и спецификатор alignas. Битовые поля в структурах.

1.9.   Ключевое слово constexpr, его значение, отличие от const. Ограничения, накладываемые на constexpr-функции в С++11 и С++14.

1.10. Ключевое слово noexcept, два его значения. [EMC 3.8]

2.      Move-семантика, rvalue-ссылки и прямая передача (2 лекции)

2.1.   Три нерешенные проблемы в С++03: неэффективный swap, неэффективный push_back, неэффективный конструктор из большого временного объекта.

2.2.   Применение функции std::move для устранения вышеописанных проблем.

2.3.   Понятие move-конструктора и move-assignment оператора, условия их генерации компилятором, ручное определение.

2.4.   Реализация функции std::move. [EMC 5.1]

2.5.   Понятие прямой передачи. Пример, когда необходимо использовать функцию std::forward. [EMC 5.1]

2.6.   Понятие rvalue-ссылок. Особенности инициализации rvalue-ссылок, разрешенные и запрещенные присваивания между нессылочными объектами, lvalue-ссылками и rvalue-ссылками.

2.7.   Правила продления жизни объектов с помощью ссылок. Правила присваивания между константными и неконстантными lvalue- и rvalue-ссылками.

2.8.   Понятие универсальных ссылок. Отличия универсальных ссылок от обычных rvalue-ссылок. Использование универсальных ссылок в аргументах методов STL (пример: функция emplace_back). [EMC 5.2]

2.9.   Понятия lvalue, rvalue, glvalue, prvalue и xvalue. Диаграмма связей между этими понятиями. Примеры выражений, являющихся тем или иным видом value.

2.10.  Сворачивание ссылок (reference collapsing). Правила сворачивания ссылок, связь этих правил с понятием универсальных ссылок. [EMC 5.6]

2.11.  Реализация функции std::forward. [EMC 5.6]

2.12.  Ссылочные квалификаторы (reference qualifiers). Пример использования. [EMC 3.6] Особенности вызова неконстантных методов у временных объектов.

2.13.  Return Value Optimization и условия ее возникновения. Целесообразное и нецелесообразное использование std::move в функциях, где возможна RVO (пример: сложение двух матриц). [EMC 5.3]

2.14. Проблема, связанная с использованием универсальных ссылок совместно с перегрузкой. [EMC 5.4]

3.      Принципы работы new/delete, аллокаторы (1 лекция)

3.1.   Понятие выражения new (new-expression). Отличие оператора new от функции operator new. Содержимое заголовочного файла <new>. [MEC 8]

3.2.   Синтаксис глобальной перегрузки operator new и operator delete. Пример: логгирование всех динамических выделений памяти. Синтаксис перегрузки new и delete для пользовательских классов. [MEC 8, EC 50]

3.3.   Проблема конструирования объекта в выделенной памяти. Placement new, пример его использования, синтаксис перегрузки placement new для пользовательских типов. Перегрузка new и delete с пользовательскими параметрами. [EC 52, MEC 8]

3.4.   Функции new_handler, set_new_handler и get_new_handler. Соглашения при написании operator new: бесконечный цикл, выравнивание, возможные проблемы с наследованием. [EC 49, 51]

3.5.   Понятие аллокатора. Класс std::allocator, его методы и их примерная реализация. Класс std::allocator_traits, его предназначение.

4.      Умные указатели (1 лекция)

4.1.   Идиома RAII. Проблема освобождения динамической памяти в случае исключений. Класс std::auto_ptr, его методы и недостатки.

4.2.   Класс std::unique_ptr, его методы, идея их реализации. Отличия auto_ptr от unique_ptr. [EMC 4.1]

4.3.   Класс std::shared_ptr, его предназначение, отличия от unique_ptr. Основные методы, идея их реализации. [EMC 4.2]

4.4.   Проблема закольцованности указателей. Счетчик ссылок и слабый счетчик. Класс std::weak_ptr, основные методы, идея их реализации. [EMC 4.3]

4.5.   Функции make_unique, make_shared, allocate_shared, их примерная реализация. Преимущество make_unique перед прямым вызовом конструктора unique_ptr. [EMC 4.4]

4.6.   Проблема создания нескольких указателей на один объект. Класс std::enable_shared_from_this, его назначение и пример использования. [EMC 4.2]

5.      Вывод типов (1 лекция)

5.1.   Вывод типов для шаблонов и для ключевого слова auto. Правила вывода типов для ссылок, не являющихся универсальными; для универсальных ссылок; для нессылочных объектов. [EMC 1.1]

5.2.   Вывод типов для случая с std::initializer_list. Отличия в выводе типов шаблонов и auto. [EMC 1.2]

5.3.   Трюк для просмотра выводимых типов на этапе компиляции (намеренный вызов ошибок инстанцирования шаблона). [EMC 1.4]

5.4.   Ключевое слово decltype и его назначение. Отличия в выводе типов для auto и для decltype. Особенности поведения decltype для выражений, не являющихся одиночными переменными. [EMC 1.3] Навешивание модификаторов типа (*, &) на результат decltype.

5.5.   Конструкция decltype(auto) и пример, когда она необходима. [EMC 1.3]

5.6.   Особенности инициализации с помощью initializer_list, его поведение при перегрузке конструкторов. [EMC 3.1]

6.      Функциональные объекты и лямбда-выражения (1 лекция)

6.1.   Понятие лямбда-выражения, замыкания, класса замыкания. Общий синтаксис лямбда-выражений. Явное указание возвращаемого типа.

6.2.   Списки захвата в лямбда-выражениях, их синтаксис. Захват по ссылке и по значению. Переменные, не подвергающиеся захвату. Использование mutable для лямбда-выражений. [EMC 6.1]

6.3.   Захват с инициализацией. Захват выражений, не являющихся переменными. [EMC 6.2]

6.4.   Обобщенные лямбда-выражения. Использование decltype в обобщенных лямбда-выражениях. [EMC 6.3]

6.5.   Класс std::function, функция std::bind, placeholder’ы, примеры использования. Применение std::bind для захвата объектов по rvalue-ссылке в С++11. [EMC 6.4]

7.      Программирование на шаблонах и compile-time вычисления (2 лекции)

7.1.   Шаблоны с переменным числом параметров (variadic templates). Синтаксис объявления, использования. Оператор “sizeof…”.

7.2.   Язык шаблонного метапрограммирования в С++, его полнота по Тьюрингу (б/д). Реализация ветвлений (if, switch), циклов (for, while) через язык шаблонов. Примеры: вычисление факториала, вычисление n-го числа Фибоначчи, вывод чисел от 1 до N без использования if/switch/for/while.

7.3.   Заголовочный файл <type_traits>. Шаблоны-модификаторы типов: add/remove const/volatile/reference/pointer, их реализация, пример применения.

7.4.   Шаблоны std::integral_constant, std::true_type, std::false_type. Шаблоны std::conjunction, std::disjunction, std::negation, их реализация. Шаблон std::conditional, его реализация.

7.5.   Идиома SFINAE. Шаблон std::enable_if, его реализация, пример применения. Шаблон std::decay.

7.6.   Шаблон std::declval. Его предназначение, принцип работы.

7.7.   Шаблоны-свойства типов: is_same, is_class, is_union, is_pod и т.п.. Шаблоны std::is_constructible и std::is_convertible, их реализация.

Литература

[EMC] Скотт Мейерс. Эффективный и современный С++. М.: Вильямс, 2016 г.

[DMC] Питер Готтшлинг. Современный C++. Для программистов, инженеров и ученых. М.: Вильямс, 2016 г.

[MEC] Скотт Мейерс. Наиболее эффективное использование С++. М.: ДМК Пресс, 2013 г.

[EC] Скотт Мейерс. Эффективное использование С++. Третье издание. М.: ДМК Пресс, 2006 г.

Вопросы для контроля за второй семестр

Замечание. Всюду, где не указано обратное, подразумевается, что речь идет о версии языка С++14 (свой код также нужно писать в этой версии языка).

В скобках указана сложность вопроса (по некоторой условной шкале).

Вариант 1

  1. (1) Определите шаблонный тип MapIterator<T> как std::map<T, T>::iterator.
  2. (2) Определите пользовательский литерал типа BigInteger. Литерал должен относиться к типу BigInteger, если представляет из себя последовательность цифр, завершаемую буквой b, например, 123456789b.
  3. (2) Рассмотрим следующую программу (считаем, что все необходимые заголовочные файлы подключены):
    union S {
        std::string str;

        std::vector<int> vec;

        ~S() {}

    };

    int main() {

        S s = {"Hello, world"};

        new (&s.vec) std::vector<int>;

        s.vec.push_back(10);

        std::cout << s.str.size() << ' ' << s.vec.size() << '\n';

    }

    Корректен ли этот код? Если нет, объясните, какие потенциальные проблемы он содержит и почему.
  4. (2) Какие из следующих объявлений приведут к ошибке компиляции? В каждом таком случае объясните причину ошибки.
    int& a = 5;
    const int& b = 5;
    int& const c = 5;
    int&& d = 5;
    int const&& e = 5;
    int& f = d;
    int&& h = b;
    int&& g = d;
  5. (2) Каким из следующих функций можно передавать lvalue, а каким - только rvalue?
    void f(int&& x);
    void ff(vector<int>&& x);
    void fff(auto&& x);
    void ffff(const auto&& x);
    template<typename T> class C {
       void g(T&& x);
       void gg(const T&& x);
       template<typename TT> void ggg(TT&& x);
    };
    template<typename T> void h(T&& x);
    template<typename T> void hh(vector<T>&& x);
    template<typename T> void hhh(const T&& x);
  6. (3) Не используя объявлений и определений из заголовочного файла <utility>, напишите функцию move, аналогичную функции std::move из <utility>.
  7. (2) Каким существенным недостатком, с точки зрения эффективности, обладает функция std::vector::push_back в С++03? Приведите пример, когда этот недостаток проявляется. Объясните, как в С++11 устраняется этот недостаток (и как это реализуется).
  8. (2) Пусть есть класс:
    class TreeNode {
       int x;
       std::string s;
       TreeNode *parent, *leftChild, *rightChild;
       // ...
     
     // some methods
    };
    Определите для данного класса конструктор перемещения и перемещающий оператор присваивания так, чтобы move-семантика корректно поддерживалась.
  9. (2) Что такое “ссылочные квалификаторы” (reference qualifiers) в С++? Что они обозначают? Приведите пример их применения.
  10. (2) Пусть есть шаблонная функция “template<typename T> void f(T x)” и ее вызов в main’е с некоторым параметром. Предложите способ на этапе компиляции увидеть, какой тип имеет этот параметр (то есть какой тип компилятор подставил в качестве Т). Объясните, как работает ваш способ.
  11. (2) Рассмотрим следующий класс:
    class Widget {
    public:
       Widget(const Widget&) = default; // 0
       Widget(Widget&&) = default; // 1
       Widget(int i, bool b) {} // 2
       Widget(int i, double d) {} // 3
       Widget(std::initializer_list<long double> il) {} // 4
       operator float() const {}
    };
    Для каждой из следующих строчек кода ответьте, приведет ли она к ошибке компиляции, а если не приведет, то какой из конструкторов Widget будет вызван (подразумевается, что заголовочный файл <utility> подключен):
    Widget w2{10, true};
    Widget w4{10, 5.0};
    Widget w6{w4};
    Widget w8{std::move(w4)};
  12. (2) Вы пишете шаблонный класс TalkativeAllocator<T>, который ведет себя аналогично std::allocator, с той разницей, что выводит на экран сообщения обо всех своих действиях. Не используя сущностей из заголовочного файла <memory>, определите метод TalkativeAllocator<T>::construct. (Он должен принимать то же, что и std::allocator<T>::construct, и делать то же самое, что и упомянутый метод, но предварительно выводить на экран сообщение “Construct method has been called!”.)
  13. (2) Пусть имеется реализованный класс BigInteger. Переопределите для него операцию placement new таким образом, чтобы при каждом ее вызове выводилось сообщение “BigInteger has been created!”, а в остальном все происходило бы как обычно.
  14. (1) Что такое new-handler, в какой ситуации он вызывается? Объясните назначение функций get_new_handler и set_new_handler.
  15. (2) Для чего нужна функция std::make_shared, что она принимает и что возвращает? Почему использование этой функции в С++14 предпочтительнее, чем непосредственный вызов конструктора shared_ptr?
  16. (2) Рассмотрим следующую программу (подразумевается, что все необходимые заголовочные файлы подключены):
    int main() {
       std::vector<std::unique_ptr<int>> vec;
       vec.reserve(10000);
       for (int i = 0; i < 10000; ++i) {
           vec.push_back(std::make_unique<int>(new int(rand())));
       }
       auto cmp = [](auto x, auto y){return *x < *y;};
       std::sort(vec.begin(), vec.end(), cmp);
    }
    Скомпилируется ли она? Если нет, то в каких строчках возникнут ошибки компиляции и почему? Если да, то какие потенциальные проблемы она в себе содержит (undefined behaviour, утечки памяти и т.п.) и почему?
  17. (2) Зачем нужен класс std::enable_shared_from_this? Приведите пример ситуации, когда его нужно использовать.
  18. (2) Рассмотрим следующую программу:
    #include <iostream>
    class FunctionCreater {
    private:
        int divisor;
    public:
        FunctionCreater(int divisor): divisor(divisor) {}
        std::function<int(int)> getFunction() const {
            auto func = [=](int x){return x % divisor;};
            return func;
        }
    };
    int main() {
        auto f = FunctionCreater(5).getFunction();
        auto g = FunctionCreater(10).getFunction();
        std::cout << f(15) << ‘ ‘ << g(15);
    }
    Какую потенциальную проблему она содержит? Почему так происходит? Как нужно исправить код getFunction, чтобы возвращаемая функция работала корректно?
  19. (2) Для чего нужна функция std::bind, что она принимает и что возвращает? Приведите пример ее использования.
  20. (3) Напишите шаблонную функцию print с переменным количеством шаблонных аргументов, которая бы принимала std::tuple с таким набором типов и выводила в std::cout все элементы tuple через пробел.
  21. (2) Не используя сущностей из заголовочного файла type_trais, реализуйте шаблонную структуру IsSame, которая бы работала аналогично std::is_same из type_traits.
  22. (4) Напишите функцию foo, которая ведет себя следующим образом.
    Будучи вызванной от двух параметров, где тип первого параметра - класс или структура С, а второй параметр является указателем на публичную функцию-член класса С, функция foo выводит на экран 1. Будучи же вызванной от любого другого набора параметров, функция foo выводит 0.
    (Подсказка: скорее всего, чтобы достичь такого эффекта, вам потребуется написать две функции с именем foo и разными сигнатурами.)
  23. (2) Напишите шаблонный класс Combinations<int N, int K> с полем static const long long value, значение которого для каждой специализации с конкретным N равнялось бы числу сочетаний из N по K, при условии, что оно не превосходит максимально возможного значения long long. (Для удобства считаем, что глубина шаблонной рекурсии ничем не ограничена.)

Вариант 2

  1. (1) Что такое argument-dependent lookup в С++? Приведите пример.
  2. (2) Объясните значение ключевого слова constexpr. В чем отличие между объявлениями "constexpr int x = 5;" и "const int x = 5;"? В чем заключалось усовершенствование возможностей constexpr в С++14 по сравнению с С++11?
  3. (2) Зачем нужен оператор noexcept? В чем разница между ним и одноименным спецификатором? Приведите пример его применения.
  4. (2) Какие из следующих объявлений приведут к ошибкам компиляции? В каждом таком случае объясните причину ошибки (подразумевается, что заголовочный файл <vector> подключен).
    using std::vector;
    vector<int> a = vector<int>();
    vector<int>&& aa = a;
    const vector<int>&& aaa = a;
    vector<int>&& y = vector<int>();
    vector<int>& yy = y;
    vector<int>&& yyy = y;
    const vector<int>& yyyy = y;
  5. (2) Расшифруйте термины lvalue, rvalue, glvalue, xvalue и prvalue (давать определения не нужно, только расшифровать). Приведите по одному примеру выражений, являющихся lvalue, xvalue и prvalue.
  6. (3) Не используя объявлений и определений из заголовочного файла <utility>, напишите функцию forward, аналогичную функции std::forward из <utility>. (Незначительные различия в деталях допускаются, но в большинстве случаев ваша реализация должна работать корректно.)
  7. (2) В С++14 имеется функция std::exchange со следующей сигнатурой:
    template<typename T, typename U = T>
    T exchange(T& obj, U&& new_value);
    которая эффективно присваивает объекту obj значение new_value, а возвращает его старое значение. Предложите реализацию данной функции, выполняющую описанные действия.
  8. (2) Что такое “универсальные ссылки”? Перечислите ситуации, в которых возникают универсальные ссылки.
  9. (3) Рассмотрим функции
    template <typename T> void f1(T x);
    template <typename T> void f2(T& x);
    template <typename T> void f3(T&& x);
    Для каждого из следующих вызовов укажите, чему будет равно Т и какой тип будет иметь локальная переменная х в теле функции (то есть чему будет равно decltype(x) в теле функции):
    int x;
    int& y = x;
    int&& z = std::move(x);
    f1(x);          f2(x);          f3(x);
    f1(y);          f2(y);          f3(y);
    f1(z);          f2(z);          f3(z);
    f1(5);                          f3(5);
  10. (2) Некто написал функцию, которая по замыслу должна быть оберткой над обращением к STL-контейнеру по индексу, производя вспомогательные действия, а затем возвращая ссылку на запрошенный элемент:
    template<typename Container, typename Index>
    auto& getElementFromContainer(Container& container, Index index) {
       // ... write something to log file
       return container[index];
    }
    Допустим, мы хотим использовать эту функцию для обращения к std::vector. В чем недостатки приведенной реализации? Как нужно исправить данную функцию, чтобы устранить потенциальные проблемы? Поясните ваш ответ.
  11. (2) Рассмотрим такой оператор сложения двух длинных чисел:
    BigInteger operator +(const BigInteger& a, const BigInteger& b) {
       BigInteger sum = a;
       sum += b;
       return sum;
    }
    Имеет ли смысл написать вместо “return sum” “return std::move(sum)”? Аргументируйте свой ответ.
  12. (3) Вам понадобилось логировать всякое динамическое выделение и освобождение памяти в вашей программе. Напишите реализацию глобальных new и delete так, чтобы при каждом выделении памяти выводилось сообщение вида “N bytes allocated”, а при каждом освобождении - “N bytes deallocated”, и только затем память выделялась (соответственно, освобождалась). (Помните о соглашениях, которых нужно придерживаться при реализации этих функций.)
  13. (2) Для чего нужен placement new? Чем он отличается от обычного new? Приведите пример placement new.
  14. а) (1) Сформулируйте проблему, для решения которой был создан класс std::auto_ptr.
    б) (1) Сформулируйте недостаток класса std::auto_ptr, который отсутствует у std::unique_ptr.
  15. (2) Как известно, в С++11 отсутствовала функция std::make_unique. Напишите собственную функцию makeUnique для С++11, которая работала бы аналогично функции std::make_unique.
  16. Рассмотрим следующую программу (подразумевается, что все необходимые заголовочные файлы подключены):
    int main() {
        int* x = new int(5);                    // 1

        std::unique_ptr<int> up(x);             // 2

        std::shared_ptr<int> sp(x);             // 3

        std::weak_ptr<int> wp(x);               // 4

        auto uup = up;                          // 5

        auto ssp = std::shared_ptr<int>(up);    // 6

        auto sssp = std::make_shared<int>(up);  // 7

        std::weak_ptr<double> wwp = sp;         // 8

        auto&& sp2 = sp;                        // 9

        auto&& wwwp = wwp;                      // 10

    }
    а) (2) В каких строчках (для удобства строки пронумерованы) возникнут ошибки компиляции? В каждом случае объясните причину ошибки.
    б) (1) Если закомментировать все строки, вызывающие ошибки компиляции, и запустить программу, отработает ли она корректно? В случае отрицательного ответа поясните, какая ошибка возникнет и почему.
  17. (2) Рассмотрим следующую лямбда-функцию:
    auto logAndProcess = [](const auto& x) {
        std::cout << “logAndProcess has been called!\n”;
        return process(x);
    };
    Предположим теперь, что функция process по-разному обрабатывает lvalue и rvalue. Как надо изменить код logAndProcess, чтобы прямая передача работала правильно (в process должно передаваться rvalue, если и только если в logAndProcess было передано rvalue)?
  18. (2) Объявите и определите лямбда-функцию, которая захватывает перемещением локальный std::vector<int> (назовем его vec), сортирует его стандартным способом и выводит содержимое получившегося вектора в cout. Для удобства можно считать, что все необходимые заголовочные файлы уже подключены.
  19. (3) Реализуйте булеву функцию isHomogeneous с переменным количеством шаблонных аргументов, которая бы принимала std::tuple с таким набором типов и возвращала бы true тогда и только тогда, когда все типы в tuple одинаковые.
  20. (2) Не используя сущностей из файла type_traits, реализуйте шаблонную структуру Conditional, аналогичную std::conditional из type_traits.
  21. (4) Не используя сущностей из файла type_traits, реализуйте шаблонную структуру IsMoveConstructible<T>. В структуре должно быть поле static const bool value, принимающее значение true тогда и только тогда, когда для типа T определен конструктор перемещения.
  22. (2) Напишите шаблонный класс Fibonacci<int N> с полем static const long long value, значение которого для каждой специализации с конкретным N равнялось бы N-му числу Фибоначчи, при условии, что это число не превышает максимальное значение типа long long. (Для удобства считаем, что глубина шаблонной рекурсии ничем не ограничена.)


Bonus

Последняя задача из домашних заданий второго семестра, пользовавшаяся особой популярностью во время сдач.

Задача 4. Effective Modern Dynamic Programming

У маленького мальчика Илюши было k клетчатых досочек размеров M_i на N_i, где M_i <= 6, N_i <= 100. Дома по вечерам, когда все взрослые смотрели программу “Время”, он любил делать замощения этих досочек доминошками размера 1х2. Однажды ему пришел в голову вопрос: а сколькими различными способами он может замостить каждую из этих досочек по модулю 1000000007?

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

const int MODULUS = 1000000007;

#include “ahalaimahalai”
#include <iostream>

int main() {
    std::cout << AhalaiMahalai<M_1, N_1>::value << ‘\n’;
    std::cout << AhalaiMahalai<M_2, N_2>::value << ‘\n’;

    ...
    std::cout << AhalaiMahalai<M_k, N_k>::value << ‘\n’;

То есть на самом деле внутри функции main() он написал k строк кода - по одной строке для каждой пары M_i, N_i, где вместо M_i и N_i подставил конкретные числа (нам они, увы, неизвестны). В остальном его программа выглядела именно так, как написано выше.

Увидев это, к Илюше подошел дедушка и сказал: “Глупый ты, глупый мальчик Илюша! Ничего ты такой программой посчитать не сможешь! В хороших, годных программах обязательно есть слово define и слово goto. А в твоей программе нет даже ветвлений (if, switch, тернарный оператор), даже циклов (for, while, do). Так что ничего у тебя не получится, если ты, конечно, сам не посчитаешь ответы для всех M_i, N_i каким-то другим способом и не запишешь эти готовые ответы в программу. Эх, Илюша, не умеешь ты программировать”.

Илюша страшно обиделся и сказал: “Нет, дедушка! Это ты ничего не понимаешь! Эффективные и современные программы на С++ обходятся без всего того, что ты назвал! И я тебе это докажу!”.

Но доказать так и не сумел. И к кому бы вы думали он обратился за помощью? Конечно, к Вам.

Напишите код файла ahalaimahalai так, чтобы Илюшина программа выводила желаемое, но при этом файл бы не содержал ничего того, что перечислил дедушка. Более формально:

Замечание. Когда вы будете тестировать свою программу, скорее всего, вам понадобится при компиляции добавить параметр -ftemplate-depth=20000.