天天看點
傳回

STL之map與pair與unordered_map常用函數詳解

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:\clion\qifei\cmake-build-debug\qifei.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()

     删除元素有兩種方法：删除單個元素；删除一個區間的元素。
    1. 删除單個元素：
      • 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:\clion\qifei\cmake-build-debug\qifei.exe
1 student1
6 student6
7 student7
2 student2
4 student4
5 student5
3 student3

Process finished with exit code 0
上一篇: UIColor，CGColor，CIColor三者的差別和聯系
下一篇: iOS 開發 RGB 色值轉換