| 導購 | 订阅 | 在线投稿
分享
 
 
 

實現真正意義上的二維動態數組模板

來源:互聯網  2008-06-01 02:08:09  評論

我們可以通過動態數組的反例來確定動態數組應該具有哪些特性。大家都知道以下的方式是定義一個靜態數組 int iCount[10];

int iCount[10][10];

從上面可以看出,定義了靜態數組之後,無論程序假如使這個數組,該數組在內存中所占空間的大小,位置是確定不變的。

我們可以得出結論,對于編譯器,靜態數組的大小和空間是已知的,因此編譯器可以自動爲該數組分配空間。具體情況是:假如你定義了一個全局數組,編譯器將在數據區爲你的數組分配一個空間;假如是個局部數組(比如定義在某一個局數中),編譯器爲你的數組分配一個棧(Stack)空間。

從靜態數組的討論中我們得出動態數組應具有的特性:在程序的運行中,動態數組是大小應該是可變的。因些動態組數的實現應該是基于動態的分配內存基礎上。下面看這個例子:

假設我們建立一個工廠工人的數據庫,數據庫中有多個表各代表不同的車間。每個表中保存該車間職工的信息,爲了代碼簡單,可以只讓數據庫保存職工的姓名。

下面是一個InputWorkers函數,以車間爲單位輸入全車間職工姓名,然後一次性將這些數據存入數據庫中。void InputWorkers()

{

int iCountOfWorkers, int iNo;

……

用戶輸入獲得車間的人數和車間號

……

string* iArray = new string[iCountOfWorkers];

……

用戶輸入車間所有職工的信息,並存在iArray數組中

……

StoreInDatabase(iArray, iNo ); //存入數據庫

delete [] iArray;

}

在程序中iArray是個string指針,並不是數組。但是數組的原理和指針是一樣的,比如p[1]是指數組p中的第二個元素,但在實際尋址中是以p+1進行的。所以我們可以這樣使用iArray[1]。

InputWorkers中的iArray根據車間的總人數來分配不同大小的空間。從這種意義上,可以認爲iArray實現了動態數組的功能。

假如iArray定義爲一個靜態數組,那麽iArray的大小是固定的,因此我們必須估計車間人數的一個上限。string iArray[100];

靜態數組的速度是快于動態數組。因爲從理論上,棧在速度上是快于堆的。但是我們假如決定使用動態數組在是因爲節省空間的考慮。另外要注重靜態數組上限變化帶來的成本。我們必須重新設定上限以解決這個bug,然後重新編譯程序。假如你能控制程序的編譯,這沒問題。但是,你要做是的爲每一個用戶更新程序。沒有更新的用戶就可以碰到這個bug。想到這一點,你就快樂不起來。

你可能會說,我設一下大一點的上限,超出它的可能性會非常小,而且內存的浪費也不會多大。比如最多一個車間200人,最少一個車間100人,那也只浪費了100空間。現在機器的內存根本不在乎這麽一個空間浪費。是的,你可以這麽做,但是請繼續向下討論。

現在我們要將所有職工的姓名存入一個二維數組,數組的每一行表示一個車間,每行中的元素是職工的姓名。想想看,假如用靜態數組,你會浪費多空間。而且你還要爲車間數加一個上限。這個例子並不好,因爲工廠中的車間數應該是可以確定的。但是我可以換個角度說,我只要某幾個車間,也可能是所有車間,那麽你是否還堅持呢?

說了上面這些,只是少少的討論了一下動態數組可能是使用情況。現實中,尤其是大型軟件系統中動態數組的使用其實很普遍。而且在C++的各種庫中也有數組的實現的類,通過調用相應的類函數就可以對數組中的元素實現增/刪。而且也可以通過嵌套實現二維的動態。這些類或類模板使用起來很輕易。比如:CAtlArray<int> iArray;

iArray[0] = 1; // 出錯,iArray中並沒有元素

iArray.Add(1); // element 2

iArray[0] = 1; // 可以,iArray中並有1個元素

iArray[0] = 1; // 出錯,iArray中並只有1個元素

看了上面,你會覺得很煩,每當數組擴大時必須通過一個函數Add。但程序員們都會習慣的,我們會想這是應該爲動態數組付出的代價。再想一想二維數組,Add動作的工作會讓你很是不爽。你會懷念靜態數組的操作方法,直接使用iArray[10] = 10,只要你定義的上限是大于是10的。而下面,我就是要討論這一種方法的實現。

首先我們希望有這樣的一維數組:CDynamic1Dim<int> m_dim; // m_dim的大小是1

