Bimap

В данном задании необходимо написать bimap (bidirectional map).

map-ами называются такие структуры данных, которые хранят набор пар, и позволяют эффективно по первому элементу пары (который называется ключом) находить соответствующий ему второй элемент пары (называется значением). Существует две распространенные реализации map-ов: деревья поиска и хеш-таблицы. Далее, в этом задании я буду предполагать, что map устроен как бинарное дерево поиска.

Также как и map-ы, bimap-ы хранят набор пар и позволяют эффективно по первому элементу пары находить второй, а по второму — первый. То есть поиск можно делать в обе стороны. Первый элемент пары я буду называть left, второй — right.

Наивная реализация bimap-а, могла бы состоять из двух map-ов: прямой и обратной. Прямая использовалась бы для поиска из left в right, а обратная — из right в left. Такая реализация не является эффективной, так как в ней на каждую пару хранимую в bimap аллоцируется два объекта в хипе. Можно сделать эффективнее, если завести класс node следующего вида:

struct node { left_t left_data; node* left_left; node* left_right; node* left_parent; right_t right_data; node* right_left; node* right_right; node* right_parent; };

В приведенном классе left_data и right_data являются значениями левого и правого элемента пары соответственно. left_{left,right,parent} образуют бинарное дерево поиска, в котором left_data является ключом. right_{left,right,parent} образуют бинарное дерево поиска, в котором right_data является ключом. То есть node-ы провязаны в два независимых дерева поиска.

Обычное бинарное дерево поиска позволяет находить следующий по величине элемент и предыдущий по величине элемент. Такая структура node-ов как в bimap позволяет находить node со следующим по величине left, следующим по величине right, предыдущим по величине left, предыдущим по величине right.

В std::map итераторы поддерживают две операции: перейти к следующему элементу по величине и перейти к предыдущему. begin() возвращает итератор на минимальный элемент, end() — на следующий за максимальным. Таким образом цикл от begin() до end() позволяет просмотреть все элементы std::map в порядке возрастания.

В bimap итераторы можно сделать следующим способом. Существует два вида итераторов: left_iterator и right_iterator. Проход от begin_left() до end_left() позволяет просмотреть все левые элементы пар в возрастающем порядке. Проход от begin_right() до end_right() — все правые элементы пар в возрастающем порядке. Оба вида итераторов имеют функцию flip(), которая возвращает итератор другого вида, но ссылающийся на эту же пару.

Задание

В этом задании необходимо реализовать класс со следующим интерфейсом:

struct bimap
{
    // Вы можете определить эти тайпдефы по вашему усмотрению.
    typedef ... left_t;
    typedef ... right_t;

    struct left_iterator;
    struct right_iterator;

    // Создает bimap не содержащий ни одной пары.
    bimap();

    // Деструктор. Вызывается при удалении объектов bimap.
    // Инвалидирует все итераторы ссылающиеся на элементы этого bimap
    // (включая итераторы ссылающиеся на элементы следующие за последними).
    ~bimap();

    // Вставка пары (left, right), возвращает итератор на left.
    // Если такой left или такой right уже присутствуют в bimap, вставка не
    // производится и возвращается end_left().
    left_iterator insert(left_t const& left, right_t const& right);

    // Удаляет элемент и соответствующий ему парный.
    // erase невалидного итератора неопределен.
    // erase(end_left()) и erase(end_right()) неопределены.
    // Пусть it ссылается на некоторый элемент e.
    // erase инвалидирует все итераторы ссылающиеся на e и на элемент парный к e.
    void erase(left_iterator it);
    void erase(right_iterator it);

    // Возвращает итератор по элементу. В случае если элемент не найден, возвращает
    // end_left()/end_right() соответственно.
    left_iterator  find_left (left_t  const& left)  const;
    right_iterator find_right(right_t const& right) const;

    // Возващает итератор на минимальный по величине left.
    left_iterator begin_left() const;
    // Возващает итератор на следующий за последним по величине left.
    left_iterator end_left() const;

    // Возващает итератор на минимальный по величине right.
    right_iterator begin_right() const;
    // Возващает итератор на следующий за последним по величине right.
    right_iterator end_right() const;
};

struct bimap::left_iterator
{
    // Элемент на который сейчас ссылается итератор.
    // Разыменование итератора end_left() неопределено.
    // Разыменование невалидного итератора неопределено.
    left_t const& operator*() const;

    // Переход к следующему по величине left'у.
    // Инкремент итератора end_left() неопределен.
    // Инкремент невалидного итератора неопределен.
    left_iterator& operator++();
    left_iterator operator++(int);

    // Переход к предыдущему по величине left'у.
    // Декремент итератора begin_left() неопределен.
    // Декремент невалидного итератора неопределен.
    left_iterator& operator--();
    left_iterator operator--(int);
    
    // left_iterator ссылается на левый элемент некоторой пары.
    // Эта функция возвращает итератор на правый элемент той же пары.
    // end_left().flip() возращает end_right().
    // end_right().flip() возвращает end_left().
    // flip() невалидного итератора неопределен.
    right_iterator flip() const;
};

struct bimap::right_iterator
{
    // Здесь всё аналогично left_iterator.
    right_t const& operator*() const;

    right_iterator& operator++();
    right_iterator operator++(int);

    right_iterator& operator--();
    right_iterator operator--(int);
    
    left_iterator flip() const;
};

bimap хранит набор пар (left, right). begin_left()/end_left() позволяет пройти все левые элементы пар в порядке возрастания. begin_right()/end_right() позволяет пройти все правые элементы пар в порядке возрастания. Функция итератора flip() позволяет стоя на левом элементе какой-то пары перейти к правому и наоборот.

Необходимо, чтобы bimap создавал один объект в памяти на каждую пару хранящуюся в нем.

Необходимо, чтобы bimap использовал внутри себя дерево поиска (не обязательно сбалансированное), а операции поиска/вставки/удаления работали за O(h), где h — высота дерева.

Конструкторы копирования и оператор присваивания bimap-а должны быть запрещены.

В случаях когда это задание не предписывает определенного поведения, любое поведение конкретной реализации считается удовлетворяющим заданию. Предполагается, что не все случаи неопределенного поведения, указанные в этом задании, можно свести к assert-у, не жертвуя простотой или эффективностью реализации. В тех случаях, где это уместно, рекомендуемым поведением является срабатывание assert-а.

left_iterator-у и right_iterator-у не обязательно быть двумя независимыми классами. Они могут быть, например, typedef-ами на разные инстанциации одного темплейта.

Bimap

Введение

Задание