章節1-3.STL(一)

什麼是STL

STL是標準模板函式庫(Standard Template Library)的縮寫。
模板是C++中的一個重要功能，有時候某些函式執行完全一樣的功能、過程，但若要分出許多函式處理不同型別的參數或回傳值顯然很浪費資源，因此模板允許在編寫這類程式時進行泛型，也就是事後呼叫時再決定變數的確切型別，如此一來就可以編寫一個沒有確切型別的函式，等執行的當下再將該型別帶入函式裡。
而STL正是將許多實用的函式、功能內建在C++中的程式庫。

簡而言之，以模板定義的函式是靈活的機器，不會限制輸入的材料必須是什麼類型，但會對不同材料進行同樣的處理。而STL就是C++內建包含許多方便的模板函式的神器。

其實STL主要提供的是一卡車的「演算法函式」跟一卡車的「容器(用來對眾多資料進行特定方式儲存的工具)」，不過在此之前先介紹一項雖然不歸類在上述兩種，但超級方便並且會經常使用的工具，讓我們從STL的pair開始。

實用工具:pair

直接開門見山的解釋pair的用途，他可以將兩個一樣或不一樣的型別包在一起。
使用方式為「pair<型別1,型別2>」，如「pair<int,string>」，左邊這坨就是將int與string包裝在一起，也算是一個型別，不僅可以整個處理，也可以將包裝起來的內容物拿出來。
不多說直接看程式碼。

#include<bits/stdc++.h>
using namespace std;
int main(){
    pair<int,string> p;
    //賦值給pair或者說製作pair的方式有三種，以下由複雜但不容易錯的介紹到簡單但容易不小心寫錯的
    p=pair<int,string>(5,"Samuel");//第一是在該pair型別後加上(值1,值2)，型別固定
    p=make_pair(5,"Samuel");//第二是C++內建的make_pair()函式，會依據填入的引述決定pair型別，如左所示會回傳pair<int,string>型別
    //假設寫成make_pair(5LL,'S')就會回傳pair<long long int,char>型別
    p={5,"Samuel"};//最偷懶的寫法，唯一需要注意的是需要在確定p之型別時使用，換句話說不能搭配auto進行宣告(auto是另一種偷懶方式，以下介紹)
}

▼ 重要技巧:auto自動型別

C++在宣告變數時需要給定變數的型別，但同時也有自動判斷型別的功能「auto」，將型別寫作auto進行宣告就可以，只不過必須在宣告的同時先賦值，而C++就可以根據賦值的型別來決定變數型別。
這個技巧雖然算是偷懶，但在十分確定變數型別時會十分好用，並且在後續的STL課程中有部分名稱較長的型別利用此方式就會非常方便。
以下為範例程式。

#include<bits/stdc++.h>
using namespace std;
int main(){
    auto n=5;//n之型別為5之型別int
    auto m=1LL*n;//1LL*n進行運算後的結果型別為long long int，m之型別自動判斷為long long int
    auto c='A';//c之型別為'A'之型別char
    auto d=1.0;//d之型別為1.0之型別double
}

配合前述製作pair的介紹，可以知道「auto p=pair<int,string>(5,"Samuel");」跟「auto p=make_pair(5,"Samuel");」因為可以非常確定要賦值的型別所以是正確的用法，但「~~auto p={5,"Samuel"};~~」就不是正確的寫法了，因為{5,"Samuel"}的型別不明確，執行後會導致auto變成非pair的型別。

而前面介紹了如何把兩個變數綁起來變成pair，這裡要開始介紹如何把pair拆開了，直接在以下示範。

#include<bits/stdc++.h>
using namespace std;
int main(){
    pair<int,string> p=pair<int,string>(5,"Samuel");//宣告p
    cout<<p.first<<','<<p.second<<'\n';//輸出「5,Samuel」
    //在pair變數後加上.first、.second可以取得pair下的兩個變數
    p.first=10;//取出後的變數可以直接使用，也可以操作單個變數來改變p，此時p變為「10,Samuel」

    //以上就是最常用的拆解方法了，但下面補充一個有點抽象的拆解方法，若記不起來可跳過
    p=pair<int,string>(5,"Samuel");
    auto [x,y]=p;//此時p的內容會被拆解並賦值給兩個新變數x,y，但x,y與p沒有連結，修改x,y值不影響p
    cout<<x<<','<<y<<'\n';//輸出「5,Samuel」
    auto &[a,b]=p;//還記得上個章節的&取別名嗎，在此方法加上&可以讓a,b為p.first,p.second的別名，修改a,b值影響p
    cout<<a<<','<<b<<'\n';//輸出「5,Samuel」
}