然後執行下面的語句: m_dim[4] = 710;

此時m_dim的大小是5。

如何使m_dim[4] = 710在數組只有一個元素的情況下不會出錯而且增加數組的大小以使該語句成功?最爲簡單的方法是重載operator[]操作符。下面我們討論實現的細節。template<typename T>

class Dynamic1Dim

{

public:

Dynamic1Dim();

~Dynamic1Dim();

T& operator[](int index);

protected:

bool EnlargeDim(int iSize);

public:

T* m_pBuf;

int m_iSize;

};

上面定義一個模板類Dynamic1Dim<T>。其構造函數如下: //--------------------------------------------------// 構造函數

template<typename T>

Dynamic1Dim<T>::Dynamic1Dim()

{

//數組的初始大小的1個T類型對象

//分配一塊內存其大小爲T型類所占的空間

m_pBuf = (T*)malloc(sizeof(T));

//在內存空間中建立一個T型對象

new(m_pBuf) T();

m_iSize = 1;

}

在初始函數中我們設定數組的默認長度爲1。當用戶使用語句m_dim[4] = 710時,重載的操作符被調用。 //--------------------------------------------------// operator []

template<typename T>

T& Dynamic1Dim<T>::operator [](int index)

{

// 假如下標是負值,抛出一個異常

if( index < 0 ) throw std::out_of_range(" Index shouldn\\\'\\\'t be negative");

//檢查下標是否超來數組大小,假如超過則調用EnlargeDim擴大數組

if(index > m_iSize - 1)

EnlargeDim(index + 1);

Return m_pBuf [index];

}

//--------------------------------------------------// Enlarge

template<typename T>

bool Dynamic1Dim<T>::EnlargeDim(int iSize)

{

// 重新分配一塊內存,其大小爲擴大後T類型數組的大小

m_pBuf = (string*) realloc(m_pBuf, sizeof(T) * iSize);

// 在擴大部分的內存空間上建立T類型的數組對象,並調用其默認構造函數

for(int i = m_iSize; i < iSize; i++)

{

new(&m_pBuf[i]) T();

}

m_iSize = iSize;

return true;

}

上面的代碼已基本實現了動態一維數組的要求。但有一個點必須當心,就是數組空間的釋放問題。在Dynamic1Dim的析構函數中必須釋放動態分配的空間。 //--------------------------------------------------// DestrUCtor

template<typename T>

Dynamic1Dim<T>::~Dynamic1Dim()

{

// 調用T類的析構函數

for(int i = 0; i < m_iSize; i++)

{

m_pBuf [i].~T();

}

// 釋放內存空間

free(m_pBuf);

}

注重,m_pElem[i].~T()是必要的,因爲T對象中也可能有內存的分配。假如沒有這句,T對象中分配的內存就無法釋放,其實這也是很多內存泄露的原因。

上面的代碼實現了動態一維數組的模板。我們最後就要討論動態二維數組的實現。

我們會希望有這樣的二維數組:CDynamic2Dim<int> m_dim; // m_dim的大小是1*1

然後執行下面的語句: m_dim[1][3] = 33;

m_dim[4][10] = 710;

此時m_dim的大小是:0、2、3行都只有一個元素,1行有4個元素,4行有11個元素。 可以這樣設想,動態二維數組是由數目不定的動態一維數組組成的。基于這種想法,我們看一下動態二維數組的實現。 template<typename T>

class Dynamic2Dim

{

public:

Dynamic2Dim();

~Dynamic2Dim();

Dynamic1Dim<T>& operator[] (int index);

protected:

bool EnlargeY(int nYSize);

private:

int m_iYSize;

Dynamic1Dim<T>* m_pYBuf;

Dynamic1Dim<T> m;

};

初始的二維數組應該是1*1大小的,因此Dynamic2Dim的構造函數應該如下 // Constructor

template<typename T>

Dynamic2Dim<T>::Dynamic2Dim()

{

m_iYSize = 1;

m_pYBuf = (Dynamic1Dim<T>*) malloc(sizeof(Dynamic1Dim<T>));

m_pYElem = new(m_pYBuf) Dynamic1Dim<T>();

}

在析構函數中釋放分配的內存空間: // Desctructor

template<typename T>

Dynamic2Dim<T>::~Dynamic2Dim()

{

for(int i = 0; i < m_iYSize; i++)

{

m_pYElem[i].~Dynamic1Dim();

}

free(m_pYBuf);

}

需要爲動態二維數組重載操作符[],其實現如下 // operator[] overload

template<typename T>

