map與set應用詳情 - 迭代器,鍵值對,紅黑樹,數據倉庫,大數據,yyds乾貨盤點阿森CTO 博客

@TOC

在C++ STL的容器家族中，map和set作為核心關聯式容器，憑藉紅黑樹的底層實現，兼具自動排序、高效檢索的特性。

一、關聯式容器與鍵值對：基礎概念鋪墊

1.1 關聯式容器 vs 序列式容器

STL容器分為序列式容器（如vector、list、deque）和關聯式容器（如map、set、multimap、multiset），核心差異在於數據存儲方式和檢索邏輯：

序列式容器：存儲元素本身，底層是線性結構，檢索需遍歷，時間複雜度O(n)；
關聯式容器：存儲<key, value>鍵值對（set中value即key），底層是紅黑樹（平衡二叉搜索樹），檢索、插入、刪除的時間複雜度均為O(log n)，效率遠超序列式容器。

1.2 鍵值對`pair`的本質

鍵值對是關聯式容器的基礎數據結構，用於表示“一一對應”的關係（如字典中的“單詞-釋義”）。STL中pair的定義簡化如下：

template <class T1, class T2>
struct pair {
    T1 first;  // 鍵key
    T2 second; // 值value
    // 構造函數
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

常用操作：

直接構造：pair<string, int> kv("apple", 5)；
便捷構造：make_pair("banana", 3)（無需顯式指定模板參數，更簡潔）；
訪問成員：通過first和second訪問鍵和值，如kv.first、kv.second。

二、set容器：有序唯一的集合

2.1 set的核心特性

存儲單一類型元素，value即key，且所有元素唯一（自動去重）；
底層是紅黑樹，元素默認按less<T>規則升序排序（可自定義排序規則）；
不支持直接修改元素（會破壞紅黑樹的有序性），需先刪除再插入。

2.2 常用接口實戰

（1）初始化與遍歷

#include <set>
#include <iostream>
using namespace std;

void test_set_init() {
    // 1. 列表初始化（C++11+）
    set<int> s1 = {3, 1, 4, 1, 5, 9}; // 自動去重+升序，結果：1,3,4,5,9
    // 2. 迭代器區間初始化
    int arr[] = {2, 7, 1, 8, 2};
    set<int> s2(arr, arr + sizeof(arr)/sizeof(int)); // 結果：1,2,7,8
    // 3. 自定義排序（降序）
    set<int, greater<int>> s3 = {3, 1, 4}; // 結果：4,3,1

    // 遍歷方式：迭代器遍歷
    for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) {
        cout << *it << " "; // 輸出：1 3 4 5 9
    }
    cout << endl;

    // 範圍for遍歷（更簡潔）
    for (auto e : s2) {
        cout << e << " "; // 輸出：1 2 7 8
    }
    cout << endl;
}

map與set應用_迭代器

（2）插入與刪除

void test_set_insert_erase() {
    set<int> s = {1, 3, 5, 7};

    // 插入：返回pair<iterator, bool>，bool表示是否插入成功（避免重複）
    auto ret1 = s.insert(4); // 插入成功，ret1.second = true
    auto ret2 = s.insert(3); // 重複插入，ret1.second = false

    // 刪除：三種方式
    s.erase(5); // 按值刪除（存在則刪除，返回刪除個數）
    auto pos = s.find(7); // 按迭代器刪除（先查找再刪除，更安全）
    if (pos != s.end()) {
        s.erase(pos);
    }
    s.erase(s.begin(), s.find(4)); // 按區間刪除（刪除[begin, 4)的元素）

    for (auto e : s) {
        cout << e << " "; // 輸出：4
    }
}

（3）查找與區間查詢

void test_set_find() {
    set<int> s = {10, 20, 30, 40, 50};

    // find：查找值，返回迭代器（未找到返回end()）
    auto pos = s.find(30);
    if (pos != s.end()) {
        cout << "找到：" << *pos << endl; // 輸出：30
    }

    // count：返回元素個數（set中僅0或1，用於判斷存在性）
    cout << "20的個數：" << s.count(20) << endl; // 1
    cout << "25的個數：" << s.count(25) << endl; // 0

    // 區間查詢：lower_bound和upper_bound（左閉右開區間）
    auto it_low = s.lower_bound(25); // 返回>=25的第一個元素（30）
    auto it_up = s.upper_bound(40);  // 返回>40的第一個元素（50）
    cout << "區間[" << *it_low << "," << *it_up << ")" << endl; // [30,50)

    // equal_range：返回pair<lower_bound, upper_bound>
    auto ret = s.equal_range(30);
    cout << "lower_bound: " << *ret.first << endl;  // 30
    cout << "upper_bound: " << *ret.second << endl; // 40
}

