# 常用容器 container
# Vector
簡單的講就是動態的陣列，大小可以是 0 到無限大
- 標頭檔：<vector>
- v [i]：v 的第 i 項
- v.size ()：回傳 v 目前的長度
- v.push_back (T a)：在 v 的結尾加一個 a
- v.pop_back ()：刪除 v 的最末項，若 v 為空，會發生無法預期的結果
- v.empty ()：回傳一個 bool，表示 v 是否為空的
- v.clear ()：清空 v，但原本的空間不會被釋放掉。
# 範例 1
#include<iostream> | |
#include<vector> | |
using namespace std; | |
vector <int> v; | |
int main(){ | |
v.push_back(10); //[10] | |
v.push_back(20); //[10 , 20] | |
v.push_back(30); //[10 , 20 , 30] | |
int length = v.size(); | |
for(int i = 0; i < length;i++) | |
cout << v[i] << " "; //10 20 30 | |
} |
# 範例 2
#include<iostream> | |
#include<vector> | |
using namespace std; | |
vector <int> v; | |
int main(){ | |
v.push_back(10); //[10] | |
v.push_back(20); //[10 , 20] | |
v.pop_back(); //[10] | |
v.push_back(30); //[10 , 30] | |
int length = v.size(); // = 2 | |
for(int i = 0; i < length;i++) | |
cout << v[i] << " "; //10 20 30 | |
} |
另外，vector 也可以像是 array 一樣，(預) 開設一個固定的大小，用 v () 來控制
# 範例 3
#include<iostream> | |
#include<vector> | |
using namespace std; | |
vector <int> v(5); // int v[5]={ }; | |
int main(){ | |
int length = v.size(); // length = 5 | |
for(int i = 0;i<length;i++) | |
v[i] = i * 10; // [ 0 , 10 , 20 , 30 , 40 ] | |
for(int i = 0;i<length;i++) | |
cout<<v[i]<<" "; // 0 10 20 30 40 | |
} |
# deque
- 位於 <deque> 標頭檔。
- 可視為可以在最前面加東西刪東西的 vector。
- d.pop_front (): 刪掉最前面的東西
- d.push_front (a): 在最前面加東西
- d.pop_back (): 刪掉最後面的東西
- d.push_back (a): 在最後面加東西
- 時間和空間複雜度很爛，沒事不要用 deque。
# Stack
Stack 就像是疊盤子，最先放置的會壓在最下面，最先放的會先拿出，有 First in,Last out 的特性
- 標頭檔：<stack>
- st.push (): 疊上一個盤子
- st.pop (): 把最上方的盤子移除掉
- st.top (): 取得最上面的值
- st.size (): 目前的盤子數
- st.empty (): 當沒有值的時候會 true
# 範例 1
#include<iostream> | |
#include<stack> | |
using namespace std; | |
stack <int> st; | |
int main(){ | |
st.push(10); //| 30 | | |
st.push(20); //| 20 | | |
st.push(30); //|_10_| | |
while(!st.empty()){ | |
cout<<st.top()<<" "; // 30 20 10 | |
st.pop(); | |
} | |
} |
# Queue
Queue 就像是排隊買東西，從尾巴進，前頭出來，有 First in,First out 的特性
- 標頭檔：<queue>
- q.push (): 把一個值加到尾巴
- q.pop (): 把第一個值移除掉
- q.back (): 得到尾巴的值
- q.front (): 得到頭的值
- q.empty (): 當 queue 沒有值的時候會 true
#include<iostream> | |
#include<queue> | |
using namespace std; | |
queue <int> q; | |
int main(){ | |
for(int i = 0;i<5;i++) | |
q.push(i*10); //[0 , 10 , 20 , 30 , 40] | |
while(!q.empty()){ | |
cout<<q.front()<<" "; | |
q.pop(); | |
} | |
} |
# priority_queue
priority_queue，就是 queue 的變種，內建了函式實現 binary heap 結構，可以維持最頂的元素永遠是最大 (最小) 的
- 標頭檔: <queue>
- pq.push (a): 將 a 加入 pq 內部
- pq.pop (): 將 pq 中最大 (最小) 的元素移除
- pq.top (): 回傳 pq 中最大 (最小) 的元素
- pq.empty (): 判斷還有沒有值在裡面
# 範例 1
#include<iostream> | |
#include<queue> | |
using namespace std; | |
priority_queue <int> pq; // 由大到小排列 (最大優先) | |
// priority_queue<int,vector<int>,less<int> >pq; | |
int main(){ | |
pq.push(30); //[30] | |
pq.push(50); //[50 , 30] | |
pq.push(20); //[50 , 30 , 20] | |
pq.push(80); //[80 , 50 , 30 , 20] | |
pq.pop(); //[50 , 30 , 20] | |
while(!pq.empty()){ | |
cout<<pq.top()<<" "; // 50 30 20 | |
pq.pop(); | |
} | |
} |
# 範例 2
#include<iostream> | |
#include<queue> | |
using namespace std; | |
priority_queue<int,vector<int>,greater<int> >pq;// 由小到大排列 (最小優先) | |
int main(){ | |
pq.push(30); //[30] | |
pq.push(50); //[30 , 50] | |
pq.push(20); //[20 , 30 , 50] | |
pq.push(80); //[20 , 30 , 50 , 80] | |
pq.pop(); //[30 , 50 , 80] | |
while(!pq.empty()){ | |
cout<<pq.top()<<" "; // 30 50 80 | |
pq.pop(); | |
} | |
} |
# Map
Map 就像是一個對應表，也就像是 Python 的字典
- 標頭檔：<map>
- mp []: 得到對應的值
- mp.count (): 檢查某個值是否有對應值
# 範例 1
#include<iostream> | |
#include<map> | |
using namespace std; | |
map <string,int> mp; // string -> int | |
int main(){ | |
mp["one"] = 1; | |
mp["two"] = 2; | |
cout<<mp.count("one")<<endl; //--> 1 (有對應) | |
cout<<mp.count("two")<<endl; //--> 1 (有對應) | |
cout<<mp.count("ten")<<endl; //--> 0 (無對應) | |
} |
# 範例 2
#include<iostream> | |
#include<map> | |
using namespace std; | |
map <string,int> mp; // string -> int | |
int main(){ | |
mp["one"] = 1; | |
mp["two"] = 2; | |
mp["three"] = 3; | |
cout<<mp["two"]<<endl; // -->2 | |
cout<<mp["ten"]<<endl; // -->0 | |
} |
# Set
顧名思義，就只是個集合
- 標頭檔：<set>
- s.insert (): 把一個數字放進集合
- s.erase (): 把某個數字從集合中移除
- s.count (): 檢查某個數是否有在集合中
# 範例 1
#include<iostream> | |
#include <set> | |
using namespace std; | |
set <int> s; | |
int main(){ | |
s.insert(20); // s = {20} | |
s.insert(10); // s = {10, 20} | |
s.insert(30); // s = {10, 20, 30} | |
cout << s.count(20) << endl; // 存在 -> 1 | |
cout << s.count(100) << endl; // 不存在 -> 0 | |
s.erase(20); // s = {10, 30} | |
cout << s.count(20) << endl; // 0 | |
} |
# multiset,multimap
在 <set>,<map> 中分別有 multiset 和 multimap，與前面的差不多，唯一的差別在於 multiset 和 multimap 中鍵值可以重複出現。
# 疊代器 iterator
叠代器提供對一個容器中的對象的訪問方法。叠代器就如同一個指針，叠代器是一種檢查容器內元素並遍歷元素的數據類型。
標準庫為每一種標準容器（包括 vector）定義了一種叠代器類型。
# iterator 類型
每個標準庫容器類型都定義了一個名為 iterator 的成員，用來定義自己的叠代器。如：
vector<int>::iterator iter; | |
stack<int>::iterator iter; |
# begin 和 end 操作
每種容器都定義了一對命名為 begin 和 end 的函數，用於返回叠代器。如果容器中有元素的話，由 begin 返回的叠代器指向第一個元素：
vector<int>::iterator iter = v.begin(); |
把 iter 初始化為由名為 vector 操作返回的值。假設 vector 不空，初始化後，iter 即指該元素為 v [0]。
vector<int>::iterator iter2 = v.end() |
由 end 操作返回的叠代器指向 vector 的末端元素的下一個，被稱為超出末端叠代器。
# 叠代器支持的其他方法
比較：用 == 或！= 操作符來比較兩個叠代器，如果兩個叠代器對象指向同一個元素，則它們相等，否則就不相等。
使用叠代器遍歷容器：
vector<int>::iterator iter = v.begin() | |
for (; iter != v.end(); ++iter) | |
cout<<*iter<<endl; | |
//------------------------------------------------- | |
for (int i = 0;i < v.size();i++) | |
cout<<v[i]<<endl; |
# 叠代器的算術操作
除了一次移動叠代器的一個元素的增量操作符外，vector 叠代器也支持其他的算術操作。包括：
iter + n | |
iter - n | |
iter1 - iter2 | |
vector<int>::iterator mid = v.begin() + v.size() / 2; |
