無痛入手 C++：基礎教學8 - vector

待解決的問題

了解了前面文章的內容後，已經可以使用程式解決一些基本的問題了。但目前為止能夠解決的問題有兩個很大的侷限:

1. 無法一次宣告多個變數
舉例來說，使用者依序輸入了 n 個數字，並且希望用相反的順序將所有的數字印出來的話，這時候就會需要「一個一個」宣告 n 個變數，因為需要用變數記住所有輸入的數字，才有辦法用相反的順序印出來。以下為 n = 3 的範例程式:

int x, y, z;
cin >> x >> y >> z;
cout << z << ' ' << y << ' ' << x <<; 

這有一個顯而易見的問題，假如使用者想輸入一百個數字，難道要宣告一百個變數嗎? 顯然是不可行的。

2. 需要事先知道資料的數量。
接續上述的例子，我們在寫程式的時候，需要知道 n 的值為多少，才有辦法宣告對應數量的變數。這樣的問題也很明顯，大部分的程式在寫的時候根本不知道資料的數量會有多少。

為了解決上述的兩個問題，我們要來學習 C++ 標準函式庫中提供的一個強大的容器 (container): vector。

補充: C++ 的標準函式庫定義了許多專門用來儲存資料的容器 (container)，比起一般的變數如: int 或 char，容器擁有更多強大的功能，使用起來非常方便。前面所介紹的 string 也是容器之一，它的功用應該不難猜: string 是專門用來儲存一堆 char 的容器。

vector 是什麼?

注意: 在程式中使用 vector 前，要先導入相關的函式庫 <vector>，如下所示:

#include <vector>

如果把變數比喻成一個盒子，可以把資料放進盒子，那 vector 就是一堆黏在一起的盒子。下列程式宣告了一個型態為整數的變數 x 以及型態為整數的 vector vec:

int x = 0;
vector<int> vec(6, 0);

宣告與初始化 vector 的方式幾乎就跟 x 一樣:

1. 指定資料型態: vector<int> 這整坨東西是一種資料型態，vector 指的是容器的種類，而 int 的意思是「這個容器裡面裝的資料型態是整數」。換句話說，在宣告容器的時候，資料型態 = 容器的種類 + 裡面裝什麼資料型態。
2. 幫變數取名字: vec 是一個變數，它的資料型態為 vector<int>。
3. 初始化: 這個部分跟一般的變數不太一樣，(6, 0) 的意思是「這個 vector 有六個盒子，每個盒子裡面的初始值都是 0」​。

可以把 vector<int> vec(6, 0) 想像成把六個資料型態為 int 的變數黏在一起，並且幫它們取一個新名字: vec。下面是 vec 的示意圖:

vector 裡面包含的資料數量稱為 vector 的「長度」。換句話說， vec 是一個資料型態為 vector<int> 且長度為 6 的 vector。

我們也可以在 vector 裡面裝其他的資料型態，下面是一些範例:

// vector of char, initialized with 2 char: 'a'
vector<char> vec_c(2, 'a');
// vector of float, initialized with 10 float: '3.14'
vector<char> vec_f(10, 3.14);
// vector of bool, initialized with 6 bool: true
vector<bool> vec_b(6, true);​

事實上，目前為止 (還有以後會學到的) 資料型態都可以裝到 vec 裡面，包含 string! 因為 string 也是一種資料型態，我們可以宣告一個「用來儲存 string 的 vector」，方法就跟上述的其他例子一模一樣:

// vector of string, initialized with 2 string: "Hi!"
vector<string> vec_str(2, "Hi!");​

補充: string 是由一堆 char 組成的，所以 string 跟 vector<char> 概念上很接近。它們的差別在於，因為許多程式都需要進行大量的文字、符號的處理，所以特別設計了獨立的 string 資料型態，裡面定義了許多好用的功能。string 基本上就是 vector<char> 加上很多專門用來操作字元和字串的功能。

還有另一種初始化 vector 的方法，叫做 list initialize，它的用途是直接指定一串常值存到 vector 裡面。list initialize 的好處是每個 element 的初始值不一定要相同:

// list initialize a vector
vector<char> vec{-1, 5, 10, 2};

上述的 vec 有四個 element，分別為 -1, 5, 10, 2。

vector 的 index

前面有提到 vector<int> vec(6, 0) 就是把六個 int 變數黏在一起，這六個變數有各自的編號，如下圖所示:

編號從 0 開始到 5，每個編號都代表一個型態為整數的變數。在程式語言中，有專門的術語來稱呼編號和其對應到的變數: index (索引) 和 element (元素)。
舉例來說，vec 中的第一個變數是「index 為 0 的 element」，最後一個變數是「index 為 5 的 element」，依此類推。

