Difference between revisions of "Array"
RogueScholar (talk | contribs) m (Fix link capitalization oversights) |
|||
(56 intermediate revisions by 20 users not shown) | |||
Line 1: | Line 1: | ||
− | + | {{Array}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | The array is in | + | An '''array''' is a linear data structure concept that groups elements of the same type, stores them in contiguous and adjacent memory locations and provides random access to all of said elements (also known as components) by way of a linear index. |
− | + | ||
− | to | + | The word <syntaxhighlight lang="pascal" inline>array</syntaxhighlight> is a [[Reserved word|reserved word]]. It always occurs in conjunction with the word [[Of|<syntaxhighlight lang="pascal" inline>of</syntaxhighlight>]]. |
+ | |||
+ | == Notion == | ||
+ | An <syntaxhighlight lang="pascal" inline>array</syntaxhighlight> is a limited and arranged aggregation of elements, all having the same [[Data type|data type]] which is called the “base type.” It has at least one discrete, bounded dimension and continuously enumerates all of its elements. Each element can be uniquely identified by one or more scalar values, called ''indices'', along those dimensions. | ||
+ | |||
+ | A one-dimensional <syntaxhighlight lang="pascal" inline>array</syntaxhighlight> resembles an '''n-tuple''', as it is known in mathematics, but has the constraint of being homogenous (all elements must be of the same type). The range of all possible values such an <syntaxhighlight lang="pascal" inline>array</syntaxhighlight> can acquire is the homogenous n-ary Cartesian product of the base type. | ||
+ | |||
+ | A two-dimensional <syntaxhighlight lang="pascal" inline>array</syntaxhighlight> resembles the mathematical concept of a '''matrix''', except for the homogeneity restriction. | ||
+ | |||
+ | == Usage == | ||
+ | === Length === | ||
+ | Originally, Pascal only provided arrays of fixed length ([[Standard Pascal]]), meaning the number of elements an array consisted of had to be known at compile-time. Since this turned out to be a major constraint, and changes in computer hardware since then justified a step forward, variable-length arrays were introduced. | ||
+ | |||
+ | [[Extended Pascal]] defined the notion of “schemata” for this. [[Delphi]] introduced “dynamic arrays”. As of 2020, [[FPC]] only supports the latter regarding variable-length arrays, while support for “schemata” is planned. | ||
+ | |||
+ | Depending on whether an array is intended of being capable of changing its size, its definition varies, but just marginally. For a one-dimensional static array, the type definition looks like this: <syntaxhighlight lang="pascal"> | ||
+ | array[indexType] of baseType | ||
+ | </syntaxhighlight> | ||
+ | A dynamic array type definition is simply relieved of its dimension specification: | ||
+ | <syntaxhighlight lang="pascal"> | ||
+ | array of baseType | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === Static arrays === | ||
+ | In static arrays, the ranges of all dimensions are known in advance. All dimension specifications have to be ordinal types. The following code shows some valid array definitions, all of them static. | ||
+ | <syntaxhighlight lang="pascal" highlight="8,15,17,21,22,23" line> | ||
+ | program staticArrayDemo(input, output, stderr); | ||
+ | |||
+ | type | ||
+ | // specifying ordinal types as index directly | ||
+ | |||
+ | /// allows selection of a character | ||
+ | /// based on a Boolean value | ||
+ | characterChoice = array[boolean] of UCS4char; | ||
+ | |||
+ | // enumerations | ||
+ | |||
+ | /// enumerates Cartesian axes | ||
+ | spaceAxis = (xAxis, yAxis, zAxis); | ||
+ | /// a point in three-dimensional Euclidean space | ||
+ | locus = array[spaceAxis] of valReal; | ||
+ | /// a point in a two-dimensional Euclidean plane | ||
+ | point = array[xAxis..yAxis] of valReal; | ||
+ | |||
+ | // integer subranges | ||
+ | |||
+ | level = array[-24..24] of longint; | ||
+ | box = array[-1..1, -1..1, -1..1] of boolean; | ||
+ | transformationMatrix = array[0..1, 0..1] of valReal; | ||
+ | begin | ||
+ | end. | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | As all of an array’s elements have to be addressable, there exists a maximum limit of elements an array can hold. The [[SizeOf|<syntaxhighlight lang="pascal" inline>sizeOf</syntaxhighlight>]] every array type has to be less than {{Doc|package=RTL|unit=system|identifier=ptrint|text=<syntaxhighlight lang="pascal" inline>ptrInt</syntaxhighlight>}}’s maximum value. | ||
+ | |||
+ | === Initialization === | ||
+ | It's possible to set the initial values of a static (and dynamic) array's elements when it is declared – | ||
+ | <syntaxhighlight lang="pascal"> | ||
+ | var | ||
+ | SArray : array[0..2] of integer = (1,2,3); // A static Array | ||
+ | CArray : array[0..1] of TColor = (clRed, clBlue); // A static Array | ||
+ | </syntaxhighlight> | ||
+ | |||
+ |   '''See more:''' [https://forum.lazarus.freepascal.org/index.php/topic,52656.15.html Topic: How to initialize the array (Free Pascal Lazarus Forum)] | ||
+ | |||
+ | === Addressing elements === | ||
+ | An array’s element is addressed by naming the array variable’s identifier, followed by a valid index value enclosed by square brackets. | ||
+ | <syntaxhighlight lang="pascal" highlight="5-7" line> | ||
+ | program arrayAddressDemo(input, output, stderr); | ||
+ | var | ||
+ | msg: array[0..2] of char; | ||
+ | begin | ||
+ | msg[0] := 'H'; | ||
+ | msg[1] := 'i'; | ||
+ | msg[2] := '!'; | ||
+ | writeLn(msg); | ||
+ | end. | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Multidimensional arrays’ elements can be addressed in two ways: either by [[Comma|comma]]-separated indices… | ||
+ | <syntaxhighlight lang="pascal"> | ||
+ | arrayVariable[firstDimensionIndex, secondDimensionIndex, thirdDimensionIndex] | ||
+ | </syntaxhighlight> | ||
+ | …or by putting indices in dedicated square brackets. | ||
+ | <syntaxhighlight lang="pascal"> | ||
+ | arrayVariable[firstDimensionIndex][secondDimensionIndex][thirdDimensionIndex] | ||
+ | </syntaxhighlight> | ||
+ | A third syntactically-valid option would be mixing both styles, however that is considered poor style, unless perhaps there is indication to group indices (e.g. <syntaxhighlight lang="pascal" inline>x</syntaxhighlight>, <syntaxhighlight lang="pascal" inline>y</syntaxhighlight> and <syntaxhighlight lang="pascal" inline>z</syntaxhighlight> coordinates versus other indices) it is okay. Nonetheless, only the first mentioned notation is valid while defining array types. | ||
+ | |||
+ | Note, it is very important to specify indices in the defined order, within each dimensions’ range. Consider the following program; it will compile, but fail during [[runtime|run-time]] due to <syntaxhighlight lang="pascal" inline>{$rangeChecks on}</syntaxhighlight>: | ||
+ | <syntaxhighlight lang="pascal"> | ||
+ | program arrayAddressOrderDemo(input, output, stderr); | ||
+ | {$rangeChecks on} | ||
+ | var | ||
+ | i: integer; | ||
+ | f: array[0..1, 0..3] of boolean; | ||
+ | begin | ||
+ | for i := 0 to 7 do | ||
+ | begin | ||
+ | f[0, i] := true; | ||
+ | end; | ||
+ | end. | ||
+ | </syntaxhighlight> | ||
+ | While the program would indeed iterate over every array’s elements, it doesn’t do so in the intended way, but rather exploits the fact that the array’s internal memory structure is just a continuous block of memory. This is bad style. A programmer working with a high-level language is not supposed to care about specific memory layouts. Cave: It is possible to tamper with other variables in this way. At any rate, a [[runtime error|run-time error]], namely “RTE 216 general protection fault,” will occur if an attempt is made to access memory which is not within the purview of the process owner. | ||
+ | |||
+ | When values contained in arrays are merely read (and thus the indices do not matter), a [[for-in loop|<syntaxhighlight lang="pascal" inline>for … in</syntaxhighlight> loop]] can be used. | ||
+ | |||
+ | == Dynamic arrays == | ||
+ | A [[Dynamic array|dynamic array]] is an approach for overcoming the limitation of knowing the sizes of all dimensions in advance. See its dedicated page for more details. | ||
+ | |||
+ | == Application == | ||
+ | See, for instance: | ||
+ | * [[Array sort]] | ||
+ | * [[15-puzzle]]’s and [[Peg Solitaire tutorial|Peg]]’s game board states are stored as an array. | ||
+ | |||
+ | In the default [[RTL]]’s system unit, the function {{Doc|package=RTL|unit=system|identifier=slice|text=<syntaxhighlight lang="pascal" inline>system.slice</syntaxhighlight>}} returns the initial part of an array, similar to the Ruby notation <syntaxhighlight lang="ruby" inline>arrayVariable[0, n]</syntaxhighlight>. Furthermore, there is {{Doc|package=RTL|unit=system|identifier=arraystringtoppchar|text=<syntaxhighlight lang="pascal" inline>system.arrayStringToPPchar</syntaxhighlight>}}. Most [[Functions for descriptive statistics|statistical routines of the RTL’s math unit]] accept arrays as parameters, as well as some other routines. | ||
+ | |||
+ | == See also == | ||
+ | * [[Type information]] | ||
+ | * [[Defensive programming techniques]] | ||
+ | * [[Vectorization]] | ||
+ | * [[Flexible Array Member]] | ||
+ | * Tutorial: [[Basic Pascal Tutorial/Chapter 5/1-dimensional arrays|1-dimensional arrays]] | ||
+ | * Tutorial: [[Basic Pascal Tutorial/Chapter 5/Multidimensional arrays|Multidimensional arrays]] | ||
+ | * Example: [[Example: Multidimensional dynamic array|Multidimensional dynamic array]] | ||
+ | * Article: [[Why Pascal is Not My Favorite Programming Language#The size of an array is part of its type|Why Pascal is not my favorite programming language § “The size of an array is part of its type”]] | ||
+ | * {{Doc|package=RTL|unit=matrix|text=<syntaxhighlight lang="pascal" inline>matrix</syntaxhighlight> unit}} | ||
+ | {{Data types}} |
Latest revision as of 22:30, 20 September 2023
│
Deutsch (de) │
English (en) │
español (es) │
suomi (fi) │
français (fr) │
Bahasa Indonesia (id) │
日本語 (ja) │
русский (ru) │
中文(中国大陆) (zh_CN) │
An array is a linear data structure concept that groups elements of the same type, stores them in contiguous and adjacent memory locations and provides random access to all of said elements (also known as components) by way of a linear index.
The word array
is a reserved word. It always occurs in conjunction with the word of
.
Notion
An array
is a limited and arranged aggregation of elements, all having the same data type which is called the “base type.” It has at least one discrete, bounded dimension and continuously enumerates all of its elements. Each element can be uniquely identified by one or more scalar values, called indices, along those dimensions.
A one-dimensional array
resembles an n-tuple, as it is known in mathematics, but has the constraint of being homogenous (all elements must be of the same type). The range of all possible values such an array
can acquire is the homogenous n-ary Cartesian product of the base type.
A two-dimensional array
resembles the mathematical concept of a matrix, except for the homogeneity restriction.
Usage
Length
Originally, Pascal only provided arrays of fixed length (Standard Pascal), meaning the number of elements an array consisted of had to be known at compile-time. Since this turned out to be a major constraint, and changes in computer hardware since then justified a step forward, variable-length arrays were introduced.
Extended Pascal defined the notion of “schemata” for this. Delphi introduced “dynamic arrays”. As of 2020, FPC only supports the latter regarding variable-length arrays, while support for “schemata” is planned.
Depending on whether an array is intended of being capable of changing its size, its definition varies, but just marginally. For a one-dimensional static array, the type definition looks like this:
array[indexType] of baseType
A dynamic array type definition is simply relieved of its dimension specification:
array of baseType
Static arrays
In static arrays, the ranges of all dimensions are known in advance. All dimension specifications have to be ordinal types. The following code shows some valid array definitions, all of them static.
1program staticArrayDemo(input, output, stderr);
2
3type
4 // specifying ordinal types as index directly
5
6 /// allows selection of a character
7 /// based on a Boolean value
8 characterChoice = array[boolean] of UCS4char;
9
10 // enumerations
11
12 /// enumerates Cartesian axes
13 spaceAxis = (xAxis, yAxis, zAxis);
14 /// a point in three-dimensional Euclidean space
15 locus = array[spaceAxis] of valReal;
16 /// a point in a two-dimensional Euclidean plane
17 point = array[xAxis..yAxis] of valReal;
18
19 // integer subranges
20
21 level = array[-24..24] of longint;
22 box = array[-1..1, -1..1, -1..1] of boolean;
23 transformationMatrix = array[0..1, 0..1] of valReal;
24begin
25end.
As all of an array’s elements have to be addressable, there exists a maximum limit of elements an array can hold. The sizeOf
every array type has to be less than ptrInt
’s maximum value.
Initialization
It's possible to set the initial values of a static (and dynamic) array's elements when it is declared –
var
SArray : array[0..2] of integer = (1,2,3); // A static Array
CArray : array[0..1] of TColor = (clRed, clBlue); // A static Array
See more: Topic: How to initialize the array (Free Pascal Lazarus Forum)
Addressing elements
An array’s element is addressed by naming the array variable’s identifier, followed by a valid index value enclosed by square brackets.
1program arrayAddressDemo(input, output, stderr);
2var
3 msg: array[0..2] of char;
4begin
5 msg[0] := 'H';
6 msg[1] := 'i';
7 msg[2] := '!';
8 writeLn(msg);
9end.
Multidimensional arrays’ elements can be addressed in two ways: either by comma-separated indices…
arrayVariable[firstDimensionIndex, secondDimensionIndex, thirdDimensionIndex]
…or by putting indices in dedicated square brackets.
arrayVariable[firstDimensionIndex][secondDimensionIndex][thirdDimensionIndex]
A third syntactically-valid option would be mixing both styles, however that is considered poor style, unless perhaps there is indication to group indices (e.g. x
, y
and z
coordinates versus other indices) it is okay. Nonetheless, only the first mentioned notation is valid while defining array types.
Note, it is very important to specify indices in the defined order, within each dimensions’ range. Consider the following program; it will compile, but fail during run-time due to {$rangeChecks on}
:
program arrayAddressOrderDemo(input, output, stderr);
{$rangeChecks on}
var
i: integer;
f: array[0..1, 0..3] of boolean;
begin
for i := 0 to 7 do
begin
f[0, i] := true;
end;
end.
While the program would indeed iterate over every array’s elements, it doesn’t do so in the intended way, but rather exploits the fact that the array’s internal memory structure is just a continuous block of memory. This is bad style. A programmer working with a high-level language is not supposed to care about specific memory layouts. Cave: It is possible to tamper with other variables in this way. At any rate, a run-time error, namely “RTE 216 general protection fault,” will occur if an attempt is made to access memory which is not within the purview of the process owner.
When values contained in arrays are merely read (and thus the indices do not matter), a for … in
loop can be used.
Dynamic arrays
A dynamic array is an approach for overcoming the limitation of knowing the sizes of all dimensions in advance. See its dedicated page for more details.
Application
See, for instance:
- Array sort
- 15-puzzle’s and Peg’s game board states are stored as an array.
In the default RTL’s system unit, the function system.slice
returns the initial part of an array, similar to the Ruby notation arrayVariable[0, n]
. Furthermore, there is system.arrayStringToPPchar
. Most statistical routines of the RTL’s math unit accept arrays as parameters, as well as some other routines.
See also
- Type information
- Defensive programming techniques
- Vectorization
- Flexible Array Member
- Tutorial: 1-dimensional arrays
- Tutorial: Multidimensional arrays
- Example: Multidimensional dynamic array
- Article: Why Pascal is not my favorite programming language § “The size of an array is part of its type”
matrix
unit
simple data types |
|
---|---|
complex data types |