C++中的堆與棧

轉自：http://blog.csdn.net/mitedu/article/details/3430332

1 基本概念

也不知道是什麼原因，很多人總是把堆和棧混合一起，在寫程式時，總是經常脫口而出地說堆棧。網上的一些資料說堆棧的叫法是有曆史原因的，至于具體是什麼曆史原因，這不是本文所要讨論的問題。

堆：在資料結構中，堆是一種滿足“堆性質”（至于什麼是堆性質可以查閱任何一本資料結構的書）的資料結構。然而，通常我們所指的堆都是指二叉堆，即一種使用數組來模拟完全二叉樹的結構。當然，也存在其它形式的堆，包括斐波拉契堆、二項堆、楊氏表等，想獲得有關這些特殊堆的性質可以查閱算法導論。然而，在編譯器中，堆是一個存儲區，通常用于動态配置設定存儲空間，一般堆具有不連續性（在下文中将講到堆的不連續性）。

棧：在資料結構中，棧是一種按照資料項先進後出的順序排列的資料結構，我們隻能在棧頂來對棧中的資料項進行操作。然而在編譯器中，棧通常是用來為函數中的臨時變量配置設定存儲空間，通常棧空間的配置設定具有連續性。

2 相關知識

通常一個由C++編譯的程式占用的記憶體分為以下五個部分（這些知識對了解下文至關重要，這些是對一個基本的C++程式的存儲方式的認識）：

1）棧區（stack）

是由編譯器自動配置設定釋放，存放函數的參數值，局部變量的值等。其操作方式類似于資料結構中的棧。

2）堆區（heap）

一般由程式員配置設定釋放，若程式員不釋放，程式結束時可能由作業系統回收（如果回收的不及時有可能會造成記憶體洩露）。堆空間的配置設定方式類似于資料結構中的連結清單。

3）全局區（靜态區）（static）

全局變量和靜态變量的存儲是放在一塊的，初始化的全局變量和靜态變量在一塊區域，未初始化的全局變量和未初始化的靜态變量在相鄰的另一塊區域。在程式結束後由系統釋放。

4）文字常量區

用于存放常量資料，程式結束後由系統釋放。

5）程式代碼區

存放函數體的二進制代碼。

3 堆和棧的差別

在IT面試中，通常有人會問哪個變量是堆變量，哪個變量又是棧變量，作業系統中的棧是向上（從低位址向高位址的方向）申請空間還是向下申請空間等等問題。我想隻要掌握了堆和棧的差別，以及它們的工作原理，這些問題都會迎刃而解。本節将分以下幾個方面來講述它們之間的差别。

3.1 存儲對象的不同

這個問題其實在第2節已經初步提到，在本小節中再次詳細說明一下，因為這對下文的了解至關重要。

3.1.1堆區的存儲對象

主要存儲動态申請的空間。在C++中，存儲“new出來”的對象，如下程式段

int *a;

a = new int;

*a = 1;

那麼，變量a存儲的值為1，1的存儲位址在堆區，即指針a所指向的那個對象的存儲位址是在堆區，但是要注意的是指針a本身所存儲的區域是在棧區（嘿嘿，暈乎了把，可以看以下例子）。

Exp01:

#include <iostream.h>

int main ()

{

       int *a;

       a = new int;

       *a = 1;

       cout << "指針a所指向對象的位址為：" << a << endl;

       cout << "存儲指針a本身的位址為：" << &a << endl;

       return 0;

}

Exp01的輸出結果如下：

指針a所指向對象的位址(堆區位址)為：0x00371100

存儲指針a本身的位址(棧區位址)為：0x0012FF7C

3.1.2 棧區的存儲對象

主要存儲程式中的臨時變量，這些臨時變量包括函數的參數變量、函數内的臨時變量、指針變量（指的是指針本身）、數組變量等。注意：全局變量和靜态變量不在棧區，它們是放在全局區。

3.2 存儲空間的配置設定方式

3.2.1 堆區的空間配置設定方式

堆區的空間配置設定是由程式管理，而不是由系統管理。堆空間通常是由程式動态申請的。通常作業系統中有一個記錄空閑記憶體位址的連結清單，當系統收到程式的申請時，會周遊該連結清單，根據某種記憶體管理算法，尋找一個空間大于所申請空間的堆結點，然後将該結點從空閑結點連結清單中删除，并将該結點的空間配置設定給程式。對于這種申請方式，需要在程式中使用delete語句釋放空間，否則容易導緻記憶體洩露。

