C++ map/multimap 完全指南：从红黑树原理到算法实战

multimap

multimap 的参考文档： multimap

map 类的介绍

map 的声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 value 的类型。set 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数。map 底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map 底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按 key 有序顺序遍历的。

两条直线相交，其中一条直线上有一个点 A，过点 A 作与另一条直线的垂线，焦点是 B——

A 点和直线上的 B 也可以是成映射关系。

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;

pair 类型介绍

map 底层的红黑树节点中的数据，使用 pair<Key，T> 存储键值对数据。

typedef pair<const Key, T> value_type; 
template <class T1, class T2> struct pair { 
    typedef T1 first_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) {} 
    template<class U, class V> pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {} 
}; 
template <class T1, class T2> inline pair<T1, T2> make_pair(T1 x, T2 y) { 
    return (pair<T1, T2>(x, y)); 
}

map 和 multimap 的底层原理浅解

底层原理

map 和 multimap 底层使用红黑树（平衡二叉搜索树）实现。

键不可修改（key），值可修改（value）

typedef std::pair<const Key, T> value_type;

map 使用层详解

增删查

map 增接口，插入的 pair 键值对数据，跟 set 所有不同，但是查和删的接口只用关键字 key 跟 set 是完全类似的。不过 find 返回 iterator，不仅仅可以确认 key 在不在，还找到 key 映射的 value，同时通过迭代还可以修改 value。

insert

上面是 C++98 标准的插入操作，下面是 C++11 的插入操作。

map 的构造

map 对象的构造——

map：C++98 的插入操作

插入操作的多种方式——

C++98 风格的插入 —— 构造 pair 对象插入：

map：C++11 的插入操作

C++11 风格的插入 —— 使用初始化列表：

map 的 key 唯一性

这个插入会失败，因为'left'已存在，所以不会再插入。

遍历方式：迭代器遍历

再举个例子——

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

C++11：范围 for

C++17：结构化绑定

查找操作：find

查：find

auto it = dict.find("key"); 
if (it != dict.end()) { 
    // 找到 
}

at

count

// 查找 k，返回 k 所在的迭代器，没有找到返回 end()
iterator find (const key_type& k);
// 查找 k，返回 k 的个数
size_type count (const key_type& k) const;

删除（用范围 for 遍历显示结果）：erase

auto pos = dict.find("left"); 
if (pos != dict.end()) { 
    dict.erase(pos); 
}

也可直接通过键删除——

dict.erase("left");

技术笔记

以字典 dict 为例，展示词频统计的两种实现方式

查找 + 插入

// 查找 + 插入组合 
map<string, int> countMap; 
for (auto& e : arr) { 
    auto it = countMap.find(e); 
    if (it != countMap.end()) { 
        it->second++; // 存在则递增 
    } else { 
        countMap.insert({ e,1 }); // 不存在则插入 
    } 
}

存在时直接通过迭代器修改 value（second），不存在时使用 insert 插入新的 pair。

利用 operator[] 搞定 dict 查找

// 利用 operator[] 的特性 
for (auto e : arr) { 
    countMap[e]++; 
}

map 和 multimap 的差异

multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 key 冗余，那么 insert / find / count / erase 都围绕着支持关键值 key 冗余有所差异，这里跟 set 和 multiset 完全一样，比如 find 时，有多个 key，返回中序第一个。其次就是 multimap 不支持 []，因为支持 key 冗余，[] 就只能支持插入了，不能支持修改。

map 的数据修改

前面提到 map 支持修改 mapped_type 数据，不支持修改 key 数据，修改关键字数据，破坏了底层搜索树的结构。map 第一个支持修改的方式时通过迭代器，迭代器遍历时或者 find 返回 key 所在的 iterator 修改。map 还有一个非常重要的修改接口 operator[]，但是 operator[] 不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口需要注意。

从内部实现角度，map 这里把我们传统说的 value 值，给的是 T 类型，typedef 为 mapped_type。而 value_type 是红黑树结点中存储的 pair 键值对值。日常使用中，我们还是习惯将这里的 T 映射值叫做 value。

