在 C++ 工程师的面试中，STL 中的 map 和 unordered_map 是常见的考察点。它们的用法、底层实现和性能差异等方面都会被重点考察。以下是一些典型的面试题：

1. map 和 unordered_map 的区别

• 问题: 请解释 map 和 unordered_map 之间的主要区别。
• 回答要点:
  • 底层实现:
    • map 是基于红黑树（自平衡二叉搜索树）实现的，键值对是有序的。
    • unordered_map 是基于哈希表实现的，键值对是无序的。
  • 查找、插入、删除的时间复杂度:
    • map 的时间复杂度为 O(log n)。
    • unordered_map 的平均时间复杂度为 O(1)，最坏情况是 O(n)。
  • 使用场景:
    • 使用 map 时需要保持键的有序性。
    • 使用 unordered_map 时更关注查找效率，而不关心键的顺序。

2. unordered_map 的哈希函数

• 问题: unordered_map 是如何确定每个键的存储位置的？你能自定义哈希函数吗？
• 回答要点:
  • unordered_map 使用哈希函数将键映射到存储桶中，默认使用 std::hash。
  • 可以通过模板参数自定义哈希函数和相等性比较函数。例如：

    struct MyHash {
        std::size_t operator()(const MyType& key) const {
            // 自定义哈希逻辑
        }
    };
    std::unordered_map<MyType, ValueType, MyHash> myMap;
    

3. map 和 unordered_map 的遍历顺序

• 问题: 在遍历 map 和 unordered_map 时，键值对的遍历顺序是什么样的？
• 回答要点:
  • map: 键值对按键的顺序（从小到大）遍历，因为底层是红黑树。
  • unordered_map: 键值对的遍历顺序是无序的，因为底层是哈希表，顺序取决于哈希函数和当前哈希表的状态。

4. map 和 unordered_map 的内存使用

• 问题: 讨论 map 和 unordered_map 的内存使用情况。哪种容器更节省内存？
• 回答要点:
  • map: 因为是基于红黑树实现的，每个节点额外存储父节点指针、左右子节点指针和颜色信息，因此内存开销较大。
  • unordered_map: 虽然需要存储哈希表的桶，但通常情况下比 map 更节省内存，尤其在大规模数据时，哈希表更节省空间。

5. 自定义类型作为键

• 问题: 如何在 map 和 unordered_map 中使用自定义类型作为键？
• 回答要点:
  • map: 自定义类型必须实现 operator< 以便在红黑树中比较键的大小。

    struct MyType {
        int a;
        bool operator<(const MyType& other) const {
            return a < other.a;
        }
    };
    std::map<MyType, ValueType> myMap;
    

  • unordered_map: 自定义类型必须提供哈希函数和相等性比较函数。

    struct MyType {
        int a;
        bool operator==(const MyType& other) const {
            return a == other.a;
        }
    };
    struct MyHash {
        std::size_t operator()(const MyType& key) const {
            return std::hash<int>()(key.a);
        }
    };
    std::unordered_map<MyType, ValueType, MyHash> myMap;
    

6. 性能优化

• 问题: 在使用 map 和 unordered_map 时，有哪些可以进行性能优化的策略？
• 回答要点:
  • 对于 map：
    • 预分配内存，减少内存分配的次数。
    • 如果可以确定键值对是有序插入的，避免无序插入导致的重平衡。
  • 对于 unordered_map：
    • 选择合适的初始大小，减少哈希表的扩展次数。
    • 使用自定义哈希函数，以减少冲突，优化查找时间。

7. 迭代器失效

• 问题: 讨论在 map 和 unordered_map 中迭代器失效的情况。插入和删除操作是否会使迭代器失效？
• 回答要点:
  • map: 插入操作不会使现有的迭代器失效，但删除操作会使指向被删除元素的迭代器失效。
  • unordered_map: 由于可能触发 rehash，插入操作可能会使所有迭代器失效。删除操作只会使指向被删除元素的迭代器失效。

8. unordered_map 最坏情况

• 问题: unordered_map 的最坏情况性能是什么？如何避免这种情况？
• 回答要点:
  • 最坏情况是所有键哈希到同一个桶中，导致查找、插入和删除的时间复杂度退化为 O(n)。
  • 可以通过选择合适的哈希函数，避免哈希冲突来减少最坏情况发生的概率。

9. 使用场景

• 问题: 在什么情况下你会选择 map，在什么情况下你会选择 unordered_map？
• 回答要点:
  • 选择 map：当你需要保持键的有序性时，如实现有序字典或基于范围查询的操作。
  • 选择 unordered_map：当你更关心查找和插入的速度，而不关心键的顺序时，如快速查找元素。

10. 容量管理

• 问题: unordered_map 如何管理其容量？你如何控制 unordered_map 的增长策略？
• 回答要点:
  • unordered_map 会自动管理其容量，并在负载因子超过一定阈值时进行扩展。
  • 可以使用 reserve 方法来预先分配内存，减少扩展次数，提高性能。