C++ 竞赛训练营第四课：STL 核心容器之 map/unordered_map（哈希表的竞赛用法）

一、课程导航 🚀

1. 🎯 竞赛视角：为什么哈希表是 “快速查找” 的终极方案？
2. 📚 核心特性：map（红黑树）与 unordered_map（哈希表）的本质区别
3. 🔧 竞赛高频操作：构造、增删查改与效率对比
4. ⚡ 竞赛进阶用法：键值对映射、频率统计、自定义排序
5. 📝 真题实战：两数之和、字母异位词、最长连续序列
6. ❌ 竞赛避坑指南：哈希冲突、有序性陷阱、效率选型错误
7. 🔖 下节预告：algorithm 头文件神器 —— 竞赛常用算法函数

二、核心知识点与竞赛实战

🎯 1. 竞赛视角：哈希表的 “效率核心”

在竞赛中，“快速查找” 是高频需求（如判断元素是否存在、统计出现次数、建立映射关系），而 map 与 unordered_map 正是为解决这类问题而生，核心价值在于：

• 高效查找：unordered_map 查找 / 插入 / 删除均为 O (1) 平均时间，远超数组遍历的 O (n)；map 为 O (log n)，但支持有序遍历；

• 键值对存储：天然适配 “映射关系” 场景（如字符串→整数、id→属性、值→出现次数），无需手动维护数组下标；

• 场景全覆盖：无序场景用 unordered_map 追求速度，有序场景用 map 满足排序需求，适配竞赛各类 “查找 + 统计” 题型。

竞赛场景适配：

• 快速查找：两数之和、判断元素是否存在、查询某个键对应的值；

• 频率统计：字母异位词、前 k 个高频元素、统计数组中元素出现次数；

• 映射转换：字符串编码（如罗马数字转整数）、id 与属性绑定（如学生 id→成绩）；

• 有序需求：有序映射（如按键排序的字典）、区间查询（如查找键大于 x 的最小元素）。

📚 2. 核心特性：map 与 unordered_map 的本质区别

2.1 底层实现与核心规则

容器	底层结构	核心特性	时间复杂度（查找 / 插入 / 删除）	适用场景
map	红黑树（平衡二叉搜索树）	键有序（默认升序）、无哈希冲突	O(log n)	有序映射、区间查询、需要排序的场景
unordered_map	哈希表（哈希桶）	键无序、可能出现哈希冲突	O (1)（平均）、O (n)（最坏）	快速查找、频率统计、无序映射场景

2.2 核心区别可视化

• unordered_map：像 “字典查字”—— 通过哈希函数直接定位键的位置，速度快但无顺序；

• map：像 “排序好的电话簿”—— 按键有序排列，可按顺序遍历，但查找速度略慢于哈希表。

2.3 竞赛选型原则（必记）

• 优先用 unordered_map：无有序需求时（如统计频率、两数之和），追求 O (1) 高效查找；

• 必须用 map：需要键有序（如按出现次数排序）、区间查询（如查找大于 x 的最小键）时；

• 避免误区：不要因 “无序” 而否定 unordered_map，竞赛中 80%+ 的哈希表场景均无需有序。

🔧 3. 竞赛高频操作：构造与核心接口

两类容器接口高度一致，竞赛中仅需掌握 “核心 5 接口 + 2 构造”，简洁高效：

3.1 核心构造方式（竞赛直接套用）

// 1. 空容器构造（最常用）

map<int,string> mp1; // 有序map，键为int，值为string

unordered_map<string,int> mp2; // 无序unordered_map，键为string，值为int

// 2. 初始化列表构造（C++11+）

map<int, int> mp3 = {{1,2}, {3,4}, {2,5}}; // 构造后自动按键升序：1→2, 2→5, 3→4

unordered_map mp4 = {{'a',3}, {'b',1}, {'c',2}}; // 无序存储

// 3. 迭代器范围构造（从其他容器拷贝）

vector<pair vec = {{1,"a"}, {2,"b"}};

map<int,string> mp5(vec.begin(), vec.end());

3.2 核心接口（竞赛必备）

unordered_map<string,int> mp;

// 1. 插入键值对（三种方式，竞赛常用前两种）

mp["apple"] = 5; // 直接赋值，不存在则插入，存在则更新值

mp.insert(make_pair("banana", 3)); // 插入pair，若键已存在则不更新

mp.emplace("orange", 4); // 直接构造键值对，效率高于insert

