【C++题解】关联容器

发布于：2025-09-05 ⋅ 阅读:(20) ⋅ 点赞:(0)

关于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;
                    }else
                        freq[pri[i]]++;
                    a/=pri[i];
                    flag = true;
                    break;
                }
            }
            if(!flag){
                if(freq.find(a)==freq.end())
                    freq[a]=1;
                else
                    freq[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)），这在绝大多数算法竞赛中是可以接受的。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布