Array: Difference between revisions

Line 1:

[[Category:Encyclopedia]]An '''array''' is a composite data type, in the [[Collections|collection]] category, that stores multiple values all of the same declared type. The stored values are called '''elements''' and are accessed by a tuple of indices. By using a variable indices, the array may be accessed for a not predetermined set of indices, during the run of the program. All indices of an array are [http://en.wikipedia.org/wiki/Total_order totally ordered].

An array of which some of the indices have infinite (or else very large) [http://en.wikipedia.org/wiki/Upper_and_lower_bounds bounded subsets] is known as an [[associative array]]. For example, arrays indexed by [http://en.wikipedia.org/wiki/Lexicographical_order lexicographically ordered] strings are associative.

An array in which some of the indices have infinite (or else very large) [http://en.wikipedia.org/wiki/Upper_and_lower_bounds bounded subsets] is known as an [[associative array]]. For example, arrays indexed by [http://en.wikipedia.org/wiki/Lexicographical_order lexicographically ordered] strings are associative.

Arrays with more than one index are called '''multidimensional''' arrays. For example, matrix is a two-dimensional array.

Arrays with more than one index are called '''multidimensional''' arrays. For example, a matrix is a two-dimensional array.

Basic operations defined on arrays are:

* Indexing, accessing an array element by its tuple of indices;

* Indexing: accessing an array element by its tuple of indices

* Slicing, producing a subarray by putting some constraint on the indices. For example, [[PL/1]] provides extracting of a row or a column of an array. In [[Ada]] any range of the index can be used in order to extract a subarray from a single-dimensional array;

* Slicing: producing a subarray by putting some constraint on the indices. For example, [[PL/1]] provides extracting of a row or a column of an array. In [[Ada]] any range of the index can be used in order to extract a subarray from a single-dimensional array

* Iteration of the ~~arrays~~ elements. Some languages have [[Loop/Foreach]] construct for array iteration;

* Iteration of the array's elements. Some languages have a [[Loop/Foreach|foreach loop]] construct for array iteration

* Querying the bounds of array indices;

* Querying the bounds of array indices

* Operations on indices (next, previous, range etc);

* Operations on indices (next, previous, range etc)

* Array programming languages provide ~~operation~~ applied to entire arrays, so programs in such languages often lack specific index reference.

* Array programming languages provide operations applied to entire arrays, so programs in such languages often lack specific index reference

Values of arrays are called '''array aggregates'''.

Multidimensional arrays ~~with~~ ~~some~~ of ~~indices~~ ~~varying~~ are called '''ragged'''. This term comes from a typical example of a ragged array, when a two-dimensional array is used to store strings of different length in its rows. When put on paper the right margin of the output become ''ragged''.

Multidimensional arrays in which the valid range of one index depends on the value of another are called '''ragged''' (also '''jagged'''). This term comes from a typical example of a ragged array, when a two-dimensional array is used to store strings of different length in its rows. When put on paper the right margin of the output become ''ragged''.

⚫

Each array index is bounded at run time. Further when

⚫

Each array index is bounded at run time. Further, when

# array is not associative

# each index is within the bounds (including the bounds)

then it is legal to access the array at the tuple of these indices.

The lower bound is in many [[:Category:Programming Languages|programming languages]] fixed to either 0 ([[C]] and relatives) or 1 (Old [[Fortran]] and relatives), or arbitrary ([[Pascal]] and relatives, modern Fortran). In [[Ada]] any discrete type can used as an index.

The lower bound in many [[:Category:Programming Languages|programming languages]] is fixed to either 0 ([[C]] and relatives) or 1 (Old [[Fortran]] and relatives), or arbitrary ([[Pascal]] and relatives, modern Fortran). In [[Ada]] any discrete type can used as an index.

For an empty array the lower bound of an index is greater than the upper bound. This causes the famous problem of declaring an empty array when the index type is a singleton (has only one value).

When bounds of all array indices are fixed, the array is said to be '''constrained'''. When some bounds are unknown until run time, the array is '''unconstrained'''. Non-associative unconstrained arrays are usually passed to the subprograms with a "dope" attached to the array body. The dope contains the actual bounds of unconstrained array indices. Associative arrays carry some indexing structure with them, like a [[hash table]] etc.

When bounds of all array indices are fixed, the array is said to be '''constrained'''. When some bounds are unknown until run time, the array is '''unconstrained'''. Non-associative, unconstrained arrays are usually passed to the subprograms with a "dope" attached to the array body. The dope contains the actual bounds of unconstrained array indices. Associative arrays carry some indexing structure with them, like a [[hash table]] etc.

The minimal size of a non-associative array is determined by the current bounds of its indices. In all regular programming languages, the size of such array can be set by the programmer at [[compile time]] or after. In many modern programming languages the size of the array may be computed and allocated at run time.