当前位置：首页 > news >正文

【C++】手把手教你看懂的 STL map 详解（超详细解析，小白一看就懂！！）

news 2025/6/26 18:23:40

一、前言

二、预备知识

💢关联式容器💢

💢键值对💢

💢哈希结构的关联式容器💢

三、map 详解

🔥map 的介绍

🔥map的模板参数说明

🔥map的构造函数

🔥map的使用

🍇 insert

🍐 operator [ ]

🥝 find

🍍 erase

🍉 swap

🍈 empty

🍌 size

🍋 count

🔥 总结

四、常考面试题

五、共勉

一、前言

【map】 是 STL 中的容器之一，不同于普通容器，它的查找速度极快，常用来存储各种经常被检索的数据，因为容器的底层是【红黑树】。除此之外，还可以借助其特殊的性质，解决部分难题。

二、预备知识

在正式学习 map 之前，首先要有一些预备知识，否则后面可能看不懂相关操作

💢关联式容器💢

在以往的【STL 容器】学习中，我们接触到的都是 序列式容器，比如 string、vector、list、deque 等，序列式容器的特点就是 底层为线性序列的数据结构，就比如 list，其中的节点是 线性存储 的，一个节点存储一个元素，其中存储的元素都可序，但未必有序

【关联式容器】 则比较特殊，其中存储的是 <key, value> 的 键值对，这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置，关联式容器 没有首尾的概念，因此没有头插尾插等相关操作，本文中学习的 map 就属于 关联式容器

注意： stack、queue 等适配器也属于序列式容器，因为他们的底层是 deque 等容器

💢键值对💢

【键值对】是一种用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量：key 和 value，前者表示键值，后者表示实值关联式容器的实现离不开【键值对】

因此在标准库中，专门提供了这种结构 pair 定义如下：

//SGI 版 STL 中的实现
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) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class U1, class U2>pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

pair 中的 first 表示键值，second 则表示实值，在给【关联式容器】 中插入数据时，可以构建 pair 对象

比如下面就构建了一个 键值 key 为 string，实值 value 为 int 的匿名键值对 pair 对象

pair<string, int>("hehe", 123);

可以将此匿名对象传入 关联式容器 中，当然这样写未免过于麻烦了，于是库中设计了一个函数模板 make_pair，可以根据传入的参数，去调用 pair 构建对象并返回

make_pair("hehe", 123);	//构建出的匿名对象与上面的一致

make_pair 的定义如下所示：

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

该函数实际会被编译器优化为 内联函数，因此不会造成过多消耗，可以放心使用

💢哈希结构的关联式容器💢

所以在 C++ 标准中，共提供了四种 哈希结构的关联式容器

unordered_set
unordered_multiset
unordered_map
unordered_multimap

关于 树形结构的关联式容器 将在 二叉搜索树 中学习

树型结构与哈希结构的关联式容器功能都是一模一样的，不过哈希结构查找比树型结构快得多 -> O(1)

注：

STL 中选择的树型结构为红黑树 RB-Tree
树型结构中的元素中序遍历后有序，而哈希结构中的元素无序

三、map 详解

在C++98中，STL提供了底层为 红黑树结构 的一系列关联容器，在查询时效率可以达到 log(N)。但是在较差的情况下，需要比较红黑树的高度次，当树中节点非常多的时候，查询效率也会不理想达到 log(N)

接下来我们将会对，map 进行详细的介绍，其余的容器将会在后续的文章中讲述。

🔥map 的介绍

map是关联容器，它按照特定的次序（按照key来比较）存储由键值 key 和值 value 组合而成的元素。

在map中，键值 key 通常用于排序和唯一的标识元素，而 value 中存储的值与键值 key 产生关联。键值 key 和值 value 的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair::typedef pair value_type;
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在 [ ] 中放入key，就可以找到与key对应的value。
map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

🔥map的模板参数说明

如下图所示：

