Monday November 20.
A common data structure is an extensible array (XArray for short). An
extensible array grows monotonically in size, and allows efficient retrieval.
Once an element of the array is assigned to, its value does not change, but
its final size is not known at priori. The two operations that we need to
define on XArray are insertion (always at the end) and retrieval (indexing).
In addition we want to define equality and assignment.
an efficient implementation of an XArray is as a structure that contains a
pointer to the current contents (a real array) and some indices that keep
track of the current maximum size and the current next available entry.
When an insertion is made on a full XArray, we double the size of the
real array, recopy the elements, and have plenty of growth room. The doubling
factor means that the Xarray will reach its final size in a logarithmic
number of copying steps.
1. Define a XArray template, parametrized by the initial size and the class
of the element. Implement the operations of indexing, insertion, current
length (number of entries made), equality and assignment.
2. Test your template by instatiating it with ints, doubles, and Xarrays of
3. Define an iterator over an XArray, and assuming that << is declared for
the element class, write a function that prints all elements stored at
odd positions in the XArray.
4. Suppose you use an iterator in some function that also performs insertions
on the XArray over which you are iterating. Does the iterator still work if
the container undergoes a doubling in size?