Bimap

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

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

Что вообще такое интрузивные контейнеры? Представим ситуацию, когда вы хотите хранить какие-то тяжёлые данные в нескольких контейнерах разных типов. Соответственно, в идеале, не копировать их. Давайте представим, что у нас простой случай и мы хотим хранить данные в двух связных списках (одно- и двусвязный). Связные списки состоят из нод. Обычно они содержат значение и один-два указателя на соседние ноды. Но при этом в каждом из двух листов будут разные значения указателей на соседей (и кол-во этих указателей). Соответственно, каждый из двух листов будет иметь свой тип ноды. С точки зрения C++ это реализуется следующим образом: каждый лист заводит свою ноду со всеми нужными полями и логикой, а вы реализуете ноду для вашего случая сами, при этом наследуясь от нод листов. Выглядит это примерно так:

class ListHook {
 private:
  template <class T> friend class List;
  ListHook* prev_;
  ListHook* next_;
};

class ForwardListHook {
 private:
  template <class T> friend class ForwardList;
  ForwardListHook* next_;
};

template <typename T, typename S>
class MyNode : ListHook, ForwardListHook {
  T key_;
  S value_;
};

Таким образом теперь мы можем хранить одни и те же данные и в двусвязном списке, и в односвязном. При совершении операций в листе вы должны сделать static_cast к соответствующему типу ноды для этого листа и делать все нужные операции. В этих хуках мы можем реализовать всю нужную логику для работы с конкретным типом ноды, что позволяет не реализовывать её самому: она просто отнаследуется! Хотя хорошие реализации не пушат пользователя всё же писать ноду руками. Часто это можно засунуть в ваш класс и попросить от пользователя только типы ключа/значения, которые он хочет хранить.

Теперь к bimap.

По факту, это два бинарных поисковых дерева, каждое из которых реализует свою ноду и логику работы с ней. Просто один хук смотрит при поиске на ключи, а второй на значения. Соответственно при поиске по ключу вы делаете поиск в вашей ноде и кастуете всегда к ноде этого дерева (хотя конечно проще написать одно дерево и один тип ноды, но при этом создать что-то вроде тегов, на которые можно ориентироваться). При поиске по значению наоборот: кастуем к тегу инвертированного дерева и делаем все нужные операции. И при этом мы не храним данные дважды! Весь оверхед в том, чтобы иметь ещё по три указателя (родитель, левый и правый дети) на ещё одно дерево. Аналогично можно писать что-то вроде 3map: у вас теперь не левый/правый деревья, а первое/второе/третье.

При всём этом, конечно же, грамотная реализация позволяет наворачивать свои компараторы на ключи/значения.

Такой подход в общем случае позволяет делать различные контейнеры на ключ/значение. Например, вы можете захотеть сделать уникальную неупорядоченную хеш-таблицу слева и упорядоченную неуникальную древовидную структуру справа, то можно реализовать unordered_set и multiset соответственно. Boost даже позволяет это сделать из коробки:

boost::bimap<
  boost::bimaps::unordered_set_of<std::string>,
  boost::bimaps::multiset_of<int>
>

Часто bimap путают с bitmap (всего одна буковка). Но вы не ведитесь. Это разное.

Реализация bimap есть в boost. Там хорошие картиночки и пояснения про то, как им пользоваться. Но если интересно не утопать в сложном библиотечном коде, можно покопаться в этом репозитории. Аналогично можно найти такое даже в Golang: link.