1.set是什么
set的底层是红黑树（一种平衡搜索二叉树），树形结构，而且只有key没有value,也就是说set只能做key在不在这种场景，比如说在机场对乘客是不是黑名单中的一员进行查找的时候就可以用到set,进行查找对应的身份证号是否存在，不需要知道这个身份证号对应的姓名是什么，也就是说不需要value，这也是set和map的区别；
2.set和红黑树的关系
set是容器，而红黑树是set的底层逻辑，是一种数据结构，set对红黑树的底层逻辑做了封装，提供了我们使用的上层接口
3.set的特点
① 红黑树天生自动维护顺序，所以 set 里的元素永远是排好序的。
② set可以进行去重，也就是说set中没有重复的元素，这是因为set这个容器在进行插入数据的时候会进行判断，将重复的元素进行去除，std::set的设计目标是集合set，数学上集合的定义就是"不重复元素的无序聚集"。这也是set和list的区别之一
4.unordered_set是什么
unordered的意思是无序的，所以unordered_set的意思就是无序集合，底层使用的是哈希表，为什么unordered底层使用的是hash表而不是红黑树呢？因为业务需求不同：set需要"有序"，红黑树天然有序；unordered_set只需要"快速"，哈希表天然最快。这是根据"要什么"选"用什么"的经典案例。
5.hash是怎么将元素放到对应的桶中的
| 步骤 | 操作 | 具体做了什么？ |
|---|---|---|
| 第 1 步 | 计算哈希值 | 调用std::hash<Key>()(x)，得到一个size_t类型的整数（比如123456789） |
| 第 2 步 | 计算桶号（索引） | 用哈希值对桶数量取模：bucket_index = hash_value % bucket_count()，得到要去的桶的编号（比如5号桶） |
| 第 3 步 | 查重（遍历桶内链表） | 去对应的桶，遍历桶里的链表，用operator==逐一比较所有元素。如果有相等的，插入失败，直接返回 |
| 第 4 步 | 检查是否需要扩容 | 如果没找到重复，检查当前元素个数是否超过bucket_count * max_load_factor（默认 1.0）。如果超过了，触发 Rehash（扩容），重新分配更大的桶数组，所有旧元素重新计算桶号并搬过去 |
| 第 5 步 | 插入元素 | 把新元素挂在对应桶的链表头部（或尾部），元素个数size++ |
void unordered_set::insert(int x) { // 第 1 步：算哈希 size_t hash_val = hash_function(x); // 第 2 步：算桶号 size_t bucket_index = hash_val % bucket_count; // 第 3 步：查重 Node* cur = buckets[bucket_index]; while (cur != nullptr) { if (cur->value == x) { // 用 operator== 比较 return; // 重复了，拒绝插入 } cur = cur->next; } // 第 4 步：检查负载因子 if (size > bucket_count * max_load_factor) { rehash(bucket_count * 2); // 扩容翻倍，全部重新哈希 bucket_index = hash_val % bucket_count; // 重新计算桶号 } // 第 5 步：插入 Node* new_node = new Node(x); new_node->next = buckets[bucket_index]; buckets[bucket_index] = new_node; size++; }① rehash的什么时候进行扩容？
rehash的时间复杂度是O(n),而因为负载因子是1，意思就是当元素个数和桶的数量相同的时候需要进行扩容；
② 为什么要重新计算hash值？
因为并不是所有数据都是整数，能让你直接取模！哈希值存在的核心目的，就是把"乱七八糟的任何东西"统一转化成"整数"，这样计算机才能处理。
场景 1：如果原始值是字符串
std::unordered_set<std::string> mySet; mySet.insert("hello"); mySet.insert("world");问题来了：你没法对字符串取模！
"hello" % 13; // ❌ 编译报错！C++ 不支持对字符串取模你必须先把字符串转成一个整数，然后才能取模。这个"转成整数的过程"，就是哈希函数做的事。
场景 2：如果原始值是自定义对象
struct Person { std::string name; int age; }; std::unordered_set<Person> mySet; // 编译报错！没有哈希函数问题：Person不是整数，不能直接取模。你必须告诉 C++ 怎么把Person转成整数，这就是自定义哈希函数：
struct PersonHash { size_t operator()(const Person& p) const { return std::hash<string>()(p.name) ^ std::hash<int>()(p.age); } };6.set和unordered_set的区别是什么
值得注意的是set和unordered_set都是去重的；
| 对比维度 | std::set | std::unordered_set |
|---|---|---|
| 底层数据结构 | 红黑树（自平衡二叉搜索树） | 哈希表（数组 + 链表） |
| 元素顺序 | 自动升序排序 | 完全无序（不保证任何顺序） |
| 查找时间复杂度 | O(log n) | O(1) 平均，最坏 O(n) |
| 插入时间复杂度 | O(log n) | O(1) 平均，最坏 O(n) |
| 删除时间复杂度 | O(log n) | O(1) 平均，最坏 O(n) |
| 迭代器稳定性 | ✅ 插入/删除时已有迭代器不失效 | ❌ 扩容（Rehash）时所有迭代器失效 |
| 是否支持范围查询 | ✅ 支持（lower_bound/upper_bound） | ❌ 不支持 |
| 内存开销 | 每个节点额外存 3 个指针（父、左、右）+ 颜色位（约 32 字节） | 桶数组预分配（空桶也占内存）+ 链表节点指针 |
| 自定义类型要求 | 必须重载operator< | 必须特化std::hash+ 重载operator== |
| 适用场景 | 需要排序、范围查询、迭代器长期持有 | 只关心快速增删查改，不关心顺序 |
实际开发使用频率 | 较少（特定场景） | 极高（绝大多数场景首选） |
为什么set的查找、插入、删除的时间复杂度是Ologn,而unordered_set的时间复杂度是O(1)？
这是因为set是需要排序的，而unordered_set是不需要排序，所以查找效率最高；
为什么unordered_set的时间复杂度最坏情况是O(N)?
因为unordered_set是hash,而哈希函数可能把所有元素都映射到同一个桶（Bucket）里，导致查找时退化成遍历链表，复杂度从 O(1) 变成 O(n)。
7.什么是map
map 是一种容器，存的是"键值对（Key-Value）"，通过 Key 快速查找对应的 Value。就像"通讯录"：输入名字（Key），查到手机号（Value）。set的名字叫做集合，map叫做映射。map和set一样，map的底层使用也是红黑树，也是有序的，map和set的区别是map从set的单个元素变成了键值对，map是按照key排序。
8.map在面试中常有的面试问题
①map和set的区别是什么
set只存key，只关心元素在不在，而map存了key和value的键值对，可以通过key查找value;
②map和unordered_map的区别
| 对比维度 | std::map | std::unordered_map |
|---|---|---|
| 底层 | 红黑树 | 哈希表 |
| 顺序 | 按 Key 自动排序 | 完全无序 |
| 查找 | O(log n) | O(1) 平均，最坏 O(n) |
| 迭代器稳定性 | 插入不失效 | 扩容时失效 |
| 适用场景 | 需要排序、范围查询 | 只关心快速查找 |
③map 的 [] 操作符和 insert 有什么区别？
| 操作 | 行为 | 返回值 |
|---|---|---|
map[key] = value | Key 不存在则插入；Key 存在则覆盖Value | 返回 Value 的引用 |
map.insert({key, value}) | Key 不存在则插入；Key 存在则什么都不做 | 返回pair<iterator, bool>，bool表示是否插入成功 |
[]操作符有个陷阱：即使你只是读取map["不存在"]，它也会自动插入一个默认构造的 Value，这可能不是你想要的。所以查找时建议用find()而不是[];
// 错误方式 if (map["key"] == value) { ... } // 如果 "key" 不存在，会插入一个空值！ // 正确方式 auto it = map.find("key"); if (it != map.end() && it->second == value) { ... }④map 的迭代器会失效吗？什么时候失效？
| 容器 | 插入操作 | 删除操作 |
|---|---|---|
std::map | ✅不失效（红黑树链式结构） | ✅只失效被删除的那个迭代器 |
std::unordered_map | ❌可能失效（触发 Rehash 时全部失效） | ✅只失效被删除的那个迭代器 |
正确的处理方法
// 正确：先获取下一个迭代器，再删除 for (auto it = myMap.begin(); it != myMap.end(); ) { if (it->second < 0) { it = myMap.erase(it); // C++11 后 erase 返回下一个迭代器 } else { ++it; } }⑤map 的 Value 可以是任意类型吗
可以！Value 可以是任意类型：int、string、vector、甚至另一个map或自定义类。
因为 Map 的排序和查找只依赖Key，Value 只是跟着 Key 走的附加数据，不参与任何比较操作，所以没有任何限制。
⑥map 和 unordered_map 怎么选
| 场景 | 推荐 | 原因 |
|---|---|---|
| 需要 Key 有序（如排行榜、范围查询） | std::map | 红黑树天然有序 |
| 数据量小（< 100 个） | 都可以，差别不大 | - |
| 数据量大且只做查找 | std::unordered_map | 快得多 |
| 需要迭代器长期持有 | std::map | 插入不失效 |
| 担心哈希攻击 | std::map | 红黑树复杂度稳定 O(log n) |
⑦为什么std::map的 Key 不能修改？
因为修改 Key 会破坏红黑树的有序结构。如果允许修改，树可能不再满足"左 < 根 < 右"的规则，导致查找和遍历结果错误。
正确做法是：先删除，修改完，再插入。
// 错误（禁止） auto it = myMap.find("张三"); it->first = "张四"; // ❌ 编译报错！Key 是 const // 正确 auto it = myMap.find("张三"); int age = it->second; myMap.erase(it); myMap["张四"] = age; // 重新插入⑧multimap 和 map 的区别？
multimap允许重复 Key，即一个 Key 可以对应多个 Value。使用时注意：multimap不支持[]操作符，因为不知道你要访问的是哪一个 Value。
std::multimap<std::string, int> scores; scores.insert({"张三", 90}); scores.insert({"张三", 95}); // 允许！现在 "张三" 有两个成绩 // 遍历所有 "张三" 的成绩 auto range = scores.equal_range("张三"); for (auto it = range.first; it != range.second; ++it) { cout << it->second << " "; // 输出：90 95 }9.map和set的常用接口
| 操作 | Set（std::set<int>） | Map（std::map<string, int>） |
|---|---|---|
| 插入 | insert(x) | insert({key, value})或map[key] = value |
| 查找 | find(x) | find(key) |
| 删除 | erase(x)或erase(it) | erase(key)或erase(it) |
| 获取大小 | size() | size() |
| 判空 | empty() | empty() |
| 清空 | clear() | clear() |
| 遍历 | for (auto& x : s) | for (auto& p : m)（p.first是 Key，p.second是 Value） |
| 检查存在 | count(x)（返回 0 或 1） | count(key)（返回 0 或 1） |
| 获取元素 | ❌ 没有 | map[key]或map.at(key) |
