С++, 322 гр., спец. САПР/MM

Место и время проведения: вторник, первая пара, аудитория 2410.
Преподаватель: Шлемов Александр Юрьевич shlemovalex@gmail.com


Методические материалы и примеры

Темы и материалы к занятиям

17 февраля

  1. Краткий рассказ об истории ООП, основные понятия
  2. «Хотелки» (мотивация для применения ООП): Изолированность, Консистентность, Модульность; Повторное использование кода, Расширяемость, Масштабируемость; Абстракция
  3. «Инструменты ООП»: Инкапсуляция, Наследование, Полиморфизм
  4. От структур к классам, методы (функции-члены)
  5. Приватные поля и приватные методы, инкапсуляция
  6. Конструкторы и деструкторы

Задание
Оформить динамический массив в виде класса с конструктором, деструктором и методами доступа.

24 февраля

  1. const-методы класса
  2. Перегрузка обычных операторов (+, -, *, /)
  3. Перегрузка приведения типа
  4. Перегрузка оператора присваивания (copy assignment)
  5. Перегрузка конструктора, конструктор как приведение типа, explicit
  6. =delete и =default
  7. Блок инициализации в конструкторе
  8. Копирующий конструктор (copy constructor)

3 марта

  1. Снова про копирующий конструктор
  2. Move semantics и copy elision
  3. «Разрушающая» ссылка (rvalue reference)
  4. Move constructor
  5. Move assignment
  6. std::move, swap через move, std::swap
  7. Самостоятельная работа и консультации

10 марта

  1. Еще раз про move, copy, swap (повторение)
  2. move через swap полей
  3. Самостоятельная работа и консультации

17 марта

  1. Комбинирование объектов. Агрегация (HAS)
  2. Понятие «владения»
  3. Наследование (IS)
  4. Наследование и конструкторы/деструкторы
  5. Наследование и перегрузка методов
  6. Обращение к полю/методу родителя
  7. Приведение типа при наследовании
  8. О невозможности полноценного полиморфизма через указатели

Задание
Отнаследоваться от имеющегося класса массива таким образом, чтобы получился кольцевой массив, т.е. индекс брался по модулю длины. После чего вынести общую часть из двух классов в общий (абстрактный) класс и отнаследовать от него два массива, обычный и кольцевой.

24 марта

  1. Виртуальные методы
  2. Безопасное (dynamic_cast) и опасное (static_cast) приведение типа для классов
  3. Чисто виртуальные (pure virtual, abstract) методы

31 марта — 7 апреля

  1. Самостоятельная работа, консультирование по домашним заданиям

14 апреля

  1. Введение в шаблоны
  2. Стандартная библиотека STL
  3. iostream, std::cin, std::cout
  4. fstream
  5. Основные контейнеры: std::vector, std::list, std::map, std::set

21 апреля

  1. std::string
  2. Итераторы, for each
  3. std::pair, make_pair
  4. std::sort
  5. Самостоятельная работа

28 апреля

  1. Самостоятельная работа
  2. Стандартные алгоритмы: std::sort

5 мая

  1. Стандартные алгоритмы std::copy, std::equal_range, etc
  2. Идея «сборки мусора»
  3. Умные («одетые») указатели std::unique_ptr, std::shared_ptr, std::weak_ptr

12 мая

  1. Коротко темах, которые не вошли в курс: лямбда-функции и замыкания, регулярные выражения, многопоточность, стандартные библиотеки для решения различных задач (boost, Qt, BLAS/LAPACK, gsl, CGAL, Eigen, etc)
  2. Заключительное слово

Дополнительные темы

  1. Функциональные объекты, лямбда-функции, std::function
  2. Замыкания
  3. Проблема виртуальных конструкторов, методы-фабрики

Задачи