注意: 在電腦和程式的世界中，所有東西都是從 0 開始算，不是 1。所以 vec 的第一個 element 的 index 是 0，不是 1。

我們可以透過 index 來使用/修改 vector 中 element 的資料，就跟一般的變數一樣。實際的寫法是在 vector 的變數名後面加上中括號，中括號裡面填 element 的 index: 變數名稱[index]。

下面的程式將 vec 中 index 為 2 的 element (第三個變數) 加上 10 以後印出來:

vector<int> vec(6, 0);
vec[2] += 10;
// print 10
cout << vec[2];

用法就跟一般的變數一樣。

下面的例子使用 list initialize 初始化 vector:

vector<int> vec{0, 11, -3};
vec[2] += 10;
// print 7
cout << vec[2];

會將 index 為 2 的 element (第三個) 加上 10，並印出來。

vector 可以幫助我們解決「待解決的問題」中的第一個問題: 無法一次宣告多個變數。

也可以不對 vector 進行初始化，如下所示:

vector<int> vec;

上面宣告了一個資料型態為 vector<int> 且沒有任何 element 的 vector。這種 vector 目前對我們來說還沒有用處，但它在後面會派上用場的。

使用 for 走訪 vector

走訪 (iterate) vector 的意思是對 vector 的 element 進行存取 (拿出裡面的資料、修改資料、或是任何使用的行為) 。有時候會使用另一個術語: 迭代，它跟走訪是相同的意思。

我們可以利用 for 的 induction variable 來計算 vector element 的 index。下面的程式會走訪 vector 中的所有 element，並計算它們的總和:

// vector of int, initialized with 10 integer: 2
vector<int> vec(10, 2);
int sum = 0;
for (int i = 0; i < 10; ++i)
	sum += vec[i];
cout << sum;​

首先宣告了一個資料型態為 vector<int> 的 vector: vec，且初始狀態為 10 個整數 2。接著我們又宣告了一個變數 sum 初始化為 0，用來計算 vec 所有 element 的總和。

for 迴圈的部分，因為第一個 element 的 index 為 0，所以將 i 初始化為 0，然後每走訪完一個 element 並將它的值加到 sum 以後，就將 i 的值加 1。注意 i 必須要小於 10 (最後一個 element 的 index 為 9)。

vector 有一個好用的函式，叫做 size()，它會回傳目前這個 vector 的長度 (有幾個 element)，使用方式為: 變數名稱.size()，範例如下:

// vector of string, initialized with 10 string: "?"
vector<string> vec(10, "?");
cout << vec.size();

注意: 需要在變數名稱和函式中間加上 . 的原因是，我們這邊使用的 size() 是 vector<int> 這個資料型態所定義的函式。沒錯! 資料型態不只是定義資料的格式而已，還可以為這個資料型態定義專屬的函式。string 也有定義 size() 這個函式，它會回傳目前這個 string 中包含了幾個字元，範例如下:

string str = "Hello C++!";
cout << str.size();

可以發現兩個範例的用法一模一樣，想達成的目的也一樣，但它們一個定義在 vector<int> 中，一個定義在 string 中，所以是不一樣的函式。

了解了 size() 怎麼使用以後，我們可以將一開始計算 element 總和的程式改得更通用，本來 i 的上限寫死成 10，現在可以把它替換成 vec.size()，讓電腦幫我們算出目前的 vec 有多少 element 並設成 induction variable 的上限:

// vector of int, initialized with 10 integer: 2
vector<int> vec(10, 2);
int sum = 0;
for (int i = 0; i < vec.size(); ++i)
	sum += vec[i];
cout << sum;

下列是使用 list initialize 的範例:

// list initialize
vector<int> vec{-1, 2, 10, 3, 5, -4};
int sum = 0;
for (int i = 0; i < vec.size(); ++i)
	sum += vec[i];
cout << sum;

注意: 我們可以使用 vec.size() 算出利用 list initialize 進行初始化以後，vec 擁有多少個 element。

範例1: 計算 vector 中所有偶數的總和

// list initialize
vector<int> vec{-1, 2, 10, 3, 5, -4};
int sum = 0;
for (int i = 0; i < vec.size(); ++i) {
	if (vec[i] % 2 == 0)
		sum += vec[i];
}
cout << sum;

範例2: 將兩個長度相同的 vector 中相同 index 所對應到的 element 相加，存入第三個 vector 對應的 element 中，並將第三個 vector 的 element 印出來。

// list initialize
vector<int> vec1{-1, 2, 10, 3, 5, -4};
vector<int> vec2{12, 0, 11, -3, 2, -10};
// initialize with six 0
vector<int> vec3(6, 0);

