Assignment V

Due date 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 ints.
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?