分类： C/C++
2008-05-28 16:27:58
看到上面这些声明，是不是有些面熟？STL！对，这些成员函数的声明是与STL中container concept完全一致的。也就是说，这里提供了与STL容器一致的访问界面，所谓与STL的兼容性正是在这里体现出来了。而const_multi_array_ref更是“类如其名”，const_multi_array_ref中所有访问元素、查询数组信息等成员函数都返回const的reference或iterator。而反观multi_array_ref的声明，其中只比const_multi_array_ref多了访问元素、查询数组信息的对应的non-const版本成员函数。
那么const_multi_array_ref的基类multi_array_impl_base的职责又是什么呢?multi_array_impl_base是属于实现细节的，它的作用只是根据数组信息（const_multi_array_ref中的成员变量）计算偏移量、步长等，也就是把多维的下标最终转化为一维偏移量。而multi_array_impl_base的基类——value_accessor_n或者value_accessor_one——的功能则是提供一个对原始数据的访问。这种访问方式是大家所熟悉的把多维索引转化为一维偏移量的方式——凡是写过用一维数组模拟多维数组的人都应该清楚。至于为什么要有value_accessor_n和value_accessor_one两个版本，后文会详细阐释。
至此，multi_array的大致架构就已经浮现出来了：
multi_array -> multi_array_ref -> const_multi_array_ref -> multi_array_impl_base -> value_accessor_n/value_accessor_one
其中每一层都担任各自的角色：
¨ multi_array : 为数组元素分配空间，将各种操作转发至基类。
¨ multi_array_ref : 提供与STL容器一致的数据访问界面。也可以独立出来作为一个adapter使用。
¨ const_multi_array_ref : 提供const的STL数据访问界面。也可以作为一个const adapter使用。
¨ multi_array_impl_base及其基类 :最底层实现，提供一组对原始数据的基本操作。
这种架构看似复杂，却提供了很高的复用性，其中的(const_)multi_array_ref类都可以独立出来作为一个adapter使用——例如：
int a[24]; //一维的10个元素数组，位于栈上！
//把一维数组a“看成”一个3*4*2的三维数组：
multi_array_ref
arr_ref[i][j][k] = value; //和multi_array一样的使用界面
很简单吧！从此你就不用辛辛苦苦的去模拟多维数组了。即使是位于栈上的一维数组，也可以把它“看成”是一个多维数组。倘若你不想让multi_array来自动分配内存的话，你可以自行分配数组（可以位于栈上或堆上）然后用multi_array_ref把它包装成一个多维的数组。
multi_array的存储策略
接下来，就来看看multi_array的存储策略，例如：C风格的多维数组存储方式是按行存储，而fortran恰恰相反，是按列存储，甚至，用户可能有自己的存储策略要求。那么，如何支持多种风格的存储策略呢？秘密就在于代码（3-3）处，const_multi_array_ref的成员storage_——其类型为storage_order_type，下面的声明指出了storage_order_type的“本来面目”——general_storage_order
// multi_array_ref.hpp
... ...
typedef general_storage_order
... ...
// storage_order.hpp
template
class general_storage_order {
general_storage_order(const c_storage_order&){ //（4-1）
for (size_type i=0; i != NumDims; ++i)
{ ordering_[i] = NumDims - 1 - i; }
ascending_.assign(true); //缺省为升序排列
}
... ...
boost::array
boost::array<bool,NumDims> ascending_;//升序排列还是降序排列
};
在（4-1）处的构造函数中，ordering_和ascending_是两个数组，缺省情况下，当函数（4-1）执行完毕后，ordering_中的元素应当是{NumDims-1, NumDims-2,...1,0}，也就是说，NumDims-1维在先，然后是NumDims-2维，...，如果将这些元素作为各维度存储顺序的标识——具有较小ordering_值的维度优先——那么就这和C语言中的存储方式就完全一致了，而ascending_勿庸置疑就是用来表明各维度是否升序存储。其实general_storage_order还有一个模板构造函数，它是为了支持更为一般化的存储策略（例如fortran的按列存储或用户自定义的存储策略）。这里不作详述。
除了存储策略，const_multi_array_ref的构造还通过调用init_from_extent_gen函数，将extents中的内容取出来进行处理，并以此设定其它若干表述多维数组的变量（（3-3）处其它一些变量），具体细节不再赘述。
现在关于一个多维数组的所有信息都已经准备齐备，可谓“万事具备，只欠‘空间’”。multi_array下面要做的就是调用前面提到的allocate_space来为数组中的元素分配空间了。
// multi_array.hpp
void allocate_space() {
... ...
base_ = allocator_.allocate(this->num_elements(),no_hint);
... ... std::uninitialized_fill_n(base_,allocated_elements_,T());
}
原来，在底层，存储仍然是退化为一维数组的存储： allocate_space使用allocator_分配一块连续的空间用以存储元素，其中num_elements()返回的就是数组各维度的大小的乘积，即数组的总元素个数。分配完之后，就将首指针赋给表述数组基地址的成员base_，然后std::uninitialized_fill_n负责把该数组进行缺省初始化。至此multi_array的构造工作终于大功告成了。
一致性界面——GP的灵魂
multi_array的另一重要特性就是支持与内建多维数组相同的访问方式，也就是说，multi_array支持以连续的“[]”来访问数组元素。就以文章开头给出的示例代码（1-3）处的赋值语句为例，让我们看看multi_array是如何支持这种与内建数组兼容的访问方式的。
// multi_array_ref.hpp
// 使用operator[]来访问元素,返回类型reference是什么呢？不是T&!
reference operator[](index idx) {
return super_type::access(boost::type
idx,origin(),this->shape(),this->strides(),
this->index_bases());
}
这个调用转入了value_accessor_n::access(...)之中：
// base.hpp
// in class value_accessor_n
template <typename Reference, typename TPtr>
Reference access(boost::type
index idx,TPtr base,const size_type* extents,
const index* strides,const index* index_base)
{
TPtr newbase = base + idx * strides[0];
return Reference(newbase,extents+1,
strides+1,index_base+1);
}
这个连续调用operator[]的过程和extend_gen是很类似的——每调用一层就返回一个“proxy(替身)”，这个替身并非实际元素，因为这时候后面还跟有“[]”，所以对这个替身也应该能调用operator[]，从而使这个过程能够连续下去直到后面没有“[]”为止”。
举个例子，如果以A[x1][x2][x3]方式访问A中的元素，就相当于
A.operator[x1].operator[x2].operator[x3] //连续调用“[]”
这三次operator[]调用返回的类型依次为：
sub_array
注意sub_array的第二个模板参数（维度）递减的过程，当递减到0时，表明已经递归到了最后一个维度，真正的访问开始了，所以最后一次调用“[]”返回的恰好是对元素的引用（这就刚好印证了前面所说的——当且仅当“[]”的个数和数组的维数相同的时候，才能够取出元素，否则你得到的返回值要么还是sub_array<...>（而不是元素），要么会由于试图在T&上继续调用“[]”而编译失败）那么，这一切究竟是如何做到的呢？
从上面的递归过程，我们可以轻易看出：真正对元素进行访问并返回T&的任务交给了sub_array
sub_array的秘密
sub_array的定义在sub_array.hpp中：
// sub_array.hpp
template <typename T, std::size_t NumDims>
class sub_array : public const_sub_array
template <typename T, std::size_t NumDims, typename TPtr>
class const_sub_array :
public multi_array_impl_base
//base.hpp
template
class multi_array_impl_base:public
value_accessor_generator
唔，原来sub_array最终继承自multi_array_impl_base，后者的基类型由value_accessor_generator来生成——它会根据NumDims的不同而生成不同的基类型：
// base.hpp
template <typename T, typename NumDims>
struct value_accessor_generator {
... ...
typedef typename //如果NumDims为1，则类型为value_accessor_one
mpl::apply_if_c<(dimensionality == 1),
choose_value_accessor_one<T>,
choose_value_accessor_n<T,dimensionality>
>::type type; //把这个类型作为multi_array_impl_base的基类！
};
很显然，如果dimensionality == 1，那么“::type”就是value_accessor_one<T>，而只有对value_accessor_one使用“[]”才能返回T&，否则，“::type”被推导为value_accessor_n，这只是个“proxy”而已，对它运用“[]”只会返回sub_array
取出元素
根据上面的分析，取元素的任务最终交给value_accessor_one，其成员函数access如下：
template <typename Reference, typename TPtr>
Reference access(boost::type
const size_type*,const index* strides,
const index*) const {
return *(base + idx * strides[0]); //终于取出了数据！
}
这里，access的返回类型Reference就是T&，即数组中元素类型的引用，从而可以将指定元素的引用返回，达到访问数组元素的目的。看到这里，multi_array以内建数组访问方式访问数组元素的过程基本已经弄清楚了，至于其中一些细节，尤其是计算地址的细节，譬如：偏移量的计算、步长的使用等，皆已略去了。
现在也许你会有这样的疑惑：以内建多维数组的“[][][]...”访问方式来访问multi_array的元素的能力真的如此重要吗？费这么大力气、写这么多代码还不如以多参数的方式重载operator[]呢（“[i,j,...]”形式）！这么大代价真的值得吗？值得！这是勿庸置疑的。以内建数组访问方式访问multi_array元素的能力最重要的表现就是：可以把multi_array作为一个内建多维数组来对待，与内建类型的一致性是你的类能够和泛型算法合作的关键。举个例子：用户编写了一个函数模板，
template <typename ReturnType, typename _3DArray>
ReturnType someAlgo(_3Array& mda){//可以作用于内建多维数组
... ...
mda[x][y][z] = mda[z][x][y]; //对内建多维数组的访问形式！
... ...
}
因为有了以内建数组访问方式访问multi_array元素的能力，这个someAlgo算法就可以同时应用在内建数组和multi_array上（否则用户就得为multi_array提供一个单独的重载版本），如此一来，代码的可重用性、可扩展性都大大提高了。
效率
效率是C++永恒的主题，MultiArray库也不例外。执行时间效率上，纵观MultiArray库对数组元素的访问代码，虽然函数调用嵌套层数甚多，但多数调用都是简单的转发或者编译期的递归，在一个成熟的现代C++编译器下，这些转发的函数调用代码应该可以很轻易地被优化掉，所以在效率上几乎没有什么损失。在空间方面，由于大量运用模板技术，基本能够在编译期决定的内容都已决定，没有为运行期带来不必要的空间上的负担。总的看来，Boost.MultiArray库的确是难得的高效又通用的多维数组的实现。
结语
本文只是将multi_array最基本的功能代码做了一个扼要的分析，正如文章开始所说，multi_array还有许多很有用的特性，如果读者想充分了解multi_array的运作机制与实现技巧，就请深入完整地分析multi_array的代码吧，相信一定会大有收获的！
