Re: A class template for an N-dimensional generic resizable array

From: Kris Thielemans (kris.thielemans_at_[hidden])
Date: 2000-12-04 09:41:55

Hi,

I've just joined this mailing list, and see lots of discussion on
N-dimensional arrays.

I went through this myself 1 year ago, and have implemented (freely
available) N-dimensional arrays as well. I didn't look yet at Giovanni's
code, but from reading about it I think that the main differences with my
implementation are:

- multi-dimensional arrays needn't be 'regular' or 'rectangular'. For
instance, a each index in a 2D array can give you a 1D array with different
sizes
- I allow indices with non-zero offset
- there is some extra code like operator+ etc and (binary) IO (but that's
pretty trivial to add).

The 1st property was required by our application, and does complicate
optimisation of various operations.

Internally my Array<N,T> is just a pointer to (a C-array) of Array<N-1,t>.
This simplifies a lot of the implementation (no need for RefArray), but has
some drawbacks:

- memory allocation is slow, as it consists of a lot of calls to new
- it leads to arrays which are dispersed over memory, which is presumably
important for present processors with memory caching
- it makes it non-trivial (but doable) to iterate over all elements as if
this was a 1D sequence of T's.

(I think that it should be possible to get round these difficulties by
having the memory allocated as 1 big chunk by the 'highest dimensional'
object, and let the N-x dimensional arrays just be a collection of pointers
in this chunk.)

To solve the issue of 2 types of iterators I have different members:

// iterators for a 1D view on the nD array, so 'pointing' to a T
inline full_iterator begin_all();
inline full_iterator end_all();

// iterators which 'point' to a N-1-dim Array.
inline iterator begin();
inline iterator end();

I'm not 100% happy with my implementation, as
- I don't have something like 'slices' (but this will be difficult for
non-regular arrays)
- it should all have been derived from valarray (but that wasn't around yet
when I started this project).

If anyone is interested you could check the online doc at
http://www.brunel.ac.uk/~masrppet/ (there's a whole lot more there), or drop
me a line.

Kris Thielemans
(kris.thielemans_at_[hidden])
MRC Cyclotron Unit,
Hammersmith Hospital,
DuCane Rd,London W12 0NN, United Kingdom

Phone on :   [phone]
FAX on :     [phone]

NEW web site address:
http://www.cu.mrc.ac.uk/~kris