- 為了支持快速隨機訪問，vector將元素連續存儲，每個元素緊挨著前一個元素存儲。通常情況下，我們不必關心一個標準庫類型是如何實現的，而只需關心它如何使用。然而，對于vector和string,其部分實現滲透到了接口中。
- 假定容器中元素是連續存儲的，且容器的大小是可變的，考慮向vector或string中添加元素會發生什么：如果沒有空間容納新元素，容器不可能簡單地將它添加到內存中其他位置--因為元素必須連續存儲。容器必須分配新的內存空間來保存已有元素和新元素，將已有元素從舊位置移動到新空間中，然后添加新元素，釋放舊存儲空間。如果我們每添加一個新元素，vector就執行一次這樣的內存分配和釋放操作，性能會慢到不可接受。為了避免這種代價，標準庫實現者采用了可以減少容器空間重新分配次數的策略。當不得不獲取新的內存空間時，vector和string的實現通常會分配比新的空間需求更大的內存空間。容器預留這些空間作為備用，可用來保存更多的新元素(提前分配更大的空間)。這樣，就不需要每次添加新元素都重新分配容器的內存空間了。這種分配策略比每次添加新元素時都重新分配容器內存空間的策略要高效得多。其實際性能也表現得足夠好--雖然vector在每次重新分配內存空間時都要移動所有元素，但使用此策略后，其擴張操作通常比list和deque還要快。
管理容量的成員函數
- 如表9.10所示，vector和string類型提供了一些成員函數，允許我們與它的實現中內存分配部分互動。capacity操作告訴我們容器在不擴張內存空間的情況下可以容納多少個元素。reserve操作允許我們通知容器它應該準備保存多少個元素。
- 有當需要的內存空間超過當前容量時，reserve調用才會改變vector的容量。如果需求大小大于當前容量，reserve至少分配與需求一樣大的內存空間(可能更大)。如果需求大小小于或等于當前容量，reserve什么也不做。特別是，當需求大小小于當前容量時，容器不會退回內存空間。因此，在調用reserve之后，capacity將會大于或等于傳遞給reserve的參數。這樣，調用reserve永遠也不會減少容器占用的內存空間。類似的，resize成員函數(參見9.3.5節，第314頁)只改變容器中元素的數目，而不是容器的容量。我們同樣不能使用resize來減少容器預留的內存空間。
- 在新標準庫中，我們可以調用shrink_to_fit來要求deque、vector或string退回不需要的內存空間。此函數指出我們不再需要任何多余的內存空間。但是，具體的實現可以選擇忽略此請求。也就是說，調用shrink_to_fit也并不保證一定退回內存空間。
capacity和size
- 理解capacity和size的區別非常重要。容器的size是指它已經保存的元素的數目；而capacity則是在不分配新的內存空間的前提下它最多可以保存多少元素。下面的代碼展示了size和capacity之間的相互作用
vector<int> ivec;
//size 應該為0 capacity應該依賴于具體實現
cout << "ivec:size: " <<ivec.size()<< "capacity: " <<ivec.capacity() << endl;
//向ivec 添加24個元素
for(vector<int>::size_type ix = 0; ix != 24; ix++){ivec.push_back(ix);
}
//size 應該為24 capacity應該大于等于24 具體依賴于標準庫的實現
cout << "ivec:size: " <<ivec.size()<< "capacity: " <<ivec.capacity() << endl;
- 當在我們的系統上運行時，這段程序得到如下輸出：
- ivec:size:0 capacity:0
- ivec:size:24 capacity:32
- 我們知道一個空vector的size為0,顯然在我們的標準庫實現中一個空vector的capacity也為0。當向vector中添加元素時，我們知道size與添加的元素數目相等。而capacity至少與size一樣大，具體會分配多少額外空間則視標準庫具體實現而定。在我們的標準庫實現中，每次添加1個元素，共添加24個元素，會使capacity變為32。可以想象ivec的當前狀態如下圖所示：
- 現在可以預先分配一些額外的空間
- ivec.reserve(50);//將capacity的容量設置至少為50 可能會更大
- size的大小應該為24，capacity的大小應該大于等于50 具體依賴于標準庫的實現
- 添加元素用光預留空間 while(ivec.size() != ivec.capacity()){ ivec.push_back(0);}
- 只要使用的空間沒有超過vector的容量，就不需要為此重新分配空間
- 使用shrink_to_fit將vector超出當前大小的多余內存空間退回給系統
- ivec.shrink_to_fit(); 要求歸還內存。這僅僅是一個請求，是否歸還并無保證
- 每個vector實現都可以選擇自己的內存分配策略。但是必須遵守的一條原則 ，是 ：只有當迫不得已時才可以分配新的內存空間
- 只有在執行insert操作時size與capacity相等，或者調用resize或reserve時給定的大小超過當前capacity,vector才可能重新分配內存空間。會分配多少超過給定容量的額外空間，取決于具體實現。
- 雖然不同的實現可以采用不同的分配策略，但所有實現都應遵循一個原則：確保用push_back向vector添加元素的操作有高效率。從技術角度說，就是通過在一個初始為空的vector上調用n次push_back來創建一個n個元素的vector,所花費的時間不能超過n的常數倍
