Go to the first, previous, next, last section, table of contents.
Arrays are very efficient data structures but they can only be used when their size is known in advance. For situations where the number of elements is not even known at run-time, most programmers resort to using linked lists. SUIF provides a compromise. Extensible arrays provide almost the same efficiency as arrays without requiring a bound on the number of elements. They are not as flexible as linked lists, however, because it is still not possible to insert new elements in the middle of an extensible array.
Extensible arrays are implemented by the x_array class in the
files `xarray.h' and `xarray.cc'. When an x_array is
first created, you must specify the number of elements to be allocated
in the first chunk of memory. If more elements are needed later,
additional chunks of the same size will be allocated automatically. The
ub method returns the number of elements that are currently in an
x_array.
The elements of an x_array cannot be referenced until they are
added to the array. New elements can only be added at the end of an
array by using the extend method. In this way an x_array
behaves like a linked list. Elements must be appended (with
extend) to the end of an array before they can be used.
The x_array class also provides an operator[] method so
that once an element has been entered in an x_array it can be
referenced using the standard array reference syntax. This works
regardless of which chunk of memory contains the element.
Each element of an x_array is a void* pointer. You can
cast these pointers to any other type that fits in the same amount of
storage. A better solution is to use the DECLARE_X_ARRAY macro
to derive a subclass of x_array with elements that are pointers
to the correct type. This macro takes three arguments: the name of the
derived class, the type to which the elements should point, and the
default chunk size. As with the macros for creating new list classes,
this is just a cheap substitute for templates.
Go to the first, previous, next, last section, table of contents.