память — реализация кучи C ++
C ++ имеет два основных типа памяти: куча и стек. Со стеком все понятно, и у меня возник вопрос — как реализуется куча памяти. Я пытался гуглить, читал о структура данных кучи, но, похоже, это не так, потому что в C ++ я могу получить доступ к любым данным из кучи, а не только с помощью min или max.
Итак, мой вопрос, как кучи памяти организованы в C ++? Когда мы читаем «выделено в куче», какую организацию памяти следует иметь в виду?
Решение
Обычная (хотя, конечно, не единственная) реализация бесплатного хранилища представляет собой связанный список свободных блоков памяти (то есть блоков, которые в данный момент не используются). Менеджер кучи обычно выделяет большие блоки памяти (например, по 1 мегабайту за раз) из операционной системы, а затем разделяет эти блоки на части для использования вашим кодом при использовании. new и тому подобное. Когда вы используете deleteблок памяти, который вы используете, будет добавлен как узел в этот связанный список.
Существуют различные стратегии использования этих бесплатных блоков. Три наиболее подходящих, наиболее подходящих и наиболее подходящих.
В лучшем случае вы пытаетесь найти свободный блок, который по размеру ближе к требуемому выделению. Если он больше требуемого (обычно после округления размера выделения), вы разделяете его на две части: одну для возврата для выделения и новый (меньший) свободный блок для возврата в список для удовлетворения других запросов выделения. Хотя это может показаться хорошей стратегией, это часто проблематично. Проблема в том, что, когда вы находите наиболее близкое соответствие, оставшийся блок часто оказывается слишком маленьким, чтобы его можно было использовать. Через короткое время вы получите огромное количество крошечных блоков свободного пространства, ни один из которых не годится ни для чего.
Худшая подгонка борется с этим, вместо этого находя худшую подгонку среди свободных блоков — IOW, самый большой блок свободного пространства. Когда он разделяет этот блок, то, что осталось, будет как можно больше, максимально увеличивая вероятность того, что это будет полезно для других распределений.
Первый кулак просто просматривает список свободных блоков и (как можно догадаться из названия) использует первый блок, достаточно большой, чтобы соответствовать требованию.
Многие из них также начинают с поиска точного соответствия и используют его в предпочтении разбиению блока.
Многие также сохраняют (например) несколько отдельных связанных списков для разных размеров размещения, чтобы минимизировать поиск блока правильного размера.
Во многих случаях у менеджера также есть некоторый код для просмотра списка свободных блоков, чтобы найти те, которые находятся рядом друг с другом. Если он их найдет, он объединит два небольших блока в один большой блок. Иногда это делается правильно, когда вы free/delete Блок. Чаще это делается лениво, чтобы избежать объединения, а затем повторного разделения блоков, когда / если вы используете много блоков одинакового размера (что довольно распространено).
Другая возможность, которая часто встречается при работе с большим количеством элементов одинакового размера (особенно небольших), — это массив блоков с набором битов для указания того, какие из них бесплатны или используются. В этом случае вы обычно отслеживаете индекс в битовом наборе, где был найден последний свободный блок. Когда требуется блок, просто ищите вперед от последнего индекса, пока не найдете следующий, для которого набор битов говорит, что блок свободен.
Другие решения
Куча имеет два основных значения с двумя разными понятиями:
- Структура данных для упорядочения данных, дерево.
- Пул доступной памяти. Он управляет памятью путем выделения / освобождения доступных блоков памяти.
Введение о Куча в управлении памятью:
Куча — это другая область динамической памяти, выделенная / освобожденная
malloc / free и их варианты ….
Здесь куча не означает структуру данных кучи. Эта память называется кучной памятью, где хранятся глобальные статические переменные. Также, когда мы выделяем память динамически, она выделяется в куче памяти.
Когда вы читаете «размещено в куче», обычно это зависит от реализации реализации «динамической длительности хранения» в C ++. Это означает, что вы использовали new выделить память, и иметь указатель на нее, что теперь вы должны следить за вами delete (или же delete[]) Это.
Что касается того, как это организовано, нет единого установленного способа сделать это. В какой-то момент, если память служит, «куча» используется на самом деле быть минимальная куча (организованная по размеру блока). Это зависит от реализации, и не должно быть так. Подойдет любая структура данных, некоторые лучше, чем другие для данных обстоятельств.