Boost logo

Boost :

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
> >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
> 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
> 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
> >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
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?



Boost list run by bdawes at, gregod at, cpdaniel at, john at