Difference between revisions of "Dynamic array"

From Free Pascal wiki
Jump to navigationJump to search
(complete rewrite, with more structure, more examples, more huzzah)
Line 1: Line 1:
−
{{Dynamic array}}
+
A dynamic array is an [[Array|array]] its dimensions are not known during compile-time.
 +
The dynamic array type is not the only type providing variable-length arrays, but as of 2018 it is the only one [[FPC]] supports.
  
−
The dynamic array type is a very nice feature of FreePascal (and Delphi) syntax. It is very similar to the [[Array|array]] type, but allows more flexibility for the programmer since the number of elements does not need to be known until program execution.
+
== usage ==
 +
=== concept ===
 +
A dynamic array's definition will only allocate space for a [[Pointer|pointer]].
 +
During run-time various routines will ensure convenient usage, but most importantly the syntax how to access array's elements by placing indices in square brackets, is supported by the compiler (implemented as automatic de-referencing the pointer).
  
−
The declaration part is just as simple as for the [[Array|array]] type: 
+
Dynamic arrays' indices are always non-negative integers starting at zero for the first element.
−
<syntaxhighlight>
+
It is not possible to use an enumerative type, any other ordinal type as index, or to change the first element being specified by an index of <syntaxhighlight lang="pascal" enclose="none">1</syntaxhighlight>.
 +
 
 +
=== definition ===
 +
A one-dimensional dynamic array is defined like this:
 +
<syntaxhighlight lang="pascal">
 +
array of char
 +
</syntaxhighlight>
 +
Note, how no dimensions' size is specified.
 +
 
 +
In order to define a multidimensional array, an array itself is specified as the base type.
 +
<syntaxhighlight lang="pascal">
 +
array of array of longInt
 +
</syntaxhighlight>
 +
 
 +
=== sizing ===
 +
The compiler procedure {{Doc|package=RTL|unit=system|identifier=setlength|text=<syntaxhighlight lang="pascal" enclose="none">setLength</syntaxhighlight>}} will change a dynamic array's length, provided there is enough memory.
 +
<syntaxhighlight lang="pascal" line highlight="5">
 +
program setLengthDemo(input, output, stdErr);
 
var
 
var
−
  ...
+
sieve: array of longWord;
−
  MyVariable : array of type;
+
begin
−
  ...
+
setLength(sieve, 1337);
 +
end.
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
The procedure allocates memory for as many records of the base type as specified, plus some management data.
 +
It then {{Doc|package=RTL|unit=system|identifier=copyarray|text=''copies''}} all elements of the old incarnation to the new one.
  
−
The number of elements can be set or modified whenever needed during the execution of the program by inserting the statement:
+
Multidimensional arrays can be resized with <syntaxhighlight lang="pascal" enclose="none">setLength</syntaxhighlight>, too.
 +
<syntaxhighlight lang="pascal" line highlight="5">
 +
program multidimensionalSetLengthDemo(input, output, stdErr);
 +
var
 +
samples: array of array of smallInt;
 +
begin
 +
setLength(samples, 12, 64);
 +
end.
 +
</syntaxhighlight>
 +
Valid indices for <syntaxhighlight lang="pascal" enclose="none">samples</syntaxhighlight>' first dimension are in <syntaxhighlight lang="pascal" enclose="none">0..11</syntaxhighlight>, while valid indices for its second dimension are within the range <syntaxhighlight lang="pascal" enclose="none">0..63</syntaxhighlight>.
  
−
<syntaxhighlight>
+
One quite useful fact is, the limitation all dimensions have to be of the same size does not apply to dynamic arrays.
 +
<syntaxhighlight lang="pascal" line highlight="7,9,12,19">
 +
program binomialPotence(input, output, stdErr);
 +
var
 +
pascalsTriangle: array of array of longWord;
 +
exponent: longInt;
 +
factor: longInt;
 
begin
 
begin
−
  ...
+
setLength(pascalsTriangle, 20);
−
  SetLength(MyVariable, ItsNewLength);
+
−
  ...
+
setLength(pascalsTriangle[0], 1);
−
end
+
pascalsTriangle[0][0] := 1;
 +
 +
setLength(pascalsTriangle[1], 2);
 +
pascalsTriangle[1][0] := 1;
 +
pascalsTriangle[1][1] := 1;
 +
 +
// construct values by simple addition
 +
for exponent := 2 to high(pascalsTriangle) do
 +
begin
 +
setLength(pascalsTriangle[exponent], exponent + 1);
 +
pascalsTriangle[exponent][0] := 1;
 +
pascalsTriangle[exponent][exponent] := 1;
 +
for factor := 1 to exponent - 1 do
 +
begin
 +
pascalsTriangle[exponent][factor] :=
 +
pascalsTriangle[exponent - 1][factor - 1] +
 +
pascalsTriangle[exponent - 1][factor];
 +
end;
 +
end;
 +
 +
// ...
 
</syntaxhighlight>
 
</syntaxhighlight>
−
You can put as many '''SetLength''' statements as you want in your program in order to expand or truncate an array but you must put at least one statement before you can use the variable for the first time.
 
  
−
The individual elements can be accessed as follows:
+
=== handling ===
−
<syntaxhighlight>
+
Keep in mind dynamic arrays are pointers.
−
...
+
Assigning dynamic array variables to each other does not copy any payload, but just the address.
−
SetLength(MyVariable,19);
+
This differs from static arrays' behavior.
−
...
+
 
−
MyVariable[18] := 123;
+
If you want to duplicate data you have to use {{Doc|package=RTL|unit=system|identifier=copy|text=<syntaxhighlight lang="pascal" enclose="none">system.copy</syntaxhighlight>}}.
−
...
+
<syntaxhighlight lang="pascal" line highlight="25">
−
MyOtherVariable := MyVariable[0];
+
program dynamicArrayCopyDemo(input, output, stdErr);
−
...
+
 
−
WriteLn('MyVariable has ', Length(MyVariable), ' elements'); {should be 19}
+
var
−
...
+
foo, bar: array of char;
−
WriteLn('Its range is ', Low(MyVariable), ' to ', High(MyVariable)); {should be 0 to 18}
+
 
−
...
+
procedure printArrays;
 +
begin
 +
writeLn('foo[0] = ', foo[0], '; bar[0] = ', bar[0]);
 +
end;
 +
 
 +
begin
 +
setLength(foo, 1);
 +
foo[0] := 'X';
 +
// copies _reference_
 +
bar := foo;
 +
write('     initial values: ');
 +
printArrays;
 +
 +
// change content _via_ _second_ reference
 +
bar[0] := 'O';
 +
write('changed via 2nd ref: ');
 +
printArrays;
 +
 +
// copy content
 +
bar := copy(foo, 0, length(foo));
 +
bar[0] := 'X';
 +
write(' copied and changed: ');
 +
printArrays;
 +
end.
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
Only by using <syntaxhighlight lang="pascal" enclose="none">copy</syntaxhighlight> both arrays can be modified independently.
  
−
The index of a dynamic array is ZERO based, i.e. it must be within the range from 0 to (Length-1). It is NOT possible to change this to a ONE based system.
+
As stated above, <syntaxhighlight lang="pascal" enclose="none">setLength</syntaxhighlight> copies data.
 +
The <syntaxhighlight lang="pascal" enclose="none">copy</syntaxhighlight> call in the example above is (semantically) equivalent to <syntaxhighlight lang="pascal" enclose="none">setLength(bar, length(bar))</syntaxhighlight>.
 +
 
 +
Dynamic arrays are reference counted.
 +
Calling <syntaxhighlight lang="pascal" enclose="none">setLength(myDynamicArrayVariable, 0)</syntaxhighlight> virtually does [[Nil|<syntaxhighlight lang="pascal" enclose="none">myDynamicArrayVariable := nil</syntaxhighlight>]] and decreases the reference count.
 +
Only when the reference count hits zero, the memory block is released.
 +
<syntaxhighlight lang="pascal" line highlight="9,10,15">
 +
program dynamicArrayNilDemo(input, output, stdErr);
 +
var
 +
foo, bar: array of char;
 +
begin
 +
setLength(foo, 1);
 +
foo[0] := 'X';
 +
// copy _reference_, increase reference count
 +
bar := foo;
 +
// foo becomes nil, reference count is decreased
 +
setLength(foo, 0);
 +
writeLn('length(foo) = ', length(foo),
 +
'; length(bar) = ', length(bar));
 +
 +
// decrease reference count another time
 +
bar := nil;
 +
writeLn('length(foo) = ', length(foo),
 +
'; length(bar) = ', length(bar));
 +
end.
 +
</syntaxhighlight>
 +
Nonetheless, dynamic arrays are finalized automatically.
 +
It is not necessary to manually <syntaxhighlight lang="pascal" enclose="none">setLength(…, 0)</syntaxhighlight> on all your references when the program comes to end, or when leaving a scope in general.
  