// 2. 查找键（核心操作，必掌握）

if (mp.count("apple")) { // count返回1（存在）或0（不存在），O(1)/O(log n)

cout << mp["apple"] << endl; // 访问值，存在则返回值，不存在则插入默认值（int为0）

}

auto it = mp.find("banana"); // find返回迭代器，存在则指向键值对，不存在则指向end()

if (it != mp.end()) {

cout << it->first << ":" << it->second < // 迭代器访问键值对（first=键，second=值）

}

// 3. 删除键值对

mp.erase("apple"); // 按键删除，O(1)/O(log n)

mp.erase(it); // 按迭代器删除，O(1)/O(log n)

mp.clear(); // 清空所有元素，O(n)

// 4. 其他常用接口

int size = mp.size(); // 获取元素个数，O(1)

bool empty = mp.empty(); // 判断是否为空，O(1)

3.3 竞赛关键提醒（效率优先）

• unordered_map 的 [] 操作：访问不存在的键会自动插入（值为默认构造，如 int=0），若仅需判断是否存在，优先用 count() 或 find()（避免误插入）；

• map 的有序性：默认按键升序排列，可通过反向迭代器 rbegin()/rend() 实现降序遍历；

• 迭代器遍历：适合需要遍历所有键值对的场景（如频率统计后遍历结果），map 遍历是有序的，unordered_map 是无序的。

⚡ 4. 竞赛进阶用法：高频场景实战模板

4.1 场景 1：频率统计（竞赛最高频）

模板功能：统计数组 / 字符串中元素出现的次数，适配字母异位词、高频元素等题。

// 统计字符串中字符频率
unordered_map<char, int> Freq(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++; // 不存在的键会自动初始化值为0，再+1
    }
    return freq;
}

// 统计数组中元素频率
unordered_map<int, int> countArrayFreq(vector<int> nums) {
    unordered_map<int, int> freq;
    for (int x : nums) freq[x]++;
    return freq;
}

4.2 场景 2：键值映射（字符串 / 数字转换）

模板功能：建立两个集合的映射关系（如罗马数字转整数、字符串编码）。

 

// 罗马数字转整数（LeetCode 13）
int romanToInt(string s) {
    // 1. 修正：正确拼写+指定键值类型
    unordered_map<char, int> romanMap = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},  // 修正：'L'的值写法
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

    int res = 0;
    // 2. 修正：for循环条件
    for (int i = 0; i < s.size(); ++i) {
        // 3. 修正：逻辑判断（当前值 < 下一个值 → 减去当前值）
        if (i < s.size() - 1 && romanMap[s[i]] < romanMap[s[i+1]]) {
            res -= romanMap[s[i]];
        } else {
            res += romanMap[s[i]];
        }
    }
    return res;
}

4.3 场景 3：有序映射（map 专属）

模板功能：需要按键排序的映射场景（如按分数排序、区间查询）。

// 按键降序的map（自定义排序）

map<int, string, greater>> scoreMap; // 第三个参数greater键降序

scoreMap[95] = "Alice";

scoreMap[88] = "Bob";

scoreMap[98] = "Charlie";

// 遍历结果：98→Charlie, 95→Alice, 88→Bob（自动降序）

for (auto& [score, name] : scoreMap) {

    cout << score << ":" << name <

}

// 区间查询：查找键大于等于90的所有元素

auto it = scoreMap.lower_bound(90); // 返回第一个键>=90的迭代器

while (it != scoreMap.end()) {

    cout <->first << ":" <->second < it++;

}

📝 5. 真题实战：竞赛高频题模板（直接套用）

例题 1：两数之和（LeetCode 1，入门题）

题目描述：给定整数数组和目标值，返回两个数的下标，使它们的和等于目标值（假设仅一个解）。

核心思路：用 unordered_map 存储 “值→下标”，遍历数组时查找 target - nums[i] 是否存在，O (n) 时间复杂度。

竞赛代码（模板）：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 两数之和（LeetCode 1）
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> valToIdx; // 键：数值，值：下标（修正拼写：unordered_map）
    for (int i = 0; i < nums.size(); ++i) { // 修正循环条件：i < nums.size()
        int complement = target - nums[i];
        // 查找补数是否存在（且不是当前元素自身）
        if (valToIdx.count(complement)) {
            return {valToIdx[complement], i};
        }
        valToIdx[nums[i]] = i; // 插入当前值和下标
    }
    return {}; // 题目保证有解，实际不会走到这
}

