Версия 20:44, 26 февраля 2013

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

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

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

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

Общее

Результаты

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

O typename

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

You don't know const and mutable

Осенний семестр

Компиляция

Напишите псевдо код на основе ассемблерного кода в который разворачивается инструкция 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 - это собственно способ задания итератора. Он остается на ваше усмотрение)