STL vector 效率小記

懶人看結論。

用 C++ 寫程式，會用到 vector 來儲存陣列。用過的人都知道，用法大約是

vector<string> foo;
foo.push_back("Hello");
foo.push_back("World");

要拿單筆資料時，可以用 foo[1] 拿到 string("World")。要 loop 過全部資料時，寫

for (vector<string>::iterator it = foo.begin(); it != foo.end(); ++it) {
  //  *it 是字串資料
}

如果只要讀資料不改資料，可以用 const_iterator 代替 iterator。

用 push_back() 新增資料的一個特性是：如果 vector 的容量不夠，會自動配置新的記憶體空間（預設是兩倍大）、把資料拷過去，再把新資料寫入。

記憶體配置是很耗時的，能免則免。如果事先不知道所需的儲存量，這樣依需要配空間做是維持 vector 用 O(1) 時間取得資料、又不會浪費太多空間的好方法。可是如果事先知道要存 65 筆資料，還反覆去要 4、8、16、32、64 筆的空間，最後又用 128 筆的空間來存 65 筆，既浪費時間、又浪費空間！

所以 vector class 提供了三種指定長度的方法：reserve()、resize() 和 constructor 引數：

vector<string> a;  // 長度為 0
a.reserve(65);  // 預留 65 個元素的位置，沒有初始化
vector<string> b;  // 長度為 0
b.resize(65);  // 預留 65 個元素的位置，呼叫 string 的 default constructor
vector<string> c(65);  // 長度為 65

用在空的 vector 上，對慣 C 的人來說，reserve() 類似 malloc()，resize() 類似 calloc()。如果是在 constructor 給長度就有點像 char* c[65]; 這樣的陣列宣告。不過 C++ 和 C 還是不一樣，這邊的主要差異是物件，和物件的 default constructor、assignment operator 的行為，對效率有些影響。

先講講這三種做法的原理。

預留 reserve()

每個 vector 都有兩個重要的數字：容量（capacity）和長度（size）。容量是這個 vector 擁有的空間，長度是實際儲存了元素的空間大小，其值等於陣列的終點減起點。capacity 不小於 size 是個不變條件。

reserve() 的目的是擴大容量，做完時，vector 的長度不變，capacity 只會長大不會縮小，資料所在位置可能會移動。

reserve(N) 的做法很簡單：

1. 如果 N <= 容量，不做事結束。
2. 配置大小為 N 的空間，
   
3. 把資料拷過去，
   
4. 歸還原來的儲存空間，
   
5. 更新陣列的起點、終點、容量。

因為 vector 一開始是空的，立刻預留顯然比填了資料後才預留省了拷資料的時間。

調整長度 resize()

調整長度目的是改變 vector 的長度，如果變小就擦掉尾巴的資料，如果變大就補零。更精確一點說，擦尾時會呼叫元素物件的 destructor，補零是補元素類型的 default constructor 產生的物件。補零如果會超過容量，會先預留空間，就是上面說的〔配置新空間、拷資料、歸還舊空間、更新陣列位置〕整個程序走一遍。

resize() 結束時，vector 的長度會改變為指定的大小，capacity 則視需要調整，確保不小於 size，資料所在位置可能會移動。

resize() 除了新長度 N 之外，還可以接受第二個引數，就是新元素的值，如果沒給就會用 default constructor 生一個來用。

在 constructor 指定長度

在 constructor 指定長度 N 的結果是一個容量和長度均為 N 的 vector，因為長度為 N，代表 N 個元素有資料，這資料就是元素類型的 default constructor 生出來的，或是用 vector constructor 的第二個引數給的物件。

這個 constructor 的做法也很簡單：

1. 配置大小為 N 的空間，
   
2. 設定陣列的起點、終點、容量，
   
3. 把相同的值填入 N 個元素的位置。

效率

使用 vector 要注意的效率問題大致有兩點：

1. 不做不必要的記憶體重配置：少依賴 push_back() 的自動記憶體配置，能自己要記憶體的就自己要，善用 reserve()、resize() 或 constructor 引數。
   
2. 不做不必要的物件拷貝。比方說，要延長或建立一個 vector、但各個元素的值不同，不要用會填值的 resize() 或 constructor 引數，而是用 reserve() 再把物件一個一個 push_back() 進去。另外要注意的是，reserve() 要來的空間切不可用 operator[] 填值，除非元素是 POD。見下節。
   

少用 operator[]

既然寫了 vector，順便提一下 operator[]。一旦有個 vector<string> foo，可能會想用

foo[3] = "movie";

這種寫法，但要小心，這可能會 Segmentation Fault！

• 第一，operator[] 不做邊界檢查，foo vector 的容量可能不到 4，foo[3] 就越界了。
  
• 第二，foo vector 就算容量夠，但長度可能不到 4，foo[3] 是未初始化的記憶體，拿來當成 string 物件，就爆了，更不用說還要呼叫它的 assignment operator。但如果元素類別是 int、double、pointer 這類 POD（Plain Old Data），assignment 是用 memory copy 實作的，倒是不會出問題。

如果確定 vector 的各個位置都有物件了，但不確定 index 會不會越界（也許 index 是別人傳來的），除了自己檢查邊界外，也可以考慮用 at() 方法：

string that = foo.at(an_index);
foo.at(an_index) = "movie";

at() 會做邊界檢查，越界時會丟出 out_of_range 異常，比較容易 debug，必要時也可以把這個異常接住來處理。