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

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

1. 容器分類與特點(diǎn)

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

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

2. 底層實(shí)現(xiàn)

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

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

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

3. 搜索模型

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

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

二、set 的原理與使用

1. set 的核心特性

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

• 自動(dòng)排序：插入元素后，容器會(huì)按鍵的升序（默認(rèn)）排列；
• 自動(dòng)去重：插入重復(fù)元素時(shí)，操作會(huì)失敗，容器中僅保留一個(gè)實(shí)例；
• 不可修改元素：set 中的元素是 const 類型，修改元素會(huì)破壞紅黑樹(shù)的結(jié)構(gòu)，需通過(guò) “刪除舊元素 + 插入新元素” 實(shí)現(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 中的元素會(huì)自動(dòng)排序?yàn)?nbsp;{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 支持兩種刪除方式：

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

// 方式 1：通過(guò)迭代器刪除
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：直接通過(guò)值刪除
s.erase(1);  // 刪除元素 1，若不存在則無(wú)操作

（4）查找操作

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

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

示例對(duì)比：

#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 的實(shí)際應(yīng)用

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

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

示例：驗(yàn)證學(xué)號(hào)是否存在

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é)號(hào) " << id << " 存在" << endl;
} else {
    cout << "學(xué)號(hào) " << id << " 不存在" << endl;
}

三、map 的原理與使用

1. map 的核心特性

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

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

2. map 的常用操作

（1）pair 類型介紹

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

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

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

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

（2）插入操作

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

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

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

（3）遍歷操作

        map 支持迭代器遍歷和范圍 for 遍歷，通過(guò) it->first 訪問(wèn)鍵，it->second 訪問(wèn)值：

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

（4）查找與修改操作

        通過(guò)鍵查找值有兩種方式：

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

// 方式 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)訪問(wèn)（注意：鍵不存在時(shí)會(huì)自動(dòng)插入）
string name = student_info[3];  // 訪問(wèn)鍵 3 的值，存在則返回 "王五"
student_info[4] = "趙六";       // 鍵 4 不存在，插入 {4:趙六}

（5）刪除操作

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

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

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

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

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

示例：統(tǒng)計(jì)字符串出現(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. 相同點(diǎn)

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

2. 不同點(diǎn)

五、使用注意事項(xiàng)

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

六、總結(jié)

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

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

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

最新評(píng)論