实现真正意义上的二维动态数组模板

实现真正意义上的二维动态数组模板

作者：zyq654321

我们可以通过动态数组的反例来确定动态数组应该具有哪些特性。大家都知道以下的方式是定义一个静态数组。

int iCount[10];
int iCount[10][10];

从上面可以看出，定义了静态数组之后，无论程序如果使这个数组，该数组在内存中所占空间的大小，位置是确定不变的。

我们可以得出结论，对于编译器，静态数组的大小和空间是已知的，因此编译器可以自动为该数组分配空间。具体情况是：如果你定义了一个全局数组，编译器将在数据区为你的数组分配一个空间；如果是个局部数组（比如定义在某一个局数中），编译器为你的数组分配一个栈(Stack)空间。

从静态数组的讨论中我们得出动态数组应具有的特性：在程序的运行中，动态数组是大小应该是可变的。因些动态组数的实现应该是基于动态的分配内存基础上。下面看这个例子：

假设我们建立一个工厂工人的数据库，数据库中有多个表各代表不同的车间。每个表中保存该车间职工的信息，为了代码简单，可以只让数据库保存职工的姓名。

下面是一个InputWorkers函数，以车间为单位输入全车间职工姓名，然后一次性将这些数据存入数据库中。

void InputWorkers()
{
	int iCountOfWorkers, int iNo；
	……
	用户输入获得车间的人数和车间号
	……
	string* iArray = new string[iCountOfWorkers];
	……
	用户输入车间所有职工的信息，并存在iArray数组中
	……
	StoreInDatabase(iArray, iNo ); //存入数据库
	delete [] iArray;
}

在程序中iArray是个string指针，并不是数组。但是数组的原理和指针是一样的，比如p[1]是指数组p中的第二个元素，但在实际寻址中是以p+1进行的。所以我们可以这样使用iArray[1]。

InputWorkers中的iArray根据车间的总人数来分配不同大小的空间。从这种意义上，可以认为iArray实现了动态数组的功能。

如果iArray定义为一个静态数组，那么iArray的大小是固定的，因此我们必须估计车间人数的一个上限。

string iArray[100];

静态数组的速度是快于动态数组。因为从理论上，栈在速度上是快于堆的。但是我们如果决定使用动态数组在是因为节省空间的考虑。另外要注意静态数组上限变化带来的成本。我们必须重新设定上限以解决这个bug，然后重新编译程序。如果你能控制程序的编译，这没问题。但是，你要做是的为每一个用户更新程序。没有更新的用户就可以遇到这个bug。想到这一点，你就快乐不起来。

你可能会说，我设一下大一点的上限，超出它的可能性会非常小，而且内存的浪费也不会多大。比如最多一个车间200人，最少一个车间100人，那也只浪费了100空间。现在机器的内存根本不在乎这么一个空间浪费。是的，你可以这么做，但是请继续向下讨论。

现在我们要将所有职工的姓名存入一个二维数组，数组的每一行表示一个车间，每行中的元素是职工的姓名。想想看，如果用静态数组，你会浪费多空间。而且你还要为车间数加一个上限。这个例子并不好，因为工厂中的车间数应该是可以确定的。但是我可以换个角度说，我只要某几个车间，也可能是所有车间，那么你是否还坚持呢？

说了上面这些，只是少少的讨论了一下动态数组可能是使用情况。现实中，尤其是大型软件系统中动态数组的使用其实很普遍。而且在C++的各种库中也有数组的实现的类，通过调用相应的类函数就可以对数组中的元素实现增/删。而且也可以通过嵌套实现二维的动态。这些类或类模板使用起来很容易。比如：

CAtlArray<int> iArray;
iArray[0] = 1; // 出错，iArray中并没有元素
iArray.Add(1);   // element 2
iArray[0] = 1; // 可以，iArray中并有1个元素
iArray[0] = 1; // 出错，iArray中并只有1个元素

看了上面，你会觉得很烦，每当数组扩大时必须通过一个函数Add。但程序员们都会习惯的，我们会想这是应该为动态数组付出的代价。再想一想二维数组，Add动作的工作会让你很是不爽。你会怀念静态数组的操作方法，直接使用iArray[10] = 10，只要你定义的上限是大于是10的。而下面，我就是要讨论这一种方法的实现。

首先我们希望有这样的一维数组：

CDynamic1Dim<int> m_dim; // m_dim的大小是1

然后执行下面的语句：

m_dim[4] = 710;

此时m_dim的大小是5。

如何使m_dim[4] = 710在数组只有一个元素的情况下不会出错而且增加数组的大小以使该语句成功？最为简单的方法是重载operator[]操作符。下面我们讨论实现的细节。

template<typename T>
class Dynamic1Dim
{
public:
    Dynamic1Dim();
    ~Dynamic1Dim();
    T& operator[](int index);
protected:
    bool EnlargeDim(int iSize);
public:
    T*    m_pBuf;  
    int    m_iSize;
};

上面定义一个模板类Dynamic1Dim<T>。其构造函数如下：

//--------------------------------------------------// 构造函数

template<typename T>
Dynamic1Dim<T>::Dynamic1Dim()
{
    //数组的初始大小的1个T类型对象
    //分配一块内存其大小为T型类所占的空间

    m_pBuf = (T*)malloc(sizeof(T)); 

    //在内存空间中建立一个T型对象

    new(m_pBuf) T(); 
    m_iSize    = 1;
}

在初始函数中我们设定数组的默认长度为1。当用户使用语句m_dim[4] = 710时，重载的操作符被调用。

//--------------------------------------------------// operator [] 

