Difference between revisions of "Dynamic array"

From Free Pascal wiki
(Undo revision 121337 by Bart (talk): “array” is neuter, not a person)
 
(15 intermediate revisions by 5 users not shown)
Line 1: Line 1:
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.
+
{{Dynamic array}}
 +
 
 +
A '''dynamic array''' is an [[Array|array]] whose dimensions are not known at [[Compile time|compile-time]].
 +
The dynamic array type is not the only type providing variable-length arrays, but as of 2020 it is the only one [[FPC]] supports.
  
 
== usage ==
 
== usage ==
 
=== concept ===
 
=== concept ===
A dynamic array's definition will only allocate space for a [[Pointer|pointer]].
+
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).
+
During [[runtime]], various routines will ensure convenient usage but, most importantly, the syntax of accessing an array’s elements by placing indices in square brackets is supported by the [[Compiler|compiler]], implemented as automatic de-referencing of the pointer.
  
Dynamic arrays' indices are always non-negative integers starting at zero for the first element.
+
Dynamic arrays’ indices are always non-negative integers starting at zero for the first element. It is not possible to use an enumerative type or any other ordinal type as an index. The first element is always specified by an index of <syntaxhighlight lang="pascal" inline>0</syntaxhighlight>&nbsp;– this cannot be changed.
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 ===
 
=== definition ===
Line 15: Line 17:
 
array of char
 
array of char
 
</syntaxhighlight>
 
</syntaxhighlight>
Note, how no dimensions' size is specified.
+
Note how no dimensions’ size is specified.
 +
This is what distinguishes the definition from a normal array.
  
In order to define a multidimensional array, an array itself is specified as the base type.
+
In order to define a multidimensional array, an array itself is specified as the base type, thus creating an “array of arrays”:
 
<syntaxhighlight lang="pascal">
 
<syntaxhighlight lang="pascal">
 
array of array of longInt
 
array of array of longInt
Line 23: Line 26:
  
 
=== sizing ===
 
=== 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.
+
The compiler [[Procedure|procedure]] {{Doc|package=RTL|unit=system|identifier=setlength|text=<syntaxhighlight lang="pascal" inline>setLength</syntaxhighlight>}} will change a dynamic array’s length, provided there is enough memory.
 
<syntaxhighlight lang="pascal" line highlight="5">
 
<syntaxhighlight lang="pascal" line highlight="5">
 
program setLengthDemo(input, output, stdErr);
 
program setLengthDemo(input, output, stdErr);
Line 34: Line 37:
 
The procedure allocates memory for as many records of the base type as specified, plus some management data.
 
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.
 
It then {{Doc|package=RTL|unit=system|identifier=copyarray|text=''copies''}} all elements of the old incarnation to the new one.
 +
New fields that did not exist before are initialized with the <syntaxhighlight lang="delphi" inline>default</syntaxhighlight> intrinsic.
 +
 +
It is important to remember that, since all elements are copied during <syntaxhighlight lang="pascal" inline>setLength</syntaxhighlight>, it can become extremely inefficient to use it with large arrays, or inside inner loops.
  
Multidimensional arrays can be resized with <syntaxhighlight lang="pascal" enclose="none">setLength</syntaxhighlight>, too.
+
Multidimensional arrays can be resized with <syntaxhighlight lang="pascal" inline>setLength</syntaxhighlight>, too, by specifying multiple sizes in the call, like this:
 
<syntaxhighlight lang="pascal" line highlight="5">
 
<syntaxhighlight lang="pascal" line highlight="5">
 
program multidimensionalSetLengthDemo(input, output, stdErr);
 
program multidimensionalSetLengthDemo(input, output, stdErr);
Line 44: Line 50:
 
end.
 
end.
 
</syntaxhighlight>
 
</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>.
+
In this example, valid indices for <syntaxhighlight lang="pascal" inline>samples</syntaxhighlight>first dimension are in the range <syntaxhighlight lang="pascal" inline>0..11</syntaxhighlight>, while valid indices for its second dimension are within <syntaxhighlight lang="pascal" inline>0..63</syntaxhighlight>.
  
One quite useful fact is, the limitation all dimensions have to be of the same size does not apply to dynamic arrays.
+
One quite useful fact is that, because multidimensional dynamic arrays are always “arrays of arrays”, the limitation that all dimensions must be of the same size does not apply to them.
 +
Different dimensions are implemented as arrays, and can each have their own size.
 +
For instance,
 
<syntaxhighlight lang="pascal" line highlight="7,9,12,19">
 
<syntaxhighlight lang="pascal" line highlight="7,9,12,19">
 
program binomialPotence(input, output, stdErr);
 
program binomialPotence(input, output, stdErr);
Line 78: Line 86:
 
 
 
// ...
 
// ...
 +
