【C/C++】詳解關聯容器map的使用

🔗?運行環境：Matlab

🚩?撰寫作者：左手の明天

🥇?精選專欄：《python》

🔥??推薦專欄：《算法研究》

🔐####?防偽水印——左手の明天?####🔐

💗 大家好🤗🤗🤗，我是左手の明天！好久不見💗

💗今天分享C/C++——關聯容器map的使用💗

📆? 最近更新：2024 年 05 月 26 日，左手の明天的第?331?篇原創博客

📚?更新于專欄：C/C++入門與進階

🔐####?防偽水印——左手の明天?####🔐

一、引言

關聯容器map是STL（Standard Template Library，標準模板庫）中的一個重要組件，它提供了一對一的數據處理能力。在map中，每個元素都是一個關鍵字-值（key-value）對，其中關鍵字起到索引的作用，而值則表示與索引相關聯的數據。這種特性使得map在處理一對一數據時，能夠在編程上提供快速通道。

map內部自建一棵紅黑樹（一種非嚴格意義上的平衡二叉樹），這顆樹具有對數據自動排序的功能，因此map內部的所有數據都是有序的。這種有序性為數據的查找、插入和刪除等操作提供了便利。

在map中，關鍵字是唯一的，每個關鍵字在map中只能出現一次。而值是可以修改的，可以通過關鍵字來訪問和修改與之對應的值。此外，map還支持下標訪問符，通過在[]中放入關鍵字，可以找到與該關鍵字對應的值。

總的來說，關聯容器map是一個功能強大的數據結構，它能夠在處理一對一數據時提供高效的數據處理能力，并在編程中提供便捷的操作方式。

二、Map的構造函數

map的構造函數有多種形式，包括匿名對象構造、有名構造、多參數構造函數的隱式類型轉換等。在插入數據時，可以使用insert函數插入pair數據或value_type數據，也可以使用數組方式插入數據。需要注意的是，當使用insert函數插入數據時，如果map中已存在相同的關鍵字，則插入操作不會生效；而使用數組方式插入數據時，如果關鍵字已存在，則會覆蓋以前該關鍵字對應的值。

std::map在C++標準庫中有多個構造函數，允許你以不同的方式初始化map對象。以下是一些常見的std::map構造函數及其用法：

2.1 默認構造函數

默認構造函數創建一個空的map。

std::map<int, std::string> myMap;

2.2 復制構造函數

復制構造函數允許你從一個已存在的map對象創建一個新的map對象。

std::map<int, std::string> myMap1;
myMap1[1] = "one";
myMap1[2] = "two";std::map<int, std::string> myMap2(myMap1); // 使用myMap1初始化myMap2

2.3 初始化列表構造函數

使用初始化列表可以直接在構造函數中初始化map的元素。

std::map<int, std::string> myMap = {{1, "one"},{2, "two"},{3, "three"}
};

或者C++11及以后的語法：

std::map<int, std::string> myMap{{1, "one"},{2, "two"},{3, "three"}
};

2.4 迭代器范圍的構造函數

你可以使用一對迭代器來從一個已存在的容器（如數組、另一個map、vector等）初始化map。

std::pair<int, std::string> array[] = {{1, "one"},{2, "two"},{3, "three"}
};std::map<int, std::string> myMap(array, array + sizeof(array) / sizeof(array[0]));

2.5 分配器構造函數

分配器構造函數允許你使用一個自定義的分配器來管理map的內存。這在需要控制內存分配和釋放時特別有用。

std::allocator<std::pair<const int, std::string>> alloc;
std::map<int, std::string> myMap(alloc);

在實際使用中，你通常會使用默認構造函數或初始化列表構造函數來創建和初始化map對象。例如，當你需要快速創建一個具有固定鍵值對的map時，初始化列表構造函數非常方便。

記住，由于map是有序的，所以當你使用初始化列表或迭代器范圍構造函數時，鍵值對的順序將影響最終map中元素的順序。如果你使用默認的比較函數（std::less<Key>），元素將按照鍵的升序排列。如果你提供了自定義的比較函數，元素將根據該比較函數的邏輯排序。

