在C++中，unordered_map 和 map 都是用于存储键值对的关联容器，但它们在多个方面存在明显区别，下面为你详细介绍：

1. 底层数据结构

• map：map 基于红黑树（一种自平衡的二叉搜索树）实现。红黑树的每个节点包含一个键值对，并且左子树节点的键小于根节点的键，右子树节点的键大于根节点的键，同时通过一些规则（如节点颜色、旋转操作等）保证树的高度平衡，从而保证插入、删除和查找操作的时间复杂度稳定。
• unordered_map：unordered_map 基于哈希表实现。哈希表通过哈希函数将键映射到一个固定大小的数组（哈希桶）中，每个桶可以存储一个或多个键值对。当发生哈希冲突（即不同的键映射到同一个桶）时，通常使用链表或红黑树来处理冲突。

2. 元素顺序

• map：元素会按照键的大小进行排序，默认使用 < 运算符进行比较。这意味着当你遍历 map 时，元素会按照键的升序排列。例如，如果你插入键为 {3, 1, 2} 的元素，遍历 map 时会按照 1, 2, 3 的顺序输出。
• unordered_map：元素是无序的，不会按照键的任何顺序进行存储。元素的存储位置取决于哈希函数的计算结果，因此遍历 unordered_map 时元素的顺序是不确定的。

3. 时间复杂度

• 插入操作：
  • map：插入操作的时间复杂度为 $O(\log n)$，因为在红黑树中插入一个节点需要进行平衡操作，以保证树的高度平衡。
  • unordered_map：平均情况下，插入操作的时间复杂度为 $O(1)$，因为哈希表可以直接通过哈希函数计算出元素的存储位置。但在最坏情况下（如哈希冲突严重），时间复杂度可能会达到 $O(n)$。
• 查找操作：
  • map：查找操作的时间复杂度为 $O(\log n)$，因为需要在红黑树中进行二分查找。
  • unordered_map：平均情况下，查找操作的时间复杂度为 $O(1)$，通过哈希函数直接定位到元素所在的桶。最坏情况下时间复杂度为 $O(n)$。
• 删除操作：
  • map：删除操作的时间复杂度为 $O(\log n)$，因为需要在红黑树中找到要删除的节点并进行平衡操作。
  • unordered_map：平均情况下，删除操作的时间复杂度为 $O(1)$，但最坏情况下为 $O(n)$。

4. 空间复杂度

• map：由于红黑树需要额外的指针来维护节点之间的关系，因此空间复杂度相对较高，大约为 $O(n)$。
• unordered_map：哈希表需要一个固定大小的数组（哈希桶），并且在处理哈希冲突时可能需要额外的空间（如链表或红黑树），因此空间复杂度也为 $O(n)$，但通常会比 map 占用更多的空间。

5. 迭代器

• map：map 的迭代器是双向迭代器，支持递增和递减操作，可以方便地遍历有序的元素。
• unordered_map：unordered_map 的迭代器是前向迭代器，只支持递增操作，并且由于元素无序，迭代器的遍历顺序是不确定的。

6. 适用场景

• map：适用于需要元素按照键的顺序进行遍历的场景，例如需要对数据进行排序输出、范围查找等。此外，当对数据的有序性有要求，并且插入、删除和查找操作的时间复杂度可以接受 $O(\log n)$ 时，使用 map 更为合适。
• unordered_map：适用于对元素顺序没有要求，更注重插入、查找和删除操作的平均时间复杂度为 $O(1)$ 的场景，例如缓存系统、哈希表实现等。

示例代码

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // 使用 map
    std::map<int, int> orderedMap;
    orderedMap[3] = 30;
    orderedMap[1] = 10;
    orderedMap[2] = 20;
    std::cout << "Map (ordered by key):" << std::endl;
    for (const auto& pair : orderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 使用 unordered_map
    std::unordered_map<int, int> unorderedMap;
    unorderedMap[3] = 30;
    unorderedMap[1] = 10;
    unorderedMap[2] = 20;
    std::cout << "\nUnordered map (unordered):" << std::endl;
    for (const auto& pair : unorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

在上述代码中，map 会按照键的升序输出元素，而 unordered_map 的输出顺序是不确定的。