1 2 3 4 5
1. Корчажников Федор + +? + +? +
2. Круглова Валентина + + + + +
3. Сальников Дмитрий + +
4. Ширинкина Дарья + + + +? +
5. Ролдугин Пётр +
6. Григорьева Ирина + + + + +
7. Агеев Владимир + + + + +
8. Гориславский Ростислав + + + +? +

Номер Вашего варианта = Ваш номер в таблице выше. Если у Вас нет задания, Вы нашли ошибку или формулировка не до конца ясна, просьба отправить мне запрос по почте. Обозначения: плюсик — задача зачтена, вопрос — решение отправлено на доработку (т.е. я жду исправлений).

(1) Динамический массив Оформить динамический массив в виде класса. Реализовать для него все шесть специальных методов (default constructor, destructor, copy constructor, move constructor, assignment, move assignment) а также перегрузить оператор subscript ([]), с const и без. Опционально, сделать массив расширяющимся, перегрузить оператор сложения для склейки массивов.

(2) Комплексные числа Реализовать класс для работы с комплексными числами. Корректно перегрузить арифметические операции, приведение типа. Специальные методы оставить стандартными.

(3) Фигуры Написать программу, состоящую из нескольких классов геометрических фигур. Фигура, Треугольник, Квадрат, Круг. Фигура — базовый класс, остальные — его наследники. В базовом классе объявить методы: площадь, периметр и метод introduce. Метод introduce должен выводить на экран сообщение-приветствие для фигуры: ее тип, площадь, периметр. Для наследников определить конструкторы с достаточными параметрами (для круга, к примеру, радиус) и реализовать методы базового класса. Далее в main() создается массив длины N (к примеру, 20) указателей на Фигура и заполняется случайными фигурами со случайными параметрами. Далее пройтись по массиву в цикле и вывести для каждой фигуры вызвать метод introduce(), затем корректно удалить все созданные объекты.

(4) Шаблонная сортировка Реализовать свой алгоритм шаблонной сортировки. Функция должна принимать три параметра: два указателя (или random-access итератора) и функтор сравнения less, задающий порядок).

(4*) Обобщенное расстояние Левенштейна (это альтернатива предыдущему заданию, для тех, кому оно кажется слишком простым. Предполагается, что Вы самостоятельно освоили соответствующие разделы, например, по Страуструпу) Написать шаблонную функцию, которая позволяет считать расстояние Левенштейна между произвольными последовательностями s1, s2 элементов произвольного типа T. Каждая последовательность задается в виде двух итераторов (шаблонного типа). Расстояние Левенштейна определяется как наименьшая стоимость трансформации s1 → s2 с помощью операций замены, вставки и удаления элемента Само расстояние параметризуется тремя функционалами:

  1. M: T x T → R+, «стоимость» превращения одного символа. M имеет смысл расстояния (необязательно симметричного).

Свойства: M(x, y) >= 0; M(x, x) == 0; M(x, y) + M(y, z) >= M(x, z) для любых x, y, z из T. Типичные примеры — M(x, y) := |x - y| для чисел, M(x, y) := I(x != y) для символов.

  1. A: T → R+, «стоимость» добавления элемента в s1
  2. D: T → R+, «стоимость» удаления элемента из s1

Функционалы должны передаваться как обычные (нешаблонные) параметры типа std::function<…> (или как все то, что к нему неявно приводится). Перегрузить функцию для контейнеров (т.е. для объектов с методами begin(), end()). Функция должна корректно работать для последовательностей элементов одного типа, но заданных различными контейнерами, к примеру, должна быть возможность посчитать расстояние от списка std::list<double> до вектора std::vector<double>. В случае несовпадения типа хранимых элементов выдавать ЧИТАЕМУЮ ошибку (используйте static_assert). Сам алгоритм подсчета обобщенного расстояние Левенштейна совпадает с обычным, динамическое программирование за O(|s1|*|s2|), при этом реализовать его нужно так, чтобы он требовал минимально возможное количество памяти O(min{|s1|, |s2|}). Обязательны Unit-тесты, в частности, рекомендуется проверить варианты, когда последовательности состоят из символов, расстояние I(x != y); вещественные числа, расстояние эвклидово; строки (т.е. строка из строк), расстояние — обычное расстояние Левенштейна. Еще необходимо проверить корректность для случая несимметричной функции M (но это лучше сделать на строках вида ACGTTTTTAACGT, задавая M с помощью матрицы расстояний 4×4)

