在 C++ 中，容器是存放數(shù)據(jù)的重要數(shù)據(jù)結(jié)構(gòu)，分為序列式容器和關(guān)聯(lián)式容器。序列式容器（如 vector、list、deque）按線性順序存儲元素，元素的位置與值無關(guān)；而關(guān)聯(lián)式容器則通過鍵（key）建立元素間的關(guān)聯(lián)，實現(xiàn)高效的查找、插入和刪除操作。本文將詳細(xì)介紹關(guān)聯(lián)式容器中最常用的 map 和 set，包括它們的底層實現(xiàn)、核心特性、使用方法及實際應(yīng)用。

一、關(guān)聯(lián)式容器的核心概念

1. 容器分類與特點

        關(guān)聯(lián)式容器的核心是 “關(guān)聯(lián)關(guān)系”，即通過鍵（key）快速定位元素，而無需像序列式容器那樣遍歷整個容器。其特點如下：

• 元素按特定規(guī)則排序（有序容器）或無序存儲（無序容器）；
• 插入位置由元素的鍵決定，而非用戶指定；
• 查找效率極高，平均時間復(fù)雜度為 O(logN)（有序容器）或 O(1)（無序容器）。

2. 底層實現(xiàn)

        有序容器（set、map 等）的底層通常采用 平衡二叉搜索樹（紅黑樹） 實現(xiàn)，其特性為：

• 左子樹所有節(jié)點的值 < 根節(jié)點的值；
• 右子樹所有節(jié)點的值 > 根節(jié)點的值；
• 樹的高度保持平衡，確保查找、插入、刪除操作的時間復(fù)雜度為 O(logN)。

        無序容器（unordered_set、unordered_map 等）的底層采用 哈希表 實現(xiàn)，通過哈希函數(shù)將鍵映射到存儲位置，平均時間復(fù)雜度為 O(1)，但最壞情況下可能退化為 O(N)。

3. 搜索模型

        關(guān)聯(lián)式容器分為兩種搜索模型：

• K 模型：僅存儲鍵（key），如 set，核心功能是判斷元素是否存在；
• KV 模型：存儲鍵值對（key-value），如 map，核心功能是通過鍵查找對應(yīng)的值。

二、set 的原理與使用

1. set 的核心特性

        set 是 有序、不重復(fù) 的 K 模型容器，底層為紅黑樹。其核心特性：

• 自動排序：插入元素后，容器會按鍵的升序（默認(rèn)）排列；
• 自動去重：插入重復(fù)元素時，操作會失敗，容器中僅保留一個實例；
• 不可修改元素：set 中的元素是 const 類型，修改元素會破壞紅黑樹的結(jié)構(gòu)，需通過 “刪除舊元素 + 插入新元素” 實現(xiàn)。

2. set 的常用操作

（1）插入操作

        set 不支持 push_back/push_front，需使用 insert() 插入元素：

#include <set>
using namespace std;
set<int> s;
s.insert(3);   
s.insert(1);   
s.insert(3);   // 重復(fù)插入，操作失敗

        插入后，set 中的元素會自動排序為 {1, 3}。

（2）遍歷操作

set 支持迭代器遍歷和范圍 for 遍歷：

void test(){
    set<int> s;
    s.insert(3);
    s.insert(4);
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(7);
    //排序＋去重
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
	    cout << *it << " ";
	    it++;
    }
    cout << endl;
    for (auto e : s)
    {
    	cout << e << " ";
    }
    cout << endl;
}

（3）刪除操作

        set 支持兩種刪除方式：

• 通過迭代器刪除（需先通過 find() 查找元素）；
• 直接通過值刪除。

// 方式 1：通過迭代器刪除
set<int>::iterator pos = s.find(7);	//log(N)
//set<int>::iterator pos = find(s.begin(), s.end(), 4); //OP(N)
if (pos != s.end())
{
	s.erase(pos);
}
// 方式 2：直接通過值刪除
s.erase(1);  // 刪除元素 1，若不存在則無操作

（4）查找操作

        set 的查找功能是其核心，提供兩種方式：

