2011年9月29日

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,必要時也可以把這個異常接住來處理。


7 則留言 :

  1. Exceptional C++ Style也有探討reserve()跟resize()意義上微妙的不同,不過我看過這篇又更清楚了!

    回覆刪除
  2. 真是佛心來的...
    感恩

    回覆刪除
  3. resize()出來的東西會是用copy constructor產生的物件喔

    回覆刪除
    回覆
    1. 對啊,我寫的是〔配置新空間、拷資料、歸還舊空間、更新陣列位置〕整個程序走一遍,應該沒寫錯吧?

      刪除