当然！以下是《【C++】map 和 set 的使用全解析》教程内容，适用于初学者和中高级开发者全面理解 STL 中 map 和 set 的工作原理、接口、常见用法与性能分析。

🧭【C++】Map 和 Set 的使用全解析：底层机制与实战指南

📚 目录

  1. Map 和 Set 是什么？
  2. 背后的数据结构（红黑树 vs 哈希表）
  3. map 和 set 的常见操作
  4. multimap / multiset 的区别与应用
  5. unordered_map / unordered_set 概览
  6. 自定义排序与比较函数
  7. 遍历与查找技巧
  8. 实战案例：词频统计与唯一集合管理
  9. 性能分析与使用建议
  10. 总结与踩坑点汇总

1️⃣ Map 和 Set 是什么？

容器类型是否键值对是否允许重复排序规则
setstd::set<T>❌❌升序（默认）
mapstd::map<K, V>✅❌按 key 升序
multisetstd::multiset<T>❌✅升序（默认）
multimapstd::multimap<K, V>✅✅按 key 升序

2️⃣ 底层结构：红黑树（RB-Tree）

map 和 set 默认基于 红黑树 实现：

  • 插入、删除、查找：时间复杂度 O(log n)
  • 自动排序
  • 有序遍历（支持区间操作）

🔁 unordered 系列使用哈希表，查找更快但无序。

3️⃣ 基本操作语法

✅ std::set

std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.erase(1);
if (s.count(2)) { std::cout << "Found 2\n"; }

✅ std::map

std::map<std::string, int> mp;
mp["apple"] = 3;
mp["banana"] = 5;
mp.erase("apple");
if (mp.count("banana")) { std::cout << mp["banana"] << "\n"; }

4️⃣ multimap 和 multiset 的特点

std::multiset<int> ms;
ms.insert(1);
ms.insert(1);  // 允许重复

std::multimap<std::string, int> mm;
mm.insert({"Tom", 100});
mm.insert({"Tom", 80});  // 同键多值

💡 适合统计频率、做优先队列、排行榜等。

5️⃣ unordered_map / unordered_set

std::unordered_set<int> uset;
std::unordered_map<std::string, int> umap;
  • 基于哈希表，平均复杂度 O(1)
  • 不保证元素顺序
  • 更快，但不能用 lower_bound / upper_bound

6️⃣ 自定义排序规则

set 自定义排序（降序）：

std::set<int, std::greater<int>> s;  // 降序排列

map 自定义 key 类型排序：

struct Comp {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const {
        return a.second > b.second; // 根据值排序
    }
};
std::map<std::pair<int, int>, int, Comp> custom_map;

7️⃣ 遍历与查找技巧

✅ 遍历 set：

for (int x : s) std::cout << x << "\n";

✅ 遍历 map：

for (const auto& [key, val] : mp) {
    std::cout << key << ": " << val << "\n";
}

✅ 查找与区间：

auto it = s.lower_bound(3); // >= 3
auto it2 = s.upper_bound(3); // > 3

8️⃣ 实战案例

📌 词频统计（map）

std::map<std::string, int> freq;
std::string word;
while (std::cin >> word) freq[word]++;

📌 唯一集合（set）

std::set<std::string> names;
names.insert("Tom");
names.insert("Tom"); // 不会插入重复项

9️⃣ 性能分析与建议

操作类型map/set（红黑树）unordered（哈希）
插入/删除/查找O(log n)O(1) ~ O(n)
是否有序✅❌
是否可用 lower_bound✅❌

🚨 注意：

  • unordered_map 不能用于自定义类型（除非提供哈希函数）
  • 插入大量元素时，使用 emplace 性能优于 insert

🔟 常见坑点与总结

❌ map[key] 会默认插入 key：

std::map<std::string, int> m;
std::cout << m["hello"]; // 插入了 "hello"，值为 0

✔ 建议使用 count() 判断再访问。

💡 使用建议：

  • 有序查找、区间操作用 map/set
  • 高频增删、无序查找用 unordered_map/set
  • 可重复数据用 multi 系列

📚 推荐资料