• 成員函數(shù) find()：利用紅黑樹特性，時間復(fù)雜度 O(logN)；
• 算法 std::find()：線性遍歷，時間復(fù)雜度 O(N)。

示例對比：

#include <algorithm>  // 包含 std::find
// 成員函數(shù) find()
set<int>::iterator pos1 = s.find(3);  // 高效查找
// 算法 find()
set<int>::iterator pos2 = find(s.begin(), s.end(), 3);  // 低效遍歷

使用建議：優(yōu)先使用 set 的成員函數(shù) find() 以獲得最佳性能。

3. set 的實際應(yīng)用

        set 的核心優(yōu)勢是 快速存在性檢查 和 高效去重排序，適用于以下場景：

• 存儲學(xué)號、身份證號等唯一標(biāo)識，快速驗證是否存在；
• 對輸入數(shù)據(jù)去重并排序，如統(tǒng)計考試成績的不重復(fù)分?jǐn)?shù)；
• 實現(xiàn)集合運(yùn)算（交集、并集、差集）。

示例：驗證學(xué)號是否存在

student_ids.insert("001");
student_ids.insert("002");
student_ids.insert("003");
string id = "002";
if (student_ids.find(id) != student_ids.end()) {
    cout << "學(xué)號 " << id << " 存在" << endl;
} else {
    cout << "學(xué)號 " << id << " 不存在" << endl;
}

三、map 的原理與使用

1. map 的核心特性

        map 是 有序、鍵唯一 的 KV 模型容器，底層為紅黑樹。其核心特性：

• 存儲鍵值對（key-value），鍵（key）唯一，值（value）可重復(fù)；
• 按鍵自動排序（默認(rèn)升序）；
• 通過鍵快速查找對應(yīng)的值，時間復(fù)雜度 O(logN)；
• 支持通過鍵修改值，但鍵不可修改（否則會破壞紅黑樹結(jié)構(gòu)）。

2. map 的常用操作

（1）pair 類型介紹

        map 中的元素是 pair<const key_type, value_type> 類型，pair 是一個模板結(jié)構(gòu)體，包含兩個成員：

• first：鍵（key），不可修改；
• second：值（value），可修改。

創(chuàng)建 pair 的方式：

// 方式 1：顯式指定模板參數(shù)
pair<int, string> p1(1, "張三");
// 方式 2：使用 make_pair（自動推導(dǎo)類型）
pair<int, string> p2 = make_pair(2, "李四");

（2）插入操作

        map 通過 insert() 插入 pair 類型元素：

#include <map>
using namespace std;
map<int, string> student_info;
// 方式 1：插入 pair 對象
student_info.insert(pair<int, string>(1, "張三"));
// 方式 2：使用 make_pair（推薦，更簡潔）
student_info.insert(make_pair(2, "李四"));
// 方式 3：C++11 統(tǒng)一初始化
student_info.insert({3, "王五"});

        插入后，map 會按鍵的升序排列：{1:張三, 2:李四, 3:王五}。

（3）遍歷操作

        map 支持迭代器遍歷和范圍 for 遍歷，通過 it->first 訪問鍵，it->second 訪問值：

// 迭代器遍歷
map<int, string>::iterator it = student_info.begin();
while (it != student_info.end()) {
    cout << "學(xué)號：" << it->first << "，姓名：" << it->second << endl;
    ++it;
}
// 范圍 for 遍歷
for (auto e : student_info) {
    cout << "學(xué)號：" << e.first << "，姓名：" << e.second << endl;
}

（4）查找與修改操作

        通過鍵查找值有兩種方式：

• 成員函數(shù) find()：返回指向該鍵值對的迭代器；
• 下標(biāo)運(yùn)算符 []：直接通過鍵訪問值（若鍵不存在，會自動插入一個默認(rèn)構(gòu)造的鍵值對）。

