动态数组对比STL vector及其实现(c/c++)

c/c++动态数组

动态数组 顾名思义能 动态增加内存的数组。 STL标准库中的vector具有类似的功能，c标准库的realloc也具有类似的功能，那为何还需要自己实现动态内存方式呢?对于追求效率，和有重要性能需求的我们来说，实现动态数组能让我们的程序运行的更有效率,下面分别谈一下vector 和realloc.

1.vector

再STL标准库的实现当中，vector内存不够时，会动态的把自己的容量扩展原来的1.5-2倍(这个大家可以自己写个例子检验一下）

这个过程他会重新申请内存，并把原来的数据拷贝到新内存当中来，并删除原来的内存。这样操作会有些弊端，比如操作大对象数据

这样的拷贝效率确实有点低. 这个问题可以通过在vector当中只存储大对象的指针来优化， 但是还是存在一些不必要的拷贝。

而且有些需求动态增加的内存并不是我们想要的。在一些动态可控的内存管理上vector还不能满足我们的需求。

2.realloc

realloc函数的调用可能会引发元素地址的迁移，尤其是多线程环境下，发生的概率更大，地址变化的结果足以使的整个系统的崩溃。

分析了vector和realloc的不足，来对比一下动态数组。

1.数组的地址是不会变化的，因此不会出现内存迁移的问题

2.可以根据需求任意更改内存增加的大小来控制内存分配。

3.满足特定的、可控的动态内存分配，避免由于动态内存分配引起的浪费。

4.没有内存copy的顾虑，效率高

5.使用上几乎和普通数组没什么区别

动态内存的实现:

其实现原理比较简单，主要操作跟数组一样，根据插入元素，根据index查找元素，还有独特的是动态分配内存。下面是动态内存实现的伪代码

(仅供思路)

#define ARRAY_SIZE  1024
#define ARRAY_NUMBER 1024
typedef  int  Type;
typedef struct dArray
{
    Type elementArray[ARRAY_SIZE];
}DArray;
DArray *pDynamicArray[ARRAY_NUMBER];
int gAllocArraySize = 0;
int gCurrentArrayIndex = 0;
bool rellocArray(int size);
bool insert_element(Type *value)
{
    if(false ==rellocArray(sizeof(Type)))
       return false;
    if(gCurrentArrayIndex>gAllocArraySize-1)
        return false;
    int mainIndex = gCurrentArrayIndex / ARRAY_SIZE;
    int elementArrayInex = (++gCurrentArrayIndex)%ARRAY_SIZE - 1;
    pDynamicArray[mainIndex]->elementArray[elementArrayInex] = *value;
    
    return true;
}
Type *get_element(int index)
{
    if(index>=0 && index<gAllocArraySize)
    {
        int mainIndex = index/ARRAY_SIZE;
        int elementArrayIndex = index%ARRAY_SIZE  - 1;
        return &(pDynamicArray[mainIndex]->elementArray[elementArrayIndex]);
    }
    return NULL;
}
bool rellocArray(int size)
{
    if(size> ARRAY_NUMBER*ARRAY_SIZE - gAllocArraySize)
        return false;
    while(gAllocArraySize<=size)
    {
        int mainIndex =  gAllocArraySize /ARRAY_SIZE;
        pDynamicArray[mainIndex] = (DArray*)calloc(1,sizeof(DArray));
        if(NULL==pDynamicArray[mainIndex])
            return false;
        gAllocArraySize += ARRAY_SIZE;
    }
    return true;
}

转转请注明：点击打开链接http://blog.csdn.net/typename/article/details/8202741