changed 4 years ago  
Linked with GitHub

進階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











#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"

​​​​-> 多功能陣列

標頭檔

#include<vector>

宣告







#include<vector>
using namespace std; // 沒打的話，vector前面要加 std::

vector <type> name(size , memset); //最完整的寫法
// or
vector <type> name(); // size = 0 , memset = 0

初始化











#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>

功能

空間相關功能

v.empty() ：
 if v 的 size 為 0 ，回傳 1 ， else 回傳 0。

v.size() ：
 輸出 v 的 size

v.resize( , ) ：
 重新分配空間 - 像是一開始初始化的( , )

v.clear() ：
 把 v 清空












#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] 的偽指標

// 它常會跟其他功能一起用











#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()










#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 項移掉














#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


















#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() ）;

使用前，陣列要先 由小到大 排列過















#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
}

二維陣列




vector< vector<type> > name(size1 , vector<type>(size2 , memset));

type name[size1][size2];
















#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



























#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排序

Select a repo