0%

0-17 vector

vector

可隨時改變長度的陣列!

宣告

1
vector<int> v;

這時的 v 是空的,若要宣告大小為 n,可以:

1
2
vector<int> v;
v.resize(n);

或者:

1
vector<int> v(n);

也可以直接:

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

填滿

1
vector<int> v(12,10);

宣告長度為 12 的 vector,並將值全部設為 10,後面參數沒有傳入的話,預設是 0。

1
2
vector<int> v(12);
fill(v.begin(), v.end(), 10);

使用 fill,並傳入 vector 的頭、尾、以及要填入的值也可以。

尾端加入元素

1
2
3
vector<int> v;
v.push_back(10);
v.emplace_back(45);

push_back 與 emplace_back 功能相同,但 emplace_back 速度稍快,push_back 比較好打

移除尾端

1
2
3
4
vector<int> v;
v.push_back(10);
v.emplace_back(45);
v.pop_back();

前端加入元素

無法

前端移除元素

無法

取得第 k 項

1
2
vector<int> v = {1, 2, 3};
cout << v[1] << '\n';

若索引值超過範圍,會噴 RE。

取得大小

1
2
vector<int> v = {1, 2, 3};
cout << v.size() << '\n';

是否為空

1
2
vector<int> v;
if(v.empty()) cout << "Empty!\n";

排序

1
2
3
4
int arr[] = {2, 1, 3, 8, -15};
vector<int> v = {2, 1, 3, 8, -15};
sort(v.begin(), v.end());
sort(arr, arr+5);

跟陣列相同,但開頭與結尾改為 begin 與 end。

反轉

1
2
vector<int> v = {2, 1, 3, 8, -15};
reverse(v.begin(), v.end());

意外的常用。

最小元素

1
2
3
vector<int> v = {2, 1, 3, 8, -15};
cout << *min_element(v.begin(), v.end()) << '\n';
cout << min_element(v.begin(), v.end()) - v.begin() << '\n';

若沒有*,回傳的是位址,可透過減掉 v.begin() 知道最小值所在的 index。

輸出所有 vector 裡的元素

1
2
3
vector<int> v = {1, 3, 2};
for(int i=0;i<v.size();i++) cout << v[i] << "\n";
for(int i:v) cout << i << "\n"; // C++ 11 以上

相信第一種寫法各位已經熟悉。

第二種寫法效果與第一種相同,但短很多,在 vector 等 STL 容器中非常好用,由於它是 C++ 11 以後才有的功能,若無法編譯可能要調整編譯器參數

使用vector時機

隨時。

當你想在函式內傳入二維陣列時使用 vector,因為一般的二維陣列無法傳入

當你需要很多個一維陣列,但每個陣列長度不一,最大可能很大(ex: 1000000)但不會每個都這麼大,直接開二維陣列記憶體會爆炸。這時就是 vector 的出場時機。

例題(花了我的兩個小時QQ)

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int N, K;
vector<int> pal[1000005];

int main(){
cin >> N >> K;
for(int i=0,a,b;i<K;i++){
cin >> a >> b;
pal[a].push_back(b); // pal[a] 存放 a 的朋友。 將 b 放入 pal[a] 的最後方
pal[b].push_back(a);
}
for(int i=1;i<=N;i++) sort(pal[i].begin(), pal[i].end());
for(int i=1;i<=N;i++){
for(int j=0;j<(int)pal[i].size();j++){
if(j != 0) cout << " ";
cout << pal[i][j];
}
cout << '\n';
}
}

練習

把之前 array 的練習題,用 vector 去寫寫看吧!