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

From: Giovanni Bavestrelli (gibav_at_[hidden])
Date: 2000-12-02 15:46:04

--- In boost_at_[hidden], Kevlin Henney <kevlin_at_c...> wrote:
> In message <9098m5+8qj0_at_e...>, Giovanni Bavestrelli
> <gibav_at_y...> writes
> >> In thinking about the whole dimension and sizing issue, I was 
> >wondering
> >> about the following classification:
> >> 
> >>         size_type is the size_type in a given dimension
> >>         resize resizes the base dimension wrt size_type
> >>         size returns the length of the base dimension
> >> 
> >
> >The base dimension or the total dimension? If by base dimension 
you 
> >mean the first dimension, why should it be treated differently?
> 
> Yes, I mean the first dimension. It would not really be a case of
> treating it differently. Following on from Jeremy's point about 
having
> iterators per dimension, this would certainly fit in: end() - begin
()
> for any dimension would also equal size() for that dimension. I
> mentioned the base dimension as that is your immediate point of 
contact
> with the array and, in terms of resizing, it would also be the only
> dimension to which this would be appropriate.
> 
> >>         shape_type is the type that holds the size for each 
> >dimension
> >>         reshape resizes all of the dimensions
> >>         shape returns the sizes of all the dimensions
> >> 
> >
> >This looks nice, but does not seem necessary if you don't define 
the 
> >concept above.
> 
> And, if the concept above were relevant, it would indeed make sense.
> 
> Just food for thought.
> 
> Kevlin

I think this is part of a very important issue. Should we see an N 
dimensional array as a container of elements, or as a container of N-
1 dimensional arrays? It really is both, but which view simplifies 
what we want to do with it? How do we want to access it? I think I 
ended up privileging the former view, that of a multidimensional 
array as a container of elements, structured in N dimensions, and I 
just used class SubArray as a way to get at the elements. I do not 
treat the various dimensions differently. When I resize the Array, I 
resize it all, I pass all the N dimensions of the Array to the resize 
member function (naturally some of these can remain the same, and in 
any case, I preserve the existing elements where possible and 
desired). I do not see the first dimension as being different, and 
the result is that in my thinking:

1) size() returns the total number of elements in the N dimensional 
(sub)array, not the number of N-1 dimensional subarrays.
2) begin() returns an iterator that allows direct access to the first 
element, not to the first N-1 dimensional array.  
3) I wanted to maintain also a flat view of the underlying elements, 
so that I could apply algorithms and traverse the array sequentially, 
following the order in which the elements are stored in memory. 

The alternative is thinking of the N dimensional array as a vector of 
N-1 dimensional arrays, and that's exactly what you can do with 
std::vector. That way, size() would return the size of the first 
dimension, and begin() would return an iterator over SubArrays. 
That's what you end up with using std::vector, and in my opinion it 
has some problems, which I listed at the beginning of my article. 

Some of these problems, like the number of heap allocations, can be 
reduced using my array and modifying the view of it, seeing it as a 
container of SubArrays. But I would like to know how you would do the 
following two things, with that approach:

1) Find the maximum element in a 10 dimensional array, and do it 
quickly.
2) Iterate through all the elements in a 5 dimensional SubArray of a 
10 dimensional Array.

As I mentioned, this is a fundamental issue. Which view do we 
privilege? In reality, I think we can provide both views, do you 
think that would be reasonable, or would it just complicate the 
interface? I hope we get many comments on this one!

About comments, I read none on efficiency, and I am rather concerned 
with it. My array appears half as fast as a pure C array and a 
std::vector, and the faster version (40% slower than pure C arrays) 
is not thread safe. With increasing number of dimensions, it might 
even be slower. Any ideas on how to speed it up?

Thanks

Giovanni