主页：HABUO🍁主页：HABUO

🍁C++入门到精通专栏🍁

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

目录

📕1、map和set的介绍

📕2、pair结构

📕3、set详解

📕4、map详解

📕5、multimap和multiset

📕6、总结

前言：

前篇博客我们了解了二叉搜索树，本篇博客我们就可以来了解map和set，其中重点讲解map和set的使用方法以及一些特性,以及讲解muti为前缀的map/set和普通map/set的区别,其中会学到一个重要的结构pair,这个结构用处还是很多的。

📕1、map和set的介绍

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面 存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？ 关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

map

  • map是C++标准模板库（STL）中的关联容器，它提供了一种键-值对的存储方式，其中键（key）是唯一的，每个键都映射到一个值（value）。

  • map内部的元素总是按照键的升序排列（默认情况下），除非用户指定了自定义的比较函数。

  • map通常基于红黑树（一种平衡二叉搜索树）实现，因此其查找、插入和删除操作的时间复杂度为O(log n)。

set

  • set也是STL中的关联容器，它只存储键（key），并且每个键是唯一的。

  • set中的元素也是按升序排列（默认情况下），同样基于红黑树实现。

  • 由于set只存储键，它常用于检查元素是否存在、去重等场景。

简单来说：set是key模型,本质是确定一个元素在不在此容器中,也就是说set中存储的是一个单一数据。map和set的区别就是,map中存储的并不是一个单一数据,而是存储了一个pair结构!

可以观察到map的模板参数中有key和T
而set的模板参数只有T，请注意它们之中都有一个比较函数参数，compare等到本文结束，一道小试牛刀的题中就会知道它的用处。

set和map结构中遍历出来是数据有序并且去重的!

map和set都只支持增删查,不支持改!（当然对于map而言是键值，对应的值是可以重的）

📕2、pair结构

pair结构实际上是一个键值对，以下是对于键值对的介绍:

template <class T1, class T2>
struct pair
{
	T1 first;
	T2 second;
	pair(): first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};

它实际上就是封装了两个可以是不同类型的数，它可以用作中英字典，存储pair<string,string>的结构，first存储中文second存储对应的英文解释，非常好用!

map中存储的就是pair结构，所以map也叫存储的KV模型，因为first和second对应key和value

map的三种常见使用方法:

insert的意思就是如果已经存在就不会插入，返回已经存在的pair结构，如果不存在，就进行插入，并返回刚插入的pair结构

1. 方法一: 定义pair对象后插入

map<string,string> dict;
pair<string,string> kv1("排序","sort");
pair<string,string> kv2("左边","left");
dict.insert(kv1);
dict.insert(kv2);

2. 方法二: 使用匿名对象插入

map<string,string> dict;
dict.insert(pair<string,string>("排序","sort"));
dict.insert(pair<string,string>("左边","left"));

3. 方法三: 使用make_pair插入

map<string,string> dict;
dict.insert(make_pair("排序","sort"));
dict.insert(make_pair("左边","left"));

make_pair是最常用的方法!

📕3、set详解

set的插入函数insert

插入我们需要关心三点：一是插入可以不用写pos,直接插入，二是可以插入一段迭代器区间，三是插入的返回值也是一个pair结构，pair中存储了布尔类型和迭代器,分代表此次插入是否成功,若成功则返回被插入元素迭代器的位置一般来讲第一个用的相对比较多

set的查找和删除函数find,erase

对于find相信大家会有疑惑，不是C++库里面算法不是提供了find，set怎么单独弄出来一个find？事实上，我们都知道，set底层是二叉搜索树，查找一个数的效率是比较高的，但是算法里的find就是通过循环迭代查找的如下图所示，为优化性能set单独有一个set就是因为它的效率为O(logN)

int main() {
    // 声明set
    set<int> numbers;

    // 插入元素
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    numbers.insert(2);  // 重复元素，不会被插入
    //排序+去重
	set<int>::iterator it = numbers.begin();
	while (it != numbers.end())//set底层是二叉搜索树不支持修改
	{
		cout << *it << " ";
		++it;;
	}
	cout << endl;
    // 遍历set
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;  // 输出: 2 5 8 (自动排序)

    set <int> copy(s);//可以用来拷贝一份
}

📕4、map详解

前面我们了解了map里面主要存储的是键值对（pair结构），对其插入也做了了解，下面我们来了解遍历、删除等其它用法

map的删除和查找:

map<string, int> m;
m.erase("key");    // 删除元素
// 查找操作
auto it = m.find("key");  // 查找键，返回迭代器
if (it != m.end()) {
    cout << "找到: " << it->first << " -> " << it->second << endl;
}

erase和find传参只用传pair中的first类型的参数,即可完成任务,并且find的返回值和set的find是一样的。

map的遍历：

map的遍历相对于set是不一样的，并且map的也提供了operator[]重载，让我们来见识一下：

    map<int, int> m;
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(3, 3));
	m.insert(pair<int, int>(2, 2));
	m.insert(make_pair(4, 4));//日常大家喜欢用make_pair,因为他不用声明模板参数，自动推演  
    map<int, int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;//这里为了可读性省略了一个->
		++it;;
	}

    for (auto e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}

operator[]：

map的方括号设计的十分巧妙，它的参数是pair中的first，返回值是pair中的second,并且它返回的是引用,可以根据first修改second它可以用来计数,请看如下demo代码:

    string strs[] = { "西瓜", "樱桃", "西瓜", "西瓜", "苹果", "西瓜", "西瓜" };
	map<string, int> countMap;
	for (auto& str : strs)
	{
		countMap[str]++;
	}

