?引言
C++ 标准模板库（STL）中的 set 和 map 是两种非常实用的关联式容器。它们具备快速查找、有序存储的特点，因而在很多需要高效数据管理的场景中被广泛应用。本文将深入讲解 set 和 map 的用法，并通过实际例子分析如何将它们应用到编程问题中。
一、关联式容器的基础知识
1.1 什么是关联式容器？
在 STL 中，容器分为两大类：序列式容器和关联式容器。
序列式容器：包括vector、deque、list 等，它们的特点是按元素插入的顺序存储数据，并提供快速的随机访问能力。然而，在这些容器中查找某个特定值的效率较低（线性时间复杂度 O(n)），不适合频繁查找的情况。关联式容器：包括 set、map、multiset、multimap 等，它们采用键值对（key-value）的形式存储数据，可以通过键快速找到相应的值。这类容器的查找、插入和删除操作的时间复杂度较低（O(log n)），且存储的元素自动按键排序。 关联式容器的特点如下：
高效查找：set 和 map 可以在 O(log n) 的时间内查找、插入或删除数据。自动排序：存储的元素按键自动排序，默认是升序，可以通过自定义比较函数实现降序排序。键值对存储：对于 map 和 multimap，每个元素都以键值对的形式存储，即每个键对应一个值。 1.2 键值对概念
map 和 multimap 是基于键值对（key-value pair）结构的关联式容器。键值对是一种用于表示一一对应关系的数据结构。在键值对中，key 表示键，value 表示值。通过 key 可以快速定位到 value，这种设计非常适合用于数据查找和映射。
1.在 C++ 中，标准库提供了 pair 结构用于实现键值对。例如：
pair<string, int> p("Alice", 90); cout << "Name: " << p.first << ", Score: " << p.second << endl;pair 中的 first 表示 键值，second 则表示 实值，在给 关联式容器 中插入数据时，可以构建 pair 对象。
2.利用函数实现键值对：
make_pair 是一个方便的工具函数，用于创建 pair 对象。通过它，你可以简洁地创建键值对、返回多个值以及处理成对的数据。在 STL 容器（如 map 和 multimap）中使用 make_pair，不仅使代码简洁，而且提高了代码的可读性。
#include <iostream>#include <vector>#include <algorithm>#include <utility>int main() { std::vector<std::pair<int, std::string>> items; // 使用 make_pair 添加元素 items.push_back(std::make_pair(3, "Apple")); items.push_back(std::make_pair(1, "Banana")); items.push_back(std::make_pair(2, "Cherry")); // 按第一个元素排序 std::sort(items.begin(), items.end()); for (const auto& item : items) { std::cout << item.second << " "; } std::cout << std::endl; return 0;}1.3、树型结构的关联式容器
所以在 C++ 标准中，共提供了四种 树型结构的关联式容器
set
multiset
map
multimap
关于 哈希结构的关联式容器 将在 哈希表 中学习
树型结构与哈希结构的关联式容器功能都是一模一样的，不过 哈希结构查找比树型结构快得多 -> O(1)
注： STL 中选择的树型结构为 红黑树 RB-Tree 树型结构中的元素 中序遍历 后有序，而哈希结构中的元素无序
二、set 容器详解
set 是 C++ STL 中的一个集合容器，用于存储不重复的元素，且所有元素是有序存储的。它适合需要唯一性和快速查找的场景。
2.1 set 的特点
排序+去重
唯一性：set 中的每个元素都是唯一的，不能重复，重复元素不插入。自动排序：set 会自动对元素进行排序，默认情况下按升序排列。无键值对：set 只存储键值，数据即键值，不存在 key-value 对。 2.2 set 的常用操作
| 操作 | 作用 |
|---|---|
insert | 插入一个元素 |
erase | 删除一个元素 |
find | 查找一个元素，返回其迭代器 |
count | 统计元素个数，set 中最多为 1 |
empty | 判断 set 是否为空 |
size | 返回 set 中元素的个数 |
clear | 清空 set 中的所有元素 |
begin、end | 返回迭代器，支持遍历 |
代码演示：
#include <iostream>#include <vector>#include <set>using namespace std;int main(){vector<int> arr = { 7,3,6,9,3,1,6,2 };set<int> s1(arr.begin(), arr.end());//迭代器遍历cout << "迭代器遍历结果: ";set<int>::iterator it = s1.begin();while (it != s1.end()){cout << *it << " ";++it;}cout << endl;//判空、求大小cout << "===================" << endl;cout << "empty(): " << s1.empty() << endl;cout << "size(): " << s1.size() << endl;cout << "max_size(): " << s1.max_size() << endl;//插入元素cout << "===================" << endl;cout << "insert(5): ";s1.insert(5);for (auto e : s1) cout << e << " ";cout << endl;//删除元素cout << "===================" << endl;cout << "erase(6): ";s1.erase(6);for (auto e : s1) cout << e << " ";cout << endl;//交换、查找、清理cout << "===================" << endl;set<int> s2(arr.begin() + 5, arr.end());s1.swap(s2);cout << "s1: ";for (auto e : s1) cout << e << " ";cout << endl;cout << "s2: ";for (auto e : s2) cout << e << " ";cout << endl;cout << "s1.find(9): ";cout << (s1.find(9) != s1.end()) << endl;cout << "s2.clear(): " << endl;s2.clear();cout << "s1: ";for (auto e : s1) cout << e << " ";cout << endl;cout << "s2: ";for (auto e : s2) cout << e << " ";cout << endl;return 0;}
至于 count 也可以用来查找元素是否存在，对于 set 来说，键值 key 就是 实值 value，并且因为不允许冗余，所以只有一个 键值，count 统计 键值 数量就相当于 查找 。
#include <iostream>#include <vector>#include <set>using namespace std;int main(){vector<int> arr = { 7,3,6,9,3,1,6,2 };set<int> s1(arr.begin(), arr.end());for (int i = 0; i < 10; i++){if (s1.count(i))cout << i << " 在 set 中" << endl;elsecout << i << " 不在 set 中" << endl;}return 0;}
2.3 set 的基本用法
示例：创建和插入数据
以下是一个创建 set 的例子，并展示如何插入和删除数据。
#include <iostream>#include <set>using namespace std;int main() { set<int> s; // 创建一个空的 set // 插入元素 s.insert(10); s.insert(20); s.insert(10); // 重复插入 10，不会被插入 // 输出 set 中的元素 for (int e : s) { cout << e << " "; } cout << endl; return 0;} 
示例：查找元素
find 可以用于查找元素是否存在于 set 中。如果存在，返回该元素的迭代器；否则，返回 end 迭代器。
int main() { set<int> s = {1, 2, 3, 4, 5}; // 查找元素 3 auto it = s.find(3); if (it != s.end()) { cout << "Element 3 found." << endl; } else { cout << "Element 3 not found." << endl; } return 0;}set的特点：
2.4 multiset 容器
multiset 是 set 的一个变体，multiset 和 set 的操作没什么区别，一模一样，允许存储重复的元素。multiset 的操作与 set 基本相同，只是它允许插入重复元素。示例如下：
#include <iostream>#include <set>using namespace std;int main() { multiset<int> ms; ms.insert(5); ms.insert(5); ms.insert(3); for (int e : ms) { cout << e << " "; } cout << endl; return 0;} 
值得一提的是，当在 multiset 中查找冗余的数据时，返回的是 中序遍历中，第一次出现的元素。
#include <iostream>#include <vector>#include <set>using namespace std;int main(){vector<int> arr = { 3,5,3,4,5,9,2,3 };multiset<int> ms1(arr.begin(), arr.end());auto it = ms1.begin();while (it != ms1.end()){cout << *it << " | " << &*(it) << endl;++it;}cout << "================" << endl;cout << "ms1.find(3): " << &*(ms1.find(3)) << endl;return 0;} 
所以，multiset 才是真正的排序，set 则是去重 + 排序
统计 键值 数 count 在 multiset 中可以发挥真正效果。
#include <iostream>#include <vector>#include <set>using namespace std;int main(){vector<int> arr = { 3,5,3,4,5,9,2,3 };multiset<int> ms1(arr.begin(), arr.end());for (int i = 0; i < 10; i++)cout << i << "在 multiset 中的数量: " << ms1.count(i) << endl;return 0;}
三、map 容器详解
map 是 C++ STL 中的一种键值对关联式容器，每个元素包含一个键和值。map 中的键是唯一的，不能重复；每个键都映射到一个对应的值。map 在很多场景中被用作哈希表来存储键值对数据。
3.1 map 的特点
唯一键：map 中的每个键是唯一的。键值对存储：map 存储的是键值对，即 key-value。按键自动排序：map 会自动对键进行排序，默认按升序排列。可以通过键访问值：可以通过 operator[] 运算符直接访问键对应的值。 3.2 map 的常用操作
| 操作 | 作用 |
|---|---|
insert | 插入一个键值对 |
erase | 删除指定键的键值对 |
find | 查找指定键，返回其迭代器 |
count | 统计键的数量（map 中最多为 1） |
operator[] | 根据键访问值，如果键不存在则自动插入新键 |
empty | 判断 map 是否为空 |
size | 返回 map 中键值对的个数 |
clear | 清空 map 中的所有键值对 |
map 的定义和常用操作
map 位于 <map> 头文件中，定义方式如下：
#include <map>#include <iostream>using namespace std;int main() { map<string, int> age; // 创建一个 map，其中键是 string，值是 int // 插入键值对 age["Alice"] = 25; age["Bob"] = 30; // 查找键值对 if (age.find("Alice") != age.end()) { cout << "Alice's age: " << age["Alice"] << endl; } // 遍历 map for (const auto& entry : age) { cout << entry.first << ": " << entry.second << endl; } return 0;}map 的基本用法示例
1. 插入和访问键值对
#include <map>#include <iostream>using namespace std;int main() { map<string, int> scores; // 插入键值对 scores.insert(make_pair("Alice", 90)); scores.insert(make_pair("Bob", 85)); // 也可以通过 operator[] 插入和访问 scores["Charlie"] = 95; // 访问值 cout << "Alice's score: " << scores["Alice"] << endl; return 0;}2. 查找和删除键值对
#include <map>#include <iostream>using namespace std;int main() { map<string, int> scores = {{"Alice", 90}, {"Bob", 85}, {"Charlie", 95}}; // 查找键 "Bob" auto it = scores.find("Bob"); if (it != scores.end()) { cout << "Found Bob's score: " << it->second << endl; } // 删除键 "Alice" scores.erase("Alice"); // 输出所有键值对 for (const auto& entry : scores) { cout << entry.first << ": " << entry.second << endl; } return 0;}3.3 map 的特点与性能
自动排序：map 中的元素按键自动排序，因此每次插入键值对后，map 都会根据键进行重新排序。唯一性：map 中不允许重复键，如果试图插入相同键的元素，将会被忽略。高效查找：map 的查找、插入和删除的时间复杂度为 O(log n)，适合需要快速查找的场景。默认初始化：使用 operator[] 时，如果键不存在，则会创建一个默认值的键值对。 注意事项
map[key] 如果访问的键不存在，则会自动创建该键，并给其赋一个默认值（如 int 的默认值是 0）。使用 find 可以避免这种不必要的插入。map 中的数据是按键有序的，因此 map 不支持像 unordered_map 那样的 O(1) 查找。 map 的应用场景
map 来统计字符串中每个字符的出现频率。缓存机制：可以通过 map 来实现简单的缓存机制，用于存储经常使用的键值对。字典实现：map 是存储字典（如配置文件、键值对映射等）的一种常用数据结构。 总计：
总结
map 是一个非常强大的数据结构，可以存储唯一的键值对并按键排序。它在很多场景中都非常实用，尤其适合用于需要快速查找和唯一键的情况。在使用时需要注意 map[key] 会默认初始化键值对的问题，可以通过 find 函数来避免不必要的插入。
四、前K个高频单词
692. 前K个高频单词 - 力扣（LeetCode）
题目分析：题目很短，就是在一个字符串数组中，找出前 k 个出现频率最高的单词
注意： 如果出现次数相同，则按字典序排序。（相同次数小写排前面）。
解法：map + 快排
利用 map 建立 <string, int> 的映射关系，在按照字典序排序的同时统计出每个单词的出现频率，再通过快排依照数量进行二次排序，选择前 k 个高频单词即可
因为基础版快排 不稳定，可能会导致频率相同的单词顺序出问题，即违背题目要求：如果出现频率相同，则按字典序排序
所以这里需要使用 稳定版快排 stable_sort，如果频率相同，保持原有顺序
//map + stable_sortclass Solution {public: struct Compare { bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const { return kv1.second > kv2.second; } }; 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()); //按照出现频率进行二次排序 stable_sort(vTable.begin(), vTable.end(), Compare()); //取出前 k 个高频单词 vector<string> vs; for(int i = 0; i < k; i++) vs.push_back(vTable[i].first); return vs; }};LCR 154. 复杂链表的复制 - 力扣（LeetCode）
五、补充：交集与差集
交集，指两个数组中相同的元素所构成的集合
求交集的步骤如下：
先将两个数组 排序 + 去重遍历两个数组如果不相等，小的++相等就是交集，记录下来其中一方走完，所有交集就查找完了 排序 + 去重，这就不就是 set 吗？
349. 两个数组的交集 - 力扣（LeetCode）
class Solution {public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> set1(nums1.begin(),nums1.end()); set<int> set2(nums2.begin(),nums2.end()); vector<int> num1(set1.begin(),set1.end()); vector<int> num2(set2.begin(),set2.end()); int i=0,j=0; vector<int> v; while(i<num1.size()&&j<num2.size()) { if(num1[i]==num2[j]) { v.push_back(num1[i]); } else if(num1[i]<num2[j]) { i++; } else{ j++; } } return v; }};总结：
| 容器 | 特点 | 适用场景 |
|---|---|---|
set | 唯一元素，有序存储 | 去重，查找唯一元素 |
multiset | 允许重复元素，有序存储 | 频率统计，处理重复数据 |
map | 键值对存储，唯一键，有序 | 频率统计，字典查询 |
multimap | 键值对存储，允许重复键，有序 | 频率统计，管理多值的数据 |