Member types 
key_type->The first template parameter(Key) 
mapped_type->The second template parameter(T) 
value_type->pair<const key_type, mapped_type> 

// 查找 k，返回 k 所在的迭代器，没有找到返回 end()， 
// 如果找到了通过 iterator 可以修改 key 对应的 mapped_type 值 
iterator find(const key_type& k);

// 文档中对 insert 返回值的说明 
// The single element versions (1) return a pair, with its member pair::first 
//set to an iterator pointing to either the newly inserted element or to the 
//element with an equivalent key in the map.The pair::second element in the pair 
//is set to true if a new element was inserted or false if an equivalent key 
//already existed. 
// insert 插⼊⼀个 pair<key, T> 对象 
// 1、如果 key 已经在 map 中，插⼊失败，则返回⼀个 pair<iterator,bool> 对象， 
// 返回 pair 对象 first 是 key 所在结点的迭代器，second 是 false 
// 2、如果 key 不在在 map 中，插⼊成功，则返回⼀个 pair<iterator,bool> 对象， 
// 返回 pair 对象 first 是新插⼊ key 所在结点的迭代器，second 是 true 
// 也就是说无论插入成功还是失败，返回 pair<iterator,bool> 对象的 first 都会指向 key 所在的迭代器 
// 那么也就意味着 insert 插⼊失败时充当了查找的功能，正是因为这⼀点，insert 可以⽤来实现 operator[] 
// 需要注意的是这⾥有两个 pair，不要混淆了，⼀个是 map 底层红⿊树节点中存的 pair<key, T>， 
// 另⼀个是 insert 返回值 pair<iterator, bool> 
pair<iterator, bool> insert(const value_type& val);

mapped_type& operator[] (const key_type& k);

// operator 的内部实现 
mapped_type& operator[] (const key_type& k) { 
    // 1、如果 k 不在 map 中，insert 会插⼊ k 和 mapped_type 默认值， 
    // 同时 [] 返回结点中存储 mapped_type 值的引⽤，那么我们可以通过引用修改返映射值。所以 [] 具备了插入 + 修改功能 
    // 2、如果 k 在 map 中，insert 会插⼊失败，但是 insert 返回 pair 对象的 first 是指向 key 结点的迭代器， 
    // 返回值同时 [] 返回结点中存储 mapped_type 值的引用，所以 [] 具备了查找 + 修改的功能 
    pair<iterator, bool> ret = insert({ k, mapped_type() }); 
    iterator it = ret.first; 
    return it->second; 
}

operator[]（重点）

文档链接： operator[]

插入默认值

// 插入 
dict["sort"]; // 插入 {"sort", ""}，string 默认构造为空字符串

插入 + 修改

// 插入 + 修改 
dict["left"] = "左边"; // 插入 {"left", "左边"}

修改已存在的值

// 查找 
cout << dict["sort"] << endl; // 修改已存在的 key 的 value

查找

// 查找 
cout << dict["sort"] << endl; // 如果不存在会插入空字符串！

at()

修改存在的 key

dict.at("left") = "xxxxxxxxxx"; // 安全修改

访问不存在的 key（抛异常）

// dict.at("insert") = "xxxxxxxxxx"; // 抛出 std::out_of_range 异常

对比：operator[] VS at( )

map 算法题实战

随机链表的复制

力扣链接： 138. 随机链表的复制

题目描述：

图解题给示例

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点，拷贝结点}建立映射关系放到 map 中，控制随机指针会非常简单方便，这里体现了 map 在解决一些问题时的价值，完全是降维打击。

算法实现

/* // Definition for a Node. 
class Node { 
public: 
    int val; 
    Node* next; 
    Node* random; 
    Node(int _val) { 
        val = _val; 
        next = NULL; 
        random = NULL; 
    } 
}; */ 
class Solution { 
public: 
    Node* copyRandomList(Node* head) { 
        map<Node*,Node*> nodeMap; 
        Node* copyhead =nullptr,*copytail = nullptr; 
        Node* cur= head; 
        while(cur) { 
            Node* copy=new Node(cur->val); // 尾随 
            if(copytail == nullptr) { 
                copyhead = copytail=copy; 
            } else { 
                copytail->next=copy; 
                copytail=copy; 
            } 
            nodeMap.insert({cur,copy}); 
            cur=cur->next; 
        } 
        cur = head; 
        Node* copy = copyhead; 
        while(cur) { 
            if(cur->random == nullptr) { 
                copy->random = nullptr; 
            } else { 
                copy->random = nodeMap[cur->random]; 
            } 
            cur = cur->next; 
            copy = copy->next; 
        } 
        return copyhead; 
    } 
};

