[C++_] set | map | unordered

[C++_] set | map | unordered_map

前文回顾：

【C++】详解 set | multiset

【C++】关联容器探秘：Map与Multimap详解

在 C++ 中，map 和 unordered_map 都是存储键值对的关联容器，但它们的实现和特性有显著区别。如下：

1. 底层实现与有序性

map
基于红黑树（自平衡二叉搜索树）实现，元素按键的升序排列。插入、删除、查找操作的时间复杂度均为 O(log n)。
示例代码：

#include <map>
int main() {
    std::map<std::string, int> m;
    m["banana"] = 3;  // 插入无序
    m["apple"] = 5;
    m["cherry"] = 8;
    
    // 遍历时按键升序输出
    for (auto& pair : m)
        std::cout << pair.first << ": " << pair.second << std::endl;
    // 输出顺序：apple:5 → banana:3 → cherry:8
    return 0;
}

特点：有序性支持范围查询（如遍历时按顺序访问）[1] [5]。

unordered_map
基于哈希表实现，元素无序存储，查找、插入、删除的平均时间复杂度为 O(1)（最坏情况 O(n)）。
示例代码：

#include <unordered_map>
int main() {
    std::unordered_map<std::string, int> um;
    um["banana"] = 3;
    um["apple"] = 5;
    um["cherry"] = 8;
    
    // 遍历顺序不确定（依赖哈希函数）
    for (auto& pair : um)
        std::cout << pair.first << ": " << pair.second << std::endl;
    // 输出可能为：banana:3 → cherry:8 → apple:5
    return 0;
}

特点：查找速度快，但迭代顺序不可预测 [3] [5]。

2. 性能对比

特性	`map`	`unordered_map`
插入/查找时间复杂度	O(log n)	平均 O(1)，最坏 O(n)
内存占用	较高（红黑树节点额外存储信息）	较低（哈希表可能需预留空间）
适用场景	需要有序性或范围查询	高频查找且不关心顺序

3. 关键操作示例

// 查找元素
auto it_map = m.find("apple");
if (it_map != m.end()) 
    std::cout << "Found: " << it_map->second << std::endl;

// 哈希表查找（直接通过键访问）
int val = um["apple"];  // 若键不存在，自动插入默认值（如0）