key: 键值对中 key 的类型
T：键值对中 value 的类型
Compare: 比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则 (一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

注意：在使用map时，需要包含头文件。

#include <map>

🔥map的构造函数

主要有下面三个构造方式：

（1）指定 key 和 value 的类型构造一个空容器

// 构造一个key为string类型，value为int类型的空容器
map<string, int> m1;

（2）拷贝构造某类型容器

// 拷贝构造key为string类型，value为int类型的m1容器的复制品
map<string, int> m2(m1);

（3）使用迭代器区间进行初始化构造

// 使用迭代器拷贝构造m2容器某段区间的复制品
map<string, int> m3(m2.begin(), m2.end());

简单的使用一下：

#include <iostream>
#include <vector>
#include <map>
using namespace std;int main()
{vector<pair<string, int>> arr = { make_pair("G", 71), make_pair("A", 65), make_pair("F", 70) };map<string, int> m1;	//创建一个空的 mapmap<string, int> m2(arr.begin(), arr.end());	//创建包含数据的 mapcout << "m1: " << endl;for (auto e : m1)cout << e.first << " | " << e.second << endl;cout << "========================" << endl;cout << "m2: " << endl;for (auto e : m2)cout << e.first << " | " << e.second << endl;return 0;
}

🔥map的使用

map 的接口虽然比较多，但是常用的也就那么几个

🍇 insert

在 map 中插入键值对 x ，注意 x 是一个键值对，返回值也是键值对

iterator 代替新插入元素的位置，bool 代表是否插入成功

在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair

typedef pair<const key, T> value_type;

下面对于 insert 的插入有两种方式

（1）直接使用 pair 直接来构建键值对

void testmap()
{map<string, string> dict;// 调用pair的构造函数，构造一个匿名对象插入dict.insert(pair<string, string>("sort", "排序"));dict.insert(pair<string, string>("root", "根"));dict.insert(pair<string, string>("left", "左边"));// 遍历for (auto e : dict){cout << e.first << ":" << e.second << endl;}
}

可以看到插入的英文是按照升序进行排列的。

（2）使用 make_pair 函数来构造键值对

构造一个第一个元素设为 x ，第二个元素设为 y 的 pair 对象
模板类型可以传递给 make_pair 的参数隐式推到出来
如果各自类型可以隐式转换，则可以从包含不同类型的其它 pair 对象构造 pair 对象

void testmap()
{map<string, string> dict;// 调用make_pair的构造函数，构造一个匿名对象插入dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("root", "根"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("up", "上面"));// 遍历for (auto e : dict){cout << e.first << ":" << e.second << endl;}
}

推荐使用这个方式插入数据

（3）统计水果出现的次数

既然已经知道 insert 的用法，我就用 map 来统计一下水果出现的次数

void testmap()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countFruit;for (auto& str : arr){map<string, int>::iterator it = countFruit.find(str);if (it != countFruit.end()){it->second++;}else{countFruit.insert(make_pair(str, 1));}}// 遍历for (const auto& kv : countFruit){cout << kv.first << ":" << kv.second << endl;}
}

可以看出水果的次数已经被打印出来啦

但是代码还是可以进行优化，我们知道 insert 的返回值是 pair<iterator，bool>：

其中第一个成员 iterator （pair::first）是指向新插入元素或映射中具有等效键的元素迭代器。

第二个成员 bool （pair::second）是返回插入成功与否的结果

若待插入元素的键值 key 在 map 当中不存在，则 insert 函数插入成功，并返回插入后元素的迭代器和 true。
若待插入元素的键值 key 在 map 当中已经存在，则 insert 函数插入失败，并返回 map 当中键值为 key 的元素的迭代器和 false。

void testmap()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countFruit;for (auto& str : arr){pair<map<string, int>::iterator, bool> ret = countFruit.insert(make_pair(str, 1));// auto ret = countFruit.insert(make_pair(str, 1)); // 也可以写成autoif (ret.second == false){ret.first->second++; // ret.first是插入位置的迭代器,通过迭代器去访问second}}// 遍历for (const auto& kv : countFruit){cout << kv.first << ":" << kv.second << endl;}
}

运行可以看到结果是一样的

🍐 operator [ ]

返回 key 对应的 value :

如果 k 与容器中元素的键匹配，则函数返回对其映射值得引用。
如果 k 与容器中任何元素得键不匹配，该函数将插入一个具有该键得新元素，并返回对其映射值得引用。

对这个函数的调用相当于：

(*((this->insert(make_pair(k,mapped_type()))).first))

operator[ ] 的原理就是：

用 <key，T()> 构造一个键值对，然后调用 insert() 函数将该键值对插入到 map 中
如果 key 已经存在，插入失败，insert 函数返回该 key 所在位置的迭代器
如果 key 不存在，插入成功，insert 函数返回新插入元素所在位置的迭代器
operator[ ] 函数最后将 insert 返回值键值对中的 value 返回

void testmap()
{map<string, string> dict;// 用make_pair函数来构造键值对dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("root", "根"));dict.insert(make_pair("left", "左边"));dict["up"] = "向上"; // up不存在,那么就插入up元素并修改(插入+修改)dict["left"] = "剩余"; // left存在,那么只修改(查找+修改)dict["erase"]; // erase不存在,那么插入// 遍历for (auto e : dict){cout << e.first << ":" << e.second << endl;}
}

对于上面统计水果的次数，其实比较常用的就是 operator[ ]

void testmap()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countFruit;for (auto& str : arr){countFruit[str]++; }// 遍历for (const auto& kv : countFruit){cout << kv.first << ":" << kv.second << endl;}
}

如果水果是第一次出现，那么就先插入，因为是第一次出现，所以水果的次数为 0，插入成功以后，会把插入的这个水果所在的节点里面的次数进行引用返回，也就是返回 0 的引用，那么此时进行++，变成 1 。
如果水果是第二次出现，那么不会插入成功，那么就直接返回这个水果所在的节点迭代器里面的次数,然后再进行++变成 2。

