Boost源码笔记：boost::multi_array

动机

         C++是一门自由的语言，允许你自由的表达自己的意图，对不对? 所以我们既然可以new一个一维数组，也应该可以new出多维数组，对不对?先来看一个例子：

        int* pOneDimArr = new int[10]; //新建一个10个元素的一维数组

        pOneDimArr[0] = 0; //访问

        int** pTwoDimArr = new int[10][20]; //错误！

        pTwoDimArr[0][0] = 0; //访问

    但是，很可惜，三四两行代码的行为并非如你所想象的那样——虽然从语法上它们看起来是那么“自然”。

    这里的问题在于，new int[10][20]返回的并非int**类型的指针，而是int (*)[20]类型的指针（这种指针被称为行指针，对它“+1”相当于在数值上加上一行的大小（本例为20），也就是说，让它指向下一行），所以我们的代码应该像这样：

int (*pTwoDimArr)[20] = new int[i][20]; //正确

pTwoDimArr[1][2] = 0; //访问

    注意pTwoDimArr的类型——int(*)[20]是个很特殊的类型，它不能转化为int**，虽然两者索引元素的语法形式一样，都是“p[i][j]”的形式，但是访问内存的次数却不一样，语义也不一样。

    最关键的问题还是：以上面这种朴素的方式来创建多维数组，有一个最大的限制，就是：除了第一维，其它维的大小都必须是编译期确定的。例如：

       int (*pNdimArr)[N2][N3][N4] = new int[n1][N2][N3][N4];

    这里N2,N3,N4必须都是编译期常量，只有n1可以是变量，这个限制与多维数组的索引方式有关——无论多少维的数组都是线性存储在内存中的，所以：

        pTwoDimArr[i][j] = 0;

被编译器生成的代码类似于：

        *( (int*)pTwoDimArr+i*20+j ) = 0;

    20就是二维数组的行宽，问题在于，如果允许二维数组的行宽也是动态的，这里编译器就无法生成代码（20所在的地方应该放什么呢？）。基于这个原因，C++只允许多维数组的第一维是动态的。

    不幸的是，正由于这个限制，C++中的多维数组就在大多数情况下变成了有名无实的无用之物。我们经常可以在论坛上看到关于多维数组的问题，一般这类问题的核心都在于：如何模仿一个“完全动态的”多维数组。这里“完全动态”的意思是，所有维的大小都可以是动态的变量，而不仅是第一维。论坛上给出的答案不一而足，有的已经相当不错，但是要么缺乏可扩展性（即扩展到N维的情况），要么在访问元素的形式上远远脱离了内建的多维数组的访问形式，要么消耗了过多额外的空间。归根到底，我们需要的是一个类似这样的多维数组实现：

 

//创建一个int型的DIMS维数组，dim_sizes用于指定各维的大小，即n1*n2*n3

multi_arrayDIMS> ma ( dim_sizes[n1][n2][n3] );

ma[i][j][k] = value; //为第i页j行k列的元素赋值

ma[i][j] = value; //编译错！

ma[i] = value; //编译错！

ma[i][j][k][l] = value;//编译错！

 

这样一个multi_array，能够自动管理内存，拥有和内建多维数组一致的界面，并且各维的大小都可以是变量——正符合我们的要求。看起来，实现这个multi_array并非难事，但事实总是出乎意料，下面就是对boost中已有的一个multi_array实现的剖析——你几乎肯定会发现一些出乎意料的（甚至是令人惊奇的）地方。

 

Boost中的多维数组实现——boost::multi_array

在Boost库中就有一个用于描述多维数组的功能强大的MultiArray库。它实现了一个通用、与标准库的容器一致的接口，并且具有与C++中内建的多维数组一样的界面和行为。正是基于这种通用性的设计，MultiArray库与标准库组件甚至用户自定义的泛型组件之间可以具有很好的兼容性，并能够很好的协同工作。

除此之外，MultiArray还提供了诸如改变大小、重塑（reshaping）以及对多维数组的视图访问等极为有用的特性，从而使MultiArray比其它描述多维数组的方式（譬如：std::vector< std::vector<...> > ）更为便捷、高效。

下面我们就逐层深入，去揭开boost::multi_array的神秘面纱——对示例程序进行调试、跟踪是分析库源代码最有效的手段之一。我们就从MultiArray文档中的示例程序入手：

 

// 略去头文件包含

