Почему массивы не расширяемы?

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

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

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

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

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

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

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

Итак, вы можете Не просто расширяйте массив без его физического перемещения.

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

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

Многие языки просто обертывают массивы как коллекции, которые допускают такую ​​функциональность. Например, Java Vector / ArrayList автоматически перераспределяет память для вас. Связанный список фактически просто выделяет один элемент каждый раз с указателем на следующий. Делает это очень быстро добавить элементы, но очень медленно перейти к элементу 5000 (да ve для чтения каждого отдельного элемента, тогда как с элементом массива чтение 1 так же быстро, как элемент 5000)

Это зависит от языка.

В C (и подобных языках, таких как Java), когда вы объявляли массив типа int ary [10] , система выделяла ровно столько памяти, чтобы хранить десять целых чисел подряд. Расширять его было непросто, потому что система не выделяла дополнительное пространство (поскольку она не знает, хотите ли вы его расширить или на сколько), а память, которая появилась сразу после того, как массив, вероятно, использовался чем-то другим. Итак, единственный способ получить больший массив - это выделить новый блок памяти, который будет содержать расширенный массив, затем скопировать старое содержимое и добавить новые элементы.

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

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

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

Например, в языке программирования Curl есть тип FastArray, который имеет размер и max-size. max-size задает максимальный размер массива и определяет, сколько памяти будет выделено под массив. Существует более общий тип Array, который использует FastArray в качестве своей базовой реализации и заменяет экземпляр FastArray, если массив необходимо расширить сверх максимального размера базового FastArray.

Еще в языке ассемблера, человек был обязан объявить пространство памяти, необходимое для переменной. Это была зарезервированная память в регистре сегмента данных (DS).

Итак, примерно это выглядело так (Borland Turbo Assembler):

.DATA
    myStringVariable   DB   "Hello world!", 13, 10
    myArrayVariable    DW   "                    " 'Reserving 20 bytes in memory (in a row)

.CODE

    MOV AX, @DATA
    MOV DS, AX
    ' ...

Затем, когда сегмент .DATA был разграничен, он не мог быть изменен, поскольку сегмент .CODE (CS) начинался на несколько байт дальше.

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

C/C++ (3.0), Pascal (7.0), QBasic, PowerBasic и отладочные программы COM были основаны на этой архитектуре и не могли сделать ничего лучше того, что позволял Assembler.

Сегодня, благодаря более гибкой технологии, мы можем, я полагаю, выделять адреса памяти "на лету", по мере необходимости, и хранить ссылки на них с помощью всего одной переменной, поэтому массивы стали расширяемыми с помощью коллекционирования. Но есть некоторые ситуации, когда вам нужно хранить точное количество байт, например, сетевые пакеты и т.д., где массивы все еще полезны. Другой пример - хранение изображений в базе данных. Вы точно знаете, сколько байт занимает изображение, поэтому вы можете хранить его в байтовом массиве (Byte[]).

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

Надеюсь, это поможет! =)