III. Subscript Bindings
and Array Categories
In some languages, the lower bound of the subscript
range is implicit. For example, in the C-based languages, the lower
bound of all subscript ranges is fixed at 0 ; in Fortran 95+ it
defaults to 1 but can be set to any integer literal.
In some other languages, the lower bounds of the
subscript ranges must be specified by the programmer.
There are five
categories of arrays, based on the binding to subscript ranges, the
binding to storage, and from where the storage is allocated :
i. Static Array
A static array is one in which the subscript
ranges are statically bound and storage allocation is static (done before run
time).
e.g. Arrays declared in C
and C++ functions that include the static modifier are static.
The advantage of static arrays is efficiency: No
dynamic allocation or deallocation is required.
The disadvantage is that the storage for the array is
fixed for the entire execution time of the program.
ii. fixed stack-dynamic array
A fixed stack-dynamic array is one in which the
subscript ranges are statically bound, but the allocation is done at
declaration elaboration time during execution.
e.g.
Arrays that are declared in C and C++ functions
(without the static specifier) are examples of fixed stack-dynamic arrays.
The advantage
of fixed stack-dynamic arrays over static arrays is space efficiency.
The disadvantage is the required allocation and
deallocation time.
iii. stack-dynamic array
A stack-dynamic array is one in which both the
subscript ranges and the storage allocation are dynamically bound at
elaboration time.
e.g.
Ada arrays can be stack dynamic, as in the following:
Get(List_Len);
declare
List : array (1..List_Len) of
Integer;
begin
. . .
end;
The advantage of stack-dynamic arrays over
static and fixed
stack-dynamic arrays is flexibility. The size of an array need not be known
until the array is about to be used.
iv. fixed heap-dynamic array
A fixed heap-dynamic array is similar to a fixed
stack-dynamic array, in that the subscript ranges and the storage binding are
both fixed after storage is allocated.
e.g.
C and C++ also provide fixed heap-dynamic
arrays.
The standard C library functions malloc
and free , which are general heap allocation and deallocation
operations, respectively, can be used for C arrays.
C++ uses the operators new and delete
to manage heap storage.
In Java, all non-generic arrays are fixed
heap-dynamic. C# also provides the same kind of arrays.
The advantage of fixed heap-dynamic arrays is
flexibility i.e. the array’s size always fits the problem.
The disadvantage is allocation time from the heap,
which is longer than allocation time from the stack.
v. heap-dynamic array
A heap-dynamic array is one in which the binding
of subscript ranges and storage allocation is dynamic and can change any number
of times during the array’s lifetime.
e.g.
C# also provides generic heap-dynamic arrays, which are
objects of the List class. These array objects are created without any
elements, as in
List<String> stringList
= new List<String>();
Elements are added to this object with the Add method,
as in
stringList.Add("Michael");
Java includes a generic class similar to C#’s
List , named ArrayList . It is different from C#’s List in that
subscripting is not supported get and set methods must be used to access
the elements.
The advantage of
heap-dynamic arrays over the others is flexibility: Arrays can grow and shrink
during program execution as the need for space changes.
The disadvantage is that allocation and deallocation
take longer and may happen many times during execution of the program.
No comments:
Post a Comment