Dynamic array

From Free Pascal wiki
Jump to: navigation, search

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 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.

  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.

Multidimensional arrays can be resized with setLength, too.

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

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.

  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. The highlighted line 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.

  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, forin 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