Задания по С++ — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Задание merge sort)
(Лабораторная работа №12 метапрограммирование smart_print)
 
(не показано 13 промежуточных версий 5 участников)
Строка 1: Строка 1:
== Лабораторная работа №1 ==
+
== Лабораторная работа №1 Шаблоны ==
 +
Реализовать собственный контейнер
 +
<source lang="cpp">template<typename T>
 +
class Container {
 +
public:
 +
    void push_back(const T& t);
 +
    T& back();
 +
    size_t size() const;
 +
};</source>
 +
В качестве хранилища значенией в реализации <code>Container</code> используйте <code>std::vector</code>.
  
Задание
+
Затем создайте новый контейнер с двумя шаблонными параметрами, первый - тип хранимых значений, второй - тип хранилища, используемый в реализации вашего контейнера.
  
== Лабораторная работа №2 ==
+
Пример использования такого контейнера
 +
<source lang="cpp">
 +
Container<int, std::list<int> > c;
 +
</source>
  
Задание
+
Затем создайте новый контейнер с двумя шаблонными параметрами, первый - тип хранимых значений, второй - шаблон, используемый в реализации вашего контейнера.
  
== Лабораторная работа №3 ==
+
Пример использования такого контейнера
 +
<source lang="cpp">
 +
Container<int, std::deque> c;
 +
</source>
  
=== Задание merge sort ===
+
== Лабораторная работа №2 Синглтон ==
 +
 
 +
Написать простой логгер
 +
<source lang="cpp">class Logger {
 +
public:
 +
    void warn(const std::string& msg);
 +
    static Logger& getInstance();
 +
};
 +
</source>
 +
Запретить пользователю его создание, копирование.
 +
 
 +
Пример использования
 +
<source lang="cpp">
 +
Logger& log = Logger::getInstance();
 +
log.warn("Ooops");
 +
</source>
 +
 
 +
Представить, что понадобилось ещё несколько синглтонов, вынести общий для всех синглтонов код в отдельный класс <code>Singleton</code>.
 +
Реализовать логгер с использованием класса <code>Singleton</code> так, чтоб код, использующий логгер, не надо было модифицировать.
 +
 
 +
== Лабораторная работа №3 merge sort ==
 
Необходимо написать функцию сортировки слиянием.<br />
 
Необходимо написать функцию сортировки слиянием.<br />
 
Сигнатура функции должны быть такой:<br />
 
Сигнатура функции должны быть такой:<br />
<source lang="cpp">template<typename Iter><br />
+
<source lang="cpp">template<typename Iter>
 
std::list<typename Iter::value_type> mergeSort(Iter left, Iter right);</source><br />
 
std::list<typename Iter::value_type> mergeSort(Iter left, Iter right);</source><br />
 
Исходные данные функция модифицировать не должна, в возвращаемом списке должны быть отсортированные элементы.
 
Исходные данные функция модифицировать не должна, в возвращаемом списке должны быть отсортированные элементы.
  
 
Затем необходимо добиться, чтоб можно было сортировать по указателям:<br />
 
Затем необходимо добиться, чтоб можно было сортировать по указателям:<br />
<source lang="cpp">int* array = new int[SIZE];<br />
+
<source lang="cpp">int* array = new int[SIZE];
 
mergeSort(array, array + SIZE);</source>
 
mergeSort(array, array + SIZE);</source>
  
Строка 23: Строка 58:
 
для получения типа, на который указывает указатель, можно воспользоваться <code>std::iterator_traits</code>
 
для получения типа, на который указывает указатель, можно воспользоваться <code>std::iterator_traits</code>
  
== Лабораторная работа №4 ==
+
== Лабораторная работа №4 iterator ==
 +
Написать шаблонный класс <code>slist</code> односвязный список.<br />
 +
<source lang="cpp">template<typename _Ty>
 +
class slist {
 +
public:
 +
  push_back(const _Ty&);
 +
  forward begin();
 +
  forward end();
 +
  slist();
 +
  _Ty back() const;
 +
};
 +
</source>
 +
Реализовать для него <code>forward</code> итератор.
 +
 
 +
== Лабораторная работа №5 functor ==
 +
Реализовать алгоритм
 +
<source lang="cpp">
 +
template<typename InIter, typename OutIter, typename Pred>
 +
OutIter filter(InIter begin, InIter end, OutIter out, Pred pred);
 +
</source>
 +
который читает элементы и, если <code>pred(val)</code> возвращает <code>true</code>, то записывает элемент в <code>out</code>.
 +
 
 +
