怎样在C++中使用map和unordered_map？

在C++中使用map和unordered_map

map和unordered_map是C++标准库中的两种关联容器，用于存储键值对。它们的主要区别在于底层实现和性能特征：

map (std::map)

基于红黑树实现，保持元素按键排序。

基本用法

#include <iostream>
#include <map>
#include <string>

int main() {
    // 创建map
    std::map<std::string, int> ageMap;
    
    // 插入元素
    ageMap["Alice"] = 25;
    ageMap["Bob"] = 30;
    ageMap.insert({"Charlie", 28});
    
    // 访问元素
    std::cout << "Alice's age: " << ageMap["Alice"] << std::endl;
    
    // 检查元素是否存在
    if (ageMap.find("David") == ageMap.end()) {
        std::cout << "David not found" << std::endl;
    }
    
    // 遍历map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 删除元素
    ageMap.erase("Bob");
    
    return 0;
}

特点

元素按键排序（默认升序）
插入、删除、查找时间复杂度：O(log n)
需要键类型支持<操作或提供自定义比较函数

unordered_map (std::unordered_map)

基于哈希表实现，元素无序存储。

基本用法

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建unordered_map
    std::unordered_map<std::string, int> ageMap;
    
    // 插入元素
    ageMap["Alice"] = 25;
    ageMap["Bob"] = 30;
    ageMap.insert({"Charlie", 28});
    
    // 访问元素
    std::cout << "Alice's age: " << ageMap.at("Alice") << std::endl;
    
    // 检查元素是否存在
    if (ageMap.count("David") == 0) {
        std::cout << "David not found" << std::endl;
    }
    
    // 遍历unordered_map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 删除元素
    ageMap.erase("Bob");
    
    return 0;
}

特点

元素无序存储
平均情况下插入、删除、查找时间复杂度：O(1)
最坏情况下时间复杂度：O(n)
需要键类型支持哈希函数和==操作

选择建议

如果需要元素有序，使用map
如果追求更高性能且不需要排序，使用unordered_map
对于小数据集，两者性能差异不大
对于自定义类型作为键，map需要定义比较函数，unordered_map需要定义哈希函数

自定义键类型示例

#include <unordered_map>
#include <string>

struct Person {
    std::string name;
    int id;
    
    // 重载==运算符
    bool operator==(const Person& other) const {
        return name == other.name && id == other.id;
    }
};

// 自定义哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.id);
    }
};

int main() {
    std::unordered_map<Person, int, PersonHash> personMap;
    
    Person p1{"Alice", 1};
    Person p2{"Bob", 2};
    
    personMap[p1] = 25;
    personMap[p2] = 30;
    
    return 0;
}

希望这些示例能帮助你在C++中有效地使用map和unordered_map！