堆空間的配置設定一般都是向高位址擴充，并且具有不連續性。這是由于系統是用連結清單來管理空閑記憶體位址的，當然也就不連續了，而系統中連結清單的周遊方向通常是由低位址向高位址周遊。我們可以通過以下例子可以看到，

Exp02:

#include <iostream.h>

int main ()

{

       int *a,*b,*c;

       a = new int;

       b = new int;

       c = new int;

       cout << a << "       " << b << "     " << c << endl;

       return 0;

}

Exp02的輸出結果：

0x00371100      0x00371138      0x00371170

由前文我們可以知道*a,*b,*c均為堆變量（注意指針本身為棧變量），再由輸出結果我們可以看到，a的位址小于b，b小于c，并且a,b,c之間的差不是4，而是內插補點較大，由此可以說明堆配置設定的特點是向高位址擴充的、不連續的。

3.2.2 棧區的空間配置設定方式

棧通常是由系統自動配置設定空間的。隻要系統剩餘的空間大于程式所申請的空間，那麼空間申請操作一般都會成功，否則就會出現緩沖棧溢出的錯誤。Windows系統中C++編譯器的棧區空間的配置設定有以下一些性質：

1）  在Windows系統中，棧空間的配置設定是從高位址向低位址擴充的，并且棧空間的配置設定一般

具有連續性，棧頂的位址和棧的最大容量是由系統預先規定。可以通過以下例子來檢視這一性質。

Exp03:

#include <iostream.h>

int main ()

{

       //a,b,c均為臨時變量，即為棧變量，由系統自動配置設定空間

       int a;

       int b;

       int c;

       cout << &a << "    " << &b << "  " << &c << endl;

       return 0;

}

Exp03的輸出結果為：

0x0012FF7C      0x0012FF78      0x0012FF74

顯然，a的位址大于b和c的位址，并且a,b,c的位址間隔均為4個位元組，這可以說明2個問題：1 棧空間的配置設定是由高位址向低位址擴充的；2 棧空間的配置設定一般具有連續性（即相鄰變量之間的位址是不間斷的，我做了多次實驗，均證明了這點，不過仍然不能代表正确，是以隻能說一般具有連續性）。

2）C++中函數參數的空間配置設定

函數參數的位址配置設定是根據參數清單中，從左到右的方向來配置設定的。我們根據下面這個例子來分析：

Exp04:

#include <iostream.h>

int p(int a, int b, int *h)

{

       int c,d;

       a = 1;

       cout << &a << "    " << &b  << "       " << &h << "  " << &c << "  " << &d << endl;

       return a;

}

int main ()

{

       int a;

       cout << "變量a的位址：" << &a << endl;

       int *h;

       cout << "指針變量h的位址：" << &h << endl;

       a = p(2,3,h);

       h = new int;

       a = p(2,3,h);

       a = q(a);

       int *q;

       q = new int;

       cout << &p << "    " << &q << "  " << endl;

       cout << "堆變量位址：" << h << "     " << q << endl;

       return 0;

}

Exp04的輸出結果為：

變量a的位址：0x0012FF7C

指針變量h的位址：0x0012FF78

0x0012FF14      0x0012FF18      0x0012FF1C      0x0012FF08      0x0012FF04

0x0012FF14      0x0012FF18      0x0012FF1C      0x0012FF08      0x0012FF04

0x00401028      0x0012FF74

堆變量位址：0x00371280  0x003712B8

由上面的輸出結果我們可以得到以下結論：

1）進一步證明棧區的配置設定位址方式是由高位址向低位址擴充（根據主函數中變量a的位址大于指針變量h的位址）；

2）函數參數變量的位址配置設定是由右向左的方式進行的（根據函數p中參數變量a的位址小于參數變量b的位址，參數變量b的位址小于指針參數變量h的位址，此處還發現了一個現象就是：臨時變量c的位址比參數變量a的位址小了12個位元組，那麼編譯器需要這12個位元組是做什麼用的呢？莫非是用于儲存斷點等資訊，這些東西我們不得而知）；

