###### tags: `程設筆記`
{%hackmd theme-dark %}
# STL(Standard Template Library)
## Vector
* 用法基本跟array一樣，可以把它想成動態陣列。
* 宣告時可以不用確定大小
* 宣告一向量時，所有範圍內的值會被初始成0。
* 可以使用'=='比較兩向量時
* 使用'='時，會將一向量的值賦予到另一向量。
* vector<int> v2(v1);=>複製v1到v2。
* 集合尾端增刪元素很快 : O(1)
* 集合中間增刪元素比較費時 : O(n)
* erase(a, b); => 刪除 $[a,b)$.
* begin()=>第一個元素
* end()=>最後一個元素的下一個(沒有值)
* erase(v.begin(), v.end()) => erase every elements.
* pop_back()只會將vector的大小做修改，但值還是會存在原本的位置。
* vector[100]=vector$.$at(100);
* 使用"[]"並不會在超過向量大小時顯示錯誤。
* 使用".at()"會在超過向量大小時顯示錯誤。
用法1(push_back and pop_back):
```c++=
#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)
```c++=
#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:https://stackoverflow.com/questions/7397768/choice-between-vectorresize-and-vectorreserve
```c++=
#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。
```c++=
#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())
```c++=
#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())
```c++=
#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())
```c++=
#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())
```c++=
#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())
```c++=
#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]<<" ";
}
}
```
Sign in with Wallet
Connect another wallet