此外pair還有一個強大的功能，就是可以直接判斷相等、比較大小，若兩個pair的first和second都一樣，那麼是相等很好理解，但若不相等的話，會先依據兩個pair的first來決定大小，若相同就依second決定大小，其實就是字典序的概念。

以上就是pair的用法。若能熟悉pair的使用將很有幫助，如函式回傳值只會有一個，但利用pair就可一次回傳多個數值，另外在後續STL的課程中還會有許多pair的應用。

▼ 補充:綁定更多數值的方法

前面提過pair綁定兩種型別後自己也算是一個型別，因此理所當然可以再被包到其他pair中，如下。

#include<bits/stdc++.h>
using namespace std;
int main(){
    pair< pair<int,long long int> , pair<double,char> > p;
    //p.first為pair<int,long long int>，p.first.first為int，p.first.second為long long int
    //p.second為pair<double,char>，p.second.first為double，p.second.second為char
}

通常不會實作到需要把超級多種不同型別變數包在一起的程式，因此用以上方式多包個一層應該就足夠了。
但還有另一個工具tuple可以包起多個變數，用法基本上與pair類似，直接看範例。

#include<bits/stdc++.h>
using namespace std;
int main(){
    tuple<int,int,double> a=tuple<int,int,double>(5,10,1.0);//將兩個或以上的型別用逗號分隔，語法與pair類似
    tuple<int,int,double> b=make_tuple(5,10,1.0);//make_tuple函式會自動根據填入的型別判斷回傳的tuple型別
    //以上兩種將宣告的型別寫作auto也可以
    tuple<int,int,double> c={5,10,1.0};//不可以用auto宣告

    //跟pair最大的差別可能是沒有類似.first、.second的拆解方式，只有比較抽象的拆解方法
    auto [x,y,z]=a;//將tuple a的值賦值給新變數a,b,c
    auto &[i,j,k]=a;//將tuple a內的變數取別名i,j,k

    //另外tuple同樣能比大小
}

內建函式

前面提到了STL有許多方便的函式，以下挑出最常見的介紹，都跟陣列有關，需要搭配陣列的指標，若不熟悉可以回章節1-2的指標pro複習。

事先預告一下，下面的函式會需要對「一個範圍的陣列」進行操作，而丟給函式要操作範圍的方式就是提供「起始位址」與「結束位址」，這時函式就會幫我們從「起始位址」處理到「結束位址的前一個」，沒錯，實際處理的範圍不會包含「結束位址」。
或許你會覺得很奇怪，為什麼要設計成這樣？這樣不是很難思考嗎？但其實一切都在安排裡。
假設今天剛好有一個長度為n的數列，我們將其存在陣列的a[0]~a[n-1]，對應位址a~a+n-1，但因為函式不會執行到我們給他的「結束位址」，因此要將a~a+n丟給函式，有沒有發現這個範圍看起來簡潔多了。
但相對的如果存在a[1]~a[n]就要丟給函式位址a+1~a+n+1，因此筆者才會在章節0-2時就建議將資料存在從0開始(也是伏筆！)。

由於以上概念類似於數學中「前閉後開」的區間，也就是包含範圍開頭但不包含範圍結尾，記做[a,b)，因此以下將位址first到位址last但不含last記做[first,last)

為了統一版面，以下將直接寫出函式的名稱、引數、回傳、說明、時間複雜度(忘記的建議複習章節1-1)、範例程式。

find(first, last, val)
first:填入位址；last:填入位址；val:填入與陣列中變數相同的型別
回傳:位址
說明:在[first,last)尋找val出現的第一個位址，回傳該位址，若找不到則回傳last
時間複雜度:O(n)，n為尋找範圍大小。因為尋找方式為從頭到尾判斷一遍是否等於val，所以複雜度O(n)，就算找到會提早回傳，但考慮最壞情況是找不到或者出現在隨機位置時期望值需要跑一半，複雜度仍為O(n)。

▼ find範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={0,2,4,6,8,10,12,14,16,18};
    auto pointer=find(a,a+10,8);//在a[0]~a[9]尋找8
    //auto會自動判斷型別為指向int的指標，等價於以下註解掉的程式碼
    //int *pointer=find(a,a+10,8);
    int n;
    cin>>n;
    if(find(a,a+10,n)!=a+10){//回傳非last代表有找到
        cout<<"found "<<n<<" at index "<<find(a,a+10,n)-a;//輸出「found n at index 找到的索引值」
        //如輸入「12」會輸出「found 12 at index 6」
    }else{//跑到else代表find(a,a+10,n)等於a+10，沒找到
        cout<<"not found";//輸出「not found」
        //如輸入「15」會輸出「not found」
    }
}

count(first, last, val)
first:填入位址；last:填入位址；val:填入與陣列相同的型別
回傳:int
說明:在[first,last)計算val出現的次數
時間複雜度:O(n)，n為計算範圍大小。因為要從頭到尾判斷是否等於val，故複雜度O(n)。