三、Map的基本操作函數

C++ Maps是一種關聯式容器，包含“關鍵字/值”對，如下表：

操作函數	含義
begin()	返回指向map頭部的迭代器
clear(）	刪除所有元素
count()	返回指定元素出現的次數
empty()	如果map為空則返回true
end()	返回指向map末尾的迭代器
equal_range()	返回特殊條目的迭代器對
erase()	刪除一個元素
find()	查找一個元素
get_allocator()	返回map的配置器
insert()	插入元素
key_comp()	返回比較元素key的函數
lower_bound()	返回鍵值>=給定元素的第一個位置
max_size()	返回可以容納的最大元素個數
rbegin()	返回一個指向map尾部的逆向迭代器
rend()	返回一個指向map頭部的逆向迭代器
size()	返回map中元素的個數
swap()	交換兩個map
value_comp()	返回比較元素value的函數
upper_bound()	返回鍵值>給定元素的第一個位置

四、Map的實現

Map是存儲鍵值對的數據結構，它提供了一種方便的方法來訪問和操作這些鍵值對。在C語言中，可以使用哈希表來實現Map。Map提供了以下基本操作：

插入：將一個新的鍵值對插入到Map中。
查找：根據鍵查找對應的值。
刪除：刪除指定的鍵值對。
更新：修改指定鍵的值。
大小：返回Map中存儲的鍵值對的數量。
遍歷：遍歷Map中的所有鍵值對。

在C++中，std::map是一個關聯容器，它存儲的元素都是鍵值對（key-value），并且根據鍵的值自動排序。每個鍵在map中只能出現一次，鍵不能修改，但對應的值可以修改。map的底層結構通常是用紅黑樹實現的，因此map中的元素總是有序的。

下面是使用std::map的基本步驟：

4.1?包含頭文件

首先，你需要包含<map>頭文件來使用std::map。

#include <map>

4.2?定義和創建map對象

你可以使用std::map模板來定義和創建map對象。你需要指定鍵和值的類型。

std::map<int, std::string> myMap;  // 定義一個map，鍵是int類型，值是std::string類型

4.3?插入元素

你可以使用insert()函數來插入元素。通常，你可以使用std::make_pair來創建一個鍵值對，并將其插入到map中。

myMap.insert(std::make_pair(1, "one"));
myMap.insert(std::make_pair(2, "two"));

或者，你可以直接使用[]運算符來插入或修改元素（如果鍵已存在，則修改對應的值；如果鍵不存在，則插入新的鍵值對）。

myMap[3] = "three"; // 插入鍵為3，值為"three"的鍵值對

4.4 訪問元素

你可以使用[]運算符或at()函數來訪問元素。如果鍵不存在于map中，at()會拋出異常，而[]會創建一個新的元素。

std::string value = myMap[1]; // 訪問鍵為1的元素的值
std::string value2 = myMap.at(2); // 另一種訪問元素的方式

4.5?遍歷map

你可以使用迭代器來遍歷map中的所有元素。

for (std::map<int, std::string>::iterator it = myMap.begin(); it != myMap.end(); ++it) {std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

或者使用基于范圍的for循環（C++11及以后版本）：

for (const auto& kv : myMap) {std::cout << "Key: " << kv.first << ", Value: " << kv.second << std::endl;
}

4.6?刪除元素

你可以使用erase()函數來刪除元素。

myMap.erase(1); // 刪除鍵為1的元素

4.7 查找元素

你可以使用find()函數來檢查元素是否存在。find()函數返回一個迭代器指向鍵值為key的元素，如果沒找到就返回指向map尾部的迭代器。

auto it = myMap.find(1);
if (it != myMap.end()) {std::cout << "Element found with key 1." << std::endl;
} 
else {std::cout << "Element not found." << std::endl;
}

這些是std::map的基本用法。在實際編程中，你可能還需要了解更多關于map的高級用法，比如自定義比較函數、使用emplace()函數插入元素等。你可以查閱C++標準庫文檔或相關教程來獲取更多信息。

4.8 map中swap的用法：

Map中的swap不是一個容器中的元素交換，而是兩個容器交換；

#include <map>
#include <iostream>using namespace std;int main( )
{map <int, int> m1, m2, m3;map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 10 ) );m1.insert ( pair <int, int> ( 2, 20 ) );m1.insert ( pair <int, int> ( 3, 30 ) );m2.insert ( pair <int, int> ( 10, 100 ) );m2.insert ( pair <int, int> ( 20, 200 ) );m3.insert ( pair <int, int> ( 30, 300 ) );cout << "The original map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter->second;cout << "." << endl;// This is the member function version of swap//m2 is said to be the argument map; m1 the target mapm1.swap( m2 );cout << "After swapping with m2, map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;cout << "After swapping with m2, map m2 is:";for ( m1_Iter = m2.begin( ); m1_Iter != m2.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;// This is the specialized template version of swapswap( m1, m3 );cout << "After swapping with m3, map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;
}

4.9 map的sort問題：

Map中的元素是自動按key升序排序,所以不能對map用sort函數：

#include <map>
#include <iostream>using namespace std;int main( )
{map <int, int> m1;map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 20 ) );m1.insert ( pair <int, int> ( 4, 40 ) );m1.insert ( pair <int, int> ( 3, 60 ) );m1.insert ( pair <int, int> ( 2, 50 ) );m1.insert ( pair <int, int> ( 6, 40 ) );m1.insert ( pair <int, int> ( 7, 30 ) );cout << "The original map m1 is:"<<endl;for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << m1_Iter->first<<" "<<m1_Iter->second<<endl;
}

