ВУЗ:
Составители:
Рубрика:
6
size. Рассмотрим два противоположных подхода. Первый подход заключается в
следующем: под массив отводится максимально возможная память, а при измене-
нии размера меняется только значение закрытого поля, хранящего текущий раз-
мер массива. Это решение – эффективное по скорости, но расточительное по па-
мяти. Второй подход – всякий раз выделяется память, размер которой совпадает
с
размером массива. Такое решение эффективно по памяти, но крайне неэффектив-
но по скорости работы. Действительно, при каждом изменении размера надо соз-
давать новый участок памяти, копировать в него содержимое старого массива и
освобождать старый участок памяти. К примеру, если массив состоит из 1000
элементов, то при добавлении одного элемента необходимо выделить
память под
1001 элемент, скопировать 1000 элементов в эту память и освободить старую па-
мять.
Как известно, истина находится посередине между полярными мнениями.
Обычно выбирается следующая стратегия изменения размера динамического мас-
сива. В начальный момент времени под массив отводится память, превосходящая
его размер. Если при выполнении Resize новый размер не превосходит выде
-
ленную память, то просто меняется внутреннее поле, характеризующее размер. В
противном случае выделяется новая память, происходит копирование старого со-
держимого в новую память и старое содержимое освобождается. Размер выделяе-
мой памяти должен превосходить новый размер массива с прицелом на дальней-
шее увеличение. Обычно принимают следующую стратегию: выделяют память, в
2 раза
превосходящую запрашиваемый размер. Назовем метод, ответственный за
выделение памяти, именем Reserve. Отметим, что выделенная память не ини-
циализируется нулями, поэтому за ее инициализацию ответственна клиентская
программа.
Таким образом, динамический массив характеризуется не только своим раз-
мером Count, но и так называемой емкостью Capacity, определяющей количе-
ство элементов, под которые выделена память.
В любой момент времени
Size<=Capacity. Если вызывается Resize(newsize) с news-
ize<=Capacity, то Size просто устанавливается равным newsize, в против-
ном случае вначале резервируется новая память, в 2 раза превосходящая затребо-
ванный размер: Reserve(2*newsize).
Заметим, что, согласно нашим договоренностям, при уменьшении размера
массива новая память не выделяется. Таким образом, память, отводимая под мас-
сив, в течение его существования может только расти. В реальных же задачах не-
редка ситуация, когда размер массива в начале программы может быть значитель-
ным, а в конце – маленьким. Например, в поисковой системе мы вначале отбира-
ем 1000 сайтов, удовлетворяющих запросу, а потом выбираем из них 10 лучших, и
потом работаем только с
ними. В этой ситуации следует предусмотреть возмож-
ность уменьшения объема выделяемой под массив памяти. Наиболее простая реа-
лизация заключается в следующем: в интерфейс класса вводят метод
Страницы
- « первая
- ‹ предыдущая
- …
- 2
- 3
- 4
- 5
- 6
- …
- следующая ›
- последняя »
