---
title: "boost源码剖析之：泛型多维数组类multi_array"
author: "winzenghua"
date: "2007-04-11T16:16:00Z"
tags: []
slug: "boost-multi-array"
draft: false
lastmod: "2007-04-11T16:16:00Z"
id: 947866
url: "https://java4gis.iteye.com/blog/947866"
---

**boost源码剖析之：boost::multi\_array**

谢轩 刘未鹏

C++的罗浮宫(http://blog.csdn.net/pongba)

*Note: 并非新作，是以前和老朋友谢轩写的，也可以在*[*谢轩的blog上找到。*](http://blog.csdn.net/infinitude_CN)

**动机**

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型的**3**维数组，*dim\_sizes*表示各维的大小：n1\*n2\*n3

*multi\_array*&lt;int,**3**&gt; 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&lt; std::vector&lt;…&gt; &gt; ）更为便捷、高效。对示例程序进行调试、跟踪是分析库源代码最有效的手段之一。我们就从MultiArray文档中的示例程序入手：

// 略去头文件包含

int main () {

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

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

typedef boost::multi\_array&lt;double,**DIMS**&gt; array\_type; // (1-1)

array\_type A(**boost::extents\[3]\[4]\[2]**); // **(1-2)**

// 为数组中元素赋值

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

... ...

return 0;

}

在上述代码中，（1-1）处的typedef是我们程序中使用的三维数组类型的声明，很明显，**boost::multi\_array的两个模板参数分别代表数组元素的类型和数组的维度**。而（1-2）处就是三维数组对象的构造语句。**boost::extents\[3]\[4]\[2]**的意思是：定义一个3\*4\*2的三维数组。

下面我就为你层层剥开boost::extents的所有奥秘——

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

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

typedef detail::multi\_array::**extent\_gen&lt;0&gt;** **extent\_gen**;

... ...

multi\_array\_types::**extent\_gen** **extents**; //注意它的类型！

可见**extents**的类型为extent\_gen，这个extend\_gen则位于extent\_gen.hpp中：

// extent\_gen.hpp

template &lt;std::size\_t NumRanges&gt;

class **extent\_gen** {

range\_list ranges\_; // **（2-1）**

... ...

**extent\_gen**(const **extent\_gen&lt;NumRanges-1&gt;**& rhs, const range& a\_range) // **（2-2）**

{

std::copy(rhs.ranges\_.begin(),rhs.ranges\_.end(),ranges\_.begin());

\*ranges\_.rbegin() = a\_range;

}

**extent\_gen**&lt;**NumRanges+1**&gt;

**operator\[]**(index idx) // **（2-3）**

{ return **extent\_gen&lt;NumRanges+1&gt;**(\*this,range(0,idx)); }

};

所以，**boost::extents\[3]\[4]\[2]**展开为操作符调用的方式就相当于：

extents.**operator** \[](**3**).**operator** \[](**4**).**operator** \[](**2**);

extents是**extent\_gen&lt;0&gt;**类型的，extents.operator \[](3)应调用函数**（****2-3）**，**此时****NumRange为0**，而返回类型是**extent\_gen&lt;1&gt;**；再以该返回对象调用operator \[](4)，**此时****NumRange为1**，而返回类型则是**extent\_gen&lt;2&gt;**了。再看函数**（****2-3）**的内容，其实就是将参数idx以range包装一下再转发给构造函数（2-2），注意此时调用的是**extent\_gen&lt;NumRange+1&gt;**类型的构造函数。至于range(0,idx)则表示一个[0,idx)的区间。进入构造函数**（****2-2）**，我们注意到extent\_gen&lt;...&gt;中具有public的成员ranges\_，声明位于**（****2-1）**处，而ranges\_就是一个容器，保存了一系列的range。

跟踪这些代码，基本了解了extents的工作方式：每调用一次operator \[]，都会返回一个**extent\_gen&lt;NumRange+1&gt;**类型的对象，所以，对于boost::extents\[3]\[4]\[2]，依次返回的是：

**extent\_gen&lt;1&gt; =&gt; extent\_gen&lt;2&gt; =&gt; extent\_gen&lt;3&gt;**

最后一个也是最终的返回类型——**extent\_gen&lt;3&gt;**。其成员ranges\_中，共有[0，3）、[0，4）、[0，2）三组区间。这三组区间指定了我们定义的multi\_array对象的三个维度的下标区间，值得注意的是这些区间都是前闭后开的，即不包含上界值，这一点在后面的代码中能够看到。当boost::extents准备完毕后，就被传入multi\_array的构造函数，用于指定各维的下标区间：

// multi\_array.hpp

explicit multi\_array(const **extent\_gen&lt;NumDims&gt;**& ranges) :

super\_type((T\*)initial\_base\_,ranges) {

**allocate\_space**(); // **（2-5）**

}

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

**使用extent\_gen的好处**

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

multi\_array&lt;int,**3**&gt; A(boost::extents**\[3]\[4]\[2]\[5]**);//错！多了一维！

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

**另一种替代方案及其缺点**

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

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

boost::**array**&lt;int,**3**&gt; **shape** = {{ **3**, **4**, **2** }};

array\_type B(**shape**); //3\*4\*2的三维数组

这种方式将调用multi\_array的第二种构造函数：

// multi\_array.hpp

template &lt;class ExtentList&gt;

explicit **multi\_array**( **ExtentList** const& **extents** ) :

super\_type((T\*)initial\_base\_,**extents**) {

boost::function\_requires&lt; // **（2-4）**

detail::multi\_array::CollectionConcept&lt;**ExtentList**&gt; &gt;();

**allocate\_space**(); // **（2-6）**

}

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

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

boost::array&lt;int,**4**&gt; **shape** = {{**3,4,2,5**}}; //**一个四维数组的shape**

multi\_array&lt;int,**3**&gt; A(**shape**); // **竟然可以通过编译！！**

这里，用一个四维的shape来指定一个三维multi\_array显然是错误的，但是居然通过了编译，这是由于这个构造函数将它的参数extents作为一个普通的collection来对待，构造函数根据自己的需求用iterator从&lt;