???C++?表情包趣味教程????《C++要笑著學》

• ?? 寫在前面：本章我們繼續(xù)講解 STL，講解 STL 的 map 類。我們將詳細介紹 map 類的基礎概念，包括 pair 類型（value_type）的應用和插入元素的方法。隨后，我們將深入研究 Map 的遍歷方式以及統計元素出現次數的幾種方式。最后我們再簡單介紹一下不去重版本的 multimap，建議通過查看官方文檔的方式輔助學習。

目錄

Ⅰ. Map 類

0x00 引入：Map 的介紹

0x01 pair 類型（value_type）

0x02 map 的插入（insert）

0x03 map 的遍歷

0x04 統計次數的方式

0x05 map::operator[]

Ⅱ. multimap 類

0x00 引入：不去重的 multi

0x01 multimap 不支持 operator[]

0x02?mutimap 的刪除

Ⅰ. Map 類

0x00 引入：Map 的介紹

template <class Key,   // map::key_type
          class T,     // map::mapped_type
          class Compare = less<Key>,    // map::key_compare
          class Alloc = allocator<pair<const Key, T>>  // map::allocator_type
          > class map;

STL 的 map 是關聯容器，按照特定順序存儲關聯，由 鍵 (key) 與 值 (value) 組合而成的元素：

它們組合成?鍵值對，key 通常用于排序和唯一地標識元素，value 中存儲與 key 關聯的內容。

key 和 value 的類型可以不同，在 map 內部，key 和 value 通過成員類型 value_type 綁定。

?value_type 實際上就是?pair 類型：

typedef pair value_type;

底層基于紅黑樹，是一種自平衡的二叉搜索樹，能確保在插入和刪除元素時維持良好的性能。

map 通常被實現為二叉搜索樹，更準確地說是平衡二叉搜索樹（紅黑樹）。

在內部，map 中的元素總是按照 key 進行比較排序的。

map 還支持下標訪問符，在 [ ] 中放入 key，就可以找到與 key 對應的 value，我們下面會細說。

0x01 pair 類型（value_type）

map 的 insert 接口就是是一個 value_type，我們先來搞清楚什么是 value_type。

我們剛才說了，value_type 實際上就是?pair 類型，在 map 中稱之為 鍵值對，定義如下：

typedef pair<const Key, T> value_type;

pair 是在庫里面就定義好了的，SGI-STL 中關于鍵值對的定義如下：

template<class T1, class T2>
struct pair {
	typedef T1 fisrt_type;
	typedef T2 second_type;

	T1 first;
	T2 second;
	pair() 
		: first(T1())
		, second(T2())
	{}
	pair(const T1& a, const T2& b)
		: first(a)
		, second(b) 
	{}
};

實際上 pair 的定義遠沒有我們想象中的復雜，里面就定義了一個?first 和一個?second。

0x02 map 的插入（insert）

我們假設 dict?變量的數據類型為?map<string, string>，我們可以如何插入數據呢？

① 我們可以直接調用 pair 的構造函數來插入：

dict.insert(pair<string, string>("sort", "排序"));

② 似乎比較麻煩？我們可以用匿名對象的方式來寫：

pair<string, string> kv("insert", "插入");
dict.insert(kv);

這就體現了匿名對象的優(yōu)勢了，這里調用 pair 的構造函數來構造一塊這樣的對象出來。

③ 還有更爽的方式，調用神奇的 make_pair ！我們戲稱之為 "做對子" ：

" 樹上的鳥兒成雙對……"

dict.insert( make_pair("left", "左邊") );

make_pair 是一個函數模板，使用時不用聲明參數，可自動推導出對應的類型。

我們來看一下 make_pair 的底層實現：

template<class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y) {
    return (pair<T1, T2>(x, y) );
}

• ?? 分析：可以看到，自動推導出參數類型的同時也構造出 pair 的匿名對象并返回，并且還會推舉為?inline。本質上其實還是調用 pair 的構造函數，只是它把推導參數的任務交給了編譯器去完成。

④ 還有更強大的方式插入，直接用 { }?：

dict.insert( {"right", "右邊"} );

這得益于 C++11 支持類型轉化，可以用大括號進行初始化！

再上一章講解 set 的示例中我們也用到了這一方法：

set<int> s = {4, 2, 4, 6, 1, 0};

（我們將在后續(xù)講解 C++11 時作詳細解釋）

? 推薦使用什么方式進行插入？

• 推薦使用匿名對象或 make_pair 的方式進行插入，個人還是更喜歡用 make_pair 的方式。

0x03 map 的遍歷

和其他容器的迭代器一樣，加上?:: 小尾巴后就可以召喚出屬于 map 的迭代器了：

map<string, string>::iterator it = dict.begin();

map 的迭代器的底層相似于鏈表的迭代器。這里的類型真的是很長，寫起來很費勁……

讓我們掌聲有請?auto 關鍵字：

auto it = dict.begin();

下面我們來寫遍歷部分，我們發(fā)現似乎不行：

當然不行！本質上是因為 C++ 不支持一次返回兩個值，這里的 * 就是 it->operator*() 。

但是可以打包，我們可以把這些返回值打包成一個結構數據 —— pair?

這里返回值需要返回迭代器中節(jié)點的數據，節(jié)點的數據是 pair，可惜?pair 并不支持 流 (stream) ：

• error C2679: 二元“<<”: 沒有找到接受“std::pair<const std::string,std::string>”類型的右操作數的運算符(或沒有可接受的轉換)

這里有兩種方法，第一種方法就是在?*it 中分別提取 first 和 second：

auto it = dict.begin();
while (it != dict.end()) {
    cout << (*it).first << ":" << (*it).second << " ";
	it++;
}
cout << endl;

??? 運行結果如下：

我們可以看到，map 也是會自動排序的。當然，我們還可以用 -> 操作符：

auto it = dict.begin();
while (it != dict.end()) {
	cout << it->first << ":" << it->second << " ";
	it++;
}
cout << endl;

對于 map 的手動遍歷，個人還是更傾向于使用 -> 的方式。

（但是考慮到向下兼容的情況，還是 *. 更加包容，這個我們下面會探討一下）

當然，map 同樣支持甜甜的 范圍 for 來遍歷，這里建議加上 & 提效：

for (auto& kv : dict) {
	cout << kv.first << ":" << kv.second << " ";
}
cout << endl;

一般我們將其命名為 ，因為這里我們取到的就是一對對 pair。

0x04 統計次數的方式

現在我們要統計一些數據，比如我們需要統計這些水果的個數：

"蘋果", "西瓜", "蘋果", "香蕉", "草莓", "檸檬"
"西瓜", "蘋果", "檸檬", "檸檬", "西瓜", "橙子"
"草莓", "檸檬", "香蕉", "蘋果", "橙子", "檸檬"

我們就可以使用 map 來存儲，pair 我們就可以用 string + int 類型來組合：

map<string, int> count_map;   // 統計水果的個數

我們先用?"最老實" 的方式來進行統計，用迭代器進行檢查。

檢查很簡單，如果這個元素在 map 中就 次數++，如果不在就將元素 insert 到 map 中：