3）函數指針存儲在另外一個區域（由函數指針p的位址為0x00401028，我們可以知道，它并不是存儲在一般的棧區，因為根據輸出結果，棧區的位址一般都是0x0012FFxx左右，也不是存儲在一般的堆區，因為根據輸出結果，堆區的位址一般為0x003712xx左右，那到底編譯器是如何給函數指針配置設定空間的呢？是另外開一塊區域嗎？這些問題我們也不得而知，不過我個人認為函數指針仍然是存儲在一個“特殊的棧區”，這一點下文會有一個說明）；

4）函數變量申請空間的順序為：按照先參數變量，後函數内的臨時變量的順序來申請空間（由函數p中臨時變量c的位址小于參數a的位址）；

5）一個函數在調用結束後，所有的臨時變量都會由系統釋放，并且再次調用該函數時，仍然是從第一次調用的位址開始配置設定空間，這也說明了棧空間是由系統管理的，而不必程式員手工釋放（這一點可以由2次調用函數p的輸出結果一樣來說明）。

3.3 存儲空間的回收方式

1）堆空間的回收方式

堆空間通常需要使用free, delete等函數來釋放，系統本身不會對堆空間進行回收。

2）棧空間的回收方式

棧空間通常是在程式結束時由系統回收，或者在函數調用完畢後，由系統自動回收。

3.4 存儲空間的配置設定效率

棧由系統自動配置設定，速度較快，但程式員是無法控制的。堆是由new配置設定的記憶體，一般速度比較慢，而且容易産生記憶體碎片。這也解釋了在寫ACM程式時，使用靜态數組要比動态數組的速度要快。

4 關于函數指針變量的存儲問題

在第3節中，我們不能确定函數指針的存儲位置，下面我們通過下面一個執行個體來說明我的觀點：

Exp05:

#include <iostream.h>

int p()

{     return 0;  }

int q()

{     return 0;  }

int o()

{     return 0;  }

void f()

{}

void g()

{}

void h()

{}

int main ()

{

       p();

       q();

       o();

       f();

       g();

       h();

       cout << &p << endl;

       p();

       cout << &p << endl;

       cout << &q << endl;

       cout << &o << endl;

       cout << &f << endl;

       cout << &g << endl;

       cout << &h << endl;

       return 0;

}

Exp05的輸出結果為：

0x00401019

0x00401019

0x00401014

0x00401037

0x00401023

0x0040101E

0x00401032

由輸出結果，我們可以知道，函數指針的存儲不具有連續性，但也不像堆區域那樣有很大的間隔（各個函數指針的位址都相差不大）。我的觀點是：編譯器會專門開一塊連續的記憶體區域來函數指針，然後通過某種hash算法來找到相應的函數，其空間的釋放和申請也是由系統來管理。函數指針不會像堆那樣，動态申請記憶體空間，因為我們在寫程式時，是不需要為函數指針申請空間，也不需要為函數指針釋放空間，是以這一點跟棧類似，但也它也不像棧，滿足向低位址擴充、位址連續等特性。雖然它不是棧，但跟棧有很多共同點，是以可以認為，函數指針是存儲在一個“特殊的棧區”。

5 附錄

1）記憶體洩露

在計算機科學中，記憶體洩漏指由于疏忽或錯誤造成程式未能釋放已經不再使用的記憶體的情況。記憶體洩漏并非指記憶體在實體上的消失，而是應用程式配置設定某段記憶體後，由于設計錯誤，失去了對該段記憶體的控制，因而造成了記憶體的浪費。

2）  緩沖棧溢出

指程式中棧所申請的空間大于系統剩餘的空間時就會發生緩沖棧溢出的錯誤。

一點說明：寫這篇文章主要是出于學習的目的，以便以後能夠牢牢記住堆與棧的差別。這也是今天和實驗室的陳老師在讨論項目中的記憶體洩露問題所談到的，由此有感而發，寫下此文，供以後參考。

鳴謝：廣州聚晖電子科技有限公司

         百度百科

         騰訊QQ空間

Hint: 寫鳴謝也是學一個同學的，因為在現實中，你完成任何事情一般都需要得到别人的幫助，在寫論文的時候不也有個acknowledge嗎。