先說vector吧。

C++ Vector（向量容器）

是一個線性順序結構。相當于數組，但其大小可以不預先指定，并且自動擴展。它可以像數組一樣被操作，由于它的特性我們完全可以將vector 看作動態數組。

vector 的數據安排以及操作方式，與 array 非常像似。兩者的唯一差別在于空間的運用彈性。array是靜態空間，一旦配置了就不能改變；要換個大（或小）一點的房子，可以，一切細瑣得由客端自己來：首先配置一塊新空間，然后將元素從舊址一一搬往新址，然后再把原來的空間釋還給系統。vector 是動態空間，隨著元素的加入，它的內部機制會自行擴充空間以容納新元素。因此，vector 的運用對于內存的樽節與運用彈性有很大的幫助，我們再也不必因為害怕空間不足而一開始就要求一個大塊頭 array 了，我們可以安心使用vector，吃多少用多少。

vector 的實作技術，關鍵在于其對大小的控制以及重新配置時的數據搬移效率。一旦 vector 舊有空間滿載，如果客端每新增一個元素，vector 內部只是擴充元素的空間，實為不智，因為所謂擴充空間（不論多大），在創建一個vector 后，它會自動在內存中分配一塊連續的內存空間進行數據存儲，初始的空間大小可以預先指定也可以由vector 默認指定，這個大小即capacity （）函數的返回值。當存儲的數據超過分配的空間時vector 會重新分配一塊內存塊，但這樣的分配是很耗時的，在重新分配空間時它會做這樣的動作：

首先，vector 會申請