(5) Записная книжка Взять задание «Записная книжка» из прошлого года и переделать его, используя средства C++ и STL (т.е. использовать вместо своей реализации словаря встроенный std::map, вместо char*-строк использовать std::string, etc). Постараться сделать код как можно более простым и компактным.

Посещаемость

17.0224.0203.0310.0317.0324.0331.0307.0414.0421.0428.0405.0512.0519.05
1. Корчажников Федор + + + + + + + + + + + + +
2. Круглова Валентина + + + + + - - + + + + + +
3. Сальников Дмитрий + + + - + + + + + + + + +
4. Ширинкина Дарья + + + + + + + + + + + + +
5. Ролдугин Пётр + + + + - + + + + + + + +
6. Григорьева Ирина + + + + + + + + + + + + +
7. Агеев Владимир + + + + + + + + + - + + +
8. Гориславский Ростислав - + - - - + - - + - - - +

Литература (и другие источники)

  1. Г. Шилдт. Полный справочник по C++ Довольно классическая книжка, сильно ее рекомендую. Мой стиль и порядок изложения в целом соответствует ей. Последнее издание — четвертое, есть и по-русски, и по-английски. Книга очень известна, хорошо доступна. Однако книга далеко не новая, из-за чего некоторые вещи выглядят устаревшими.
  2. C++ Для чайников Несмотря на провокационное название, довольно приличная книга. Хорошее введение для начинающих с правильно поставленными акцентами. Есть русская и английская версия, при этом русский перевод очень приличный. Особенно приятно, что книга новая (точнее, новое переиздание) и она учитывает новые стандарты языка. Однако многие подробности в ней опущены, не следует рассматривать ее как руководство.
  3. The C++ Programming Language (4th Edition) Новое издание легендарной книги от создателя языка. Очень достойный и исчерпывающий источник, но для начинающих, пожалуй, тяжеловата.
  4. http://cplusplus.com/ Всякая инфа по языку и документация по использованию встроенной библиотеки с примерами. Коротко и удобно.
  5. http://en.cppreference.com/w/ Аналогично предыдущему ресурсу.
  6. C++11 Standard latest draft Последний черновой вариант1) актуального стандарта C++. Чтение не очень захватывающее, документ пропитан духом формализма. Но позволяет точно ответить на вопрос «А как это должно быть на самом деле?» 2)
  7. C++14 Standard latest draft Последний черновой вариант новейшего (будущего) стандарта C++
  8. C++11/14 compiler and library shootout Сводная таблица по поддержке новых возможностей различными компиляторами.
  9. MSDN C++ Позволяет ответить на вопрос «А как же оно на самом деле работает» применительно к майкрософтовской реализации C++ (Visual C++). В целом, удобная онлайн-справка по языку и Visual Studio IDE. Некоторыми признается вообще лучшей документацией по языку.
1)
за окончательный вариант стандарта ISO требует весьма круглую сумму денег, но последний черновик отличается от окончательно варианта в исключительно мелких деталях (если не ошибаюсь, двумя опечатками), поэтому простые смертные обычно довольствуются этим самым черновиком. Впрочем, существуют и другие пути получения финальной версии стандарта
2)
Ключевое слово здесь должно. Дело в том, что на данный момент поддержка распространенными компиляторами Стандарта является далеко неполной
study/spring2015/3cpp_sapr.txt · Последнее изменение: 2015/05/18 23:57 — ash
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0