注意：这里的 [ ] 不支持随机访问！

🥝 find

在容器中搜索键值等于 k 的元素,如果找到则返回该元素的迭代器，否则返回map::end的迭代器。

void testmap()
{map<string, string> dict;// 用make_pair函数来构造键值对dict["sort"] = "排序";dict["up"] = "向上";;dict["left"] = "左边";dict["root"] = "根";auto pos = dict.find("root");if (pos != dict.end()){cout << "找到了" << endl;cout << pos->first << ":" << pos->second << endl;}
}

🍍 erase

从 map 容器中移除单个元素或一组元素

（1）从 map 容器中移除单个元素

void testmap()
{map<string, string> dict;// 用make_pair函数来构造键值对dict["sort"] = "排序";dict["up"] = "向上";;dict["left"] = "左边";dict["root"] = "根";auto pos = dict.find("root");if (pos != dict.end()){dict.erase(pos);cout << "删除成功" << endl;}// 遍历for (auto e : dict){cout << e.first << ":" << e.second << endl;}
}

（2）从 map 容器中移除一组元素（【first，last））

void testmap()
{map<string, string> dict;// 用make_pair函数来构造键值对dict["sort"] = "排序";dict["up"] = "向上";;dict["left"] = "左边";dict["root"] = "根";auto pos = dict.find("root");if (pos != dict.end()){dict.erase(pos, dict.end()); // 删除从pos位置开始后面所有的元素cout << "删除成功" << endl;}// 遍历for (auto e : dict){cout << e.first << ":" << e.second << endl;}
}

可以看到 root 后面的元素已经删掉了

🍉 swap

交换 map 容器中的元素

void testmap()
{map<string, string> dict1;dict1["sort"] = "排序";dict1["up"] = "向上";;dict1["left"] = "左边";dict1["root"] = "根";map<string, string> dict2;dict2["size"] = "大小";dict2["erase"] = "删除";dict2["clear"] = "清除";dict2["insert"] = "插入";dict1.swap(dict2); // 交换两个对象中的元素for (auto e1 : dict1){cout << e1.first << ":" << e1.second << endl;}cout << endl;for (auto e2 : dict2){cout << e2.first << ":" << e2.second << endl;}
}

可以看到两个对象的元素已经被交换

🍈 empty

检测 map 中的元素是否为空，是返回 true，否则返回 false

void testmap()
{map<string, string> dict1;dict1["sort"] = "排序";dict1["up"] = "向上";dict1["left"] = "左边";dict1["root"] = "根";map<string, string> dict2;cout << dict1.empty() << endl; // 不为空,返回falsecout << dict2.empty() << endl; // 为空,返回true
}

🍌 size

返回 map 中的有效元素个数

void testmap()
{map<string, string> dict;dict["sort"] = "排序";dict["up"] = "向上";dict["left"] = "左边";dict["root"] = "根";cout << dict.size() << endl;
}

🍋 count

获取 map 容器中指定 k 值的元素个数

void testmap()
{map<string, string> dict;dict["sort"] = "排序";dict["up"] = "向上";dict["left"] = "左边";dict["root"] = "根";cout << dict.count("root") << endl; // root的个数cout << dict.count("hello") << endl; // hello的个数
}

这个接口对于 map 容器其实没有太大用处，因为 map 当中的每个键值 key 和值 value 都是唯一的。

🔥 总结

map 中的元素是键值对
map 中的 key 是唯一的，并且不能修改
默认按照小于的方式对 key 进行比较
map 中的元素如果用迭代器去遍历，可以得到一个有序的序列
map 的底层为平衡搜索树（红黑树），查找效率比较高 O(logN)
支持 [ ] 操作符，operator[ ] 中实际进行插入查找

四、常考面试题

题目描述：前 K 个高频单词
题目链接：692. 前K个高频单词 - 力扣（LeetCode）

利用 map 建立 <string, int> 的映射关系，在按照字典序排序的同时统计出每个单词的出现频率，再通过快排依照数量进行二次排序，选择前 k 个高频单词即可
只需要将 仿函数进行设计即可：优先按照出现频率排序，如果频率相同，则按照字典序排序即可

//map + sort
class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {//统计每个单词出现的频率，同时先按照字典序排序map<string, int> table;for(auto e : words)table[e]++;//将处理好的数据存入数组中vector<pair<string, int>> vTable(table.begin(), table.end());//按照出现频率进行二次排序sort(vTable.begin(), vTable.end(), [](const pair<string, int>& kv1, const pair<string, int>& kv2)->bool{return kv1.second == kv2.second ? kv1.first < kv2.first : kv1.second > kv2.second;});//取出前 k 个高频单词vector<string> vs;for(int i = 0; i < k; i++)vs.push_back(vTable[i].first);return vs;}
};