Dynamic1Dim<T>& Dynamic2Dim<T>::operator[] (int index)

{

if(index < 0) throw std::out_of_range("negative index!");

if(index > m_iYSize - 1)

EnlargeY(index + 1);

return m_pYElem[index];

}

從上我們可以知道,這裏實現的是二維數組的縱向擴大,即根據二維數組的第一下標在決定是否擴大二維數組。這裏須要注重的是返回值是一個一維動態數組,由于一維動態數組也重載了[]操作符,所以用戶可以最終得到一個指定的二維數組元素的引用(其類型爲T)。

以上就是一個動態二維數組的基本實現,說它是基本實現,我是指它可以工作,但實際使用應該注重下而幾個問題。

1.數組的動態擴張是否在我們所期望的情況下進行的。看下面的例子:Dynamic2Dim<string> arrString;

arrString[3][4] = "34";

string str = arrString[6][6];

根據動態數組的定義,可以確定動態二維數組進行了二次擴張,第一次數組空間爲4*n,這是我們期望的;第二次爲7*n,在大多數情況下這不是我們期望的。(這裏使用n是因爲二維數組的行元素數目是不同的。)

在這裏我給出一個解決的方法。可以使用代理類(proxy class)來區別上面二種情況,在第二種情況下可以抛出一個異常。

2.動態分配空間的大小。malloc須要調用操作系統的低級操作,我們不希望頻繁調用它,因此可以預先分配較大一些的空間。例如:用戶使用下標5時,我們分配5*2的空間。

3.realloc的問題。在已經分配了較大內存空間時,realloc會引起很大的開銷(它必須進行內存的拷貝以保持原有數據)。此時我們可以考慮使用malloc只分配所須的新的空間,盡管這樣有點複雜,但相比大塊的內存拷貝帶來的開銷還是值得的。

4.因爲動態二維數組操作符[]返回的是一個動態一維數組的引用,所以與普通二維數組相比,它有一些限制。Dynamic2Dim<string> dim1;

string dim2[10][10];

string *p;

p = dim2[3]; //Ok

p = dim1[3]; //Error. 因爲dim1[3]返回的是Dynamic1Dim<string>類型,而不是string類型。

5.在實際使用時,可以增加一個函數,返回當前數組的大小。可以使用inline來減小引入其帶來的開銷。

6.從二維動態對象(不是指針)數組的角度,以上代碼並不適用于指針。