int main () {

    // 创建一个尺寸为3×4×2的三维数组

    #define DIMS 3 //数组是几维的

    typedef boost::multi_array<double,DIMS> array_type; // (1-1)

    array_type A(boost::extents[3][4][2]); // (1-2)

    // 为数组中元素赋值

    A[1][2][0] = 120;     // (1-3)

    ... ...

    return 0;

}

 

在上述代码中，boost::multi_array的两个模板参数分别代表数组元素的类型和数组的维度。（1-2）处是三维数组对象的构造语句。boost::extents[3][4][2]则用于指明该数组各维的大小，这里的含义是：定义一个3*4*2的三维数组。你肯定对boost::extents心存疑惑——为什么对它可以连用“[]”？如果用多了一个或用少了一个“[]”又会如何？下面我就为你层层剥开boost::extents的所有奥秘——

 

extents——与内建数组一致的方式

boost::extents是一个全局对象，在base.hpp中：

 

    typedef detail::multi_array::extent_gen<0> extent_gen;

    ... ...

    multi_array_types::extent_gen extents; //注意它的类型！

 

可见extents的类型为extent_gen，后者位于extent_gen.hpp中：

 

// extent_gen.hpp

template NumRanges>

class extent_gen {

    range_list ranges_;    // （2-1）

... ...

extent_gen(const extent_gen1>& rhs, const range& a_range)

{ // （2-2）

 ... //

}

extent_gen<NumRanges+1> operator[](index idx) //(2-3)

{ return extent_gen1>(*this,range(0,idx)); }

    //返回一个extent_gen，不过第二个模板参数增加了1

};

 

boost::extent_gen重载了operator[]操作符，但是，既然这里只有一个“[]”，为什么我们可以写“extents[n1][n2][n3][...]呢？继续看——

如果把boost::extents[n1][n2][n3]展开为操作符调用的方式就相当于：

boost::extents.operator[](n1).operator[](n2).operator[](n3);

boost::extents对象的类型是extent_gen<0> ——其NumRanges模板参数为0。extents.operator[](n1)调用（2-3），返回一个extent_gen1>，也就是extent_gen<1>，由于这个类型也是extent_gen，所以仍然可以对它调用operator[](n2)，返回extent_gen<2>，然后再对该返回值调用operator[](n3)，最终返回一个extent_gen<3>类型的对象。

这里，每一重operator[]调用都转到（2-3），在那里将参数idx以range包装一下再转发给构造函数（2-2），注意此时调用的是extent_gen类型的构造函数。至于range(0,idx)则表示一个[0,idx)的下标区间。

总结一下extents的基本工作方式——每对它调用一次operator[]，都会返回一个extent_gen类型的对象，所以，对于boost::extents[n1][n2][n3]，依次返回的类型是：

extent_gen<1> => extent_gen<2> => extent_gen<3>

