Повторяемая вставка O (1) и случайное удаление

Question

Я хочу реализовать свой собственный класс коллекции.Мне нужны следующие характеристики:

1. Итерируемый - порядок не важен
2. Вставка - в конце или в месте расположения итератора, это не имеет значения
3. Случайное удаление -это хитрый.Я хочу иметь возможность ссылаться на фрагмент данных, который гарантированно находится в списке, и удалять его из списка за O (1) раз.

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

Вот где я застреваю.Мне интересно, было бы лучше, чтобы элементы в списке содержали ссылку на свой узел или встраивали узел прямо в них.Я чувствую, что оба были бы довольно просты, но я беспокоюсь о соединении этих узлов в кучу классов.

Мне интересно, есть ли у кого-нибудь идея о том, как минимизировать связь, или, возможно, знать о другомструктура данных, которая имеет характеристики, которые я хочу.

Answer 1

Было бы трудно победить хэш-карту.

Answer 2

Взгляните на попытки .

Очевидно, они могут побить хеш-таблицы:

В отличие от большинства других алгоритмов, попытки имеютОсобенность в том, что время для вставки, или удаления, или поиска почти идентично, потому что пути кода для каждого из них практически идентичны.В результате, для ситуаций, когда код вставляется, удаляется и находит в равной мере попытки , можно легко превзойти двоичные деревья поиска или даже хеш-таблицы , а также лучше для кэшей команд и ветвлений ЦП.

Это может или не может соответствовать вашему использованию, но если это так, это, вероятно, один из лучших возможных вариантов.

Answer 3

В C ++ это звучит как идеально подходящее для std::unordered_set (это std::tr1::unordered_set или boost::unordered_set для вас, если у вас более старый компилятор).Он реализован в виде хеш-набора, который имеет характеристики, которые вы описываете.

Вот документация интерфейса .Обратите внимание, что хеш-контейнеры на самом деле предлагают два набора итераторов, обычные и локальные , которые проходят только через одну корзину.

Многие другие языки имеют "хэш-наборы"а также, конечно, Java и C #.