STL(Standard Template Library)-程式設計筆記

STL(Standard Template Library)

Vector

• 用法基本跟array一樣，可以把它想成動態陣列。
• 宣告時可以不用確定大小
• 宣告一向量時，所有範圍內的值會被初始成0。
• 可以使用'=='比較兩向量時
• 使用'='時，會將一向量的值賦予到另一向量。
• vector v2(v1);=>複製v1到v2。
• 集合尾端增刪元素很快 : O(1)
• 集合中間增刪元素比較費時 : O(n)
• erase(a, b); => 刪除 .
• begin()=>第一個元素
• end()=>最後一個元素的下一個(沒有值)
• erase(v.begin(), v.end()) => erase every elements.
• pop_back()只會將vector的大小做修改，但值還是會存在原本的位置。
• vector[100]=vectorat(100);
  • 使用"[]"並不會在超過向量大小時顯示錯誤。
  • 使用".at()"會在超過向量大小時顯示錯誤。

用法1(push_back and pop_back):

#include <iostream>
#include <vector>
using namespace std;
int main(){
	vector<int> vec; //declaration of vector
	for(int i=1; i<=3; i++){
		vec.push_back(i);	//push_back to put elements into vector
	}
	cout<<vec.size()<<"\n";	
	for(int i=0; i<3; i++){
		cout<<vec[i]<<"\n";	//cout each element
	}
	for(int i=0; i<3; i++){
		vec.pop_back();	//pop_back to remove the last element from the vector
	}
	cout<<vec.size()<<"\n";	
}

用法二(insert and erase)

#include <iostream>
#include <vector>
using namespace std;
int main(){
	vector<int> vec;
	for(int i=0; i<3; i++){
		if(i==1) continue;
		else vec.push_back(i+1); 
	}
	for(int i=0; i<vec.size(); i++){
		cout<<vec[i]<<' ';				//cout 1 3
	}
	cout<<"\n";
	vec.insert(vec.begin()+1, 2);
	for(int i=0; i<vec.size(); i++){
		cout<<vec[i]<<' ';				//cout 1 2 3
	}
	cout<<"\n";
	vec.erase(vec.begin()+1);
	for(int i=0; i<vec.size(); i++){
		cout<<vec[i]<<' ';				//cout 1 3
	}
}

用法三(empty(), size(), resize(), capacity(), reserve()) Reference:link

#include <iostream>
#include <vector>
using namespace std;
int main(){
	vector<int> vec;
	if(vec.empty()){
		cout<<boolalpha<<vec.empty()<<'\n';
		cout<<"size of vector "<<vec.size()<<'\n'; 
	}
	vec.resize(3);		
	cout<<vec.size()<<'\n';		//current size
	cout<<vec.capacity()<<'\n';		//current maximum capacity
	vec.reserve(4);		
	cout<<vec.size()<<'\n';
    cout<<vec.capacity()<<"\n";
}

• capacity and size
  • 容量 (capacity) : 是這個 vector 擁有的空間。
  • 長度 (size) : 是實際儲存了元素的空間大小。capacity 永遠不小於 size。
• reserve() vs resize()
  • reserve() 的目的是擴大容量。做完時，vector 的長度不變，capacity 只會長大不會縮小，資料所在位置可能會移動 (因為會重配空間)。因為 vector 一開始是空的，立刻預留顯然比填了資料後才預留省了拷貝資料的時間。
  • resize() 的目的是改變 vector 的長度。做完時，vector 的長度會改變為指定的大小，capacity 則視需要調整，確保不小於 size，資料所在位置可能會移動。如果變小就擦掉尾巴的資料，如果變大就補零。補零如果會超過容量，會做重配空間的動作。
  • 白話文就是reserve()創造空間，但沒有隨機產生值，因此不能做訪問。resize()則是除了創造空間，也隨機產生值，故可直接訪問。
• 二維vector
  • 將眾多一維vector塞入二維vector。

