Повышение.Навязчивая и неупорядоченная карта

Question

Я хочу использовать навязчивый unordered_map.По какой-то причине в библиотеке есть только unordered_set .Существует также навязчивая хэш-таблица, но я не уверен, что она обладает такой же функциональностью, также у нее нет такого же интерфейса.
Я ошибаюсь, и я пропустил ссылку unordered_map?
Если это не так, есть ли учебник, который поможет мне его реализовать?

Answer 1

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

На мой взгляд, у вас есть два варианта:

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

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

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

Есть ли в этом смысл?

Answer 2

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