【C++题解】关联容器

关于set，map以及变种
|关联容器| set&multiset | map&multimap |无序关联容器| Unordered set&multiset | Unordered map&multimap |
建议先了解之后再配合练习
这次练习CCF真题比较多，也比较基础，预计耗时不用这么久。

今天的重点是 C++ STL 中两个非常强大的关联式容器：map和 set。它们在处理需要高效统计、去重和查找的场景时极为有用，尤其在CCF认证考试的题目中频繁出现。

练习计划概览

• 总时长: 约 4 小时

• 核心目标:

  1. 掌握 std::map 的基本用法，用于建立键-值（key-value）映射，实现快速词频统计和数据聚合。

  2. 掌握 std::set 的基本用法，利用其自动去重和排序的特性，进行数据去重和有序集合操作。

  3. 理解 map 和 set 底层基于红黑树实现所带来的 O(log n) 时间复杂度特性。

  4. 通过练习CCF真题，熟悉这类考点的设问方式和解题套路。

---

第一部分：map 的应用——统计与映射 (约 2 小时)

map 提供的是键（Key）到值（Value）的映射关系。它非常适合需要根据某个标识（如单词、ID）来存储和查询对应信息（如出现次数、属性）的场景。

题目编号	题目名称	核心知识点	练习目标
CCF202403-1	词频统计	map, set	这是最经典的词频统计题。使用 map<int, int> 统计单词总频次，并可结合 set 对每篇文章的单词去重，以统计单词出现的文章数 1。是 map 和 set 结合使用的绝佳练习。（来自您提供的文件）
CCF202305-1	重复局面	map, vector<string>	统计每个 8x8 棋盘局面出现的次数 2。本题是练习将 vector<string> 等复杂数据结构作为 map 的键，来进行频次统计的绝佳题目。（来自您提供的文件）
CCF202006-2	稀疏向量	map<int, int>	这道题是 map 应用的绝佳范例。由于向量维度很高但非零值很少（稀疏） 3，使用数组会浪费巨大空间。而用 map 只存储非零值的下标和值，可以高效地解决空间和计算问题 4。 （CCF真题）
CCF202312-2	因子化简	map	在对整数进行质因数分解时，使用 map<long long, int> 来存储每个质因数及其出现的次数（指数）5，是 map 在数论问题中进行频次统计的典型应用。（来自您提供的文件）

//33-1 (第33次第一题)
//构建两个map来映射，也可以吧两个合成一个map<int,vector<int>>来操作，但我觉得没必要#include <iostream>
#include <map>
#include <vector>using namespace std;int main(){int m,n;cin >> n >> m;map<int,int> freq;map<int,int> arti;for(int i=1;i<=m;i++){freq.insert(make_pair(i,0));arti.insert(make_pair(i,0));}while(n--){int a;cin >> a;vector<bool> vis(m,false);for(int i=0;i<a;i++){int tmp;cin >> tmp;freq[tmp]++;if(!vis[tmp]){arti[tmp]++;vis[tmp] = true;}}}for(int i=1;i<=m;i++){cout << arti[i] << " " << freq[i] <<"\n";}return 0;
}``````cpp
//30-1 直接无脑把各种情况往映射里面插入就行。#include <iostream>
#include <vector>
#include <map>  
#include <string>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;map<vector<string>,int> freq;for(int i=0;i<n;i++){vector<string> situ(8);for(int j=0;j<8;j++){cin >> situ[j];}if(freq.find(situ)==freq.end()){freq[situ]=1;}else{freq[situ]++;}cout << freq[situ] <<"\n";}return 0;
}

//19-2 写两个map，数据传入后直接乘#include <iostream>
#include <vector>
#include <map>  
#include <string>using namespace std;int main(){int n,a,b;cin >> n >> a >> b;map<int,int> vc1;map<int,int> vc2;for(int i=0;i<a;i++){int tmp;cin >> tmp;cin >> vc1[tmp];}for(int i=0;i<b;i++){int tmp;cin >> tmp;cin >> vc2[tmp];}long long sum=0;// 遍历第一个向量中的所有索引for(auto& p : vc1){int index = p.first;if(vc2.find(index) != vc2.end()){sum += (long long)p.second * vc2[index];}}cout << sum << "\n";return 0;
}

//素数我直接打表的，注意一个可能本身是大数的情况，所以加了一步flag#include <iostream>
#include <vector>
#include <map>  
#include <string>
#include <sstream>
#include <math.h>std::vector<int> pri={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,701,709,719,727,733,739,743,751,757,761,769,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
using namespace std;int main(){int n;cin >> n;while(n--){long long a;int k;map<int,int> freq;cin >> a >> k;while(a>1){bool flag = false;for(int i=0;i<pri.size()&&a>=pri[i];i++){if(a%pri[i]==0){if(freq.find(pri[i])==freq.end()){freq[pri[i]]=1;}elsefreq[pri[i]]++;a/=pri[i];flag = true;break;}}if(!flag){if(freq.find(a)==freq.end())freq[a]=1;elsefreq[a]++;break;}}long long b = 1;for(auto& p : freq){if(p.second>=k){b *= pow(p.first,p.second) ;}}cout << b << "\n";}return 0;
}

