Какова лучшая структура данных для хранения элементов, которые будут извлечены только один раз, а затем удалены?

Question

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

Я не могу использовать стек или очередь, так как порядок поиска не гарантируется.

[РЕДАКТИРОВАТЬ] - Я хотел бы использовать непрерывную память (я бы предпочел избегать использования malloc время от времени), а также я бы предпочел также возможность поиска.

Answer 1

Отделите требования к хранилищу от структуры данных.

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

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

Так что какая-то форма сбалансированного дерева звучит так, как вам нужно. Выбор, вероятно, зависит от того, какие шаблоны существуют с поступающими ключами. Случайные? По возрастанию?

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

Было бы интересно узнать, почему вы цените непрерывный блок памяти.

Answer 2

Я думаю, что выбор алгоритма требует больше информации о том, как он будет использоваться. Из вашего комментария, который вы хотите лучше, чем линейный поиск, я предполагаю, что скорость поиска важна. Ваши комментарии о непрерывной памяти приводят меня к мысли, что вы хотите минимизировать потребление памяти. Я бы предположил, что самобалансирующаяся древовидная структура ( Красно-Черное дерево) может быть подходящей. Было бы вставить / удалить амортизированный журнал (N), что позволило бы достичь обеих целей, которые я обозначил. Если использование памяти представляет меньшую проблему, хеш-таблица будет более эффективной для поиска. Вы можете реализовать дерево ограниченного размера в смежной памяти - хотя сами фактические элементы не обязательно являются смежными.

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

Answer 3

Вдвойне связанный список, очевидно. Что вы подразумеваете под "вы хотите, чтобы ваша память была непрерывной"? Независимо от того, какую структуру данных вы используете, она будет непрерывной, пока вы не удалите один элемент, после чего вам нужно будет упаковать данные, чтобы сохранить непрерывность. А если серьезно, когда вам нужно перемещать в среднем половину своих записей после каждого удаления, то неважно, какую структуру данных вы используете, вы все равно испорчены. Просто перейдите с динамическим массивом.

Answer 4

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

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

Редактировать: ИМО, вы, вероятно, не хотите получить связанный список. Хотя связанный список делает само удаление постоянной скоростью, нахождение элемента является линейным, поэтому общая скорость равна O (N + K) = O (N). Для хеш-таблицы ожидаемая скорость будет O (1), а для дерева O (lg N).

Answer 5

Список связанных сортов сада будет соответствовать вашим требованиям. Но уточнение ваших требований даст лучшие рекомендации.

Например:

1. Важна ли скорость? Связанные списки вводят время поиска и выделяют / освобождают накладные расходы.
2. Вас беспокоит фрагментация памяти? Связанные списки с высокой активностью вставки / удаления могут со временем плохо фрагментировать память.
3. Каковы границы набора данных? Если вы ожидаете относительно ограниченный набор данных, тогда таблица совпадений может оказаться лучше связанного списка, который может увеличиться до произвольного размера.

Answer 6

Вы можете использовать (дважды) связанный список, сохраняя при этом непрерывную память.

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

У вас есть несколько вариантов управления предварительно выделенной памятью.

Одним из методов является использование очереди или стека доступных узлов, вы можете взять свободный узел, записать свои данные и добавить его в связанный список. Когда вы закончите работу с узлом, удалите его из связанного списка и поместите обратно в очередь / стек.

В зависимости от реализации стека / очереди это может означать поддержание двух связанных списков. Немного подумайте, чтобы получить эффективный и экономный дизайн со структурами данных и базовым кодом.

Answer 7

Звучит так, будто вам нужна самая распространенная структура данных - массив. В вашем случае это динамически размещаемый объект, аналогичный тому, который предоставляется классом C ++ std :: vector.

Answer 8

Используйте красно-черное дерево с пулом памяти для выделения элементов из смежного блока памяти. Примеры реализаций красно-черных деревьев, написанных на C, легко доступны . Большинство из них следует легко модифицировать для поддержки пользовательского распределителя памяти, если они еще не предоставляют такую ​​возможность.