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

From: Gavin Collings (gcollings_at_[hidden])
Date: 2000-12-04 08:32:43

--- In boost_at_[hidden], Kevlin Henney <kevlin_at_c...> wrote:
> In message <90bn2c+o6d5_at_e...>, Giovanni Bavestrelli
> <gibav_at_y...> writes
> [...]
> >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!

Both views should be provided, and, as you've already hinted at, 
others as well (e.g. a 3-D slice of a 5-D object).  And since we're 
talking about STL, I'm leaning towards privileging the flattened 
view, but read on.

> 
> [...]
> the expectation would be
> 
>         c.begin()[i] is equivalent to c[i]
>         c.begin() + c.size() == c.end()

Agreed, but this doesn't necessarily imply that iterators and size 
etc. should be operating on N-1 dimensional sub arrays. ie. operator
[] could be changed to return elements.  This obviously goes against 
intuition, but I'd like to put forward the case for doing so.

The requirement to iterate over all elements shouldn't be 
underestimated; from my own experience I've been through situations 
where I've made similar choices to the one you are discussing only 
later to reverse them after realising just how often I wanted to 
iterate over all elements.  Therefore, I'm a little hesitant about 
dropping it as the default behaviour.

But what of the problematic operator[]?  At the heart is the STL 
imposition of its view that containers, in particular random access 
containers, should be one dimensional.  And if we're passing a 
container to STL algorithms that, most commonly, we'd like to act on 
elements, shouldn't we conform?

Even if we do this, though, we now have counter-intuitive indexing 
behaviour.  One way around this is to have size() return an 
array_size_type and then overload operator[] -

   operator[]( array_size_type ) returns elements to conform to STL
   operator[]( int )             returns sub arrays.

With luck, array_size_type indexing could map directly to an integer 
offset and bypass the multidimensional sub structure in the data (in 
other words, be fast).

I'm sure that other views of the container can be most elegantly 
represented by adapters (like SubArray/RefArray) passing the 
container around by reference.  Perhaps a general function slice( 
dimensions ) is what's needed?

Thoughts anyone?

Gavin