owned this note
owned this note
Published
Linked with GitHub
---
tags: 2021CRC
title: 進階STL：Vector
slideOptions:
transition: slide
theme:
---
# 進階STL：vector
## 2021/11/19 電算社第九堂社課
---
## STL ？
standard template library（標準模板庫）
更多的資料結構
----
複習一下之前遇到的資料結構
std::string 字串
ex `string s = "C8763";`
c-array （c式陣列）
ex `int arr[100] = {0};`
除了這兩種，我們之後會學到更多種類的資料結構。
---
## STL簡介
----
將來會學到的東西 一覽
`vector`
`queue` , `stack` , `deque`
`set` , `map`
`priority_queue`
（可能有更動）
---
## c-array
----
```cpp=
#include<iostream>
using namespace std;
int main()
{
int arr[10];
for(int i=0 ; i<10 ; i++) cin >> arr[i];
int found = 5
cout << arr[found];
}
```
----
### 缺點
1. 使用長度固定（size改不了）
2. 存取size之外的位置，程式會直接crash
---
## vector
----
What is "vector"
-> 多功能陣列
----
### 標頭檔
```cpp=
#include<vector>
```
----
### 宣告
```cpp=
#include<vector>
using namespace std; // 沒打的話，vector前面要加 std::
vector <type> name(size , memset); //最完整的寫法
// or
vector <type> name(); // size = 0 , memset = 0
```
----
### 初始化
```cpp=
#include<vector>
#include<iostream>
using namespace std;
int main()
{
vector<int> v(10 , -1);
// {-1,-1,-1,-1,-1,-1,-1,-1,-1-,-1}
cout << v[9]; // -1
}
```
`Tips： 除了初始化，剩下的時候，c-array的用法，vector都可以用。`
`但是 vector 多了很多功能`
----
### 缺點
1. n維陣列宣告要打超長
（下面會詳細說明）
2. 要打標頭檔 `#include<vector>`
---
## 功能
----
### 空間相關功能
<font color="#FFF300">v.empty() ：
</font> if v 的 size 為 0 ，回傳 1 ， else 回傳 0。
<font color="#FFF300">v.size() ：
</font> 輸出 v 的 size
<font color="#FFF300">v.resize( , ) ：
</font> 重新分配空間 - 像是一開始初始化的`( , )`
<font color="#FFF300">v.clear() ：
</font> 把 v 清空
----
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v(3,5); // 5 5 5
cout << v.empty() << " " << v.size() << "\n";
// 0 3
v.resize(5,2); // 2 2 2 2 2
v.clear(); //
}
```
----
### 位置相關功能
（假設 v 的 size 為 5）
v.front() ： `v[0]` 的值
v.back() ： `v[4]` 的值
v.begin() ： `v[0]` 的**偽指標**
v.end() : **`v[5]`** 的**偽指標**
// 它常會跟其他功能一起用
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
cout << v.front(); // 1
cout << v.back(); // 10
cout << v.end() - v.begin(); // 10 (v.size());
}
```
----
### 資料相關功能
v.push_back()
v.pop_back()
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v; // (size = 0)
v.push_back(1); // 1
v.push_back(2); // 1 2
v.pop_back(); // 1
}
```
----
### Vector額外功能
刪除或新增中間的第 i 項
v.insert(v.begin() + i, a)：在第 i 項插入a
v.erase(v.begin() + i)：把第 i 項移掉
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> v(5); // size = 5
for(int i = 0 ; i < 5 ; i++) v[i] = 2 * i;
// {0 , 2 , 4 , 6 , 8}
v.erase(v.begin() + 0); // 2 4 6 8
v.erase(v.begin() + 2 , v.begin() + 3); // 2 4 8
v.insert(v.begin() + 1 , 5); // 2 5 4 8
}
```
---
## algorithm x vector
----
### sort
```cpp=
#include <iostream>
#include <vector>
#include <algorithm> // sort的函式庫
using namespace std;
int main(){
vector<int> v = {5,6,3,1,2,9,8,7,0,4};
sort(v.begin(), v.end());
for(int i = 0; i < 10; i++){
cout << v[i] << ' '; // 0 1 2 3 4 5 6 7 8 9
}
sort(v.begin(), v.begin() + 5, greater<int>());
for(int i = 0; i < 10; i++){
cout << v[i] << ' '; // 4 3 2 1 0 5 6 7 8 9
}
}
```
----
### upper_bound , lower_bound
`upper_bound(v.begin() , v.end() , num);`
第一個 **大於** num 的偽指標（類似 `v.begin()` ）;
`lower_bound(v.begin() , v.end() , num);`
第一個 **大於等於** num 的偽指標（類似 `v.begin()` ）;
**使用前，陣列要先 <font color="#F00">由小到大</font> 排列過**
----
```cpp=
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
vector<int> v(10);
for(int i=0 ; i<10 ; i++) v[i] = i*2;
// {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}
cout << upper_bound(v.begin() , v.end() , 14) - v.begin();
// 8
cout << lower_bound(v.begin() , v.end() , 14) - v.begin();
// 7
}
```
---
### 二維陣列
----
```cpp=
vector< vector<type> > name(size1 , vector<type>(size2 , memset));
type name[size1][size2];
```
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<vector<int>> v(2, vector<int>(3, 2));
// { {2, 2, 2}, {2, 2, 2} }
int arr[2][3];
for(int i = 0; i < 2; i++){
for(int j = 0; j < 3; j++){
arr[i][j] = i + j;
}
}
// 0 1 2
// 1 2 3
}
```
---
## 小練習
卡森社長找到了一個好玩的機器，上面有兩個按鈕，按1可以放入一顆球，按2可以從最前端射出一顆球，現在卡森社長要進行$n$輪操作，你可以幫他看看最終機器裡面剩下的球依序為何嗎
----
輸入說明：輸入一個整數$n$，代表會有$n$輪操作，接著輸入數字$m$，代表要按的按鈕，若$m = 1$，則輸入一個數字$k$，代表放入球的編號
輸出說明：輸出最後機器裡剩下的球依序為何
範例輸入：
```
5
1 2
1 3
1 4
2
2
```
範例輸出：`4`
----
我是防雷頁:D
----
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> v;
int n;
cin >> n;
for(int i = 0; i < n; i++){
int m;
cin >> m;
if(m == 1){
int k;
cin >> k;
v.push_back(k);
}
if(m == 2){
if(!v.empty()){
v.erase(v.begin() + 0);
}
}
}
for(int i = 0; i < v.size(); i++){
cout << v[i] << ' ';
}
return 0;
}
```
---
## OJ練習題
[zerojudge a104排序](https://zerojudge.tw/ShowProblem?problemid=a104)
Google Drive
Gist
Clipboard
Sign in with Wallet