for (int i = 0; i < vec1.size(); ++i)
	vec3[i] = vec1[i] + vec2[i];
for (int i = 0; i < vec1.size(); ++i)
	cout << vec3[i] << ' ';

範例3: 比較兩個長度相同的 vector 中，每個 index 所對應到的 element 誰比較大，將比較大的數值存入第三個 vector 對應的 element 中，並將第三個 vector 的 element 印出來。

// list initialize
vector<int> vec1{-1, 2, 10, 3, 5, -4};
vector<int> vec2{12, 0, 11, -3, 2, -10};
// initialize with six 0
vector<int> vec3(6, 0);

for (int i = 0; i < vec1.size(); ++i) {
	if (vec1[i] > vec2[i])
		vec3[i] = vec1[i];
	else
		vec3[i] = vec2[i];
}
for (int i = 0; i < vec1.size(); ++i)
	cout << vec3[i] << ' ';

vector 的指派運算

vector 像前面介紹過的 C++ 內建資料型態一樣，也可以使用 = 運算子，如:

vector<int> vec1{1, 2, 3};
vector<int> vec2{-1};
// assign vec2 to vec1
vec1 = vec2;

// print 1 2 3
for (int i = 0; i < vec2.size(); ++i)
	cout << vec2[i] << ' ';

vec2 = vec1 的意思是將 vec2 儲存的資料清空，並將 vec1 所有 element 的值複製給 vec2。也就是說，vec1 的內容會跟 vec2 變得一模一樣。

也可以利用 = 來進行 vector 的初始化:

vector<int> vec1{1, 2, 3};
vector<int> vec2 = vec1;

// print 1 2 3
for (int i = 0; i < vec2.size(); ++i)
	cout << vec2[i] << ' ';

就像一般變數一樣，我們可以利用 = 運算來交換兩個 vector 的資料:

vector<int> vec1{1, 2, 3};
vector<int> vec2{-1};
// temparary vector for swap
vector<int> tmp;
tmp = vec1;
vec1 = vec2;
vec2 = tmp;

不過 vector 其實有提供專門的函式來交換資料，就叫做 swap():

vector<int> vec1{1, 2, 3};
vector<int> vec2{-1};
vec1.swap(vec2);

上述兩段程式會得到一樣的結果，但第二個寫法明顯比較簡潔，讓未來讀程式碼的人一眼就看出這段程式在做什麼。

注意: 往後會學到更多 C++ 標準函式庫提供給我們的函式，善用這些函式來撰寫程式不只可以加快開發流程，還可以讓程式碼更簡潔、更好讀，執行起來通常也會更有效率。

常犯的錯誤

對一個長度為 n 的 vector 來說，第一個 element 的 index 為 0，最後一個 element 的 index 為 n -1。

這件事情很重要的原因是，使用 index 來存取 element 的時候，程式設計師有責任確保這個 index 是在正確的範圍內的，也就是 index 必須要 >= 0 且 <= n-1。

假如有個 vector<int> vec 的長度為 5，vec[5] 這個操作是錯誤的! 因為最後一個 element 的 index 是 5 - 1 = 4，index 5 已經超出 vec 目前涵蓋的範圍了。

最可怕的事情是，這種錯誤有時候很難被發現，因為程式有可能會像是沒事一樣的繼續執行 (原因之後會解釋)。而且不只是新手可能犯這個錯，就算是有經驗的程式設計師，也可能在撰寫比較複雜的程式的時候，不小心用超出範圍的 index 去存取 vector。

這種類型的錯誤可能會成為資安漏洞。事實上，許多軟體的漏洞都是這類錯誤造成的。

push_back()

這裡要介紹 vector 另一個很常用的函式: push_back()。使用這個函式的時候需要傳入一個常值或變數，或可以產生數值的運算式 (如兩個變數相加)，如下所示:

vec.push_back(1);
int x = 10;​
vec.push_back(x);
vec.push_back(x + 4);

這個函式的功用是在目前這個 vector 的尾端加入一個新的 element，並將它的值初始化為參數傳入的值。舉個例子來說，假設我現在有一個 vector<int> vec，如下所示，它目前有三個 element，分別為 3, -1, 0:

假設我們執行 vec.push_back(7)，vec 就會在尾端加上一個整數型態的 element 並初始化為 7:

範例: 將兩個長度相同的 vector 中相同 index 所對應到的 element 相加，存入第三個 vector 對應的 element 中，並將第三個 vector 的 element 印出來。

// list initialize
vector<int> vec1{-1, 2, 10, 3, 5, -4};
vector<int> vec2{12, 0, 11, -3, 2, -10};
// size of vec3 is 0
vector<int> vec3;

