From: Ralf W. Grosse-Kunstleve (rwgk_at_[hidden])
Date: 2002-01-18 13:45:01
FWIW: a few theoretical remarks (born out of very pragmatic needs):
I came to the conclusion that multi_array will not
immediately work for us (see my other messages). Therefore
I thought some more about multi dimensional arrays. IMHO
Toon's questions only show that a more general design is
needed. There are three major concepts that I can
distinguish, and which I believe should be presented and
parameterized as such:
- Memory management
- Access schemes
Ultimately any array is a one-dimensional array. Here I
see six important memory management policies that are
useful in different contexts:
- automatic allocation, fixed size() (aka boost::array)
- automatic allocation (fixed capacity), variable size()
- dynamic allocation, fixed size()
deep copy semantics
- dynamic allocation, variable size() (e.g. std::vector)
deep copy semantics
The automatically allocated (i.e. stack) arrays will tend
to be small, therefore deepcopy semantics is always
For the dynamically allocated arrays, both deepcopy and
handle-based (referenced counting) copy semantics are
useful, depending on the application. However, an array
that is reference counted can easily provide a deep copy,
but not vice versa. Therefore in practice four memory
management varieties should be sufficient.
A comprehensive package should give access to each of
An access scheme is a transformation from a general index
object to a 1-dimensional array index. A simple index
object is a tuple of integers. A simple access scheme is
that of a conventional n-dimensional grid of points (as
represented by multi_array). In real-world applications
there are many other useful types of access schemes,
mostly related to some type of symmetry (e.g. Hermitian
symmetry of complex-valued arrays).
A comprehensive package should parameterize the access
scheme (as a template argument) and provide the most
common schemes as part of the package.
Toon would provide a class implementing his custom
access scheme, and then instantiate, e.g.
A slice is just a special access scheme, or a generalized
simple access scheme.
In the context of multi-dimensional arrays, iterators are
a somewhat artificial concept. An iterator that does not
keep track of the index object corresponding to the position
in the underlying 1-dimensional array (e.g. the mapping from
the 1-dimensional index to the corresponding three-tuple)
is either fast but of limited use, or general but slow.
A general multi-dimensional iterator must have some sort
of nested loop inside. Therefore an iterator and a nested
loop become almost indistinguishable. However, I find it
much more natural to think of a nested loop rather than
an iterator. One could even argue that the STL iterators
are the trivial form of a nested loop, and the nested
loop is the proper abstraction for higher dimensions.
A partial implementation of these ideas can be found in the
cvs tree at cctbx.sf.net (e.g. shared_storage.h, ndim.h,
loops.h; maps/ndim.h implements a specialized accessor;
naming is still a bit disorganized). We are currently
refining the design. I would be happy to share more details
if there is an interest.
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk