Go to the previous, next section.

Extensible Arrays

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 previous, next section.