练习建议:

• CCF202403-1 (词频统计) 是必做题，它完美地体现了CCF对 map 基本能力的考察。请务必掌握 map[key]++ 这种简洁的计数方式。

• 做 CCF202305-1 (重复局面) 时，关键在于理解C++中 map 的键只要是可比较的，就可以是任意复杂类型。这为你解决更多样的问题打开了思路。

• 做 CCF202006-2 (稀疏向量) 时，需要遍历其中一个 map，然后用 find 或 count 方法在另一个 map 中查找是否存在相同的 key（维度下标），从而计算内积。

---

第二部分：set 的应用——去重与查找 (约 1.5 小时)

set 容器存储的元素都是唯一的，并且会自动排序。它非常适合需要去除重复元素，或者需要快速判断某个元素是否在集合中的场景。

题目编号	题目名称	核心知识点	练习目标
P1059	[NOIP2006 普及组] 明明的随机数	set	最经典的去重入门题。将所有数字插入 set 容器，它会自动完成去重和排序，是理解 set 核心特性的不二之选。
CCF202403-2	相似度计算	set, string	题目核心是“去掉各自重复的单词”并计算交集与并集 6。这是 set 数据结构的教科书式应用，用于高效地进行字符串去重和集合运算。（来自您提供的文件）
P3370	【模板】字符串哈希	set<string>	统计一堆字符串中有多少个不同的字符串。可以直接使用 std::set<string> 来自动去重并计数，是 set 用于字符串去重的模板题。
P1540	[NOIP2010 提高组] 机器翻译	set/map, queue	模拟内存缓存。需要一个数据结构能快速判断某单词是否存在于内存中，set 的 find 或 count 方法非常适合这个场景。

P1059 -这个题目我在排序和二分那里用set做了一遍

//33-2 两个点：大小写转换记得用引用；这里用无序容器更好，因为基于哈希的无序容器查找耗时O(1)#include <iostream>
#include <set>
#include <string>using namespace std;int main(){int a,b;cin >> a >> b;set<string> s1;set<string> s2;for(int i=0;i<a;i++){string tmp;cin >> tmp;for(char &c : tmp){c = tolower(c);}s1.insert(tmp);}for(int i=0;i<b;i++){string tmp;cin >> tmp;for(char &c : tmp){c = tolower(c);}s2.insert(tmp);}set<string> s3;for(auto& p : s1){if(s2.find(p)!=s2.end()){s3.insert(p);}}cout << s3.size() << endl << s1.size()+s2.size()-s3.size() << endl;return 0;
}

//P3370 - 题目想要你自己搞哈希，既然有现成容器直接用就行#include <iostream>
#include <set>
#include <string>using namespace std;int main(){int n;cin >> n;set<string> s;while(n--){string tmp;cin >> tmp;s.insert(tmp);}cout << s.size() << endl;return 0;
}

//P1540 - 我这里了个queue来进行内存里面数据的处理（先进先出），因为删除set里面东西的时候只能找key，愿意的话可以用u_map然后把key顺序一下，每次删最前面就行。（我觉不如queue实在）#include <iostream>
#include <unordered_set>
#include <string>
#include <deque>using namespace std;int main(){int m,n;int rst=0;cin >> m >> n;unordered_set<int> s;deque<int> q;while(n--){int i;cin >> i;if(s.find(i)==s.end()){s.insert(i);q.push_back(i);rst++;if(q.size()>m){s.erase(q.front());q.pop_front();}}}cout << rst << endl;return 0;
}

练习建议:

• P1059 和 CCF202403-2 是必做题，它们分别代表了对数字和字符串的去重，覆盖了 set 最核心的应用。

• 在做 CCF202403-2 (相似度计算) 时，在将两个单词集合（set）构建好之后，可以通过遍历较小的集合，并使用 find 方法在较大的集合中查找，来高效地计算交集的大小。

• P1540 是一个很好的综合题，它会让你思考 set 只负责去重和查找，但不记录顺序，因此需要结合 queue等其他数据结构来记录元素的进入次序。

---

目标达成自查 (约 0.5 小时)

完成以上练习后，进行复盘和总结：

1. 关于 map vs 数组:

   • 在什么情况下必须使用 map 而不能用数组？（当键的类型不是整数，或者键是整数但范围非常大且分布稀疏时）

   • map 的 m[key]++ 操作包含了哪些步骤？（查找 key，如果不存在则插入默认值0，然后自增）

2. 关于 set vs vector+sort+unique:

   • 使用 set 去重和使用 vector 排序去重各有什么优缺点？（set 插入时自动维护，代码简单；vector 操作对于静态数据一次性处理速度可能更快）

   • 如何用 set 快速判断一个元素是否存在？（使用 s.count(element) 或 s.find(element) != s.end()，时间复杂度为 O(log n)）

3. 复杂度意识:

   • map 和 set 中一次插入、删除、查找操作的平均时间复杂度是多少？（O(log n)）

   • 对于 10^5 级别的数据量，使用 map 或 set 的总时间复杂度大约是多少？（O(n log n)），这在绝大多数算法竞赛中是可以接受的。