map和set的使用及top K問題
- 2019 年 11 月 12 日
- 筆記
1.map和set的應用和比較
map和set都是關聯式容器，底層容器都是紅黑樹。
map以鍵值對的形式進行存儲，方便進行查找，關鍵詞起到索引的作用，值則表示與索引相關聯的數據，以紅黑樹的結構實現，插入刪除等操作都可以在O(log n)時間內完成。
- 所有元素都是鍵+值存在，key=value組成pair，是一組映射關係。
- 不允許鍵重複
- 所有元素是通過鍵進行自動排序的
- map的鍵是不能修改的，但是其鍵對應的值是可以修改的
1 #include<string> 2 #include<vector> 3 4 //模擬pair和 make_pair的底層實現 5 //template<class K, class V> 6 //struct pair 7 //{ 8 // K first; 9 // V second; 10 // 11 // pair(const K& key, const V& value) 12 // :first(key) 13 // , second(value) 14 // {} 15 //}; 16 //template<class K, class V> 17 //pair<K, V> make_pair(const K& key, const V& value) 18 //{ 19 // return pair<K, V>(key, value); 20 //} 21 22 //vector<string> GetTopKF(const vector<string>& fruits) 23 //{ 24 // vector<string> topk; 25 // typedef map<string, int> CountTop; 26 // typedef map<string, int>::iterator CountIt; 27 // CountTop counttop; 28 // for (size_t i = 0; i < fruits.size(); i++) { 29 // CountIt countit = counttop.find(fruits[i]); 30 // if (countit != counttop.end()) 31 // (countit->second)++; 32 // else 33 // //counttop.insert(pair<string, int>(fruits[i], 1)); 34 // counttop.insert(make_pair(fruits[i], 1)); 35 // } 36 // return topk; 37 //} 38 vector<string> GetTopKF(const vector<string>& fruits) 39 { 40 vector<string> topk; 41 typedef map<string, int> CountTop; 42 typedef map<string, int>::iterator CountIt; 43 CountTop counttop; 44 for (size_t i = 0; i < fruits.size(); i++) { 45 /*pair<CountIt, bool> retKV = counttop.insert(make_pair(fruits[i], 1)); 46 if (retKV.second == false) 47 { 48 retKV.first->second++; 49 }*/ 50 counttop[fruits[i]]++; 51 } 52 return topk; 53 } 54 55 56 void MapTest() 57 { 58 typedef map<string, string> Dict; 59 typedef map<string, string>::iterator DictIt; 60 Dict dict; 61 dict.insert(pair<string, string>("right", "右邊")); 62 dict.insert(pair<string, string>("left", "左邊")); 63 dict.insert(pair<string, string>("世界", "你好")); 64 dict.insert(pair<string, string>("hello", "word")); 65 dict.insert(pair<string, string>("key", "鍵值")); 66 67 DictIt dictit = dict.begin(); 68 while (dictit != dict.end()) { 69 cout << (*dictit).first << " " << (*dictit).second << endl; 70 ++dictit; 71 } 72 DictIt ret = dict.find("left"); 73 if(ret != dict.end()) 74 dict.erase(ret); 75 vector<string> v; 76 v.push_back("梨"); 77 v.push_back("蘋果"); 78 v.push_back("西瓜"); 79 v.push_back("香蕉"); 80 v.push_back("西瓜"); 81 v.push_back("香蕉"); 82 v.push_back("菠蘿"); 83 v.push_back("西瓜"); 84 v.push_back("草莓"); 85 GetTopKF(v); 86 }
set支援高效的關鍵字查詢操作—檢查每一個給定的關鍵字是否在set中，也支援高效插入刪除。
以平衡二叉檢索樹實現，查找使用中序遍歷演算法，檢索效率高於vector，deque，list等容器，另外使用中序遍歷可將鍵值按照從小到大遍歷出來，構造set集合的主要目的是為了快速檢索，不可直接去修改鍵值。
- 所得元素的只有key沒有value，value就是key
- 不允許出現鍵值重複
- 所有的元素都會被自動排序
- 不能通過迭代器來改變set的值，因為set的值就是鍵
1 #pragma once 2 #include<iostream> 3 #include<set> 4 #include<map> 5 6 using namespace std; 7 8 void SetTest() 9 { 10 set<int> s1; //沒有數據冗餘 11 s1.insert(4); 12 s1.insert(5); 13 s1.insert(7); 14 s1.insert(7); 15 s1.insert(14); 16 s1.insert(7); 17 s1.insert(9); 18 s1.insert(3); 19 s1.insert(0); 20 s1.insert(30); 21 s1.insert(14); 22 s1.insert(6); 23 s1.insert(28); //set的插入操作 24 25 set<int>::iterator ite = s1.begin(); 26 //ite = 10; 27 while (ite != s1.end()) { //利用迭代器遍歷列印數據 28 cout<<*ite<<" "; 29 ite++; 30 } 31 cout << endl; 32 set<int>::reverse_iterator ret1= s1.rbegin(); 33 while (ret1 != s1.rend()) { //降序列印 34 cout << *ret1 << " "; 35 ret1++; 36 } 37 38 set<int>::iterator ret = s1.find(10); // 39 if (ret != s1.end()) //set的查找，如果沒有找到不會報錯 40 cout << "find it" << *ret << endl; 41 else 42 cout << "null" << endl; 43 44 if (s1.count(14))//只判斷是否存在14，返回1或0 45 cout << "find it" << endl; 46 else 47 cout << "null" << endl; 48 49 ret = s1.find(30); //find後刪除 50 if (ret != s1.end()) 51 s1.erase(ret); 52 set<int>::iterator last, first; 53 first = s1.lower_bound(8); //返回8大的第一個數 54 last = s1.upper_bound(20); //返回20大的第一個數 55 s1.erase(first, last);//刪除這個範圍的數據 56 s1.erase(100); //有就刪除，沒有也不報錯 57 58 set<int>::iterator ite1 = s1.begin(); 59 while (ite1 != s1.end()) { 60 cout << *ite1 << " "; 61 ite1++; 62 } 63 } 64 void MultisetTest() { 65 multiset<int> s2; //允許數據冗餘,其他操作同set 66 s2.insert(13); 67 s2.insert(4); 68 s2.insert(6); 69 s2.insert(19); 70 s2.insert(20); 71 s2.insert(16); 72 s2.insert(9); 73 s2.insert(12); 74 s2.insert(9); 75 s2.insert(7); 76 s2.insert(5); 77 s2.insert(13); 78 s2.insert(9); 79 multiset<int>::iterator mit = s2.begin(); 80 while (mit != s2.end()) { 81 cout << *mit << " "; 82 mit++; 83 } 84 multiset<int>::iterator mIt = s2.find(20); 85 /*++mIt; 86 ++mIt; 87 ++mIt; 88 ++mIt;*/ 89 }
map的節點是一對數據，set的節點是一個數據。
2.擴展
Multimap允許數據冗餘，即存儲的數據不唯一。
hashmap是基於散列表（哈希表，hash table）實現的。基本原理是：使用一個下標範圍比較大的數組來存儲元素。可以設計一個函數（哈希函數，也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標，hash值）相對應，於是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素“分類”，然後將這個元素存儲在相應“類”所對應的地方，稱為桶。
但不能夠保證每個元素的關鍵字與函數值是一一對應的，有可能出現對於不同的元素，得到相同的函數值，這就是哈希衝突，往往需要專門的哈希衝突處理函數來解決。
hashma插入和查找的速度與 哈希函數和衝突處理函數的 實現有關，是這兩個函數耗時的總和。查詢時間複雜度是O(1)；
看具體的應用，不一定常數級別的hash_map一定比log(n)級別的map要好，hash_map的hash函數以及解決地址衝突等都要耗時間，而且眾所周知hash表是以空間換時間的，因而hash_map的記憶體消耗肯定要大，一般情況下，如果記錄非常大，考慮hash_map，查找效率會高很多，如果要考慮記憶體消耗，則要謹慎使用hash_map。
Multiset允許數據冗餘。
