Структура данных в виде очереди с удалением элементов произвольного доступа

Question

Существует ли структура данных, подобная очереди, которая также поддерживает удаление элементов в произвольных точках? Постановка в очередь и снятие очереди происходят чаще всего, но удаление элементов в средней очереди должно быть аналогичным по скорости, поскольку могут быть периоды, когда это является наиболее распространенной операцией. Постоянство производительности важнее абсолютной скорости. Время важнее памяти. Длина очереди мала, менее 1000 элементов при абсолютной пиковой нагрузке. В случае, если это не очевидно, я укажу это явно: случайная вставка не требуется.

Помечены тегами C ++, поскольку это мой язык реализации, но я не использую (и не хочу) использовать STL или Boost. Только на чистом C или C ++ (я преобразую решения C в класс C ++.)

Редактировать: я думаю, что мне нужен словарь, который также имеет интерфейс очереди (или очередь, которая также имеет интерфейс словаря), так что я могу делать что-то вроде этого:

Container.enqueue(myObjPtr1);
MyObj *myObjPtr2 = Container.dequeue();
Container.remove(myObjPtr3);

Answer 1

Я думаю, что список двойных ссылок - это именно то, что вам нужно (при условии, что вы не хотите очереди с приоритетами):

1. Простое и быстрое добавление элементов в оба конца
2. Легкои быстрое удаление элементов из любого места

Вы можете использовать std::list контейнер, но (в вашем случае) трудно удалить элемент из середины списка, если у вас есть только указатель (или ссылка) на элемент (обернутый в элемент списка STL), но у вас нет итератора.Если использование итераторов (например, их сохранение) не вариант, то реализация двойного связанного списка (даже со счетчиком элементов) должна быть довольно простой.Если вы реализуете свой собственный список - вы можете напрямую работать с указателями на элементы (каждый из них содержит указатели на обоих своих соседей).Если вы не хотите использовать Boost или STL, это, вероятно, лучший вариант (и самый простой), и у вас есть контроль всего (вы даже можете написать свой собственный распределитель блоков для элементов списка, чтобы ускорить процесс).

Answer 2

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

Надеюсь, это поможет!

Answer 3

Вы можете использовать комбинацию связанного списка и хэш-таблицы. В Java это называется LinkedHashSet.

Идея проста, иметь связанный список элементов, а также поддерживать hash map из (key,nodes), где node - указатель на соответствующий узел в связанном списке, а key - ключ представляющий этот узел.

Обратите внимание, что базовая реализация - set, и потребуется некоторая дополнительная работа, чтобы эта структура данных допускала дублирование.

Эта структура данных предоставляет вам как O(1) доступ к голове / хвосту, так и O(1) доступ к любому элементу в списке. [все в среднем с ручным приводом]