我們可以通過動態數組的反例來確定動態數組應該具有哪些特性。大家都知道以下的方式是定義一個靜態數組 int iCount[10]; int iCount[10][10]; 從上面可以看出,定義了靜態數組之後,無論程序假如使這個數組,該數組在內存中所占空間的大小,位置是確定不變的。 我們可以得出結論,對于編譯器,靜態數組的大小和空間是已知的,因此編譯器可以自動爲該數組分配空間。具體情況是:假如你定義了一個全局數組,編譯器將在數據區爲你的數組分配一個空間;假如是個局部數組(比如定義在某一個局數中),編譯器爲你的數組分配一個棧(Stack)空間。 從靜態數組的討論中我們得出動態數組應具有的特性:在程序的運行中,動態數組是大小應該是可變的。因些動態組數的實現應該是基于動態的分配內存基礎上。下面看這個例子: 假設我們建立一個工廠工人的數據庫,數據庫中有多個表各代表不同的車間。每個表中保存該車間職工的信息,爲了代碼簡單,可以只讓數據庫保存職工的姓名。 下面是一個InputWorkers函數,以車間爲單位輸入全車間職工姓名,然後一次性將這些數據存入數據庫中。void InputWorkers() { int iCountOfWorkers, int iNo; …… 用戶輸入獲得車間的人數和車間號 …… string* iArray = new string[iCountOfWorkers]; …… 用戶輸入車間所有職工的信息,並存在iArray數組中 …… StoreInDatabase(iArray, iNo ); //存入數據庫 delete [] iArray; } 在程序中iArray是個string指針,並不是數組。但是數組的原理和指針是一樣的,比如p[1]是指數組p中的第二個元素,但在實際尋址中是以p+1進行的。所以我們可以這樣使用iArray[1]。 InputWorkers中的iArray根據車間的總人數來分配不同大小的空間。從這種意義上,可以認爲iArray實現了動態數組的功能。 假如iArray定義爲一個靜態數組,那麽iArray的大小是固定的,因此我們必須估計車間人數的一個上限。string iArray[100]; 靜態數組的速度是快于動態數組。因爲從理論上,棧在速度上是快于堆的。但是我們假如決定使用動態數組在是因爲節省空間的考慮。另外要注重靜態數組上限變化帶來的成本。我們必須重新設定上限以解決這個bug,然後重新編譯程序。假如你能控制程序的編譯,這沒問題。但是,你要做是的爲每一個用戶更新程序。沒有更新的用戶就可以碰到這個bug。想到這一點,你就快樂不起來。 你可能會說,我設一下大一點的上限,超出它的可能性會非常小,而且內存的浪費也不會多大。比如最多一個車間200人,最少一個車間100人,那也只浪費了100空間。現在機器的內存根本不在乎這麽一個空間浪費。是的,你可以這麽做,但是請繼續向下討論。 現在我們要將所有職工的姓名存入一個二維數組,數組的每一行表示一個車間,每行中的元素是職工的姓名。想想看,假如用靜態數組,你會浪費多空間。而且你還要爲車間數加一個上限。這個例子並不好,因爲工廠中的車間數應該是可以確定的。但是我可以換個角度說,我只要某幾個車間,也可能是所有車間,那麽你是否還堅持呢? 說了上面這些,只是少少的討論了一下動態數組可能是使用情況。現實中,尤其是大型軟件系統中動態數組的使用其實很普遍。而且在C++的各種庫中也有數組的實現的類,通過調用相應的類函數就可以對數組中的元素實現增/刪。而且也可以通過嵌套實現二維的動態。這些類或類模板使用起來很輕易。比如:CAtlArray<int> iArray; iArray[0] = 1; // 出錯,iArray中並沒有元素 iArray.Add(1); // element 2 iArray[0] = 1; // 可以,iArray中並有1個元素 iArray[0] = 1; // 出錯,iArray中並只有1個元素 看了上面,你會覺得很煩,每當數組擴大時必須通過一個函數Add。但程序員們都會習慣的,我們會想這是應該爲動態數組付出的代價。再想一想二維數組,Add動作的工作會讓你很是不爽。你會懷念靜態數組的操作方法,直接使用iArray[10] = 10,只要你定義的上限是大于是10的。而下面,我就是要討論這一種方法的實現。 首先我們希望有這樣的一維數組:CDynamic1Dim<int> m_dim; // m_dim的大小是1 然後執行下面的語句: m_dim[4] = 710; 此時m_dim的大小是5。 如何使m_dim[4] = 710在數組只有一個元素的情況下不會出錯而且增加數組的大小以使該語句成功?最爲簡單的方法是重載operator[]操作符。下面我們討論實現的細節。template<typename T> class Dynamic1Dim { public: Dynamic1Dim(); ~Dynamic1Dim(); T& operator[](int index); protected: bool EnlargeDim(int iSize); public: T* m_pBuf; int m_iSize; }; 上面定義一個模板類Dynamic1Dim<T>。其構造函數如下: //--------------------------------------------------// 構造函數 template<typename T> Dynamic1Dim<T>::Dynamic1Dim() { //數組的初始大小的1個T類型對象 //分配一塊內存其大小爲T型類所占的空間 m_pBuf = (T*)malloc(sizeof(T)); //在內存空間中建立一個T型對象 new(m_pBuf) T(); m_iSize = 1; } 在初始函數中我們設定數組的默認長度爲1。當用戶使用語句m_dim[4] = 710時,重載的操作符被調用。 //--------------------------------------------------// operator [] template<typename T> T& Dynamic1Dim<T>::operator [](int index) { // 假如下標是負值,抛出一個異常 if( index < 0 ) throw std::out_of_range(" Index shouldn\\\'\\\'t be negative"); //檢查下標是否超來數組大小,假如超過則調用EnlargeDim擴大數組 if(index > m_iSize - 1) EnlargeDim(index + 1); Return m_pBuf [index]; } //--------------------------------------------------// Enlarge template<typename T> bool Dynamic1Dim<T>::EnlargeDim(int iSize) { // 重新分配一塊內存,其大小爲擴大後T類型數組的大小 m_pBuf = (string*) realloc(m_pBuf, sizeof(T) * iSize); // 在擴大部分的內存空間上建立T類型的數組對象,並調用其默認構造函數 for(int i = m_iSize; i < iSize; i++) { new(&m_pBuf[i]) T(); } m_iSize = iSize; return true; } 上面的代碼已基本實現了動態一維數組的要求。但有一個點必須當心,就是數組空間的釋放問題。在Dynamic1Dim的析構函數中必須釋放動態分配的空間。 //--------------------------------------------------// DestrUCtor template<typename T> Dynamic1Dim<T>::~Dynamic1Dim() { // 調用T類的析構函數 for(int i = 0; i < m_iSize; i++) { m_pBuf [i].~T(); } // 釋放內存空間 free(m_pBuf); } 注重,m_pElem[i].~T()是必要的,因爲T對象中也可能有內存的分配。假如沒有這句,T對象中分配的內存就無法釋放,其實這也是很多內存泄露的原因。 上面的代碼實現了動態一維數組的模板。我們最後就要討論動態二維數組的實現。 我們會希望有這樣的二維數組:CDynamic2Dim<int> m_dim; // m_dim的大小是1*1 然後執行下面的語句: m_dim[1][3] = 33; m_dim[4][10] = 710; 此時m_dim的大小是:0、2、3行都只有一個元素,1行有4個元素,4行有11個元素。 可以這樣設想,動態二維數組是由數目不定的動態一維數組組成的。基于這種想法,我們看一下動態二維數組的實現。 template<typename T> class Dynamic2Dim { public: Dynamic2Dim(); ~Dynamic2Dim(); Dynamic1Dim<T>& operator[] (int index); protected: bool EnlargeY(int nYSize); private: int m_iYSize; Dynamic1Dim<T>* m_pYBuf; Dynamic1Dim<T> m; }; 初始的二維數組應該是1*1大小的,因此Dynamic2Dim的構造函數應該如下 // Constructor template<typename T> Dynamic2Dim<T>::Dynamic2Dim() { m_iYSize = 1; m_pYBuf = (Dynamic1Dim<T>*) malloc(sizeof(Dynamic1Dim<T>)); m_pYElem = new(m_pYBuf) Dynamic1Dim<T>(); } 在析構函數中釋放分配的內存空間: // Desctructor template<typename T> Dynamic2Dim<T>::~Dynamic2Dim() { for(int i = 0; i < m_iYSize; i++) { m_pYElem[i].~Dynamic1Dim(); } free(m_pYBuf); } 需要爲動態二維數組重載操作符[],其實現如下 // operator[] overload template<typename T> Dynamic1Dim<T>& Dynamic2Dim<T>::operator[] (int index) { if(index < 0) throw std::out_of_range("negative index!"); if(index > m_iYSize - 1) EnlargeY(index + 1); return m_pYElem[index]; } 從上我們可以知道,這裏實現的是二維數組的縱向擴大,即根據二維數組的第一下標在決定是否擴大二維數組。這裏須要注重的是返回值是一個一維動態數組,由于一維動態數組也重載了[]操作符,所以用戶可以最終得到一個指定的二維數組元素的引用(其類型爲T)。 以上就是一個動態二維數組的基本實現,說它是基本實現,我是指它可以工作,但實際使用應該注重下而幾個問題。 1.數組的動態擴張是否在我們所期望的情況下進行的。看下面的例子:Dynamic2Dim<string> arrString; arrString[3][4] = "34"; string str = arrString[6][6]; 根據動態數組的定義,可以確定動態二維數組進行了二次擴張,第一次數組空間爲4*n,這是我們期望的;第二次爲7*n,在大多數情況下這不是我們期望的。(這裏使用n是因爲二維數組的行元素數目是不同的。) 在這裏我給出一個解決的方法。可以使用代理類(proxy class)來區別上面二種情況,在第二種情況下可以抛出一個異常。 2.動態分配空間的大小。malloc須要調用操作系統的低級操作,我們不希望頻繁調用它,因此可以預先分配較大一些的空間。例如:用戶使用下標5時,我們分配5*2的空間。 3.realloc的問題。在已經分配了較大內存空間時,realloc會引起很大的開銷(它必須進行內存的拷貝以保持原有數據)。此時我們可以考慮使用malloc只分配所須的新的空間,盡管這樣有點複雜,但相比大塊的內存拷貝帶來的開銷還是值得的。 4.因爲動態二維數組操作符[]返回的是一個動態一維數組的引用,所以與普通二維數組相比,它有一些限制。Dynamic2Dim<string> dim1; string dim2[10][10]; string *p; p = dim2[3]; //Ok p = dim1[3]; //Error. 因爲dim1[3]返回的是Dynamic1Dim<string>類型,而不是string類型。 5.在實際使用時,可以增加一個函數,返回當前數組的大小。可以使用inline來減小引入其帶來的開銷。 6.從二維動態對象(不是指針)數組的角度,以上代碼並不適用于指針。
󰈣󰈤
 
 
 
>>返回首頁<<
 
 
 
 
 熱帖排行
 
 
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有