−
Actually, dynamic arrays are pointers with automatic dereferencing. They are initialized to '''nil''' automatically. This means, that '''MyVariable''' is interpreted as a pointer variable when handed over to low level routines like '''fillchar''', '''sizeof''', etc. but it is automatically expanded to '''MyVariable^''' when indexing its elements (as in '''MyVariable[2]''') or when handing it over to routines that expect array types.
+
Without <syntaxhighlight lang="pascal" enclose="none">{$rangeChecks on}</syntaxhighlight> it is possible to reach beyond an array's limits.
 +
That means when iterating over dynamic arrays, it is impossible to work without {{Doc|package=RTL|unit=system|identifier=low|text=<syntaxhighlight lang="pascal" enclose="none">low</syntaxhighlight>}} and {{Doc|package=RTL|unit=system|identifier=high|text=<syntaxhighlight lang="pascal" enclose="none">high</syntaxhighlight>}} to determine valid indices (the former being optional, since dynamic arrays always start at zero).
 +
Alternatively, [[for-in loop|<syntaxhighlight lang="pascal" enclose="none">for … in</syntaxhighlight> loops]] can be used, if no index is required.
  
−
From a memory management view, dynamic array variables are simple pointers. '''SetLength''' allocates and frees memory on the heap as needed. When used in functions or procedures only the pointer is added to the stack. When the procedure exits, the dynamic array variable is removed and the memory is made available again. In fact, the memory management procedures are inserted in the executable program and the result is totally transparent to the programmer.
+
Remember, [[SizeOf#dynamic arrays and alike|<syntaxhighlight lang="pascal" enclose="none">sizeOf</syntaxhighlight>]] of a dynamic array evaluates to the size of a pointer.
  
−
Assigning '''nil''' to a dynamic array variable automatically frees the memory where the pointer pointed to. It's identical to '''SetLength(MyVariable, 0)'''. This can have a side effect, if the pointer value is not valid for some reason (i.e., if it was read from disk where it was stored from previous program runs). To init such an invalid pointer you have to use '''FillChar(MyVariable,sizeof(MyVariable), #0)'''.
+
== application ==
 +
* there is {{Doc|package=RTL|unit=system|identifier=tboundarray|text=<syntaxhighlight lang="pascal" enclose="none">system.tBoundArray</syntaxhighlight>}} and {{Doc|package=RTL|unit=objpas|identifier=tboundarray|text=<syntaxhighlight lang="pascal" enclose="none">objPas.tBoundArray</syntaxhighlight>}}
  
−
Although writing to elements of dynamic arrays does '''not''' create a new instance of the array (no copy-on-write as it exists for Ansistrings) using '''SetLength''' on such arrays '''does''' create a copy! So if 2 dynamic array variables point to the same array (one has been assigned to the other) they do not do so after using '''SetLength''' on one (or both) of them. After the SetLength() call the two variables are distinct arrays whose elements are independent from each other.
+
== see also ==
 +
* [[String|<syntaxhighlight lang="pascal" enclose="none">string</syntaxhighlight>]]
 +
* example: [[Example: Multidimensional dynamic array|multidimensional dynamic array]]
 +
* [https://www.freepascal.org/docs-html/ref/refsu14.html#x38-510003.3.1 Free Pascal Reference guide: “Dynamic arrays”]
  
−
== See also ==
+
[[Category:Code]]
−
* [https://www.freepascal.org/docs-html/ref/refsu14.html#x38-510003.3.1 Free Pascal Reference guide: Dynamic arrays]
 
−
* [[Example: Multidimensional dynamic array]]
 
−
* [[Array|Static array]]
 

Revision as of 20:52, 25 November 2018

A dynamic array is an array its dimensions are not known during compile-time. The dynamic array type is not the only type providing variable-length arrays, but as of 2018 it is the only one FPC supports.

usage

concept

A dynamic array's definition will only allocate space for a pointer. During run-time various routines will ensure convenient usage, but most importantly the syntax how to access array's elements by placing indices in square brackets, is supported by the compiler (implemented as automatic de-referencing the pointer).

Dynamic arrays' indices are always non-negative integers starting at zero for the first element. It is not possible to use an enumerative type, any other ordinal type as index, or to change the first element being specified by an index of 1.

definition

A one-dimensional dynamic array is defined like this: 

array of char

Note, how no dimensions' size is specified.

In order to define a multidimensional array, an array itself is specified as the base type. 

array of array of longInt

sizing

The compiler procedure setLength will change a dynamic array's length, provided there is enough memory. 

1program setLengthDemo(input, output, stdErr);
2var
3	sieve: array of longWord;
4begin
5	setLength(sieve, 1337);
6end.

The procedure allocates memory for as many records of the base type as specified, plus some management data. It then copies all elements of the old incarnation to the new one.

Multidimensional arrays can be resized with setLength, too. 

1program multidimensionalSetLengthDemo(input, output, stdErr);
2var
3	samples: array of array of smallInt;
4begin
5	setLength(samples, 12, 64);
6end.

Valid indices for samples' first dimension are in 0..11, while valid indices for its second dimension are within the range 0..63.

One quite useful fact is, the limitation all dimensions have to be of the same size does not apply to dynamic arrays. 

 1program binomialPotence(input, output, stdErr);
 2var
 3	pascalsTriangle: array of array of longWord;
 4	exponent: longInt;
 5	factor: longInt;
 6begin
 7	setLength(pascalsTriangle, 20);
 8	
 9	setLength(pascalsTriangle[0], 1);
10	pascalsTriangle[0][0] := 1;
11	
12	setLength(pascalsTriangle[1], 2);
13	pascalsTriangle[1][0] := 1;
14	pascalsTriangle[1][1] := 1;
15	
16	// construct values by simple addition
17	for exponent := 2 to high(pascalsTriangle) do
18	begin
19		setLength(pascalsTriangle[exponent], exponent + 1);
20		pascalsTriangle[exponent][0] := 1;
21		pascalsTriangle[exponent][exponent] := 1;
22		for factor := 1 to exponent - 1 do
23		begin
24			pascalsTriangle[exponent][factor] :=
25				pascalsTriangle[exponent - 1][factor - 1] +
26				pascalsTriangle[exponent - 1][factor];
27		end;
28	end;
29	
30	// ...

handling

Keep in mind dynamic arrays are pointers. Assigning dynamic array variables to each other does not copy any payload, but just the address. This differs from static arrays' behavior.

If you want to duplicate data you have to use system.copy. 

 1program dynamicArrayCopyDemo(input, output, stdErr);
 2
 3var
 4	foo, bar: array of char;
 5
 6procedure printArrays;
 7begin
 8	writeLn('foo[0] = ', foo[0], '; bar[0] = ', bar[0]);
 9end;
10
11begin
12	setLength(foo, 1);
13	foo[0] := 'X';
14	// copies _reference_
15	bar := foo;
16	write('     initial values: ');
17	printArrays;
18	
19	// change content _via_ _second_ reference
20	bar[0] := 'O';
21	write('changed via 2nd ref: ');
22	printArrays;
23	
24	// copy content
25	bar := copy(foo, 0, length(foo));
26	bar[0] := 'X';
27	write(' copied and changed: ');
28	printArrays;
29end.

Only by using copy both arrays can be modified independently.

As stated above, setLength copies data. The copy call in the example above is (semantically) equivalent to setLength(bar, length(bar)).

Dynamic arrays are reference counted. Calling setLength(myDynamicArrayVariable, 0) virtually does myDynamicArrayVariable := nil and decreases the reference count. Only when the reference count hits zero, the memory block is released. 

 1program dynamicArrayNilDemo(input, output, stdErr);
 2var
 3	foo, bar: array of char;
 4begin
 5	setLength(foo, 1);
 6	foo[0] := 'X';
 7	// copy _reference_, increase reference count
 8	bar := foo;
 9	// foo becomes nil, reference count is decreased
10	setLength(foo, 0);
11	writeLn('length(foo) = ', length(foo),
12		'; length(bar) = ', length(bar));
13	
14	// decrease reference count another time
15	bar := nil;
16	writeLn('length(foo) = ', length(foo),
17		'; length(bar) = ', length(bar));
18end.

Nonetheless, dynamic arrays are finalized automatically. It is not necessary to manually setLength(…, 0) on all your references when the program comes to end, or when leaving a scope in general.

Without {$rangeChecks on} it is possible to reach beyond an array's limits. That means when iterating over dynamic arrays, it is impossible to work without low and high to determine valid indices (the former being optional, since dynamic arrays always start at zero). Alternatively, for … in loops can be used, if no index is required.

Remember, sizeOf of a dynamic array evaluates to the size of a pointer.

application

see also

Retrieved from "http://wiki.freepascal.org/index.php?title=Dynamic_array&oldid=121335"