C++中用vectors改進(jìn)內(nèi)存的再分配
作者: MTT 工作室 C++學(xué)習(xí)資源網(wǎng)
摘要：本文描述的是一種很常見(jiàn)的情況：當(dāng)你在某個(gè)緩存中存儲(chǔ)數(shù)據(jù)時(shí)，常常需要在運(yùn)行時(shí)調(diào)整該緩存的大小，以便能容納更多的數(shù)據(jù)。本文將討論如何使用 STL 的 vector 進(jìn)行內(nèi)存的再分配。
這里描述的是一種很常見(jiàn)的情況：當(dāng)你在某個(gè)緩存中存儲(chǔ)數(shù)據(jù)時(shí)，常常需要在運(yùn)行時(shí)調(diào)整該緩存的大小，以便能容納更多的數(shù)據(jù)。傳統(tǒng)的內(nèi)存再分配技術(shù)非常繁瑣，而且容易出錯(cuò)：在 C 語(yǔ)言中，一般都是每次在需要擴(kuò)充緩存的時(shí)候調(diào)用 realloc()。在 C++ 中情況更糟，你甚至無(wú)法在函數(shù)中為 new 操作分配的數(shù)組重新申請(qǐng)內(nèi)存。你不僅要自己做分配處理，而且還必須把原來(lái)緩存中的數(shù)據(jù)拷貝到新的目的緩存，然后釋放先前數(shù)組的緩存。本文將針對(duì)這個(gè)問(wèn)題提供一個(gè)安全、簡(jiǎn)易并且是自動(dòng)化的 C++ 內(nèi)存再分配技術(shù)——即使用 STL 的 vector。
用 STL vector 對(duì)象取代內(nèi)建的數(shù)組來(lái)保存獲取的數(shù)據(jù)，既安全又簡(jiǎn)單，并且是自動(dòng)化的。
進(jìn)一步的問(wèn)題分析
在提出解決方案之前，我先給出一個(gè)具體的例子來(lái)說(shuō)明 C++ 重新分配內(nèi)存的弊病和復(fù)雜性。假設(shè)你有一個(gè)編目應(yīng)用程序，它讀取用戶(hù)輸入的 ISBNs，然后將之插入一個(gè)數(shù)組，直到用戶(hù)輸入 0 為止。如果用戶(hù)插入的數(shù)據(jù)多于數(shù)組的容量，那么你必須相應(yīng)地增加它的大?。?div style="height:15px;">
#include ＜iostream＞
using namespace std;
int main()
{
int size=2; // 初始化數(shù)組大?。辉谶\(yùn)行時(shí)調(diào)整。
int *p = new int[size];
int isbn;
for(int n=0; ;++n)
{
cout＜＜ "enter an ISBN; press 0 to stop ";
cin＞＞isbn;
if (isbn==0)
break;
if (n==size) // 數(shù)組是否到達(dá)上限?
reallocate(p, size);
p[n]=isbn; // 將元素插入擴(kuò)容的數(shù)組
}
delete [] p; // 不要忘了這一步!
}
注意上述這個(gè)向數(shù)組插入數(shù)據(jù)的過(guò)程是多么的繁瑣。每次反復(fù)，循環(huán)都要檢查緩存是否達(dá)到上限。如果是，則程序調(diào)用用戶(hù)定義的函數(shù) reallocate()，該函數(shù)實(shí)現(xiàn)如下：
#include ＜algorithm＞ // for std::copy
int reallocate(int* &p, int& size)
{
size*=2; // double the array‘‘s size with each reallocation
int * temp = new int[size];
std::copy(p, p+(size/2), temp);
delete [] p; // release original, smaller buffer
p=temp; // reassign p to the newly allocated buffer
}
reallocate() 使用 STL std::copy() 算法對(duì)緩存進(jìn)行合理的擴(kuò)充——每次擴(kuò)充都放大一倍。這種方法可以避免預(yù)先分配過(guò)多的內(nèi)存，從量上減少需要重新分配的內(nèi)存。這個(gè)技術(shù)需要得到充分的測(cè)試和調(diào)試，當(dāng)初學(xué)者實(shí)現(xiàn)時(shí)尤其如此。此外，reallocate() 并不通用，它只能處理整型數(shù)組的情形。對(duì)于其它數(shù)據(jù)類(lèi)型，它無(wú)能為力，你必須定義該函數(shù)額外的版本或?qū)⑺０寤?。幸運(yùn)的是，有一個(gè)更巧妙的辦法來(lái)實(shí)現(xiàn)。
創(chuàng)建和優(yōu)化 vector
每一個(gè) STL 容器都具備一個(gè)分配器（allocator），它是一個(gè)內(nèi)建的內(nèi)存管理器，能自動(dòng)按需要重新分配容器的存儲(chǔ)空間。因此，上面的程序可以得到大大簡(jiǎn)化，并擺脫 reallocator 函數(shù)。
第一步：創(chuàng)建 vector
用 vector 對(duì)象取代內(nèi)建的數(shù)組來(lái)保存獲取的數(shù)據(jù)。main() 中的循環(huán)讀取 ISBN，檢查它是否為 0，如果不為 0 ，則通過(guò)調(diào)用 push_back() 成員函數(shù)將值插入
vector： #include ＜iostream＞
#include ＜vector＞
using namespace std;
int main()
{
vector ＜int＞ vi;
int isbn;
while(true)
{
cout ＜＜ "enter an ISBN; press 0 to stop ";
cin ＞＞ isbn;
if (isbn==0)
break;
vi.push_back(isbn); // insert element into vector
}
}
在 vector 對(duì)象構(gòu)造期間，它先分配一個(gè)由其實(shí)現(xiàn)定義的默認(rèn)的緩存大小。一般 vector 分配的數(shù)據(jù)存儲(chǔ)初始空間是 64-256 存儲(chǔ)槽（slots）。當(dāng) vector 感覺(jué)存儲(chǔ)空間不夠時(shí)，它會(huì)自動(dòng)重新分配更多的內(nèi)存。實(shí)際上，只要你愿意，你可以調(diào)用 push_back() 任何多次，甚至都不用知道一次又一次的分配是在哪里發(fā)生的。
為了存取 vector 元素，使用重載的 [] 操作符。下列循環(huán)在屏幕上顯示所有 vector 元素：
for (int n=0; n＜vi.size(); ++n)
{
cout＜＜"ISBN: "＜＜vi[n]＜＜endl;
}
第二步：優(yōu)化
在大多數(shù)情況下，你應(yīng)該讓 vector 自動(dòng)管理自己的內(nèi)存，就像我們?cè)谏厦娉绦蛑兴龅哪菢?。但是，在注重時(shí)間的任務(wù)中，改寫(xiě)默認(rèn)的分配方案也是很有用的。假設(shè)我們預(yù)先知道 ISBNs 的數(shù)量至少有 2000。那么就可以在對(duì)象構(gòu)造期間指出容量，以便 vector 具有至少 2000 個(gè)元素的容量：
vector ＜int＞ vi(2000); // 初始容量為 2000 個(gè)元素
除此之外，我們還可以調(diào)用 resize() 成員函數(shù)：
vi.resize(2000);// 建立不小于 2000 個(gè)元素的空間
這樣，便避免了中間的再分配，從而提高了效率。
