C++ 中 map/set 和 unordered_map/unordered_set 的底层实现是什么？

推荐答案

在C++中，map和set的底层实现通常是基于红黑树（Red-Black Tree），而unordered_map和unordered_set的底层实现则是基于哈希表（Hash Table）。

本题详细解读

map 和 set 的底层实现

• 红黑树：map 和 set 是基于红黑树实现的。红黑树是一种自平衡的二叉搜索树，它通过一些特定的规则来保持树的平衡，从而确保在最坏情况下，查找、插入和删除操作的时间复杂度为 O(log n)。
  • 红黑树的特性：
    1. 每个节点要么是红色，要么是黑色。
    2. 根节点是黑色。
    3. 每个叶子节点（NIL节点）是黑色。
    4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
    5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
  • 优点：红黑树的平衡性保证了操作的稳定性，适用于需要有序存储和快速查找的场景。

unordered_map 和 unordered_set 的底层实现

• 哈希表：unordered_map 和 unordered_set 是基于哈希表实现的。哈希表通过哈希函数将键映射到表中的特定位置，从而实现快速的查找、插入和删除操作。
  • 哈希表的特性：
    1. 哈希表通过哈希函数将键映射到桶（bucket）中。
    2. 当多个键映射到同一个桶时，通常使用链表或开放地址法来解决冲突。
    3. 在理想情况下，哈希表的查找、插入和删除操作的时间复杂度为 O(1)。
  • 优点：哈希表在平均情况下提供了非常高效的查找性能，适用于不需要有序存储的场景。

对比

• 有序性：map 和 set 是有序的，而 unordered_map 和 unordered_set 是无序的。
• 时间复杂度：map 和 set 的操作时间复杂度为 O(log n)，而 unordered_map 和 unordered_set 的操作时间复杂度在平均情况下为 O(1)。
• 适用场景：如果需要有序存储或频繁进行范围查询，使用 map 和 set 更为合适；如果只需要快速查找且不关心顺序，使用 unordered_map 和 unordered_set 更为高效。