CWYAlpha

Just another WordPress.com site

Thought this was cool: C/C++语言实现动态数组

leave a comment »


C数组的小问题
     这里说的动态数组是可以根据需要动态增长占用内存的数组,比如程序初始分配了100个元素,可是运行了一段时间后区区100个空间不能满足了,现在需要400个,怎么办呢;那肯定需要再额外分配300个。
     C语言有realloc()函数来解决空间扩充的问题,但是不要忘了realloc可能会迁移内存,很多时候数组中的元素会被其它函数/模块引用,如果地址发生了变化,结果将是灾难性的。
     那么STL的vector呢?它也有相同的问题。
     一次分配足够的空间是可以解决这个问题,很明显这会造成内存的浪费,这个做法不算明智。
     不使用数组呢?使用list能解决一部分问题,但是list不能支持随机访问啊,鉴于效率上的硬伤,显然不能随便用list替换数组。
     怎么解决这个问题呢?动态数组!在HPServer 的Demutex Table就用到了动态数组,事实证明效果不错。
动态数组的特征
动态数组是一个很简单易用的数据结构,但是简单不代表优点小,它的特征如下:
1 根据需要动态批量增长内存;
2 一经分配,元素地址不会再次变化;
3 实现简单,效率高,事实上它和普通数组相比基本没有效率损失;
4 最大个数固定;
其实最重要的就是特征2了,不然直接使用realloc多方便呢,当然动态数组的实现也很方便,下面就会详细说说。
特征4实际上是个限制,但是相信我,你的程序不可能达到这个最大值。
动态数组的实现
如上面所说的,动态数组实现起来很简单,以下都假设数组元素类型是T,首先需要一个辅助数据结构。
[cpp] view plaincopyprint?
struct ARRAY_ELE_S  
{  
    T item_array[1024];  
};  
ARRAY_ELE_S *pArray[2000];  
int iSize;   
变量pArray是一个ARRAY_ELE_S类型的指针数组,这个也就是你的动态数组了;iSize记录了当前数组的大小。
上面的代码表明:
1 数组每次动态增长1024个元素;
2 数组的最大元素个数可以到:2000*1024个,如果这个还不够,你可以把这个值改的更大点。
先来看看内存占用,pArray本身占用2000*4,大约是8K的内存,基本可以忽略了。
如果一次分配一个2000*1024的数组array[2000*1024],那么一次就要分配的内存是:2*sizeof(T) M,空间浪费严重。
再来看看效率,下面就从数组最主要的操作——随机访问来看看它的效率如何;接下来再看看它是如何根据需要动态增长的。
随机访问
访问指定的索引位置上的数组元素,这个需要两步计算,首先定位到元素在哪个子数组上,然后再定位到子数组的元素上;其实很简单。
[cpp] view plaincopyprint?
T *get(int idx)  
{  
    // 确保索引有效   
    if((idx>=0) && (idx
    {  
        int idx_maj = idx/1024; // 主索引   
        int idx_mor = idx – (idx_maj); // 次索引   
        return (&(pArray[idx_maj]->item_array[idx_mor]));  
    }  
    return NULL;  
}  
item_array[idx_mor])); } return NULL; }
动态增长
如果当前空间不够,需要动态增长数组,不然怎么叫动态呢,基本思想就是如果需要的size超过当前的数组大小,就需要增长数组,直到能够容纳size个元素,代码如下所示。
[cpp] view plaincopyprint?
int reclac(int size)  
{  
    if(size >= 1024*2048)     return -1; // 太大了   
    while(iSize <= size)  
    {  
        // 分配内存,并初始化为0   
        int idx = iSize/1024;  
        pArray[idx] = (ARRAY_ELE_S*)calloc(1, sizeof(ARRAY_ELE_S));  
        if(pArray[idx] == NULL)  
        {  
            return (-1);  
        }  
        iSize += 1024;  
    }  
    return 0;  
}  
转自:www.software8.co/wzjs/cpp/  转载请注明
动态数组就这么多零碎了,怎么样,实现起来够简单吧。

段正淳 2012-10-30 14:12 发表评论


from C++博客_Kevin Lynx: http://www.cppblog.com/newcnzz/archive/2012/10/30/194088.html

Written by cwyalpha

十月 31, 2012 在 3:09 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: