Группа Михайлова — различия между версиями
AM5800 (обсуждение | вклад) (→Задание 1) |
AM5800 (обсуждение | вклад) |
||
(не показано 15 промежуточных версий этого же участника) | |||
Строка 18: | Строка 18: | ||
[http://herbsutter.com/2013/01/01/video-you-dont-know-const-and-mutable/ You don't know const and mutable] | [http://herbsutter.com/2013/01/01/video-you-dont-know-const-and-mutable/ You don't know const and mutable] | ||
+ | |||
+ | [http://msdn.microsoft.com/en-us/library/e5ewb1h3(v=vs.80).aspx Memory leaks detection in Visual Studio] | ||
=Осенний семестр= | =Осенний семестр= | ||
Строка 152: | Строка 154: | ||
std::copy(magic1, magic2, std::ostreambuf_iterator<char>(std::cout)); | std::copy(magic1, magic2, std::ostreambuf_iterator<char>(std::cout)); | ||
Должен вывести на экран "aaa". (magic1&2 - это собственно способ задания итератора. Он остается на ваше усмотрение) | Должен вывести на экран "aaa". (magic1&2 - это собственно способ задания итератора. Он остается на ваше усмотрение) | ||
+ | |||
+ | ==Algorithms== | ||
+ | Реализовать на выбор любые 2 алгоритма из списка | ||
+ | std::random_shuffle | ||
+ | std::rotate | ||
+ | std::reverse | ||
+ | |||
+ | ==Указатели на функции== | ||
+ | Используя libexpat распарсить http://img.lenta.ru/r/EX/yandexfull.rss | ||
+ | Сгруппировать новости по категориям и вывести заголовки. | ||
+ | |||
+ | Дополнительное задание (1 балл максимум): | ||
+ | Реализовать std::ptr_fun и std::bind | ||
+ | |||
+ | ==Исключения== | ||
+ | Реализовать класс квадратной матрицы. Уделить особое внимание обработке исключений (bad_alloc, out of range) | ||
+ | Методы | ||
+ | # Конструктор от одного аргумента - размер матрицы | ||
+ | # copy ctor/operator=/dtor | ||
+ | # operator[] реализованный так, чтобы было возможно использовать его как m[9][10] | ||
+ | При возникновении каких-либо проблем при конструировании объекта Matrix необходимо обработать эти проблемы и не допустить утечки памяти. | ||
+ | Используйте ручное управление памятью (new/delete) | ||
+ | Память под матрицу выделять "построчно" | ||
+ | |||
+ | ==Гарантии безопасности исключений== | ||
+ | Реализовать ini-парсер. Пример работы с таким классом | ||
+ | ini_parser parser("settings.ini"); | ||
+ | std::string key1 = parser.get_string("General", "Key1"); | ||
+ | int n = parser.get_int("General", "Key2"); // Если значение Key2 не может быть преобразовано к Int - сгенерировать исключение | ||
+ | parser.set_int("NewSection", "Key1", n); | ||
+ | parser.write("settings2.ini"); | ||
+ | |||
+ | ==RTTI== | ||
+ | Реализовать парадигму multiple dispatch | ||
+ | Asteroid ra1, ra2; | ||
+ | Spaceship rs1, rs2; | ||
+ | Object &a1 = ra1; | ||
+ | Object &a2 = ra2; | ||
+ | Object &s1 = rs1; | ||
+ | Object &s2 = rs2; | ||
+ | a1.CollideWith(a2); | ||
+ | a1.CollideWith(s1); | ||
+ | s1.CollideWith(s2); | ||
+ | s1.CollideWith(a1); | ||
+ | Доп. задание: реализовать то же самое тремя различными способами. | ||
+ | |||
+ | ==C++11== | ||
+ | Реализовать вектор, используя (осмысленно) как можно больше новых механизмов C++11 (делегирующие конструкторы, список инициализации, foreach, move semantics, auto и прочие) | ||
+ | |||
+ | ==C++11 2== | ||
+ | Реализовать switch для строк: | ||
+ | |||
+ | std::string s = ... | ||
+ | SWITCH(s) { | ||
+ | CASE("ONE"): ... | ||
+ | CASE("TWO"): ... | ||
+ | } | ||
+ | |||
+ | Разворачивать в if-else нельзя. Необходимо гарантировать отсутствие хеш коллизий для строк. Поскольку сделать это для любых строк невозможно - разрешается | ||
+ | устанавливать ограничение на максимальную длину строк. Однако это ограничение должно быть аргументированно. |
Текущая версия на 14:19, 22 мая 2013
Правила жизни
За успешную сдачу практической работы на паре, на которой она была задана студент получает 2 балла рейтинга. За успешную сдачу на следующей паре - один балл. На следующей паре первоначальное задание разбирается. И сдача такого задания оценивается уже в пол балла.
Проверка работ по электронной почте осуществляется только в экстренных случаях. (Болезнь, например).
Для получения зачета необходимо набрать некоторе количествоо баллов. Точное значение будет определено позже. Те, кто их не набрал - будут выполнять дополнительные задания.
Общее
Интересные ссылки
Об арифметике с плавающей запятой
You don't know const and mutable
Memory leaks detection in Visual Studio
Осенний семестр
Компиляция
Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция for:
for (int i = 0; i < N; ++i) { //body }
Пример псевдокода:
if (a == 5) goto mark1 something mark1:
Чем плоха конструкция
#define MAX(a, b) a > b ? a : b
Приведите пример ее некорректного использования. (Возврат не максимального значения, побочные эффекты) Как можно ее улучшить?
Как работает линковка? Какую роль в ней играет relocation table
Сортировка слиянием
Реализуйте алгоритм merge sort
Выделение памяти
Создайте двумерный массив двумя способами. 1) Используя N + 1 аллокацию 2) Используя 2 аллокации Замерьте, при каких значениях размера массива происходит экстерминатус? (Компилируйте 32 разрядную версию. 64 может и не упасть) Какой вариант работает быстрее? Подумайте, почему это происходит. Обращаю внимание, что оба варианта созданных матриц должны иметь тип int**
Усложненное задание - сделать матрицы трегольными и написать процедуру, сливающие 2 такие матрицы в прямоугольную
Расширяющийся массив
Реализуйте класс расширяющегося массива. Size - количество элементов в массиве. Capacity - вместимость массива. Size <= Capacity Если при добавлении очередного элемента Size превышает Capacity, то Capacity следует увеличить вдвое
struct Array { Array(size_t capacity = 3); Array(Array & array); ~Array(); Array & operator=(Array & array); size_t Size(); size_t Capacity(); void Add(int value); int Get(size_t index); void Set(size_t index, int value); void Swap(Array & array); private: int* myData; size_t mySize; size_t myCapacity; };
Обертка над FILE
String
Реализовать класс String со следующими методами/требованиями
String() String(String &) String(char *) operator=(String &) operator=(char *) //реализовывать не нужно. Объясните, почему? append(String &) char ? at(size_t) // реализовать в двух версиях. Константную и не константную char * c_str() - возвращает обычную нуль-терминированную строку
Данные хранить как буффер для строки и ее размер. Строку хранить НЕ как нуль-терминированную. В приведенном выше ключевое слово const не используется умышленно.
Дополнительное задание - реализовать строку с таким же интерфейсом, но реализующую стратегию Copy On Write (COW)
Smart FILE
Rational
Напишите класс работающий с рациональными числами и определите следующие операторы:
- ostream <<
- istream >>
- +=
- -=
- *=
- /=
- +
- - бинарный
- - унарный
- *
- /
- ++ префиксный
- ++ постфиксный
- -- префиксный
- -- постфиксный
- ==
- !=
- <
- >
- <=
- >=
Smart pointers
Реализовать шаблонный scoped_ptr [1]
Весенний семестр
Задание 1
Реализовать алгоритм merge sort для сортировки произвольных контейнеров. Специализировать алгоритм так, чтобы для некоторых контейнеров он работал эффективнее. Например: list vs vector
HashMap
- HashMap<TKey, TValue, TTraits = SomeDefaultTraits<TKey>>, TKey - тип ключа, TValue - тип значения
- TTraits - некоторый тип, определяющий как именно будет вычисляться хеш-значение для ключа, а также сравнение с другими ключами. Реализация по-умолчанию должна уметь работать со всеми встроенными типами
- Для упрощения реализации количество ячеек в массиве можно считать константным
- Обязательные для реализации функции
- begin()/end() - функции, возвращающие итераторы начала/конца таблицы. Тип итерируемых элементов - std::pair<TKey, TValue>
- TValue & operator[](TKey) - оператор, возращающий значение по ключу. Если такого ключа в коллекции нет - он создается вместе со значением TValue по-умолчанию.
- iterator lower_bound(TKey) - возвращает итератор на искомый элемент. Если такого нет - возвращает итератор, равный end()
- iterator insert(std::pair<TKey, TValue>) - помещает пару ключ-значение в таблицу. Возвращает итератор на место, в которое элемент был вставлен. Если в таблице уже существует пара с таким же ключем - сгенерировать ошибку. Например, поделив на ноль =)
- void remove(TKey) - угадайте с трех раз
- Дополнительно
- Представляемая реализация должна работать с любыми примитивными типами "из коробки" т.е. без явного указания traits.
- Помимо примитивных типов, реализовать поддержку std::string и любого своего поля, хеш для когорого считается из более чем двух полей.
- Для вычисления хеша запрещается использовать готовые функции из std. (std::hash_value)
- Протестировать как минимум на следующем коде:
HashMap<int, int> hm; for (int i = 0; i < N; ++i) hm[i] = i; for (int i = 0; i < N; ++i) if (i != hm[i]) std::cout << ...;
Где N в несколько (>=4) раз больше числа "бакетов".
Iterator
Реализовать итератор, "ходящий" по строке, пропуская цифры. В частности код:
std::string s = "aa44a"; std::copy(magic1, magic2, std::ostreambuf_iterator<char>(std::cout));
Должен вывести на экран "aaa". (magic1&2 - это собственно способ задания итератора. Он остается на ваше усмотрение)
Algorithms
Реализовать на выбор любые 2 алгоритма из списка
std::random_shuffle std::rotate std::reverse
Указатели на функции
Используя libexpat распарсить http://img.lenta.ru/r/EX/yandexfull.rss Сгруппировать новости по категориям и вывести заголовки.
Дополнительное задание (1 балл максимум): Реализовать std::ptr_fun и std::bind
Исключения
Реализовать класс квадратной матрицы. Уделить особое внимание обработке исключений (bad_alloc, out of range) Методы
- Конструктор от одного аргумента - размер матрицы
- copy ctor/operator=/dtor
- operator[] реализованный так, чтобы было возможно использовать его как m[9][10]
При возникновении каких-либо проблем при конструировании объекта Matrix необходимо обработать эти проблемы и не допустить утечки памяти. Используйте ручное управление памятью (new/delete) Память под матрицу выделять "построчно"
Гарантии безопасности исключений
Реализовать ini-парсер. Пример работы с таким классом
ini_parser parser("settings.ini"); std::string key1 = parser.get_string("General", "Key1"); int n = parser.get_int("General", "Key2"); // Если значение Key2 не может быть преобразовано к Int - сгенерировать исключение parser.set_int("NewSection", "Key1", n); parser.write("settings2.ini");
RTTI
Реализовать парадигму multiple dispatch
Asteroid ra1, ra2; Spaceship rs1, rs2; Object &a1 = ra1; Object &a2 = ra2; Object &s1 = rs1; Object &s2 = rs2; a1.CollideWith(a2); a1.CollideWith(s1); s1.CollideWith(s2); s1.CollideWith(a1);
Доп. задание: реализовать то же самое тремя различными способами.
C++11
Реализовать вектор, используя (осмысленно) как можно больше новых механизмов C++11 (делегирующие конструкторы, список инициализации, foreach, move semantics, auto и прочие)
C++11 2
Реализовать switch для строк:
std::string s = ... SWITCH(s) { CASE("ONE"): ... CASE("TWO"): ... }
Разворачивать в if-else нельзя. Необходимо гарантировать отсутствие хеш коллизий для строк. Поскольку сделать это для любых строк невозможно - разрешается устанавливать ограничение на максимальную длину строк. Однако это ограничение должно быть аргументированно.