Ex:

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<vector<int>> test_2D;
    for(int i=0; i<3; i++){
        vector<int> temp;
        static int counter=1;
        for(int j=0; j<3; j++){
            temp.push_back(counter);
            counter++;
        }
        test_2D.push_back(temp);
    }
    for(int i=0; i<test_2D.size(); i++){
        for(int j=0; j<test_2D[0].size(); j++){
            cout<<test_2D[i][j]<<" ";
        }
        cout<<"\n";
    }
}

Result:

Queue

• 僅能取得(操作)頭與尾的element.
• 具有fifo(first in first out)的特性.
• 用法1(push(), pop(), front(), back(), size(), empty())

#include <iostream>
#include <queue>
using namespace std;
int main(){
	queue<int> q;
	for(int i=0; i<3; i++){
		q.push(i+1);	//adding elements
	}
	cout<<"Size: "<<q.size()<<"\n";
	cout<<"First element: "<<q.front()<<"\n";
	cout<<"Last element: "<<q.back()<<"\n";
	for(int i=0; i<3; i++){
		q.pop();		//remove the first element
	}
	if(q.empty()){
		cout<<boolalpha<<q.empty(); //return 1 if q is empty
	}
}

Stack

• 僅能取得(操作)最上層的element.
• 具有lifo(last in first out)的特性.

用法1(psuh(), pop(), top(), size(), empty())

#include <iostream>
#include <stack>
using namespace std;
int main(){
	stack<int> s;
	for(int i=0; i<3; i++){
		s.push(i+1);    //not reference
	}
	cout<<"Size: "<<s.size()<<"\n";
	cout<<"The top stack: "<<s.top()<<"\n"; //reference
	s.pop();	//removing the first stack
	cout<<"Size:"<<s.size()<<"\n";
	for(int i=0; s.size()!=0; i++){
		s.pop();
	}
	cout<<"size: "<<s.size()<<"\n";
	if(s.empty()){
		cout<<"empty"<<"\n";
	}
}

Set

• 就是集合。
• 可用於快速查找elements 是否存在。
• 每個elements皆是唯一的，不可重複。
• 每個elements皆不能做修改。
• 具有順序性。
• 操作簡單。
• elements 太多會拖慢速度。

用法1(insert(), count(), erase(), clear(), empty())

#include <iostream>
#include <set>
using namespace std;
int main(){
    set<int> s;
    for(int i=10;i<=50; i+=10){
        s.insert(i);
    }
    if(s.count(10)){
        cout<<boolalpha<<true<<"\n";
    }
    s.erase(10);
    if(s.count(10)){
        cout<<boolalpha<<true<<"\n";
    }
    else{
        cout<<boolalpha<<false<<"\n"; 
    }
    s.clear();
    if(s.empty()){
        cout<<"empty"<<'\n';
    }

}

Map

• 有排序關聯式容器。
• map中的元素會根據對應的鍵值(key)做排序。
• 鍵值具有唯一性。
• 高效率，使用簡單。

用法1(insert(), erase(), clear(), empty())

#include <iostream>
#include <map>
#include <cstring>
using namespace std;
int main(){
    //initialization
    map<string, int> m ={
        {"One", 1},
        {"Two", 2},
        {"Three", 3}
    };
    m.insert(pair<string, int>("Four", 4));
    m["Five"]=5;
    cout<<m["Five"]<<"\n";
    m.erase("Five");
    cout<<m.size()<<"\n";
    m.clear();
    if(m.empty()){
        cout<<"empty"<<"\n";
    }
}

Algorithm

• 常用演算法。

用法1(sort(), reverse())

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    vector<int> v;
    int input;
    while(cin>>input&&input!=-1){
        v.push_back(input);
    }
    sort(v.begin(), v.end());
    for(int i=0; i<v.size(); i++){
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    reverse(v.begin(), v.end());
    for(int i=0; i<v.size(); i++){
        cout<<v[i]<<" ";
    }
}