(C++) 別再用dynamic array與pointer了! 趕快學STL的vector與iterator！

(一) 廢話

別再用array與pointer?那我不是在自打上一篇的嘴巴嗎? 其實並不衝突。因為在C之下，pointer還是非常重要的，本篇所著重的是C++。

不知道大家在學C++時，老師或書中有沒有教或學到STL(Standard Template Library)呢? STL是C++下非常非常好用的函式庫，他提供了非常多Template形式的"容器"，讓開發上省去不少麻煩，且使得C++與C之間相去越遠，兩者已經儼然是不同的語言了!(Jserv 大師也曾說過 - 自 1999 年制訂的 C99 規格開始，C 語言和 C++ 程式語言就分道揚鑣，換言之「C++ 是 C 語言的超集 (super-set)」不再成立。)

(二)前言

C++之父-Bjarne Stroustrup曾說過, "you should use vector over Array unless you have a really good reason to use an array"。因為記憶體的管理永遠是開發者的痛，在現今的程式開發中最好能避免使用new，因為這會使我們必須持續的追蹤其大小且須手動刪除釋放。尤其是在re-size array時，vector會更加好用。

當然不諱言的是，dynamic array的速度還是優於vector的，只是那是只在極端講求速度的class 的內部實作中才使用。

(三) Vector與Iterator是何物?

Vector 是 C++中STL容器(container)中其中一個 template class，他在宣告後就可以使用。只需要一直進行新增資料，而不用在乎其大小，亦可視為會自動擴展容量(capacity)的陣列，所以只要一直塞一直塞一直塞就可以了XD。是C++標準程式庫中的眾多容器（container）之一。

Iterator有時又稱cursor，是一種在很多程式語言中都有的interface，主要功能就是讓工程師可以無需關心memory分配而在各種container中進行尋訪。C++雖然本身不具此功能，但在STL中對於此進行了實作。會綁定所指向的容器。因此Iterator可以視為容器(在這就是用於vector)的指標的概念，因此亦可以直接做+n表示向後位移n個元素。

使用前都必須先載入  #include <vector>

(四) 名詞介紹

在開始使用vector之前，有幾個很重要的名詞要先解釋介紹，分別是：

size：表示目前該vector所擁有的元素個數。

capacity：表示vector目前可容納的最大元素個數。這個方法與記憶體的配置有關，它通常只會增加，不會因為元素被刪減而隨之減少。

大概就是長下面這：(是不是覺得很像別的blog的圖呢?沒辦法因為就長這樣QQ)

(五) 開始使用

(1) 宣告與一些基本：

// T 可以放任何資料型態甚至是使用者自定類別(user-defined class)。
// 下面為三種較常用的宣告方式
vector<T> vec;
vector<T> vec(n);          // 初始size= n 的vector，並且填滿0或\0
vector<T> vec(arr, arr+n); // 可以將一T*類別陣列賦予給vector
vector<T> vec(count, val); // 將vec做初始化，將size = count，且塞滿元素val。

// 要使用iterator前必須要在前面加上要指定的scope resolution operator(::)
vector<T>::iterator iter;
iter = vec.begin();     // 將vector的第零個元素位址綁定給iterator，之後就可以直接存取值了!

vec.size();             // 回傳擁有的元素個數。
vec.capacity();         // 回傳最大可擁有的元素個數，此值只會越來越大不會變小。
vec.empty();            // 若為空，回傳true。
vec.begin();            // 回傳的vector的第零個元素的iterator。
vec.end();              // 回傳的vector的第最後一個元素的iterator。

(2) 元素的存取：

vec[i];         \\ 如同一般array樣，存取index為i的元素。少用。
vec.at(i);      \\ vector本身的方法，存取時會做邊界檢查(檢查size)，如果超過邊界會拋出一個例外，這是和[]的差別。
vec.front();    \\ 回傳 vector 第一個元素值(同 vec.at(0))。
vec.back();     \\ 回傳 vector 最尾端元素值(同 vec.at(vec.size()-1) )。

*(iter+i);      \\ 利用iterator進行第i個元素存取，就如同pointer一樣加個*即可使用。

注意!千萬不要用vec[i]與vec.at(i)進行元素新增，因為雙方都不會改變size值，只能對已存在的元素進行修改!!!!(前者不會報錯，後者會報錯)，要進行元素新增請用下面的方法。

(3) 元素的增刪：

vec.push_back(n);               \\ 核心函式。將元素n塞至vector的尾端並size+1。若size超過capacity時會再進行記憶體配置。
vec.pop_back();                 \\ 刪除vector最尾端的元素，size會-1。很像stack的pop。
vec.insert(iterator pos, n);    \\ 將元素n插入至vector內pos的位置之後。

// 以下的動作都會調整size大小，畢竟size代表的就是元素個數
vec.erase(iterator pos);        \\ 刪除 vector 中位置pos的元素。
vec.erase(iterator first, iterator last); \\ 刪除 vector 中位置first~last-1的元素。
vec.clear();                    \\ 清空所有元素。

(4) 容器的大小管理：

vec.reserve(n);        \\ 改變vector整體的最大容量(capacity)為n，且n必須大於capacity，也就是只能變大，否則不會做事。類似realloc。
vec.resize(n);         \\ 改變vector的擁有元素數(size)成n。size變少時多的元素會被移除；變多時則是補0(或\0)。類似calloc。

注意以上兩種改變的是不同的東西。且若resize的大小大於原本的capacity，vector也會跟著重新分配記憶體唷。
另外，雖然push_back()真的很好用，但畢竟一直使用會造成過多的記憶體重新配置， 因此可以的話還是最好都是先使用reserve()進行空間配置再push_back()，超過前再重新reserve()，可以減少過多的重新配置與記憶體浪費。

