Vector

**Vector** 是 C++ 標準程式庫中的一個類，可視為會自動擴展容量的陣列，以循序（Sequential）的方式維護變數集合。vector 的特色有支援隨機存取，在集合尾端增刪元素很快，但是在集合中間增刪元素比較費時。vector 是 C++ 標準程式庫中的眾多容器之一。 vector 以模板方式實現，可以儲存任意類型的變數，包括使用者自訂的資料型態，例如：它可以是放置整數（int）型態的 vector、也可以是放置字串（string）型態的 vector、或者放置使用者自訂類別（user-defined class）的 vector。

## 設計

vector 定義於 <vector> 標頭檔中。與其他 STL 元件一樣，vector 屬於 std 名稱空間。

vector 是 C++ 標準程式庫裡最基本的容器，大多數狀況下都很有效率。vector 設計之初即是為了改善 C 語言原生陣列的種種缺失與不便，而欲提供一種更有效、更安全的陣列。vector 的使用介面刻意類比 C 語言原生陣列，較明顯的差異在於記憶體管理，原生陣列必須在宣告陣列的時候明確指定陣列長度 (例如 int a [5])，但是 vector 不需要指定，而是會在執行期依據狀況自我調整長度，動態增大容量。

vector 的表現一如資料結構中的陣列，允許隨機存取 (Random Access)，以索引值 (index) 存取任一元素只要花費常數時間 O (1)，在集合尾端增加或刪除元素也是花費常數時間 O (1)，若在 vector 集合中間增加或刪除元素時間複雜度是線性時間 O (n)，較為費時。雖然 C++ 標準並沒有規定實作方式，但大多數 vector 內部均使用動態陣列方式實作。

### 成員函式概觀

`vector` 類別是以容器 模式為基準設計的，也就是說，基本上它有 `begin()`，`end()`，`size()`，`max_size()`，`empty()` 以及 `swap()` 這幾個方法。

* 存取元素的方法
  * `vec[i]` - 存取索引值為 i 的元素參照。 (索引值從零起算，故第一個元素是 vec [0]。)
  * `vec.at(i)` - 存取索引值為 i 的元素的參照，以 at () 存取會做陣列邊界檢查，如果存取越界將會拋出一個例外，這是與 operator [] 的唯一差異。
  * `vec.front()` - 回傳 vector 第一個元素的參照。
  * `vec.back()` - 回傳 vector 最尾端元素的參照。
* 新增或移除元素的方法
  * `vec.push_back()` - 新增元素至 vector 的尾端，必要時會進行記憶體組態。
  * `vec.pop_back()` - 刪除 vector 最尾端的元素。
  * `vec.insert()` - 插入一個或多個元素至 vector 內的任意位置。
  * `vec.erase()` - 刪除 vector 中一個或多個元素。
  * `vec.clear()` - 清空所有元素。
* 取得長度 / 容量
  * `vec.size()` - 取得 vector 目前持有的元素個數。
  * `vec.empty()` - 如果 vector 內部為空，則傳回 true 值。
  * `vec.capacity()` - 取得 vector 目前可容納的最大元素個數。這個方法與記憶體的組態有關，它通常只會增加，不會因為元素被刪減而隨之減少。
* 重新組態／重設長度
  * `vec.reserve()` - 如有必要，可改變 vector 的容量大小（組態更多的記憶體）。在眾多的 STL 實例，容量只能增加，不可以減少。
  * `vec.resize()` - 改變 vector 目前持有的元素個數。
* 迭代 (Iterator)
  * `vec.begin()` - 回傳一個 Iterator，它指向 vector 第一個元素。
  * `vec.end()` - 回傳一個 Iterator，它指向 vector 最尾端元素的下一個位置（請注意：它不是最末元素）。
  * `vec.rbegin()` - 回傳一個反向 Iterator，它指向 vector 最尾端元素的。
  * `vec.rend()` - 回傳一個 Iterator，它指向 vector 的第一個元素的前一個位置。

## 使用說明

### 聲明

使用 vector 之前，必須先 #include<vector>。

聲明一個 vector 變數的方法如下:

T 是 vector 要儲存的物件集合的型別，該 vector 的變數名稱是 v。T 可以是任何符合 Copy/Move Assignable 條件的型別，包括使用者自訂型別。如果 T 不符合 Copy / Move Assignable 或者複製 / 移動成本很高昂，可以考慮使用 T\* 甚至 std::unique\_ptr<T> 來代替 T。

### 取代陣列使用

### 長度 / 容量

以下程式碼是用來說明 vector 的長度變化。

### string 類型 Vector 的使用

第一種：使用迭代器進行遍歷

輸出結果為：

```
I Love Wikipedia
I Love Wikipedia
I Love Wikipedia
```

第二種，與 int 類型相同

輸出結果為：

```
I Love Wikipedia
123
```

## 刪除元素

vector 的成員函式 clear () 來刪除所有的元素。這個操作並沒有改變容器的容量，所以容量不變。

使用 vector 的成員函式 pop\_back () 來刪除容器尾部的元素。

成員函式 swap ()，這個函式用來交換兩個 vector 容器中的元素。因此可以與一個具有相同資料類型的內容為空的局部變數 swap，從而實現徹底刪除元素、釋放容量的目的。

成員函式 shrink\_to\_fit ()，會造成容器現有的迭代器都失效。

成員函式 erase () 有 2 個多載版本：

* 刪除單個元素，vector 的大小減 1；但容量不變；返回一個迭代器，它指向被刪除元素後的一個元素。如果移除了最後一個元素，會返回 std::end (data)。
* 移除一個範圍內的元素：傳入兩個迭代器。返回的迭代器指向被刪除元素後的位置，它是 std::begin (data)+1 ；如果刪除了最後一個元素，它就是 std::end (data)。

algorithm 標頭檔中的 std::remove ()，可以移除一個範圍內匹配特定值的元素。remove () 是一個全域函式，所以它不能刪除容器中的元素。會保持未移除的元素的順序。真正刪除需要用 erase () 成員函式，這叫做 **erase-remove**。remove () 演算法返回的迭代器作為 erase () 的第一個參數，erase () 的第二個參數是所指向容器中最後一個元素後一個位置的迭代器。如：

```
   words.erase(std::remove(std::begin(words), std::end(words),"none"), std::end(words));
```

## 優缺點探討

## 外部連結

* （英文） SGI 的 vector 使用說明（SGI STL specification of vector） （頁面存檔備份，存於網際網路檔案館）
* （英文） C++ 參考：vector（C++ reference: vector） （頁面存檔備份，存於網際網路檔案館）
* （英文） C++ 標頭檔說明（C++ Header description）