程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C++中用vectors改進內存的再分配

C++中用vectors改進內存的再分配

編輯:關於C

這裡描述的是一種很常見的情況:當你在某個緩存中存儲數據時,常常需要在運行時調整該緩存的大小,以便能容納更多的數據。傳統的內存再分配技術非常繁瑣,而且容易出錯:在 C 語言中,一般都是每次在需要擴充緩存的時候調用 realloc()。在 C++ 中情況更糟,你甚至無法在函數中為 new 操作分配的數組重新申請內存。你不僅要自己做分配處理,而且還必須把原來緩存中的數據拷貝到新的目的緩存,然後釋放先前數組的緩存。本文將針對這個問題提供一個安全、簡易並且是自動化的 C++ 內存再分配技術——即使用 STL 的 vector。

  用 STL vector 對象取代內建的數組來保存獲取的數據,既安全又簡單,並且是自動化的。

  進一步的問題分析

  在提出解決方案之前,我先給出一個具體的例子來說明 C++ 重新分配內存的弊病和復雜性。假設你有一個編目應用程序,它讀取用戶輸入的 ISBNs,然後將之插入一個數組,直到用戶輸入 0 為止。如果用戶插入的數據多於數組的容量,那麼你必須相應地增加它的大小:

#include <iostream>
using namespace std;

int main()
{
 int size=2; // 初始化數組大小;在運行時調整。
 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) // 數組是否到達上限?
   reallocate(p, size);
   p[n]=isbn; // 將元素插入擴容的數組
 }
 delete [] p; // 不要忘了這一步!
}

  注意上述這個向數組插入數據的過程是多麼的繁瑣。每次反復,循環都要檢查緩存是否達到上限。如果是,則程序調用用戶定義的函數 reallocate(),該函數實現如下:

#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() 算法對緩存進行合理的擴充——每次擴充都放大一倍。這種方法可以避免預先分配過多的內存,從量上減少需要重新分配的內存。這個技術需要得到充分的測試和調試,當初學者實現時尤其如此。此外,reallocate() 並不通用,它只能處理整型數組的情形。對於其它數據類型,它無能為力,你必須定義該函數額外的版本或將它模板化。幸運的是,有一個更巧妙的辦法來實現。

  創建和優化 vector

  每一個 STL 容器都具備一個分配器(allocator),它是一個內建的內存管理器,能自動按需要重新分配容器的存儲空間。因此,上面的程序可以得到大大簡化,並擺脫 reallocator 函數。

  第一步:創建 vector

  用 vector 對象取代內建的數組來保存獲取的數據。main() 中的循環讀取 ISBN,檢查它是否為 0,如果不為 0 ,則通過調用 push_back() 成員函數將值插入

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 對象構造期間,它先分配一個由其實現定義的默認的緩存大小。一般 vector 分配的數據存儲初始空間是 64-256 存儲槽(slots)。當 vector 感覺存儲空間不夠時,它會自動重新分配更多的內存。實際上,只要你願意,你可以調用 push_back() 任何多次,甚至都不用知道一次又一次的分配是在哪裡發生的。

  為了存取 vector 元素,使用重載的 [] 操作符。下列循環在屏幕上顯示所有 vector 元素:

for (int n=0; n<vi.size(); ++n)
{
 cout<<"ISBN: "<<vi[n]<<endl;
}

  第二步:優化

  在大多數情況下,你應該讓 vector 自動管理自己的內存,就像我們在上面程序中所做的那樣。但是,在注重時間的任務中,改寫默認的分配方案也是很有用的。假設我們預先知道 ISBNs 的數量至少有 2000。那麼就可以在對象構造期間指出容量,以便 vector 具有至少 2000 個元素的容量:

vector <int> vi(2000); // 初始容量為 2000 個元素

  除此之外,我們還可以調用 resize() 成員函數:

vi.resize(2000);// 建立不小於 2000 個元素的空間

  這樣,便避免了中間的再分配,從而提高了效率。

  

*
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved