c++ 數據結構map的使用詳解

map的常用用法

map 表示映射,可以將任何基本類型(包括 STL 容器)映射到任何基本類型(包括 STL 容器),例如可以建立如 int 到 double,string 到 int 的映射等。

map 提供一對一的 hash,該功能類似 Python 的字典:

  • 第一個稱為鍵( key ),每個關鍵字隻能在 map 中出現一次;
  • 第二個稱為該鍵的值( value );

1. 頭文件

<bits/stdc++.h> 頭文件已經包括瞭該頭文件。

2. 定義

定義 map 如下,參數的第一個為 key 的類型,第二個為 value 的類型。

map<typename1, typename2> mp;

【註意】如果是字符串到整型的映射,必須使用 string 而不能用 char 數組。

map 的鍵和值也可以是 STL 容器,例如可以將一個 set 容器映射到一個字符串:

map<set<int>, string> mp;

3. map 容器內元素的訪問

(1)通過下標訪問

註意:map 的鍵是唯一的。

#include <iostream>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['c'] = 30; 
    cout << mp['c'] << endl; 
    return 0;
}

30

(2)通過迭代器訪問

定義迭代器:

map<typename1, typename2>::iterator it;

這樣可以得到迭代器 it,map 可以使用 it->first來訪問鍵,使用 it->second 來訪問值。

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

輸出:

a 40
m 20
r 30

【註意】map 會以鍵從小到大的順序自動排序。迭代器的比較不能用 < 或者 >,而隻能使用 == 或者 !=

(3)通過逆向迭代器訪問

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::reverse_iterator it = mp.rbegin(); it!=mp.rend();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

輸出:

r 30
m 20 
a 40

rbegin()指向 map 的最後一個元素,rend()指向 map 第一個元素之前。

4. map 元素的插入

(1)通過insert + <key, value> 插入

map<int, string> mapStudent;  
mapStudent.insert(pair<int, string>(1, "student_one"));  

(2)通過insert + 迭代器 插入

map<int, string> mapStudent;  
mapStudent.insert(map<int, string>::value_type (1, "student_one")); 

(3)通過數組方式插入

map<int, string> mapStudent;  
mapStudent[1] = "student_one";

【註意】第一、二種方法完全等價,但是第三種和前兩種有所區別。當映射中包含瞭鍵,則第一、二中方法插入失敗,而第三種方法會覆蓋之前的鍵值對。所以先後插入相同 key 的元素,第一、二種方法會保留第一次的數據,第三種會保留最後一次的。

5. map 常用函數實例解析

(1)find()

find(key) 返回鍵為 key 的映射的迭代器,時間復雜度為 O(logN),N為 map 中映射的個數。

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char, int>::iterator it = mp.find('b');
    printf("%c %d\n", it->first, it->second);
    return 0;
}

b 2

(2)erase()

① 刪除單個元素

mp.erase(it) :it 是要刪除的元素的迭代器,時間復雜度為 O(1)

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char, int>::iterator it = mp.find('b');
    mp.erase(it);  // 刪除 b 2
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

a 1
c 3

mp.erase(key):key是要刪除的映射的鍵,時間復雜度為 O(logN)

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    mp.erase('b');  // 刪除 b 2
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

a 1
c 3

② 刪除一個區間內所有元素

mp.erase(first, last):first 為需要刪除區間的起始迭代器,last 為需要刪除的區間的末尾迭代器的下一個地址,即刪除左閉右開區間 [first, last) 內所有元素。

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char, int>::iterator it = mp.find('b');  // 令it指向鍵為b的映射
    mp.erase(it, mp.end());  // 刪除it之後所有的映射
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

a 1

(3)size()

size() :獲取 map 中映射的對數,時間復雜度為 O(1)。

#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 10;
    mp['b'] = 20;
    mp['c'] = 30;
    printf("%d\n", mp.size());  // 3對映射
    return 0;
}

(4)count()

count(): 返回 map 中對應鍵的個數,由於 map 中相同鍵隻能最多有一個,所以 count() 的結果隻能是 0 或者 1。

#include <iostream>
#include <map>

int main (){
  	std::map<char,int> mymap;
	char c;
	
	mymap ['a']=101;
	mymap ['c']=202;
	mymap ['d']=303;
	
	for (c='a'; c<'e'; c++){
	  std::cout << c;
	  if (mymap.count(c)>0)
	    std::cout << " is an element of mymap.\n";
	  else 
	    std::cout << " is not an element of mymap.\n";
	}
	return 0;
}

結果:

a is an element of mymap.
b is not an element of mymap.
c is an element of mymap.
d is an element of mymap.

(5)clear()

clear(): 用於清空 map,map變為初始的空狀態。

(6)empty()

empty():判斷 map 是否為空,如果 map 為空,返回 true,否則返回 false.

(7)lower_bound() 、upper_bound()

lower_bound() : 返回鍵值 >= 給定元素的第一個位置。即如果鍵的類型可以比較,可以使用二分查找的方法,返回的類型是一個迭代器。 upper_bound(): 返回鍵值>給定元素的第一個位置。即如果鍵的類型可以比較,可以使用二分查找的方法,返回的類型是一個迭代器。

map<int, string> mapStudent;  
mapStudent[1] = "student_one";  
mapStudent[3] = "student_three";  
mapStudent[5] = "student_five"; 
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(2); // 返回鍵值為3的迭代器;
iter = mapStudent.upper_bound(2); // 返回鍵值為3的迭代器

以上就是c++ 數據結構map的使用詳解的詳細內容,更多關於c++ 數據結構map的使用的資料請關註WalkonNet其它相關文章!