The original map m1 is:

1 20

2 50

3 60

4 40

6 40

7 30

五、Map定義自定義比較函數

在std::map中定義自定義比較函數是通過向std::map模板的第三個參數傳遞一個比較對象來實現的。這個比較對象通常是一個函數對象（也稱為仿函數）或者Lambda表達式，它需要重載operator()來定義兩個元素之間的比較邏輯。

下面是使用自定義比較函數的std::map的幾種方式：

5.1 使用函數對象（仿函數）

首先，定義一個比較函數對象：

struct MyComparator {bool operator()(const int& a, const int& b) const {// 定義比較邏輯，這里假設我們要按照降序排列return a > b;}
};

然后，使用這個比較函數對象來創建std::map：

std::map<int, std::string, MyComparator> myMap;

5.2 使用Lambda表達式（C++11及以后）

在C++11及更高版本中，你可以使用Lambda表達式作為比較函數：

auto comp = [](const int& a, const int& b) {// 定義比較邏輯return a > b;
};std::map<int, std::string, decltype(comp)> myMap(comp);

注意這里使用了decltype(comp)來自動推斷比較函數的類型。

5.3 使用標準庫函數對象

有時，你可能不需要完全自定義比較邏輯，而是想要對map中的鍵進行某種轉換后再比較。在這種情況下，你可以使用標準庫提供的函數對象適配器，如std::greater<>或std::less<>，配合自定義的鍵轉換函數。但是，這通常是通過自定義比較函數對象來實現的，其中內部使用這個轉換函數。

示例：降序排列的`std::map`

假設想要一個按照鍵的降序排列的std::map：

#include <iostream>
#include <map>
#include <string>int main() {// 使用自定義比較函數對象創建降序排列的mapstd::map<int, std::string, std::greater<int>> myMap;myMap[3] = "three";myMap[1] = "one";myMap[2] = "two";// 遍歷map，顯示鍵值對for (const auto& kv : myMap) {std::cout << "Key: " << kv.first << ", Value: " << kv.second << std::endl;}return 0;
}

在這個例子中，使用了std::greater<int>作為比較函數對象，它會使std::map按照鍵的降序排列。