章節1-4.STL(二)

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> v;//宣告時v為空
    if(v.empty())cout<<"v is empty\n";//輸出「v is empty」
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    //依序在末端新增1,2,3
    cout<<"v has "<<v.size()<<" elements\n";//輸出「v has 3 elements」
    for(int i=0;i<v.size();i++)cout<<v[i]<<' ';//輸出「1 2 3」
    cout<<'\n';
    
    v.pop_back();//移除末端的元素，即3，v變為「1,2」
    cout<<"v has "<<v.size()<<" elements\n";//輸出「v has 2 elements」
    for(int i=0;i<v.size();i++)cout<<v[i]<<' ';//輸出「1 2」
    cout<<'\n';
}

與pair<int,int>(5,10)回傳一個內容為「5,10」的pair類似，在vector<型別>後打上括號，可以填入兩個數字分別為大小、初始值(也可只填大小，此時初始值自動帶0)，如「vector<int>(100,1)」會回傳包含100個1的vector、「vector<int>(10)」回傳包含10個0的vector，若搭配此進行宣告可使用auto。

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> v;
    for(int i=0;i<10;i++)v.push_back(i);//v之內容為「0,1,2,...,9」
    cout<<"v.begin() is "<<*v.begin()<<'\n';//輸出「v.begin() is 0」
    cout<<"v.end()-1 is "<<*(v.end()-1)<<'\n';//輸出「v.end()-1 is 9」
    //因v.end()無存值，屬v之範圍外，執行如*v.end()的操作會導致程式掛掉
    for(auto it=v.begin();it!=v.end();it++)cout<<*it<<' ';//輸出「0 1 2 ... 9」
    //考慮先前章節0-2對for的解讀，it會從v.begin()，每次向後跑一位，直到it!=v.end()不符合，此時it指向v的範圍外，直接跳出迴圈就不會造成程式掛掉
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> v;
    for(int i=0;i<10;i++)v.push_back(i);
    for(int i:v)cout<<i<<' ';//輸出「0 1 2 ... 9」
    cout<<'\n';
    //以上程式會將v從頭到尾跑過一遍，並將每個元素賦值給新變數i來執行迴圈內容
    //我習慣念其中的:為in，因為int i in v解讀成「在v內的int i」會好懂很多
    for(int &i:v)i*=2;
    cout<<v[5];//輸出「10」
    //與章節1-2提到的一樣，宣告時加&為取別名，此時變數i等價於v中元素，會將v中的元素逐個以i為別名執行迴圈內容

    //以上for迴圈內的宣告皆可用auto取代
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(3);
    //依次插入5、1、3、3，但由於set不儲存重複元素，故3僅儲存一次
    cout<<"s has "<<s.size()<<" elements\n";//輸出「s has 3 elements」
    for(int i:s)cout<<i<<' ';//STL set儲存方式為將元素排列，輸出「1 3 5」
    cout<<'\n';
    //遍歷set元素的方式有二，一是如vector遍歷的快速寫法一樣，只不過由於改變set的元素會導致儲存順序改變，因此不允許改變set之元素，也就不能使用int &i的方式來為s之元素取別名
    //方式二是利用迭代器，後續再進行介紹

    s.erase(1);
    cout<<"s has "<<s.size()<<" elements\n";//輸出「s has 2 elements」
    for(int i:s)cout<<i<<' ';//STL set儲存方式為將元素排列，輸出「3 5」
    cout<<'\n';
    cout<<s.count(1)<<' '<<s.count(3);//輸出「0 1」
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(3);
    for(auto it=s.begin();it!=s.end();it++)cout<<i<<' ';//輸出「1 3 5」
    cout<<'\n';
}

如果對前述STL函式夠熟悉，應該會記得sort也是將資料進行排序，複雜度為O(n log n)。
但使用set進行n次insert，會得到同為O(n log n)的複雜度(雖然看似是log 1+log 2+...+log n，但由於log增長速度為遞減，大部分項目的數值會接近log n，總和趨近n log n)。
那是否可以用set來替代sort呢？
答案是不建議，因為最初介紹複雜度時有提到我們會把其係數消掉，因此雖然複雜度看似一樣，但實際上可能會有數倍甚至數十倍的時間差異，而set由於其功能強、實作細節複雜，操作花費實際時間略長，最後效率是較sort差許多的。
但如果估算結果(數字帶入，log部分用以2為底的log₂計算)低於10⁸則可以考慮在set較易實作時用set偷懶。

#include<bits/stdc++.h>
using namespace std;
int main(){
    multiset<int> ms;
    ms.insert(5);
    ms.insert(1);
    ms.insert(3);
    ms.insert(3);
    for(int i:ms)cout<<i<<' ';//輸出「1 3 3 5」
    cout<<'\n';
    ms.erase(3);
    for(int i:ms)cout<<i<<' ';//輸出「1 5」
    cout<<'\n';
    //若改為ms.erase(ms.find(3));，則只會刪除一個，輸出會是「1 3 5」
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    map<string,int> m;
    m["Samuel"]=5;//若直接使用不存在map內的key，會自動新增進去並賦值，等同m.insert({"Samuel",5});
    cout<<m["Samuel"]<<'\n';//輸出「5」
    m["Alice"]=10;
    m.insert({"Bob",15});
    cout<<"m has "<<m.size()<<" elements\n";//輸出「m has 3 elements」
    for(auto p:m)cout<<p.first<<','<<p.second<<' ';//輸出「Alice,10 Bob,15 Samuel,5」
    cout<<'\n';

    //需要注意若存取了未出現的key會自動新增一項，建議若有key不在map內的可能，先用m.count()來確認是否存在
    cout<<m["Allen"]<<'\n';//輸出「0」，因為該key不存在且並未直接賦值value，會自動設為0
    cout<<"m has "<<m.size()<<" elements\n";//輸出「m has 4 elements」
    for(auto p:m)cout<<p.first<<','<<p.second<<' ';//輸出「Alice,10 Allen,0 Bob,15 Samuel,5」
}

上面提到若需取值再取成員，需要把取值的部分()起來先做，但這樣並不好寫，因此C++有->運算，我習慣稱其箭頭，可以做到對指標或迭代器取其值的成員，如「it->second」等同「(*it).second」