之前我們介紹過vector, queue, stack，他們都有一個共同的特點，就是都可以用線性表來模擬。今天我們來學習一個全新且高封裝性的容器：map。

🎈 作者：Eriktse
🎈 簡介：19歲，211計算機在讀，現役ACM銀牌選手🏆力爭以通俗易懂的方式講解算法！❤️歡迎關注我，一起交流C++/Python算法。（優質好文持續更新中……）🚀
🎈 個人博客：www.eriktse.com

什麼是 map

std::map是C++標準庫中的一個容器，數據以<key, value>的形式存儲，也就是我們常説的“鍵值對”形式，且其“鍵值對”是有序的，也就是可以順序遍歷的。

這意味着一個key只能對應一個value，而一個value可能對應了多個key，其關係有點像高中學過的函數的關係。

map的底層一般實現為紅黑樹，這個僅作了解即可。搜索、移除和插入操作擁有log級別複雜度。

初始化 map

首先引入頭文件：

#include <map>

用以下代碼聲明一個空的map：

map<int, string> mp;//聲明一個類型為<int, string>的map

注意這裏使用了string，也就需要引入頭文件#include <string>。

插入數據

map有一個函數是insert()，支持將數據插入。時間複雜度O(logn)，n為map中已有的數據個數。

mp.insert({0, "張三"});//插入一條數據

當然還有另外一種辦法來插入數據，就是直接賦值，像操作數組一樣操作map，但是這個map的下標可不是連續的，可以是任意符合條件的key。

mp[2] = "李四";
//現在map中的數據：{0: "張三", 2: "李四"}

可能會有小夥伴疑惑，這裏沒有1的嗎？在這裏map的key只要int類型即可，就算是負數都可以！

mp[-1] = "王五";
//mp = {-1: "王五", 0: "張三", 2: "李四"};

mp[-1] = "eriktse";
//mp = {-1: "eriktse", 0: "張三", 2: "李四"};

值得注意的是，value是可覆蓋的，且這裏的key是有序的，雖然我的-1這個key是後面加入的，但是卻排在了第一個，如果順序遍歷這個mp的話，{-1: "eriktse"}會是第一個被遍歷到的。後面會講到如何遍歷map。

刪除數據 & 清空map

erase(key)方法：刪除key所對應的數據。時間複雜度O(logn)。

clear()方法：清空整個map。

mp.earse(-1);
////mp = {0: "張三", 2: "李四"};

獲取map大小（元素個數）

size()方法：返回map的大小，是一個非負整數。

檢查容器是否無元素，即是否 begin() == end() 。

獲取map中的數據

直接像用數組一樣獲取就行了。

mp[key]表示map中這個key所對應的value。

cout << mp[0] << '\n';//輸出： 張三

遍歷輸出map

遍歷map需要用到std::iterator迭代器，沒有接觸過的同學可能不太瞭解，可以先看代碼，或者用第二種方法。

方法一：迭代器法

void print(map<int, string> mp)
{
    cout << '{';
    for(map<int, string>::iterator it = mp.begin(); it != mp.end(); ++ it)
    {
        cout << i.first << ": " << "\"" << i.second << "\"";
        if(next(it) != mp.end())cout << ", ";//這裏的next(it)表示it的下一個位置，注意這裏不能用 + 1運算，會報錯
    }
    cout << '}';
}

在需要輸出map的地方調用print(mp)即可。

方法二：auto關鍵字

void print(map<int, string> mp)
{
    cout << '{';
    for(auto &i : mp)
    {
        cout << i.first << ": " << "\"" << i.second << "\"";
        if(i != *mp.rbegin())cout << ", ";
    }
    cout << '}';
}

關於auto關鍵字，在這篇文章末尾有簡單介紹：https://www.eriktse.com/algorithm/1051.html

判斷某個key是否存在

count(key)可以返回key出現的次數，但是在經典的map中一個key只能出現一次，所以當返回值為1時説明key存在，返回值為0説明key不存在。時間複雜度O(logn)。

在容器multimap中一個key允許出現多次。

還可用find()函數判斷。

find(key)返回一個迭代器表示找到的數據項，當找不到時返回end()。

if(mp.count(x))cout << "mp中存在key == x的項";
else cout << "mp中不存在key == x的項";

if(mp.find(x) != mp.end())cout << "mp中存在key == x的項";
else cout << "mp中不存在key == x的項";

swap方法

mp1.swap(mp2)方法：交換兩個map容器。

看下面這個例子：

map<int, string> mp1, mp2;//聲明一個類型為<int, string>的map
mp1.insert({0, "張三"});//插入一條數據
mp1[2] = "李四";
mp1[-1] = "eriktse";

mp2[5] = "A";
mp1.swap(mp2);
//print函數需要自己實現
print(mp1);//輸出： {5: "A"}

總結

map是C++中常用的stl之一，也是算法競賽中的常客，大家一定要牢牢記住map的用法、

🎈 本文由eriktse原創，創作不易，如果對您有幫助，歡迎小夥伴們點贊👍、收藏⭐、留言💬