map<string, int> count_map;
for (auto& str : arr) {
	map<string, int>::iterator it = count_map.find(str);
	if (it != count_map.end()) {
		it->second++;
	}
	else {
		count_map.insert(make_pair(str, 1);
	}
}

?? 代碼演示：我們打印一下看看效果如何

void test_map2() {
	string arr[] = {
		"蘋果", "西瓜", "蘋果", "香蕉", "草莓", "檸檬",
		"西瓜", "蘋果", "檸檬", "檸檬", "西瓜", "橙子",
		"草莓", "檸檬", "香蕉", "蘋果", "橙子", "檸檬"
	};

	// 統計
	map<string, int> count_map;
	for (auto& str : arr) {
		map<string, int>::iterator it = count_map.find(str);
		if (it != count_map.end()) {
			it->second++;
		}
		else {
			count_map.insert(make_pair(str, 1));
		}
	}
	
	// 打印
	for (auto& kv : count_map) {
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;
}

?? 運行結果如下：

實際上這里從樹根往下找了兩次，第一次是 find 在找，第二次是 insert 再找，有點多余了。

這里實際上可以讓 insert 來兼顧 "查找" 的工作，我們來看下 map 的 insert 接口的原型：

std::pair<iterator, bool>insert(const value_type& value);

我們可以看到 insert 的返回值是一個 pair<iterator, bool>?類型。

插入成功， second 就是 true；如果插入失敗， second 就是 false。

既然如此，我們就可以這么去迭代：

for (auto& str : arr) {
	pair< map<string, int>::iterator, bool >ret
    = count_map.insert(make_pair(str, 1)); 
}

這個類型是相當的長，pair<map<string, int>::iterator, bool>，不用 auto 簡化一下簡直沒法看：

for (auto& str : arr) {
	auto ret = count_map.insert(make_pair(str, 1)); 
}

• 插入成功的情況：說明這個 "水果" 第一次出現
• 插入失敗的情況：說明這個 "水果" 已經有了，insert 又充當了 find 的作用

所以我們寫一個判斷，判斷 second (bool) 是不是 false，如果是就讓統計 次數++。

?? 代碼演示：

map<string, int> count_map;
for (auto& str : arr) {
	auto ret = count_map.insert(make_pair(str, 1)); 
	if (ret.second == false) {
		ret.first->second++;
	}
}

?? 運行結果如下：

• ?? 解讀：ret.first->second++?不好理解？實際上這里是兩個 pair 嵌套在一塊的！一個 pair 是 insert 的返回值，一個 pair 是節(jié)點。insert 的返回值里是 pair<iterator, int>，其中第一個是迭代器，所以我們取 first。而迭代器里是節(jié)點 pair<string, int> ，我們要讓次數 +1，所以我們節(jié)點里我們取 second。

這種方法相較于第一種 find + insert 的方法有一點點效率上的優(yōu)勢，但是屬實是微乎其微：

實際運用中這兩種方法我們幾乎都不用，因為有更加????的方式！非?？植赖姆绞?！

for (auto& str : arr) {
	count_map[str]++;
}

我嘞個豆！只需要用一個 operator[]?再?++ 就搞定了？！

0x05 map::operator[]

" 一句代碼統計次數，如何辦到的？?"

下面我們來看看這神奇的一句代碼統計次數是如何做到的。我們先來看看它的底層實現：

mapped_type& operator[] (const key_type& k) {
	return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
}

剛看就吐一口老血，雖然只有一行，但這也太復雜了吧？我們來寫得更清晰易懂一些：

mapped_type& operator[] (const key_type& k) {
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	// return (*(ret.first)).second;
	return ret.first->second;
}

• ?? 解讀：目的是在關聯容器中通過鍵訪問元素，如果元素不存在，則插入一個具有默認值的新元素，并返回對這個元素的引用。首先?const key_type& k 是傳入的鍵，表示要查找或插入的元素的鍵值。make_pair(k, mapped_type()) 創(chuàng)建了一個?pair?對象，該對象的第一個元素是傳入的鍵 k，第二個元素是使用 mapped_type 的默認構造函數創(chuàng)建的默認值。this->insert(...) 調用關聯容器的 insert 函數，該函數用于將一個鍵-值對插入容器中。返回值是一個?pair，其 first 成員指向插入的元素，second 成員指示是否插入成功。(this->insert(...).first) 獲取返回的 std::pair 對象的 first 成員，即指向插入的元素的迭代器。*((this->insert(...).first)) 解引用上一步中獲取的迭代器，得到插入的元素。(*((this->insert(...).first)).second 再次解引用，獲取插入的元素的 second 成員，即與傳入的鍵關聯的值。return (*((this->insert(...).first)).second; 返回通過 operator[] 訪問或插入的元素的引用。

?現在我們再來看看神奇的 [ ] 是如何實現的：

for (auto& str : arr) {
	count_map[str]++;
}

如果是第一次出現，就先插入。插入成功后會返回插入的節(jié)點中的次數 0 的引用，對它 ++ 后變?yōu)?1。如果是第二次插入，插入失敗，會返回它所在節(jié)點的迭代器的次數，再 ++。

Ⅱ. multimap 類

0x00 引入：不去重的 multi

一詞多義的情況，比如 left 這個單詞，我們同時想記錄它的 "左邊" 和 "剩余" 這兩個意思。

這時我們就可以使用 multimap 類，和 multiset 一樣，只排序不去重。

void test_multimap() {
	multimap<string, string> dict;
	dict.insert(make_pair("left", "左邊"));
	dict.insert(make_pair("left", "剩余"));
}

這種情況如果在 map 中，第二次 insert 是失敗的，但是在 multimap 中是成功的。

• multimap?允許在容器中存儲多個具有相同鍵的元素，這使得它成為處理具有相同鍵的多個值的理想選擇。每個元素是一個鍵-值對，鍵用于按順序組織元素，而值則是與鍵關聯的實際數據。

0x01 multimap 不支持 operator[]

相比 map?和?multimap 函數接口差不多，但是?multimap 并不支持 operator[] ！

這也是情理之中的，主要原因是它允許存儲相同鍵的多個元素，主要原因是 multimap 一對多。

?存在多個相同鍵對應的值，無法明確確定要返回哪個值：

int main(void) 
{
    multimap<int, std::string> myMultimap;

    myMultimap.insert(std::make_pair(1, "apple"));
    myMultimap.insert(std::make_pair(1, "apricot"));
    myMultimap.insert(std::make_pair(2, "banana"));

    // 下面這行代碼會引發(fā)問題，因為有兩個鍵為1的元素
    cout << myMultimap[1] << endl;

    return 0;
}

• ?? 解讀：這里的?myMultimap[1]?就無法明確地確定返回哪個值，因為有兩個鍵為 1 的元素。因此，multimap?不提供 operator[] 的方式插入。

那怎么辦？如果我們想?multimap 中特定鍵的所有值，我們就老老實實用迭代器遍歷，或者使用 equal_range 函數來獲取鍵對應的范圍：

auto range = myMultimap.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
    cout << "Value: " << it->second << std;
}

這樣可以處理具有相同鍵的多個元素的情況了。

0x02?mutimap 的刪除

使用?erase?函數可以刪除指定鍵的元素，。比如下面這樣就會刪除所有鍵為 1 的元素。

mmap.erase(1);   // 刪除所有鍵為1的元素

?? [ 筆者 ]? ?王亦優(yōu)
?? [ 更新 ]? ?2023.12.20
? [ 勘誤 ]?? /* 暫無 */
?? [ 聲明 ]? ?由于作者水平有限，本文有錯誤和不準確之處在所難免，
              本人也很想知道這些錯誤，懇望讀者批評指正！

到了這里，關于?【C++要笑著學】(31) 映射類：map 類 | pair 類型 (value_type) | map 的插入和遍歷 | map 的 operator[] | multimap 類的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！