2.3 multiset：允許重複元素的set

multiset是set的變體，核心差異是允許存儲重複元素，其他特性與set一致：

插入：無返回值（無需判斷重複）；
find：查找時返回中序遍歷的第一個匹配元素；
erase：按值刪除時，刪除所有匹配元素；按迭代器刪除時，僅刪除指定元素。

void test_multiset() {
    multiset<int> ms = {3, 1, 2, 1, 3, 3}; // 允許重複，排序後：1,1,2,3,3,3

    cout << "1的個數：" << ms.count(1) << endl; // 2
    auto pos = ms.find(3); // 返回第一個3的迭代器
    while (pos != ms.end() && *pos == 3) {
        cout << *pos << " "; // 輸出：3 3 3
        ++pos;
    }

    ms.erase(3); // 刪除所有3，結果：1,1,2
}

map與set應用_鍵值對_02

三、map容器：鍵值映射的字典

3.1 map的核心特性

存儲<key, value>鍵值對，key唯一且用於排序，value存儲關聯數據；
底層是紅黑樹，按key的less<T>規則默認升序排序；
支持下標訪問符[]，可直接通過key查找、插入、修改value（最常用特性）。

3.2 常用接口實戰

（1）初始化與遍歷

void test_map_init() {
    // 1. 直接插入pair
    map<string, string> dict;
    dict.insert(pair<string, string>("sort", "排序"));
    dict.insert(make_pair("vector", "向量")); // 推薦用make_pair，更簡潔

    // 2. 列表初始化（C++11+）
    map<string, string> dict2 = {{"left", "左邊"}, {"right", "右邊"}};

    // 遍歷：迭代器遍歷
    for (map<string, string>::iterator it = dict.begin(); it != dict.end(); ++it) {
        // it是指向pair的指針，通過->訪問first和second
        cout << it->first << ":" << it->second << endl;
    }

    // 範圍for遍歷（推薦）
    for (auto& kv : dict2) {
        cout << kv.first << ":" << kv.second << endl;
    }
}

map與set應用_鍵值對_03

（2）下標[]的底層邏輯（核心重點） map的[]是最便捷的操作，其底層實現等價於：

V& operator[](const K& key) {
    // 插入鍵值對，若key不存在則插入pair(key, V())，返回value的引用
    pair<iterator, bool> ret = insert(make_pair(key, V()));
    return ret.first->second;
}

例如：統計元素出現次數（一行代碼實現）

void test_map_count() {
    string arr[] = {"蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "西瓜"};
    map<string, int> countMap;

    // 統計次數：key不存在時插入並初始化value為0，再++；存在時直接++
    for (auto& str : arr) {
        countMap[str]++;
    }

    for (auto& kv : countMap) {
        cout << kv.first << ":" << kv.second << endl; // 蘋果:3 西瓜:2 香蕉:1
    }
}

（3）插入與修改

void test_map_insert_modify() {
    map<int, string> student;

    // 插入：三種方式
    student.insert(make_pair(101, "張三"));
    student.insert(pair<int, string>(102, "李四"));
    student[103] = "王五"; // 下標插入（最簡潔）

    // 修改value：通過迭代器或下標
    student[102] = "李小四"; // 下標直接修改
    auto pos = student.find(101);
    if (pos != student.end()) {
        pos->second = "張大三"; // 迭代器修改
    }

    for (auto& kv : student) {
        cout << kv.first << ":" << kv.second << endl;
        // 輸出：101:張大三 102:李小四 103:王五
    }
}

3.3 map與set的核心差異

特性	set	map
數據結構	單一元素（value=key）	鍵值對`<key, value>`
核心用途	去重、排序、集合操作	鍵值映射、字典、統計計數
元素修改	不支持直接修改（需刪後插）	支持修改value，不支持修改key
下標訪問	不支持	支持`[]`通過key訪問value
內存佔用	較低（僅存key）	較高（存key+value）
插入返回值	`pair<iterator, bool>`	`pair<iterator, bool>`

四、實戰OJ：map與set的經典應用

複雜鏈表的複製（LCR 154）

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        map<Node*, Node*> nodeMap; // 原節點 -> 複製節點

        // 第一次遍歷：複製節點，建立映射
        Node* cur = head;
        while (cur) {
            nodeMap[cur] = new Node(cur->val);
            cur = cur->next;
        }

        // 第二次遍歷：設置next和random指針
        cur = head;
        while (cur) {
            nodeMap[cur]->next = nodeMap[cur->next]; // 複製next
            nodeMap[cur]->random = nodeMap[cur->random]; // 複製random
            cur = cur->next;
        }

        return nodeMap[head];
    }
};

