Динамический или статический?

### Баннеры

# Динамический или статический?

Просмотров: 25586

Традиционно в языке Паскаль используются статические массивы вида

    var a: array [1..10] of integer;

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

    var LettersCount: array ['a'..'z'] of integer;

и работать с ним в свое удовольствие:

    LettersCount['z'] := 1;
    LettersCount['d'] := LettersCount['d'] + 1;

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

В Delphi Object Pascal появились динамические массивы, размер которых можно не только задавать, но и менять по ходу работы программы. Именно об этих массивах и о преимуществах их использования пойдет речь далее.

Описываются они предельно просто:

    var a: array of integer;

Чтобы задать размер такого массива, следует вызвать процедуру SetLength:

    var n: integer;
    read(n);
    SetLength(a,n);

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

Чтобы определить размер динамического массива, следует вызвать функцию Length: Length(a) возвращает размер динамического массива.

Индексы динамического массива - только целочисленные. Кроме того, нижняя граница индекса всегда равна нулю. То есть после вызова SetLength(a,n) элементами массива a являются a[0]..a[n-1]. Вот как вывести элементы динамического массива:

    for i:=0 to Length(a)-1 do
      write(a[i],' ');

Чем замечательна процедура SetLength - так это тем, что она может вызываться повторно, и при последующих вызовах старое содержимое массива сохраняется:

    SetLength(a,3);
    a[0] := 666;
    SetLength(a,5);
    writeln(a[0]); // выведется 666

Динамические массивы представляются в памяти ссылками. Это означает, что любая переменная типа "динамический массив" является указателем на непрерывный участок динамической памяти. Первоначально этот указатель хранит nil, а вызов SetLength(a) выделяет под данные массива блок динамической памяти и записывает в a адрес этого блока памяти.

Тот факт, что переменные - динамические массивы - это всего лишь адреса, имеет несколько следствий.

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

    var a1,a2: array [1..10] of integer;
    var b1,b2: array of integer;
    a1 := a2; // копируется содержимое
    b1 := b2; // копируется указатель

То есть, присваивание больших статических массивов происходит долго, а присваивание динамических - быстро независимо от их размера.

Во-вторых, при присваивании динамических массивов обе пременные b1 и b2 указывают на один участок динамической памяти, поэтому изменение элемента в массиве b1 приводит и к изменению массива b2:

    b1[0] := 5;
    writeln(b2[0]); // выведется 5

Чтобы создать копию данных динамического массива, необходимо вызвать функцию Copy:

    b2[0] := 3;
    b1 := Copy(b2);
    b1[0] := 5;
    writeln(b2[0]); // выведется 3

Передача динамических массивов в подпрограммы тоже проста:

    type IntArr = array of integer;

    procedure print(a: IntArr);
    var i: integer;
    begin
      for i:=0 to Length(a)-1 do
        write(a[i],' ');
    end;

    var b: IntArr;
    ...
    print(b);

Передавать динамические массивы по ссылке чтобы исключить копирование массива не имеет никакого смысла - в подпрограмму передается указатель. Динамический массив имеет смысл передавать как var-параметр только в одном случае: если мы отводим в подпрограмме для него память:

    procedure CreateAndFill(var a: IntArr; n: integer; fill: integer);
    var i: integer;
    begin
      SetLength(a,n);
      for i:=0 to n-1 do
        a[i] := fill;
    end.

И, наконец, в использовании динамических массивов в подпрограммах скрыта одна западня: если мы меняем элемент массива внутри подпрограммы, то меняется соответствующий массив - фактический параметр:

    procedure Trap(a: IntArr);
    begin
      a[0] := 666;
    end;

    var b: IntArr;
    ...
    b[0] := 777;
    Trap(b);
    writeln(b[0]); // выведется 666

Еще в Delphi имеются так называемые открытые массивы. К сожалению, они по внешнему виду очень похожи на динамические:

    procedure print1(a: array of integer);
    var i: integer;
    begin
      for i:=0 to High(a)-1 do
        write(a[i],' ');
    end;

Смысл в том, что при вызове на место открытого массива можно подставлять статический массив любого размера. Но запись array of integer используется в совершенно другом смысле! Поэтому мы полностью отказались от открытых массивов в PascalABC.NET. Пользуйтесь динамическими массивами!

Посмотрим теперь, что нового появилось в динамических массивах в PascalABC.NET.

1. Динамические массивы можно инициализировать при описании:

    var a: array of integer := (1,3,5);

2. Выделять память под динамическе массивовы можно с помощью операции new:

    a := new integer[5];

Такой способ хорош тем, что он подчеркивает, что динамический массив в .NET является классом. Плох же он тем, что при повторном выделении памяти таким способом старое содержимое теряется.

3. Как мы упомянули, динамический массив в PascalABC.NET является классом, а значит, он имеет методы и свойства:

a.Length - свойство, возвращающее длину массива
System.Array.Sort(a) - статический метод, сортирующий массив a по возрастанию
System.Array.Reverse(a) - статический метод, инвертирующий данные в массиве a

и многие другие.

4. Для динамических массивов в PascalABC.NET имеет место структурная эквивалентность типов (в Delphi - именная). Поэтому следующий код в PascalABC.NET будет работать, а в Delphi вызовет ошибку компиляции:

    var
    b1: array of integer;
    b2: array of integer;
    ...
    b1 := b2;

5. Ввиду структурной эквивалентности типов для динамических массивов их можно передавать в подпрограмму следующим образом:

    procedure print(a: array of integer);
    begin
      for var i:=0 to a.Length-1 do
        write(a[i],' ');
    end;

Напомним, что открытые массивы в PascalABC.NET отсутствуют!

6. Для динамических массивов (в отличие от статических) можно использовать цикл foreach (при условии, что мы осуществляем доступ к элементам только на чтение):

    foreach x: integer in a do
      write(x,' ');

И, наконец, скажем несколько слов про двумерные динамические массивы. Они моделируются как массивы массивов.

Следующий код иллюстрирует создание двумерного динамического массива размера m на n:

    var
      с: array of array of integer;
      m,n: integer;
    ...
    read(m,n);
    SetLength(с,m);
    for var i:=0 to m-1 do
      SetLength(c[i],n);

- Назад
- Вперёд

### Новости

12.02.16. Вышла версия 3.1. Добавлены кортежи в стиле (a,b) и кортежное присваивание (a,b) := (b,a)

31.12.15. Версия 3.0.0.1128. Реализованы обобщенные методы расширения для операций

22.12.15. Версия 3.0.0.1116. Реализован новый синтаксис extension-методов

28.08.15. Вышла версия PascalABC.NET 3.0. Здесь - новое в версии 3.0.

### Случайная программа

    // Линейный поиск в массиве
    // Уровень сложности: 1
    uses Arrays;

    function IndexOf(a: array of integer;
      k: integer): integer;
    begin
      Result := -1;
      for var i:=0 to a.Length-1 do
        if a[i] = K then
        begin
          Result := i;
          exit
        end;
    end;

    const N = 10;

    var a: array of integer;

    begin
      a := CreateRandomIntegerArray(N,0,19);
      writeln('Исходный массив: ');
      a.Writeln;

      var k := Random(10);
      writeln('Ищем элемент = ',k);

      var ind := IndexOf(a,k);
      if ind >=0 then
        writeln(K,' найден; индекс первого вхождения = ',ind)
      else writeln(K,' не найден')
    end.