最后一个也是最终的返回类型——extent_gen<3>。其模板参数3表示这是用于三维数组的下标指定。其成员ranges_中，共有[0，n1）、[0，n2）、[0，n3）三组区间。这三组区间指定了我们定义的multi_array对象的三个维度的下标区间，值得注意的是这些区间都是前闭后开的（这和STL的迭代器表示的区间一样）。当boost::extents准备完毕后，就被传入multi_array的构造函数，用于指定各维的下标区间：

 

// multi_array.hpp

explicit multi_array(const extent_gen& ranges):

super_type((T*)initial_base_,ranges){

    allocate_space();    // （2-5）

}

 

这里，multi_array接受了ranges参数中的信息，取出其中各维的下标区间，然后保存，最后调用allocate_space()来分配底层内存。

 

使用extent_gen的好处——do things right!

使用boost::extents作参数的构造过程和内建多维数组的方式一致，简练直观，语义清晰。首先，boost::extents使用“[]”，能让人很容易想到内建多维数组的声明，也很清晰地表达了每个方括号中数值的含义——表明各维度的下标区间；最关键的还是，使用boost::extents，可以防止用户一不小心写出错误的代码，例如：

 

multi_array<int,3> A(boost::extents[3][4][2][5]);

//错！不能用四维的下标指定来创建一个三维数组!

 

上面的语句是完全错误的，因为mult_array是个三维数组，而boost::extents后面却跟了四个“[]”，这显然是个错误。这个错误被禁止在编译期，这是由于在语法层面，multi_array3>的构造函数只能接受extent_gen<3>类型的参数，而根据我们前面对extents的分析，boost::extents[3][4][2][5]返回的却是extent_gen<4>类型的对象，于是就会产生编译错误。这种编译期的强制措施阻止了用户一不小心犯下的错误（如果你正在打瞌睡呢？），也很清晰明了地表达（强制）了语义的需求。

 

另一种替代方案及其缺点

另外，还有一种声明各维大小的替代方式，就是使用所谓的Collection Concept，例如：

 

// 声明一个shape（“形状”），即各个维度的size

    boost::array3> shape = {{ 3, 4, 2 }};

    array_type B(shape);     //3*4*2的三维数组

 

这种构造方式将调用multi_array的第二个构造函数：

 

    // multi_array.hpp

    template <class ExtentList>

    explicit multi_array( ExtentList const& extents ) :

    super_type((T*)initial_base_,extents) {

        boost::function_requires< // （2-4）

    detail::multi_array::CollectionConcept<ExtentList> >();

        allocate_space();    // （2-6）

    }

 

    这个构造函数的形参extents只要是符合collection concept就可以了——shape的类型为boost::array，当然符合这个concept。这个构造函数的行为与接受extents_gen的构造函数是一样的——仍然是先取出各维的range保存下来，然后分配底层内存。至于（2-4）处的代码，则是为了在编译期静态检查模板参数ExtentList是否符合Collection concept，实现细节在此不再赘述。

把这种方式与使用extent_gen的方式作一个简单的比较，很容易就看出优劣：采用这种方式，就不能保证编译期能够进行正确性的检查了，例如：

 

boost::array<int,4> shape = {{3,4,2,5}}; //一个四维数组的shape

multi_array<int,3> A(shape); // 竟然可以通过编译！！

 

这里，用一个四维的shape来指定一个三维multi_array是不恰当的，但是却通过了编译，这是由于该构造函数对它的参数extents没什么特殊要求，只是把它作为一个普通的collection来对待，构造函数会根据自己的需要从extents中取出它所需要的各维下标区间——A是三维数组，于是构造函数从shape中取出前三个数值作为A三个维度的下标区间，而不管shape究竟包含了几个数值。这样的语句在语义上是不清晰甚至错误的。但是既然这样的构造函数存在，设计者自然有他的道理，文档中就明确的表明，这个构造函数最大的用处就是编写维度无关（dimension-independent）的代码，除此之外multi_array库默认为前一种构造函数。

 

multi_array的架构

无论采用哪一种构造函数，构造的流程都是相似的——将一系列下标区间传入基类的构造函数中去，基类构造完成之后就调用相同的allocate_space()函数（见（2-5）和（2-6）处），allocate_space，顾名思义，用于为多维数组的元素分配空间。

然而，在这个看似简单的构造过程背后，却隐藏了两三层层次结构，每层的结构和功能都有所不同，担任了不同的角色，有些层次则能够单独拉出来复用于其他地方。

下面我们就来看看multi_array的架构到底长什么样J首先，multi_array继承自multi_array_ref：

   

// multi_array_ref.hpp

template <typename T, std::size_t NumDims>

class multi_array_ref :  //multi_array的基类！！

public const_multi_array_ref

{

    typedef const_multi_array_ref super_type;

    ... ...

    explicit multi_array_ref(T* base, //指向数组存储空间的指针

        const extent_gen& ranges): //下标区间

    super_type(base,ranges)    //把初始化的任务转发给基类（3-1）

    { }

    ... ...

};

    而multi_array_ref又以const_multi_array_ref为基类：

 

// multi_array_ref.hpp

class const_multi_array_ref : //multi_array_ref的基类!管理底层存储！

public multi_array_impl_base

{

    ... ...

    explicit const_multi_array_ref(TPtr base,

        const extent_gen& ranges) :

        base_(base), storage_(c_storage_order()) // （3-2）

        { init_from_extent_gen(ranges); }

    ... ...

    storage_order_type storage_;//支持多种存储策略！（3-3）

   

};

 

multi_array的构造之路途经（3-1）处（multi_array_ref的构造函数），延伸至（3-2）处（const_multi_array_ref的构造函数）——这里看似一个终结，因为再没有参数传递给 const_multi_array_ref的基类multi_array_impl_base了。但是心中还是疑惑：为什么会有如此多层的继承结构？这样的类层次结构设计究竟有什么玄机呢？

 

多层继承的奥秘——访问界面&&复用性

转到基类const_multi_array_ref的声明，似乎可以看出一些端倪：

 

template< ... >

class const_multi_array_ref {

    ... ...

    //和所有的STL容器一致的迭代器界面！！

    const_iterator    begin() const;

    const_iterator end() const;

    ... ...

    //和std::vector一致的元素访问界面！！

    const_reference    operator[](index i) const;

    ... ...

};