副标题#e#
我们可以通过动态数组的反例来确定动态数组应该具有哪些特性。各人都知道以下的方法是界说一个静态数组。
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个元素
#p#副标题#e#
看了上面,你会以为很烦,每当数组扩大时必需通过一个函数Add。但措施员们城市习惯的,我们会想这是应该为动态数组支付的价钱。再想一想二维数组,Add行动的事情会让你极端不爽。你会吊唁静态数组的操纵要领,直接利用iArray[10] = 10,只要你界说的上限是大于是10的。而下面,我就是要接头这一种要领的实现。
首先我们但愿有这样的一维数组:
CDynamic1Dim<int> m_dim; // m_dim的巨细是1
然后执行下面的语句:
m_dim[4] = 710;
此时m_dim的巨细是5。
#p#分页标题#e#
如何使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);
}
需要为动态二维数组重载操纵符[],其实现如下
#p#分页标题#e#
// 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.从二维动态工具(不是指针)数组的角度,以上代码并不合用于指针。