</syntaxhighlight>
 +
 +
=== initializing ===
 +
[[FPC New Features 3.0.0#Dynamic array constructors|Since FPC 3.0.0]] dynamic array types that are not anonymous are automatically equipped with a “constructor” as it might be familiar from object-oriented programming.
 +
This lets you unite <syntaxhighlight lang="pascal" inline>setLength</syntaxhighlight> calls and a series of assignments in one statement:
 +
<syntaxhighlight lang="pascal" line highlight="7">
 +
program dynamicArrayCreateDemo(input, output, stdErr);
 +
type
 +
truths = array of boolean;
 +
var
 +
l: truths;
 +
begin
 +
l := truths.create(false, true, true, false, true, false, false);
 +
end.
 +
</syntaxhighlight>
 +
Of course you can nest arrays as well:
 +
<syntaxhighlight lang="pascal" line highlight="8-13">
 +
program nestedDynamicArrayCreateDemo(input, output, stdErr);
 +
type
 +
truths = array of boolean;
 +
pattern = array of truths;
 +
var
 +
p: pattern;
 +
begin
 +
p := pattern.create(
 +
truths.create(false, false),
 +
truths.create(true, false),
 +
truths.create(true, false, false),
 +
truths.create(true, true, false)
 +
);
 +
end.
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Line 83: Line 122:
 
Keep in mind dynamic arrays are pointers.
 
Keep in mind dynamic arrays are pointers.
 
Assigning dynamic array variables to each other does not copy any payload, but just the address.
 
Assigning dynamic array variables to each other does not copy any payload, but just the address.
This differs from static arrays' behavior.
+
This differs from static arrays’ behavior.
  
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>}}.
+
If you want to duplicate data you have to use {{Doc|package=RTL|unit=system|identifier=copy|text=<syntaxhighlight lang="pascal" inline>system.copy</syntaxhighlight>}}.
 
<syntaxhighlight lang="pascal" line highlight="25">
 
<syntaxhighlight lang="pascal" line highlight="25">
 
program dynamicArrayCopyDemo(input, output, stdErr);
 
program dynamicArrayCopyDemo(input, output, stdErr);
Line 117: Line 156:
 
end.
 
end.
 
</syntaxhighlight>
 
</syntaxhighlight>
Only by using <syntaxhighlight lang="pascal" enclose="none">copy</syntaxhighlight> both arrays can be modified independently.
+
Only by using <syntaxhighlight lang="pascal" inline>copy</syntaxhighlight> both arrays can be modified independently.
  
As stated above, <syntaxhighlight lang="pascal" enclose="none">setLength</syntaxhighlight> copies data.
+
As stated above, <syntaxhighlight lang="pascal" inline>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>.
+
This procedure can be used to make data unique again, despite the fact only the references, the pointers (so just addresses) have been copied (<syntaxhighlight lang="pascal" inline>bar := foo</syntaxhighlight>).
 +
The highlighted line in the example above could be replaced by <syntaxhighlight lang="pascal" inline>setLength(bar, length(bar))</syntaxhighlight>, though the <syntaxhighlight lang="pascal" inline>copy</syntaxhighlight> function is preferred as it is more explanatory.
  
 
Dynamic arrays are reference counted.
 
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.
+
Calling <syntaxhighlight lang="pascal" inline>setLength(myDynamicArrayVariable, 0)</syntaxhighlight> virtually does [[Nil|<syntaxhighlight lang="pascal" inline>myDynamicArrayVariable := nil</syntaxhighlight>]] and decreases the reference count.
 
Only when the reference count hits zero, the memory block is released.
 
Only when the reference count hits zero, the memory block is released.
 
<syntaxhighlight lang="pascal" line highlight="9,10,15">
 
<syntaxhighlight lang="pascal" line highlight="9,10,15">
Line 146: Line 186:
 
</syntaxhighlight>
 
</syntaxhighlight>
 
Nonetheless, dynamic arrays are finalized automatically.
 
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.
+
It is not necessary to manually <syntaxhighlight lang="pascal" inline>setLength(…, 0)</syntaxhighlight> on all your references when the program comes to end, or when leaving a scope in general.
  
