Lecture
A vector (one-dimensional array) is a data structure with a fixed number of elements of one and the same type. Each element of a vector has a number that is unique within the given vector. Access to an element of a vector is performed by the name of the vector and the number of the required element.
The elements of a vector are placed in memory in consecutively located memory cells. For an element of a vector, a number of bytes of memory is allocated, determined by the base type of the element of this vector. The required number of bytes of memory to store one element of a vector is called a slot. The amount of memory to store a vector is determined by the product of the slot length and the number of elements.
In programming languages a vector is represented by a one-dimensional array with a description syntax of the form (PASCAL):
< Name > : array [n..k] of < type >;
where n is the number of the first element, k is the number of the last element. The representation of the vector in memory will be as shown in fig. 1.
Fig. . Representation of a vector in memory
where @ Name is the address of the vector or, what is the same, the address of the first element of the vector,
Sizeof(type) is the size of a slot (the number of bytes of memory for writing one element of a vector), (k-n)*Sizeof(type) is the relative address of the element with number k, or, what is the same, the offset of the element with number k.
For example:
var m1:array[-2..2] of real;
the representation of this vector in memory will be as in fig. 2.
Fig. 2. Representation of the vector m1 in memory
In languages where memory is allocated before the program runs, at compile time (C, PASCAL, FORTRAN), when describing a vector type the boundary values of the indices must be defined. In languages where memory can be allocated dynamically (ALGOL, PL/1), the values of the indices can be specified during program execution.
The number of bytes of contiguous memory area occupied by a vector at once is determined by the formula:
ByteSise = ( k - n + 1 ) * Sizeof (type)
Access to the i-th element of a vector is performed by the address of the vector plus the offset to the given element. The offset of the i-th element of a vector is determined by the formula:
ByteNumer = ( i- n ) * Sizeof (type),
and its address: @ ByteNumber = @ name + ByteNumber.
where @ name is the address of the first element of the vector.
For example:
var MAS: array [ 5..10 ] of word.
The base type of a vector element - Word requires 2 bytes, so two bytes are allocated for each element of the vector. Then table 1 of the offsets of the vector elements relative to @Mas looks like this:
| Offset (bytes) | + 0 | + 2 | + 4 | + 6 | + 8 | + 10 |
| Field identifier | MAS | MAS | MAS | MAS | MAS | MAS[10] |
Table 1
This vector will occupy in memory: (10-5+1)*2 = 12 bytes.
The offset to the vector element with number 8: (8-5)*2 = 6
The address of the element with number 8: @ MAS + 6.
When accessing a vector, the name of the vector and the number of the vector element are specified. Thus, the address of the i-th element can be computed as:
@Name[i] = @Name + i*Sizeof(type) - n*Sizeof(type) (3.1)
This computation cannot be performed at compile time, since the value of the variable i is not yet known at that time. Consequently, the computation of the element's address must be performed at program execution time on each access to the vector element. But for this, at execution time, firstly, the parameters of formula (3.1) must be known: @Name, Sizeof(type), n, and secondly, on each access two multiplication operations and two addition operations must be performed. Having transformed formula (3.1) into formula (3.2),
@Name[i] = A0 + i*Sizeof(type) -- (3.2)
A0 = @Name - n*Sizeof(type) --
let's reduce the number of stored parameters to two, and the number of operations to one multiplication and one addition, since the value of A0 can be computed at compile time and stored together with Sizeof(type) in the vector's descriptor. Usually the boundary values of the indices are also stored in the vector's descriptor. On each access to a vector element, the given value is compared with the boundaries and the program terminates abnormally if the given index goes outside the allowed limits.
Thus, the information contained in the vector's descriptor makes it possible, firstly, to reduce access time, and secondly, provides a check on the correctness of the access. But for these advantages one has to pay, firstly, in speed, since accesses to the descriptor are instructions, and secondly, in memory both for placing the descriptor itself and the instructions working with it.
Is it possible to do without a vector descriptor?
In the C language, for example, there is no vector descriptor, or more precisely, it is not stored at execution time. Indexing of arrays in C necessarily starts from zero. The compiler replaces every access to an array element with a sequence of instructions implementing the particular case of formula (3.1) for n = 0:
@Name[i] = @Name + i*Sizeof(type)
Programmers used to working in C often, instead of an expression of the form: Name[i], use an expression of the form: *(Name+i).
But firstly, the restriction on the choice of the starting index may itself be an inconvenience for the programmer, and secondly, the absence of boundary values of the indices makes it impossible to check for going beyond the limits of the array. Programmers working with C know well that it is precisely such errors that are often the cause of a C program "hanging" during its debugging.
Comments