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]
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]
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]
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;
}
