Boost.Intrusive и unordered_map

Ответ 1

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

У меня есть два варианта:

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

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

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

Это имеет смысл?

Ответ 2

Прошло много времени с тех пор, как этот вопрос был задан, но я думаю, что люди, приезжающие сюда, должны быть заинтересованы в том, как использовать unordered_set как карту. Решение состоит в том, чтобы использовать расширенные методы вставки: нужно просто сохранить ключ и его значение в одном и том же value_type и вставить его с помощью insert_check и insert_commit.