也就是说，方括号自带插入功能，当出现第一个"西瓜"时，会自动把"西瓜"插入到map中，第二次遇见"西瓜"时，会将西瓜的计数++变成2。具体可以看上述等效代码(*((this->insert (make_pair (k, mapped_type ()))).first)).second  

1.(this->insert (make_pair (k, mapped_type ())))解释：这个就是调用map的insert函数，注意函数的返回值是pair结构，插入键值如果已经存在则返回已经存在的这个节点的迭代器，如果不存在就返回新插入节点的迭代器，所以此句相当于pair<iterator,bool>

2. ((this->insert (make_pair (k, mapped_type ()))).first)解释：访问pair结构第一个参数iterator

3. *((this->insert (make_pair (k, mapped_type ()))).first)解释：对返回的pair<iterator,bool>第一个参数解引用相当于pair<key_type, mapped_type>

4. (*((this->insert (make_pair (k, mapped_type ()))).first)).second解释：相当于访问pair<key_type, mapped_type>的第二个参数即key对应的值。

综上，我们就了解了为什么countMap[str]++可以对第二个参数进行++了。

这里用insert原因：
1、如果k不在map中，则插入pair<k， mapped_type()>，再返回映射对象的引用
2、如果k在map中，则插入失败，返回k所在节点中的映射对象的引用

map的operator[]三层作用：        
1、插入 2、查找k对应的映射对象（但一般不会用他去做查找，因为如果key不在会插入数据） 3、修改k对应的映射对象

总结：

遍历出来的数据是按K排序的，因为底层是搜索树，遍历走的树的中序

其它统计次数的方法：

    string strs[] = { "西瓜", "樱桃", "西瓜", "西瓜", "苹果", "西瓜", "西瓜"};
	map<string, int> countMap;
	for (auto& str : strs)
	{
		map<string, int>::iterator ret = countMap.find(str);
		if (ret != countMap.end())
		{
			ret->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}


    string strs[] = { "西瓜", "樱桃", "西瓜", "西瓜", "苹果", "西瓜", "西瓜" };
	map<string, int> countMap;
	for (auto& str : strs)
	{
		pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
		if (ret.second == false)
			ret.first->second++;
	}

📕5、multimap和multiset

map和set的遍历是有序并且去重的，也就是说里面没有相同的元素，但是STL提供了multimap和multiset，它们允许存在相同的元素！

它们的使用方法和map、set没有什么区别。小的区别就在于：1. 允许键值冗余（set和map）2. 由于支持元素冗余所以multimap不支持方括号了！3. 因为支持键值冗余，存在了多个key值，因此insert也和map、set不一样了，只要插入就一定能成功

插入相同的数据时,它也会保存

小试牛刀：

前K个高频单词

本题目不仅仅要找出前k个高频的单词并且还要按照字典序来排序，也就是说，要满足两个排序的条件：字符串出现的次数和字符串在字典中的顺序!

想到要计数,当然是用map啦!但是我们统计次数时，数据是放在第二个参数的，那么map默认排序是按照第一个参数进行排，聪明的你一定会想到，统计完之后将它们调转一下位置不就ok，但是这又会遇到第二个问题：map的key键是不允许存在重复的，万一次数有一样的，那这不就完了，依然聪明的你，会想到我们刚刚讲述的multimap。

综上思路：1.我们可以用map进行统计次数，此时刚刚好按照字母进行排序满足题意

2.统计之后，我们再进行用mltimap再进行一次存储，不过此时，是次数做key，字符串做value

3.mltimap的前k个值即是题中所要的答案

完整代码如下：

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        //统计出现次数
        map<string, int> countMap;
        for(auto e : words)
        {
            countMap[e]++;
        }
        //按照由高到低进行排序
        multimap<int, string, greater<int>> countSort;
        for(auto kv: countMap)
        {
            countSort.insert(make_pair(kv.second, kv.first));
        }
        //插入到数组中
        vector<string> ret;
        for(auto r : countSort)
        {
            ret.push_back(r.second);
            k--;
            if(k == 0)
            {
                break;
            }
        }
        return ret;
    }
};

有任何疑问都可以私信我！

📕6、总结

map和set是C++中非常重要的关联容器：

  • map用于键值对映射，适合字典-like的数据结构

  • set用于唯一元素集合，适合去重和成员检查

  • 两者都提供O(log n)的查找、插入、删除操作

  • 元素自动排序，基于红黑树实现

熟悉map和set的使用在平常做题时会有大用处，虽然平时用的更多的是unordered_map/set，但是它们的使用方法基本一致，掌握这些容器将一定程度提高你处理结构化数据的能力！

# c++ # c语言 # 开发语言 # 后端 # 学习 # 数据结构 # 算法
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026最新AI Agent高频面试题（分类型精简详解）

本文梳理AI Agent高频面试考点，覆盖基础概念、架构、推理规划、工具调用、记忆、RAG融合、多智能体与工程落地。区分Agent、Workflow与普通工具调用，讲解ReAct、Plan‑and‑Execute等主流范式，分析三级记忆机制与上下文溢出的解决办法，对比传统RAG与Agent‑RAG差异，介绍多智能体协作模式。同时总结落地痛点、优化手段和安全风控要点，划分初/中/高级面试复习重点，可

avatar AI Agent技术社区
cover

深入理解 AI Agent · AGENT #03：从单 Agent 到多 Agent

avatar AI Agent技术社区
cover

AI Agent安全风险启示：工业巡检机器人的AI安全管控

avatar AI Agent技术社区