內容
- vector:不定長數組
- map:映射
- queue:隊列
- sort:排序
- priority_queue:優先隊列
vector:不定長數組
1 #include <cstdio> 2 #include <iostream> 3 #include <vector> //相關頭文件 4 using namespace std; 5 6 int main(){ 7 //vector(不定長數組)用法介紹 8 vector<int> G; //創建vector 9 G.push_back(5); //加入元素5, 類似于棧 10 G.push_back(3); //加入元素3 11 G.push_back(7); //加入元素7 12 //這時vector里面有元素: 5, 3, 7 13 14 //訪問 15 int a; 16 a = G[0]; //a被賦值為vector里面的第一個元素，即a = 5 17 a = G[1]; //a被賦值為vector里面的第二個元素，即a = 3 18 19 //獲得vector的大小: G.size() //這里是遍歷vector里面的元素 20 for(int i = 0; i < G.size(); i++){ 21 printf("%d\n", G[i]); 22 //這里G.size() == 3, 所以輸出G[0], G[1], G[2] 23 } 24 printf("\n"); 25 26 //高級用法: vector數組 27 vector<int> g[3]; 28 //這里創建了3個vector, 其中分別是g[0], g[1], g[2] 29 g[1].push_back(4); //向g[1]這個vector加入元素4 30 g[1].push_back(1); //向g[1]這個vector加入元素1 31 32 //訪問 33 a = g[1][0]; //a被賦值為g[1]里面的第一個元素，即a = 4 34 a = g[1][1]; //a被賦值為g[1]里面的第二個元素，即a = 1 35 36 for(int i = 0; i < g[1].size(); i++){ 37 printf("%d\n", g[1][i]); 38 //這里g[1].size() == 2, 所以輸出g[1][0], g[1][1] 39 } 40 41 return 0; 42 }
map:映射
1 #include <cstdio> 2 #include <iostream> 3 #include <map> 4 #include <string> 5 using namespace std; 6 7 int main(){ 8 //map用法介紹 9 map<string, int> mp; //創建一個map: 從string到1的映射 10 mp["abc"] = 1; //建立從字符串"abc"到整數1的映射 11 string s = "efg"; //創建一個string 12 mp[s] = 5; //建立從字符串"efg"到整數5的映射 13 14 //訪問 15 int a; 16 a = mp["abc"]; //這時mp["abc"]的值為1, 也就是a = 1 17 cout << a << endl; 18 a = mp[s]; //這時mp[s]的值為5, 也就是a = 5 19 cout << a << endl; 20 21 //使用char數組 22 char s2[5] = "gsd"; 23 mp[s2] = 9; //建立從字符串"gsd"到整數9的映射 24 cout << mp[s2] << endl; 25 26 //最后注意的是, 雖然map看起來很像hash, 但其內部實現不是hash, 而是一顆樹(紅黑樹) 27 //也就是說, 當進行訪問map的操作時, 時間復雜度為O(log m)(m為映射數量), 并不是O(1) 28 29 return 0; 30 }
queue:隊列
1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 using namespace std; 5 6 int main(){ 7 //queue基本用法 8 queue<int> q; //創建一個先進先出的隊列(也就是這個隊列只能在尾部加入元素, 頭部取出元素, 這個是關鍵) 9 q.push(1); //加入元素1 10 q.push(2); //加入元素2 11 q.push(3); //加入元素3 12 //這時隊列是: 1, 2, 3 13 14 //訪問 15 int a; 16 a = q.front(); //這時q.front()的值為1, 所以a = 1, 注意這里只是讀取隊列首元素, 并沒有彈出元素 17 cout << a << endl; 18 a = q.front(); 19 cout << a << endl; 20 21 //彈出 22 q.pop(); //彈出隊列的首元素, 也就是變成2, 3 23 a = q.front(); 24 cout << a << endl; 25 26 //判斷隊列是否為空 27 q.pop(); //彈出隊列的首元素, 也就是變成3 28 q.pop(); //彈出隊列的首元素, 此時隊列為空 29 if(q.empty()) cout << "Yes\n"; //如果隊列為空, 則q.empty()為真, 則輸出"Yes" 30 if(q.size() == 0) cout << "Yes\n"; //如果隊列大小為0, 則輸出"Yes" 31 32 return 0; 33 }
sort:排序
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 using namespace std; 5 //先從主函數看 6 7 struct node{ 8 int first, second; 9 }; 10 11 bool cmp1(int x, int y){ 12 return x > y; //從大到小排 13 } 14 15 bool cmp2(int x, int y){ 16 return x < y; //從小到大排 17 } 18 19 bool cmp_node(node x, node y){ 20 if(x.first == y.first) return x.second < y.second; 21 else return x.first < y.first; 22 //這里的意思: 優先對結構體的第一個值進行排序, 如果第一個值相等, 就按照第二個值進行排序 23 } 24 25 int main(){ 26 //sort的用法 27 int a[5] = {5,4,3,2,1}; 28 sort(a, a+5); //默認對數組a進行從小到大排序 29 for(int i = 0; i < 5; i++){ 30 cout << a[i] << " "; 31 } 32 cout << endl; 33 34 string s[3] = {"bcd", "abc", "a"}; 35 sort(s, s+3); //默認對字符串進行字典序排序 36 for(int i = 0; i < 3; i++){ 37 cout << s[i] << endl; 38 } 39 cout << endl; 40 41 //自定義比較級(比較函數): 42 sort(a, a+5, cmp1); //按cmp1的比較級排序, 注意這里cmp1后面不能加() 43 for(int i = 0; i < 5; i++){ 44 cout << a[i] << " "; 45 } 46 cout << endl; 47 48 sort(a, a+5, cmp2); //按cmp2的比較級排序 49 for(int i = 0; i < 5; i++){ 50 cout << a[i] << " "; 51 } 52 cout << endl; 53 54 cout << endl; 55 //對結構體進行排序 56 node G[3] = {{5,3}, {5, 2}, {1, 9}}; 57 sort(G, G+3, cmp_node); //按照cmp_node進行排序 58 for(int i = 0; i < 3; i++){ 59 printf("G[%d]: %d %d\n", i, G[i].first, G[i].second); 60 } 61 cout << endl; 62 63 return 0; 64 }
priority_queue:優先隊列
1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 //從主函數看起 7 8 struct node{ 9 int first, second; 10 }; 11 12 struct cmp1{ //這里比較級是用結構體, 而不是函數 13 bool operator () (int a, int b){ //重載操作, 記住就行 14 return a > b; 15 //小的優先在前面, 因為是用"堆"去實現的, 不清楚堆就直接記住和sort的cmp剛好相反 16 } 17 }; 18 19 struct cmp2{ 20 bool operator () (node a, node b){ 21 if(a.first == b.first) return b.second > b.second; 22 return a.first > b.first; 23 } 24 }; 25 26 int main(){ 27 //priority_queue基本用法 28 priority_queue<int> q; //創建一個優先隊列 29 q.push(1); //加入元素1 30 q.push(3); //加入元素3 31 q.push(2); //加入元素2 32 33 if(!q.empty()) printf("YES\n"); //q.empty():判斷優先隊列是否為空 34 35 int a; 36 while(!q.empty()){ 37 a = q.top(); //這里只是讀取隊列首元素, 并沒有彈出元素 38 printf("%d ", a); 39 q.pop(); //彈出首元素 40 } 41 printf("\n"); 42 //運行上面程序，發現輸出為:3, 2, 1, 也就是說, 默認優先隊列默認從大到小排列 43 44 priority_queue<int, vector<int>, less<int> > q_less; 45 //創建一個優先級為:從大到小, 排的優先隊列 46 47 priority_queue<int, vector<int>, greater<int> > q_great; 48 //創建一個優先級為:從小到大, 排的優先隊列 49 50 priority_queue<int, vector<int>, cmp1> q_cmp1; 51 //自定義比較級:cmp1 52 53 priority_queue<node, vector<node>, cmp1> q_cmp1; 54 //自定義比較級:cmp2 55 return 0; 56 }
c++中的std？?