▼ count範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={1,2,2,3,3,3,4,4,4,4};
    cout<<count(a,a+10,3);//輸出「3」
}

reverse(first, last)
first:填入位址；last:填入位址
回傳:void，無回傳
說明:反轉[first,last)的值
時間複雜度:O(n)，n為反轉範圍大小。其實反轉就是從頭跟從尾跑，兩兩配對交換直到跑到正中間，故複雜度O(n)。

▼ reverse範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5]={1,2,3,4,5};
    reverse(a,a+5);
    for(int i=0;i<5;i++)cout<<a[i]<<' ';//輸出「5 4 3 2 1」
    //可以想想若將範圍改成(a,a+4)會輸出什麼

    //答:「4 3 2 1 5」
}

sort(first, last, cmp)
first:填入位址；last:填入位址；cmp:可留空，或填入函式或greater<與陣列相同的型別>()
回傳:void，無回傳
說明:由小到大排序[first,last)的值，若有cmp函式則依據cmp函式排序，詳細解釋請查看下方補充
時間複雜度:O(n log n)，n為排序範圍大小。關於排序演算法的原理與複雜度，請參考章節2-2。

▼ sort範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={9,8,2,4,1,3,5,0,7,6};
    sort(a,a+10);
    for(int i=0;i<10;i++)cout<<a[i]<<' ';//輸出「0 1 2 3 4 5 6 7 8 9」
    sort(a,a+10,greater<int>());//greater的意思為大於，加入greater會變成由大到小排序
    for(int i=0;i<10;i++)cout<<a[i]<<' ';//輸出「9 8 7 6 5 4 3 2 1 0」
}

▼ 補充:cmp函式解釋

cmp函式除了使用內建的升冪、降冪，也就是小到大、大到小的排序，也可以用自訂的函式排序。
而這個cmp函式的本質是一個比較的函式，就跟內建的大於小於一樣，所以回傳值必須是真值、假值的bool，然後因為是比較，所以必須有兩個同型別的參數，如下。

bool compare(string a,string b){
    if(a.size()!=b.size())return a.size()<b.size();//字串長度不一樣則回傳a長度小於b長度是否為真
    return a<b;//否則回傳a字典序小於b字典序是否為真
}

而這個比較函式的意義是什麼呢？顯然這個函式是拿來比較字串函式，所以可以用在字串陣列的排序中，但先不要考慮這個函式隨意輸入兩個字串會怎樣，我們把函式輸入的字串想成(索引值小的元素,索引值大的元素)，或者說(陣列靠前的字串,陣列靠後的字串)，此時這個函式怎麼樣才會回傳1呢，答案是「如果字串不一樣長，靠前的字串較短；否則靠前的字典序小」，為了盡量滿足這樣的條件，排序的時候「字串短的優先排前面，一樣長的照字典序排」就可以了，這正是自訂排序後的結果。

#include<bits/stdc++.h>
using namespace std;
bool compare(string a,string b){
    if(a.size()!=b.size())return a.size()<b.size();//字串長度不一樣則回傳a長度小於b長度是否為真
    return a<b;//否則回傳a字典序小於b字典序是否為真
}
int main(){
    string s[6]={"Taipei","Tainan","Tokyo","London","NewYork","Paris"};
    sort(s,s+6,compare);
    for(int i=0;i<6;i++)cout<<s[i]<<' ';
    //輸出「Paris Tokyo London Tainan Taipei NewYork」
}

用精簡的話來解讀cmp函式的運作原理，就是會讓cmp(前面元素,後面元素)皆為真。

如此一來也能理解為何加入greater<與陣列相同的型別>()會變成降冪了，greater一詞的意思是大於，因此會讓排序結果符合前面的大於後面的。

▼ sort函式的進階應用

上面已經介紹了pair，而這裡要解釋如何使用pair讓sort能處理的問題更多元。

第一個例子是，假設要對不同人的考試分數進行排名，就可以利用C++內建sort進行排序，但要如何將分數對應到每個人呢？
這時候pair的綁定功能就很重要了，由於pair會先比較first再比較second，因此可以用pair<int,string>來做到先比分數。
以下為範例程式。

#include<bits/stdc++.h>
using namespace std;
pair<int,string> p[105];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>p[i].second>>p[i].first;//先輸入人名、再輸入分數
    sort(p,p+n,greater<pair<int,string>>());//由大排到小
    for(int i=0;i<n;i++)cout<<"rank "<<i+1<<':'<<p[i].second<<", score:"<<p[i].first<<'\n';
    //範例輸入:
    //5
    //Samuel 100
    //Bob 95
    //Alice 80
    //Candy 90
    //Danny 85
    //範例輸出:
    //rank 1:Samuel, score:100
    //rank 2:Bob, score:95
    //rank 3:Candy, score:90
    //rank 4:Danny, score:85
    //rank 5:Alice, score:80
}