时间复杂度：O(n)，空间复杂度：O(n)。

解题思路推导

本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！

前 K 个高频单词

力扣链接： 692. 前 K 个高频单词

题目描述：

题目理解

本题目我们利用 map 统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

算法实现

写法 1

用排序找前 k 个单词，因为 map 中已经对 key 单词排序过，也就意味着遍历 map 时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到 vector 中用一个稳定的排序就可以实现上面特殊要求，但是 sort 底层是快排，是不稳定的，所以我们要用 stable_sort，他是稳定的。

// 方法 1 
class Solution { 
public: 
    struct kv_pair { 
        bool operator()(const pair<string, int>& kv1,const pair<string, int> kv2) { 
            return kv1.second > kv2.second; 
        } 
    }; 
    vector<string> topKFrequent(vector<string>& words, int k) { 
        map<string, int> countMap; 
        for(auto& str : words) { 
            countMap[str]++; 
        } 
        // multimap<int,string> sortMap; // 降序 
        vector<pair<string, int>> v(countMap.begin(), countMap.end()); 
        // sort(v.begin(),v.end(),kv_pair()); // 稳定的排序 
        stable_sort(v.begin(), v.end(), kv_pair()); 
        for (auto& [k, v] : v) { 
            cout << k << ":" << v << endl; 
        } 
        cout << endl; 
        vector<string> ret; 
        for (size_t i = 0; i < k; ++i) { 
            ret.push_back(v[i].first); 
        } 
        return ret; 
    } 
};

时间复杂度：O(nlogn)，空间复杂度：O(n)。

写法 2

自己实现一个仿函数，控制比较逻辑。

将 map 统计出的次数的数据放到 vector 中排序，或者放到 priority_queue 中来选出前 k 个。利用仿函数强行控制次数相等的，字典序小的在前面。

次数大的在前面，次数相等的、字典序小的在前面——

// 方法 2 
class Solution { 
public: 
    // 自己实现一个仿函数，控制比较逻辑 
    struct kv_pair { 
        // 次数大的在前面，次数相等的、字典序小的在前面 
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) { 
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first); 
        } 
    }; 
    vector<string> topKFrequent(vector<string>& words, int k) { 
        map<string, int> countMap; 
        for(auto& str : words) { 
            countMap[str]++; 
        } 
        // multimap<int,string> sortMap; // 降序 
        vector<pair<string,int>> v(countMap.begin(),countMap.end()); 
        sort(v.begin(),v.end(),kv_pair); 
        for(auto& [k,v] : v) { 
            cout<< k << ":" << v << endl; 
        } 
        cout << endl; 
        vector<string> ret; 
        for(size_t i = 0;i < k;++i) { 
            ret.push_back(v[i].first); 
        } 
        return ret; 
    } 
};

时间复杂度：O(nlogn)，空间复杂度：O(n)。

写法 3

使用优先级队列，大堆提供的小于的比较逻辑。

次数大的在前面，次数相等的，字典序小的在前面——

// 方法 3 
class Solution { 
public: 
    struct kv_pair{ 
        // 次数大的在前面，次数相等的，字典序小的在前面 
        // 优先级队列，大堆提供的小于的比较逻辑 
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) { 
            return kv1.second < kv2.second || (kv1.second == kv2.second && kv1.first > kv2.first); 
        } 
    }; 
    vector<string> topKFrequent(vector<string>& words, int k) { 
        map<string,int> countMap; 
        for(auto& str : words) { 
            countMap[str]++; 
        } 
        // 大堆 
        priority_queue<pair<string,int>,vector<pair<string,int>>, kv_pair> pq(countMap.begin(),countMap.end()); 
        vector<string> ret; 
        for(size_t i = 0;i < k;++i) { 
            ret.push_back(pq.top().first); 
            pq.pop(); 
        } 
        return ret; 
    } 
};

