# How can I have constant time initialization for multi-dimensional arrays?

For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in constant time because there are pointers to access and keep track of the elements in the array.

How can I extend the idea of using the Which, Data, and When pointers to have constant time initialization for multi-dimensional arrays? Would I have to have multiple Which, Data, and When pointers to keep track of n-th D array dimensions?

Or is the use of hierarchical tables, which stores multi-dimensional arrays as an array of pointers to tables, where each table contains a row of the array, and implementing the Which, Data, and When pointers to the hierarchical tables a correct way for having constant time initialization of multi-dimensional arrays?

Edit: Use C notation for simplicity. Let's say for a large N we have an array:

SomeType array[N];


If N is very large, and only a few of the array's elements are ever used, just initializing it can become the largest cost of an algorithm. A way around this is to have a self-checking structure that can be filled in on demand. To the above add (I'm not the original poster, so I will use my own names here):

int last_used = -1, place[N], order[N];


The idea is that last_used tells the last used entry, place[i] is the index of the i-th asigned element of array, and order[k] is the order in which the array[k] was initialized. Note that none of array, place and order are initialized, their initial values are arbitrary. place[i] and order[k] serve to check each other. To use array[i], see if order[i] < last_used (it is in the right range, might have been set already; if not, it is clearly garbage) and also place[order[i]] == i. If so, the element has been used, go ahead. If not, do:

last_used++;          /* Another one is in use */
place[last_used] = i; /* The next one in use is array[i] */
order[i] = last_used; /* Point back */
initialize(array[i]); /* Prepare for use */
/* Furiously frob array[i] */


The time of this is bounded by a constant; so the initialization time, amortized over the initialized elements, is constant. For a practical implementation, this can be packaged conveniently in a C++ class (templated on SomeType and N) overloading operator[].

Remark: This can clearly be extended to an array of such arrays.

• Which, Data, and When pointers -- I'm not sure exactly what you are referring to. Please edit the question to make it self-contained, and don't assume we know what you mean by those terms. – D.W. Mar 6 '14 at 1:17
• Now that this has been edited to make the data structure clear, it seems to me that it's essentially a programming question. – David Richerby Mar 11 '14 at 12:36

I think you can use the same pattern, but simply need index conversion routines to go from multi-dimensional indices back to linear indices. For example, if you want a 2-D array, of dimensions A and B, create a linear array withN = A*B. Then array, place, and order would all have size N. When you access the 2-D array with indices a and b, instead compute n = a*B + b and lookup the linear array at n. This generalizes to as many dimensions as you wish.