Accessing an element without initializing the vector. Do I need extra space? [closed]

Question

I am reading about a "trick" (references to Aho,Hopcroft,Ullman) on how to use a data vector without explicitely initializing it.

The trick is to use 2 extra vectors (From To) and an integer Top.

Before accesing an element in the vector DATA[i] if a specific condition between From To and Top is met the element i has been considered as initialized.

If the condition does not meet then the element is initialized and the From To and Top are updated as follows:

Top = Top + 1
From[i] = Top
To[Top] = i
Data[i] = 0

The condition is to know whether an element has been initialized is:
From[i] <= Top && To[From[i]] == i
If true then it has been initialized.

My question is: why are the extra vectors needed?

From my point of view, if I access an element and i<=Top then the element is initialized. Then I increment i i.e. i++.

In this case if i <= TOP means that DATA[i] has been initialized.

Am I not seeing a boundary case? It seems to me this is enough.
Or am I wrong?

Answer 1

If this is the example I am thinking of, then you don't know the order in which the elements of DATA[] will be accessed - it is used as a sparse array, for example the values in an almost empty hash table. So the first 3 items to be accessed might be DATA[113], DATA[29], and DATA[123123], not DATA[0], DATA[1], and DATA[2]. You could in fact get away without From[], in which case To would store {113, 29, 123123} - but then you would have to search all of To every time you wanted to see if an element of DATA was valid, e.g. if you wanted to see if 123123 was valid you would see To[0] = 113 no luck To[1] = 29 no luck To[2] = 123123 Oh yes 123123 is valid.