时间复杂度：O(nlogn)，空间复杂度：O(n)。

完整代码示例与实践演示

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1 
#include<iostream> 
#include<map> 
#include<string> 
using namespace std; 

void Test_map1() { 
    map<string, string> dict; 
    // C++98 
    pair<string, string> kv1("sort", "排序"); 
    dict.insert(kv1); 
    dict.insert(pair<string, string>("left", "左边")); 
    dict.insert(make_pair("pair", "左边")); 
    // C++11 
    dict.insert({ "right","右边" }); 
    //dict.insert({ kv1,pair<string,string>("left","左边") }); 
    dict.insert({ { "string","字符串" }, { "map","地图，映射" } }); 
    // key 相同就不会再插入，value 不相同也不会插入 
    dict.insert({ "left","左边 xxxx" }); 
    
    map<string, string>::iterator it = dict.begin(); 
    while (it != dict.end()) { 
        //cout << (*it).first << ":" << (*it).second << endl; 
        cout << it->first << ":" << it->second << endl; 
        //cout << it.operator->()first << ":" << it.operator->()second << endl; 
        ++it; 
    } 
    cout << endl; 
    
    for (auto& e : dict) { 
        cout << e.first << ":" << e.second << endl; 
    } 
    cout << endl; 
    
    // 结构化绑定 C++17 
    auto [x, y] = kv1; 
    // 使用结构化绑定遍历 
    //for (auto [k, v] : dict) 
    //for (auto& [k, v] : dict) 
    for (const auto& [k, v] : dict) { 
        cout << k << ":" << v << endl; 
    } 
    cout << endl; 
    
    // 查找和删除 
    auto pos = dict.find("left"); 
    if (pos != dict.end()) { 
        dict.erase(pos); 
    } 
    // 再次遍历显示结果 
    for (const auto& [k, v] : dict) { 
        cout << k << ":" << v << endl; 
    } 
    cout << endl; 
}

void Test_map2() { 
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; 
    map<string, int> countMap; 
    for (auto& e : arr) { 
        auto it = countMap.find(e); 
        if (it != countMap.end()) { 
            it->second++; 
        } else { 
            countMap.insert({ e,1 }); 
        } 
        countMap[e]++; 
    } 
    for (auto e : arr) { 
        countMap[e]++; 
    } 
    for (auto& [k, v] : countMap) { 
        cout << k << ":" << v << endl; 
    } 
    cout << endl; 
    
    map<string, string> dict; 
    // 插入 
    dict["sort"]; 
    // 插入 + 修改 
    dict["left"] = "左边"; 
    // 修改 
    dict["sort"] = "排序"; 
    // 查找 
    cout << dict["sort"] << endl; 
    // 纯粹的查找 + 修改 
    // at 
    dict.at("left") = "xxxxxxxxxx"; 
    // key 不存在，会抛异常 
    dict.at("insert") = "xxxxxxxxxx"; 
    //报错 
    // 0x00007FF9E4CE837A 处 (位于 map 的使用.exe 中) 
    // 有未经处理的异常：Microsoft C++ 
    // 异常：std::out_of_range（抛异常），位于内存位置 0x000000279D0FEBE0 处。 
}

void Test_map3() { 
    multimap<string, string>dict; 
    dict.insert({ "right","右边" }); 
    dict.insert({ "left","左边" }); 
    dict.insert({ "right","右边 xxx" }); 
    dict.insert({ "right","右边" }); 
    for (const auto& [k, v] : dict) { 
        cout << k << ":" << v << endl; 
    } 
    cout << endl; 
}

int main() { 
    Test_map1(); 
    //Test_map2(); 
    //Test_map3(); 
    return 0; 
}

运行演示

Test_map1()

Test_map2()

Test_map3()

技术笔记

下面这里博主手记的墨水旋开了，uu 们先凑合凑合看一下，内容和本文大体一致——