template<typename T>
T& Dynamic1Dim<T>::operator [](int index) 
{
    // 如果下标是负值，抛出一个异常

    if( index < 0 ) throw std::out_of_range(" Index shouldn''t be negative"); 

    //检查下标是否超来数组大小，如果超过则调用EnlargeDim扩大数组

    if(index > m_iSize - 1)
       EnlargeDim(index + 1);
    Return m_pBuf [index];
}

//--------------------------------------------------// Enlarge

template<typename T>

bool Dynamic1Dim<T>::EnlargeDim(int iSize) 
{

    // 重新分配一块内存，其大小为扩大后T类型数组的大小

    m_pBuf = (string*) realloc(m_pBuf, sizeof(T) * iSize); 

    // 在扩大部分的内存空间上建立T类型的数组对象，并调用其默认构造函数

    for(int i = m_iSize; i < iSize; i++)
    {
       new(&m_pBuf[i]) T();
    }

    m_iSize = iSize;
    return true;
}

上面的代码已基本实现了动态一维数组的要求。但有一个点必须当心，就是数组空间的释放问题。在Dynamic1Dim的析构函数中必须释放动态分配的空间。

//--------------------------------------------------// Destructor

template<typename T>
Dynamic1Dim<T>::~Dynamic1Dim()
{ 
    // 调用T类的析构函数

    for(int i = 0; i < m_iSize; i++)
    {
       m_pBuf [i].~T();
    }

    // 释放内存空间
    free(m_pBuf);
}

注意，m_pElem[i].~T()是必要的，因为T对象中也可能有内存的分配。如果没有这句，T对象中分配的内存就无法释放，其实这也是很多内存泄露的原因。

上面的代码实现了动态一维数组的模板。我们最后就要讨论动态二维数组的实现。

我们会希望有这样的二维数组：

CDynamic2Dim<int> m_dim; // m_dim的大小是1*1

然后执行下面的语句：

m_dim[1][3] = 33;
m_dim[4][10] = 710;

此时m_dim的大小是：0、2、3行都只有一个元素，1行有4个元素，4行有11个元素。 可以这样设想，动态二维数组是由数目不定的动态一维数组组成的。基于这种想法，我们看一下动态二维数组的实现。

template<typename T>
class Dynamic2Dim
{
public:
    Dynamic2Dim();
    ~Dynamic2Dim();
    Dynamic1Dim<T>& operator[] (int index);
protected:
    bool EnlargeY(int nYSize);
private:
    int m_iYSize;
    Dynamic1Dim<T>* m_pYBuf;
    Dynamic1Dim<T> m;
};

初始的二维数组应该是1*1大小的，因此Dynamic2Dim的构造函数应该如下

// Constructor

template<typename T>
Dynamic2Dim<T>::Dynamic2Dim()
{
    m_iYSize = 1;
    m_pYBuf = (Dynamic1Dim<T>*) malloc(sizeof(Dynamic1Dim<T>));
    m_pYElem = new(m_pYBuf) Dynamic1Dim<T>();
}

在析构函数中释放分配的内存空间:

// Desctructor

template<typename T>
Dynamic2Dim<T>::~Dynamic2Dim()
{
    for(int i = 0; i < m_iYSize; i++)
    {
       m_pYElem[i].~Dynamic1Dim();
    }
    free(m_pYBuf);
}

需要为动态二维数组重载操作符[]，其实现如下

// operator[] overload

template<typename T>
Dynamic1Dim<T>& Dynamic2Dim<T>::operator[] (int index)
{
    if(index < 0) throw std::out_of_range("negative index!");

    if(index > m_iYSize - 1)
       EnlargeY(index + 1);

    return m_pYElem[index];
}

从上我们可以知道，这里实现的是二维数组的纵向扩大，即根据二维数组的第一下标在决定是否扩大二维数组。这里须要注意的是返回值是一个一维动态数组，由于一维动态数组也重载了[]操作符，所以用户可以最终得到一个指定的二维数组元素的引用（其类型为T）。

以上就是一个动态二维数组的基本实现，说它是基本实现，我是指它可以工作，但实际使用应该注意下而几个问题。

1．数组的动态扩张是否在我们所期望的情况下进行的。看下面的例子：

Dynamic2Dim<string> arrString;
arrString[3][4] = "34";
string str = arrString[6][6];

根据动态数组的定义，可以确定动态二维数组进行了二次扩张，第一次数组空间为4*n，这是我们期望的；第二次为7*n，在大多数情况下这不是我们期望的。（这里使用n是因为二维数组的行元素数目是不同的。）

在这里我给出一个解决的方法。可以使用代理类(proxy class)来区别上面二种情况，在第二种情况下可以抛出一个异常。

2．动态分配空间的大小。malloc须要调用操作系统的低级操作，我们不希望频繁调用它，因此可以预先分配较大一些的空间。例如：用户使用下标5时，我们分配5*2的空间。

3．realloc的问题。在已经分配了较大内存空间时，realloc会引起很大的开销（它必须进行内存的拷贝以保持原有数据）。此时我们可以考虑使用malloc只分配所须的新的空间，尽管这样有点复杂，但相比大块的内存拷贝带来的开销还是值得的。

4．因为动态二维数组操作符[]返回的是一个动态一维数组的引用，所以与普通二维数组相比，它有一些限制。

Dynamic2Dim<string> dim1;
string dim2[10][10];
string *p;
p = dim2[3]; //Ok
p = dim1[3]; //Error. 因为dim1[3]返回的是Dynamic1Dim<string>类型，而不是string类型。

5．在实际使用时，可以增加一个函数，返回当前数组的大小。可以使用inline来减小引入其带来的开销。

6．从二维动态对象（不是指针）数组的角度，以上代码并不适用于指针。