1 <?xml version=
"1.0" encoding=
"utf-8"?>
2 <!DOCTYPE library PUBLIC
"-//Boost//DTD BoostBook XML V1.0//EN"
3 "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd" [
4 <!ENTITY concepts SYSTEM
"MultiArray.xml">
5 <!ENTITY multi_array SYSTEM
"multi_array.xml">
6 <!ENTITY multi_array_ref SYSTEM
"multi_array_ref.xml">
7 <!ENTITY const_multi_array_ref SYSTEM
"const_multi_array_ref.xml">
9 <library name=
"MultiArray" dirname=
"multi_array" id=
"multi_array"
10 xmlns:
xi=
"http://www.w3.org/2001/XInclude"
11 last-revision=
"$Date$">
14 <firstname>Ronald
</firstname>
15 <surname>Garcia
</surname>
17 <orgname>Indiana University
</orgname>
18 <orgdiv>Open Systems Lab
</orgdiv>
21 <orgname>BOOST
</orgname>
24 <holder>The Trustees of Indiana University
</holder>
26 <librarypurpose>Multidimensional containers and adaptors for
27 arrays of contiguous data
</librarypurpose>
28 <librarycategory name=
"category:math"/>
29 <librarycategory name=
"category:containers"/>
32 <title>Boost.MultiArray Reference Manual
</title>
35 <para>Boost.MultiArray is composed of several components.
36 The MultiArray concept defines a generic interface to multidimensional
38 <literal>multi_array
</literal> is a general purpose container class
39 that models MultiArray.
<literal>multi_array_ref
</literal>
40 and
<literal>const_multi_array_ref
</literal> are adapter
42 you can manipulate any block of contiguous data as though it were a
43 <literal>multi_array
</literal>.
44 <literal>const_multi_array_ref
</literal> differs from
45 <literal>multi_array_ref
</literal> in that its elements cannot
46 be modified through its interface. Finally, several auxiliary classes are used
47 to create and specialize arrays and some global objects are defined as
48 part of the library interface.
</para>
51 <title>Library Synopsis
</title>
52 <para>To use Boost.MultiArray, you must include the header
53 <filename>boost/multi_array.hpp
</filename> in your source. This file
54 brings the following declarations into scope:
</para>
56 <![CDATA[namespace boost {
58 namespace multi_array_types {
59 typedef *unspecified* index;
60 typedef *unspecified* size_type;
61 typedef *unspecified* difference_type;
62 typedef *unspecified* index_range;
63 typedef *unspecified* extent_range;
64 typedef *unspecified* index_gen;
65 typedef *unspecified* extent_gen;
68 template
<typename ValueType,
70 typename Allocator = std::allocator
<ValueType> >
73 template
<typename ValueType,
75 class multi_array_ref;
77 template
<typename ValueType,
79 class const_multi_array_ref;
81 multi_array_types::extent_gen extents;
82 multi_array_types::index_gen indices;
84 template
<typename Array, int N
> class subarray_gen;
85 template
<typename Array, int N
> class const_subarray_gen;
86 template
<typename Array, int N
> class array_view_gen;
87 template
<typename Array, int N
> class const_array_view_gen;
89 class c_storage_order;
90 class fortran_storage_order;
91 template
<std::size_t NumDims
> class general_storage_order;
99 <sect1 id=
"array_types">
100 <title>Array Components
</title>
102 Boost.MultiArray defines an array class,
103 <literal>multi_array
</literal>, and two adapter classes,
104 <literal>multi_array_ref
</literal> and
105 <literal>const_multi_array_ref
</literal>. The three classes model
106 MultiArray and so they share a lot of functionality.
107 <literal>multi_array_ref
</literal> differs from
108 <literal>multi_array
</literal> in that the
109 <literal>multi_array
</literal> manages its own memory, while
110 <literal>multi_array_ref
</literal> is passed a block of memory that it
111 expects to be externally managed.
112 <literal>const_multi_array_ref
</literal> differs from
113 <literal>multi_array_ref
</literal> in that the underlying elements it
114 adapts cannot be modified through its interface, though some array
115 properties, including the array shape and index bases, can be altered.
116 Functionality the classes have in common is described
121 <title>Note: Preconditions, Effects, and Implementation
</title>
123 Throughout the following sections, small pieces of C++ code are
124 used to specify constraints such as preconditions, effects, and
125 postconditions. These do not necessarily describe the underlying
126 implementation of array components; rather, they describe the
127 expected input to and
128 behavior of the specified operations. Failure to meet
129 preconditions results in undefined behavior. Not all effects
130 (i.e. copy constructors, etc.) must be mimicked exactly. The code
131 snippets for effects intend to capture the essence of the described
137 <title>Queries
</title>
141 <term><programlisting>element* data();
142 const element* data() const;
</programlisting></term>
144 <para>This returns a pointer to the beginning of the
145 contiguous block that contains the array's data. If all dimensions of
146 the array are
0-indexed and stored in ascending order, this is
147 equivalent to
<literal>origin()
</literal>. Note that
148 <literal>const_multi_array_ref
</literal> only provides the const
149 version of this function.
155 <term><programlisting>element* origin();
156 const element* origin() const;
</programlisting></term>
158 <para>This returns the origin element of the
159 <literal>multi_array
</literal>. Note that
160 <literal>const_multi_array_ref
</literal> only provides the const
161 version of this function. (Required by MultiArray)
167 <term><function>const index* index_bases();
</function></term>
169 <para>This returns the index bases for the
170 <literal>multi_array
</literal>. (Required by MultiArray)
176 <term><function>const index* strides();
</function></term>
178 <para>This returns the strides for the
179 <literal>multi_array
</literal>. (Required by MultiArray)
185 <term><function>const size_type* shape();
</function></term>
187 <para>This returns the shape of the
188 <literal>multi_array
</literal>. (Required by MultiArray)
197 <title>Comparators
</title>
200 <term><programlisting><![CDATA[
201 bool operator==(const *array-type*& rhs);
202 bool operator!=(const *array-type*& rhs);
203 bool operator<(const *array-type*& rhs);
204 bool operator
>(const *array-type*& rhs);
205 bool operator
>=(const *array-type*& rhs);
206 bool operator<=(const *array-type*& rhs);]]
></programlisting></term>
209 <para>Each comparator executes a lexicographical compare over
210 the value types of the two arrays.
211 (Required by MultiArray)
214 <title>Preconditions
</title>
215 <para><literal>element
</literal> must support the
216 comparator corresponding to that called on
217 <literal>multi_array
</literal>.
</para>
221 <title>Complexity
</title>
222 <para>O(
<literal>num_elements()
</literal>).
</para>
232 <title>Modifiers
</title>
240 template
<typename SizeList
>
241 void reshape(const SizeList& sizes)
247 <para>This changes the shape of the
<literal>multi_array
</literal>. The
248 number of elements and the index bases remain the same, but the number
249 of values at each level of the nested container hierarchy may
252 <formalpara><title><literal>SizeList
</literal> Requirements
</title>
253 <para><literal>SizeList
</literal> must model
254 <ulink url=
"../../utility/Collection.html">Collection
</ulink>.
</para>
257 <formalpara><title>Preconditions
</title>
260 <![CDATA[std::accumulate(sizes.begin(),sizes.end(),size_type(
1),std::times
<size_type>()) == this-
>num_elements();
261 sizes.size() == NumDims;]]
>
262 </programlisting></para>
266 <formalpara><title>Postconditions
</title>
268 <literal>std::equal(sizes.begin(),sizes.end(),this-
>shape) == true;
</literal>
278 template
<typename BaseList
>
279 void reindex(const BaseList& values);
284 <para>This changes the index bases of the
<literal>multi_array
</literal> to
285 correspond to the the values in
<literal>values
</literal>.
</para>
288 <title><literal>BaseList
</literal> Requirements
</title>
289 <para><literal>BaseList
</literal> must model
290 <ulink url=
"../../utility/Collection.html">Collection
</ulink>.
</para>
294 <title>Preconditions
</title>
295 <para><literal>values.size() == NumDims;
</literal></para>
300 <title>Postconditions
</title>
301 <para><literal>std::equal(values.begin(),values.end(),this-
>index_bases());
311 void reindex(index value);
316 <para>This changes the index bases of all dimensions of the
317 <literal>multi_array
</literal> to
<literal>value
</literal>.
</para>
320 <title>Postconditions
</title>
324 std::count_if(this-
>index_bases(),this-
>index_bases()+this-
>num_dimensions(),
325 std::bind_2nd(std::equal_to
<index>(),value)) ==
326 this-
>num_dimensions();
339 &const_multi_array_ref;
344 <sect1 id=
"auxiliary">
345 <title>Auxiliary Components
</title>
347 <sect2 id=
"multi_array_types">
348 <title><literal>multi_array_types
</literal></title>
351 <![CDATA[namespace multi_array_types {
352 typedef *unspecified* index;
353 typedef *unspecified* size_type;
354 typedef *unspecified* difference_type;
355 typedef *unspecified* index_range;
356 typedef *unspecified* extent_range;
357 typedef *unspecified* index_gen;
358 typedef *unspecified* extent_gen;
362 <para>Namespace
<literal>multi_array_types
</literal> defines types
363 associated with
<literal>multi_array
</literal>,
364 <literal>multi_array_ref
</literal>, and
365 <literal>const_multi_array_ref
</literal> that are not
366 dependent upon template parameters. These types find common use with
367 all Boost.Multiarray components. They are defined
368 in a namespace from which they can be accessed conveniently.
369 With the exception of
<literal>extent_gen
</literal> and
370 <literal>extent_range
</literal>, these types fulfill the roles of the
371 same name required by MultiArray and are described in its
372 concept definition.
<literal>extent_gen
</literal> and
373 <literal>extent_range
</literal> are described below.
378 <sect2 id=
"extent_range">
379 <title><classname>extent_range
</classname></title>
381 <para><classname>extent_range
</classname> objects define half open
382 intervals. They provide shape and index base information to
383 <literal>multi_array
</literal>,
<literal>multi_array_ref
</literal>,
384 and
<literal>const_multi_array_ref
</literal> constructors.
385 <classname>extent_range
</classname>s are passed in
386 aggregate to an array constructor (see
387 <classname>extent_gen
</classname> for more details).
391 <title>Synopsis
</title>
392 <programlisting><![CDATA[
395 typedef multi_array_types::index index;
396 typedef multi_array_types::size_type size_type;
399 extent_range(index start, index finish);
400 extent_range(index finish);
407 };]]
></programlisting>
411 <title>Model Of
</title>
412 <para>DefaultConstructible,CopyConstructible
</para>
415 <formalpara><title>Methods and Types
</title>
418 <term><function>extent_range(index start, index finish)
</function></term>
420 <para> This constructor defines the half open interval
421 <literal>[start,finish)
</literal>. The expression
422 <literal>finish
</literal> must be greater than
<literal>start
</literal>.
427 <varlistentry><term><function>extent_range(index finish)
</function></term>
429 <para>This constructor defines the half open interval
430 <literal>[
0,finish)
</literal>. The value of
<literal>finish
</literal>
431 must be positive.
</para>
435 <varlistentry><term><function>index start()
</function></term>
437 <para>This function returns the first index represented by the range
</para>
441 <varlistentry><term><function>index finish()
</function></term>
443 <para>This function returns the upper boundary value of the half-open
444 interval. Note that the range does not include this value.
</para>
449 <term><function>size_type size()
</function></term>
451 <para>This function returns the size of the specified range. It is
452 equivalent to
<literal>finish()-start()
</literal>.
</para>
460 <sect2 id=
"extent_gen">
461 <title><classname>extent_gen
</classname></title>
462 <para>The
<classname>extent_gen
</classname> class defines an
463 interface for aggregating array shape and indexing information to be
464 passed to a
<literal>multi_array
</literal>,
465 <literal>multi_array_ref
</literal>, or
<literal>const_multi_array_ref
</literal>
466 constructor. Its interface mimics
467 the syntax used to declare built-in array types
468 in C++. For example, while a
3-dimensional array of
469 <classname>int
</classname> values in C++ would be
471 <programlisting>int A[
3][
4][
5],
</programlisting>
472 a similar
<classname>multi_array
</classname> would be declared:
473 <programlisting>multi_array
<int,
3> A(extents[
3][
4][
5]).
</programlisting>
476 <formalpara><title>Synopsis
</title>
477 <programlisting><![CDATA[
478 template
<std::size_t NumRanges
>
479 class *implementation_defined* {
481 typedef multi_array_types::index index;
482 typedef multi_array_types::size_type size_type;
484 template
<std::size_t NumRanges
> class gen_type;
486 gen_type
<NumRanges+
1>::type operator[](const range& a_range) const;
487 gen_type
<NumRanges+
1>::type operator[](index idx) const;
490 typedef *implementation_defined*
<0> extent_gen;
494 <formalpara><title>Methods and Types
</title>
497 <term><function>template gen_type
<Ranges
>::type
</function></term>
499 <para>This type generator is used to specify the result of
500 <literal>Ranges
</literal> chained calls to
501 <literal>extent_gen::operator[].
</literal> The types
502 <classname>extent_gen
</classname> and
503 <classname>gen_type
<0>::type
</classname> are the same.
</para>
508 <term><function>gen_type
<NumRanges+
1>::type
509 operator[](const extent_range
& a_range) const;
</function></term>
511 <para>This function returns a new object containing all previous
512 <classname>extent_range
</classname> objects in addition to
513 <literal>a_range.
</literal> <classname>extent_range
</classname>
514 objects are aggregated by chained calls to
515 <function>operator[]
</function>.
</para>
520 <term><function>gen_type
<NumRanges+
1>::type
521 operator[](index idx) const;
</function></term>
523 <para>This function returns a new object containing all previous
524 <classname>extent_range
</classname> objects in addition to
525 <literal>extent_range(
0,idx).
</literal> This function gives the array
526 constructors a similar syntax to traditional C multidimensional array
536 <title>Global Objects
</title>
537 <para>For syntactic convenience, Boost.MultiArray defines two
538 global objects as part of its
539 interface. These objects play the role of object generators;
540 expressions involving them create other objects of interest.
543 <para> Under some circumstances, the two global objects may be
544 considered excessive overhead. Their construction can be prevented by
545 defining the preprocessor symbol
546 <literal>BOOST_MULTI_ARRAY_NO_GENERATORS
</literal> before including
547 <filename>boost/multi_array.hpp.
</filename></para>
550 <title><literal>extents
</literal></title>
553 <![CDATA[namespace boost {
554 multi_array_base::extent_gen extents;
558 <para>Boost.MultiArray's array classes use the
559 <literal>extents
</literal> global object to specify
560 array shape during their construction.
562 a
3 by
3 by
3 <classname>multi_array
</classname> is constructed as follows:
563 <programlisting>multi_array
<int,
3> A(extents[
3][
3][
3]);
</programlisting>
564 The same array could also be created by explicitly declaring an
<literal>extent_gen
</literal>
565 object locally,, but the global object makes this declaration unnecessary.
570 <title><literal>indices
</literal></title>
573 <![CDATA[namespace boost {
574 multi_array_base::index_gen indices;
578 <para>The MultiArray concept specifies an
579 <literal>index_gen
</literal> associated type that is used to
581 <literal>indices
</literal> is a global object that serves the role of
582 <literal>index_gen
</literal> for all array components provided by this
583 library and their associated subarrays and views.
585 <para>For example, using the
<literal>indices
</literal> object,
586 a view of an array
<literal>A
</literal> is constructed as follows:
588 A[indices[index_range(
0,
5)][
2][index_range(
2,
4)]];
594 <sect2 id=
"generators">
595 <title>View and SubArray Generators
</title>
597 Boost.MultiArray provides traits classes,
<literal>subarray_gen
</literal>,
598 <literal>const_subarray_gen
</literal>,
599 <literal>array_view_gen
</literal>,
600 and
<literal>const_array_view_gen
</literal>, for naming of
601 array associated types within function templates.
602 In general this is no more convenient to use than the nested
603 type generators, but the library author found that some C++ compilers do not
604 properly handle templates nested within function template parameter types.
605 These generators constitute a workaround for this deficit.
606 The following code snippet illustrates
607 the correspondence between the
<literal>array_view_gen
</literal>
608 traits class and the
<literal>array_view
</literal> type associated to
612 template
<typename Array
>
614 typedef typename Array::template array_view
<3>::type view1_t;
615 typedef typename boost::array_view_gen
<Array,
3>::type view2_t;
620 In the above example,
<literal>view1_t
</literal> and
621 <literal>view2_t
</literal> have the same type.
626 <sect2 id=
"memory_layout">
627 <title>Memory Layout Specifiers
</title>
629 While a multidimensional array represents a hierarchy of containers of
630 elements, at some point the elements must be laid out in
631 memory. As a result, a single multidimensional array
632 can be represented in memory more than one way.
635 <para>For example, consider the two dimensional array shown below in
638 <graphic fileref=
"matrix.gif"/>
640 Here is how the above array is expressed in C++:
642 int a[
3][
4] = {
0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11 };
644 This is an example of row-major storage, where elements of each row
645 are stored contiguously.
647 While C++ transparently handles accessing elements of an array, you
648 can also manage the array and its indexing manually. One way that
649 this may be expressed in memory is as follows:
651 int a[] = {
0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11 };
655 With the latter declaration of
<literal>a
</literal> and
656 strides
<literal>s
</literal>, element
<literal>a(i,j)
</literal>
658 accessed using the expression
659 <programlisting>*a+i*s[
0]+j*s[
1]
</programlisting>.
662 <para>The same two dimensional array could be laid out by column as follows:
665 int a[] = {
0,
4,
8,
1,
5,
9,
2,
6,
10,
3,
7,
11 };
668 Notice that the strides here are different. As a result,
669 The expression given above to access values will work with this pair
670 of data and strides as well.
673 <para>In addition to dimension order, it is also possible to
674 store any dimension in descending order. For example, returning to the
675 first example, the first dimension of the example array, the
676 rows, could be stored in
677 reverse, resulting in the following:
680 int data[] = {
8,
9,
10,
11,
4,
5,
6,
7,
0,
1,
2,
3 };
685 Note that in this example
<literal>a
</literal> must be explicitly set
686 to the origin. In the previous examples, the
687 first element stored in memory was the origin; here this is no longer
692 Alternatively, the second dimension, or the columns, could be reversed
693 and the rows stored in ascending order:
696 int data[] = {
3,
2,
1,
0,
7,
6,
5,
4,
11,
10,
9,
8 };
703 Finally, both dimensions could be stored in descending order:
706 int data[] = {
11,
10,
9,
8,
7,
6,
5,
4,
3,
2,
1,
0};
708 int s[] = { -
4, -
1 };
715 All of the above arrays are equivalent. The expression
716 given above for
<literal>a(i,j)
</literal> will yield the same value
717 regardless of the memory layout.
719 Boost.MultiArray arrays can be created with customized storage
720 parameters as described above. Thus, existing data can be adapted
721 (with
<literal>multi_array_ref
</literal> or
722 <literal>const_multi_array_ref
</literal>) as suited to the array
723 abstraction. A common usage of this feature would be to wrap arrays
724 that must interoperate with Fortran routines so they can be
725 manipulated naturally at both the C++ and Fortran levels. The
726 following sections describe the Boost.MultiArray components used to
727 specify memory layout.
730 <sect3 id=
"c_storage_order">
731 <title><literal>c_storage_order
</literal></title>
733 <![CDATA[class c_storage_order {
738 <para><literal>c_storage_order
</literal> is used to specify that an
739 array should store its elements using the same layout as that used by
740 primitive C++ multidimensional arrays, that is, from last dimension
741 to first. This is the default storage order for the arrays provided by
745 <sect3 id=
"fortran_storage_order">
746 <title><literal>fortran_storage_order
</literal></title>
748 <![CDATA[class fortran_storage_order {
749 fortran_storage_order();
753 <para><literal>fortran_storage_order
</literal> is used to specify that
754 an array should store its elements using the same memory layout as a
755 Fortran multidimensional array would, that is, from first dimension to
759 <sect3 id=
"general_storage_order">
760 <title><literal>general_storage_order
</literal></title>
762 <![CDATA[template
<std::size_t NumDims
>
763 class general_storage_order {
765 template
<typename OrderingIter, typename AscendingIter
>
766 general_storage_order(OrderingIter ordering, AscendingIter ascending);
770 <para><literal>general_storage_order
</literal> allows the user to
771 specify an arbitrary memory layout for the contents of an array. The
772 constructed object is passed to the array constructor in order to
773 specify storage order.
</para>
776 <literal>OrderingIter
</literal> and
<literal>AscendingIter
</literal>
777 must model the
<literal>InputIterator
</literal> concept. Both
778 iterators must refer to a range of
<literal>NumDims
</literal>
779 elements.
<literal>AscendingIter
</literal> points to objects
780 convertible to
<literal>bool
</literal>. A value of
781 <literal>true
</literal> means that a dimension is stored in ascending
782 order while
<literal>false
</literal> means that a dimension is stored
783 in descending order.
<literal>OrderingIter
</literal> specifies the
784 order in which dimensions are stored.
790 <sect2 id=
"range_checking">
791 <title>Range Checking
</title>
793 By default, the array access methods
<literal>operator()
</literal> and
794 <literal>operator[]
</literal> perform range
795 checking. If a supplied index is out of the range defined for an
796 array, an assertion will abort the program. To disable range
797 checking (for performance reasons in production releases), define
798 the
<literal>BOOST_DISABLE_ASSERTS
</literal> preprocessor macro prior to
799 including multi_array.hpp in an application.