Реализовать собственный функтор, который принимает <code>std::set<char></code> и <code>char</code> и проверят наличие входного символа в сете.
 +
С помощью алгоритма <code>filter</code> и вашего функтора отфильровать строку.
 +
 
 +
== Лабораторная работа №6 mem_fun ==
 +
Реализовать аналог <code>std::mem_fun</code>, убедиться, что аналог работает на коде:
 +
<source lang="cpp">
 +
std::vector<char> v;
 +
std::set<int> s;
 +
mem_fun(&std::vector<char>::push_back)(v, 'd');
 +
mem_fun(&std::set<int>::count)(s, 3);
 +
</source>
 +
 
 +
== Лабораторная работа №7 заполнитель мапы ==
 +
Реализовать заполнитель мапы
 +
<source lang="cpp">
 +
std::map<float, int> m(mapper(1.0, 2)(2, 2)(4, 2));
 +
</source>
 +
 
 +
== Лабораторная работа №8-9 класс матрицы ==
 +
Реализовать класс матрицы MxN (с двумя выделениями памяти).<br/>
 +
Спроектировать его с учётом исключений: безопасный, с декларацией бросаемых исключений.
 +
 
 +
== Лабораторная работа №10 двойная диспетчерезация ==
 +
Иногда в больших системах возникает потребность в некоторой бинарной операции, которая полиморфно зависит от типов обоих аргументов.
 +
 
 +
Пример: пересечение геометрических примитивов. Мы умеем пересекать круги с кругами, прямоугольники с прямоугольниками и прямоугольники с кругами. Нужно реализовать функцию <code>bool intersects(Shape * a, Shape * b);</code>
 +
 
 +
Ваше задание: написать механизм, который позволил бы реализовать двойную диспетчеризацию.
 +
 
 +
Идея механизма: есть некоторый класс, которые отвечает за диспетчеризацию (диспетчер). У него хранится map, который паре <code>typeid</code> сопоставляет класс, реализующий функцию <code>intersects</code>.
 +
В функции <code>intersects</code> у диспетчера запрашивается реализация по паре <code>typeid</code> аргументов. Диспетчер позволяет регистрировать/
 +
разрегистрировать различные реализации. Если реализации для пересечения двух объектов не нашлось, то функция пересечения кидает исключение.
 +
 
 +
''Примечание'': сравнивать объеткы <code>type_info</code> надо с помощью <code>type_info.before(type_info)</code>.
 +
<code>intersects</code> должна быть коммутативна.
 +
 
 +
== Лабораторная работа №11 операторы new/delete ==
 +
Перегрузить глобальные операторы <code>new/delete</code>, <code>new[]/delete[]</code>.
 +
Оптимизировать процедуру веделения/освобождения памяти, например, не очищать память при вызове <code>delete</code>, а кешировать её и отдавать при следующем вызове <code>new</code>.
  
Задание
+
Попробовать реализованный менеджер памяти в каком-нибудь вашем проекте, сравнить времена работы вашей реализации и дефолтной.
  
== Лабораторная работа №5 ==
+
== Лабораторная работа №12 метапрограммирование smart_print ==
 +
Реализовать шаблонную функцию
 +
<source lang="cpp">
 +
template<typename T>
 +
void smart_print(const T& arg);
 +
</source>
 +
которая выводит на печать аргумент.
 +
Если у аргумента есть <code>arg::iterator</code>, то вывести на печать символ начала коллекции, затем проитерироваться по элементам коллекции и вывести их на печать с помощью <code>smart_print</code> и в конце символ конца коллекции.
 +
Иначе просто вывести агрумент на печать.
  
Задание
+
Результат работы такой функции на списке векторов интов должен выглядить подобным образом
 +
<code>[ [ 1 2 ] [ 3 ] [ 45 32 ] ]</code>.
  
== To be continued ==
+
Для этого необходимо воспользоваться бустовыми <code>BOOST_MPL_HAS_XXX_TRAIT_DEF</code> и <code>enable_if_c/disable_if_c</code>.

Текущая версия на 20:09, 13 мая 2011

Лабораторная работа №1 Шаблоны

Реализовать собственный контейнер

template<typename T>
class Container {
public:
    void push_back(const T& t);
    T& back();
    size_t size() const;
};

В качестве хранилища значенией в реализации Container используйте std::vector.

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

Пример использования такого контейнера

Container<int, std::list<int> > c;

Затем создайте новый контейнер с двумя шаблонными параметрами, первый - тип хранимых значений, второй - шаблон, используемый в реализации вашего контейнера.

Пример использования такого контейнера

Container<int, std::deque> c;

Лабораторная работа №2 Синглтон

Написать простой логгер

class Logger {
public:
    void warn(const std::string& msg);
    static Logger& getInstance();
};

Запретить пользователю его создание, копирование.

Пример использования

Logger& log = Logger::getInstance();
log.warn("Ooops");

Представить, что понадобилось ещё несколько синглтонов, вынести общий для всех синглтонов код в отдельный класс Singleton. Реализовать логгер с использованием класса Singleton так, чтоб код, использующий логгер, не надо было модифицировать.

Лабораторная работа №3 merge sort

Необходимо написать функцию сортировки слиянием.
Сигнатура функции должны быть такой:

template<typename Iter>
std::list<typename Iter::value_type> mergeSort(Iter left, Iter right);

Исходные данные функция модифицировать не должна, в возвращаемом списке должны быть отсортированные элементы.

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

int* array = new int[SIZE];
mergeSort(array, array + SIZE);

Рекомендации: для merge можно воспользоваться std::list::merge
для получения типа, на который указывает указатель, можно воспользоваться std::iterator_traits

Лабораторная работа №4 iterator

Написать шаблонный класс slist односвязный список.

template<typename _Ty>
class slist {
public:
  push_back(const _Ty&);
  forward begin();
  forward end();
  slist();
  _Ty back() const;
};

Реализовать для него forward итератор.

Лабораторная работа №5 functor

Реализовать алгоритм

template<typename InIter, typename OutIter, typename Pred>
OutIter filter(InIter begin, InIter end, OutIter out, Pred pred);

который читает элементы и, если pred(val) возвращает true, то записывает элемент в out.

Реализовать собственный функтор, который принимает std::set<char> и char и проверят наличие входного символа в сете. С помощью алгоритма filter и вашего функтора отфильровать строку.

Лабораторная работа №6 mem_fun

Реализовать аналог std::mem_fun, убедиться, что аналог работает на коде:

std::vector<char> v;
std::set<int> s;
mem_fun(&std::vector<char>::push_back)(v, 'd');
mem_fun(&std::set<int>::count)(s, 3);

Лабораторная работа №7 заполнитель мапы

Реализовать заполнитель мапы

std::map<float, int> m(mapper(1.0, 2)(2, 2)(4, 2));

Лабораторная работа №8-9 класс матрицы

Реализовать класс матрицы MxN (с двумя выделениями памяти).
Спроектировать его с учётом исключений: безопасный, с декларацией бросаемых исключений.

Лабораторная работа №10 двойная диспетчерезация

Иногда в больших системах возникает потребность в некоторой бинарной операции, которая полиморфно зависит от типов обоих аргументов.

Пример: пересечение геометрических примитивов. Мы умеем пересекать круги с кругами, прямоугольники с прямоугольниками и прямоугольники с кругами. Нужно реализовать функцию bool intersects(Shape * a, Shape * b);

Ваше задание: написать механизм, который позволил бы реализовать двойную диспетчеризацию.

Идея механизма: есть некоторый класс, которые отвечает за диспетчеризацию (диспетчер). У него хранится map, который паре typeid сопоставляет класс, реализующий функцию intersects. В функции intersects у диспетчера запрашивается реализация по паре typeid аргументов. Диспетчер позволяет регистрировать/ разрегистрировать различные реализации. Если реализации для пересечения двух объектов не нашлось, то функция пересечения кидает исключение.

Примечание: сравнивать объеткы type_info надо с помощью type_info.before(type_info). intersects должна быть коммутативна.

Лабораторная работа №11 операторы new/delete

Перегрузить глобальные операторы new/delete, new[]/delete[]. Оптимизировать процедуру веделения/освобождения памяти, например, не очищать память при вызове delete, а кешировать её и отдавать при следующем вызове new.

Попробовать реализованный менеджер памяти в каком-нибудь вашем проекте, сравнить времена работы вашей реализации и дефолтной.

Лабораторная работа №12 метапрограммирование smart_print

Реализовать шаблонную функцию

template<typename T>
void smart_print(const T& arg);

которая выводит на печать аргумент. Если у аргумента есть arg::iterator, то вывести на печать символ начала коллекции, затем проитерироваться по элементам коллекции и вывести их на печать с помощью smart_print и в конце символ конца коллекции. Иначе просто вывести агрумент на печать.

Результат работы такой функции на списке векторов интов должен выглядить подобным образом [ [ 1 2 ] [ 3 ] [ 45 32 ] ].

Для этого необходимо воспользоваться бустовыми BOOST_MPL_HAS_XXX_TRAIT_DEF и enable_if_c/disable_if_c.