C++ std :: vector如何工作？

Question

添加和刪除元素如何「重新調整」數據？如何計算矢量的大小（我相信它保持跟蹤）？任何其他額外的資源瞭解矢量將不勝感激。

Answer 1

在上漿的方面，有興趣的兩個值用於std::vector：size，和capacity（經由.size().capacity()和訪問）。

.size()是向量中包含的元素的數量，而.capacity()是在重新分配內存之前可添加到向量的元素的數量。

如果你的元素是.push_back()，大小會增加1，直到達到容量。一旦達到容量，大多數（全部？）實現，重新分配內存，容量翻倍。

您可以使用.reserve保留容量。例如：

的存儲器

std::vector<int> A; 
A.reserve(1);  // A: size:0, capacity:1 {[],x} 
A.push_back(0);  // A: size:1, capacity:1 {[0]} 
A.push_back(1);  // A: size:2, capacity:2 {[0,1]} 
A.push_back(2);  // A: size:3, capacity:4 {[0,1,2],x} 
A.push_back(3);  // A: size:4, capacity:4 {[0,1,2,3]} 
A.push_back(4);  // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x} 

的重新分配將發生在線路4,5，和7

Answer 2

我在C++一年前寫了一個向量。它是一個具有一定大小（例如16個字符）的數組，在需要時會擴展該數量。也就是說，如果默認大小爲16個字符，並且您需要存儲Hi my name is Bobby，那麼它將數組的大小加倍爲32個字符，然後將char數組存儲在那裏。

Answer 3

的載體通常具有三個指針。如果矢量從未被使用過，它們都是0或NULL。

• 一個向量的第一個元素。 （這是開始（）迭代）
• 一到的最後一個元素的矢量+ 1（這是結束（）迭代）
• 還有一到最後分配但未被使用的元件+ 1（這個減去開始（）是容量）

當插入一個元素，向量分配一些存儲和設置其指針。它可能分配1個元素，或者可能分配4個元素。或50.

然後它插入元素並遞增最後一個元素指針。

當你插入更多的元素比分配向量必須獲得更多的內存。它出去並得到一些。如果內存位置發生變化，則必須將所有元素複製到新空間並釋放舊空間。

調整大小的常見選擇是在每次需要更多內存時將分配加倍。

Answer 4

std::vector的實現在C++ 0x和稍後引入移動語義（請參見What are move semantics?作爲簡介）稍作修改。

當將一個元素增加到一個std::vector這已經是滿的，則該vector被調整大小，其包括分配一個新的，更大的存儲器區域中，現有的數據移動到新vector，刪除舊vector空間的過程，然後添加新元素。

std::vector是標準模板庫中的集合類。將對象放入vector中，將其取出或在將項目添加到完整的vector時執行調整大小都要求對象的類支持賦值運算符，複製構造函數和移動語義。 （參見type requirements for std::vector以及std::vector works with classes that are not default constructible?聯繫）想std::vector

的一種方式是爲C樣式指定的類型的連續元素array當vector被定義，有一些額外的功能將其集成到標準模板庫產品。將vector與標準array分開的是vector將隨着項目的添加而動態增長。 （有關分歧一些討論見std::vector and c-style arrays以及When would you use an array rather than a vector/string?。）

使用std::vector允許使用其他標準模板庫組件，如算法，所以使用std::vector了一個C風格array帶有相當多的優點，當你到使用已經存在的功能。

如果提前知道最大值，您可以指定初始大小。 （請參閱Set both elements and initial capacity of std::vector以及Choice between vector::resize() and vector::reserve()）

std::vector的基本知識物理表示形式是一組使用從堆中分配的內存的指針集。這些指針允許用於訪問存儲在所述vector的元素，從vector刪除元素，遍歷vector，確定元件的數量，來確定其大小的實際操作等

由於物理表示是連續存儲器，刪除項目可能導致移動剩餘項目以關閉由刪除操作創建的任何漏洞。

使用現代C++移動語義，std::vector的開銷已經減少，因此它通常是默認的容器，可用於大多數應用程序，正如Bjarne Stroustrup在他的書「The C++ Programming Language 4th Edition」 +11。