當然了以上程式有個小問題，如果遇到分數一樣的情況會變成以字典序由大排到小。
不過這可以用單純的條件判斷來解決，只要宣告一個變數「當前排名」，然後改成「如果i>0且第i人與第i-1人同分時，第i人排名為當前排名；否則第i人排名為i+1，且更新當前排名為i+1」就可以。

第二個例子是，輸入一個數列，對數值的個位數排列，若個位數一樣則照原本的順序排列。
這個例子的重點是照原本順序排序，假設在自訂的cmp函式中有長得不一樣但卻比不出來，或者說在cmp函式相等的元素，要怎麼保留原先的順序呢？
如果直接使用sort會發現當資料數量變多，有的順序就會被打亂。有些人可能知道C++有提供內建函式stable_sort可以做到這件事，但筆者建議可以不用多記函式，將輸入的資料與順序綁定成pair不就好了嗎，如果用first沒辦法決定誰先，那就用索引值小的吧。
以下為範例程式。

#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[105];
bool compare(pair<int,int> a,pair<int,int> b){
    if(a.first%10!=b.first%10)return a.first%10<b.first%10;
    return a.second<b.second;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p[i].first;
        p[i].second=i;
    }
    sort(p,p+n,compare);
    for(int i=0;i<n;i++)cout<<p[i].first<<' ';
    //範例輸入:
    //6
    //51 42 31 62 70 80
    //範例輸出:
    //70 80 51 31 42 62
}

lower_bound(first, last, val, cmp)
first:填入位址；last:填入位址；val:填入與陣列相同的型別；cmp:可留空，或填入函式或greater<與陣列相同的型別>()
回傳:位址
說明:必須將[first,last)先進行sort，cmp函式與sort時使用的相同，而函式會回傳在[first,last)中第一個大於等於的位址，或者在提供cmp的情況下會回傳在[first,last)中第一個等於val或排序會在val之後的位址，若無符合條件的元素會回傳last
時間複雜度:O(log n)，n為[first,last)範圍大小。使用二分搜尋實現，關於二分搜尋的原理與複雜度，請參考章節2-1。

▼ lower_bound範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={0,2,4,6,8,10,12,14,16,18};//資料已排序，以下不另外進行sort
    cout<<*lower_bound(a,a+10,8)<<' '<<*lower_bound(a,a+10,9);//輸出「8 10」
}

upper_bound(first, last, val, cmp)
first:填入位址；last:填入位址；val:填入與陣列相同的型別；cmp:可留空，或填入函式或greater<與陣列相同的型別>()
回傳:位址
說明:必須將[first,last)先進行sort，cmp函式與sort時使用的相同，而函式會回傳在[first,last)中第一個嚴格大於(即不含等於)的位址，或者在提供cmp的情況下會回傳在[first,last)中第一個不等於val且排序會在val之後的位址，若無符合條件的元素會回傳last
時間複雜度:O(log n)，n為[first,last)範圍大小。使用二分搜尋實現，關於二分搜尋的原理與複雜度，請參考章節2-1。

▼ upper_bound範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={0,2,4,6,8,10,12,14,16,18};//資料已排序，以下不另外進行sort
    cout<<*upper_bound(a,a+10,8)<<' '<<*upper_bound(a,a+10,9);//輸出「10 10」
}

這時或許有人在思考，那如果要找到小於等於或嚴格小於特定值之最大值的函式呢？
將sort與lower_bound、upper_bound都加上cmp函式greater<型別>是個方法，但不推薦，有更好的。
考慮到我們可以用lower_bound在預設排序下找到大於等於特定值的最小值，那麼其前一個數(位址是lower_bound-1)其實就是嚴格小於特定值的最大值，但須注意若lower_bound之值已經是最小值就代表沒有嚴格小於特定值的最大值。(該結果之證明可以直接帶數字嘗試或者以數學下去思考，此處不贅述)
同理，upper_bound在預設排序下找到嚴格大於特定值的最小值，其前一個數(位址是upper_bound-1)就是小於等於特定值的最大值。

accumulate(first, last, val)
first:填入位址；last:填入位址；val:填入與陣列相同或可以相加的型別
回傳:與val相同的型別
說明:將[first,last)的所有值加到以val為初始值的變數上，或者說回傳val加上[first,last)的總和
時間複雜度:O(n)，n為[first,last)範圍大小。其實也是從頭到尾一個一個加，故複雜度O(n)。
註:若相加總合會超過int範圍，記得把val值型別改為long long int。

▼ accumulate範例程式

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5]={1,3,5,7,9};
    cout<<accumulate(a,a+5,0);//輸出「25」
}