Повышение. Навязчивый и unordered_map

Это интересный вопрос. Boost.Intrusive, похоже, не предоставляет никакого интерфейса карты, упорядоченного или неупорядоченного. Он имеет множество типов реализации, которые отлично работают как упорядоченные (красно-черные деревья, деревья AVL, растянутые деревья), так и неупорядоченные (хэш-таблицы). Но нет карт, и я не могу сказать вам, почему.

У вас есть два варианта, как я вижу:

1. Просто используйте хеш-таблицу : неупорядоченные контейнеры реализованы как хэш-таблицы (и единственная причина, по которой они не вызывается hash_map , чтобы избежать конфликтов имен с уже существующими библиотеками, которые уже используют это имя). Это сработает, если вы хотите выполнить свою работу.
2. Если вы действительно хотите реализовать свою собственную, вам нужно взглянуть на описание интерфейса для Boost.Intrusive's unordered_set . Я не рассматривал реализацию, но почти наверняка это оболочка для одного или нескольких типов дерева. std :: set и std :: map обычно реализуются как оболочки вокруг красно-черного дерева (во всех реализациях стандартных библиотек, на которые я смотрел: GCC, MSVC и Apache stdcxx). Также обратите внимание на то, как libstdc ++ оборачивает свою реализацию дерева в и в . Это много шаблонов, многие из них утомительны, но оба типа возлагают почти всю работу на дерево. Нечто подобное почти наверняка происходит с unordered_set Boost.Intrusive. Вам нужно будет посмотреть на различия между интерфейсами map и set и использовать это как основу для преобразования unordered_set в unordered_map .

Я сделал последнее. Это немного утомительно, и я настоятельно рекомендую писать для него модульные тесты (или красть те, которые поставляются с libstdc ++ или Boost.Intrusive). Но это выполнимо. Я также настоятельно рекомендую прочитать документы с требованиями для наборов и карт либо в SGI ( set , map ), либо для libstdc ++

Update: Я понял, почему они не делают карт: навязчивые контейнеры требуют, чтобы вы встраивали информацию об узлах для структуры данных в тип значения, который вы в ней храните. Для карт вам нужно будет сделать это как для значений , так и для ключей . Не то чтобы это невозможно, но стандартная реализация для карты использует тот же внутренний тип , что и набор . Но эти внутренние типы имеют только одну переменную value_type : для хранения ключей и значений они копируют ключ и значение в эту переменную и сохраняют их в узлах. Чтобы сделать это с навязчивым типом (т.е. без копирования), вам придется изменить этот тип реализации, чтобы он был несовместим с наборами: он должен хранить ссылки на ключи и значения отдельно . Поэтому для этого вам также необходимо изменить используемую реализацию (вероятно, hashtable ). Опять же, это не невозможно, но разработчики библиотеки, вероятно, пытаются избежать серьезного дублирования кода, поэтому из-за отсутствия простого способа реализации этого они, скорее всего, решили не использовать карты.