// 方式 1：find() 查找（推薦，避免誤插入）
map<int, string>::iterator pos = student_info.find(2);
if (pos != student_info.end()) {
    cout << "找到：" << pos->second << endl;  // 輸出：李四
    pos->second = "李小四";  // 修改值
}
// 方式 2：下標(biāo)訪問（注意：鍵不存在時會自動插入）
string name = student_info[3];  // 訪問鍵 3 的值，存在則返回 "王五"
student_info[4] = "趙六";       // 鍵 4 不存在，插入 {4:趙六}

（5）刪除操作

        map 的刪除方式與 set 類似，支持迭代器刪除和鍵刪除：

// 方式 1：通過迭代器刪除
map<int, string>::iterator pos = student_info.find(2);
if (pos != student_info.end()) {
    student_info.erase(pos);
}
// 方式 2：通過鍵刪除
student_info.erase(3);  // 刪除鍵 3 對應(yīng)的鍵值對

3. map 的實際應(yīng)用

        map 的核心優(yōu)勢是 通過鍵快速查找值，適用于以下場景：

• 存儲鍵值對映射關(guān)系，如字典（單詞 - 翻譯）、學(xué)號 - 成績；
• 統(tǒng)計元素出現(xiàn)次數(shù)，如統(tǒng)計字符串中每個單詞的出現(xiàn)次數(shù)；
• 實現(xiàn)緩存機(jī)制（鍵為緩存 key，值為緩存數(shù)據(jù)）。

示例：統(tǒng)計字符串出現(xiàn)次數(shù)

string str[] = { "西瓜","圣女果", "圣女果", "西瓜", "西瓜", "香蕉", "葡萄", "葡萄", "菠蘿", "西瓜", "桃子", "西瓜",  "栗子", "水蜜桃", "西瓜", "葡萄" };
map<string, int> countMap;
for (auto e : str)
{
	map<string, int>::iterator pos = countMap.find(e);
	if (pos == countMap.end())
		countMap.insert(make_pair(e, 1));
	else
		pos->second++;	
}
for (auto e : countMap)
{
	cout << e.first<<":"<<e.second<<endl;
}

四、map 與 set 的區(qū)別與聯(lián)系

1. 相同點

• 底層均為紅黑樹（有序容器），操作時間復(fù)雜度均為 O(logN)；
• 均支持自動排序和去重（set 去重鍵，map 去重鍵）；
• 均不支持直接修改元素（set 元素不可修改，map 鍵不可修改）。

2. 不同點

五、使用注意事項

1. 元素不可修改：set 的元素和 map 的鍵均為 const 類型，修改會破壞紅黑樹結(jié)構(gòu)，需通過 “刪插” 實現(xiàn)；
2. 迭代器有效性：插入元素時，紅黑樹可能重新平衡，迭代器不會失效；刪除元素時，僅被刪除元素的迭代器失效，其他迭代器有效；
3. 比較規(guī)則：默認(rèn)按鍵的升序排序，若需自定義排序，可在定義容器時指定比較函數(shù)（如 set<int, greater<int>> 按降序排序）；
4. 效率選擇：
   • 需有序存儲且高效查找時，使用 set/map；
   • 無需排序且追求極致查找效率時，使用 unordered_set/unordered_map（哈希表實現(xiàn)）；
   • 僅需線性存儲時，使用 vector/list 等序列式容器。

六、總結(jié)

        map 和 set 是 C++ 中最常用的關(guān)聯(lián)式容器，其核心優(yōu)勢在于 高效的查找、插入和刪除操作，底層依賴紅黑樹實現(xiàn)有序存儲和去重。set 專注于 “鍵的存在性檢查”，map 專注于 “鍵值對的映射查找”，二者在實際開發(fā)中應(yīng)用廣泛，如數(shù)據(jù)去重、統(tǒng)計計數(shù)、字典映射等場景。

        掌握 map 和 set 的使用，需理解其底層實現(xiàn)原理和核心特性，根據(jù)實際需求選擇合適的容器，以優(yōu)化程序性能。

到此這篇關(guān)于C++ 關(guān)聯(lián)式容器map 與 set 的原理與實踐操作的文章就介紹到這了,更多相關(guān)c++ map和set原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論