Array

An array is a composite data type -- it can store multiple values, and so is in the collection category. The stored values are called elements of the array, and are accessed by a sequence of indices. In a program, indices may be a mixture of constant values or variables that allow the elements accessed to vary under program control. The indices of an array are totally ordered.

The implementation details of an array give rise to an important distinction between arrays and associative arrays.

The implementation of arrays is based on setting the bounds of indices of the array, the size of the array, normally by allocating a contiguous region of memory to hold the elements of the array, and using simple offset calculations on the indices from the origin of the memory to access memory elements. Some languages support extensions to allow such arrays to be resized, or re-shaped, in which the memory area is adjusted, but extent elements are retained.

By contrast, an associative array maps the association between index "keys" and their associated values, generally using more complex hash functions on the keys of the array to map them to their corresponding elements (by pointers, references or memory addresses of some sort). Associative arrays are referred to variously as "hashes" (Perl), "maps" or "mappings" (Lua), or "dictionaries" (Python), as well as "associative arrays" (AWK, ksh, and others). The keys into associative arrays are normally not constrained to be integers, unlike arrays, which generally required contiguous integer ranges. Different languages may impose various constraints on these keys. For example, in Perl, keys must always be strings, so 1, "1", and 1.0, each of which stringifies to "1", are the same key, but "1.0" is distinct from all of these. In PHP, keys must be strings or integers; floats and booleans get implicitly converted to an integer. Other languages (such as Python) may treat each type of object as distinct. (See associative array for further discussion.)

Non-associative arrays may have speed and memory consumption advantages. Associative arrays have greater flexibility in types used for keys, and generally obviate the need to implement searches through the collection. (Each component on which one would search can be implemented as a different associative array of references to their corresponding values or records.)

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

Some languages (such as AWK) do not support true arrays; they merely emulate them through their associative arrays. Similarly, some languages emulate multi-dimensional arrays by concatenation of dimensional indices into keys (perhaps a peculiarity of AWK).

Common operations defined on arrays include:

• Indexing: accessing an array element by its indices. (There is a one to one mapping between an index and its corresponding element). While the cost of indexing is O(1) on typical current machines, the cost of indexing an element adjacent to a recently accessed element is much faster than indexing an arbitrary random element of a large 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. In Python slices can extract any contiguous subset of an array and extended slice notation can extract elements in reversed order and/or by traversing in a given "stride" --- for example a[100:0:-2] would return every odd element from 100 to the beginning of the list: a[99], a[97], ... a[1].
• Iteration over the array's elements. Some languages make this a universal or implicit operation, some languages have a foreach loop construct for array iteration, in others this must be done with conventional looping and arithmetic.
• Iteration over the indices of an associative or sparse array.
• Querying the bounds of array indices (determining the maximum element index of offset)
• Querying the indices of an associative array (determining if the collection contains a value for any given key).
• Operations on indices (next, previous, range etc)
• Sorting the contents of the array to satisfy some relationship.
• Searching an array for the location(s) of some value(s)

Array programming languages provide operations applied to entire arrays, so programs in such languages often do not bother using index references (for example APL).

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.

The lower bound of non-associative arrays in many programming languages is commonly fixed at either 0 (C and relatives) or 1 (Old Fortran and relatives); or an arbitrary integer (Pascal and relatives, modern Fortran). In Ada any discrete type can used as an index. Zero-based indexing is best thought of in terms of the index being an offset from the beginning of the array. Thus the first element is located zero elements from this starting point. The alternative can be thought of as ordinal indexes referring to the first, second, ... and nth elements of the array.

In most programming languages, arrays are accessed by using the array brackets [ and ], e.g. in A[i]. However, exceptions exist, including REXX which instead uses the dot operator ., such as in A.i; Fortran, Ada and BASIC which use round parentheses A(i), and in lisp dialects which use constructions like (ELT A n) for accessing and (SETA A n new_val) for setting (Interlisp) or (vector-ref A n) for accessing and (vector-set! A n new_val) for setting (Scheme). No bracket indexing occurs in J, an array language; instead, the normal syntax of function creation and function calling applies.

See also

• Array
• Associative array: Creation, Iteration
• Collections
• Compound data type
• Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
• Linked list
• Queue: Definition, Usage
• Set
• Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
• Stack

Computational metrics

Access is O(1), appending is O(1), and insertion is O(n) for a single item.

Examples

• letter frequency

Pascal

This defines an array suitable to hold a 64x64 truecolor image (i.e. red, green and blue RGB values all can go from 0 to 255) and then sets the color of a single pixel <lang pascal> type

 color = red, green, blue;
 rgbvalue = 0 .. 255;

var

 picture: array[0 .. 63, 0 .. 63, color] of rgbvalue

begin

 { set pixel (4,7) to yellow }
 picture[4, 7, red]   := 255;
 picture[4, 7, green] := 255;
 picture[4, 7, blue]  := 0

end. </lang>

jq

jq's data types are the same as JSON's data types, and thus jq's arrays can hold any combination of JSON entities. jq arrays are indexed beginning with 0, so ["hello"][0] evaluates to "hello".

Immutability

jq offers a comprehensive collection of operators and functions for array processing, but to understand them it must be appreciated that all data values in jq are immutable. In particular, if a is an array, a jq expression such as "a[0] = 1" may give the appearance of updating the array, but it simply returns an array identical to a except for the first element.

