Skip to content

Latest commit

 

History

History
101 lines (71 loc) · 6.12 KB

Task 1 - Flat Map.md

File metadata and controls

101 lines (71 loc) · 6.12 KB
Raw

Задача 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. Должны быть автоматические тесты с использованием GoogleTest. В коде тестов можно использовать контейнеры STL.

Tip

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

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

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

  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";
}