Skip to content

Latest commit

 

History

History
113 lines (84 loc) · 11.8 KB

Task 4 - Templates.md

File metadata and controls

113 lines (84 loc) · 11.8 KB
Raw

Задача 4. Шаблоны (templates) и элементы метапрограммирования

Общие условия

Для успешной сдачи задачи нужно реализовать базовые условия всех подзадач. Поэтому сначала сделайте базовые условия всех подзадач, и только после этого беритесь за допы. Допы можно делать свободно из разных подзадач в любом порядке.

Подзадача 1. Кортежи (tuples)

Реализуйте оператор для печати std::tuple. Должен работать код наподобие следующего:

// кортеж может быть любым возможным, не обязательно 3 этих типа
std::tuple<int, std::string, double> t = {5, "abcd", 3.14};
// выводит (5, abcd, 3.14). Вместо std::cout может быть файловый поток (ofstream)
std::cout << t;

Вы ограничены возможностями стандарта С++11. Это означает, что нельзя, например, использовать if constexpr, std::integer_sequence/std::index_sequence и fold expressions, т.к. они появились в более поздних версиях. (Этот запрет действует только здесь; в допах этой подзадачи и в следующих подзадачах его нет.)

Дополнительно:

  1. Сделайте другую реализацию, на этот раз используя if constexpr.
  2. Сделайте ещё одну реализацию, используя выражения свёртки (fold expressions) и, если понадобится, std::integer_sequence/std::index_sequence.
  3. Реализуйте собственный вариант шаблонного класса tuple.
  4. Напишите программу, которая компилируется дольше 1 минуты. Успешная компиляция не требуется.

Подзадача 2. Парсер CSV

Формат CSV: табличные данные могут быть представлены как текстовый файл с разделителем \n между строками и символом , для разделения ячеек внутри строки. Считаем, что данные символы не встречаются внутри данных.

Напишите класс, делающий возможным следующую потоковую работу с CSV:

int main()
{
    ifstream csv_stream("test.csv");    
    CsvParser<int, std::string, double> parser(csv_stream, 0 /*skip first lines count*/);
    for (std::tuple<int, std::string, double> rs : parser) {
        std::cout << rs << "\n";
    }
}

Потоковая обработка подразумевает lazy (ленивое) чтение строк, то есть вы читаете строку только тогда, когда она реально нужна. Таким образом необходимо реализовать InputIterator для чтения данных в CSV файле.

При сдаче продемонстрировать:

  1. Чтение нескольких валидных файлов и печать их содержимого в консоль.
  2. Чтение из std::cin.
  3. Чтение нескольких ошибочных файлов и/или не подходящих по типам.

Дополнительно:

  1. Реализуйте проверку на этапе компиляции, что все шаблонные параметры парсера могут быть получены из строк (то есть, вы можете строку распарсить в этот тип). Если это не так, выведите ваше собственное понятное сообщение об ошибке.
  2. Добавьте в конец кортежа, который возвращает итератор, параметр типа std::vector<std::string>, куда будут записаны все остальные колонки, если их в файле больше, чем шаблонных параметров парсера. То есть, для примера выше итератор должен возвращать тип std::tuple<int, std::string, double, std::vector<std::string>>.
  3. Выделите логику приведения строки из CSV-файла к нужному типу в отдельную стратегию. Для этого сделайте так, чтобы первым шаблонным параметром CsvParser можно было указать шаблонный функтор для приведения строки к нужному типу. Сделайте реализацию этого функтора, которая использует operator<<, и другую реализацию, которая строку возвращает как есть, для числовых типов использует функции std::sto* (например, std::stoi для int), а остальные типы по умолчанию не поддерживает (при попытке их использовать возникает ошибка компиляции).

Подзадача 3. Обобщённый Flat Map

Превратите ваш класс FlatMap из первой задачи в шаблонный класс, поддерживающий любые типы ключей (для которых определён operator<) и любые типы значений (для которых определён конструктор без параметров).

template <class Key, class Value>
class FlatMap {
    // ...
}

Note

Если в первой задаче вы не сделали итераторы, реализуйте их сейчас. Итераторы - часть минимальных требований данной задачи. Другие допы первой задачи делать не обязательно.

Дополнительно:

  1. К шаблонным параметрам Key и Value добавьте Compare и Allocator, определяющие стратегии сравнения ключей и выделения памяти.

    template <class Key,
          class Value,
          class Compare = std::less<Key>,
          class Allocator = std::allocator<...>
         >
class FlatMap {
    // ...
}

    Работайте с аллокатором не напрямую, а через шаблон std::allocator_traits.

    1.1. Продемонстрируйте, как можно использовать в качестве ключа тип, для которого не перегружены операторы сравнения (например, <).

  2. Реализуйте поддержку инициализации списком (List-Initialization), а именно, чтобы работал код наподобие FlatMap<std::string, int> m = { {"a", 1}, {"b", 2} };

  3. Реализуйте собственный аллокатор, который выделяет большой кусок памяти (пул) один раз при создании. Его метод allocate не делает реального выделения памяти, а лишь возвращает указатель на свободный участок из этого пула, а метод deallocate просто ничего не делает. Убедитесь, что с вашим аллокатором корректно работает как ваш класс FlatMap, так и стандартные контейнеры (например, std::vector или std::list). Продемонстрируйте разницу в производительности контейнера std::list со стандартным аллокатором и с вашим.

    3.1. Реализуйте метод deallocate так, чтобы освобожденное место в пуле можно было использовать повторно.

  4. Реализуйте проверку на этапе компиляции, что тип Key поддерживает сравнение по operator<, а тип Value имеет конструктор без параметров.

  5. Сделайте специализацию таблицы для ключей целочисленных беззнаковых типов и значений типа bool (то есть, например, Key = unsigned int, Value = bool). Эта специализация для хранения данных должна использовать std::vector<bool> и не хранить дополнительно больше никаких данных. Из допов данной задачи эта специализация может использовать аллокаторы и реализовывать итераторы, другие допы для неё делать не надо.

  6. Реализуйте шаблонный метод try_emplace, который позволит вставлять элементы в таблицу следующим образом:

    class A {
public:
    A(int x, double y, const std::string& z) {
        // ...
    }
}
FlatMap<std::string, A> map_of_a;
std::pair<iterator, bool> x = map_of_a.try_emplace("key1", 3, 5.6, "test");
    // создан и вставлен в таблицу объект A(3, 5.6, "test") по ключу "key1"

    Если такой ключ уже есть в таблице, метод ничего не делает. Метод возвращает пару std::pair<iterator, bool>, где iterator - это ваш тип итератора. В этой паре итератор указывает на элемент по данному ключу, а булево значение указывает на то, был ли этот элемент вставлен в результате вызова try_emplace (true), или он существовал раньше (false).

  7. Сделайте так, чтобы ваш шаблонный класс FlatMap корректно работал с типами ключей и значений, у которых запрещено копирование или перемещение (но не оба сразу). Например, у std::unique_ptr запрещено копирование.

  8. Сделайте так, чтобы FlatMap корректно работал для случаев: Key = const T, Value = const V, Key = T&, Value = V& (где T и V - произвольные типы) и их комбинаций (например, Key = const T&, Value = V&). Некоторые вызовы методов для некоторых комбинаций могут не компилироваться, это нормально (например, m[key] = value для случаев Value = const V). Но в целом работоспособность класса должна сохраняться.

    8.1. Принимается также частичная реализация (например, только для констант).