第六章 关联式容器

一、关于 set 的详细解答

1. set的底层结构是什么？

std::set 的底层结构通常是红黑树（Red-Black Tree）。

• 红黑树的性质：它是一种自平衡的二叉搜索树（BST）。通过颜色约束（红黑规则）和旋转操作，红黑树能够保证最长路径不超过最短路径的两倍，从而保证树的高度维持在 (O(\log N))。
• 性能保证：因此，set 的插入、删除、查找操作的时间复杂度稳定为 (O(\log N))。
• 补充：C++11 引入的 std::unordered_set 底层则是哈希表（Hash Table），平均时间复杂度为 (O(1))，但最坏情况为 (O(N))。

2. set中存储的数据元素特点是什么？

• 唯一性：set 中不允许存在重复元素（如果允许重复，需使用 multiset）。
• 有序性：元素在插入时会自动按照大小进行排序（默认升序，底层基于 < 运算符）。可以自定义比较器（仿函数）。
• 不可变性（Immutable）：set 的迭代器是 const_iterator，不允许通过迭代器修改元素的值。因为修改元素的值会破坏红黑树的结构（失去有序性），必须先删除再插入。
• 元素类型要求：存储的元素类型必须能够进行比较（支持 < 运算符，或者提供自定义的比较规则）。

3. set的插入，删除，遍历怎么操作？

• 插入：
  • insert(value)：插入元素。返回一个 pair<iterator, bool>。bool 表示是否插入成功（若元素已存在，返回 false）。
  • emplace(args...)（C++11）：原地构造，效率通常比 insert 高。
• 删除：
  • erase(value)：删除值为 value 的元素，返回删除的元素个数（对于 set 是 0 或 1）。
  • erase(iterator)：删除迭代器指向的元素。
  • erase(first, last)：删除迭代器区间 [first, last) 内的元素。
  • clear()：清空所有元素。
• 遍历：
  • 使用迭代器：for (auto it = s.begin(); it != s.end(); ++it)。
  • 范围 for 循环：for (const auto& val : s)。
  • 特性：由于底层是红黑树，迭代器的遍历本质上是中序遍历，因此遍历出来的结果天然是有序的。

4. set的应用场景有哪些？

• 去重与排序：例如统计一篇英文文章中出现了多少个不同的单词，并按照字典序输出。
• 存在性查找：例如黑名单/白名单系统，需要快速判断某个 IP 或用户 ID 是否存在。
• 集合运算：求两个集合的交集、并集、差集（可以使用 <algorithm> 中的 set_intersection 等函数）。

二、关于 map 的详细解答

5. map的底层结构是什么？

std::map 的底层结构同样是红黑树（Red-Black Tree）。

• 它是一棵平衡二叉搜索树，节点中存储的不再是单一元素，而是键值对（key-value pair）。
• 同样保证了插入、删除、查找的时间复杂度稳定为 (O(\log N))。

6. map中存储的数据元素特点是什么？

• 键值对（Key-Value）：存储的数据类型是 std::pair<const Key, T>。
• 键（Key）唯一：map 中不允许存在重复的键（如果允许重复键，需使用 multimap）。
• 键有序：元素在插入时，会按照**键（Key）**的大小自动排序（默认升序）。
• 键不可修改，值可修改：Key 被 const 修饰，绝对不能修改（修改会破坏树结构）；但 T（Value）是可以修改的。
• 元素类型要求：键的类型必须支持比较操作。

7. map的插入，删除，遍历怎么操作？

• 插入：
  1. insert(pair<const Key, T>(k, v)) 或 insert(make_pair(k, v))：返回 pair<iterator, bool>，bool 表示是否插入成功。
  2. map[key] = value;（最常用）：如果 key 不存在，会默认构造一个 value（如 0、空字符串）并插入，然后赋值；如果 key 已存在，则覆盖原来的值。
  3. emplace(k, v)（C++11）：原地构造，避免临时对象的拷贝，效率最高。
• 删除：
  • erase(key)：根据键删除，返回删除的元素个数（0 或 1）。
  • erase(iterator) / erase(first, last)：同 set。
• 遍历：
  • 迭代器：it->first 访问键，it->second 访问值。
  • C++17 结构化绑定（推荐）：for (const auto& [key, val] : myMap)。
  • 遍历结果同样是按 Key 有序的。

8. map的应用场景有哪些？

• 字典/映射：例如学号 -> 学生信息，身份证号 -> 个人信息。
• 词频统计：统计单词出现的次数（map<string, int> wordCount; wordCount[word]++;）。
• 需要有序输出的键值查找：例如按时间戳排序的事件记录，用时间戳作为 Key。
• 路由表、配置表等需要根据 Key 快速检索 Value 的场景。

三、进阶补充（面试高频考点）

1. map 和 unordered_map 的区别（必考）

2. 为什么 map 的 Key 不能被修改？

因为 map 底层是红黑树，红黑树是根据 Key 的大小关系来组织节点的。如果允许修改 Key，那么这棵树就会失去有序性，导致查找、插入等操作全部失效。因此标准库将 Key 设为 const。

3. map[key] 和 map.at(key) 的区别

• map[key]：如果 Key 不存在，会插入一个新的默认值对，并返回其引用。这可能导致意外的插入。
• map.at(key)：如果 Key 不存在，会抛出 std::out_of_range 异常，不会插入新元素。推荐在只读查找时使用 at() 或 find()。

4. 迭代器失效问题

• set / map（红黑树）：插入元素不会导致任何迭代器失效；删除元素只会导致指向被删除元素的迭代器失效，其他迭代器依然有效。
• unordered_set / unordered_map（哈希表）：插入元素可能引发扩容（Rehash），导致所有迭代器失效。