C++ vector應用介紹

什麼是Vector?
Vector以成員角度來看是類C++標準函式庫的類別(Class)，可視之為動態陣列，能適時自動擴充容量，以循序(Sequenital)方式維護資料。

資料存放在連續記憶體，以至於可使用迭代器追蹤資料，方便存取，在Vector類別裡，資料的新增是加在末端，在尾端刪除通常只要費時常數時間，反之，若在頭、中間新增或刪除資料則需要耗費線性時間。

此外Vector能透過泛型(Template)，保存任意類型的變數，包括使用者自定義的資料型態，例如整數型態(int)、字串型態(string)、或是自行定義的資料型態等。

Vector特色

• 支持隨機存取
• 末尾資料刪除耗費時間:O(1)
• 中間資料插入、刪除耗費時間:O(n)
• 利用泛型(Template)，保存任意類型的變數，包括自定義的資料型態

Vector方法

存取元素的方法

• vec[i] - 存取索引值為 i 的元素參照。 (索引值從零起算，故第一個元素是vec[0]。)
• 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 的第一個元素的前一個位置。

實戰練習

新增、刪除、存取資料

排序

題目練習

練習題1. Leetcode 中序節點拜訪

解法詳情請參考資料結構課本

練習題2. Leetcode 尋找陣列中消失的數字

思維:利用迴圈，每讀一個元素(取絕對值，有些元素可能是負數)，我們去算出它排序後的正確位子(索引)，將那個位子上的元素標記上負號，若該元素是標記過的(即負數)，我們則跳過這個目前讀取元素。

最後，我們去看哪些元素是還沒標記上，他們索引值加上1，即為消失的數字。