Какие структуры данных можно использовать для реализации пула целых чисел?

Question

Эти целые числа могут быть IP-адресами (DHCP) или идентификаторами сеансов или идентификаторами туннелей (например, в L2TP).Каждое целое число может быть свободным или использоваться.Нам нужно, чтобы он был эффективен для поиска бесплатных.

Там также определены минимальные и максимальные значения.

Answer 1

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

Поддержка списков будет стоить, но поиск бесплатный номер будет быстрым

Answer 2

Хорошо, так как у вас есть максимум и минимум, у меня есть следующая идея: Вы поддерживаете этот максимум или минимум динамически и имеете список свободных целых чисел. Сначала вы начинаете с пустого списка и полного диапазона. Когда кто-то сдает в аренду целое число, диапазон уменьшается в размере на единицу, если список пуст, если мы не берем его из списка. Если он выпускает свое целое число, есть 2 возможности:

1. Он подходит к краю вашего максимального / минимального диапазона, поэтому вы увеличиваете размер диапазонов
2. Он находится далеко от диапазона, поэтому вы помещаете его в список

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

Answer 3

Ожидаете ли вы иметь больше свободных или больше используемых целых чисел?И хотите ли вы сохранить IP-адреса, SessIds и TunIds одновременно или каждый, исключая другие?

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

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