4.2 前K個高頻單詞（LeetCode 692）

class Solution {
public:
    // 自定義比較規則：頻率降序，頻率相同則字典序升序
    struct Compare {
        bool operator()(const pair<string, int>& a, const pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1. 統計頻率
        map<string, int> countMap;
        for (auto& word : words) {
            countMap[word]++;
        }

        // 2. 轉換為vector排序（map是雙向迭代器，不支持sort）
        vector<pair<string, int>> freqVec(countMap.begin(), countMap.end());
        sort(freqVec.begin(), freqVec.end(), Compare());

        // 3. 提取前K個單詞
        vector<string> res;
        for (int i = 0; i < k; ++i) {
            res.push_back(freqVec[i].first);
        }
        return res;
    }
};

解法2：multimap排序（利用紅黑樹自動排序）

vector<string> topKFrequent(vector<string>& words, int k) {
    map<string, int> countMap;
    for (auto& word : words) {
        countMap[word]++;
    }

    // multimap按頻率降序排序（key為頻率，value為單詞）
    multimap<int, string, greater<int>> freqMap;
    for (auto& kv : countMap) {
        freqMap.insert(make_pair(kv.second, kv.first));
    }

    // 提取結果（頻率相同時，multimap按插入順序排列，恰好符合字典序）
    vector<string> res;
    auto it = freqMap.begin();
    while (k-- && it != freqMap.end()) {
        res.push_back(it->second);
        ++it;
    }
    return res;
}

解法3：set特性 + 仿函數（空間最優）

vector<string> topKFrequent(vector<string>& words, int k) {
    map<string, int> countMap;
    for (auto& word : words) {
        countMap[word]++;
    }

    // set按自定義規則排序，自動去重（此處無重複，僅利用排序特性）
    struct Compare {
        bool operator()(const pair<string, int>& a, const pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        }
    };
    set<pair<string, int>, Compare> freqSet(countMap.begin(), countMap.end());

    // 提取前K個
    vector<string> res;
    auto it = freqSet.begin();
    while (k-- && it != freqSet.end()) {
        res.push_back(it->first);
        ++it;
    }
    return res;
}

4.3 兩個數組的交集（LeetCode 349）

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    // 去重排序
    set<int> s1(nums1.begin(), nums1.end());
    set<int> s2(nums2.begin(), nums2.end());

    vector<int> res;
    auto it1 = s1.begin(), it2 = s2.begin();
    // 雙指針遍歷，查找交集
    while (it1 != s1.end() && it2 != s2.end()) {
        if (*it1 < *it2) {
            ++it1;
        } else if (*it2 < *it1) {
            ++it2;
        } else {
            res.push_back(*it1);
            ++it1;
            ++it2;
        }
    }
    return res;
}

五、注意事項

5.1 自定義排序規則無論是map還是set，都可通過傳入仿函數或lambda表達式自定義排序規則：

// 按字符串長度降序排序
struct StrLenCompare {
    bool operator()(const string& a, const string& b) {
        return a.size() > b.size() || (a.size() == b.size() && a < b);
    }
};

set<string, StrLenCompare> s = {"apple", "banana", "pear"};
// 結果：banana（6）、apple（5）、pear（4）

5.2 常見易錯點

修改set的元素：set的元素是const的，直接修改會破壞紅黑樹結構，需先刪除再插入；
map的key重複插入：insert方法插入重複key會失敗，若需修改value，應使用[]或先刪除再插入；
迭代器失效：map/set的插入、刪除操作不會導致其他迭代器失效（紅黑樹的特性），僅被刪除的迭代器失效；
效率誤區：若無需排序，優先使用unordered_map/unordered_set（哈希表實現，平均時間複雜度O(1)），效率更高。

5.3 適用場景總結

用set：需要去重、排序、集合操作（交集、並集、差集）；
用map：需要鍵值映射、統計計數、字典功能；
用multiset/multimap：需要允許重複key的場景；
用unordered_*：無需排序，追求極致檢索效率。

阿森CTO 博客

阿森CTO 博客

博客 / 詳情