|
Home | Libraries | People | FAQ | More |
The MultiArray concept defines an interface to hierarchically nested containers. It specifies operations for accessing elements, traversing containers, and creating views of array data. MultiArray defines a flexible memory model that accomodates a variety of data layouts.
At each level (or dimension) of a MultiArray's container hierarchy lie a set of ordered containers, each of which contains the same number and type of values. The depth of this container hierarchy is the MultiArray's dimensionality. MultiArray is recursively defined; the containers at each level of the container hierarchy model MultiArray as well. While each dimension of a MultiArray has its own size, the list of sizes for all dimensions defines the shape of the entire MultiArray. At the base of this hierarchy lie 1-dimensional MultiArrays. Their values are the contained objects of interest and not part of the container hierarchy. These are the MultiArray's elements.
Like other container concepts, MultiArray exports iterators to traverse its values. In addition, values can be addressed directly using the familiar bracket notation.
MultiArray also specifies
routines for creating
specialized views. A view lets you treat a
subset of the underlying
elements in a MultiArray as though it were a separate
MultiArray. Since a view refers to the same underlying elements,
changes made to a view's elements will be reflected in the original
MultiArray. For
example, given a 3-dimensional "cube" of elements, a 2-dimensional
slice can be viewed as if it were an independent
MultiArray.
Views are created using index_gen and
index_range objects.
index_ranges denote elements from a certain
dimension that are to be included in a
view. index_gen aggregates range data and performs
bookkeeping to determine the view type to be returned.
MultiArray's operator[]
must be passed the result
of N chained calls to
index_gen::operator[], i.e.
indices[a0][a1]...[aN];
where N is the
MultiArray's dimensionality and
indices an object of type index_gen.
The view type is dependent upon the number of degenerate dimensions
specified to index_gen. A degenerate dimension
occurs when a single-index is specified to
index_gen for a certain dimension. For example, if
indices is an object of type
index_gen, then the following example:
indices[index_range(0,5)][2][index_range(0,4)];
has a degenerate second dimension. The view generated from the above
specification will have 2 dimensions with shape 5 x 4.
If the "2" above were replaced with
another index_range object, for example:
indices[index_range(0,5)][index_range(0,2)][index_range(0,4)];
then the view would have 3 dimensions.
MultiArray exports
information regarding the memory
layout of its contained elements. Its memory model for elements is
completely defined by 4 properties: the origin, shape, index bases,
and strides. The origin is the address in memory of the element
accessed as a[0][0]...[0], where
a is a MultiArray. The shape is a list of numbers
specifying the size of containers at each dimension. For example, the
first extent is the size of the outermost container, the second extent
is the size of its subcontainers, and so on. The index bases are a
list of signed values specifying the index of the first value in a
container. All containers at the same dimension share the same index
base. Note that since positive index bases are
possible, the origin need not exist in order to determine the location
in memory of the MultiArray's elements.
The strides determine how index values are mapped to memory offsets.
They accomodate a
number of possible element layouts. For example, the elements of a 2
dimensional array can be stored by row (i.e., the elements of each row
are stored contiguously) or by column (i.e., the elements of each
column are stored contiguously).
Two concept checking classes for the MultiArray concepts
(ConstMultiArrayConcept and
MutableMultiArrayConcept) are in the namespace
boost::multi_array_concepts in
<boost/multi_array/concept_checks.hpp>.
What follows are the descriptions of symbols that will be used to describe the MultiArray interface.
Table 25.1. Notation
A |
A type that is a model of MultiArray |
a,b |
Objects of type A
|
NumDims |
The numeric dimension parameter associated with
A. |
Dims |
Some numeric dimension parameter such that
0<Dims<NumDims.
|
indices |
An object created by some number of chained calls
to index_gen::operator[](index_range). |
index_list |
An object whose type models Collection |
idx |
A signed integral value. |
tmp |
An object of type
boost::array<index,NumDims>
|
Table 25.2. Associated Types
| Type | Description |
|---|---|
value_type |
This is the value type of the container.
If NumDims == 1, then this is
element. Otherwise, this is the value type of the
immediately nested containers.
|
reference
|
This is the reference type of the contained value.
If NumDims == 1, then this is
element&. Otherwise, this is the same type as
template subarray<NumDims-1>::type.
|
const_reference
|
This is the const reference type of the contained value.
If NumDims == 1, then this is
const element&. Otherwise, this is the same
type as
template const_subarray<NumDims-1>::type.
|
size_type
|
This is an unsigned integral type. It is primarily used to specify array shape. |
difference_type
|
This is a signed integral type used to represent the distance between two
iterators. It is the same type as
std::iterator_traits<iterator>::difference_type.
|
iterator |
This is an iterator over the values of A.
If NumDims == 1, then it models
Random Access Iterator.
Otherwise it models
Random Access Traversal Iterator,
Readable Iterator,
Writable Iterator, and
Output Iterator.
|
const_iterator
|
This is the const iterator over the values of A.
|
reverse_iterator
|
This is the reversed iterator, used to iterate backwards over the values of
A.
|
const_reverse_iterator
|
This is the reversed const iterator.
A.
|
element
|
This is the type of objects stored at the base of the
hierarchy of MultiArrays. It is the same as
template subarray<1>::value_type
|
index
|
This is a signed integral type used for indexing into A. It
is also used to represent strides and index bases.
|
index_gen
|
This type is used to create a tuple of index_ranges
passed to operator[] to create
an array_view<Dims>::type object.
|
index_range
|
This type specifies a range of indices over some dimension of a
MultiArray. This range will be visible through an
array_view<Dims>::type object.
|
template subarray<Dims>::type
|
This is subarray type with Dims dimensions.
It is the reference type of the (NumDims - Dims)
dimension of A and also models
MultiArray.
|
template const_subarray<Dims>::type
|
This is the const subarray type. |
template array_view<Dims>::type
|
This is the view type with Dims dimensions. It is
returned by calling operator[](.
It models MultiArray.
|
template
const_array_view<Dims>::type
|
This is the const view type with Dims dimensions.
|
Table 25.3. Valid Expressions
| Expression | Return type | Semantics |
|---|---|---|
A::dimensionality |
size_type |
This compile-time constant represents the number of
dimensions of the array (note that
A::dimensionality == NumDims). |
a.shape() |
const size_type* |
This returns a list of NumDims elements specifying the
extent of each array dimension.
|
a.strides() |
const index* |
This returns a list of NumDims elements specifying the
stride associated with each array dimension. When accessing values,
strides is used to calculate an element's location in memory.
|
a.index_bases() |
const index* |
This returns a list of NumDims elements specifying the
numeric index of the first element for each array dimension.
|
a.origin() |
element* if a is mutable,
const element* otherwise.
|
This returns the address of the element accessed by the expression
a[0][0]...[0].. If the index bases are positive,
this element won't exist, but the address can still be used to locate
a valid element given its indices.
|
a.num_dimensions() |
size_type |
This returns the number of dimensions of the array
(note that a.num_dimensions() == NumDims). |
a.num_elements() |
size_type |
This returns the number of elements contained
in the array. It is equivalent to the following code:
std::accumulate(a.shape(),a.shape+a.num_dimensions(),
size_type(1),std::multiplies<size_type>());
|
a.size() |
size_type |
This returns the number of values contained in
a. It is equivalent to a.shape()[0];
|
a(index_list) |
element&; if a is mutable,
const element& otherwise.
|
This expression accesses a specific element of
a.index_list is the unique set
of indices that address the element returned. It is
equivalent to the following code (disregarding intermediate temporaries):
// multiply indices by strides
std::transform(index_list.begin(), index_list.end(),
a.strides(), tmp.begin(), std::multiplies<index>()),
// add the sum of the products to the origin
*std::accumulate(tmp.begin(), tmp.end(), a.origin());
|
a.begin() |
iterator if a is mutable,
const_iterator otherwise.
|
This returns an iterator pointing to the beginning of
a. |
a.end() |
iterator if a is mutable,
const_iterator otherwise.
|
This returns an iterator pointing to the end of
a. |
a.rbegin() |
reverse_iterator if a is mutable,
const_reverse_iterator otherwise.
|
This returns a reverse iterator pointing to the
beginning of a reversed.
|
a.rend() |
reverse_iterator if a is mutable,
const_reverse_iterator otherwise.
|
This returns a reverse iterator pointing to the end of a
reversed.
|
a[idx] |
reference if a is mutable,
const_reference otherwise.
|
This returns a reference type that is bound to the index
idx value of a. Note that if
i is the index base for this dimension, the above
expression returns the (idx-i)th element (counting
from zero). The expression is equivalent to
*(a.begin()+idx-a.index_bases()[0]);.
|
a[indices] |
array_view<Dims>::type if
a is mutable,
const_array_view<Dims>::type otherwise.
|
This expression generates a view of the array determined by the
index_range and index values
used to construct indices.
|
a == b |
bool | This performs a lexicographical comparison of the
values of a and b. The element
type must model EqualityComparable for this
expression to be valid. |
a < b |
bool | This performs a lexicographical comparison of the
values of a and b. The element
type must model LessThanComparable for this
expression to be valid. |
a <= b |
bool | This performs a lexicographical comparison of the
values of a and b. The element
type must model EqualityComparable and
LessThanComparable for this
expression to be valid. |
a > b |
bool | This performs a lexicographical comparison of the
values of a and b. The element
type must model EqualityComparable and
LessThanComparable for this
expression to be valid. |
a >= b |
bool | This performs a lexicographical comparison of the
values of a and b. The element
type must model LessThanComparable for this
expression to be valid. |
begin() and end() execute in amortized
constant time.
size() executes in at most linear time in the
MultiArray's size.
Table 25.4. Invariants
| Valid range |
[a.begin(),a.end()) is a valid range.
|
| Range size |
a.size() == std::distance(a.begin(),a.end());.
|
| Completeness |
Iteration through the range
[a.begin(),a.end()) will traverse across every
value_type of a.
|
| Accessor Equivalence |
Calling a[a1][a2]...[aN] where N==NumDims
yields the same result as calling
a(index_list), where index_list
is a Collection containing the values a1...aN.
|
The following MultiArray associated types define the interface for creating views of existing MultiArrays. Their interfaces and roles in the concept are described below.
index_range objects represent half-open
strided intervals. They are aggregated (using an
index_gen object) and passed to
a MultiArray's operator[]
to create an array view. When creating a view,
each index_range denotes a range of
valid indices along one dimension of a MultiArray.
Elements that are accessed through the set of ranges specified will be
included in the constructed view. In some cases, an
index_range is created without specifying start
or finish values. In those cases, the object is interpreted to
start at the beginning of a MultiArray dimension
and end at its end.
index_range objects can be constructed and modified
several ways in order to allow convenient and clear expression of a
range of indices. To specify ranges, index_range
supports a set of constructors, mutating member functions, and a novel
specification involving inequality operators. Using inequality
operators, a half open range [5,10) can be specified as follows:
5 <= index_range() < 10;
or
4 < index_range() <= 9;
and so on.
The following describes the
index_range interface.
Table 25.6. Associated Types
| Type | Description |
|---|---|
index |
This is a signed integral type. It is used to specify the start, finish, and stride values. |
size_type |
This is an unsigned integral type. It is used to
report the size of the range an index_range
represents. |
Table 25.7. Valid Expressions
| Expression | Return type | Semantics |
|---|---|---|
index_range(idx1,idx2,idx3) |
index_range |
This constructs an index_range
representing the interval [idx1,idx2)
with stride idx3. |
index_range(idx1,idx2) |
index_range |
This constructs an index_range
representing the interval [idx1,idx2)
with unit stride. It is equivalent to
index_range(idx1,idx2,1). |
index_range() |
index_range |
This construct an index_range
with unspecified start and finish values. |
i.start(idx1) |
index& |
This sets the start index of i to
idx. |
i.finish(idx) |
index& |
This sets the finish index of i to
idx. |
i.stride(idx) |
index& |
This sets the stride length of i to
idx. |
i.start() |
index |
This returns the start index of i. |
i.finish() |
index |
This returns the finish index of i. |
i.stride() |
index |
This returns the stride length of i. |
i.get_start(idx) |
index |
If i specifies a start
value, this is equivalent to i.start(). Otherwise it
returns idx. |
i.get_finish(idx) |
index |
If i specifies a finish
value, this is equivalent to i.finish(). Otherwise it
returns idx. |
i.size(idx) |
size_type |
If i specifies a both finish and
start values, this is equivalent to
(i.finish()-i.start())/i.stride(). Otherwise it
returns idx. |
i < idx |
index |
This is another syntax for specifying the finish
value. This notation does not include
idx in the range of valid indices. It is equivalent to
index_range(r.start(), idx, r.stride())
|
i <= idx |
index |
This is another syntax for specifying the finish
value. This notation includes
idx in the range of valid indices. It is equivalent to
index_range(r.start(), idx + 1, r.stride())
|
idx < i |
index |
This is another syntax for specifying the start
value. This notation does not include
idx in the range of valid indices. It is equivalent to
index_range(idx + 1, i.finish(), i.stride()). |
idx <= i |
index |
This is another syntax for specifying the start
value. This notation includes
idx1 in the range of valid indices. It is equivalent to
index_range(idx, i.finish(), i.stride()). |
i + idx |
index |
This expression shifts the start and finish values
of i up by idx. It is equivalent to
index_range(r.start()+idx1, r.finish()+idx, r.stride())
|
i - idx |
index |
This expression shifts the start and finish values
of i up by idx. It is equivalent to
index_range(r.start()-idx1, r.finish()-idx, r.stride())
|
index_gen aggregates
index_range objects in order to specify view
parameters. Chained calls to operator[] store
range and dimension information used to
instantiate a new view into a MultiArray.
Table 25.8. Notation
Dims,Ranges |
Unsigned integral values. |
x |
An object of type
template gen_type<Dims,Ranges>::type. |
i |
An object of type
index_range. |
idx |
Objects of type index. |
Table 25.9. Associated Types
| Type | Description |
|---|---|
index |
This is a signed integral type. It is used to specify degenerate dimensions. |
size_type |
This is an unsigned integral type. It is used to
report the size of the range an index_range
represents. |
template gen_type::<Dims,Ranges>::type
|
This type generator names the result of
Dims chained calls to
index_gen::operator[]. The
Ranges parameter is determined by the number of
degenerate ranges specified (i.e. calls to
operator[](index)). Note that
index_gen and
gen_type<0,0>::type are the same type. |
Table 25.10. Valid Expressions
| Expression | Return type | Semantics |
|---|---|---|
index_gen() |
gen_type<0,0>::type |
This constructs an index_gen
object. This object can then be used to generate tuples of
index_range values. |
x[i] |
gen_type<Dims+1,Ranges+1>::type
|
Returns a new object containing all previous
index_range objects in addition to
i. Chained calls to
operator[] are the means by which
index_range objects are aggregated. |
x[idx] |
gen_type<Dims,Ranges+1>::type
|
Returns a new object containing all previous
index_range objects in addition to a degenerate
range, index_range(idx,idx). Note that this is NOT
equivalent to x[index_range(idx,idx)]., which will
return an object of type
gen_type<Dims+1,Ranges+1>::type.
|