Это интересный вопрос. Boost.Intrusive не предоставляет интерфейс карты, упорядоченный или неупорядоченный. Он имеет много типов реализации, которые будут отлично работать как карты, упорядоченные (красно-черные деревья, деревья AVL, деревья сплайнов), так и неупорядоченные (хеш-таблицы). Но карт нет, и я не могу сказать, почему.
У меня есть два варианта, как я это вижу:
- Просто используйте
hashtable: неупорядоченные контейнеры реализованы в виде хеш-таблиц (и единственная причина, по которой они не называются hash_map, состоит в том, чтобы избежать конфликтов имен с уже существующими библиотеками, использующими это имя уже) , Это сработает, если вы хотите, чтобы ваша работа была выполнена.
- Если вы действительно хотите реализовать свой собственный, вам нужно взглянуть на описание интерфейса для unordered_set Boost.Intrusive. Я не смотрел на реализацию, но это почти наверняка обертка вокруг одного или нескольких типов деревьев.
std::set и std::map, как правило, реализуются в виде оберток вокруг красно-черного дерева (во всех стандартных реализациях библиотек, на которые я смотрел: GCC, MSVC и Apache stdcxx). Также рассмотрим, как libstdc ++ оборачивает свою реализацию дерева в <map> и <set>. Это много шаблонного, много утомительного, но оба типа переносят почти всю работу на дерево. Нечто аналогичное почти наверняка происходит с Boost.Intrusive unordered_set. Вам нужно будет посмотреть на различия между картой и настройками интерфейсов и использовать их в качестве основы для изменения unordered_set в unordered_map.
Я сделал последнее. Это немного утомительно, и я настоятельно рекомендую написать для него модульные тесты (или украсть те, которые поставляются с libstdc ++ или Boost.Intrusive). Но это выполнимо. Я также настоятельно рекомендую прочитать документы с требованиями для наборов и карт либо в SGI ( set , map ), либо для libstdc ++
Обновление: Я понял, почему они не делают карты: навязчивые контейнеры требуют, чтобы вы встраивали информацию об узле для структуры данных в тип значения, который вы храните в нем. Для карт вы должны сделать это как для значений , так и для ключей . Это не так, что это невозможно, но стандартная реализация для map использует такой же внутренний тип, как и set s. Но эти внутренние типы имеют только переменную one value_type: для хранения ключей и значений они копируют ключ и значение в эту переменную и сохраняют ее в узлах. Чтобы сделать это с помощью навязчивого типа (то есть без копирования), вам нужно изменить этот тип реализации, чтобы он был несовместим с наборами: он должен хранить ссылки на ключи и значения отдельно . Поэтому, чтобы сделать это, вы также должны изменить используемую реализацию (вероятно, hashtable). Опять же, это не невозможно, но разработчики библиотек, вероятно, пытаются избежать серьезного дублирования кода, поэтому в отсутствие простого способа реализовать это они, скорее всего, решили не использовать карты.
Имеет ли это смысл?