Пул ресурсов для структуры данных

Question

При реализации элементарной структуры данных, такой как stack, queues, linked list и др. я должен создать пул ресурсов (узлов) путем динамического выделения памяти в связке, или я должен выделять память отдельно каждый раз, когда мне нужен узел?

Answer 1

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

Пулы памяти по сравнению с просто распределением узлов:

• Сделайте выделение быстрее.В зависимости от используемого механизма выделения иногда значительно быстрее.

• Обычно меньше фрагментации памяти, хотя это может не быть проблемой для некоторых распределителей.

• Основной недостаток: потеря памяти на зарезервированных, но не используемых узлах.Это очень важно, если вы используете структуру данных без разбора (например, тысячи экземпляров), а не просто пару экземпляров.

Из-за недостатка пулы памяти не являютсяподходит для общих ситуаций.

В C ++ все стандартные контейнеры имеют параметр шаблона allocator.

Answer 2

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

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

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

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