2017年9月7日 星期四

C/C++ - Vector (STL) 用法與心得完全攻略

 

Vector 是 C++ 中一個非常好用的「容器」,是加強版的陣列,對自己的一些基本資訊提供成員函式來直接存取。

記得小時候考程式檢定的時候,初學 vector,考試時就用 vector 開心解完閃人,而隔壁桌的還在用 C 慢慢刻,才初次見識到這個東西的強大,基本上寫 c++ 很建議使用 vector 取代低階的 array 和 pointer,比較易維護,容易除錯 : )

2015.7.22 初版
2017.9.7 新增部份 [用心去感覺] 段落、排版改善。




一、Vector 簡介


Vector 是 C++ 標準程式庫中的一個 class,可視為會自動擴展容量的陣列,是C++標準程式庫中的眾多容器(container)之一,以循序 (Sequential) 的方式維護變數集合,使用前預先 #include <vector> 即可。


Vector 的特色


  • 支援隨機存取
  • 集合尾端增刪元素很快 : O(1)
  • 集合中間增刪元素比較費時 : O(n)
  • 以模板(泛型)方式實現,可以儲存任意類型的變數,包括使用者自定義的資料型態。
  • 有一些容器提供 stable iterator 保證,很不幸的 vector 不保證。因此存在一些可能造成 vector iterator 失效的操作。




二、成員函式簡介


vector 類別是以容器模式為基準設計的,也就是說,基本上它有 begin(), end(), size(), max_size(), empty(), swap()  等用法。


1. 存取元素的用法


  • vec[i] - 存取索引值為 i 的元素值。
  • vec.at(i) - 存取索引值為 i 的元素的值,
  • vec.front() - 回傳 vector 第一個元素的值。
  • vec.back() - 回傳 vector 最尾元素的值。


[用心去感覺] operator[]

用 operator[] 可能會 Segmentation Fault。以 at() 存取會做陣列邊界檢查,如果存取越界將會拋出一個例外,這是與operator[]的唯一差異。撰寫較嚴肅、安全性較高的程式時使用 at()。



2. 新增或移除元素的用法


  • vec.push_back() - 新增元素至 vector 的尾端,必要時會進行記憶體配置。
  • vec.pop_back() - 刪除 vector 最尾端的元素。
  • vec.insert() - 插入一個或多個元素至 vector 內的任意位置。
  • vec.erase() - 刪除 vector 中一個或多個元素。
  • vec.clear() - 清空所有元素。


[用心去感覺] push_back() 的效率問題

少依賴 push_back() 的自動記憶體配置,不是不要用 push_back,是不要讓 push_back 自己判定記憶體需求,能自己要記憶體的就自己要,善用 reserve()、resize() 或 constructor 引數。


[用心去感覺] 迭代器範圍刪除是前閉後開 [a,b)

這個是 STL 迭代器相關函式的設計原則,區間範圍以前閉後開範圍表示,例如,用 erase() 刪除全部元素 vec.erase( vec.begin(), vec.end() ),vec.begin() 是在第一個元素, vec.end() 是最後一個元素的下一個元素。



3. 取得長度/容量的用法


  • vec.empty() - 如果 vector 內部為空,則傳回 true 值。
  • vec.size() - 取得 vector 目前持有的元素個數。
  • vec.resize() - 改變 vector 目前持有的元素個數。
  • vec.capacity() - 取得 vector 目前可容納的最大元素個數。這個方法與記憶體的配置有關,它通常只會增加,不會因為元素被刪減而隨之減少。
  • 重新配置/重設長度
  • vec.reserve() - 如有必要,可改變 vector 的容量大小(配置更多的記憶體)。在眾多的 STL 實做,容量只能增加,不可以減少。


[用心去感覺] empty() 和 size()==0

不建議使用 size()==0 判斷容器是否為空,用 empty() 判斷較恰當。因為並不是所有容器的 size() 都是 O(1),例如 <list> 是 linked list 結構,其 size() 是 O(n)。



4. 疊代 (Iterator)


  • vec.begin() - 回傳一個 iterator,它指向 vector 第一個元素。
  • vec.end() - 回傳一個 iterator,它指向 vector 最尾端元素的下一個位置(請注意:它不是最末元素)。
  • vec.rbegin() - 回傳一個反向 iterator,它指向 vector 最尾端元素的。
  • vec.rend() - 回傳一個 iterator,它指向 vector 的第一個元素。


[用心去感覺] 容量 (capacity) 和長度 (size)

每個 vector 都有兩個重要的數字:容量 (capacity) 和長度 (size) 。

  • 容量 (capacity) : 是這個 vector 擁有的空間。
  • 長度 (size) : 是實際儲存了元素的空間大小。capacity 永遠不小於 size。



reserve() 的目的是擴大容量。做完時,vector 的長度不變,capacity 只會長大不會縮小,資料所在位置可能會移動 (因為會重配空間)。因為 vector 一開始是空的,立刻預留顯然比填了資料後才預留省了拷貝資料的時間。

resize() 的目的是改變 vector 的長度。做完時,vector 的長度會改變為指定的大小,capacity 則視需要調整,確保不小於 size,資料所在位置可能會移動。如果變小就擦掉尾巴的資料,如果變大就補零。補零如果會超過容量,會做重配空間的動作。




三、常用的 vector 程式寫法



1. 尋訪


//1. 使用足標運算子 function member - at
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
for(int i=0; i<v.size(); i++) cout << v.at(i) << " ";

//2. 使用 iterator
vector<int>::iterator it_i;
for(it_i=ff.begin(); it_i!=ff.end(); ++it_i) cout << *it_i << " "; 



2. Construction and Assignment


int array[] = {0,1,2,3,4};
vector v(10,0); // {0,0,0,0,0,0,0,0,0,0}
vector v1;
vector v3(v.begin(), v.end())
v1.assign(10, 0); // v1 設 10 個 0
v1.assign(v.begin(), v.end()); // v1 複制 v
v1.assign(v.begin(), v.begin()+5); // 複製 v 前5個元素到 v1
v1.assign(array, array+5); // 複製 array 前5個元素到 v1



3. 用 C++ 的 Vector 產生動態二維陣列


vector<int> row;
row.assign(n,0);//配置一個 row 的大小
vector< vector<int> > array_2D;
array_2D.assign(n,row);//配置2維



4. 使用者自定義的資料型態


class NODE{
    public:
        char symbol;
        int  count;  
};

int main(){   
 NODE temp;
 vector<NODE> gem_list;
 
 temp.symbol = 'a';
 temp.count = 0;
 gem_list.push_back(temp);
 
 // .. 經過幾次push_back
 
 for(int i=0; i<gem_list.size(); i++)
 cout<<gem_list[i].symbol<<" "<<gem_list[i].count<<endl;
 
    return 0;
}


[用心去感覺] 優先使用 vectors 和 iterators 取代低階的 array 和 pointer

pointers 和 arrays 對於某些低階任務可能有存在的必要,但我們應該盡量避免使用它們,因為他們容易出錯又很難除錯。一般而言應該優先使用程式庫提供的抽象事物而非語言內建的 array 和 pointer,這一忠告在「多用strings,少用C-Style 字串(亦即以null結尾之字元array)」這件事上尤其合適。





References


Ping 不見路 - STL vector 效率小記
http://pingyeh.blogspot.tw/2011/09/stl-vector.html#efficiency

Wiki - Vector (STL)

PTT C_and_CPP - [問題] array, pointer V.S. vector, Iterator
技術提供:Blogger.