Bimap

В этом задании вам необходимо написать bidirectional map. Интерфейс вы найдёте в репозитории, в файле src/bimap.h.

Описание структуры

bimap — это структура данных, в которой хранится набор пар и эффективно выполняется поиск ключа по значению. В отличие от std::map, поиск в bimap может выполняться как по левым ключам пар, так и по правым.

bimap параметризуется двумя типами (Left и Right) и двумя типами компараторов (CompareLeft и CompareRight), экземпляры которых определяют порядок на левых и правых ключах соответственно.

Итераторы

bimap предоставляет возможность итерироваться по левым или правым ключам в порядках, определённых их компараторами. Для этого он реализует две пары методов для получения итераторов: begin_left()+end_left() и begin_right()+end_right().

Итераторы повторяют соответствующее поведение std::map, и вдобавок реализуют метод flip, возвращающий парный итератор (на противоположный элемент в паре) — превращает left_iterator в right_iterator и наоборот.

Семантика операций

insert

Вставляет пару (left, right), возвращает итератор на left. Если такой left или такой right уже присутствуют в bimap, вставка не производится и возвращается end_left().

erase_left, erase_right от итератора

Пусть переданный итератор ссылается на некоторый ключ e. Тогда erase_left (erase_right) удаляет e и противоположный ему ключ и инвалидирует все итераторы, ссылающиеся на них. Возвращает итератор на пару после удалённой.

erase_left, erase_right от ключа

Аналогично перегрузке от итератора, но по ключу: удаляет его, если он присутствует, иначе не делает ничего. Возвращает true, если пара была удалена.

erase_left, erase_right от пары итераторов

Аналогично перегрузке от итератора, но удаляет все ключи в диапазоне [first, last). Возвращает итератор на пару после последней из удалённых.

find_left, find_right

Возвращает итератор по ключу. Если не найден — соответствующий end().

at_left, at_right

Возвращает противоположный ключ по ключу. Если не найден — бросает std::out_of_range.

at_left_or_default, at_right_or_default

Возвращает противоположный ключ по ключу. Если не найден — добавляет его в bimap, а на противоположную сторону кладёт значение, полученное вызовом конструктора по умолчанию, и возвращает ссылку на него. При этом, если дефолтный противоположный ключ уже существует — должен поменять соответствующий ему ключ на запрашиваемый (см. тесты).

lower_bound_left, lower_bound_right, upper_bound_left, upper_bound_right

Поведение аналогично std::lower_bound и std::upper_bound.

Эффективность

Вам предлагается, основываясь на описании, изложенном выше, интерфейсе и уже пройденных материалам курса, придумать и реализовать bimap, эффективный по:

• Использованной памяти:
  • Общему количеству аллокаций;
  • Пустое дерево не должно делать никаких динамических аллокаций;
  • Пустые компараторы не должны занимать дополнительную память;
• Скорости операций;
• Количеству копипасты (особенно вокруг итераторов и операций поиска).

Балансировать дерево не требуется.