C++map

C++ map 是 C++ STL 中的一个关联容器，它存储由键值（key）和映射值（value）组成的元素，并根据键自动排序。map 通常实现为红黑树，因此其查找、插入和删除操作的时间复杂度均为 $O(\log n)$。map 中的每个键都是唯一的，如果尝试插入重复键，新值将覆盖旧值。

基本特性

• 键值对存储：每个元素是一个 pair 对象，包含 key 和 value
• 自动排序：元素按 key 的升序排列（默认使用 std::less<Key>）
• 唯一键：容器中不允许有重复的 key
• 高效查找：基于红黑树实现，查找效率为对数时间

头文件

使用 map 需要包含头文件：

#include <map>

基本操作

声明与初始化

// 空map
std::map<std::string, int> wordCount;

// 初始化列表
std::map<int, std::string> idToName = {
    {1, "Alice"},
    {2, "Bob"},
    {3, "Charlie"}
};

插入元素

有三种主要插入方式：

std::map<int, std::string> m;

// 1. 使用insert和pair
m.insert(std::pair<int, std::string>(4, "David"));

// 2. 使用insert和make_pair
m.insert(std::make_pair(5, "Eve"));

// 3. 使用下标操作符
m[6] = "Frank";  // 如果键不存在会自动创建

访问元素

std::map<int, std::string> m = {{1, "Apple"}, {2, "Banana"}};

// 使用下标操作符（键不存在时会创建）
std::cout << m[1] << std::endl;  // 输出: Apple

// 使用at方法（键不存在时抛出异常）
std::cout << m.at(2) << std::endl;  // 输出: Banana

// 使用find方法（安全访问）
auto it = m.find(3);
if (it != m.end()) {
    std::cout << it->second << std::endl;
} else {
    std::cout << "Key not found" << std::endl;
}

删除元素

std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};

// 通过键删除
m.erase(2);  // 删除键为2的元素

// 通过迭代器删除
auto it = m.find(3);
if (it != m.end()) {
    m.erase(it);
}

// 删除所有元素
m.clear();

迭代器

map 提供双向迭代器：

std::map<int, std::string> m = {{1, "One"}, {2, "Two"}, {3, "Three"}};

// 正向迭代
for (auto it = m.begin(); it != m.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// 反向迭代
for (auto rit = m.rbegin(); rit != m.rend(); ++rit) {
    std::cout << rit->first << ": " << rit->second << std::endl;
}

// 范围for循环（C++11）
for (const auto& pair : m) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

容量查询

std::map<int, int> m = {{1, 10}, {2, 20}};

std::cout << "Size: " << m.size() << std::endl;      // 输出: 2
std::cout << "Empty: " << m.empty() << std::endl;    // 输出: 0 (false)
std::cout << "Max size: " << m.max_size() << std::endl;

性能分析

gantt title map操作时间复杂度 dateFormat X axisFormat %s section 操作 查找 : 0, 5 插入 : 5, 10 删除 : 10, 15

• 查找：$O(\log n)$
• 插入：$O(\log n)$
• 删除：$O(\log n)$

实际应用案例

单词统计

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

int main() {
    std::map<std::string, int> wordCount;
    std::string word;
    
    while (std::cin >> word) {
        ++wordCount[word];  // 自动初始化不存在的键为0
    }
    
    // 输出统计结果（按字母顺序）
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输入：

apple banana apple cherry banana apple

输出：

apple: 3
banana: 2
cherry: 1

学生成绩管理系统

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

class Student {
public:
    std::string name;
    int score;
    
    Student(std::string n, int s) : name(n), score(s) {}
};

int main() {
    std::map<int, Student> studentMap;
    
    // 添加学生（学号为键）
    studentMap.insert({1001, Student("Alice", 95)});
    studentMap[1002] = Student("Bob", 88);
    studentMap[1003] = Student("Charlie", 92);
    
    // 查询学生成绩
    int id = 1002;
    auto it = studentMap.find(id);
    if (it != studentMap.end()) {
        std::cout << "Student " << it->second.name 
                  << " (ID: " << it->first 
                  << ") has score: " << it->second.score << std::endl;
    } else {
        std::cout << "Student not found!" << std::endl;
    }
    
    return 0;
}

输出：

Student Bob (ID: 1002) has score: 88

高级特性

自定义比较函数

可以自定义键的排序规则：

struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char c1, char c2) { return tolower(c1) < tolower(c2); }
        );
    }
};

int main() {
    std::map<std::string, int, CaseInsensitiveCompare> wordMap;
    
    wordMap["Apple"] = 1;
    wordMap["banana"] = 2;
    wordMap["apple"] = 3;  // 会覆盖"Apple"
    
    for (const auto& pair : wordMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输出：

apple: 3
banana: 2

与unordered_map比较

map vs unordered_map

特性	map	unordered_map
实现方式	红黑树	哈希表
排序	按键排序	无序
查找时间	$O(\log n)$	平均$O(1)$，最坏$O(n)$
内存使用	通常较少	通常较多
迭代顺序	按键排序	不确定

常见问题

为什么使用map而不是vector<pair>?

• map 保证元素按键排序
• map 提供高效的查找操作（$O(\log n)$ vs vector的$O(n)$）
• map 提供方便的键值访问接口

如何选择map还是unordered_map?

• 需要有序数据 → 选择 map
• 需要最高效的查找 → 选择 unordered_map
• 内存受限 → 考虑 map
• 需要频繁遍历 → 两者均可，取决于是否需要有序

总结

C++ map 是一个强大的关联容器，它：

• 存储键值对并自动排序
• 提供高效的查找、插入和删除操作
• 保证键的唯一性
• 适用于需要按键快速查找和有序遍历的场景

掌握 map 的使用是 C++ 程序员的重要技能，它在许多实际应用中都能发挥重要作用，如配置管理、数据索引和统计等场景。