Группа Михайлова — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
 
(не показано 29 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
=Правила жизни=
 +
За успешную сдачу практической работы на паре, на которой она была задана студент получает 2 балла рейтинга.
 +
За успешную сдачу на следующей паре - один балл.
 +
На следующей паре первоначальное задание разбирается. И сдача такого задания оценивается уже в пол балла.
 +
 +
Проверка работ по электронной почте осуществляется только в экстренных случаях. (Болезнь, например).
 +
 +
Для получения зачета необходимо набрать некоторе количествоо баллов. Точное значение будет определено позже.
 +
Те, кто их не набрал - будут выполнять дополнительные задания.
 +
 +
=Общее=
 +
[https://docs.google.com/spreadsheet/ccc?key=0AhBJfSfjgJfGdEw1RlNXeWhlY1M0MGJacXQ1WXM0d2c&pli=1#gid=0 Результаты]
 +
 +
=Интересные ссылки=
 +
[http://pages.cs.wisc.edu/~driscoll/typename.html O typename]
 +
 +
[http://habrahabr.ru/post/112953/ Об арифметике с плавающей запятой]
 +
 +
[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]
 +
 +
=Осенний семестр=
 
==Компиляция==
 
==Компиляция==
  
Строка 71: Строка 94:
  
 
==Smart FILE==
 
==Smart FILE==
 +
==Rational==
 +
Напишите класс работающий с рациональными числами и определите следующие операторы:
 +
* ostream <<
 +
* istream >>
 +
* +=
 +
* -=
 +
* *=
 +
* /=
 +
* +
 +
* - бинарный
 +
* - унарный
 +
* *
 +
* /
 +
* ++ префиксный
 +
* ++ постфиксный
 +
* -- префиксный
 +
* -- постфиксный
 +
* ==
 +
* !=
 +
* <
 +
* >
 +
* <=
 +
* >=
 +
 +
==Smart pointers==
 +
Реализовать шаблонный scoped_ptr
 +
[http://www.boost.org/doc/libs/1_52_0/libs/smart_ptr/scoped_ptr.htm]
 +
 +
 +
=Весенний семестр=
 +
==Задание 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 нельзя. Необходимо гарантировать отсутствие хеш коллизий для строк. Поскольку сделать это для любых строк невозможно - разрешается
 +
устанавливать ограничение на максимальную длину строк. Однако это ограничение должно быть аргументированно.

Текущая версия на 14:19, 22 мая 2013

Правила жизни

За успешную сдачу практической работы на паре, на которой она была задана студент получает 2 балла рейтинга. За успешную сдачу на следующей паре - один балл. На следующей паре первоначальное задание разбирается. И сдача такого задания оценивается уже в пол балла.

Проверка работ по электронной почте осуществляется только в экстренных случаях. (Болезнь, например).

Для получения зачета необходимо набрать некоторе количествоо баллов. Точное значение будет определено позже. Те, кто их не набрал - будут выполнять дополнительные задания.

Общее

Результаты

Интересные ссылки

O typename

Об арифметике с плавающей запятой

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

  1. HashMap<TKey, TValue, TTraits = SomeDefaultTraits<TKey>>, TKey - тип ключа, TValue - тип значения
  2. TTraits - некоторый тип, определяющий как именно будет вычисляться хеш-значение для ключа, а также сравнение с другими ключами. Реализация по-умолчанию должна уметь работать со всеми встроенными типами
  3. Для упрощения реализации количество ячеек в массиве можно считать константным
  4. Обязательные для реализации функции
    1. begin()/end() - функции, возвращающие итераторы начала/конца таблицы. Тип итерируемых элементов - std::pair<TKey, TValue>
    2. TValue & operator[](TKey) - оператор, возращающий значение по ключу. Если такого ключа в коллекции нет - он создается вместе со значением TValue по-умолчанию.
    3. iterator lower_bound(TKey) - возвращает итератор на искомый элемент. Если такого нет - возвращает итератор, равный end()
    4. iterator insert(std::pair<TKey, TValue>) - помещает пару ключ-значение в таблицу. Возвращает итератор на место, в которое элемент был вставлен. Если в таблице уже существует пара с таким же ключем - сгенерировать ошибку. Например, поделив на ноль =)
    5. void remove(TKey) - угадайте с трех раз
  5. Дополнительно
    1. Представляемая реализация должна работать с любыми примитивными типами "из коробки" т.е. без явного указания traits.
    2. Помимо примитивных типов, реализовать поддержку std::string и любого своего поля, хеш для когорого считается из более чем двух полей.
    3. Для вычисления хеша запрещается использовать готовые функции из std. (std::hash_value)
    4. Протестировать как минимум на следующем коде: 
 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) Методы

  1. Конструктор от одного аргумента - размер матрицы
  2. copy ctor/operator=/dtor
  3. 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 нельзя. Необходимо гарантировать отсутствие хеш коллизий для строк. Поскольку сделать это для любых строк невозможно - разрешается устанавливать ограничение на максимальную длину строк. Однако это ограничение должно быть аргументированно.

Источник — «http://mit.spbau.ru/sewiki/index.php?title=Группа_Михайлова&oldid=2471»