for (int i = 0; i < vec1.size(); ++i)
	vec3.push_back(vec1[i] + vec2[i]);
for (int i = 0; i < vec1.size(); ++i)
	cout << vec3[i] << ' ';

注意: 這題其實在前面有出現過，差別在於這次我們不對 vec3 進行初始化 (長度為 0)。這樣寫的好處是，我們可以讓使用者決定 vec1 和 vec2 要裝什麼資料，無論使用者想輸入多少資料，我們都能順利算出兩個 element 的和並利用 push_back() 加到 vec3 中。

學會使用 push_back() 以後，我們就克服了「待解決的問題」中的第二個問題: 需要事先知道資料的數量。

現在我們有能力解決「待解決的問題」所提出的程式問題: 讓使用者依序輸入 n 個數字，並且用相反的順序將所有的數字印出來:

int n;
cin >> n;
// the size of vec is 0​
vector<int> vec;
// read n numbers​
for (int i = 0; i < n; ++i) {
	int x;
	cin >> x;
	vec.push_back(x);​
}
// print n numbers in reverse order​
​for (int i = n-1​; i >= 0; --i)
	cout << vec[i] << ' ';​​

注意: 第二個 for 的功用是把 element 以相反的順序印出來，對於長度為 n 的 vector 來說，第一個 element 的 index 是 0，最後一個 element 的 index 是 n - 1，所以 i 的範圍才會設成 0 ~ n-1，並且在每次迴圈後就會減 1。

clear()

clear() 的作用是清空目前的 vec，如下所示:

vector<int> vec{1, 2, 3};
vec.clear();
// print 0
cout << vec.size();

在呼叫 clear() 以後，因為所有 element 都被清除了，所以 size() 會回傳 0。

總結​

1. vector 是 C++ 標準函式庫中定義的容器，可以包含多個 element。
2. 宣告 vector 的時候需要指定 element 的資料型態為何，舉例來說: vector<float> vec; 宣告了一個型態為 vector<float> 且長度為 0 的 vector。vector 是容器的種類，vec 的資料型態是 vector<float>。
3. 目前學了兩種初始化 vector 的方式: 第一種是指定 element 的數量以及 element 的初始值，第二種則是直接指定一連串的數值存到 vector 中 (list initialize)。
4. 對一個長度為 n 的 vector 來說，第一個 element 的 index 為 0，最後一個 element 的 index 為 n -1。
5. 可以利用 for 的 induction variable 來作為 vector 的 index，藉此來存取 (讀資料、修改資料、任何其他使用方式) vector 的 element。
6. vector 定義了許多好用的函式，其中 size() 會回傳 vector 目前的 element 數量，push_back() 則會將新的值加到 vector 的尾端，clear() 則會清空 vector 內的所有 element。
   

習題

1. 宣告一個 vector<int>，讓使用者輸入 n 個 int (n 也由使用者決定)，將 vector 中所有值為奇數的 element 加 1。
2. 宣告三個 vector<float>，前兩個 vector 使用 list initialize (長度要一樣)，第三個不進行初始化。將前兩個 vector 對應 index 的 element 相乘儲存到第三個 vector 中。
3. 宣告三個 vector<float>，皆使用 list initialize (長度要一樣)。將三個 vector 對應 index 的 element 相加以後，儲存到第三個 vector 中。
4. 宣告三個 vector<int>，皆使用 list initialize，將第一個 vector 的值複製給第一個，第二個的給第三個，第三個的則給第一個。
5. 宣告兩個 vector<int>，皆使用 list initialize (長度不一樣)，持續將長度較短的 vector 後面補 0，直到跟另一個 vector 長度相同。
6. 宣告兩個 vector<int>，皆不進行初始化。讓使用者輸入 n 個 int (n 也由使用者決定) 然後存到第一個 vector 中。將第一個 vector 的 element 用相反的順序存入第二個 vector 中。舉例來說: 如果使用者輸入 1, 2, 3，第一個 vector 內的值應該要是 1, 2, 3，第二個 vector 則是 3, 2, 1。
7. 宣告一個 vector<int>，不進行初始化。讓使用者輸入 n 個 int (n 也由使用者決定) 然後存到 vector 中。將 index 0 的值和 index 1 的互換，2 和 3 的互換，若 vector 的長度是奇數的話，最後一個 element 的值保持不變。
8. 宣告一個 vector<char>，不進行初始化。讓使用者輸入 n 個 char (n 也由使用者決定) 然後存到 vector 中，接著將 vector 中每個 element 的值串接起來成為一個 string。舉例來說: 使用者如果輸入 'a', 'b', 'c', '!'，串接完的字串應該要是 "abc!"。

應用

1A2B