1.41、解释说明一下map和unordered_map

• • std::map
  采用红黑树（平衡二叉搜索树）实现，所有元素按键自动排序，保证有序性。
  这使得插入、查找、删除操作的时间复杂度均为O(log n)。
• • std::unordered_map
  采用哈希表实现，元素无序存储，键通过哈希函数映射到桶中，平均查找、插入、删除复杂度为O(1)，但最坏情况下可能退化为O(n)（哈希冲突严重时）。

性能对比

使用场景

• • 选择std::map的理由
  • • 需要保持元素按键排序（如范围查询、顺序遍历）。
  • • 对性能要求稳定，避免哈希冲突带来的最坏情况。
  • • 需要有序访问或自定义排序规则。
• • 选择std::unordered_map的理由
  • • 只关心键值映射，且对访问速度要求极高。
  • • 不需要元素排序，且希望平均常数时间复杂度。
  • • 键类型支持高效哈希函数。

额外说明

• • unordered_map通常占用更多内存，因为哈希表需要维护桶数组和处理冲突的链表或树结构。
• • map由于红黑树结构，内存利用更紧凑，但访问路径较长。
• • 哈希函数质量直接影响unordered_map性能，糟糕的哈希函数可能导致性能退化。
• • unordered_map迭代顺序不稳定，插入顺序或键值大小不影响遍历顺序。

简要总结

std::map是有序关联容器，基于红黑树，适合需要有序访问和稳定性能的场景；std::unordered_map是无序关联容器，基于哈希表，适合追求快速访问且不关心顺序的场景。

使用：

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

int main() {
    std::map<int, std::string> ordered_map;
    std::unordered_map<int, std::string> unordered_map;

    ordered_map[3] = "three";
    ordered_map[1] = "one";
    ordered_map[2] = "two";

    unordered_map[3] = "three";
    unordered_map[1] = "one";
    unordered_map[2] = "two";

    std::cout << "std::map iteration (ordered): ";
    for (const auto& [k,v] : ordered_map)
        std::cout << k << " ";
    std::cout << "\n";

    std::cout << "std::unordered_map iteration (unordered): ";
    for (const auto& [k,v] : unordered_map)
        std::cout << k << " ";
    std::cout << "\n";

    return 0;
}

输出示例：

std::map iteration (ordered): 1 2 3 
std::unordered_map iteration (unordered): 3 1 2 

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）