// 测试函数
int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    // 输出结果：0 1（对应nums[0]=2和nums[1]=7，和为9）
    cout << "下标为：" << result[0] << " 和 " << result[1] << endl;
    return 0;
}

例题 2：字母异位词分组（LeetCode 49，中等题）

题目描述：将字符串数组分组，字母异位词（字母相同但顺序不同）分到同一组。

核心思路：用 map 存储 “排序后的字符串→异位词列表”，排序后的字符串作为 key（如 "eat" 和 "tea" 排序后均为 "aet"），O (n k log k) 时间（k 为字符串长度）。

竞赛代码（模板）：

 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm> // 用于sort排序
using namespace std;

// 字母异位词分组（LeetCode 49）
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    // 键：排序后的字符串；值：对应的异位词列表
    map<string, vector<string>> sortedStrToAnagrams;

    for (string s : strs) {
        string key = s;
        sort(key.begin(), key.end()); // 将字符串排序作为key（如"eat"→"aet"）
        sortedStrToAnagrams[key].push_back(s); // 按key分组
    }

    // 将map中的值（异位词列表）转存到结果vector
    vector<vector<string>> result;
    for (auto& pair : sortedStrToAnagrams) {
        result.push_back(pair.second);
    }
    return result;
}

// 测试函数
int main() {
    vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> groups = groupAnagrams(strs);

    // 输出分组结果
    cout << "字母异位词分组结果：" << endl;
    for (auto& group : groups) {
        for (string s : group) {
            cout << s << " ";
        }
        cout << endl;
    }
    return 0;
}

例题 3：最长连续序列（LeetCode 128，困难题）

题目描述：给定未排序的整数数组，找出最长连续序列的长度（要求 O (n) 时间复杂度）。

核心思路：用 unordered_set（哈希表的无值版本）存储所有元素，遍历每个元素时，若为序列起点（即x-1不存在），则向后查找连续元素，记录最大长度。

竞赛代码（模板）：

 

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 最长连续序列（LeetCode 128）
int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0; // 空数组直接返回0

    // 用unordered_set存储所有元素（去重+O(1)查询）
    unordered_set<int> numSet(nums.begin(), nums.end());
    int maxLen = 0;

    for (int num : numSet) {
        // 只有当num是序列起点（num-1不存在）时，才向后查找连续序列
        if (numSet.find(num - 1) == numSet.end()) {
            int currentNum = num;
            int currentLen = 1;

            // 向后找连续元素
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum++;
                currentLen++;
            }

            // 更新最大长度
            maxLen = max(maxLen, currentLen);
        }
    }
    return maxLen;
}

// 测试函数
int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    int result = longestConsecutive(nums);
    cout << "最长连续序列的长度：" << result << endl; // 输出4（对应序列1,2,3,4）

    // 测试空数组
    vector<int> emptyNums;
    cout << "空数组的最长连续序列长度：" << longestConsecutive(emptyNums) << endl; // 输出0
    return 0;
}

❌ 6. 竞赛避坑指南：常见错误与效率陷阱

6.1 常见错误（最易丢分）

• 错误 1：用 unordered_map 要求键有序 ——unordered_map 是无序的，需有序则改用 map；

• 错误 2：访问 unordered_map 不存在的键 —— 如 mp["nonexist"] 会自动插入该键，值为默认值（如 int=0），导致统计错误，需先通过 count() 或 find() 判断；

• 错误 3：map 用 [] 插入键值对后，想按插入顺序遍历 ——map 按键排序，与插入顺序无关，需按插入顺序则用 unordered_map 或 vector 辅助；

• 错误 4：哈希表存储自定义结构体作为键 —— 未重载 hash 函数（unordered_map）或 （map`），导致编译报错，竞赛中优先用基础类型（int、string）作为键。

6.2 效率陷阱（避免超时）

• 错误：大规模数据（n>1e5）用 unordered_map 且频繁触发哈希冲突 —— 可通过自定义哈希函数优化，或直接改用 map（稳定 O (log n)）；

• 正确：频率统计优先用 unordered_map（O (1)），而非 map（O (log n)），尤其是 n 较大时；

• 注意：unordered_map 的迭代器在插入 / 删除后可能失效，而 map 的迭代器仅在删除当前迭代器指向的元素时失效，遍历中删除需谨慎。

🔖 7. 下节预告：algorithm 头文件神器 —— 竞赛常用算法函数

核心内容前瞻（直击竞赛痛点，节省编码时间）