(5) 容器的通用函式：

vec.swap(tmp);         \\ tmp和vec為相同類別的vector。此方法可以將兩個長度不同的vector做內容交換。

(六) 光說不練假把戲，看看例題最實際

看完那麼多廢話以後，直接實際看與pointer比較的例子吧!

int n = 5;
// (0) 宣告與給值 

// 使用vector與iterator 
vector<int> vec;
vec.reserve(n);
vector<int>::iterator iter = vec.begin();

// 使用new與pointer
int *ptr = new int [n];

// 先都塞值給兩邊，這邊請勿對vec直接使用[]或at存值
for(int i=0; i<n; i++)
{
   vec.push_back(i*i);
   ptr[i] = i*i;   
} 

// (1) 印出資料 (不討論使用[]operator) 
// Iterator: 兩種方法 分別是:
// (a) 使用iterator做迴圈，宣告時長得比較醜， 
cout <<" Iterator:" << endl;
for(vector<int>::iterator i = iter; i<vec.end(); i++)
   cout << *i << " ";
cout << endl;

// (b) 使用索引做迴圈，這方法和pointer相似 
for(int i=0; i<vec.size(); i++)
   cout << *(iter+i) << " ";
cout << endl;

// Pointer:
cout <<" Pointer:" << endl;
for(int i=0; i<n; i++) 
   cout << *(ptr+i) << " ";
cout << endl;

// (2) 對容器/動態陣列 重新分配大小 
//  Iterator: 
vec.reserve(vec.size() + n);
cout << "vec capacity = " << vec.capacity() << endl ;  // vec capacity = 10

// Pointer:  mess and mess，而且dynamic array的大小不能直接取得=~= 
int* tmp = new int[n+n];
for(int i=0; i<n; i++)
 tmp[i] = ptr[i];
delete ptr;
ptr = tmp; 

以上就是最簡單的例子了，希望讀者看到這邊還能懂以上在幹嘛XD

(六) 那麼...怎麼釋放記憶體呢?(free memory of vector)

當我們對一個vector使用clear()之後，他會清空所有該vector中的元素；同時若元素為物件時也會逐一執行deconstructor()，並且讓size()歸零，然而該記憶體還是存在的，並不會因此被回收掉。使用dynamic array時可以使用delete進行記憶體刪除，那麼vector有delete嗎?很遺憾的是沒有，同時也沒有專用的函式會進行記憶體釋出，因此必須透過宣告一個空vector，將其與要刪除的vector進行swap交換，就能做記憶體刪除摟!

vec.clear();
vector().swap(vec);

另外reserve()雖然可以釋放memory，但僅限於增加capacity時對原先的vector釋放，因此即使使用vec.reserve(0)，仍然不等於釋放memory唷。

(七) 那二維vector?

// 一般二維array
int arr[3][2] = {1, 2, 3, 4, 5, 6};
// 動態二維vector -> 給予vec初始值為 3個"長度為2的int vector(並給初值為0)"
vector<vector<int> > vec(3, vector<int>(2));
// do whatever you want like array;
for(int i=0; i<3; i++)
    for(int j=0; j<2; j++)
        (vec.at(i)).at(j) = arr[i][j];    // vec.at(i).at(j)同vec[i][j]

注意!!!!因為">>"是關鍵operator，因此宣告時兩個">"之間，一定要有空格!

另外vec在第二維宣告時，因為使用constructor，初始都塞滿了0，因此等於整個vec是預先分配好記憶體空間的，所以才可以直接用at()進行資料存取而不用push_back()。

若好想使用push_back，可以參考以下：

// 一般二維array
int arr[3][2] = {1, 2, 3, 4, 5, 6};
// 乾淨的二維vector
vector<vector<int> > vec;
for(int i=0; i<3; i++)
{
    vector<int> row;
    for(int j=0; j<2; j++)
        row.push_back(arr[i][j]);
    vec.push_back(row);
}

(八) 使用時的其他建議與注意事項：

(1) 少依賴直接使用push.back()去增加記憶體：

push_back()確實是vector的賣點，但建議還是不要依賴他自動配置記憶體的功能，因為push_back()在發現capacity不夠時，會將該vector記憶體做雙倍大小重新配置，因此若重新分配太多次後，會導致記憶體過度浪費與過多不必要的記憶體重新配置，因此若能知道要用多少的記憶體，或最多會用多少時，還是建議直接先使用reserve(n)進行記憶體配置。

(2) 少用operator[]去做存取：

因為operator[]不會進行邊界檢查，若程式過於龐大，出錯時會很難找出錯誤，建議還是使用at(i)。

(3) 少用resize()，改用reserve()：

先resize()後會先填0進去，用reserve()再push_back()元素進去會更好，且超過resize大小超過capacity時，記憶體會先雙倍配置，若用不到那麼多記憶體的話會過度浪費。

(九) 寫在最後

剛學習並接觸到vector的人可能會覺得很麻煩，但多多使用就能逐漸上手並覺得方便了，尤其是在Stack Overflow上或是業界上，在C++很多都直接使用vector代替array了，在C++ Primer 4/e中也提到盡量不要用到array 和pointer。我也是因為在業界的學長學長問我相關問題後我才真正去學習使用vector，並寫將其寫下來做為筆記，作為一份學習心得，同時可以釐清很多觀念。不過還是不要因此放棄學習pointer與array，畢竟對於c而言還是非常重要的。

若以上我有任何寫錯的地方還請多多指教!