C++ - vector

C++ vector 是一個可以改變陣列大小的序列容器。C++ vector 是陣列的升級版，主要因為 vector 能高效地對記憶體進行管理以及動態增長。vector 其實就是將陣列和方法封裝形成的一個類別。

C++ 要使用 vector 容器的話，需要引入的標頭檔： <vector>

# vector 初始化

這樣是宣告一個 int 整數類型的 vector，裡面沒有任何元素 (空)，size 為 0 表示 vector 容器中沒有任何元素，capacity 也是 0。

#include <vector>

vector<int> v;

# push_back()

先宣告一個空的 vector，再透過 push_back() 將資料一直推進去。

vector<int> v;

v.push_back(1);

v.push_back(2);

也可以寫成一行，但這語法需要編譯器 C++11 支援。

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

// or

vector<int> v({1, 2, 3});

# 複製容器

假如要從另外一個 vector 容器複製資料過來當作初始值的話可以這樣寫。

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

vector<int> v2 = v1;

// or

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

vector<int> v2(v1);

也可以從傳統陣列裡複製過來當作初始值。

int n[3] = {1, 2, 3};

vector<int> v(n, n+3);

不想複製來源 vector 全部的資料，想要指定複製 vector 的範圍的話也可以，例如我要複製 v1 vector 的第三個元素到倒數第二個元素。

vector<int> v1 = {1, 2, 3, 4, 5};

vector<int> v2(v1.begin() + 2, v1.end() - 1);

如果是指定複製傳統陣列的範圍的話，可以這樣寫。

int n[5] = {1, 2, 3, 4, 5};

vector<int> v(n + 2, n + 4);

# 存取 vector 元素

vector 用 [] 來隨機存取元素，第一個元素為 v[0] ，索引值是 0 ，第二個元素為 v[1] ，索引值是 1 ，依此類推， [] 不只可以讀取元素也可以用來修改元素。

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

cout << "v[0] = " << v[0] << endl;

v[0] = 4;

cout << "v[0] = " << v[0] << endl;

v[0] = 1
v[0] = 4

# 在 vector 尾巴新增元素

要在 vector 尾巴新增元素，要使用前面提到的 push_back() ，它會把元素加在 vector 的尾巴。

vector<int> v;

v.push_back(0);

# 在 vector 尾巴移除元素

移除 vector 容器尾巴的元素用 pop_back() ，一次只能從尾端移除一個元素，不能指定移除的數量。

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

v.pop_back(); // [1, 2]

# 迴圈遍歷 vector

第一種是常見的用法，

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

for (int i=0; i<vec.size(); i++) {

    cout << vec[i] << ' ';

}

1 2 3

第二種是使用 iterator 迭代器來印出 vector 內所有內容，其中 vector<int>::iterator it 可以簡化寫成 auto it 這樣

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

vector<int>::iterator it;

for (it = vec.begin(); it != vec.end(); it++) cout << *it << ' ';

// or

for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << ' ';

第三種是個很方便的寫法，c++11 才有支援，適合追求快速 (懶惰) 的人，相較於第一種的優點是不用多寫陣列索引去存取，直接就當變數使用。

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

for (auto &v: vec) cout << v << ' ';

# vector 使用 [] operator 與 at () 的差異

另外 vector 還提供了 at() 這個方法也是可以取得元素，那這兩種方式到底有什麼差別？

[] operator 在回傳元素時是不會作任何的邊界檢查，而在 at() 取得元素時會作邊界的處理，如果你存取越界時 vector 會拋出一個 out_of_range 例外，所以 at() 提供了較為安全的存取方式。

# vector size () 與 capacity () 的差異

vector 使用 size() 是取得目前 vector 裡的元素個數，vector 使用 capacity() 是取得目前 vector 裡的預先配置的空間大小，當容量 (capacity) 空間不夠使用時 vector 就會重新申請空間，容量 (capacity) 會增加為原來的 2 倍或 1.5 倍，例如：1、2、4、8、16、32 增長下去，各個編譯器可能不同。

# reserve () 預先配置容器大小

vector 使用 reserve() 是預留空間的意思，如果我們一開始就知道容器的裡要放置多少個元素的話，可以透過 reserve() 來預先配置容器大小，這樣可以減少一直配置記憶體的機會。

觀察看看 size 與 capacity 的變化。

vector<int> v;

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

v.reserve(5);

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

v.push_back(1);

v.push_back(2);

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

size = 0, capacity = 0
size = 0, capacity = 5
size = 2, capacity = 5

# shrink_to_fit () 收縮的用法

呈上述 reserve 例子，這時 vector 再使用 shrink_to_fit() 成員函式的話，會釋放（free）那些尚未使用的空間，

vector<int> v;

v.reserve(5);

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

v.push_back(1);

v.push_back(2);

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

v.shrink_to_fit();

cout << "size = " << v.size() << ", capacity = " << v.capacity() << "\n";

size = 0, capacity = 5
size = 2, capacity = 5
size = 2, capacity = 2

如果 size() 剛好等於 capacity() 的話，那麼使用 shrink_to_fit() 則不會有空間被釋放。

# resize()

vector 使用 resize() 跟 reserve() 不太一樣，resize 變大時會把多的元素補 0。

vector<int> v;

v.resize(5);

cout << "size =" << v.size() << ", capacity =" << v.capacity() << "\n";

for (int i = 0; i < v.size(); i++) cout << v[i] << " ";

size = 5, capacity = 5
0 0 0 0 0

resize 如果要順便指定元素初始值的話，可以將初始值帶入 resize () 的第二個引數。

vector<int> v;

v.resize(5, 10);

cout << "size =" << v.size() << ", capacity =" << v.capacity() << "\n";

for (int i = 0; i < v.size(); i++) cout << v[i] << " ";

size = 5, capacity = 5
10 10 10 10 10

如果 resize 的大小超過 capacity 容量大小會怎麼樣呢？

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

cout << "size =" << v.size() << ", capacity =" << v.capacity() << "\n";

v.resize(5);

cout << "size =" << v.size() << ", capacity =" << v.capacity() << "\n";

for (int i = 0; i < v.size(); i++) cout << v[i] << " ";

輸出如下，原本的 1, 2, 3 元素有保留以外，剩下新增的元素補 0 。

size = 3, capacity = 3
size = 5, capacity = 6
1 2 3 0 0

# vector 的優缺點

# 優點

• 宣告時可以不用確定大小
• 節省空間
• 支持隨機訪問 [i]

# 缺點

• 進行插入刪除時效率低
• 只能在末端進行 pop 和 push

# 參考資料

• https://shengyu7697.github.io/std-vector/