STL之map與pair與unordered_map常用函數詳解
- 2020 年 4 月 8 日
- 筆記
STL之map與pair與unordered_map常用函數詳解
一、map的概述
map是STL的一個關聯容器，它提供一對一（其中第一個可以稱為關鍵字，每個關鍵字只能在map中出現一次，第二個可能稱為該關鍵字的值）的數據處理能力，由於這個特性，它完成有可能在我們處理一對一數據的時候，在編程上提供快速通道。這裡說下map內部數據的組織，map內部自建一顆紅黑樹(一種非嚴格意義上的平衡二叉樹)，這顆樹具有對數據自動排序的功能，所以在map內部所有的數據都是有序的，後邊我們會見識到有序的好處。
下面舉例說明：
眾所周知，在定義數組的時候比如（int array[10]) ，array[0]=25,array[1]=10,其實就是一個映射，將0—>25,1—>10,就是將0映射到25，將1映射到10，這種一一對應的關係就是映射，就數組來說，他的下標和其下標所對應的值就是一種映射關係，但是這一種關係比較死板，於是就有map，這一種容器，map可以建立將任何基本類型（包括STL容器）映射到任何基本數據類型（包括STL容器）。
二、map的定義與初始化（插入）
- 單獨定義一個map：
// 引入一個頭文件 #include <map> map<typename1,typename2> mp; -
typename1是鍵值的數據類型
-
typename2是值的數據類型
-
如果是字元串映射到整型數組，鍵值必須使用string類型，而不能使用char數組。
這是因為char作為數組，不能作為鍵值。
-
map的鍵和值可以是STL的容器，我們將set映射到一個字元串
map<set<int>,string> mp; 三、map的元素的訪問
- map中的容器值可以通過：下標和迭代器進行訪問。
- 下標訪問map鍵值是唯一的
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<char,int> mp; mp['c']=20; mp['c']=30; // 由於鍵值唯一，第一個他的值將會被覆蓋 cout<<mp['c']<<endl; return 0; } // 輸出 30 -
通過迭代器訪問
map的迭代器與其他STL容器相同
map<typename1,typename2>::iterator it; // 由於一個it對應兩個值，我們使用 it->first 訪問鍵 it->second 訪問值 -
下面來看一個示例：
PS：下面我以3種不同的方式進行插入不懂得可以參照這一篇文章：
// 以類似數組的的表達方式來進行 #include <iostream> #include <map> #include <string> using namespace std; int main() { map<char,int> mp; char key; int val; int t=5; while(t--) { cin>>key>>val; mp[key]=val; } // 通過迭代器來訪問 for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++) { cout<<it->first<<" "<<it->second<<endl; } return 0; } a 5 s 8 z 6 p 3 t 7 a 5 p 3 s 8 t 7 z 6 其實細心的小夥伴已經發現，其輸出結果是按照鍵值進行升序排序的。
C++11中有unordered_map,以散列來代替map內部的紅黑樹實現，其不需要排序，速度就 快很多了。下面會有介紹。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<char,int> mp; char key; int val; int t=5; while(t--) { cin>>key>>val; mp.insert(make_pair(key,val)); // 以make_pair來插入 } for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++) { cout<<it->first<<" "<<it->second<<endl; } return 0; } #include <iostream> #include <map> #include <string> using namespace std; int main() { map<char,int> mp; char key; int val; int t=5; while(t--) { cin>>key>>val; mp.insert(pair<char,int>(key,val)); // 以pair來插入 } for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++) { cout<<it->first<<" "<<it->second<<endl; } return 0; } #include <iostream> #include <map> #include <string> using namespace std; int main() { map<char,int> mp; char key; int val; int t=5; while(t--) { cin>>key>>val; mp.insert(pair<char,int>(key,val)); } // 這種基於範圍的for循環，只有C++11以上才可以 for(auto it=mp.begin();it!=mp.end();it++) { cout<<it->first<<" "<<it->second<<endl; } return 0; } - 用insert函數插入
value_type數據，下面舉例說明
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student2")); for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++) cout<<it->first<<" "<<it->second<<endl; return 0; } // 輸出結果： G:clionqifeicmake-build-debugqifei.exe 1 student1 2 student2 3 student2 Process finished with exit code 0 四.map常用函數解析
find()用find函數來定位數據出現位置，它返回的一個迭代器，當數據出現時，它返回數據所在位置的迭代器，如果map中沒有要查找的數據，它返回的迭代器等於end函數返回的迭代器，程式說明：
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student2")); map<int,string>::iterator pter=mapStudent.find(2); cout<<pter->first<<" "<<pter->second<<endl; return 0; } // 輸出結果： 2 student2 -
erase()刪除元素有兩種方法：刪除單個元素；刪除一個區間的元素。-
刪除單個元素：
-
mp.erase(it), it為要刪除的元素的迭代器
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student2")); map<int,string>::iterator pter=mapStudent.find(2); mapStudent.erase(pter); for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++) cout<<it->first<<" "<<it->second<<endl; return 0; } // 輸出結果： 1 student1 3 student2- 通過鍵值來刪除一個元素：
-
-
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student2")); map<int,string>::iterator pter=mapStudent.find(2); mapStudent.erase(2); for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++) cout<<it->first<<" "<<it->second<<endl; return 0; } // 輸出結果： 1 student1 3 student2 2.erase（first，last），可以刪除整個區間的元素；刪除區間為[first,last)。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student3")); mapStudent.insert(map<int,string>::value_type(4,"student4")); mapStudent.insert(map<int,string>::value_type(5,"student5")); mapStudent.insert(map<int,string>::value_type(6,"student6")); mapStudent.insert(map<int,string>::value_type(7,"student7")); map<int,string>::iterator pter=mapStudent.find(4); mapStudent.erase(pter,mapStudent.end()); for(map<int,string>::iterator it=mapStudent.begin();it!=mapStudent.end();it++) cout<<it->first<<" "<<it->second<<endl; return 0; } // 輸出結果： 1 student1 2 student2 3 student3 - size() ，可以獲取map中的映射對數。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student3")); mapStudent.insert(map<int,string>::value_type(4,"student4")); mapStudent.insert(map<int,string>::value_type(5,"student5")); mapStudent.insert(map<int,string>::value_type(6,"student6")); mapStudent.insert(map<int,string>::value_type(7,"student7")); cout<<mapStudent.size()<<endl; return 0; } // 輸出結果： 7 - clear(),請空所有的元素。
#include <iostream> #include <map> #include <string> using namespace std; int main() { map<int, string> mapStudent; mapStudent.insert(map<int,string>::value_type(1,"student1")); mapStudent.insert(map<int,string>::value_type(2,"student2")); mapStudent.insert(map<int,string>::value_type(3,"student3")); mapStudent.insert(map<int,string>::value_type(4,"student4")); mapStudent.insert(map<int,string>::value_type(5,"student5")); mapStudent.insert(map<int,string>::value_type(6,"student6")); mapStudent.insert(map<int,string>::value_type(7,"student7")); mapStudent.clear(); cout<<mapStudent.size()<<endl; return 0; } // 輸出結果： 0 map和unordered_map(c++11)的使用
unordered_map的用法和map是一樣的，提供了 insert，size，count等操作，並且裡面的元素也是以pair類型來存貯的。其底層實現是完全不同的，上方已經解釋了，但是就外部使用來說卻是一致的。
map和unordered_map的差別
需要引入的頭文件不同
map: #include < map > unordered_map: #include < unordered_map > 內部實現機理不同
map： map內部實現了一個紅黑樹（紅黑樹是非嚴格平衡二叉搜索樹，而AVL是嚴格平衡二叉搜索樹），紅黑樹具有自動排序的功能，因此map內部的所有元素都是有序的，紅黑樹的每一個節點都代表著map的一個元素。因此，對於map進行的查找，刪除，添加等一系列的操作都相當於是對紅黑樹進行的操作。map中的元素是按照二叉搜索樹（又名二叉查找樹、二叉排序樹，特點就是左子樹上所有節點的鍵值都小於根節點的鍵值，右子樹所有節點的鍵值都大於根節點的鍵值）存儲的，使用中序遍歷可將鍵值按照從小到大遍歷出來。
unordered_map: unordered_map內部實現了一個哈希表（也叫散列表，通過把關鍵碼值映射到Hash表中一個位置來訪問記錄，查找的時間複雜度可達到O(1)，其在海量數據處理中有著廣泛應用）。因此，其元素的排列順序是無序的。哈希表詳細介紹
優缺點以及適用處
map：
優點：
有序性，這是map結構最大的優點其元素的有序性在很多應用中都會簡化很多的操作
紅黑樹，內部實現一個紅黑書使得map的很多操作在lgn的時間複雜度下就可以實現，因此效率非常的高
缺點：空間佔用率高，因為map內部實現了紅黑樹，雖然提高了運行效率，但是因為每一個節點都需要額外保存父節點、孩子節點和紅/黑性質，使得每一個節點都佔用大量的空間
適用處：對於那些有順序要求的問題，用map會更高效一些
unordered_map：
優點： 因為內部實現了哈希表，因此其查找速度非常的快
缺點： 哈希表的建立比較耗費時間
適用處：對於查找問題，unordered_map會更加高效一些，因此遇到查找問題，常會考慮一下用unordered_map
總結：
記憶體佔有率的問題就轉化成紅黑樹 VS hash表 , 還是unorder_map佔用的記憶體要高。
但是unordered_map執行效率要比map高很多
對於unordered_map或unordered_set容器，其遍歷順序與創建該容器時輸入的順序不一定相同，因為遍歷是按照哈希表從前往後依次遍歷的
#include <iostream> #include <unordered_map> #include <string> using namespace std; int main() { unordered_map<int, string> mapStudent; mapStudent.insert(unordered_map<int,string>::value_type(2,"student2")); mapStudent.insert(unordered_map<int,string>::value_type(4,"student4")); mapStudent.insert(unordered_map<int,string>::value_type(5,"student5")); mapStudent.insert(unordered_map<int,string>::value_type(3,"student3")); mapStudent.insert(unordered_map<int,string>::value_type(7,"student7")); mapStudent.insert(unordered_map<int,string>::value_type(6,"student6")); mapStudent.insert(unordered_map<int,string>::value_type(1,"student1")); for(auto it=mapStudent.begin();it!=mapStudent.end();it++) cout<<it->first<<" "<<it->second<<endl; return 0; } // 輸出結果： G:clionqifeicmake-build-debugqifei.exe 1 student1 6 student6 7 student7 2 student2 4 student4 5 student5 3 student3 Process finished with exit code 0 