Without <syntaxhighlight lang="pascal" enclose="none">{$rangeChecks on}</syntaxhighlight> it is possible to reach beyond an array's limits.
+
Without <syntaxhighlight lang="pascal" inline>{$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).
+
That means when iterating over dynamic arrays, it is impossible to work without {{Doc|package=RTL|unit=system|identifier=low|text=<syntaxhighlight lang="pascal" inline>low</syntaxhighlight>}} and {{Doc|package=RTL|unit=system|identifier=high|text=<syntaxhighlight lang="pascal" inline>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.
+
Alternatively, [[for-in loop|<syntaxhighlight lang="pascal" inline>for … in</syntaxhighlight> loops]] can be used, if no index is required.
  
Remember, [[SizeOf#dynamic arrays and alike|<syntaxhighlight lang="pascal" enclose="none">sizeOf</syntaxhighlight>]] of a dynamic array evaluates to the size of a pointer.
+
Remember, [[SizeOf#dynamic arrays and alike|<syntaxhighlight lang="pascal" inline>sizeOf</syntaxhighlight>]] of a dynamic array evaluates to the size of a pointer.
  
 
== application ==
 
== 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>}}
+
* there is {{Doc|package=RTL|unit=system|identifier=tboundarray|text=<syntaxhighlight lang="pascal" inline>system.tBoundArray</syntaxhighlight>}} and {{Doc|package=RTL|unit=objpas|identifier=tboundarray|text=<syntaxhighlight lang="pascal" inline>objPas.tBoundArray</syntaxhighlight>}}
  
 
== see also ==
 
== see also ==
* [[String|<syntaxhighlight lang="pascal" enclose="none">string</syntaxhighlight>]]
+
* [[String|<syntaxhighlight lang="pascal" inline>string</syntaxhighlight>]]
 
* example: [[Example: Multidimensional dynamic array|multidimensional dynamic array]]
 
* 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”]
 
* [https://www.freepascal.org/docs-html/ref/refsu14.html#x38-510003.3.1 Free Pascal Reference guide: “Dynamic arrays”]
  
[[Category:Code]]
+
[[Category: Code]]

Latest revision as of 23:29, 9 May 2021

English (en) suomi (fi) français (fr) 日本語 (ja) русский (ru)

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

usage

concept

A dynamic array’s definition will only allocate space for a pointer. During runtime, various routines will ensure convenient usage but, most importantly, the syntax of accessing an array’s elements by placing indices in square brackets is supported by the compiler, implemented as automatic de-referencing of 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 or any other ordinal type as an index. The first element is always specified by an index of 0 – this cannot be changed.

definition

A one-dimensional dynamic array is defined like this:

array of char

Note how no dimensions’ size is specified. This is what distinguishes the definition from a normal array.

In order to define a multidimensional array, an array itself is specified as the base type, thus creating an “array of arrays”:

array of array of longInt

sizing

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

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

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. New fields that did not exist before are initialized with the default intrinsic.

It is important to remember that, since all elements are copied during setLength, it can become extremely inefficient to use it with large arrays, or inside inner loops.

Multidimensional arrays can be resized with setLength, too, by specifying multiple sizes in the call, like this:

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

In this example, valid indices for samples’ first dimension are in the range 0..11, while valid indices for its second dimension are within 0..63.

One quite useful fact is that, because multidimensional dynamic arrays are always “arrays of arrays”, the limitation that all dimensions must be of the same size does not apply to them. Different dimensions are implemented as arrays, and can each have their own size. For instance,

 1 program binomialPotence(input, output, stdErr);
 2 var
 3 	pascalsTriangle: array of array of longWord;
 4 	exponent: longInt;
 5 	factor: longInt;
 6 begin
 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 	// ...

initializing

Since FPC 3.0.0 dynamic array types that are not anonymous are automatically equipped with a “constructor” as it might be familiar from object-oriented programming. This lets you unite setLength calls and a series of assignments in one statement:

1 program dynamicArrayCreateDemo(input, output, stdErr);
2 type
3 	truths = array of boolean;
4 var
5 	l: truths;
6 begin
7 	l := truths.create(false, true, true, false, true, false, false);
8 end.

Of course you can nest arrays as well:

 1 program nestedDynamicArrayCreateDemo(input, output, stdErr);
 2 type
 3 	truths = array of boolean;
 4 	pattern = array of truths;
 5 var
 6 	p: pattern;
 7 begin
 8 	p := pattern.create(
 9 			truths.create(false, false),
10 			truths.create(true, false),
11 			truths.create(true, false, false),
12 			truths.create(true, true, false)
13 		);
14 end.

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.

 1 program dynamicArrayCopyDemo(input, output, stdErr);
 2 
 3 var
 4 	foo, bar: array of char;
 5 
 6 procedure printArrays;
 7 begin
 8 	writeLn('foo[0] = ', foo[0], '; bar[0] = ', bar[0]);
 9 end;
10 
11 begin
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;
29 end.

Only by using copy both arrays can be modified independently.

As stated above, setLength copies data. This procedure can be used to make data unique again, despite the fact only the references, the pointers (so just addresses) have been copied (bar := foo). The highlighted line in the example above could be replaced by setLength(bar, length(bar)), though the copy function is preferred as it is more explanatory.

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.

 1 program dynamicArrayNilDemo(input, output, stdErr);
 2 var
 3 	foo, bar: array of char;
 4 begin
 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));
18 end.

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