lab1

Задача 1. Flat Map

Реализуйте класс ассоциативного массива (другие названия: map, словарь, таблица, мэпа) на основе отсортированного массива и бинарного поиска по нему.

В качестве ключей и значений контейнер принимает строки (std::string).

Нужно реализовать как минимум следующие методы:

class FlatMap {
public:

    // стандартный конструктор
    FlatMap();

    // конструктор копирования
    FlatMap(const FlatMap& other_map);

    // деструктор
    ~FlatMap();

    // оператор присваивания
    FlatMap& operator=(const FlatMap& other_map);

    // получить количество элементов в таблице
    std::size_t size() const;

    // доступ / вставка элемента по ключу
    std::string& operator[](const std::string& key);

    // возвращает true, если запись с таким ключом присутствует в таблице
    bool contains(const std::string& key);

    // удаление элемента по ключу, возвращает количество удаленных элементов (0 или 1)
    std::size_t erase(const std::string& key);

    // очистка таблицы, после которой size() возвращает 0, а contains() - false на любой ключ
    void clear();
}

Класс хранит записи в одном (или нескольких) массивах, детали продумайте сами. Запрещается использовать контейнеры STL (кроме std::string). Это должны быть обычные массивы, которые вы создаете с помощью оператора new[] и удаляете оператором delete[].

Класс обеспечивает логарифмическую сложность (O(logN)) доступа по ключу (operator[] в случае, когда ключ уже есть, contains) за счет бинарного поиска.

Сложность вставки (operator[] в случае, когда ключа еще нет) и удаления (erase) элементов - линейная.

Пример работы с этим контейнером:

FlatMap student;
student["first_name"] = "Ivan";
student["last_name"] = "Petrov";
student["university"] = "NSU";
student["department"] = "FIT";
student["group"] = "...";
// ...

std::cout << "Student: " << student["first_name"] << " " << student["last_name"] << "\n";

Технические требования:

1. Проект должен собираться с помощью CMake. Шаблон проекта для CMake с описанием, как все настроить, см. здесь.
2. Должны быть тесты с использованием GoogleTest. В шаблоне для CMake GoogleTest уже подключен, вам лишь нужно их написать. В коде тестов можно использовать контейнеры STL.

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

Дополнительные возможности, предлагаемые для реализации тем, кто сделает основное:

1. Реализуйте конструктор перемещения и перемещающий operator=:

   FlatMap(FlatMap&& x) noexcept;
   FlatMap& operator=(FlatMap&& x) noexcept;

   Продемонстрируйте случаи, когда вызывается конструктор копирования и копирующий operator=, а когда - конструктор перемещения и перемещающий operator=. Продемонстрируйте прирост производительности, который можно получить, реализовав перемещающие варианты конструктора копирования и operator=. Для демонстрации можно использовать контейнеры STL.

2. Сделайте так, чтобы все методы вашего класса обеспечивали как минимум базовую гарантию безопасности исключений. Примените идиому Copy-and-swap.

3. Реализуйте обход таблицы по итератору, а именно методы:

   // Получить итератор на первый элемент
   iterator begin();
   
   // Получить итератор на элемент, следующий за последним
   iterator end();
   
   // Получить итератор на элемент по данному ключу, или на end(), если такого ключа нет.
   // В отличие от operator[] не создает записи для этого ключа, если её ещё нет
   iterator find(const std::string& x);

   Какой именно тип будут возвращать эти функции - продумайте сами, iterator выше - лишь условное обозначение. Но должен работать следующий код:

   // выводит все пары в таблице student в формате "ключ: значение"
   for (auto it = student.begin(); it != student.end(); ++it) {
       std::cout << it->first << ": " << it->second << "\n";
   }

4. (Важно! Этот пункт можете делать только после того, как сделали все предыдущие. Он не обязателен даже для оценки 5.) Превратите ваш класс в шаблонный класс, поддерживающий любые типы ключей (для которых определён operator<) и любые типы значений (для которых определён конструктор без параметров).

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