In fact, an expression such as "a[m] = 1" (where m is some non-negative integer) does not require that the length of the array, a, be at least (m+1). The expression should instead be interpreted to mean: produce an array derived from a such that a[m] == 1. If necessary, jq will add "null" elements to achieve this requirement. Thus, one way to create an array of m+1 nulls is to write:<lang jq>[][m] = null</lang> It might seem that jq must be horrendously inefficient because of immutability, but in fact, jq is fast because of compiler optimizations.

Basic Array Operations

Assuming a and b are arrays, and if m and n are non-negative integers: <lang jq> [][n] = null # => an array with (1+n) nulls [range(0;n)] # => [0,1, ... (n-1)] a | length # => the length of a a + b # => the concatenation of a followed by b a[n] # => the element at offset n (or null) a[-1] # => the last element (or null) a[m:n] # => the subarray [a[m], ..., a[n-1]] </lang>

Streams and Arrays

jq provides support for streams of JSON entities, and thus the syntax for converting between an array and the stream of entities that an array contains is fundamental to jq. In brief: <lang jq>

1. If a is an array, then the expression

a[]

1. will produce the stream of a's entities.

1. Conversely, if S is a stream of entities,
2. then they can be gathered together using the syntax:

[ S ] </lang> For example, if S is the stream (1,2,3), then [(1,2,3)] == [1,2,3].

This highlights an important point about "," in jq: the comma is not merely a syntactic marker but an operator.

map/reduce

jq's "map" filter is quite conventional, e.g. <lang jq>[1,2,3] | map(-(.)) # => [-1, -2, -3]</lang>The reduce filter, however, has a special syntax that makes it very powerful. In brief, the syntax is:<lang jq>reduce S as $var (init; update) </lang>where S is an expression producing a stream of values, and init and update are jq expressions. The reduction takes place by setting a hidden variable to the value of "init" initially, and then performing the update on the hidden variable as specified by "update" for each value, $var, in the stream. The result of the reduction is the final value of the hidden variable.

For example, here is a toy example followed by an efficient computation of n! (factorial n):<lang jq>reduce [1,2,3][] as $i (0; . + $i) # => 6

reduce range(2;n+1) as $i (1; . * $i) # => n!</lang>

REXX

<lang rexx>/*REXX program snippets to show a variety (types) of "array" indexing. */

/*REXX arrays aren't true arrays, but can be used (and thought) as such.*/ /*REXX never needs to allocate an array (indeed, there is no mechanism */ /* in the language to do so.) */

 do j=0 to 100                        /*this "array" starts at zero.   */
 quad.j=j**2                          /*assign J's square-->QUAD array.*/
 end

say 'middle number=' quad.50 /*display a use an array element.*/

 do k=-99 to +99                      /*this "array" starts at minus 99*/
 box.k=k**3                           /*assign K's  cube --> BOX array.*/
 end

                                      /*an example of a sparse array:  */
 do m=0 to 10000 by 10                /*"array" only has odd elements. */
 wierd.m=m**3 - m**2                  /*assign something--> WIERD array*/
 end

/*How to assign a value (such as 0) to all indexes of an array. */ g.=1-1 /*trying to be fancy, but failing*/

   do n=-1e6 to 1e6 by 100
   g.n=sign(n)                        /*assigns -1 to negative elements*/
   end                                /*         1 to positive elements*/
                                      /*         0 to the 0th  element.*/

googol=10**100 say g.googol /*will show a value of 0 (zero). */

/*Indexes (or keys) need not be numeric (as in all the examples above). */

quad.kk = 'Diplomacy is the art of saying "nice doggy" until you can',

         'find a rock.'               /*a character 2-liner assignment.*/

qwot=quad.kk; say qwot /*show a quote, make user scratch head. */

                               /*since   kk   hasn't been defined yet, */
                               /*then the index is  KK  (uppercase, but*/
                               /*it doesn't matter if  KK, kk,  kK,  Kk*/
                               /*is used in the program to refer to it)*/

veryStrange='box cañon or [canyon]¿' /*note special characters.*/

                               /*illustrates a very quarky index (key).*/
                               /*this type of index must be the same   */
                               /*case as the "original"  (lowercase).  */

quad.veryStrange=box.10 /*quad's "strange" index <--one-thousand*/

/*For all intents and purposes, stemmed arrays look like arrays in other*/ /* languages, except that a dot/period (.) is used. */ /* I.E.: x.2 instead of (say, the usual): x(2) */ /*Although, if you wanted to use that format, you could. To illustrate:*/

x.1=1; x.2='two'; x.3="3.0 ± 1"; do i=1 to 3; say x.i; end

 /*another way of using arrays.*/     say x(2)
                                      exit

                                      /*further on down in the program.*/
                                           .
                                           .
                                           .
                                      x: procedure expose x.; parse arg i
                                         return x.i

/*Note that REXX knows that x(2) is a function, and x.2 is a variable*/

/*Since all arrays are sparse (or can be), there doesn't need to be a */ /*declaritive on the indexes limits (bounds). Also, there is no limit */ /*on the number of dimensions of an array. I.E.: */

ht=14411; z='feet'; mt.rainier.12.9.4.6.44.z.12.7.1.0.6.2.2.2.1 = ht</lang>